і отримати таким чином теорію
Т '= {{В¬ ip, q}, {p}, {q}}.
Звичайно, в більшості випадків для докази потрібно безліч кроків. Покладемо, наприклад, що теорія Т має вид
У цій теорії р і q зберігають колишній сенс, а г представляє твердження "Сократ - бог". Для того щоб показати, що Т | - В¬ r, будуть потрібні два кроки резолюції:
{В¬ q, p}, {Р}/{q}
{В¬ q,-r}, {q}/{-r}
Зверніть увагу, що на першому кроці використовуються дві фрази з вихідної безлічі Т, а на другому-резольвента {Q}, додана до Т. Крім того, слід зазначити, що доказ може бути виконано і по-іншому, наприклад:
{В¬ p, q}, {В¬ q, В¬ r}/{В¬ p, В¬ r},
{В¬ p, В¬ r}, {p}/{В¬ r}
При такому способі докази до Т додається інша резольвента. У зв'язку зі сказаним виникає ряд проблем. p> Коли безліч Т велике, природно припустити, що повинно існувати кілька способів вивести цікаву для нас конкретну формулу (ця формула є цільовою). Природно, що перевагу слід віддати тому методу, який дозволяє швидше сформулювати доказ.
Безліч Т може підтримувати і ті правила, які не мають нічого спільного з доказом цільової формули. Як же заздалегідь дізнатися, які правила приведуть нас до мети? p> Потенційно весь процес схильний до небезпеки комбінаторного вибуху. На кожному кроці безліч Г зростає, і в нашому розпорядженні виявляється все більше і більше можливих шляхів продовження процесу, причому деякі з них можуть привести в зациклення.
Та схема логічного висновку, якою ми слідували досі, зазвичай називається прямий, або висхідній стратегією. Ми починаємо з того, що нам відомо, і будуємо логічні судження в напрямку до того, що намагаємося довести. Один з можливих способів подолання сформульованих вище проблем - спробувати діяти в зворотному напрямку: від сформульованої цільової формули до фактів, які потрібні нам для доказу істинності цієї формули.
Припустимо, перед нами стоїть завдання вивести {q} з деякого безлічі фраз
Т = {..., {В¬ p, q}, ...}.
Складається враження, що це безліч потрібно перетворити, відшукуючи фрази, що включають q в якості литерала, а потім спробувати усунути інші літерали, якщо такі знайдуться. Але фраза {q} не В«стикається" з такою фразою, як, наприклад, {-р, q}, оскільки пара, що складається з однакових літералів q, не є взаємно доповнює.
Якщо q є метою, то метод спростування резолюції реалізується додаванням негативної формули мети до безлічі Т, а потім потрібно показати, що формула
Т '= Т U {В¬ q}
є несумісною. Вважаючи, що безліч Т несуперечливо, приходимо до висновку, що Т 'може бути суперечливим внаслідок Т | - q.
Розглянемо це питання більш докладно. Спочатку до існуючого безлічі фраз додається заперечення перевіреній фрази {-q}. Потім робиться спроба резольвіровать {-q} з інший фразою в Т. При цьому існують тільки три можливі ситуації.
В Т не існує фрази, містить q. У цьому випадку довести шукане неможливо. p> Безліч Т містить {q}. У цьому випадку доказ виконується негайно, оскільки з {В¬ q} і {q} можна вивести порожню фразу, що означає несумісні (наявність протиріччя).
Безліч Т містить фразу {..., q, ...}. Резольвірованіе цієї фрази з {В¬ q} формує нову фразу, яка містить інші літерали, причому для доказу протиріччя всі вони повинні бути видалені в процесі резольвірованія.
Ці залишилися літерали можна розглядати в якості підцілей, які повинні бути дозволені, якщо потрібно досягти головної мети. Описана стратегія отримала назву низхідній (або зворотному) і дуже нагадує формулювання підцілей в системі MYCIN. p> Як приклад покладемо, що безліч Т, як і раніше, має вигляд {{В¬ p, q}, {В¬ q, В¬ r}, {p}}. Ми намагаємося показати, що Т | - В¬ r. Для цього доведемо, що фраза {r} є наслідком існуючого безлічі Т, для чого додамо до цього безлічі заперечення фрази В¬ r. Пошук протиріччя відбувається наступним чином:
[{В¬ q, В¬ r}, {r}]/{В¬ q}
[{В¬ p, q}, {В¬ q}]/{В¬ q}
[{В¬ p}, {p}]/{}
Цей метод доведення теорем отримав назву "спростування резолюції", оскільки, по-перше, він використовує правило висновку резолюцій, а по-друге, слід стратегії "від протилежного "(стратегії спростування).
Тепер повернемося до прикладу PROLOG-програми, представленому в лістингу 1. На рис. 1 показано дерево доведення твердження above (a, с). Дерево будується зверху вниз, і кожна гілка пов'язує дві "батьківські фрази", в яких містяться доповнюють літерали, з фразою, яка утворюється в результаті застосування правила резолюції. До всіх цілям, записаним праворуч від значка ": -", неявно застосовується заперечення. У лівій частині дерева представлені формули цілей, а в правій - фрази, взяті з бази даних.
Коренем дерева є порожня фраза {}. Це означає, що пошук доказу був успішним. Додавання негативної фрази: - above (а, с) до вихідного безлічі (теорії) призвело до протиріччя. Таким чином, можна ствер...
