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

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

• в ній немає однакових співмножників;
• жоден із співмножників не містить двох однакових доданків;
• жоден із співмножників не містить якої-небудь змінної разом з її запереченням;
• в кожному окремому співмножнику є як складова або змінна 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}})}$ відмічаються лишень ті комбінації, які приводять логічний вираз до нуля.

Наприклад, четвертий рядок містить 0 в даній комірці ${\displaystyle \mathbf {f} ({x_{1}},{x_{2}},{x_{3}},{x_{4}})}$

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

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

Всі інші члени ДКНФ складаються по аналогії і тоді отримується наступна ДКНФ:

${\displaystyle ({x_{1}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({x_{1}}\lor {\overline {x_{2}}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land }$

${\displaystyle ({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {x_{3}}\lor {\overline {x_{4}}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {x_{2}}\lor {\overline {x_{3}}}\lor {\overline {x_{4}}})\land }$

${\displaystyle ({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {x_{4}})\land ({\overline {x_{1}}}\lor {\overline {x_{2}}}\lor {x_{3}}\lor {\overline {x_{4}}})}$

Див. також

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