Page 69 - 4570

68

ЛЕКЦІЯ 14. МЕТОДИ ПЕРЕВІРКИ ІСТИННОСТІ ВИСЛОВЛЮВАНЬ

1. Аксіоматичний метод
Аксіоматичний метод перевірки тотожної істинності логічних
висловлювань ґрунтується на тому, щоб серед нескінченного числа істинних
клауз знайти незалежну систему аксіом, за допомогою якої можна було
установити справедливість будь-яких клауз.

Оскільки доведення в логіці висловлювань будуються на відношенні
порядку, то логіка висловлювань є розширенням логіки Буля. Тому всі істинні
тотожності логіки Буля автоматично стають справедливими клаузами логіки
висловлювань. Наприклад, закон склеювання логіки Буля
(A B ) (A   ) B  A можна подати такими клаузами:
(A B ) ,(A  ) B  A, A (A B ) (A   ) B ,
1 ((A B ) (A   B ))~ A , A B  (A  ) B  A.

Таким чином, незалежна система аксіом логіки Буля, що складається із
чотирьох законів – комутативності, асоціативності, дистрибутивності, нуля та
одиниці, – автоматично стає системою аксіом і логіки висловлювань. Для
визначення відношення порядку необхідне будь-яке одне елементарне
висловлювання, до якого можна було б зводити всі інші найбільш складні
висловлювання. Таким висловлюванням може бути очевидна думка: «Істину
може висловлювати кожний».
Використовуючи формальну мову логіки висловлювань, цю думку можна
подати такою клаузою: A  B  A, яка означає «якщо A істинне, то
джерелом цієї істинності може бути що завгодно, наприклад B ». Якщо
зробити еквівалентне перетворення, то отримаємо клаузу:
, A B  A . (2.5)
Семантика цієї клаузи також змінилася і матиме таке висловлювання:
«Якщо раніше було встановлено, що A істинне, то істинність B не може
проявитися так, щоб A стало хибним», або «Істинність одного
висловлювання B не може впливати на істинність іншого висловлювання A ».
Отже, як основну аксіому логіки висловлювань, що виражає відношення
порядку, можна використовувати клаузу 2.5.
Приклад 2.21. Довести аксіоматичним методом справедливість клаузи:
B
A , A  B  , (2.6)
яка є правилом відділення, «Modus Ponens».
Розв’язання. Використовуючи тотожності логіки Буля, виконаємо
B
еквівалентні перетворення заданої клаузи A ( A B  )  , отримаємо B ,
B
A B , що згідно з 2.6 підтверджує справедливість клаузи A , A  B  .
Тобто якщо в процесі доведення істинності будь-якої складної клаузи вдалося
звести її до клаузи 1.7, то необхідно вважати, що доведення відбулося.
Приклад 2.22. Довести істинність логічного висловлювання
A  B , C   , B  C   аксіоматичним методом.
A