Метод Квайна

Метод Квайна для минимизации ФАЛ в классическом базисе был рассмотрен в главе 1. Все сказанное там о принципах метода и последовательности выполнения этапов минимизации остается в силе. Только здесь неотмеченные минитермы будут простыми инверсантами функции и необходимо учитывать возможное вырождение минитермов, сопровождающееся инвертированием оставшейся переменной.

Пример 2-3. Найти минимальную нормальную форму для следующей совершенной нормальной формы функции:

Минитермы третьего ранга

Используем соотношение (2-10) и производим все возможные неполные склеивания между этими минитермами. Минитермы, которые учавствовали хотя бы в одном склеивании, отмечаем звездочкой, так как они в дальнейшем будут поглощены минитермом второго ранга, являющимся результатом склеивания на основании соотношения (2-11). Получим минитермы второго ранга

В результате склеивания между первым и последним минитермом получиться вырожденный минитерм, который инвертируется. Тот же самый результат получится из склеивания третьего и четвертого минитермов. Не будет поглощаться только второй минитерм.

Минитерм первого ранга .

Удаляя из нормальной формы все поглощающиеся инверсанты, получаем сокращенную нормальную форму, содержащую только простые инверсанты:

.

Для данного примера сокращенная нормальная форма совпадает с минимальной и построение таблицы меток, и поиск минимального покрытия не дает ничего нового. Отметим, что построение таблицы и операции с нею полностью аналогичны работе с таблицей Квайна. Единственная разница состоит в том, что вырожденная инверсанта, состоящая из единственной переменной, поглощает те минитермы, которые содержат ее отрицание. Для нашего примера для строки, соответствующей инверсанте , мы должны расставить метки в столбцах, которые содержат в соответствующем им выражении .