Метод Куайна

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

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

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

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

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

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

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

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle 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

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

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

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

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

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

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

Член ${\displaystyle x_{2}\cdot {\overline {x_{3}}}}$ поглощает те члены исходного выражения, которые содержат ${\displaystyle x_{2}\cdot {\overline {x_{3}}}}$, то есть первый и четвёртый. Эти члены вычёркиваются. Член ${\displaystyle x_{1}\cdot {\overline {x_{2}}}}$ поглощает второй и третий, а член ${\displaystyle x_{1}\cdot x_{3}}$ — пятый член исходного выражения.

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

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

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

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

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

Второй этап (табличный) (получение минимальной формы)[править | править код]

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

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle x_{4}}$	${\displaystyle 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

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

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

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

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

Импликантная матрица[править | править код]

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

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

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

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

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

${\displaystyle 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}}}}$       (а)

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

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

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

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

${\displaystyle 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}$;

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

${\displaystyle 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}$;

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

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

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

${\displaystyle z\cdot (z\vee y)=z\vee z\cdot y=z\cdot (1\vee y)=z}$

См. также[править | править код]

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

Примечания[править | править код]