Булевы функции (стр. 4 из 7)

Минимизация по методу Квайна выполняется по следующему алгоитму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл 9). Ее СДНФ имеет вид:

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции fкаким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2 ) конституента 2 с конституентой 4 и т. д. В результате получаем:

1-2:

1-3:

2-4:

3-4:

4-6:

5-6:

Заметим, что результатом склеивания является всегда элементарное произведение, представляющее собой общую часть склеиваемых конституент.

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

с появлением одного и того же элементарного произведения

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

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

Пример (продолжение). Импликантная матрица имеет вид (табл. 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	Номергруппы	Двоичные номераимпликант	Номергруппы	Двоичные номераимпликант
0	-	1 (1-2)	00-1 *	1	0--1
1	0001 *	0-01 *	0--1
2	0011 *	2 (2-3)	0-11 *	2	-111
0101 *	01-1 *	111-
3	0111 *	3 (3-4)	-111
1110 *	111-
4	1111 *

Таблица 14

Простые	Конституенты единицы
импликанты
(0--1)	Х	Х	Х	Х
(-111)	Х	Х
(111-)	Х	Х

5. Строим импликантную матрицу (табл. 14). По таблице определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам: