Основні терміни
Лекція 6. Канонічні форми логічних формул, які використовуються в ЕОМ
6.1 Основні терміни. Поняття СДНФ і СКНФ.
6.2 Алгоритми побудови СДНФ і СКНФ по таблиці істинності.
Будь-яка логічна формула визначає деяку булевих функцій. У той же час ясно, що для будь-якої булевої функції можна записати нескінченно багато формул її представляють (див. Завдання 3 до § 3.6). Дійсно, якщо є хоча б одна формула, яка виражає булеву функцію, то, використовуючи тотожні перетворення, можна змінити цю формулу, побудувавши як завгодно складну рівносильну формулу, наприклад,
a xor b ≡ (a and (not b)) or ((not a) and b).
Одна з основних завдань алгебри логіки - знаходження канонічних форм (т. Е. Формул, побудованих за певним правилом, канону), а також найбільш простих формул, що представляють булеві функції.
Визначення 1. Якщо логічна функція виражена через диз'юнкцію, кон'юнкцію і заперечення змінних, то така форма подання називається нормальною.
Серед нормальних форм виділяють такі, в яких функції записуються єдиним чином. Їх називають досконалими.
Особливу роль в алгебрі логіки грають класи скоєних діз'юнктівних і кон'юнктивні нормальних форм (СДНФ і СКНФ). В їх основі лежать поняття елементарної диз'юнкції і елементарної кон'юнкції.
Визначення 2. Формулу називають елементарної кон'юнкція, якщо вона є кон'юнкція однієї або декількох змінних, взятих з запереченням або без заперечення. Одну змінну або її заперечення вважають одночленной елементарної кон'юнкція.
Приклад 1. Формули є елементарних кон'юнкція; перші дві з них - одночленним.
Визначення 3. Формула називається диз'юнктивній нормальною формою (ДНФ), якщо вона є диз'юнкція неповторяющихся елементарних кон'юнкція. ДНФ записуються у вигляді, де кожне Ai - елементарна кон'юнкція.
Приклад 2. Наведемо дві диз'юнктивні нормальні форми:
Визначення 4. Формула А від k змінних називається досконалою диз'юнктивній нормальною формою (СДНФ), якщо:
1) А є ДНФ, в якій кожна елементарна кон'юнкція є кон'юнкція k змінних, причому на i-му місці цієї кон'юнкції варто або змінна, або її заперечення;
2) все елементарні кон'юнкції в такий ДНФ попарно різні.
Завдання 1. Дано формули:
;
;
Визначити, чи є вони СДНФ двох змінних.
Рішення. Формула А є СДНФ двох змінних. Формули В і С не є СДНФ. Формула В залежить від трьох змінних, але кількість змінних в елементарних кон'юнкція менше трьох. У формулі С змінна х2 двічі входить в одну і ту ж елементарну кон'юнкцію.
Досконала діз'юнктівная нормальна форма являє собою формулу, побудовану за суворо визначеними правилами з точністю до порядку проходження елементарних кон'юнкція (диз'юнктивних членів) в ній. Вона є прикладом однозначного уявлення булевої функції у вигляді формульної (алгебраїчної) записи.
Визначення 5. Формула називається елементарної диз'юнкція, якщо вона є диз'юнкція (можливо, одночленной) змінних і заперечень змінних.
Приклад 1 Наведемо три елементарні диз'юнкції:
.
Визначення 6. Формула називається кон'юнктівной нормальною формою (КНФ), якщо вона є кон'юнкція неповторяющихся елементарних диз'юнкцій.
КНФ записуються у вигляді, де кожне Ai - елементарна диз'юнкція.
є кон'юнктивна нормальна форма.
Визначення 7. Формула А від k змінних називається досконалою кон'юнктівной нормальною формою (СКНФ), якщо:
1) А є КНФ, в якій кожна елементарна диз'юнкція є диз'юнкція k змінних, причому на i-му місці цієї диз'юнкції варто або змінна х, або її заперечення;
2) все елементарні диз'юнкції в такий КНФ попарно різні.
Завдання 2. Дано формули і. Визначити, чи є вони СКНФ.
Рішення. Формула А є СКНФ, а формула В не є СКНФ, оскільки змінна двічі входить в перший кон'юнктивний член, крім того, кількість змінних в кожній елементарній диз'юнкції менше трьох, в той час як формула залежить від трьох змінних.
Питання. Будь-яку чи логічну функцію можна представити в одній з розглянутих канонічних скоєних форм?
Відповідь. Так, будь-яку булеву функцію, не рівну тотожне 0 або 1, можна представити у вигляді СДНФ або СКНФ.
Для обгрунтування цього твердження є теорема.
Теорема 1. Нехай - булева функція від n змінних, що не рівна тотожно нулю. Тоді існує досконала діз'юнктівная нормальна форма, що виражає функцію f.
Алгоритм побудови СДНФ по таблиці істинності:
1. У таблиці істинності відзначаємо набори змінних, на яких значення функції f дорівнює одиниці.
2. Записуємо для кожного зазначеного набору кон'юнкцію всіх змінних наступним чином: якщо значення деякої змінної в цьому наборі одно 1, то в кон'юнкцію включаємо саму змінну, в іншому випадку - її заперечення.
3. Всі отримані кон'юнкції пов'язуємо операціями диз'юнкції.
Слідство теореми 1. Для будь-якої формули можна знайти рівносильну їй ДНФ.
Приклад 3. Потрібно побудувати формулу для функції f (x1. Х2. Х3), заданої таблицею істинності:
Використовуючи описаний вище алгоритм, побудуємо для неї СДНФ:
Теорема 2. Нехай - булева функція n змінних, що не рівна тотожно одиниці. Тоді існує досконала кон'юнктивна нормальна форма, що виражає функцію f.
На підставі теореми 2 можна запропонувати наступний алгоритм побудови СКНФ по таблиці істинності функції.
Алгоритм побудови СКНФ по таблиці істинності ^
1. У таблиці істинності відзначаємо набори змінних, на яких значення функції f дорівнює нулю.
2. Записуємо для кожного зазначеного набору диз'юнкцію всіх змінних наступним чином: якщо значення деякої змінної в цьому наборі дорівнює 0, то в кон'юнкцію включаємо саму змінну, в іншому випадку - її заперечення.
3. Всі отримані диз'юнкції пов'язуємо операціями кон'юнкції.
Слідство теореми 2. Для будь-якої формули можна знайти рівносильну їй КНФ.
Приклад 4. Висловимо функцію імплікація за допомогою операцій заперечення, диз'юнкції і кон'юнкції. Для цього запишемо таблицю істинності функції імплікація: