5. Диз’юнктивна та кон’юнктивна нормальні форми. Розкладання булевої функції за змінними. Досконалі диз’юнктивна та кон’юнктивна нормальні форми.

Рівносильні перетворення застосовуються також для зведення формул, які реалізують булеві функції до спеціального вигляду або до спеціальної форми, яка з логічних операцій містить тільки ,  і  .

Нехай – деякий набір (булевих) змінних.

Означення.: Елементарною кон’юнкцією від змінних називається кон’юнкція деяких із змінних або їх заперечень.

Приклад. Нехай задані змінні . Елементарними кон’юнкціями від них будуть, наприклад, такі: ; ; .

Означення. Елементарною диз’юнкцією від змінних називається диз’юнкція деяких із змінних або їх заперечень.

Приклад. Нехай задані змінні . Елементарними диз’юнкціями від них будуть, наприклад, такі: ; ; .

Означення. Елементарна диз’юнкція (кон’юнкція) від змінних називається повною, якщо до неї від кожної пари входить тільки одна змінна.

Приклад. Утворимо всі повні елементарні диз’юнкції від змінних висловлень :

Якщо в отриманих формулах всі знаки операції  замінити знаком операції , то будемо мати всі повні елементарні кон’юнкції від змінних висловлень :

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

Приклад.

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

Приклад. .

Будь-яка формула має як ДНФ, так і КНФ.

Приклад. Знайдемо ДНФ і КНФ для формули .

- ДНФ

- КНФ.

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

Серед множини ДНФ (КНФ), які має дана формула, існує унікальна форма: вона єдина для даної формули. Це – так звана досконала ДНФ (досконала КНФ).

Означення. Досконалою ДНФ (ДДНФ) називається диз’юнкція повних елементарних кон’юнкцій від змінних :

Приклад. ;

.

Означення. Досконалою КНФ (ДКНФ) називається кон’юнкція повних елементарних диз’юнкцій від змінних :

Приклад. ;

.

6. Зображення булевих функцій досконалими диз’юнктивними нормальними формами.

Позначимо:

;

–

диз’юнкція всіх можливих формул F(…), коли індекси перебігають всі можливі упорядковані набори довжини з 0 і 1.

Теорема (про розклад формули за змінними). Для будь-якої формули і для будь-якого числа справедливий розклад:

(1)

де диз’юнкція береться за всіми можливими наборами значень змінних .

Рівносильність (1) називається розкладом за змінними .

Приклад 1. При розклад за змінною запишеться так:

Приклад 2. При , розклад має вигляд:

.

Наприклад, якщо , то остання формула дає

.

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

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

1) Вибрати всі ті набори значень її змінних, на яких функція набуває значення 1;

2) Для кожного такого набору утворити відповідну повну елементарну кон’юнкцію;

3) Отримані повні елементарні кон’юнкці з’єднати знаками .

Приклад. Знайти ДДНФ для функції , яка реалізується формулою .

Розв’язання: Складемо таблицю істинності:

0	0	1
0	1	1
1	0	0
1	1	1

З таблиці видно, що наборів, на яких функція набуває значення 1 три: , і , тому



 

Алгоритм знаходження ДДНФ для даної функції

за допомогою рівносильних перетворень:

1) Позбавитися у формулі від всіх входжень знаків та ;

2) Добитися того, щоб знак  стояв тільки перд змінними;

3) поповнити елементарні кон’юнкції до повних так: якщо змінна не входить у формулу , то оскільки , то ;

4) З однакових членів отриманої диз’юнкції залишаємо тільки один.

Приклад. Знайти ДДНФ для формули за допомогою рівносильних перетворень:

 

7. Зображення булевих функцій

досконалими кон’юнктивними нормальними формами.

Всі поняття і теореми цього питання є двоїстими по відношенню до відповідних понять і теорем поперднього питання.

Позначимо:

;

–

кон’юнкція всіх можливих формул F(…), коли індекси перебігають всі можливі упорядковані набори довжини з 0 і 1.

Теорема (про розклад формули за змінними)