2.2. Минимизация методом Квайна-Мак-Класки

Метод минимизации Квайна-Мак-Класки является одним из систематических методов, основанных на формализованном порядке упрощения формул. Метод описывается строгим алгоритмом, поддается программированию и его применение дает возможность использовать ЭВМ, что неизбежно при минимизации ФАЛ большого числа переменных.

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

Процедуру минимизации в соответствии с этим методом обычно выполняют по десятичным или двоичным эквивалентам конституент заданной функции.

Пусть функция задана своими единичными наборами, представленными десятичными кодами

f = {0,1,2,3,4,5,6,7,8,9,11,15}_{X 1X 2X 3X 4},

что соответствует аналитическому заданию функции алгебры логики

Наборы разбиваются на группы так, чтобы члены любой группы в своем двоичном представлении имели одинаковое число единиц (табл.4.12). Число единиц в двоичном коде можно назвать его весом, тогда все члены одной группы будут иметь одинаковый вес.

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

Таблица 4.12

Номер группы	X1	X2	X3	X4
0	0	0	0	0
1	0	0	0	1
2	0	0	1	0
4	0	1	0	0
8	1	0	0	0
3	0	0	1	1
6	0	1	1	0
9	1	0	0	1
7	0	1	1	1
11	1	0	1	1
15	1	1	1	1

Результаты сравнения приведены в табл.4.13. Каждый член, участвующий в сравнении, отмечен.

Наборы, не отмеченные в таблице, являются простыми импликантами.

Аналогично проведем следующий этап упрощения полученного в таблице результата, объединяя только те члены, у которых прочерк стоит в одном и том же разряде. Результаты сравнения представлены в табл.4.14. В этой таблице одинаковые члены можно вычеркнуть, после чего дальнейшее упрощение невозможно. В таблице остались не вычеркнутыми только простые импликанты.

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

В табл.4.15 выбирают столбцы, содержащие только один крест.

Таблица 4.13

Сравниваемые наборы	X1	X2	X3	X4
0,1 0,2 0,4 0,8	0 0 0 -	0 0 - 0	0 - 0 0	- 0 0 0
1,3	0	0	-	1
1,9	-	0	0	1
2,3	0	0	1	-
2,6	0	-	1	0
4,6	0	1	-	0
8,9	1	0	0	-
3,7	0	-	1	1
3,11	-	0	1	1
6,7	0	1	1	-
9,11	1	0	-	1
7,15	-	1	1	1
11,15	1	-	1	1

Простые импликанты, соответствующие столбцам с одним крестом, должны обязательно входить в минимальную ДНФ.

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

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

В рассматриваемом примере минимальная ДНФ для заданной функции имеет вид

Таблица 4.14

Сравниваемые наборы	X1	X2	X3	X4
0,1;2,3 0,1;8,9 0 ,2;1,3 0 ,2;4,6 0,4;2,6 0 ,8;1,9	0 - 0 0 0 -	0 0 0 - - 0	- 0 - - - 0	- - - 0 0 -
1,3;9,11	-	0	-	1
1 ,9;3,11	-	0	-	1
2,3;6,7	0	-	1	-
2 ,6;3,7	0	-	1	-
3,7;11,15	-	-	1	1
3 ,11;7,15	-	-	1	1

Таблица 4.15

Простые импликанты	Единичные наборы заданной функции
	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4	X1X2X3X4
	+	+	+			+
	+	+						+
	+		+				+
		+				+		+		+
			+			+	+		+
						+			+	+

В методе Квайна--Мак-Класки наиболее ценным является второй этап - нахождение простых импликант при помощи таблицы Квайна-Мак-Класки. Существенными преимуществами такой таблицы являются большая наглядность, сравнительная простота, надежность контроля. В целом этот метод минимизации целесообразно применять к функциям не более, чем 6-7 переменных.

При применении метода Квайна-Мак-Класки для получения минимальной конъюнктивной нормальной формы (МКНФ) функции алгебры логики имеются следующие особенности:

‑ пары склеиваемых членов имеют вид

‑ члены КСНФ представляют собой дизъюнкции переменных, которые имеют инверсные значения по сравнению с их значениями в наборах, на которых функция равна 0.