М атрица Карно.

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

Матрицу будем составлять следующим образом. Построим таблицу с четырьмя столбцами и четырьмя строками и обозначим столбцы конъюнкциями XY, XY, XY, XY, строки – конъюнкциями ZU, ZU, ZU, ZU:

	XY	XY	XY	XY
ZU
ZU
ZU
ZU

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

XYZU; XYZU; XYZU; XYZU; XYZU, и т.д.

Таблица составлена так, что члены СДНФ, соответствующие соседним двум клеткам в столбце или строке, отличаются только одной переменной. Соседними в этом смысле являются также верхняя и нижняя клетки одного и того же столбца, левая и правая клетки одной и той же строки.

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

Пусть нам дана следующая СДНФ:

XYZUXYZUXYZUXYZUXYZUXYZUXYZU XYZUXYZUXYZU.

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

	XY	XY	XY	XY
ZU	*			*
ZU	*	*	*	*
ZU		*	*
ZU	*			*

Тогда четыре обведенных звездочки, расположенные в середине таблицы, дают YU (исключаются X и Z). Четыре верхние звездочки, расположенные по обе стороны таблицы, определяют YZ. Две нижние звездочки выражают YZU (исключается только одна переменная X).

Итак, минимальной дизъюнктивной нормальной формой нашей формулы является:

YUYZYZU.

Вынесение Y за скобку сокращает число контактов на единицу:

YUY(ZZU).

П риведем соответствующую контактную схему:

Она содержит лишь шесть контактов вместо 40, которые потребовались бы, если составлять схему непосредственно по СДНФ.

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

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

Пусть дана следующая формула своей совершенной дизъюнктивной нормальной формой:

XYZTUXYZTUXYZTUXYZTUXYZTUXYZTU XYZTUXYZTUXYZTUXYZTUXYZTU.

Составим таблицу, в которой столбцы соответствуют трехчленным конъюнкциям переменных X, Y, Z и их отрицаниям, строки двухчленным конъюнкциям T, U и их отрицаниям. Наборы значений расположены так, что соседние клетки в столбце или строк отличаются друг от друга лишь одной цифрой. Звездочки, поставленные в клетках, соответствуют членам совершенной дизъюнктивной нормальной формы.

		XYZ
		000	001	011	010	110	111	101	100
TU	00				*				*
	01		*	*
	11	*	*	*				*
	10	*						*

В соответствии с этой таблицей, составим две новые таблицы – одну для случая X=0, другую – для X=1.

		YZ
		00	01	11	10
TU	00				1
	01			*	*
	11		2 *	*	*
	10		*
X=0

		YZ
	3	00	01	11	10
TU	00	*			*
	01
	11		2 *
	10		*
X=1

Теперь уже значение X относится ко всей таблице, поэтому столбцы будут отражать лишь значения переменных Y и Z. Иначе говоря, первые цифры трехзначных чисел, обозначающих столбцы, выпадают и мы как бы получаем матрицы для четырех переменных Y, Z, T и U.

Четыре звездочки группы 1 в первой матрице означают исключение переменных Z и T, и вместо соответствующих четырех членов СДНФ остается один член, содержащий конъюнкцию YU. Во второй матрице на соответствующих столбцах звездочек не имеется, следовательно, переменная X не исключается.

В первой и второй матрицах в столбцах, помеченных набором 01, на одних и тех же местах имеются две звездочки (группа 2). Поскольку для первой матрицы X=0, а для второй X=1, то переменная X исключается. Меняются также значения второй цифры в наборах, отмечающих строки, исключается переменная U. Следовательно, вместо четырех членов СДНФ, соответствующих группе 2, остается член YZT.

Звездочки группы 3 находятся в одной и той же строке, поэтому переменные T и U не исключаются. В обозначениях столбцов меняется первая цифра, следовательно, исключается Y. Переменная X сохраняется, так как в первой матрице соответствующих звездочек не имеется. Таким образом, вместо двух членов СДНФ остается член XZTU.

Таким образом, минимальная дизъюнктивная нормальная форма данной формулы имеет вид:

XYUYZTXZTU.

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