Метод мінімізації Квайна

Вихідною формою подання перемикальної функції для виконання мінімізації за методом Квайна є ДДНФ.

Метод Квайна базується на використанні співвідношення неповного склеювання

(2. 1)

і співвідношення поглинання

, (2. 2)

де , і - довільні кон’юнктивні терми; -змінна.

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

Під ядром функції розуміють сукупність імплікант, які неможливо вилучити із СДНФ. Такі імпліканти покривають деякі конституенти тільки самостійно.

Мінімізація перемикальної функції виконується за такими етапами.

1. Записати перемикальну функцію у вихідній формі, якою є ДДНФ.

2. Застосувати співвідношення неповного склеювання (2. 1) послідовно до конституент одиниці, потім до імплікант -го рангу, -го рангу і так далі, поки формування нових імплікант можливе.

3. Виконати всі можливі поглинання, використовуючи співвідношення (2. 2), в результаті чого визначаються всі прості імпліканти, які складають СДНФ.

4. Побудувати таблицю покриття (імплікантну матрицю) для подальшого спрощення запису функції.

5. Визначити ядро перемикальної функції та всі ТДНФ. З числа отриманих ТДНФ вибрати МДНФ.

Розглянемо мінімізацію функції за методом Квайна на прикладі.

Приклад. Допустимо, що ДДНФ функції має вигляд:

.

1 2 3 4 5 6

Для зручності викладок позначимо кожну конституанту одиниці із ДДНФ функції яким-небудь десятковим номером.

Виконуємо попарне склеювання конституент одиниці відповідно до співвідношення неповного склеювання (2. 1):

1 – 2 - по ;

1 – 5 - по ;

2 – 6 - по ;

3 – 4 - по ;

4 – 5 - по ;

5 – 6 - по .

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

Одержали множину імплікант 2-го рангу:

, , , , , .

Задана перемикальна функція після склеювання приймає такий вигляд:

.

1 2 3 4 5 6

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

1 – 6 - по ;

2 – 3 - по .

з утворенням однієї й тієї ж елементарної кон’юнкції .

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

.

Виконавши поглинання, одержуємо скорочену ДНФ:

.

На наступному етапі мінімізації заданої перемикальної функції будуємо таблицю покриття (табл.2. 1).

Таблиця2. 1.

Прості імпліканти	Конституенти одиниці
	1	2	3	4	5	6
	+	+			+	+
				+	+
			+	+

Знаходимо ядро функції – сукупність імплікант, що відповідають одноразово покритим конституентам (стовпці імплікантної матриці, що відповідають таким конституентам, мають тільки одну позначку „ + “). В даному прикладі ядро складають імпліканти та . Очевидно, що імпліканта зайва, так як імпліканти і накривають всі стовпці імплікантної матриці.

Задана функція має єдину тупикову і мінімальну ДНФ

.

Зауваження. Кількість хрестиків в одному рядку завжди є степенем 2. Більш того, можна легко переконатися в тому, що ,

де - число букв що містяться в простій імпліканті.