Cтраница 2
Так как П получается из S применениями правила резолюций, то, согласно теореме 5.1, П есть логическое следствие S. [16]
Каждая из этих литер является кандидатом для применения правила резолюции. [17]
Интерпретатор осуществляет построение логического вывода путем последовательного применения правила резолюции к текущему целевому утверждению и к некоторой логической формуле, выбираемой из хранящейся в памяти программы. Если интерпретатору удается вывести пустую формулу, то процесс вывода заканчивается, и на выходе в качестве результата выдаются те значения переменных, которые были определены подстановками в результате последовательных унификаций. [18]
Если т меньше, чем т, то мы применяем правило резолюции к m и п, в противном случае не применяем. [19]
Если какую-либо отрицательную литеру невозможно фииировать или устранить с помощью правила резолюции, то нужно вернуться и испытать следующий по порядку подходящий хорновский дизъюнкт с новыми подстановками. [20]
Мы отмечаем, что так как S состоит только из основных единичных дизъюнктов, правило резолюции применяется в D только на последнем шаге, когда получается пустой дизъюнкт Q. Так как множество S - С является - выполнимым, то С должен встретиться в D хотя бы один раз. [21]
Так как стоп-дизъюнкт всегда содержит стоп-предикат QH, интуиция подсказывает, что мы можем ограничить возможные применения правила резолюции, потребовав, чтобы любое применение содержало QH хотя бы в одной из посылок. Так как обычно количество таких дизъюнктов вначале невелико, мы надеемся, что это сильно ограничит число порожденных промежуточных дизъюнктов Естественный вопрос - обеспечит ли такого рода стратегия порождение стоп-дизъюнкта. [22]
Итак, все дизъюнкты будем рассматривать как упорядоченные, отрезаемыми литерами могут стать лишь последние литеры посылок правила резолюций и последние литеры электронов при клаш-применении. [23]
Как можно увидеть, эти два дизъюнкта должны иметь контрарную пару литер и, следовательно, могут служить посылками правила резолюций. Если мы добавим в S дизъюнкт - Р, то мы будем иметь замкнутое семантическое дерево Т для SU - P, показанное на рис. 9, с. На рис. 9, с узел ( 1) - выводящий узел. [24]
В том частном случае, когда X - высказывание, а А и В - дизъюнкты, это правило называется правилом резолюций. Общезначимость правила резолюций выражается следующей леммой. [25]
Обобщая вышеуказанное правило и применяя его к любой паре дизъюнктов ( не обязательно единичных), мы получим следующее правило, которое назовем правилом резолюций. [26]
Дерево строится сверху вниз, и каждая ветвь связывает две родительские фразы, в которых содержатся дополняющие литералы, с фразой, которая образуется в результате применения правила резолюции. Ко всем целям, записанным справа от значка: -, неявно применяется отрицание. В левой части дерева представлены формулы целей, а в правой - фразы, взятые из базы данных. [27]
В том частном случае, когда X - высказывание, а А и В - дизъюнкты, это правило называется правилом резолюций. Общезначимость правила резолюций выражается следующей леммой. [28]
Интересно отметить, что задача о том, допускает ли ответ данный вопрос, аналогична задаче о том, завершает ли работу данная программа. В обоих случаях правило резолюции полно. [29]
На следующем шаге мы повторно применяем правило резолюции к этому множеству основных атомов и устанавливаем в итоге справедливость заключений, выводя пустой дизъюнкт. Используя метод резолюций, мы уверены, что любое высказывание, которое может принять истинное значение, получит это значение. Однако, в ПРОЛОГе мы не можем ориентировать вывод на интересующее нас высказывание, а это чрезвычайно важно для эффективного выполнения программ. [30]