Page 58 - 4570

57

2. Якщо припустимо, що для деякого набору значень атомів формула α(A 1,
A 2, . . ., A n) набуває значення «Істина» і прийдемо до суперечності, то вона є
суперечною.
3. Якщо не одержимо суперечності ні при припущенні 1, ні при
припущенні 2, то робимо висновок, що формула α є нейтральною.
Приклад 2.15. Визначити тип формули α = ((A  B)  A)  A.
Розв’язання. Припустимо, що α не є тотожно істинною формулою. Тоді
повинен існувати такий набір значень атомів, на якому вона набуває значення
«Хибність». Формула α є імплікацією. Значення «Хибність» можливе лише за
умови, що (A  B)  A набуває на цьому наборі значення «Істина», а А –
«Хибність». Тоді випливає, що A  B повинне набувати значення «Хибність»,
що неможливо, оскільки А – «Хибність». Отже, α є тавтологією.
Перед тим як розв’язувати проблему вирішення, інколи корисно спочатку
перетворити формулу логіки висловлювань за допомогою рівносильних
перетворень до деякої стандартної форми. Такими формами є диз’юнктивна
нормальна форма (ДНФ) та кон’юнктивна нормальна форма (КНФ).
Зафіксуємо деяку множину Х логічних змінних.
Означення 2.14. Елементарною кон’юнкцією (диз’юнкцією) називається
кон’юнкція (диз’юнкція) скінченного числа попарно різних логічних змінних,
узятих із запереченням або без нього.
,
Наприклад, ABC , ABC A A A є елементарними кон’юнкціями,
1 2 3
A B  , C A  A  A  A є елементарними диз’юнкціями, а AAB або
1 2 3 4
A  A  A вже такими не будуть.
1 1 2
Означення 2.15. Елементарні кон’юнкції, що містять усі змінні з Х,
будемо називати конституентами одиниці над Х, а елементарні диз’юнкції,
які задовольняють подібну властивість, – конституентами нуля над Х.
Неважко побачити, що кожна конституента одиниці (відповідно,
конституента нуля) лише на одному, єдиному для неї наборів атомів набуває
значення «Істина» (відповідно значення «Хибність»).
Означення 2.16. Диз’юнктивною (кон’юнктивною) нормальною
формою називається диз’юнкція (кон’юнкція) скінченного числа попарно
різних елементарних кон’юнкцій (диз’юнкцій).

Наприклад, AB  A  BC  BCD є ДНФ, (A B )(A C )(B C ) – КНФ.
Надалі елементарні кон’юнкції в ДНФ будемо називати доданками, а
елементарні диз’юнкції в КНФ – множниками.
Означення 2.17. ДНФ (КНФ) називається досконалою, якщо всі її доданки
(множники) є конституентами одиниці (нуля) над множиною всіх її атомів.
Досконалі форми будемо відповідно позначати ДДНФ та ДКНФ.
Довільну формулу алгебри висловлювань можна перетворити в одну з
нормальних форм. Для цього необхідно виконати ряд кроків:
1. Усунути логічні зв’язки «Імплікація» та «Еквіваленція» за формулами

A  B A  , B A ~B (A  B) (B  A).