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

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

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

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

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

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

${\displaystyle \mathbf {x_{1}} }$	${\displaystyle \mathbf {x_{2}} }$	${\displaystyle \mathbf {x_{3}} }$	${\displaystyle \mathbf {x_{4}} }$	${\displaystyle \mathbf {f} ({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

В комірках результату ${\displaystyle \mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})}$ відмічаються лишень ті комбінації, які приводять логічний вираз до одиниці.
Далі розглядається значення змінних при яких функція дорівнює 1. Якщо значення змінної дорівнює 0, то вона записується з інверсією. Якщо значення змінної дорівнює 1, то вона записується без інверсії. Перший стовпець містить 1 в заданому полі. Відмічаються значення всіх чотирьох змінних це:

• ${\displaystyle \mathbf {x_{1}} }$ = 0
• ${\displaystyle \mathbf {x_{2}} }$ = 0
• ${\displaystyle \mathbf {x_{3}} }$ = 0
• ${\displaystyle \mathbf {x_{4}} }$ = 0

Нульові значення — тут всі змінні представлені нулями — записуються в кінцевому виразі інверсією цієї змінної. Перший член ДДНФ даної функції має такий вигляд: ${\displaystyle {\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {\overline {x_{4}}}}$
Змінні другого члена:

• ${\displaystyle \mathbf {x_{1}} }$ = 0
• ${\displaystyle \mathbf {x_{2}} }$ = 0
• ${\displaystyle \mathbf {x_{3}} }$ = 0
• ${\displaystyle \mathbf {x_{4}} }$ = 1

${\displaystyle \mathbf {x_{4}} }$ в цьому випадку буде представлений без інверсії: ${\displaystyle {\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {x_{4}}}$

Таким чином аналізуються всі комірки ${\displaystyle \mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})}$. ДДНФ цієї функції буде диз'юнкцією всіх отриманих членів (елементарних кон'юнкцій).

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

${\displaystyle \mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})=({\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {\overline {x_{4}}})}$ ${\displaystyle \vee }$ ${\displaystyle ({\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\land {x_{4}})}$ ${\displaystyle \vee }$ ${\displaystyle ({\overline {x_{1}}}\land {\overline {x_{2}}}\land {x_{3}}\land {\overline {x_{4}}})}$ ${\displaystyle \vee }$ ${\displaystyle ({\overline {x_{1}}}\land {x_{2}}\land {x_{3}}\land {\overline {x_{4}}})}$ ${\displaystyle \vee }$ ${\displaystyle ({x_{1}}\land {x_{2}}\land {x_{3}}\land {\overline {x_{4}}})}$ ${\displaystyle \vee }$ ${\displaystyle ({x_{1}}\land {x_{2}}\land {x_{3}}\land {x_{4}})}$

Див. також

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

Посилання

Примітки