§10. Метод Куайна

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

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

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

.

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

1 – – 0000 + 6 – – 1011 +

2 – – 0100 + 7 – – 1100 +

3 – – 0110 + 8 – – 1101 +

4 – – 0111 + 9 – – 1110 +

5 – – 1010 + 10 – – 1111 +

Застосуємо правило склеювання до всеможливих пар, а самі констинтуенти, що братимуть участь у склеюванні відмітимо хрестиком:

1 та 2 –

2 та 3 – +

2 та 7 – +

3 та 4 – +

3 та 9 – +

4 та 10 – +

5 та 6 – +

5 та 9 – +

6 та 10 – +

7 та 8 – +

7 та 9 – +

8 та 10 – +

9 та 10 – +

Тепер склеїмо всеможливі пари імплікант, а самі імпліканти, які будемо склеювати, знову відмітимо хрестиком:

(2,3) та (7,9) –

(2,7) та (3,9) –

(3,4) та (9,10) –

(3,9) та (4,10) –

(5,6) та (9,10) –

(5,9) та (6,10) –

(7,8) та (9,10) –

(7,9) та (8,10) –

Оскільки вже нічого склеювати, то процес склеювання завершився. Тепер вибираємо всі констинтуенти та імпліканти, що не позначені хрестиком та записуємо скорочену ДНФ. Якщо є однакові непозначені імпліканти, то на основі закону ідемпотентності вибираємо одну з них.

Отже скорочена ДНФ має наступний вигляд:

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

Після того, як таблиця заповнена, вибираємо найменше число рядків таких, щоб для кожного стовпця з даної таблиці і хоча б однієї одиниці в цьому стовпці знайшовся принаймні один рядок (з вибраних), який містить цю одиницю. Тоді диз’юнкція імплікант, що відповідають всім вибраним рядкам, буде мінімальною ДНФ.

Таблиця 14.

					0000	0100	0110	0111	1010	1011	1100	1101	1110	1111
A	0	–	0	0	1	1	0	0	0	0	0	0	0	0
B	–	1	–	0	0	1	1	0	0	0	1	0	1	0
C	–	1	1	–	0	0	1	1	0	0	0	0	1	1
D	1	–	1	–	0	0	0	0	1	1	0	0	1	1
E	1	1	–	–	0	0	0	0	0	0	1	1	1	1

Іншими словами, нам потрібно забрати з таблиці якомога більше «непотрібних» рядків таким чином, щоб після цього в кожному стовпці таблиці залишилася б принаймні одна одиниця.

З таблиці видно, що потрібно залишити рядки A, C, D та E. Якщо одиниці в цих рядках взяти в кружечки, то бачимо, що в кожному стовпці є принаймні одна одиниця. Тепер можна записати мінімальну ДНФ:

Якщо однозначно вибрати рядки не можна, тоді можна скористатися наступним методом, який продемонструємо на нашому прикладі.

Запишемо символічний вираз

.

Зведемо цей вираз до ДНФ, використовуючи дистрибутивний закон та формулу поглинання. Отримаємо:

Запишемо тупикову ДНФ, що відповідає отриманій кон’юнкції: . Якби кон’юнкцій було декілька, потрібно було б записати тупикову ДНФ для кожної і вибрати з них ту, котра містила б мінімальну кількість змінних. Знову отримали ту саму мінімальну ДНФ: .

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