Минимальная дизъюнктивная нормальная форма

Материал из Циклопедии
Перейти к: навигация, поиск
Минимизация функций. Карты Карно. Цифровая техника // EG Lab [14:20]

Минимальная дизъюнктивная нормальная форма (МДНФ) для логической функции — это дизъюнкция с минимальным числом элементарных конъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции. При этом таблицы истинности для логической функции и её МДНФ совпадают.

Минимальная дизъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно. Для этого единицы карты Карно последовательно покрываются прямоугольниками 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) — МДНФ логической функции.

[math]f_{МДНФ}(x_1,x_2,\ldots,x_n)=\bigcup\limits_{t=1}^k\bigcap\limits_{\begin{smallmatrix}\arg_j\left[P_t(x_1,x_2,\ldots,x_n)=1\right]=1 & \text{или}\\\arg_j\left[P_t(x_1,x_2,\ldots,x_n)=1\right]=0 &\end{smallmatrix}}y_j,[/math] где
[math]y_j=\begin{cases}x_j, \text{если}\ \arg_j\left[P_t(x_1,x_2,\ldots,x_n)=1\right]=1 \\ \bar{x}_j, \text{если}\ \arg_j\left[P_t(x_1,x_2,\ldots,x_n)=1\right]=0 \end{cases}[/math]
[math]\arg_j\left[P_t(x_1,x_2,\ldots,x_n)=1\right]=\begin{cases}1, \text{если}\ \forall(i,l)\in P_t(x_1,x_2,\ldots,x_n), \arg_j(i,l)=1 \\ 0, \text{если}\ \forall(i,l)\in P_t(x_1,x_2,\ldots,x_n), \arg_j(i,l)=0\end{cases}[/math]


Примеры построения МДНФ

Пример 1

Строим карту Карно для функции трёх переменных:

f(x1,x2,x3) = (01001101)

МДНФ21.JPG

Единицы карты Карно минимально покрываются одним прямоугольником вида 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)}
[math]f_{МНДНФ}(x_1,x_2,x_3)=(x_1 \land \bar{x}_2)\lor(x_1 \land x_3)\lor(\bar{x}_2 \land x_3)[/math]

Пример 2

Строим карту Карно для функции четырёх переменных:

f(x1,x2,x3,x4) = (1111110110100000)

МДНФ22.JPG

Единицы карты Карно минимально покрываются тремя квадратами вида 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)}
[math]f_{МНДНФ}(x_1,x_2,x_3,x_4)=(\bar{x}_1 \land \bar{x}_3)\lor(\bar{x}_1 \land x_4)\lor(\bar{x}_2 \land \bar{x}_4)[/math]

Пример 3

Строим трёхмерную карту Карно для функции пяти переменных:

f(x1,x2,x3,x4,x5) = (00001010000001011100111110101111)

МДНФ23.JPG

Единицы трёхмерной карты Карно минимально покрываются параллелепипедами вида 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)}
[math]f_{МНДНФ}(x_1,x_2,x_3,x_4,x_5)=(x_1 \land x_3)\lor(x_2 \land x_3 \land x_5)\lor(\bar{x}_2 \land x_3 \land \bar{x}_5)\lor(x_1 \land x_2 \land \bar{x}_5)\lor(x_1 \land \bar{x}_2 \land \bar{x}_4)[/math]

Другие формы

Ссылки

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты