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

Материал из Циклопедии
(перенаправлено с «МКНФ»)
Перейти к: навигация, поиск
Карты Карно. Минимизация КНФ. Код Грея [10:14]

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

Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно.

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

[math]f_{МКНФ}(x_1,x_2,\ldots,x_n)=\bigcap\limits_{t=1}^k\bigcup\limits_{\begin{smallmatrix}\arg_j\left[P_t(x_1,x_2,\ldots,x_n)=0\right]=0 & \text{или}\\\arg_j\left[P_t(x_1,x_2,\ldots,x_n)=0\right]=1 &\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)=0\right]=0 \\ \bar{x}_j, \text{если}\ \arg_j\left[P_t(x_1,x_2,\ldots,x_n)=0\right]=1 \end{cases}[/math]
[math]\arg_j\left[P_t(x_1,x_2,\ldots,x_n)=0\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):

МКНФ21.JPG

Нули карты Карно минимально покрываются одним прямоугольником вида 1х2 и двумя прямоугольниками вида 2х1, что соответствует трём элементарным дизъюнкциям двух аргументов.

P1(x1,x2,x3) = {(1,1);(2,1)}
P2(x1,x2,x3) = {(2,1);(3,1)}
P3(x1,x2,x3) = {(2,1);(2,2)}
[math]f_{МКНФ}(x_1,x_2,x_3)=(x_1 \lor x_3)\land(\bar{x}_2 \lor x_3)\land(x_1 \lor \bar{x}_2)[/math]

[править] Пример 2

Строим карту Карно для функции четырёх переменных ЛФ41.JPG

МКНФ22.JPG

Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.

МКНФ12.JPG

[править] Пример 3

Строим трёхмерную карту Карно для функции пяти переменных ЛФ51.JPG

МКНФ23.JPG

Нули трёхмерной карты Карно минимально покрываются параллелепипедами вида 2х2х2, 1х4х1 (два), 2х2х1, 1х1х2, что соответствует одной элементарной дизъюнкции двух аргументов, трём элементарным дизъюнкциям трёх аргументов и одной элементарной дизъюнкции четырёх аргументов. Заметим, что соответствующие равные фигуры в разных таблицах объединяются.

МКНФ13.JPG

[править] Другие формы:

[править] Ссылки

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

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