Контрольная работа: Булевы функции

Ú=ÚÚ

с появлением одного и того же элементарного произведения . Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

ÚÚ

Переходим к следующему этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы — конституентами единицы, т. е. членами СДНФ булевой функции.

Пример (продолжение). Импликантная матрица имеет вид (табл. 10).

Таблица 10.

Простые	Конституенты единицы
импликанты
	Х	Х	Х	Х
	Х	Х
	Х	Х

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 10). Минимальные ДНФ строятся по импликантной матрице следующим образом:

1) ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функции являются импликанты и . Импликанта - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

fmin=Ú

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2n-k, где k— число букв, содержащихся в простой импликанте.

Заметим также, что используя различные соотношения, можно расширить область применения метода Квайна за пределы совершенной ДНФ.

7.2 Метод Квайна-Мак-Класки

Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

1. Все конституенты единицы из СДНФ булевой функции fзаписываются их двоичными номерами.

2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.

3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна. Более подробно рассмотрим метод на примере решения следующей задачи: минимизировать методом Квайна-Мак-Класки булеву функцию f, заданную таблицей истинности (табл. 9).

1. В СДНФ функции fзаменим все конституенты единицы их двоичными номерами: f=0001Ú0011Ú0101Ú0111Ú1110Ú1111

2. Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.11).

3. Склеим номера из соседних групп табл.11. Склеиваемые номера обозначим звездочками (номер отмечается в том случае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которым произошло склеивание, проставляются прочерки. Результаты склеивания занесем в табл. 12. Склеим номера из соседних групп табл. 12. Склеиваться могут только номера, имеющие прочерки в одинаковых позициях. Склеиваемые номера отметим. Результаты склеивания занесем в табл. 13.

4. Имеем три простые импликанты: -111, 111-, 0--1.

Таблица 11 Таблица 12 Таблица 13

Номер группы

Двоичные номера кон-ституент 1

Номер группы

Двоичные номера импликант

Номер « 1 2 3 4 5 6 7 » К-во Просмотров: 557 Бесплатно скачать Контрольная работа: Булевы функции >>> Скачать <<< Меню Поиск