Почему двойное отрицание не связывается в Прологе

Скажем, у меня есть следующая теория:

a(X) :- \+ b(X).

b(X) :- \+ c(X).

c(a).

Он просто говорит истина, что, конечно, правильно, a(X) истинно, потому что нет b(X) (с отрицанием как конечный отказ). Поскольку есть только b(X), если нет c(X), а у нас есть c(a), можно утверждать, что это правда. Однако мне было интересно, почему Пролог не дает ответа X = a? Скажем, например, я ввожу некоторую семантику:

noOrphan(X) :- \+ orphan(X).

orphan(X) :- \+ parent(_,X).

parent(david,michael).

Конечно, если я запрошу noOrphan(michael), это приведет к true и noOrphan(david) в false (поскольку я не определил родителя для david)., Но мне было интересно, почему нет упреждающего способа определить, какие люди (michael, david ,. ..) принадлежат noOrphan/1 отношению?

Это, вероятно, является результатом механизма обратного отслеживания Prolog, но Prolog может поддерживать состояние, которое проверяет, выполняется ли поиск в положительном направлении (0,2,4, ...) в глубоком отрицании или в отрицательном направлении (1,3 , 5, ...) отрицания глубокие.


person Willem Van Onsem    schedule 14.10.2013    source источник
comment
Может ли это иметь какое-то отношение к тому, делает ли пролог предположение о закрытом мире?   -  person axblount    schedule 15.10.2013
comment
Well \+ основан на двух предположениях: отрицание как конечный отказ и допущение замкнутого мира. Однако, насколько мне известно, привязка по-прежнему действует при обоих предположениях ...   -  person Willem Van Onsem    schedule 15.10.2013
comment
Это семантическая проблема, \+, а также not не означают not как в логике, а просто недоказуемо (под cwa). В этом смысл отрицания как неудачи в SLD.   -  person rano    schedule 16.10.2013


Ответы (2)


Начнем с чего попроще. Скажите \+ X = Y. Здесь отрицаемая цель - это предопределенный встроенный предикат. Так что все еще яснее: X и Y должны быть разными. Однако \+ X = Y терпит неудачу, потому что X = Y успешно. Таким образом, не осталось и следа, при каком именно условии гол не удался.

Таким образом, \+ \+ X = Y действительно дает пустой ответ, а не ожидаемый X = Y. Дополнительную информацию см. в этом ответе.

Учитывая, что такие простые запросы уже показывают проблемы, вы не можете ожидать слишком многого от определенных пользователем целей, таких как ваша.

В общем случае вам придется сначала пересмотреть, что вы на самом деле имеете в виду под отрицанием. Ответ намного сложнее, чем кажется на первый взгляд. Подумайте, программа p :- \+ p. должна p быть успешной или неудачной? Должно p быть правдой или нет? На самом деле здесь есть две модели, которые больше не вписываются в представление Пролога о минимальной модели. Соображения, поскольку они открыли новые ветви логического программирования, такие как программирование набора ответов (ASP).

Но остановимся на Прологе. Отрицание можно использовать только в очень ограниченном контексте, например, когда цель достаточно конкретизирована, а определение стратифицировано. К сожалению, общепринятых критериев безопасного выполнения поставленной цели не существует. Мы могли бы подождать, пока цель не станет переменной свободной (наземной), но это часто означает, что нам приходится ждать слишком долго - на жаргоне: отрицаемая цель не работает.

Таким образом, общее отрицание не очень хорошо сочетается с программами на чистом Prolog. Суть Пролога - это чистая, монотонная подмножество языка. Однако в части ограничений Пролога (или его соответствующих расширений) отрицание может работать достаточно хорошо.

person false    schedule 15.10.2013

Я могу неправильно понять вопрос, и я не понимаю последний абзац.

В любом случае, есть совершенно верный способ определить, какие люди не являются сиротами. В вашем примере вы забыли сообщить компьютеру то, что вам известно, а именно:

person(michael).
person(david).
% and a few more
person(anna).
person(emilia).

not_orphan(X) :- \+ orphan(X).
orphan(X) :- person(X), \+ parent(_, X).

parent(david, michael).
parent(anna, david).

?- orphan(X).
X = anna ;
X = emilia.

?- not_orphan(X).
X = michael ;
X = david ;
false.

Я не знаю, как именно вы хотите определить «сироту», поскольку это определение определенно немного странно, но дело не в этом.

В заключение: вы не можете ожидать, что Prolog узнает, что michael, david и все остальные - люди, если вы не укажете это явно. Вам также необходимо прямо указать, что orphan или not_orphan - это отношения, которые применимы только к людям. Мир, который вы моделируете, также может иметь:

furniture(red_sofa).
furniture(kitchen_table).
abstract_concept(love).
emotion(disbelief).

и вам нужен способ оставить их вне своих семейных дел.

Надеюсь, это поможет.

person Community    schedule 15.10.2013
comment
Дело в том, что с момента, когда дерево выполнения вложено в 2 отрицания на глубину, можно было бы сделать вывод, что состояние parent(_,X) равно a(X), и, таким образом, перечисление отношения no_orphans становится возможным. - person Willem Van Onsem; 15.10.2013
comment
Конечно, учитывая механизм выполнения Prolog, разумно, чтобы переменная была неограниченной, и мне было интересно, почему такие привязки не реализованы в Prolog, поскольку по крайней мере некоторые из них могут выполняться на лету или во время компиляции. - person Willem Van Onsem; 15.10.2013
comment
@CommuSoft Я наконец понял ваш вопрос. Думаю, дело здесь в том, что если вы не определите, какие основные термины могут быть (или не могут быть) сиротой, любой, кто не является сиротой (\+ orphan(X)), будет not_orphan. В вашем исходном примере неявное знание того, что michael и david являются людьми, недоступно для Prolog. Конечно, тогда любой может быть not_orphan (поэтому запрос правильно успешно выполняется с переменной). - person ; 15.10.2013
comment
ну с двойным отрицанием, это можно сделать. Я определил метод преобразования, который должен иметь возможность преобразовывать любую программу Prolog (кроме метапрограммирования и других сложных вещей), чтобы преобразовать ее в эквивалентную программу, в которой значения могут быть перечислены. В настоящее время я пишу прекомпилятор и планирую изменить существующую реализацию Prolog. - person Willem Van Onsem; 15.10.2013
comment
@CommuSoft Я, вероятно, ошибаюсь, но единственный способ, которым это может закончиться в эквивалентных программах, - это явно указать, какой предикат должен сделать термин основанием. На этом этапе вы сделали полный круг. - person ; 15.10.2013