Минимальная конъюнктивная нормальная форма
Минимальная конъюнктивная нормальная форма (МКНФ) для логической функции — это конъюнкция с минимальным числом элементарных дизъюнкций с минимальным числом аргументов (либо самих, либо их отрицаний) данной функции. При этом таблицы истинности для логической функции и её МКНФ совпадают.
Минимальная конъюнктивная нормальная форма для логической функции с числом аргументов до четырёх может быть построена с помощью карт Карно.
Для этого нули карты Карно последовательно покрываются прямоугольниками 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) — МКНФ логической функции.
Формула[править]
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_\text{МКНФ}(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,} где
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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}}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}}
Примеры построения МКНФ[править]
Пример 1[править]
Строим карту Карно для функции трёх переменных f(x1, x2, x3):
- f(x1,x2,x3)=(01001101)
Нули карты Карно минимально покрываются одним прямоугольником вида 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)}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_\text{МКНФ}(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)}
Пример 2[править]
Строим карту Карно для функции четырёх переменных
- f(x1,x2,x3,x4) = (1111110110100000)
Нули карты Карно минимально покрываются одним квадратом вида 2х2, одним прямоугольником вида 1х4 и одним прямоугольником вида 2х1, что соответствует трём элементарным дизъюнкциям, в двух из которых два аргумента, а в одной три аргумента.
- P1(x1,x2,x3,x4)={(3,2);(3,3);(4,2);(4,3)}
- P2(x1,x2,x3,x4)={(3,1);(3,2);(3,3);(3,4)}
- P3(x1,x2,x3,x4)={(2,4);(3,4)}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_\text{МКНФ}(x_1,x_2,x_3,x_4)=(\bar{x}_1\lor\bar{x}_2)\land(\bar{x}_1\lor\bar{x}_4)\land(\bar{x}_2\lor\bar{x}_3\lor x_4)}
Пример 3[править]
Строим трёхмерную карту Карно для функции пяти переменных
- f(x1,x2,x3,x4,x5) = (00001010000001011100111110101111)
Нули трёхмерной карты Карно минимально покрываются параллелепипедами вида 2х2х2, 1х4х1 (два), 2х2х1, 1х1х2, что соответствует одной элементарной дизъюнкции двух аргументов, трём элементарным дизъюнкциям трёх аргументов и одной элементарной дизъюнкции четырёх аргументов. Заметим, что соответствующие равные фигуры в разных таблицах объединяются.
- P1(x1,x2,x3,x4,x5)={(1,1,1);(1,2,1);(2,1,1);(2,2,1);(1,1,2);(1,2,2);(2,1,2);(2,2,2)}
- P2(x1,x2,x3,x4,x5)={(1,1,2);(1,2,2);(1,3,2);(1,4,2)}
- P3(x1,x2,x3,x4,x5)={(2,1,1);(2,2,1);(2,3,1);(2,4,1)}
- P4(x1,x2,x3,x4,x5)={(2,1,2);(2,2,2);(3,1,2);(3,2,2)}
- P5(x1,x2,x3,x4,x5)={(4,2,1);(4,2,2)}
- Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f_\text{МКНФ}(x_1,x_2,x_3,x_4,x_5)=(x_1\lor x_3)\land(x_1\lor x_2\lor\bar{x}_5)\land(x_1\lor\bar{x}_2\lor x_5)\land(\bar{x}_2\lor x_3\lor\bar{x}_5)\land(\bar{x}_1\lor x_2\lor x_3\lor\bar{x}_4)}