Метод Куайна

Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:

• на первом этапе осуществляется переход от канонической формы (КДНФ или ККНФ) к так называемой сокращённой форме;
• на втором этапе — переход от сокращённой формы к минимальной форме.

Первый этап (получение сокращённой формы)Править

Представим, что заданная функция $f$$f$  представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:

1. Операция склеивания;
2. Операция поглощения.

Операция склеивания сводится к нахождению пар членов, соответствующих виду $w\cdot <!--\; \cdot \; -->x$$w \cdot x$  или $w\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x}$$w \cdot \overline{x}$ , и преобразованию их в следующие выражения: $w\cdot <!--\; \cdot \; -->x\vee <!--\; \vee \; -->w\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x}=w\cdot <!--\; \cdot \; -->(x\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x})=w$$w \cdot x \lor w \cdot \overline{x} = w \cdot (x \lor \overline{x}) = w$ . Результаты склеивания $w$$w$  теперь играют роль дополнительных членов. Необходимо найти все возможные пары членов (каждый член с каждым).

Потом выполняется операция поглощения. Она основана на равенстве $w\vee <!--\; \vee \; -->w\cdot <!--\; \cdot \; -->z=w\cdot <!--\; \cdot \; -->(1\vee <!--\; \vee \; -->z)=w$$w \lor w \cdot z = w \cdot (1 \lor z) = w$  (член $w$$w$  поглощает выражение $w\cdot <!--\; \cdot \; -->z$$w \cdot z$ ). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания.
Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо.
Применение этих операций продемонстрировано в таблице:

$x_1$$x_{1}$	$x_2$$x_{2}$	$x_3$$x_{3}$	$f(x_1,x_2,x_3)$$f(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

СДНФ выглядит так:

$f(x_1,x_2,x_3)=\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->x_3\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3$$f(x_1, x_2, x_3) = \overline{x_1} \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2} \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2} \cdot x_3 \lor x_1 \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot x_2 \cdot x_3$ 

Результат операции склеивания нужен для преобразования функции на втором этапе (поглощения)

$f(x_1,x_2,x_3)=\cancel{\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->x_3}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3}=x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_3\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2$$f(x_1, x_2, x_3) = \cancel{\overline{x_1} \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot \overline{x_2} \cdot \overline{x_3}} \vee \cancel{x_1 \cdot \overline{x_2} \cdot x_3} \vee \cancel{x_1 \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot x_2 \cdot x_3} = x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2$ 

Членами результата склеивания являются

$x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_3\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2$$x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2$ 

Член $x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$$x_2 \cdot \overline{x_3}$  поглощает те члены исходного выражения, которые содержат $x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$$x_2 \cdot \overline{x_3}$ , то есть первый и четвёртый. Эти члены вычёркиваются. Член $x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}$$x_1 \cdot \overline{x_2}$  поглощает второй и третий, а член $x_1\cdot <!--\; \cdot \; -->x_3$$x_1 \cdot x_3$  — пятый член исходного выражения.

Повторение обеих операций приводит к следующему выражению:

$f(x_1,x_2,x_3)=x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->x_3}\vee <!--\; \vee \; -->\cancel{x_1\cdot <!--\; \cdot \; -->x_2}\vee <!--\; \vee \; -->x_1$$f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \vee \cancel{x_1 \cdot \overline{x_2}} \vee \cancel{x_1 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot x_3} \vee \cancel{x_1 \cdot x_2} \vee x_1$ 

Здесь склеивается пара членов $x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}$$x_1 \cdot \overline{x_2}$  и $x_1\cdot <!--\; \cdot \; -->x_2$$x_1 \cdot x_2$  (склеивание пары членов $x_1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$$x_1 \cdot \overline{x_3}$  и $x_1\cdot <!--\; \cdot \; -->x_3$$x_1 \cdot x_3$  приводит к тому же результату), результат склеивания $x_1$$x_{1}$  поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)

$f(x_1,x_2,x_3)=x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1$$f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \lor x_1$ 

 

Структурная схема функции

Члены сокращённой формы (в нашем случае это $x_2\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$$x_2 \cdot \overline{x_3}$  и $x_1$$x_{1}$ ) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.

Второй этап (табличный) (получение минимальной формы)Править

Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации — удаление таких переменных. Таблица, представленная ниже, содержит значения истинности функции. По ней будет собрана следующая СДНФ.

$x_1$$x_{1}$	$x_2$$x_{2}$	$x_3$$x_{3}$	$x_4$$x_{4}$	$f(x_1,x_2,x_3,x_4)$$f(x_{1},x_{2},x_{3},x_{4})$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

СДНФ, собранная по этой таблице выглядит следующим образом:

$f(x_1,x_2,x_3,x_4)=\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\cdot <!--\; \cdot \; -->x_4\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->x_4$$f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot{x_4} \vee \overline{x_1} \cdot \overline{x_2} \cdot{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot x_4$  $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_3 \cdot \overline{x_4} \vee x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3$ 

Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.

Импликантная матрицаПравить

Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$  поглощает члены $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4}$  и $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\cdot <!--\; \cdot \; -->x_4$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4$  (в первом и во втором столбцах поставлены крестики).

