Досконала кон'юнктивна нормальна форма
Досконалою кон’юнктивною нормальною формою (ДКНФ) булевої функції називається кон’юнкція тих конституент нуля, які перетворюються в нуль на тих самих наборах змінних, що й задана функція. Також по аналогії з ДДНФ, будь-яка булева функція має одну ДКНФ (кількість її членів дорівнює кількості нульових значень функції) і декілька КНФ. Можна навести такі властивості ДКНФ, що виділяють її з усіх КНФ:
- в ній немає однакових співмножників;
- жоден із співмножників не містить двох однакових доданків;
- жоден із співмножників не містить якої-небудь змінної разом з її запереченням;
- в кожному окремому співмножнику є як складова або змінна xi, або її заперечення для будь-якого i=1,2,…,n.
Приклад знаходження ДКНФ
Для того, щоб отримати ДКНФ функції, потрібно скласти її таблицю істинності. Наприклад, візьмемо одну з таблиць істинності з статті Метод Куайна:
| 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 |
В комірках стовпця відмічаються лишень ті комбінації, які приводять логічний вираз до нуля.
Наприклад, четвертий рядок містить 0 в даній комірці
- = 0
- = 0
- = 1
- = 1
В диз'юнкцію змінна записується без інверсії, якщо в наборі вона дорівнює 0, і з інверсією, якщо вона дорівнює 1. Перший член ДКНФ даної функції має такий вигляд:
Всі інші члени ДКНФ складаються по аналогії і тоді отримується наступна ДКНФ:
