Графический метод

Формулу, в которую входит одна переменная, можно изобразить отрезком прямой, один конец которого будет соответствовать значению 0, другой – значению 1.

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

В дальнейшем договоримся операцию Ù в членах СДНФ не писать, то есть XÙY будем записывать как XY.

На рисунке эти члены расположены так, что при переходе от одной вершины к любой соседней меняется только одна переменная.

При логическом сложении (дизъюнкции) двух членов, находящихся на концах какой-либо одной стороны квадрата, одна переменная будет исключаться. Так, при сложении XùY и XY переменная Y будет исключена и вместо суммы двух членов останется одна переменная X:

XùYÚXYºX(ùYÚY) ºX.

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

ùXùYÚXùYºùY; ùXùYÚùXYºùX; ùXYÚXYºY.

Это обстоятельство позволяет минимизировать формулы с двумя переменными, которые предварительно должны быть приведены к СДНФ.

1) Пусть нам дана такая СДНФ:

ùXYÚXYÚXùY.

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

Имея в виду изложенное выше, мы можем по чертежу сразу написать минимальную форму:

ùXYÚXYÚXùYºXÚY.

2) Пусть дана СДНФ:

X

ùXùYÚùXYÚXùYÚXY.

Все вершины квадрата отмечены жирными точками, стороны сплошными линиями.

Для замены этой формулы достаточно брать две любые противоположные стороны квадрата, т. к. ими охватываются все четыре вершины его. Получаем XÚùX или YÚùY. Любая сумма равна 1, следовательно формула тождественно истинна.

Формулы с тремя переменными удобно изображать кубом. Такое графическое выражение представляет собой весьма эффективное средство минимизации формул с тремя переменными.

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

XYùZÚXYZÚXùYZÚùXùYZ.

На рисунке изображен куб, соответствующий данной СДНФ.

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

XYùZÚXYZºXY(ùZÚZ)ºZY;

XYZÚXùYZºXZ(YÚùY)ºXZ;

XùYZÚùXùYZºùYZ(XÚùX)ºùYZ.

Следовательно, ребра куба соответствуют двухчленным конъюнкциям. Как видно из чертежа, все слагаемые данной формулы (все вершины куба, отмеченные жирными точками) охватываются двумя ребрами: XY и ùYZ. Таким образом, XYùZÚXYZÚXùYZÚùXùYZºXYÚYùZ.

Данная формула реализуется минимальной контактной схемой, содержащей четыре контакта:

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

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

Матрицу будем составлять следующим образом. Построим таблицу с четырьмя столбцами и четырьмя строками и обозначим столбцы конъюнкциями ù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
TU					*				*
		*	*
		*	*	*				*
		*						*

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

		YZ
TU
			*	*
			*	*	*
			*
X=0

		YZ
					10
TU	00	*			*
			*
			*
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.

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