Метод Куайна (Bymk; Trgwug)

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

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

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

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

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

Операция склеивания сводится к нахождению пар членов, соответствующих виду $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$

См. также

Примечания

↑ Краткое описание метода Квайна Архивная копия от 20 февраля 2009 на Wayback Machine www.ptca.narod.ru
↑ Лекция: Минимизация ФАЛ Архивная копия от 14 апреля 2009 на Wayback Machine www.works.tarefer.ru
↑ Пример минимизации переключательной функции методом Квайна Архивная копия от 17 апреля 2010 на Wayback Machine matri-tri-ca.narod.ru

[Квайн-1] Краткое описание метода Квайна Архивная копия от 20 февраля 2009 на Wayback Machine www.ptca.narod.ru

[2] Лекция: Минимизация ФАЛ Архивная копия от 14 апреля 2009 на Wayback Machine www.works.tarefer.ru

[3] Пример минимизации переключательной функции методом Квайна Архивная копия от 17 апреля 2010 на Wayback Machine matri-tri-ca.narod.ru

[1]

[2]

[3]

$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

$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

$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