Відкрити головне меню

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

  • в ній немає однакових співмножників;
  • жоден із співмножників не містить двох однакових доданків;
  • жоден із співмножників не містить якої-небудь змінної разом з її запереченням;
  • в кожному окремому співмножнику є як складова або змінна 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. Перший член ДКНФ даної функції має такий вигляд:          

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

 
 
 

Див. такожРедагувати