Метод Куайна

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

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

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

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

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

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

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

$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})={\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 {{\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 {\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 {\overline {x_{3}}}$ поглощает те члены исходного выражения, которые содержат $x_{2}\cdot {\overline {x_{3}}}$, то есть первый и четвёртый. Эти члены вычёркиваются. Член $x_{1}\cdot {\overline {x_{2}}}$ поглощает второй и третий, а член $x_{1}\cdot x_{3}$ — пятый член исходного выражения.

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

$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 {\overline {x_{2}}}$ и $x_{1}\cdot x_{2}$ (склеивание пары членов $x_{1}\cdot {\overline {x_{3}}}$ и $x_{1}\cdot x_{3}$ приводит к тому же результату), результат склеивания $x_{1}$ поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)

$f(x_{1},x_{2},x_{3})=x_{2}\cdot {\overline {x_{3}}}\lor x_{1}$

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

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

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

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

$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})={\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}$ ${\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}$

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

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

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

Простая импликанта	${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot {\overline {x_{4}}}$	${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}\cdot x_{4}$	${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}\cdot {\overline {x_{4}}}$	${\overline {x_{1}}}\cdot x_{2}\cdot x_{3}\cdot {\overline {x_{4}}}$	$x_{1}\cdot x_{2}\cdot x_{3}\cdot {\overline {x_{4}}}$	$x_{1}\cdot x_{2}\cdot x_{3}\cdot x_{4}$
${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}$	$\times$	$\times$
${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{4}}}$	$\times$		$\times$
${\overline {x_{1}}}\cdot x_{3}\cdot {\overline {x_{4}}}$			$\times$	$\times$
$x_{2}\cdot x_{3}\cdot {\overline {x_{4}}}$				$\times$	$\times$
$x_{1}\cdot x_{2}\cdot x_{3}$					$\times$	$\times$

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

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

Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{4}}}$ и $x_{2}\cdot x_{3}\cdot {\overline {x_{4}}}$. Покажем допустимость подобного исключения членов из логического выражения.

Импликанты ${\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{4}}}$ и $x_{2}\cdot x_{3}\cdot {\overline {x_{4}}}$ становятся равными лог. 1 соответственно при следующих наборах значений аргументов: $x_{1}=0$, $x_{2}=0$, $x_{4}=0$ и $x_{2}=1$, $x_{3}=1$, $x_{4}=0$.

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

• при $x_{1}=0$, $x_{2}=0$, $x_{4}=0$

$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_{3}=1$, $x_{4}=0$

$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 x$ или $w\vee {\overline {x}}$;
• правило операции поглощения выглядит следующим образом:

$z\cdot (z\vee y)=z\vee z\cdot y=z\cdot (1\vee y)=z$

См. также

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