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