Метод Куайна
Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.[1][2][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 |
СДНФ выглядит так:
Результат операции склеивания нужен для преобразования функции на втором этапе (поглощения)
Членами результата склеивания являются
Член поглощает те члены исходного выражения, которые содержат , то есть первый и четвёртый. Эти члены вычёркиваются. Член поглощает второй и третий, а член — пятый член исходного выражения.
Повторение обеих операций приводит к следующему выражению:
Здесь склеивается пара членов и (склеивание пары членов и приводит к тому же результату), результат склеивания поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)
![](../I/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0_%D0%BB%D0%BE%D0%B3%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D1%83%D1%81%D1%82%D1%80%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%B1%D0%B0%D0%B7%D0%B8%D1%81%D0%B5_%D0%98%252C_%D0%98%D0%9B%D0%98%252C_%D0%9D%D0%95_%D0%BF%D1%80%D0%B8_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%9A%D0%B2%D0%B0%D0%B9%D0%BD%D0%B0.PNG.webp)
Члены сокращённой формы (в нашем случае это и ) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.
Второй этап (табличный) (получение минимальной формы)
Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации — удаление таких переменных. Таблица, представленная ниже, содержит значения истинности функции. По ней будет собрана следующая СДНФ.
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 |
СДНФ, собранная по этой таблице выглядит следующим образом:
Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.
Импликантная матрица
Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта поглощает члены и (в первом и во втором столбцах поставлены крестики).
Простая импликанта | ||||||
---|---|---|---|---|---|---|
Вторая импликанта поглощает первый и третий члены СДНФ (указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
В нашем примере ядро составляют импликанты и (ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член.
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту .
Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:
![](../I/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D0%B0%D1%8F_%D1%81%D1%85%D0%B5%D0%BC%D0%B0%252C_%D1%81%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D1%83%D1%8E%D1%89%D0%B0%D1%8F_%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8E_%D0%B2_%D0%9C%D0%94%D0%9D%D0%A4_(%D0%B2%D1%82%D0%BE%D1%80%D0%BE%D0%B9_%D1%8D%D1%82%D0%B0%D0%BF)_%D0%BF%D1%80%D0%B8_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%BC_%D0%9A%D0%B2%D0%B0%D0%B9%D0%BD%D0%B0.PNG.webp)
Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант и . Покажем допустимость подобного исключения членов из логического выражения.
Импликанты и становятся равными лог. 1 соответственно при следующих наборах значений аргументов: , , и , , .
Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:
- при , ,
;
- при , ,
;
Использование метода для получения минимальной КНФ
Для получения Минимальной конъюнктивной нормальной формы (МКНФ), используя метод Куайна, вводятся следующие критерии:
- для минимизации берётся не СДНФ, а СКНФ функции;
- склеиваемые пары членов меняются на: или ;
- правило операции поглощения выглядит следующим образом:
См. также
Примечания
- Краткое описание метода Квайна www.ptca.narod.ru
- Лекция: Минимизация ФАЛ Архивная копия от 14 апреля 2009 на Wayback Machine www.works.tarefer.ru
- Пример минимизации переключательной функции методом Квайна matri-tri-ca.narod.ru