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

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

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

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

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

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

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

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

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

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

Первому члену ДНФ поставлены в соответствие четыре клетки карты, второму – две клетки, третьему и четвертому − по одной клетке соответственно (рис.16). Далее объединение единиц в контуры и выбор их минимального числа осуществляются рассмотренным выше методом.

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

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

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