25. Метод Квайна. Метод Квайна-Мак-Класки.
Метод Квайна.
Метод основан на попарном сравнении и склеивании при возможности всех конституент (членов СДНФ). Для этого каждая конституента сравнивается с последующими, что приводит к получению импликант. Полученные импликанты вновь подвергаются сравнению и при возможности склеиваются – и т.д. до тех пор, пока оставшиеся импликанты уже не будут поддаваться склеиванию. Это и есть простые импликанты, их дизъюнкция представляет собой сокращенную ДНФ.
Для упорядочения целесообразно разбивать конституенты на группы по числу неинверсированных переменных. В этом случае каждая очередная конституента, начиная сверху, сравнивается только с конституентами группы, соседней снизу, с числом неинверсированных переменных на единицу больше.
Пусть имеется переключательная функция, заданная СДНФ:

Разобьем конституенты на группы по числу неинверсированных переменных.
Римская цифра номера группы соответствует числу неинверсных пе-ременных. Проведем линии, указывающие склеиваемые конституенты. Результатом склеивания является всегда элементарная конъюнкция, представляющая собой общую часть исходных конъюнкций (в частности, конституент).

Полученные импликанты также допускают склеивание, причем в ре-зультате получается одна и та же импликанта  .
Дальнейшие склеивания невозможны, поэтому полученные импликанты – простые, а сокращенная ДНФ имеет вид:

Первый этап выполнен. На втором этапе необходимо исключить лишние простые импликанты. Это делается с помощью специальной импликантной таблицы Квайна (таблицы покрытий). Строки таблицы отмечаются простыми импликантами переключательной функции, т.е. членами сокращенной ДНФ, а столбцы – конституентами единицы, т.е. членами СДНФ переключательной функции.
Как уже отмечалось, простая импликанта поглощает некоторую кон-ституенту единицы, если является ее собственной частью. Соответствую-щая клетка импликантной таблицы на пересечении строки данной простой импликанты и столбцов с конституентами единицы отмечается, например, знаком «+». Минимальные ДНФ строятся по импликантной таблице следующим образом:
1) ищутся столбцы импликантной таблицы, имеющие только один крестик, соответствующие этим крестикам простые импликанты называ-ются базисными и составляют так называемое ядро переключательной функции. Ядро обязательно входит в минимальную ДНФ;
2) рассматриваются различные варианты выбора совокупности про-стых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв.
Ядром нашей функции (табл. 35) являются импликанты   и х1х2х3, т.е. функция имеет единственную тупиковую и минимальную ДНФ:

Таблица 35
Импликантная таблица Квайна
Про-стые Конституенты 1 (члены СДНФ)
импли-канты
А
+ + + +   
В х2х3х4        +    +
С х1х2х3        + +

Видно, что импликанта х2х3х4 является лишней, так как она покры-вает конституенты, уже покрытые импликантами  , х1х2х3.
Число крестиков в строке является степенью числа 2; более того, можно убедиться, что оно равно N=2n-k, где k – число букв в простой импликанте, n – число переменных, от которых зависит функция.
Если вначале не задана СДНФ, то ее надо получить, используя, например, уже известные нам методы.
Ясно, что для больших импликантных таблиц трудно визуально вы-явить варианты с минимальным числом букв. Поэтому используется метод Петрика, позволяющий получать все тупиковые ДНФ по импликантной таблице путем построения так называемого конъюнктивного ее представления. Для этого все простые импликанты обозначаются разными буквами (А, В, С в табл. 35), а затем для каждого столбца строится дизъюнкция всех букв, обозначающих строки таблицы, пересечение которых с данным столбцом отмечено крестиком. Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов. К конъюнктивному представлению импликантной таблицы могут быть применены все соотношения булевой алгебры переключательных функций с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.

Это означает, что тупиковая ДНФ содержит две простые импликанты (  и одновременно С=х1х2х3) и имеет вид:

Метод Квайна-Мак-Класки.
Метод представляет собой формализацию метода Квайна, ориентированную на использование ЭВМ. Формализация заключается в записи конституент единицы (членов СДНФ) их двоичными номерами. Все номера разбиваются на непересекающиеся группы по числу единиц в двоичном номере. Склеивания производятся только между соседними группами. Ликвидируемый разряд обозначается знаком «–» («тире»). Дальнейшие группы из полученных импликант образуются с учетом однинакового расположения тире. Такое обозначение импликант называется обобщенными кодами. Пусть задана логическая функция

Сгруппируем эти конституенты единицы по числу единиц:

Дальнейшие склеивания невозможны. Нахождение минимальных ДНФ далее производится по импликантной таблице (табл. 36):

Это означает, что тупиковые ДНФ содержат по три простые импликанты и имеют вид:
  (две инверсии);
  (три инверсии).
Таблица 36
Импликантная таблица Квайна-Мак-Класки
Простые
импликанты Конституенты единиц
х1 х2 х3 111 101 001 000 110
А 0 0 -    + +
В - 0 1    + +   
С 1 - 1 + +   
D 1 1 - +        +

Заметим, что склеивание двух импликант с тире возможно только при соответствующем их расположении, например:
00--
01--

1-01
0101

Можно выбрать любую из полученных ТДНФ, а с учетом меньшего числа инверсий – первую.