Cтраница 1
Метод резолюции предполагает, что мы рассматриваем отрицание исходной формулы и пытаемся показать, что полученная формула - противоречива. Если это действительно так, то исходная формула представляет собой тавтологию. Процесс, приводящий к искомому противоречию, состоит из отдельных шагов, на каждом из которых применяется резолюция. [1]
Метод резолюций заключается в проверке условия содержания в множестве формул S так называемого пустого ( или ложного) дизъюнкта. Если в множестве S содержится пустой дизъюнкт, то множество S невыполнимо. Если может, то множество 5 невыполнимо. [2]
Метод резолюций, получив на вход логическую программу с присоединенным к ней запросом в виде множества хорновских дизъюнктов, пытается построить вывод пустого дизъюнкта, обозначаемого символом D. Если это ему удается, тогда цель допускается, в противном случае отвергается. Реализуется метод резолюций с помощью двух правил: правила резолюции и правила склейки, которые во время работы вызывают процедуру унификации - сопоставления. [3]
Метод резолюций совершенно естествен. [4]
Метод резолюций изобразим графически в виде дерева опровержения ( рис. 2.23), в вершины которого поместим дизъюнкты, содержащие контрарные пары. [5]
Метод резолюции требует, чтобы мы делали подстановки в дизъюнкты так, чтобы две литеры с противоположными знаками содержали совпадающие атомы. Так как эти атомы могут содержать переменные, можно делать и дальнейшие подстановки вместо них, а литеры по-прежнему будут отличаться только знаками. [6]
Метод резолюций работает в значительной степени вслепую, осуществляя полный перебор всех возможных резольвент. Значительное улучшение эффективности метода резолюций было достигнуто путем использования специальных эвристик, которые обеспечивают направленность перебора резольвент и получили название стратегий резолюций. [7]
Практически метод резолюций состоит в следующем. [8]
Используя метод резолюций, докажите, что множество дизъюнктов в упражнении 14 к главе 4 невыполнимо. [9]
Хотя метод резолюций в наибольшей общности неэффективен, он эффективен в некоторых частных случаях. [10]
Докажем методом резолюций, что формула S является логическим следствием системы аксиом FI - Ь / Ч, для этого выполним г. начале операцию их стандартизации. [11]
Представленный здесь метод резолюций называется фундаментальным, так как он использует фундаментальные конкретизации дизъюнктов. [12]
Чтобы приспособить метод резолюций для исчисления предикатов с равенством, были предложены разнообразные приемы. Основной принцип, заложенный в них, состоит в возможности замены терма равным термом. Заметим, что, за исключением явно искусственных случаев, доказательства обычно очень длинны. [13]
Замечание 2.9.12. Метод резолюций фактически является развитием и упрощением соответствующих методов работы с логикой предикатов. [14]
Основная идея метода резолюций состоит в том, чтобы проверить, содержит ли S пустой дизъюнкт П - Если S содержит Q, то S невыполнимо. Если S не содержит П, то проверяется следующий факт: может ли П быть получен из S. Будет ясно позднее, что по теореме Эрбрана ( вариант I) проверка получения Q эквивалентна подсчету числа узлов замкнутого семантического дерева для S. По теореме 4.3 S невыполнимо тогда и только тогда, когда существует конечное замкнутое семантическое дерево Т для S. Ясно, что S содержит П тогда и только тогда, когда Т состоит только из одного узла - корневого узла. [15]