Метод минимизирующих карт Карно (Вейча)

При минимизации логической функции от небольшого числа переменных удобным является графический метод представления функции с помощью диаграмм (карт) Вейча и их разновидности - Карно. Карта Вейча представляет собой развертку n-мерного куба на плоскости. При этом вершины куба представляются клетками карты, каждой из которых поставлена в соответствие конститутиента единицы или нуля. Переменные, обозначающие клетки диаграммы, расставляются таким образом, чтобы наборы, записанные в двух смежных клетках, имели кодовое расстояние, равное единице. Поскольку такие наборы располагаются в смежных клетках, они получили название соседних наборов. В клетку карты, соответствующую конститутиенте единицы, заносится 1 иначе 0. Таким образом, для минимизации функции она должна быть представлена в форме СДНФ. Минимизация булевой функции с использованием карт в дизъюнктивной (конъюнктивной) форме заключается в объединении единичных (нулевых) клеток в контуры, каждому такому контуру соответствует простая импликанта.

Можно сформулировать следующие правила минимизации:

• количество клеток карты в одном контуре должно быть равно 2ⁿ;

• для контура, содержащего 2ⁿ, клеток должно быть n осей симметрии;

• количество контуров должно быть минимально;

• число единиц в контуре должно быть максимально;

• контуры могут пересекаться, то есть некоторая клетка может входить в несколько контуров.

Рис. 15. Карта Вейча для f_СДНФ

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

Рассмотрим сказанное на примере функции

f_ДНФ=x₁x₂+ x₁x₂x₃+ x₁x₂x₃x₄+ x₁x₂x₃x₄

Первому члену ДНФ поставлены в соответствие четыре клетки карты, второму – две клетки, третьему и четвертому по одной клетке соответственно.

Далее объединение единиц в контуры и выбор их минимального числа осуществляется рассмотренным выше методом.

Рис. 17. Карта для инверсии функции

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

Рис. 18. Структура карты Карно

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