озіціональние змінні, як і раніше.
Якщо U і ф представляють дві довільні фрази, які можна представити у кон'юнктивній нормальній формі, і
U = {U1, ..., Ui, ...., Um},
і
ф = {ф1 ..., фi ....., фn}, і
Ui, = В¬ фi при 1 [i [mm, 1 [j [n,
то нову фразу ВЈ можна вивести з об'єднання U 'і ф', де
U '= U В¬ {Ui} і ф' = ф В¬ {ф,}.
Фраза ВЈ = U 'і ф' називається резольвенти кроку резолюції, а U і ф є батьківськими фразами. Іноді кажуть, що U та ф "стикаються" на парі доповнюють літералів Ui, і фj.
Потужність резолюції забезпечується тим, що в ній підсумовується безліч інших правил. Це стане очевидно після того, як звичайні правила будуть представлені в кон'юнктивній нормальній формі.
У лівій колонці табл. 1 перераховані найменування правил виводу, в середній показано, як вони виглядають в звичайних позначеннях, а в правій колонці - у фразовой формі. У кожного запису вираження у верхній частині представляють схему передумов, а вирази в нижній частини - схему висновків. З цієї таблиці видно, що кожне із цитованих вище п'яти правил є одним з примірників резолюції:
Таблиця 1 . Узагальнення резолюції. br/>
Правило виводу
Звичайна форма
Кон'юнктивна нормальна форма
Modus ponens
(Uф, U)/Ф
{В¬ U, Ф}, {U}/{ф}
Modus fallens
(Uф. В¬ ф) /-U
{В¬ U, ф}, {-, ф}/{-U}
Зчеплення
(Uф, ф ВЈ) (U ВЈ)
{В¬ U, ф}, {В¬ ф, ВЈ}/{В¬ U, ВЈ}
Злиття
(Uф, В¬ U ф)/ф
{U, ф}, {В¬ U, ф}/{ф}
Reductio
(U, В¬ U)/|
{В¬ U}, {U}/{}
Протиріччя в правилі, яке зазвичай позначається значком 1, дає в результаті порожню фразу-{}. Це означає, що передумови несумісні. Якщо вважати, що передумови описують деякий стан предметної області, то такий набір передумов не може бути реально забезпечений в ній, тобто такий стан неможливо.
Головне, що компонент автоматичного доведення теорем, який є основним компонентом більшості систем штучного інтелекту і, зокрема, мов програмування штучного інтелекту, таких як PROLOG, є системою, спростування резолюцій. Для того щоб довести, що р випливає з деякого опису стану (або теорії) Т, потрібно покласти-р і спробувати довести, що з цього припущення випливає твердження, що суперечить Т. Якщо це вдасться зробити, то тим самим підтверджується твердження р, а в іншому випадку воно спростовується.
У численні предикатів використання резолюцій вимагає додаткових зусиль, оскільки в цьому обчисленні присутні змінні. Основна операція зіставлення в доказі теорем за допомогою резолюцій називається уніфікацією. При зіставленні доповнюють літералів відшукується така підстановка змінних, яка перетворює обидва вирази в ідентичні.
Наприклад, вирази БЕЖІТ_БИСТРЕЕ_ЧЕМ (Х, равлик) і БЕЖІТ_БИСТРЕЕ _ЧЕМ (черепаха, Y) перетворюються на ідентичні при підстановці {Х/черепаха, Y/равлик}. Така підстановка називається уніфікатором. Наша мета - відшукати найбільш загальну підстановку такого роду. br/>
3.4 Пошук докази в системі резолюцій
Резолюція являє собою правило висновку, за допомогою якого можна вивести нову ППФ (правильно побудовану формулу) зі старої. Проте в наведеному вище описі логічної системи нічого не говориться про те, як виконати доказ. Звернемо основну увагу на стратегічні аспекти доведення теорем.
Нехай р представляє твердження "Сократ - це людина", aq - затвердження "Сократ смертний". Нехай наша теорія має вигляд
Т = {{В¬ р, q}, {р}}.
Таким чином, стверджується, що якщо Сократ людина, то Сократ смертний, та що Сократ - людина. {17} виводиться з теорії Т за один крок резолюції, еквівалентної правилом modus ponens. . p> Вирази {В¬ р, q} і {р} "Стикаються" на парі доповнюють літералів р і В¬ р, а {q} є резольвенти. Таким чином, теорія алогічне увазі д, що записується у формі Т |-q. Тепер можна додати нову фразу {q} - резольвенту - В теорію Т...
