Алгоритм приведення до дднф і дкнф довільної логічної функції

Досконала диз'юнктивна й кон’юктивна нормальна форми дають спосіб подання булевої функцією через суперпозицію кон’юнкції, диз'юнкції й заперечення, якщо в нас є таблиця значень функції.

Подання булевої функції у вигляді

,

де диз'юнкція береться по всім , на яких , називається зробленою досконалою диз'юнктивною нормальною формою (ДДНФ). Усяка булева функція (крім 0) має єдину СДНФ.

Щоб одержати досконалу диз'юнктивну нормальну форму, треба взяти всі набори, на яких значення функції дорівнює 1 і записати для кожного з них кон’юнкцію змінних й їхніх заперечень. Якщо в наборі значення змінної 0 - то змінну треба взяти із запереченням, якщо 1 - без заперечення. З наборів кон’юнкцій змінних треба побудувати диз'юнкцію.

Приклад 1 (Досконала диз'юнктивна нормальна форма).

Побудуємо досконалу диз'юнктивну нормальну форму функції, заданою наступною таблицею.

Таблиця 2

Набори, на яких функція дорівнює 1 – це (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1). Перший набір дає кон’юнкцію x & y & z, другий – x & y & z, третій – x & y & четвертий – x & y & z.

У результаті одержуємо (x & y & z) √ (x & y & z) √ (x & y & z√ (x& y& z).

Щоб одержати досконалу кон’юктивну нормальну форму, треба взяти всі набори, на яких значення функції дорівнює 0 і записати для кожного з них диз'юнкцію змінних й їхніх заперечень. Якщо в наборі значення змінної 0 - то змінну треба взяти без заперечення, якщо 1 - із запереченням. З диз'юнкцій, що вийшли, треба побудувати кон’юнкцію.