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

Карты Карно. Минимизация КНФ. Код Грея [10:14]

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

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

Для этого нули карты Карно последовательно покрываются прямоугольниками 4×2, 2×4, 2×2, 4×1, 1×4, 2×1, 1×2 и 1×1. Затем строятся элементарные дизъюнкты МКНФ.

Обозначения

n — число аргументов функции;

k — число прямоугольников на карте Карно;

(x₁, x₂, …, x_n) — набор аргументов функции;

f(x₁, x₂, …, x_n) — логическая функция;

P_t(x₁, x₂, …, x_n) = {(i₁, l₁); (i₂, l₂); …; (i_m, l_m)} — множество клеток t-прямоугольника;

P_t(x₁, x₂, …, x_n) = 0 — множество клеток t-прямоугольника из нулей;

arg_j(i, l) — значение аргумента x_j в наборе аргументов для клетки (i, l);

f_МКНФ(x₁, x₂, …, x_n) — МКНФ логической функции.

Формула

$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},$ где

$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}}$

$\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(x₁, x₂, x₃):

f(x₁,x₂,x₃)=(01001101)

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

P₁(x₁,x₂,x₃) = {(1,1);(2,1)}

P₂(x₁,x₂,x₃) = {(2,1);(3,1)}

P₃(x₁,x₂,x₃) = {(2,1);(2,2)}

$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(x₁,x₂,x₃,x₄) = (1111110110100000)

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

P₁(x₁,x₂,x₃,x₄)={(3,2);(3,3);(4,2);(4,3)}

P₂(x₁,x₂,x₃,x₄)={(3,1);(3,2);(3,3);(3,4)}

P₃(x₁,x₂,x₃,x₄)={(2,4);(3,4)}

$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(x₁,x₂,x₃,x₄,x₅) = (00001010000001011100111110101111)

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

P₁(x₁,x₂,x₃,x₄,x₅)={(1,1,1);(1,2,1);(2,1,1);(2,2,1);(1,1,2);(1,2,2);(2,1,2);(2,2,2)}

P₂(x₁,x₂,x₃,x₄,x₅)={(1,1,2);(1,2,2);(1,3,2);(1,4,2)}

P₃(x₁,x₂,x₃,x₄,x₅)={(2,1,1);(2,2,1);(2,3,1);(2,4,1)}

P₄(x₁,x₂,x₃,x₄,x₅)={(2,1,2);(2,2,2);(3,1,2);(3,2,2)}

P₅(x₁,x₂,x₃,x₄,x₅)={(4,2,1);(4,2,2)}

$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})$

Другие формы:

1. совершенная дизъюнктивная нормальная форма;
2. совершенная конъюнктивная нормальная форма;
3. минимальная дизъюнктивная нормальная форма;
4. минимальная конъюнктивная нормальная форма);
5. алгебраическая нормальная форма.