- •Передмова
- •Розділ I Вступ до алгебри логіки
- •1.1.1. Логічні (булеві) функції
- •1.1.2. Способи подання булевих функцій
- •1.1.3. Булеві функції однієї змінної
- •1.1.4. Область визначення логічної функції
- •1.1.5. Елементарні функції алгебри логіки
- •1.2. Алгебра логіки
- •1.2.1. Поняття формули в алгебрі логіки
- •1.2.2. Еквівалентність формул
- •1.2.3. Елементи загальної алгебри
- •1.2.4. Закони булевої алгебри
- •1.3 Повні набори функцій
- •1.4 Канонічні форми булевих функцій
- •1.4.1 Проблема розв’язуваності
- •1.4.2 Нормальні та досконалі диз’юнктивні нормальні форми логічних функцій
- •1.4.3. Нормальні та досконалі кон’юнктивні нормальні форми логічних функцій
- •1.5. Спрощення формул
- •1.5.1. Утворення скороченої днф методом Квайна
- •1 Етап. Початкове скорочення формули.
- •2 Етап. Розставляння міток.
- •3 Етап. Знаходження суттєвих доданків.
- •4 Етап. Викреслювання зайвих стовпців.
- •1.5.2. Утворення скороченої днф за методом Мак Класкі
1.4.3. Нормальні та досконалі кон’юнктивні нормальні форми логічних функцій
Означення 1.19. Логічна сума будь-якої кількості різних незалежних змінних, що входять із запереченням або без нього, називається елементарною диз’юнкцією.
Звідси випливає, що , й – елементарні диз’юнкції.
Аналогічно до попереднього - елементарна диз’юнкція рангу .
Означення 1.20. Якщо яку-небудь функцію задано формулою у вигляді кон’юнкції елементарних диз’юнкцій, то функцію задано її кон’юктивною нормальною формою (КНФ).
Наприклад КНФ функції:
Будь-яка логічна функція, за виключенням рівної константі 1, може бути задана і своєю довершеною кон’юктивною нормальною формою (ДКНФ).
Означення 1.21. ДКНФ логічної функції називається її КНФ, що задовольняє такі умови:
1) в ній немає двох однакових співмножників;
2) жоден зі співмножників не містить двох однакових доданків;
3) жоден зі співмножників не містить якої-небудь змінної разом з її запереченням;
4) кожен співмножник містить як складову або для будь-якого .
Все сказане стосовно ДДНФ можна аналогічно застосувати і для ДКНФ. Так підкреслимо, що будь-яка логічна функція має єдину ДКНФ. Цю ДКНФ можна отримати двома способами: способом „розгортання” і за допомогою таблиць істинності.
Приклад 1.26. „Розгорнемо” наведену функцію:
При цьому прикладі ми розглянули принцип «розгортання» КНФ деякої функції , що залежить від змінних , до вигляду ДКНФ. Він полягає в наступному:
1. Виділити всі співмножники (елементарні диз’юнкції), в яких менше за доданків.
2. До кожного з цих співмножників додати доданок , який дорівнює нулю і не змінює значення початкового співмножника, де – відсутня в початковому співмножнику змінна.
3. Повторювати п.2, поки всі співмножники не задовольнятимуть умову наявності доданків.
Підкреслимо, що цей спосіб отримання ДКНФ застосовний тільки до формул, які мають вигляд КНФ.
Другий спосіб – це спосіб за табличним поданням функції. Він містить такі кроки:
1. побудова таблиці істинності ;
2. для кожного набору значень аргументів (кортежу), на якому в ДКНФ додається елементарна диз’юнкція вигляду: , де
Приклад 1.27. Розглянемо ту саму функцію, що і в прикладі 1.26. Побудуємо її таблицю істинності (табл.1.22)
Таблиця 1.22 |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
Будуємо ДКНФ за „нулями” функції:
Ця форма збігається з побудованою раніше.