Метод
Куайна
— способ представления функции в
ДНФ
или
КНФ
с минимальным количеством членов и минимальным набором переменных.
Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от канонической формы (
или
) к так называемой
сокращённой форме
;
на втором этапе — переход от сокращённой формы к
минимальной форме
.
Содержание
Первый этап (получение сокращённой формы)
Представим, что заданная функция
представлена в
СДНФ
. Для осуществления первого этапа преобразование проходит два действия:
Операция склеивания
;
Операция поглощения
.
Операция склеивания сводится к нахождению пар членов, соответствующих виду
или
, и преобразованию их в следующие выражения:
. Результаты склеивания
теперь играют роль дополнительных членов. Необходимо найти все возможные пары членов (каждый член с каждым).
Потом выполняется
операция поглощения
. Она основана на равенстве
(член
поглощает выражение
). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в
операции склеивания
.
Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо.
Применение этих операций продемонстрировано в таблице:
Результат операции склеивания нужен для преобразования функции на втором этапе (поглощения)
Членами результата склеивания являются
Член
поглощает те члены исходного выражения, которые содержат
, то есть первый и четвёртый. Эти члены вычёркиваются. Член
поглощает второй и третий, а член
— пятый член исходного выражения.
Повторение обеих операций приводит к следующему выражению:
Здесь склеивается пара членов
и
(склеивание пары членов
и
приводит к тому же результату), результат склеивания
поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)
Члены сокращённой формы (в нашем случае это
и
) называются
простыми импликантами
функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией —
СДНФ
. Структурная схема такого элемента показана на рисунке справа.
Второй этап (табличный) (получение минимальной формы)
Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации — удаление таких переменных. Таблица, представленная ниже, содержит значения истинности функции. По ней будет собрана следующая
СДНФ
.
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
СДНФ
, собранная по этой таблице выглядит следующим образом:
Члены этого выражения являются
простыми импликантами
выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной
матрицы
.
Импликантная матрица
Члены
СДНФ
заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов
СДНФ
, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта
поглощает члены
и
(в первом и во втором столбцах поставлены крестики).
Простая импликанта
Вторая импликанта поглощает первый и третий члены
СДНФ
(указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют
ядро
. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
В нашем примере ядро составляют импликанты
и
(ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член.
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту
.
(МДНФ) заданной функции:
(а)
Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант
и
. Покажем допустимость подобного исключения членов из логического выражения.
Импликанты
и
становятся равными
лог. 1
соответственно при следующих наборах значений аргументов:
,
,
и
,
,
.
Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции
значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу
(а)
, получаем:
при
,
,
;
при
,
,
;
Использование метода для получения минимальной
КНФ
Для получения Минимальной конъюнктивной нормальной формы (МКНФ), используя метод Куайна, вводятся следующие критерии: