Проведені в задачах 2 і 3 еквівалентні перетворення показують, що за рахунок проведення правильних математичних (булевих) викладок можна істотно спростити логічний пристрій, що реалізує функцію.
2.3. Диз'юнктивна і Кон'юнктивна нормальні форми
Будь-яка диз'юнкція елементарних кон'юнкція називається диз'юнктивній нормальною формою (ДНФ).
Будь-яка кон'юнкція елементарних диз'юнкція називається кон'юнктівной нормальною формою (КНФ).
Будь-яку логічну функцію, не рівну тотожне одиниці, можна уявити в ДНФ.
Будь-яку логічну функцію, не рівну тотожне нулю, можна уявити в КНФ.
Процедура приведення до ДНФ:
1. Всі заперечення «спустити» до змінних за допомогою формул (6) і (8).
2. Розкрити дужки за допомогою (1), (3), (4).
3. Видалити зайві кон'юнкції і повторення в кон'юнкції з допомогою (5), (9), (10).
4. Видалити константи за допомогою (7).
Завдання 4. Привести до ДНФ формулу
розкриваємо дужки (3)
правило де Моргана (8, б)
правила (9, 7, б, 8, а)
правила (8, а і 8, б, 6)
застосовуємо узагальнене склеювання (13, а),
ввівши позначення. отримаємо
розкриваємо дужки і правило (9, 5, а)
виносимо за дужки
правило узагальненого склеювання (13, б)
Процедура приведення ДНФ до КНФ:
Нехай ДНФ F має вигляд
1. Застосувати до F правило подвійного заперечення
і привести до ДНФ. де - елементарні кон'юнкції. тоді:
2. За допомогою правила де Моргана звільнитися від другого заперечення і перетворити заперечення елементарних кон'юнкція в елементарні диз'юнкції. тоді:
Завдання 5. Привести формулу до КНФ
вводимо подвійне заперечення
правило де Моргана (8, б)
правило де Моргана (8, а)
розкриваємо дужки і правило (5, 9)
розкриваємо дужки і правило (5, 9)
правило склеювання (12)
правило де Моргана (8, б)
Спосіб переходу від табличного завдання логічних функцій до булевої формулою.
Процедура переходу до СДНФ:
а) для кожного набору значень змінних. на якому функція дорівнює 1, виписуються кон'юнкції всіх змінних;
б) над тими змінними, які на цьому наборі рівні 0, ставляться заперечення;
в) всі такі кон'юнкції з'єднуються знаками диз'юнкції.
Отримана таким чином формула називається досконалою диз'юнктивній нормальною формою (СДНФ) логічної функції.
Процедура переходу до СКНФ:
а) для кожного набору значень змінних. на якому функція дорівнює 0, виписуються диз'юнкції всіх змінних;
б) над тими змінними, які на цьому наборі рівні 1, ставляться заперечення;
в) всі такі диз'юнкції з'єднуються знаками кон'юнкції.
Отримана таким чином формула називається досконалою кон'юнктівной нормальною формою (СКНФ) логічної функції.
Завдання 6. Логічний функцію трьох змінних уявити булевої формулою у вигляді СДНФ і СКНФ:
Побудуємо таблицю істинності послідовно відповідно до кроками побудови формули