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

Формулу, в которую входит одна переменная, можно изобразить отрезком прямой, один конец которого будет соответствовать значению 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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.

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