Минимальная дизъюнктивная нормальная форма
Минимальная дизъюнктивная нормальная форма (МДНФ) для логической функции — дизъюнкция с минимальным числом элементарных конъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции.
Для логической функции таблицы истинности и МДНФ совпадают.
Минимальная дизъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно. Для этого единицы карты Карно последовательно покрываются прямоугольниками 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)=1 — множество клеток t-прямоугольника из единиц;
argj(i, l) — значение аргумента xj в наборе аргументов для клетки (i, l);
fМДНФ(x1,x2,…,xn) — МДНФ логической функции.
Формула[править]
Примеры построения МДНФ[править]
Пример 1[править]
Строим карту Карно для функции трёх переменных:
- f(x1,x2,x3) = (01001101)
Единицы карты Карно минимально покрываются одним прямоугольником вида 1×2 и двумя прямоугольниками вида 2×1, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что два неполных прямоугольника вида 2×1 соответствуют одному полному прямоугольнику покрытия.
Пример 2[править]
Строим карту Карно для функции четырёх переменных:
- f(x1,x2,x3,x4) = (1111110110100000)
Единицы карты Карно минимально покрываются тремя квадратами вида 2×2, что соответствует трём элементарным конъюнкциям двух аргументов. Заметим, что четыре угловых неполных квадрата соответствуют одному полному квадрату покрытия.
Пример 3[править]
Строим трёхмерную карту Карно для функции пяти переменных:
- f(x1,x2,x3,x4,x5) = (00001010000001011100111110101111)
Единицы трёхмерной карты Карно минимально покрываются параллелепипедами вида 2×2×2, 2×2×1 (два), 1×4×1, 1×2×2, что соответствует одной элементарной конъюнкции двух аргументов и четырём элементарным конъюнкциям трёх аргументов. Заметим, что крайние по сторонам и угловые фигуры объединяются.
Другие формы:[править]