ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.10. МЕТОД КУАЙНА

      За методом Куайна прості імпліканти знаходяться по доскональній диз'юнктивній нормальній формі (ДДНФ) булевої функції в результаті застосування до неї закону неповного склеювання та операції поглинання.

Продемонструємо дію методу на прикладі.

      Приклад 6. Мінімізувати булеву функцію



. Розв'язання. Позначимо констинтуенти номерами:

1 - - 0010

2 - - 0101

3 - - 0110

4 - - 0111

5 - - 1010

6 - - 1100

7 - - 1101

8 - - 1110

Застосуємо закон склеювання констинтуент

6 та 8

6 та 7

2 та 4

3 та 4

2 та 7

3 та 8

5 та 1

Склеїмо дві останні імпліканти:

.

Нагадаємо, що одну і ту ж констинтуенту (імпліканту) можна зклеювати з іншими багато разів на основі закону ідемпотентності .

Застосовуючи закони логіки ми отримали

.

Далі, складемо таблицю Куайна (таблиця 12), в якій помістимо отримані спрощенням імпліканти та вихідні констинтуенти. Одиницю ставимо там, де імпліканта "покриває" констинтуенту, це тому, що констинтуента може бути замінена імплікантою за законом поглинання





Після того, як таблиця заповнена, проаналізувавши результати, бачимо, що загалом в кожній графі отримано дві одиниці, проте, досить мати хоча б одну. Тому, по можливості, слід виключити лишні одиниці, при цьому вибирають такі, в яких число термів найменше. В нашій таблиці вони взяті в круглі дужки.

Таблиця 12

Таким чином, можна обійтися трьома імплікантами замість шести.

.

      За допомогою таблиць істинності можна встановити, що отримана мінімальна нормальна форма функції відтворює всі значення вихідної функції. Підкреслимо, що в загальному випадку розв'язків по даному критерію мінімумів термів може бути декілька.

ЗМІСТ