Простая импликанта	$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot \overline{x_2} \cdot\overline{x_3} \cdot \overline{x_4}$	$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\cdot <!--\; \cdot \; -->x_4$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4$	$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot \overline{x_2} \cdot x_3 \cdot \overline{x_4}$	$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot x_2 \cdot x_3 \cdot \overline{x_4}$	$x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4}$	$x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->x_4$$x_1 \cdot x_2 \cdot x_3 \cdot x_4$
$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$	$\times <!--\; \times \; -->$$\times$	$\times <!--\; \times \; -->$$\times$
$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$	$\times <!--\; \times \; -->$$\times$		$\times <!--\; \times \; -->$$\times$
$\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$			$\times <!--\; \times \; -->$$\times$	$\times <!--\; \times \; -->$$\times$
$x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$x_2 \cdot x_3 \cdot \overline{x_4}$				$\times <!--\; \times \; -->$$\times$	$\times <!--\; \times \; -->$$\times$
$x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3$$x_1 \cdot x_2 \cdot x_3$					$\times <!--\; \times \; -->$$\times$	$\times <!--\; \times \; -->$$\times$

Вторая импликанта поглощает первый и третий члены СДНФ (указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.

В нашем примере ядро составляют импликанты $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}$${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$  и $x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3$$x_1 \cdot x_2 \cdot x_3$  (ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член.
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot x_3 \cdot \overline{x_4}$ .

Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:

 

Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна

$f(x_1,x_2,x_3,x_4)=\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->x_2\cdot <!--\; \cdot \; -->x_3\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee x_1 \cdot x_2 \cdot x_3 \vee \overline{x_1} \cdot x_3 \cdot \overline{x_4}$        (а)

Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$  и $x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$x_2 \cdot x_3 \cdot \overline{x_4}$ . Покажем допустимость подобного исключения членов из логического выражения.

Импликанты $\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_2}\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}$  и $x_2\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_4}$$x_2 \cdot x_3 \cdot \overline{x_4}$  становятся равными лог. 1 соответственно при следующих наборах значений аргументов: $x_1=0$$x_{1}=0$ , $x_2=0$$x_{2}=0$ , $x_4=0$$x_4 = 0$  и $x_2=1$$x_{2}=1$ , $x_3=1$$x_{3}=1$ , $x_4=0$$x_4 = 0$ .

Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции $f(x_1,x_2,x_3,x_4)$$f(x_{1},x_{2},x_{3},x_{4})$  значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:

• при $x_1=0$$x_{1}=0$ , $x_2=0$$x_{2}=0$ , $x_4=0$$x_4 = 0$ 

$f(0,0,x_3,0)=1\cdot <!--\; \cdot \; -->1\cdot <!--\; \cdot \; -->\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->0\cdot <!--\; \cdot \; -->0\cdot <!--\; \cdot \; -->x_3\vee <!--\; \vee \; -->1\cdot <!--\; \cdot \; -->x_3\cdot <!--\; \cdot \; -->1=\stackrel{¯<!--\; ¯\; -->}{x_3}\vee <!--\; \vee \; -->x_3=1$$f(0, 0, x_3, 0) = 1 \cdot 1 \cdot \overline{x_3} \vee 0 \cdot 0 \cdot x_3 \vee 1 \cdot x_3 \cdot 1 = \overline{x_3} \vee x_3 = 1$ ;

• при $x_2=1$$x_{2}=1$ , $x_3=1$$x_{3}=1$ , $x_4=0$$x_4 = 0$ 

$f(x_1,1,1,0)=\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->0\cdot <!--\; \cdot \; -->0\vee <!--\; \vee \; -->x_1\cdot <!--\; \cdot \; -->1\cdot <!--\; \cdot \; -->1\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}\cdot <!--\; \cdot \; -->1\cdot <!--\; \cdot \; -->1=x_1\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x_1}=1$$f(x_1, 1, 1, 0) = \overline{x_1} \cdot 0 \cdot 0 \vee x_1 \cdot 1 \cdot 1 \vee \overline{x_1} \cdot 1 \cdot 1 = x_1 \vee \overline{x_1} = 1$ ;

Использование метода для получения минимальной КНФПравить

Для получения Минимальной конъюнктивной нормальной формы (МКНФ), используя метод Куайна, вводятся следующие критерии:

• для минимизации берётся не СДНФ, а СКНФ функции;
• склеиваемые пары членов меняются на: $w\vee <!--\; \vee \; -->x$$w \vee x$  или $w\vee <!--\; \vee \; -->\stackrel{¯<!--\; ¯\; -->}{x}$$w \vee \overline{x}$ ;
• правило операции поглощения выглядит следующим образом:

$z\cdot <!--\; \cdot \; -->(z\vee <!--\; \vee \; -->y)=z\vee <!--\; \vee \; -->z\cdot <!--\; \cdot \; -->y=z\cdot <!--\; \cdot \; -->(1\vee <!--\; \vee \; -->y)=z$$z \cdot (z \vee y) = z \vee z \cdot y = z \cdot (1 \vee y) = z$ 

См. такжеПравить

• Куайн, Уиллард Ван Орман
• Метод Куайна — Мак-Класки
• Метод Петрика
• Карта Карно
• Конъюнктивная нормальная форма
• Дизъюнктивная нормальная форма