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 |
Будуємо ДКНФ за „нулями” функції:
Ця форма збігається з побудованою раніше.