Практичне заняття 14

Знайти МКНФ булевої функції яка дорівнює 0 на словах 0001, 0010, 0101, 0111, 1000, 1001, 1010, 1011, 1100, 1111.

Виконання.

17.4. Мінімізація функцій методом Квайна – Мак-Класкі

Метод Квайна – Мак-Класкі реалізує перехід від ДДНФ до МДНФ з використовуванням операцій склеювання та поглинання.

Алгоритм Квайна:

1. Записати ДДНФ заданої функції. Наприклад

2. Виконати всі можливі операції неповного диз’юнктивного склеювання. В результаті одержимо диз’юнкцію всіх можливих імплікант даної функції.

3. Виконати всі можливі операції диз’юнктивного поглинання. Результуюча формула є скороченою ДНФ даної функції.

4. Скласти імплікативну таблицю і знайти диз’юнктивне ядро.

5. Спростити імплікантну таблицю за допомогою видалення рядків, що відповідають імплікантам диз’юнктивного ядра і стовпчиків, що відповідають тим конституантам одиниці, які покриваються імплікантам ядра.

6. Знайти всі тупикові ДНФ даної функції.

7. Знайти мінімальну ДНФ.

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

Приклад 1. Знайти методом Квайна МДНФ функції

.

Виконання. Операції диз’юнктивного склеювання та поглинання:

,

,

,

.

Одержати інші елементарні кон’юнкції за допомогою операції склеювання неможливо. В ре одержали скорочену ДНФ:

.

Імплікантна таблиця даної функції

	*		*
		*			*
			*	*
				*	*

Диз’юнктивне ядро утворюють прості імпліканти і .

Спрощена імплікантна таблиця

	*
	*

Одержали дві тупикові ДНФ для заданої функції:

;

.

МДНФ: (містить меншу кількість заперечень.

77