5.2. Мінімальна диз’юнктивна нормальна форма

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

Для отримання МДНФ необхідно виконати такі дії:

• заносимо одиничні значення функції в карту Карно;

• створюємо ПК за одиничними значеннями. Одиниці, які ввійшли на попередніх кроках в одну із кон’юнкцій, вважаємо покритими. Із непокритих і покритих одиниць створюємо наступну кон’юнкцію, покриваючи максимальну кількість непокритих одиниць. Нову кон’юнкцію тільки із покритих одиниць створювати не потрібно. Процес завершується, коли покриті всі одиниці;

• описуємо всі ПК за допомогою таблиці;

• для кожної ПК складаємо кон’юнкцію змінних, від яких вона залежить.

Якщо змінна для даної ПК приймає одиничне значення, то вона береться в прямому вигляді, а інакше – в інверсному:

• об’єднуємо за допомогою операції диз’юнкції всі описані ПК:

. (5.1)

й отримуємо мінімальну диз’юнктивну нормальну форму.

Приклад 3. Функція f₃ задана таблицею істинності (табл. 5.7). Побудувати МДНФ.

Таблиця 5.7 – Таблиця істинності функції f₃

х1	х2	х3	f3
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Заносимо одиничні значення функції f₃ в карту Карно.

ПК₂¹

х ₁ ПК₁²

х2	6	1 7	1 3	1 2
	4	5	1 1	1 0

х₃

Об’єднуємо клітинки 0, 1, 2 і 3 в ПК₁² , а клітинки 3 і 7 в ПК₂¹. Правильні конфігурації описуємо за допомогою табл. 5.8.

Таблиця 5.8 – Опис значень змінних для правильних конфігурацій за одиничними значеннями функції f₃

Правильні Конфігурації	Значення змінних
	х1	х2	х3
ПК12	0	–	–
ПК21	–	1	1

ПК₁² описується тільки однією змінною, а саме . ПК₂¹ описується добутком змінних х₂ і х₃ Об’єднавши за допомогою операції диз’юнкції отримані описи ПК, одержимо МДНФ:

f_3мднф = .