Істинність клауз і їх докази методом резолюцій

Під висловом ми будемо розуміти граматично правильне, однозначно розуміється, оповідної пропозицію, про яке можна сказати, що воно або істинно, або хибно, наприклад:

"Київ - столиця України",
«Париж - століцаУкаіни».

Твердження, яке потрібно довести, в логіці висловлювань оформляється у вигляді наступного причинно-наслідкового відносини:
Р1, Р2. Рn-1, Рn => C (1.1)
де Рi - посилка (причина). З - висновок (наслідок). Новомосковскется: «Якщо посилки Р1, Р2. Рn-1, Рn істинні, то висновок З теж істинно »або, по-іншому« Якщо причини Р1, Р2. Рn-1, Рn мали місце, то буде мати місце і причинами-віє С ».
Щоб не сплутати об'єктне висловлювання (пропозиція) з суб'єктним висловлюванням. справедливість якого ми маємо намір встановити, домовимося пропозиції типу (1.1) називати Клаузен (clause).

Клауза - це метапредложеніе. в якому використано відношення порядку, оформлене через символ метаімплікаціі «=>». Як і ставлення еквівалентності, відношення порядку задовольняє трьом законам:
рефлексивності: А => А;
антисиметричність: якщо, то;
транзитивності: якщо А => В і В => С, то А => С.

На відміну від еквівалентності відношення порядку передбачає виконання закону антисиметричність, який можна записати так:
якщо А => В і В => А, то А = В.

Еквівалентні форми клауз

Над суб'єктом, який формулює метапредложенія, може стояти інший суб'єкт, для якого вже пропозиції першого суб'єкта виявляться об'єктними. Тоді клаузу (1.1) другий суб'єкт або метасуб'ект запише для себе наступним логічним виразом:
P1, P2, ..., Pn => C
.
- (P1P2 ... Pn) VC
Перетворивши це вираз в диз'юнкт, отримаємо:
.
Звідси легко знаходимо:
.
Клауза (1.1) може бути представлена ​​в інший еквівалентній формі:
. (1.2)
В силу коммутативности кон'юнкції на місці посилки Рn може виявитися будь-яка інша, причому не одна. Наприклад, клауз:

може бути перетворена в іншу еквівалентну форму:
. (1.3)
Однак клауз (1.1) в порівнянні з (1.2) і іншими подібними формами, типу (1.3), має певні переваги і, зокрема, використовується в мові логічного програмування ПРОЛОГ. Її називають хорновской. Довільну клаузу завжди можна звести шляхом еквівалентних перетворень до хорновскому увазі.
Якщо символ метаімплікаціі «=>» клауз (1.2) змістити в крайнє ліве положення, то вона перетвориться в тавтологію; якщо ж його змістити в крайнє праве положення, то - в протиріччя.
1 => - тавтологія,
- протиріччя.
Додавши в клаузу (1.1) зліва 1 через «,» і змістивши імплікації вліво, отримаємо зміщенням тавтологію.
Додавши в клаузу (1.1) праворуч через ";" 0 і змістивши імплікації вправо, отримаємо протиріччя.

Існує п'ять конкретних методів докази справедливості логічних клауз:

принцип резолюцій

Розглянемо еше один полуконструктівний метод докази істинності логічних клауз, в якому використовується так званий прінціпрезолюцій. Цей принцип грає роль аксіоми порядку і разом з тим породжує дуже ефективну конструктивну процедуру. Суть його зводиться до того, що два посилочних Кон'юнктів з протилежними термами завжди можна склеїти в один заключний диз'юнкт, в якому вже не буде протилежних термів:
,
де X і Y - довільні терми або цілі диз'юнкт з будь-яким набором термів, включаючи нуль; А та - довільні терми.
Вихідна клауз конструюється у формі кон'юнктивний протиріччя:
.

Алгоритм застосування методу резолюцій для доказу клауз

1. Перетворимо клаузу до еквівалентній формі протиріччя.
2. Ліву частину клауз перетворимо до кон'юнкції диз'юнкцій.
3. Застосовуємо метод резолюцій до Кон'юнктів, які мають форму диз'юнкції.
4. Повторюємо попередній пункт алгоритму до тих пір поки не отримаємо в лівій частині протилежні формули в якості Кон'юнктів.
5. Доказ клауз закінчено.

Питання.
Доведемо за допомогою методу резолюцій справедливість правила відділення:

A, A-> B, -B => 0
0VA, -AVB, -BV0 => 0
Тут є три диз'юнкт. Склеюючи їх послідовно,
0VB, -BV0 => 0
0V0 => 0
отримуємо в результаті нуль, який говорить про несумісність ув'язнення і посилок. Це як раз і свідчить про справедливість вихідної клауз.
Принцип резолюцій цілком замінює аксіому порядку, оскільки сама ця аксіома може бути доведена в рамках методу резолюцій. дійсно,
А, В => А,,,.
Звертаємо увагу на те, що посилка В тут взагалі не використовується. Це необхідно мати на увазі: не обов'язково використовувати всі посилки (їх число часто буває надмірною) - головне отримати нуль.
Нехай дана клауз:
.
Доказ її справедливості слід почати з приведення її в нормальну кон'юнктівную форму.

Випишемо по порядку всі посилки і далі почнемо їх склеювати згідно черговості. Праворуч від кожного нового диз'юнкт писатимемо номера використовуваних диз'юнктів, отримаємо: