Минимизация логических функций методом Куайна

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

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

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

Представим, что заданная функция $\mathbf{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}$ (член $\mathbf{w}$ поглощает выражение ${w}\cdot{z}$). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания.
Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо.
Применение этих операций продемонстрировано в таблице:

$\mathbf{x_1}$	0	0	0	0	1	1	1	1
$\mathbf{x_2}$	0	0	1	1	0	0	1	1
$\mathbf{x_3}$	0	1	0	1	0	1	0	1
$\mathbf{f}({x_1},{x_2},{x_3})$	0	0	1	0	1	1	1	1

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

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

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

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

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

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

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

$\mathbf{f}({x_1},{x_2},{x_3})={x_2}\cdot\overline{x_3}$ $\lor{x_1}$

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

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

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

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

$\mathbf{x_1}$	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
$\mathbf{x_2}$	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
$\mathbf{x_3}$	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
$\mathbf{x_4}$	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
$\mathbf{f}({x_1},{x_2},{x_3},{x_4})$	1	1	1	0	0	0	1	0	0	0	0	0	0	0	1	1

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

$\mathbf{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}$.
Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:

Нажмите на изображение для его увеличения

$\mathbf{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 соответственно при следующих наборах значений аргументов: $\mathbf{x_1}$ = 0, $\mathbf{x_2}$ = 0, $\mathbf{x_4}$ = 0 и $\mathbf{x_2}$ = 1, $\mathbf{x_3}$ = 1, $\mathbf{x_4}$ = 0.
Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции $\mathbf{f}({x_1},{x_2},{x_3},{x_4})$ значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:

• при $\mathbf{x_1}$ = 0, $\mathbf{x_2}$ = 0, $\mathbf{x_4}$ = 0

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

• при $\mathbf{x_2}$ = 1, $\mathbf{x_3}$ = 1, $\mathbf{x_4}$ = 0

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

См. также

• Куайн, Уиллард Ван Орман
• Метод Куайна — Мак-Класки
• Карта Карно
• КНФ
• ДНФ

Примечания

1. ↑ Краткое описание метода Квайна www.ptca.narod.ru
2. ↑ Лекция: Минимизация ФАЛ www.works.tarefer.ru
3. ↑ Пример минимизации переключательной функции методом Квайна matri-tri-ca.narod.ru