Рассмотрим правило покрытия 1.

Любой области из 2k смежных клеток можно поставить в соответствие конъюнкцию (n-k)-го ранга, состоящую из переменных, которые имеют постоянное значение во всех единичных наборах, соответствующих клеткам области.

Переменная x_i включается в конъюнкции в прямом виде, если эта переменная имеет значение 1 на всех клетках области.

Соответственно, переменная x_i включается в конъюнкции в инверсном виде, если она имеет значение 0 на всех клетках области.

Покрытая область на карте обводится контуром.

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

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

Дизъюнкция полученных конъюнкций является одной из тупиковых (возможно, минимальной) ДНФ функции.

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

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

Рассмотрим правило покрытия 2 .

Любой смежной области 2k клеток, заполненных нулями, можно поставить в соответствие дизъюнкцию (n-k)-го ранга, состоящую из переменных, которые имеют постоянное значение во всех нулевых наборах, соответствующих клеткам области.

Причем переменная xi входит в дизъюнкцию в прямом виде, если имеет значение 0 на всех клетках области, и, соответственно в инверсном виде, если она имеет значение 1 на всех клетках области.

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

Минимизация коньюнктивных нормальных форм переключательных функций

 

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

Конституентой нуля называется переключательная функция, принимающая значение нуля на одном наборе. Конституента нуля выражается дизъюнкцией всех переменных переключательной функции. Например, набору 0110 соответствует следующая конституента нуля: x₁v/x₂ v /x₃vx₄.

Имцлицентой g переключательной функции f называется функция, принимающая значение нуля на подмножестве нулевых наборов функции f.

Простой имплицентой переключательной функции f называется элементарная дизъюнкция, которая: является имплицентой функции f; никакая ее собственная часть не является имплицентой функции f.

Задачей минимизации КНФ является определение минимальной КНФ.

Данная задача также решается в два этапа:

Поиск сокращенной КНФ (конъюнкции всех простых имплицент);

Нахождение минимальной КНФ.

Для первого этапа минимизации КНФ (поиска всех простых имплицент), все методы минимизации ДНФ имеют свои аналоги для КНФ.

Второй этап минимизации КНФ выполняется с помощью таблицы Квайна точно так же, как при поиске минимальной ДНФ, поскольку возможны только два альтернативных варианта:

1) данная простая имплицента поглощает данную конституенту нуля в соответствии с соотношением поглощения (A v x)A = A;

2) данная простая имплицента не поглощает данную конституенту нуля.