М етод минимизирующих карт.

Пусть задана формула своей СДНФ:

XYZXYZXYZ.

Составим таблицу следующим образом:

1. отведем три столбца для значений переменных, столбцы для значений формулы;

2. в первых трех столбцах приведем все возможные наборы переменных;

3. в столбцах для конъюнкций будем ставить десятичные эквиваленты двоичных чисел, соответствующих наборам значений переменных; например, в столбце для конъюнкции XY при X=0 и Y=0 ставим 0; при X=0 и Y=1 – 1; при X=1 и Y=0 – 2; при X=1 и Y=1 – 3 и т. д.;

   X	Y	Z	XY	XZ	YZ	XYZ	Значение формулы
   0	0	0	0	0	0	0	0
   0	0	1	0	1	1	1	0
   0	1	0	1	0	2	2	1
   0	1	1	1	1	3	3	0
   1	0	0	2	2	0	4	1
   1	0	1	2	3	1	5	0
   1	1	0	3	2	2	6	1
   1	1	1	3	3	3	7	0

4. вычеркиваем строки, где значение формулы равно 0;

5. в оставшихся строках вычеркиваем числа, которые вычеркнуты в том же столбце в предыдущей операции;

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

Получаем

YZXZXZYZXZYZ(XY)Z.

Соответствующая схема:

М етод Квайна.

Формула предварительно приводится к СДНФ. Далее применяются так называемые операции полного и неполного склеивания и поглощения.

Операцией полного склеивания называется преобразование XYXYX, а операция неполного склеивания отличается от предыдущей операции тем, что результат склеивания складывается с преобразуемой суммой XYXYXXYXY.

Тождественность результатов вытекает из соответствующих законов алгебры логики.

Операция поглощения производится согласно закону поглощения;

XXYX.

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

Полученное в результате выражение представляет собой сокращенную дизъюнктивную нормальную форму. Но она может не являться еще минимальной.

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

Пусть нам задана СДНФ:

X YZXYZXYZXYZXYZXYZXYZ

Над парами слагаемых произведем операции неполного склеивания, какие возможны. В этом выражении кривыми линиями соединены пары, к которым применима операция склеивания:

XYZXYZYZXYZXYZ;

XYZXYZXYXYZXYZ;

XYZXYZXZXYZXYZ;

XYZXYZXYXYZXYZ;

XYZXYZYZXYZXYZ;

XYZXYZXZXYZXYZ;

XYZXYZXZXYZXYZ;

XYZXYZXYXYZXYZ.

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

Произведем мысленно все операции поглощения. Получим сокращенную дизъюнктивную нормальную форму:

YZXYXZXYYZXZXZXY.

Для получения минимальной формы строим матрицу Квайна.

	XYZ	XYZ	XYZ	XYZ	XYZ	XYZ	XYZ
YZ	*		*
XY	*			*
XZ	*
XY		*	*
XZ		*		*
XZ			*			*
XZ				*			*
XY					*		*

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

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

Далее, нужно найти наименьшее число двухчленных конъюнкций, звездочки которых охватывают все столбцы матрицы. Один из таких вариантов отмечен на чертеже обводом звездочек кривыми. Сумма этих двухчленных конъюнкций и является минимальной дизъюнктивной нормальной формой данной формулы:

YZYZXZXY.

Прежде чем составить контактную схему, в двух первых слагаемых следует вынести Y за скобку:

Y(ZZ)XZXYYXZXY.

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

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

Возникает вопрос – до каких же пределов можно заниматься минимизацией релейно-контактных схем? Существуют ли критерии, позволяющие оценить построенную схему с точки зрения ее простоты?

Такие критерии имеются.

Обозначим количество контактов, необходимы для реализации формулы алгебры логики от n переменных, через L(n):

L(n)≤n2^n-1,

или L(n)≤32^n-1-2.

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

Но такая оценка является еще довольно грубой. Американский ученый Шенон обосновал следующий критерий, который является более строгим по отношению к двум предыдущим:

.

Однако, как установил математик О. Б. Лупанов, и такая оценка не является достаточно совершенной. Он доказал, что пределом для числа контактов в схеме, реализующей формулу алгебры логики от n переменных, является число, определяемое формулой:

Это выражение и является наиболее строгим критерием при оценке экономичности релейно-контактных схем.