Резолюция

Выше было показано, что все рассматривавшиеся до сих пор правила логического вывода являются непротиворечивыми, но вопрос об их полноте применительно к алгоритмам логического вывода, в которых они используются, еще не обсуждался. Алгоритмы поиска, такие как поиск с итеративным углублением (с. 133), являются полными в том смысле, что позволяют найти любую достижимую цель, но если доступные правила логического вывода неадекватны, то цель становится недостижимой; это означает, что не существует доказательства, в котором могли бы применяться только эти правила логического вывода. Например, если мы откажемся от использования правила удаления двухсторонней импликации, то не сможем довести до конца доказательство, изложенное в предыдущем разделе. А в настоящем разделе представлено единственное правило логического вывода, правило резолюции, позволяющее получить алгоритм логического вывода, который становится полным в сочетании с любым полным алгоритмом поиска.
Начнем с использования простой версии правила резолюции в мире вампуса. Рассмотрим шаги, ведущие вверх на рис. 7.3, а: агент возвращается из квадрата [2,1] в квадрат [ 1,1 ], а затем переходит в квадрат [ 1, 2 ], где он чувствует неприятный запах, но не ощущает ветерка. Введем следующие дополнительные факты в базу знаний:
#11: -iBi,2
Д12: Bi.2 <=> {Pi.i v P2,2 v Pi/3)
С помощью того же процесса, который привел к получению высказывания д10, приведенного выше, мы теперь можем сделать заключение об отсутствии ям в квадратах [2,2] и [1,3] (напомним, что в отношении квадрата [1,1] уже известно, что в нем нет ям):
#13: ->Р2,2 #14: -.Pi,3
Кроме того, можно применить к высказыванию #3 правило удаления двухсторонней импликации, после чего применить к полученному результату в сочетании с высказыванием R5 правило отделения, чтобы выяснить тот факт, что по меньшей мере в одном из квадратов [1,1], [2,2] или [3,1] есть яма:
#15: Pi.i V Р2(2 v Р3,1
Именно здесь возникают условия, позволяющие впервые использовать правило резолюции (правило устранения противоречия): литерал -iP2<2 в высказывании #13, противоположный литералу Р2/2 в высказывании R15i устраняется, что приводит к получению следующего высказывания:
#ie: Pi.i v P3,i
Соответствующий ход рассуждения можно выразить словами таким образом: если по меньшей мере в одном из квадратов [1,1], [2,2] или [3,1] имеется яма, но ее нет в квадрате [2,2], то яма должна быть, по крайней мере, в квадрате [1,1] или [3,1]. Аналогичным образом, устраняется литерал ~Plfl в высказывании Rl9 противоположный литералу Р1Л в высказывании д1б, что приводит к получению следующего высказывания:
Rn: P3,i
Соответствующий ход рассуждений можно выразить словами таким образом: если по меньшей мере в одном из квадратов [1,1] или [3,1] есть яма, но ее нет в квадрате [ 1,1 ], то она находится в квадрате [3,1]. Эти два последних этапа логического вывода представляют собой примеры применения правила логического вывода, называемого правилом единичной резолюции:
li У ... v Ik, т
Јi v ... v /i-i v v ... v 4
где каждое из выражений Р представляет собой литерал, а выражения ЈL и т являются взаимно обратными литералами (т.е. такими литералами, что один из них является отрицанием другого). Таким образом, в правиле единичной резолюции берется выражение (дизъюнкция литералов) и еще один литерал, после чего формируется новое выражение. Обратите внимание на то, что этот единственный литерал может рассматриваться как дизъюнкция из одного литерала, называемая также единичным выражением.
Правило единичной резолюции может быть также обобщено до правила полной резолюции:
li У ... У ?к, mi У ... У тп
l\ V ... V V h + l V .,. V 4 V UIi V ... V 2T7j_i V I77j+i V ... V ЛЗП
где Јi и — взаимно обратные литералы. Если бы мы имели дело только с выражениями, имеющими длину два, то могли бы записать данное правило следующим образом:
h v ?ъ
Это означает, что в правиле резолюции берутся два выражения и вырабатывается новое выражение, содержащее все литералы двух первоначальных выражений, за исключением двух взаимно обратных литералов. Например, может иметь место такой логический вывод:
Pl,l V РЗ,1/ ~>Pl,l V -»Р2,2 РЗД V -iP2,2
11 Если некоторое выражение рассматривается как множество литералов, то такое правило сокращения применяется автоматически. Использование для логических выражений системы обозначений в виде множеств позволяет сделать правило резолюции более понятным, но за счет введения дополнительных обозначений.
Процесс применения правила резолюции связан с необходимостью выполнения еще одного формального требования: результирующее высказывание должно содержать только по одной копии каждого литерала11. Операция удаления дополнительных копий литералов называется факторизацией. Например, после удаления противоположных друг другу литералов в выражениях (A v В) и (A v -нВ) будет получено выражение (A v А), которое следует сократить до А
Непротиворечивость правила резолюции можно легко доказать, рассматривая литерал 4- Если литерал 4 является истинным, то литерал т5 является ложным, и поэтому выражение v ... v v v ... v mn должно быть истинным, поскольку дано, что истинно выражение т1 v ...v тп. Если литерал 4 является ложным, то должно быть истинным выражение 4 v ...v ЈL.xv Јi+1v...v 4, поскольку дано, что истинно выражение 4 v ...v 4- Итак, литерал 4 является либо истинным, либо ложным, поэтому справедливо одно или второе из этих заключений, а именно это утверждается в правиле резолюции.
Еще более привлекательным свойством правила резолюции является то, что оно образует основу для семейства полных процедур логического вывода. Любой полный алгоритм поиска, в котором применяется только правило резолюции, позволяет вывести любое заключение, которое следует из любой базы знаний в пропозициональной логике. Тем не менее необходимо сделать одно предупреждение: правило резолюции является полным только в узком смысле этого понятия. Если известно, что высказывание А истинно, правило резолюции нельзя использовать для автоматического формирования следствия A v в. Однако в этом случае правилом резолюции можно воспользоваться для поиска ответа на вопрос, является ли истинным высказывание A v Б. Это свойство правила резолюции называется полнотой опровержения (refutation completeness) и означает, что правило резолюции может всегда использоваться либо для подтверждения, либо для опровержения какого-то высказывания, но его нельзя применять для перебора всех истинных высказываний. В следующих двух подразделах описано, как может использоваться правило резолюции для осуществления логического вывода.







Материалы

Яндекс.Метрика