Программирование на языке пролог

левая_часть (NT,S0,S,P):- nonvar(NT), tag(NT,SO,S,P).

правая_часть((Х1,Х2),S0,S,Р):- правая_часть(Х1,S0,S1,Р1), правая_часть(X2,Sl,S,P2), и(Р1,Р2,Р).

правая_часть((Xl;X2),S0,S,(P1;P2)):-!, или(Xl,S0,S,P1), или(Х2,S0,S,Р2).

правая_часть(Р,S,S,Р):-!.

правая_часть(!,S,S,!):-!.

правая_часть(Ts,SO,S,true):- явл_списком(Тs),!, присоединить(Ts, S,S0).

правая_часть(Х,S0,S,P):- tag(X,S0,S,P).

или(Х,S0,S,Р):- правая_часть(X,S0a,S,Pa), (var(S0a), S0a=S,!, S0=S0a, P=Pa; P=(S0=S0a,Pa)).

tag(X,S0,S,P):- X =..[F|A], присоединить(А,[S0,S],АХ), P =.. [F|AX].

и(true,P,P):-!.

и(P,true,P):-!.

и(P,Q,(P,Q)).

лин(А,А):- var(A),!.

лин((А,В),С):-!, лин1(А,С,R), лин(В,R).

лин(А,А).

лин1(А,(А,R),R):- VAR(A),!.

лин1((А,В),С,R):-!, лин1(А,С,R1), лин1(В,R1,R).

лин1(A,(A,R),R) .

явл_списком([]):-!.

явл_списком([_|_]).

присоединить([А|В],С,[А|D]):- присоединить(В,С,D).

присоединить([], X, X).

Упражнение 9.2.Определение универсальной версии предиката phrase (словосочетание)выглядит следующим образом:

phrase(Cтип,Слова):- Стип =.. [Pred|Args], присоединить(Args,[Слова,[]],Newargs), Цель =.. [Pred|Newargs], call (Цель).

где присоеднитьопределен так же как в разд. 3.6.

ПРИЛОЖЕНИЕ В. ПРОГРАММА ПРИВЕДЕНИЯ ФОРМУЛ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ К СТАНДАРТНОЙ ФОРМЕ

Как было обещано в гл. 10, мы проиллюстрируем процесс преобразования формулы исчисления предикатов в стандартную форму, представив фрагменты программы на Прологе, выполняющей это преобразование. Верхний уровень программы выглядит следующим образом:

translate(X):-

 implout(X,Xl), /* Этап 1 */

 negin(Xl,X2), /* Этап 2 */

 skolem(X2,X3,[]), /* Этап 3 */

 univout(X3,X4), /* Этап 4 */

 conjn(X4,X5), /* Этап 5 */

 clausify(X5,Clauses, []), /* Этап 6 */

 pclauses(Clauses). /* Печать дизъюнктов */

Здесь приведено определение предиката translate, действующего таким образом, что, если выполнить целевое утверждение translate(X), где X– это формула исчисления предикатов, то программа напечатает эту формулу в стандартной форме в виде последовательности дизъюнктов. В этой программе формулы исчисления предикатов представляются в виде структур языка Пролог, как на это указывалось ранее (в гл. 10). Однако мы сделаем некоторое отступление от предыдущего описания и будем представлять переменные, входящие в формулы исчисления предикатов, атомами языка Пролог, с целью облегчить их обработку. Предполагается, что можно отличить переменные в формулах исчисления предикатов от констант, используя некоторое соглашение относительно формы записи имен. Например, можно считать, что имена переменных всегда начинаются с одной из букв х, у, z. В действительности, переменные всегда вводятся в формулу посредством кванторов и, следовательно, их легко можно опознать. Лишь при чтении результата, печатаемого программой, программисту необходимо помнить, какие имена соответствуют переменным формул исчисления предикатов, а какие константам.

Прежде всего, необходимо объявить операторы для логических связок, используемых в формулах:

?- op(30,fx,~).

?- op(100,xfy,#).

?- op(100,xfy,&).

?- op(150,xfy,-›).

?- op(150,xfy,‹-›).

Следует обратить внимание на то, как определены операторы. В частности ~ имеет более низкий приоритет чем # и &. Для начала, необходимо сделать одно важное предположение. Предполагается, что переменные переименованы таким образом, что в обрабатываемой формуле одна и та же переменная никогда не вводится более чем одним квантором. Это необходимо, чтобы предотвратить возможные конфликты в употреблении имен в дальнейшем.

Для преобразования формул к стандартной форме мы используем метод преобразования дерева, обсуждавшийся в разд. 7.11 и 7.12. При представлении логических связок как функторов, формулы исчисления предикатов превращаются в структуры, которые могут быть изображены в виде деревьев. Каждый из шести основных этапов перевода в стандартную форму представляет некоторое преобразование дерева, которое отображает входное дерево в выходное.

Этап 1 - исключение импликаций

Определим предикат imploutтак, что implout(X, Y)означает, что формула Yполучается из формулы Xпутем исключения всех импликаций.

implout((P ‹-› Q), (P1 & Q1) # (~Р1 & ~Q1))):- !, implout(P,Pl), implout(Q,Ql).

implout((P -› Q),(~P1 # Q1)):-!, implout(P,P1), implout(Q,Q1).

implout(all(X,P),all(X,P1)):- !.

implout(exists(X,P),exists(X,P1)):-!, implout(P, P1).

implout((P & Q),(P1 & Q1)):- !, implout(P,P1), implout(Q,Q1).

implout((P # Q),(P1 # Q1)):-!, implout(P,P1), implout(Q,Q1).

implout((-P),(~Pl)):-!, implout(P,P1).

implout(P,P).

Этап 2 - перенос отрицания внутрь формулы