Минимальная конъюнктивная нормальная форма (МКНФ) для логической функции – это конъюнкция с минимальным числом элементарных дизъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции. При этом таблицы истинности для логической функции и её МКНФ совпадают.
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно. Для этого нули карты Карно последовательно покрываются прямоугольниками 4х2, 2х4, 2х2, 4х1, 1х4, 2х1, 1х2 и 1х1. Затем строятся элементарные дизъюнкты МКНФ.
Формула
Введём обозначения:
n – число аргументов функции;
k – число прямоугольников на карте Карно;
(x1,x2,…,xn) – набор аргументов функции;
f(x1,x2,…,xn) – логическая функция;
Pt(x1,x2,…,xn)={(i1,l1); (i2,l2); ...; (im,lm)} – множество клеток t-прямоугольника;
Pt(x1,x2,…,xn)=0 – множество клеток t-прямоугольника из нулей;
argj(i,l) – значение аргумента xj в наборе аргументов для клетки (i,l);
fМКНФ(x1,x2,…,xn) – МКНФ логической функции.
Пример 1
Строим карту Карно для функции трёх переменных
Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.
Пример 2
Строим карту Карно для функции четырёх переменных
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
