2014-02-12
1024
Данный метод минимизации основан на применении свойства идемпотентности, поглощения и склеивания.
Рассмотрим этот метод на примере. Пусть заданы номера наборов из 4-х переменных, на которых функция равна единице: f(2,5,6,7,10,12,13,14) = 1. Необходимо составить СДНФ:
Далее упростить формулу, применив закон склеивания и идемпотентности, получим:
Теперь составим таблицу Квайна: по вертикали перечислены все элементарные конъюнкции, вошедшие в последнюю ДНФ, по горизонтали - элементарные конъюнкции, входящие в СДНФ. Единица в ячейке ставится, если конъюнкция ДНФ «накрывает» (используя закон поглощения) конъюнкцию в СДНФ. В каждом столбце оставляют по одной единице, исключая избыточные. Выбор единиц производят из соображения минимальности множителей в конъюнкции. Покажем таблицу:
| abcd | 
| 
| 
| 
| 
| 
| 
| 
|
| 1V | 1V | 1V | 1V | ||||
| 1V | 1V | ||||||
| ||||||||
| ||||||||
| 1V | 1V | ||||||
|
Выбранные ячейки отметим знаком «V». На последнем этапе минимизации получаем ДНФ: 
|
|
|
Отметим, что в общем случае решений может быть несколько.
