Лекция №6
6.1 Метод Квайка – Мак-Класски нахождения
сокращённой ДНФ двоичной функции.
Пусть функция f задана в виде СДНФ. Метод, предложенный Квайком в 1952 г. заключается в следующем:
- применим к элементарным конъюнкциям СДНФ операцию «неполного склеивания»:
,
до тех пор, пока в результате применения этой операции не перестанут появляться новые конъюнкции;
2. в полученной ДНФ выполняем операции поглощения:
, пока это возможно.
Теорема 6.1.1: В результате выполнения пунктов 1, 2 получается сокращённая ДНФ функции f.
Доказательство: Сначала заметим, что из всякой импликанты функции f можно с помощью «операции расклеивания» 
получить дизъюнкцию импликант длины n.
Поскольку все импликанты длины n входят в СДНФ, то в результате применения операции неполного склеивания в СДНФ на первом этапе (пункт 1) метода будут получены все, в том числе и простые, импликанты функции f.
После применения второго этапа (пункт 2), очевидно, в ДНФ останутся только простые импликанты, т.е. полученная в результате ДНФ будет сокращенной.
Теорема доказана.
Мак-Класски в 1956 г. предложил удобную интерпретацию этого метода. Прежде всего заметим, что склеиваться могут только конъюнкции одинакового ранга, отличающиеся по одной переменной. Будем записывать конъюнкции 
в виде вектора (
).
Индексом конъюнкции назовём 
.
Учитывая это замечание, разобьём все импликанты в СДНФ на группы в соответствии со значениями их индексов. Сам метод при этом заключается в заполнении таблицы специального вида.
Пример 6.1.2. Пусть f – функция, геометрическое представление которой дано на рисунке 5.2.1. Её СДНФ имеет вид:
Имеем
| Индекс | СДНФ | Шаг 1 | Шаг 2 | Шаг 3 |
 1000*
| 1_00* 10_0* | 1__0 | ______ | |
| 1100* 1010* 0101* 0011* | 11_0* 1_10* 101_ 01_1 _011 0_11 | ______ | ______ | |
| 1110* 1011* 0111* | ______ | ______ | ______ |
Таблица 6.1.3.
Применяя операцию неполного склеивания к импликантам длины n (СДНФ) производим заполнение колонки таблицы. При этом в СДНФ звёздочкой отмечаются использованные импликанты (они будут поглощаться на втором этапе). Затем операция склеивания применяется к конъюнкциям ранга (n-1) и т.д. Как только заполнение таблицы прекратилось, выбираются все не отмеченные звёздочкой импликанты и из них составляется сокращённая ДНФ. Для рассмотренного примера сокращённой ДНФ будет:
.
6.2 Метод нахождения тупиковых ДНФ.
Для изложения метода нахождения тупиковых ДНФ нам потребуется одно свойство ДНФ монотонных функций.
Утверждение 6.2.1: Минимальная ДНФ монотонной функции совпадает с её сокращённой ДНФ.
Доказательство: Сначала покажем, что все простые импликанты монотонной функции не содержат переменных с отрицаниями. Действительно, в противном случае наряду с простой импликантой 
функция имела бы импликанту 
(в силу её монотонности). Склеивая эти две импликанты, получаем противоречие с простотой импликанты 
.
Покажем теперь, что все простые импликанты входят в минимальную ДНФ. Пусть 
- простая импликанта. Тогда на наборе 
импликанта 
принимает значение 1. Все остальные импликанты должны быть равны на этом наборе нулю, так как в них обязательно должны входить переменные из множества 
. Следовательно, импликанта должна входить в минимальную ДНФ, поскольку иначе функция f на этом наборе будет равна 0.
Утверждение доказано.
Метод Петрика нахождения тупиковых ДНФ.
Рассмотрим таблицу, строки которой соответствуют простым импликантам функции f, а столбцы – конъюнкциям совершенной ДНФ (СДНФ). В каждую клетку записываем единицу, если соответствующая простая импликанта поглощает элементарную конъюнкцию и ноль – в противном случае. Такая таблица называется «импликантной таблицей».
Для функции из примера 6.1.2 она имеет вид:
| СДНФ Сокр. ДНФ | |||||||||
| P1 | 1__0 | ||||||||
| P2 | 101_ | ||||||||
| P3 | _001 | ||||||||
| P4 | 0_11 | ||||||||
| P5 | 01_1 |
Таблица 6.2.2
Согласно определению, каждая тупиковая ДНФ определяется таким набором строк, что в таблице, образованной этими строками в каждом столбце имеется одна единица, причём из этого набора нельзя удалить ни одной строки так, чтобы при этом ни один столбец не стал нулевым.
Пусть в общем случае в таблице имеется N столбцов и m строк. Поставим в соответствие простым импликантам сокращённой ДНФ переменные P1 … Pm. Фиксируем некоторую дизъюнкцию простых импликант. Будем считать, что Pi = 1, если i-ая простая импликанта
входит в эту дизъюнкцию и Pi = 0, в противном случае. Запишем в виде формалы условие того, что рассматриваемая дизъюнкция является ДНФ функции. Для этого необходимо, чтобы в каждом столбце таблицы была хотя бы одна единица, т.е.
(6.2.3) 
,
где 
– элемент матрицы (таблицы), стоящий в i-ой строке и j-м столбце, 
.
Эту формулу можно трактовать как КНФ некоторой двоичной функции от переменных P1 … Pm, которая принимает значение 1 только на тех наборах переменных, которые соответствуют некоторым ДНФ исходной функции, и значение 0 – на наборах, которые соответствуют наборам импликант, не являющихся ДНФ исходной функции.
Заметим, что функция 
монотонна, так как формула 6.2.3 не содержит переменных с отрицаниями. Поэтому согласно утверждению 6.2.1 для нахождения её сокращённой ДНФ достаточно раскрыть скобки в формуле 6.2.3, а затем произвести все поглощения. Наконец, остаётся заметить, что в силу указанного выше свойства этой функции, её простые импликанты и только они будут давать тупиковые ДНФ исходной функции f.
Для таблицы 6.2.2 функция 
равна:
Отсюда P1P3P5 даёт для f тупиковую форму: 
,
а P1P2 P4P5 даёт: 
.