Page 73 - 4570

72

3. Метод доведення від супротивного
Цей метод доведення істинності висловлювання полягає в наступному:
допускають, що істинним є заперечення того висловлювання, яке необхідно
довести (наслідок); потім через причини (посилки) намагаються дійти до
суперечності. Якщо це відбулося, то досліджуване логічне висловлювання
істинне, якщо ні – хибне.
Приклад 2.23. Довести істинність (хибність) логічного висловлювання:
A  , B B  C , A  D  C  D
методом від супротивного.
Розв’язання. Для зручності доведення логічного висловлювання подамо
його в такому вигляді:
A B B  C A  D ∆C  D,
де символ ∆ позначає «наслідок».

Припустимо, що посилки істинні, а наслідок  хибний. Якщо наслідок
хибний, тоді C  D  хибне. Але якщо C  D  хибне, то C і D також хибне.
Якщо C і D хибні, а посилки A  D і B  C істинні, то А і В також хибні. Але
якщо А і В хибні, а посилка A B за умовою істинна, то ми дійшли до
суперечності, з якої випливає, що дане висловлювання істинне.

4. Метод резолюцій

У цьому методі для доведення істинності висловлювань використовують
аксіоми порядку. Суть методу зводиться до того, що дві посилки диз’юнкти з
протилежними термами завжди можна склеїти в один остаточний диз’юнкт, у
B
якому вже не буде протилежних термів, наприклад A  , B C    A  C ,
де А і С – задовільні терми або цілі диз’юнкти з будь-яким набором термів,
включаючи хибність; В і B  задовільні терми. Якщо послідовно застосувати
метод резолюцій до досліджуваної клаузи, то внаслідок цього отримаємо
зменшення числа букв, у тому числі й до їх повного зникнення.
Метод резолюцій за своєю суттю заміняє аксіому порядку, оскільки вона
сама може бути доведена в рамках методу резолюцій, наприклад:
0
, A B  , A ,A B   0, 0, B  .
,
A
Необхідно відмітити, що посилка В тут не використовується. Це може бути
допустимо, оскільки необов’язково використовувати всі посилки (їх число
може бути збитковим), головне – це отримання результату. При доведенні
клаузи методом резолюцій необхідно її подати в нормальній кон’юктивній
формі, а необхідною умовою доведення є отримання нуля, що є підставою
істинності розглядуваної клаузи.
Приклад 2.24. Довести істинність клаузи D  F , A  (E  D ),

B
C  (B  ) A  E  ( C  F )  методом резолюцій.
Розв’язання. Подамо клаузу в КНФ:
B
E
C
B
 D  F ,     D , C    A      F   .
E
A
Перенесемо всі посилки в ліву частину кляузи:
 D  F ,     D ,  C    , A E C  F , B  .
0
A
E
B
,
,