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

I. Нахождение первичных минитермов.

Пусть задана булева функция F(X1, X2, ..., Xn) в виде СДНФ или таблицы, по которой СДНФ легко строится. Выпишем все исходные минитермы ранга N, которые составляют СДНФ. При этом, вместо полной буквенной записи элементарной конъюнкции будем записывать только цифровой бинарный набор (σ1, σ2, ..., σn), и именно такие наборы будем "склеивать". Заметим, что минитермы могут быть склеены по переменной Xi, в том и только том случае, когда соответствующие им цифровые наборы (σ1, σ2, ..., σn) отличаются только по одной (I-ой) позиции. Отсюда видно, что если предварительно разбить минитермы на группы по количеству единиц в их бинарных наборах, то склеивания возможны только для минитермов соседних групп (у которых количество единиц отличается на 1).

Будем иллюстрировать шаги алгоритма на конкретном примере. Пусть . Здесь десятичными числами представлены наборы из области истинности функции . Выпишем их, разбивая на группы по количеству единиц.

Минитермы 4-го ранга (в скобках указано соответствующее десятичное число):

1 группа: 0100 (4),

2 группа: 0011 (3), 0101 (5), 1001 (9), 1100 (12),

3 группа: 0111 (7), 1011 (11), 1101 (13).

Сравнивая каждый минитерм 1-ой группы с каждым из 2-ой группы, а затем каждый из 2-ой с каждым из 3-ей, произведём склеивания, тогда, когда минитермы отличаются только в одной позиции, ставя на этой позиции прочерк: «—». Результаты склеивания – минитермы 3-го ранга снова распределим по группам. При этом одинаковые минитермы, если таковые возникают, достаточно записать лишь один раз. Минитермы, которые участвовали в операции склеивания (хотя бы один раз) будем отмечать подчёркиванием.

Минитермы 3-го ранга (в скобках указаны, какие минитермы склеивались):

1 группа: 010- (4-5), -100 (4-12),

2 группа: 0-11 (3-7), -011 (3-11), 01-1 (5-7), -101 (5-13), 10-1 (9-11), 1-01 (9-13), 110-(12-13).

Продолжаем склеивание до тех пор, пока это возможно.

Минитермы 2-го ранга:

1 группа: -10-.

Минитермы, которые не участвовали в склеивании (и оказались не подчёркнутыми) называются Первичными.

II. Расстановка меток.

Строим таблицу, в которой строчкам соответствуют найденные первичные минитермы, а столбцам исходные минитермы СДНФ. Затем в клетках таблицы ставим метки «+», если первичный минитерм покрывает (является частью записи) исходного минитерма. Для рассматриваемого примера получим следующую таблицу:

	0100	0011	0101	1001	1100	0111	1011	1101
0-11		+				+
-011		+					+
01-1			+			+
10-1				+			+
1-01				+				+
-10-	+		+		+			+

III. Нахождение существенных минитермов.

Если в каком либо столбце имеется только одна метка, то первичный минитерм из соответствующей строчки (в которой стоит данная метка) называется Существенным. Существенные минитермы обязательно войдут в окончательную формулу, так как в противном случае не все исходные минитермы будут покрыты и, значит, полученная формула не будет представлять заданную функцию.

В данном примере имеется два столбца с одной меткой, которым соответствует один и тот же существенный минитерм –10-.

IV. Вычёркивание лишних столбцов и строчек.

Из полученной выше таблицы вычёркиваем все строки с существенными минитермами, а так же все столбцы, которые покрываются существенными минитермами. Если после этого в таблице окажутся столбцы с одинаковой расстановкой меток, то они также вычёркиваются за исключением одного (если будет покрыт исходный минитерм в данном столбце, то будут покрыты и все другие минитермы с идентичной расстановкой меток).

В рассматриваемом примере после вычёркивания последней строки, первого, третьего, пятого и последнего столбцов, одинаковых столбцов не появится, и получим таблицу:			0011	1001	0111	1011
1)	0-11	+		+
2)	-011	+			+
3)	01-1			+
4)	10-1		+		+
5)	1-01		+

Если после IV шага в полученной таблице снова обнаруживаются существенные импликанты, то повторяем шаги III и IV до тех пор, пока не получим таблицу без существенных минитермов (или же таблица не окажется вычеркнутой полностью).

V. Вычёркивание лишних строчек.

Если в какой-либо строке не окажется ни одной метки, то вычеркиваем данную строку и соответствующую ей импликанту исключаем из дальнейшего рассмотрения.

В данном примере таких строк нет.

VI. Выбор минимального покрытия

Исследуя оставшуюся часть таблицы, выбираем такой минимальный набор первичных минитермов, которые покрывают все оставшиеся исходные минитермы (т. е. такие первичные минитермы, которые содержат метки во всех столбцах). При нескольких возможных вариантах, предпочтение отдаётся тому покрытию, первичные минитермы которого содержат наименьшее в совокупности количество букв (максимальное количество прочерков).

В данном примере таким покрытием будет: { 0-11, 10-1 }.

В общем случае, когда после V шага остается большая таблица, для отыскания минимального покрытия можно применить метод Петрика, записав условие на покрытие всех, оставшихся в таблице исходных минитермов в виде конъюнктивной формы и преобразовав её в дизъюнктивную форму. При этом будут найдены все возможные покрытия, из которых останется выбрать нужное (т. е. минимальное)

Внашем примере отождествляя первичные минитермы в последней таблице с их номерами по методу Петрика получим:

.

Из найденных четырех покрытий минимальным является покрытие, состоящее из первичных минитермов 1) и 4), которые уже были указаны выше.

Добавив к полученному покрытию найденные ранее существенные минитермы, получим ответ. В данном случае, переходя от бинарных наборов к соответствующим элементарным конъюнкциям, получим: .

< Предыдущая		Следующая >