Методи пошуку рішень на основі числення предикатів

Семантика числення предикатів забезпечує основу для формалізації логічного висновку. Можливість логічно виводити нові правильні вирази з набору істинних тверджень дуже важлива. Логічно виведені затвердження коректні, і вони сумісні з усіма попередніми інтерпретаціями початкового набору виразів. Обговоримо вищесказане неформально і потім введемо необхідну формалізацію.

У численні висловів основним об'єктом є змінне висловлювання (предикат), істинність або хибність якого залежить від значень назв змінних. Так, істинність предиката "x був фізиком" залежить від значення змінної x. Якщо x - П. Капіца, то предикат істинний, якщо x - М. Лермонтов, то він хибна. Мовою числення предикатів твердження читається так: "для будь-якого x якщо P (x), то має місце і Q (x)". Іноді його записують і так: . Виділене підмножина тотожне справжніх формул (або правильно побудованих формул - ППФ), істинність яких не залежить від істинності входять до них висловлювань, називається аксіомами.

У численні предикатів є безліч правил виведення. Як приклад наведемо класичне правило відділення, або modus ponens:

яке читається так "якщо істинна формула A і істинно, що з A слід B, то істинна і формула B". Формули, що знаходяться над рисою, називаються посилками виводу, а під рискою - висновком. Це правило виведення формалізує основний закон дедуктивних систем: з істинних посилок завжди слідують справжні ув'язнення. Аксіоми і правила виводу числення предикатів першого порядку задають основу формальної дедуктивної системи, в якій відбувається формалізація схеми міркувань в логічному програмуванні. Можна згадати й інші правила виведення.

Modus tollendo tollens: Якщо з A слід B і B помилково, то і A помилково.

Modus ponendo tollens: Якщо A і B не можуть одночасно бути істинними і A істинно, то B помилково.

Modus tollendo ponens: Якщо або A, або B є істинним і A неправдиве, то B істинно.

Можна вирішити завдання представляється у вигляді тверджень (аксіом) f1, F2 ... Fn обчислення предикатів першого порядку. Мета завдання B також записується у вигляді твердження, справедливість якого слід встановити або спростувати на підставі аксіом і правил виведення формальної системи. Тоді рішення задачі (досягнення мети завдання) зводиться до з'ясування логічного слідування (виводимості) цільової формули B з заданої множини формул (аксіом) f1, F2 ... Fn. Таке з'ясування рівносильно доказу общезначимости (тотожно-істинності) формули

або нездійсненності (тотожно-хибності) формули

З практичних міркувань зручніше використовувати доказ від протилежного, тобто доводити нездійсненність формули. На доказ від протилежного засноване і веде правило виведення, що використовується в логічному програмуванні, - принцип резолюції. Робінсон відкрив сильніше правило виведення, ніж modus ponens, яке він назвав принципом резолюції (або правилом резолюції). При використанні принципу резолюції формули обчислення предикатів за допомогою нескладних перетворень приводяться до так званої диз'юнктивній формі, тобто представляються у вигляді набору диз'юнктів. При цьому під диз'юнкт розуміється диз'юнкція літералів, кожен з яких є або предикатом, або запереченням предиката.

Наведемо приклад диз'юнкт:

Нехай P - предикат поважати, c1 - Ключевський, Q - предикат знати, c2 - історія. Тепер даний диз'юнкт відображає факт "кожен, хто знає історію, поважає Ключевського".

Наведемо ще один приклад диз'юнкт:

Нехай P - предикат знати, c1 - фізика, c2 - історія. Даний диз'юнкт відображає запит "хто знає фізику і історію одночасно".

Таким чином, умови вирішуваних завдань (факти) і цільові затвердження завдань (запити) можна виразити в диз'юнктивній формі логіки предикатів першого порядку. У диз'юнкт квантори загальності , Зазвичай опускаються, а зв'язки замінюються на імплікації.

