Досконала диз'юнктивна нормальна форма

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

• в ній немає однакових доданків;
• жоден із доданків не містить двох однакових співмножників;
• жоден із доданків не містить змінну разом із її запереченням;
• в кожному окремому доданку є як співмножник або змінна x_i, або її заперечення для будь-якого i = 1, 2, …, n.

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

Приклад знаходження ДДНФ

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

${𝐱}_{\mathrm{𝟏}}$	${𝐱}_{\mathrm{𝟐}}$	${𝐱}_{\mathrm{𝟑}}$	${𝐱}_{\mathrm{𝟒}}$	$𝐟(x_1,x_2,x_3,x_4)$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

В комірках результату $𝐟(x_1,x_2,x_3,x_4)$ відмічаються лишень ті комбінації, які приводять логічний вираз до одиниці.
Далі розглядається значення змінних при яких функція дорівнює 1. Якщо значення змінної дорівнює 0, то вона записується з інверсією. Якщо значення змінної дорівнює 1, то вона записується без інверсії. Перший стовпець містить 1 в заданому полі. Відмічаються значення всіх чотирьох змінних це:

• ${𝐱}_{\mathrm{𝟏}}$ = 0
• ${𝐱}_{\mathrm{𝟐}}$ = 0
• ${𝐱}_{\mathrm{𝟑}}$ = 0
• ${𝐱}_{\mathrm{𝟒}}$ = 0

Нульові значення — тут всі змінні представлені нулями — записуються в кінцевому виразі інверсією цієї змінної. Перший член ДДНФ даної функції має такий вигляд: $\overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\wedge \overline{x_4}$
Змінні другого члена:

• ${𝐱}_{\mathrm{𝟏}}$ = 0
• ${𝐱}_{\mathrm{𝟐}}$ = 0
• ${𝐱}_{\mathrm{𝟑}}$ = 0
• ${𝐱}_{\mathrm{𝟒}}$ = 1

${𝐱}_{\mathrm{𝟒}}$ в цьому випадку буде представлений без інверсії: $\overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\wedge x_4$

Таким чином аналізуються всі комірки $𝐟(x_1,x_2,x_3,x_4)$. ДДНФ цієї функції буде диз'юнкцією всіх отриманих членів (елементарних кон'юнкцій).

Досконала ДНФ цієї функції:

$𝐟(x_1,x_2,x_3,x_4)=(\overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\wedge \overline{x_4})$ $\vee$ $(\overline{x_1}\wedge \overline{x_2}\wedge \overline{x_3}\wedge x_4)$ $\vee$ $(\overline{x_1}\wedge \overline{x_2}\wedge x_3\wedge \overline{x_4})$ $\vee$ $(\overline{x_1}\wedge x_2\wedge x_3\wedge \overline{x_4})$ $\vee$ $(x_1\wedge x_2\wedge x_3\wedge \overline{x_4})$ $\vee$ $(x_1\wedge x_2\wedge x_3\wedge x_4)$

Див. також

• Нормальна форма формули у логіці предикатів
• ДНФ
• КНФ
• Досконала кон'юнктивна нормальна форма