Cтраница 1
Резолюционное доказательство Т - это конечное множество узлов вместе с множеством троек таких узлов. Каждый узел N имеет к тому же метку, обозначаемую label ( V), которая является дизъюнктом. Каждая тройка называется резолюцией. [1]
Пусть Z - резолюционное доказательство, порожденное про - - цедурой ndfind. Нетрудно показать, что Z - наименьшее ( с точностью до изоморфизма) доказательство, удовлетворяющее следующему условию. [2]
Рассмотрим следующее m - резолюционное доказательство, взятое из примера 3 разд. [3]
Пусть Т - m - резолюционное доказательство m - дизъюнкта С1 из множества w - дизъюнктов S, U - m - резолюционное доказательство из / ( S), такое что T - fU, и пусть [ / - начальное под-доказательство V. [4]
Если V - векторное m - резолюционное доказательство, а Т - обычное m - резолюционное доказательство, то мы пишем Tli ( V, Г), когда существует соответствие формы - между V и Г, такое что если N1 е Nodes ( V), N2 е Nodes ( r) и N1 - N2, то Ш ( 1аЬе1 ( ЛП), label ( 2)) истинно. [5]
Мы теперь покажем, как векторное m - резолюционное доказательство, порожденное процедурой match, можно использовать для управления поиском доказательства в исходном пространстве. [6]
Теорема 3.8. Пусть Т - минимальное m - резолюционное доказательство m - дизъюнкта С7 из множества т-дизъкнктов 5, a f - функция m - абстракции. [7]
Vk, Afl, M2) выдает векторное m - резолюционное доказательство V, обладающее следующими свойствами. [8]
В этом случае легко показать, что если Г - m - резолюционное доказательство, то существует векторное m - резолюционное доказательство W, для которого ( ЛП; Л12) ( W, Т) истинно. [9]
Если V - векторное m - резолюционное доказательство, а Т - обычное m - резолюционное доказательство, то мы пишем Tli ( V, Г), когда существует соответствие формы - между V и Г, такое что если N1 е Nodes ( V), N2 е Nodes ( r) и N1 - N2, то Ш ( 1аЬе1 ( ЛП), label ( 2)) истинно. [10]
В этом случае легко показать, что если Г - m - резолюционное доказательство, то существует векторное m - резолюционное доказательство W, для которого ( ЛП; Л12) ( W, Т) истинно. [11]
Пусть Т - m - резолюционное доказательство m - дизъюнкта С1 из множества w - дизъюнктов S, U - m - резолюционное доказательство из / ( S), такое что T - fU, и пусть [ / - начальное под-доказательство V. [12]
Мы называем depth ( N) глубиной узла N. Таким образом, резолюционное доказательство является специальным видом гиперграфа с помеченными узлами. [13]
Векторные m - резолюционные доказательства мы определим таким же способом, каким были определены т-резолюционные и обычные резолюционные доказательства. Если V-векторное m - резолюционное доказательство, то мы требуем, чтобы все векторные m - дизъюнкты из V имели одинаковое число компонент. [14]
Мы определим процедуру ndfindm, аналогичную процедуре ndfind из разд. Эта процедура использует m - абстрактные доказательства в качестве ориентира в поисках m - резолюционного доказательства. Пусть / - функция m - абстракции, дано m - резолюционное доказательство U из / ( S), и мы хотим найти все доказательства Т из S, для которых T - f U. Вместе с каждым узлом N из U мы храним множество m - clauses ( jV) m - дизъюнктов, выводимых из S т-резолюцией. [15]