Повернемося до принципу резолюції. Головна ідея цього правила виведення полягає в перевірці того, чи містить безліч диз'юнктів R порожній (помилковий) диз'юнкт. Зазвичай резолюція застосовується з прямим або зворотним методом міркування. Прямий метод з посилок A, A -> B виводить висновок B (правило modus ponens). Основний недолік прямого методу полягає в його не направлення: повторне застосування методу призводить до різкого зростання проміжних висновків, не пов'язаних з цільовим висновком. Зворотний висновок є спрямованим: з бажаного укладення B і тих же посилок він виводить нове подцелевое висновок A. Кожен крок виведення в цьому випадку пов'язаний завжди з спочатку поставленої мети. Істотний недолік методу резолюції полягає в формуванні на кожному кроці виведення безлічі резольвент - нових диз'юнктів, більшість з яких виявляється зайвими. У зв'язку з цим розроблені різні модифікації принципу резолюції, що використовують більш ефективні стратегії пошуку і різного роду обмеження на вид вихідних диз'юнктів. У цьому сенсі найбільш вдалою і популярною є система ПРОЛОГ, яка використовує спеціальні види диз'юнктів, званих диз'юнкт Хорна.

Процес докази методом резолюції (від зворотного) складається з наступних етапів:

1. Пропозиції або аксіоми приводяться до диз'юнктивній нормальній формі.
2. До набору аксіом додається заперечення доказуваного затвердження в диз'юнктивній формі.
3. Виконується спільне вирішення цих диз'юнктів, в результаті чого виходять нові засновані на них диз'юнктивні вираження (резольвенти).
4. Генерується порожній вираз, що означає протиріччя.
5. Підстановки, використані для отримання порожнього вираження, свідчать про те, що заперечення заперечення істинно.

Розглянемо приклади застосування методів пошуку рішень на основі числення предикатів. Приклад "цікаве життя" запозичений з [1.1] . Отже, задані твердження 1-4 в лівому стовпчику таблиця 3.2 Потрібно відповісти на питання: "Чи існує людина, що живе цікавим життям?" У вигляді предикатів ці твердження записані в другому стовпці таблиці. Передбачається, що . У третьому стовпці таблиці записані диз'юнкт.

Заперечення укладення має вигляд (рядок 6):

Одне з можливих доказів (їх більше одного) дає наступну послідовність резольвент:

1. резольвента 6 і 4
2. резольвента 7 і 1
3. резольвента 8 і 2
4. резольвента 9 і 3b
5. NIL резольвента 10 і 3a

Символ NIL означає, що база даних виразів містить протиріччя і тому наше припущення, що не існує людина, що живе цікавим життям, невірно.

У методі резолюції порядок комбінації діз'юнктівних виразів не встановлювався. Значить, для великих завдань буде спостерігатися експоненціальне зростання числа можливих комбінацій. Тому в процедурах резолюції велике значення мають також евристики пошуку і різні стратегії. Одна з найбільш простих і зрозумілих стратегій - стратегія переваги одиничного вираження, яка гарантує, що резольвента буде менше, ніж найбільше батьківське вираз. Адже в підсумку ми повинні отримати вираз, що не містить литералов взагалі.

Серед інших стратегій (пошук в ширину (breadth-first), стратегія "безлічі підтримки", стратегія лінійної вхідний форми) стратегія "безлічі підтримки" показує відмінні результати при пошуку в великих просторах діз'юнктівних виразів [1.1] . Суть стратегії така. Для деякого набору вихідних діз'юнктівних виразів S можна вказати підмножина T, зване безліччю підтримки. Для реалізації цієї стратегії необхідно, щоб одна з резольвент в кожному спростування мала предка з безлічі підтримки. Можна довести, що якщо S - нездійсненний набір диз'юнктів, а ST - здійсненний, то стратегія безлічі підтримки є повною в сенсі спростування. З іншими стратегіями для пошуку методом резолюції в великих просторах діз'юнктівних виразів читач може познайомитися в спеціальній літературі [1.1] , [3.1] , [3.2] .

Дослідження, пов'язані з доказом теорем і розробкою алгоритмів спростування резолюції, призвели до розвитку мови логічного програмування PROLOG (Programming in Logic). PROLOG заснований на теорії предикатів першого порядку. Логічна програма - це набір специфікацій в рамках формальної логіки. Незважаючи на те, що в даний час питома вага мов LISP і PROLOG знизився і при вирішенні завдань ІІ все більше використовуються C, C ++ і Java, проте багато завдань і розробка нових методів вирішення завдань ІІ продовжують спиратися на мови LISP і PROLOG. Розглянемо одну з таких задач - задачу планування послідовності дій та її рішення на основі теорії предикатів.