ДДНФ і ДКНФ

Визначення 10.6. Досконалою ДНФ (ДДНФ) називається ДНФ, у якій немає рівних елементарних кон’юнкцій і всі елементарні кон’юнкції містять ті самі змінні, від яких залежить функція, причому кожну змінну – тільки один раз (з урахуванням входження під знаком інверсії).

Визначення 10.7. Досконала КНФ (ДКНФ) визначається як така КНФ, у якій немає однакових співмножників; всі співмножники містять ті самі змінні, причому кожну змінну, від яких залежить функція, – тільки один раз.

Для кожної відмінної від нуля булевої функції можна побудувати реалізацію у вигляді ДДНФ:

, (10.4)

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

Кожна функція алгебри логіки реалізується такою ДКНФ:

. (10.5)

ДДНФ і ДКНФ функції можна одержати із ДНФ і КНФ шляхом еквівалентних перетворень.

Приклад 10.2. Одержати ДДНФ і ДКНФ функції із прикладу 10.1.

Розв’язок.

1. Для одержання ДДНФ слід скористатися зображенням функції у вигляді ДНФ і застосувати закон протиріччя, помноживши кожний кон’юнктивний терм на 1 у вигляді добутку відсутньої змінної і її інверсії:

.

2. Для одержання ДКНФ слід скористатися зображенням функції у вигляді КНФ і застосувати закон виключеного третього з додаванням до кожного диз’юнктивного терму 0 у вигляді суми відсутньої змінної та її інверсії:

Зауваження. ДНФ, КНФ, ДДНФ, ДКНФ є різними формами зображення для однієї й тієї ж функції. Знаки рівності розуміють у значенні еквівалентності виконаних перетворень.

Досконалі ДНФ і КНФ можна отримати з таблиці істинності булевої функції. ДДНФ виписується за одиничним значенням функції, ДКНФ – за нульовими.

Приклад 10.3. Скласти таблицю істинності функції із прикладу 10.1 і отримати досконалі ДНФ і КНФ за таблицею.

Розв’язок. Функція залежить від трьох змінних. Її таблиця істинності має вигляд:

ДДНФ складається за одиничним значенням функції. При цьому кожному двійковому набору, на якому функція дорівнює одиниці, відповідає елементарна кон’юнкція, що складається з добутку первинних термів. Змінні, яким відповідають нульові значення, включаються під знак інверсії, а одиничні – без знака інверсії:

.

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

.

Якщо функція представлена таблицею істинності, можна відновити аналітичну форму функції у вигляді ДДНФ або ДКНФ.