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

–     записують функцію у вигляді:

          .

  Зміст