2.2 Досконала кон’юнктивна нормальна форма
Якщо задано, що логічна функція дорівнює одиниці на більшості наборів аргументів, то подання функції в ДДНФ – громіздке. В таких випадках зручніше використовувати досконалу кон’юктивну нормальну форму.
В алгебрі логіки конституентою нуля називають логічну функцію n аргументів, яка набуває значення, що дорівнює нулю, лише на одному наборі.
Оскільки наборів аргументів 2n, то і конституент нуля - 2n.
Конституенти нуля можна виразити у вигляді диз’юнкцій всіх аргументів, частина з яких береться з запереченнями.
Заперечення ставляться так, щоб обернути в нуль диз’юнкцію в потрібному наборі.
Наприклад, конституенту нуля двох аргументів отримаємо
|
при |
|
|
при |
|
|
при |
|
|
при |
|
; 
;
; 
;
; 
;
; 
.Приклад. Записати конституенту нуля на одинадцятому наборі; число аргументів дорівнює шести:
11 |
0 0 1 0 1 1 |
|
Заперечення вказується над аргументами, які дорівнюють одиниці
.
Означення: добуток конституент нуля, які дорівнюють нулю на тих самих наборах, що і задана функція, називається досконалою кон’юктивною нормальною формою.
Будь-яка логічна функція має єдину досконалу кон’юктивну нормальну форму.
Отримання ДКНФ розглянемо на такому прикладі.
Необхідно подати в ДКНФ функцію трьох аргументів, яка дорівнює нулю на наборах 1, 3, 6.
Для подання функції виконуються дії:
– записують диз’юнкцію всіх аргументів для наборів, на яких функція перетворюється в нуль, і над аргументами, які дорівнюють одиниці, вказують знак заперечення
1 |
0 0 1 |
|
3 |
0 1 1 |
|
6 |
1 1 0 |
|
– записують функцію у вигляді:
.