Пролог, подразумевающий отрицательный предикат
Как я могу написать следующее правило в PROLOG: если P, то не Q
Я понимаю, что вы можете легко написать, если P, то Q предикаты как q(X) :- p(X), но как вы можете отрицать q/1 предикат? Я не хочу определять новые предикаты с другой семантикой, такой как non_q/1,
4 ответа
Предложение "если P, то не Q" логически эквивалентно отрицательному предложению "не P ИЛИ не Q". Таким образом, это предложение Хорна без положительного литерала, и как приложение соответствия доказательств теорем SLD и предложений Хорна, может быть представлено в программировании на Прологе как предложение цели или "запрос":
?- P, Q.
Вернемся к этой мысли через минуту.
Но пункт о цели, возможно, не тот тип представления, который вы имеете в виду. Факты и правила, которые составляют "базу знаний" Пролога, представляют собой определенные положения, то есть предложения Хорна, каждый из которых содержит только один положительный литерал. "Если P, то не Q" не имеет положительного литерала, поэтому в этом смысле он не может быть представлен (как определенное предложение).
Вышеуказанное предложение цели "спрашивает", могут ли P и Q быть доказаны. В Прологе содержится понятие "отрицание как неудача", поэтому более естественным способом "спросить", имеет ли "не ИЛИ или НЕ Q", было бы:
?- not((P,Q)).
Тогда мы добьемся успеха, если P или Q потерпит неудачу, и неудачу, если оба удастся.
Однако, если ваша цель состоит в том, чтобы утверждать отрицание чего-либо в базе знаний, Пролог естественно не поддерживает это. В зависимости от вашего приложения может существовать разумный способ обойти синтаксис Prolog и выполнить то, что необходимо (всегда есть необоснованный способ сделать это, как вы уже намекали, как с предикатом non_q).
Вы когда-нибудь слышали о разрезе в Прологе?
Во всяком случае, я не знаю много о стандарте Пролог, но в SWI-Пролог символ \+ означает отрицание. Я знаю, что это не должно работать в каждом переводчике Пролога.
Вы можете сделать отрицание предиката с разрезом Пролога. Предикат определяется как:
not(Goal) :- call(Goal),!,fail.
not(Goal).
Это означает, что цель не может быть доказана, а цель не является ложной. Может быть, эта ссылка Prolog & Cut будет полезна.
"... если P, то не Q" можно представить через -> предикат потока управления if-then (например, GNU) вместе с \+ оператор отрицания (или "недоказуемое") (например, GNU), следующим образом:
(P -> \+ Q),
Обратите внимание, что, как правило, \+ будет реализовывать то, что известно как отрицание как неудача; то есть подцель / выражение \+ Q преуспеет, если Q не могу. Обратите внимание, что оценка Q под \+ не повлияет на привязки любых переменных, присутствующих в выражении Q при исполнении.
Например, рассмотрим:
foo(a).
bar(b).
Учитывая эти факты, справедливо следующее:
foo(a) -> \+ bar(a). % succeeds, as bar(a) is not provable.
foo(a) -> \+ bar(b). % fails, as bar(b) is provable.
foo(a) -> \+ bar(X). % fails, as bar(X) is provable; note that X remains unbound.
foo(X) -> \+ bar(X). % succeeds, as bar(X) where X unified to 'a' isn't provable.
Реализация чего-то похожего на \+ q(X) :- p(X) как вы, возможно, захотите (с точки зрения "правила") не так просто, как вы описываете, однако потенциальный взлом:
q(X) :- p(X), !, fail.
Это определение будет отражать только намерение q(X) это потерпеть неудачу для всех X где p(X) успешно, если он утверждается перед любыми другими пунктами q(X), но не может быть идеальным.
Вы можете использовать минимальную логику, чтобы определить отрицательную голову. В минимальной логике ~A можно рассматривать как A -> ff. Таким образом, следующее
P -> ~Q
Можно рассматривать как:
P -> (Q -> ff).
Теперь, если мы возьмем следующее тождество (A -> (B -> C)) = (A & B -> C), мы увидим, что вышеприведенное эквивалентно:
P & Q -> ff.
Теперь есть одна проблема, как мы можем задавать отрицательные запросы? Есть один способ использовать минимальную логику, которая отличается от отрицания как неудачи. Идея заключается в том, что запрос формы:
G |- A -> B
отвечает, временно добавив A в программу пролога G, а затем попытавшись решить B, т.е. выполнив следующие действия:
G, A |- B
Теперь давайте обратимся к нотации Пролога, покажем, что p, а p -> ~q подразумевает ~ q, выполняя (минимальную логику) программу Prolog. Пролог программы:
p.
ff :- p, q.
И запрос:
?- q -: ff.
Сначала нам нужно определить новый соединительный элемент (-:)/2. Быстрое решение заключается в следующем:
(A -: B) :- (assert(A); retract(A), fail), B, (retract(A); assert(A), fail).
Здесь вы видите реализацию этого минимального логического отрицания в SWI Prolog:
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 5.10.4)
Copyright (c) 1990-2011 University of Amsterdam, VU Amsterdam
1 ?- [user].
:- op(1200,xfy,-:).
|: (A -: B) :- (assertz(A); retract(A), fail), B, (retract(A); assertz(A), fail).
|: p.
|: ff :- p, q.
|:
% user://1 compiled 0.02 sec, 1,832 bytes
true.
2 ?- q -: ff.
true .
С уважением
Ссылка: Дейл Миллер, Гопалан Надатур, Фрэнк Пфеннинг, Андре Счедров: Унифицированные доказательства как основа логического программирования (1989)