Logische Programmierung Einf¨uhrende Beispiele · • Eine Unit-Klausel (oder Fakt) ist eine deﬁnite Klausel mit leerem Rumpf. Notation: A ⇐. KI, SS 06, Fol7, Seite 10, 8. Juni2006

Logische Programmierung

Einfuhrende Beispiele

Verwandschaftsbeziehungen in Prolog

vater(peter,maria).

mutter(susanne,maria).

vater(peter,monika).

mutter(susanne,monika).

vater(karl, peter).

mutter(elisabeth, peter).

vater(karl, pia).

mutter(elisabeth, pia).

vater(karl, paul).

mutter(elisabeth, paul).

KI, SS 06, Fol7, Seite 1, 8. Juni2006

Logische Programmierung

Einfuhrende Beispiele

frau(maria).

frau(elisabeth).

frau(susanne).

frau(monika).

frau(pia).

mann(peter).

mann(karl).

mann(paul).


Prolog: einfuhrendes Beispiel

eltern(X,Y) :- vater(X,Y).

eltern(X,Y) :- mutter(X,Y).

%%%%% einfach aber nicht terminierend

vorfahrtrans(X,Y) :- eltern(X,Y).

vorfahrtrans(X,Z) :- vorfahrtrans(X,Y),vorfahrtrans(Y,Z).

%%%%% einfach und terminierend

vorfahr(X,Y) :- eltern(X,Y).

vorfahr(X,Z) :- eltern(X,Y),vorfahr(Y,Z).

bruder(X,Y) :- mann(X),vater(Z,X),vater(Z,Y),

not(X == Y), mutter(M,X),mutter(M,Y).

schwester(X,Y) :- frau(X),vater(Z,X),vater(Z,Y),

not(X == Y),mutter(M,X),mutter(M,Y).

geschwister(X,Y) :- vater(Z,X),vater(Z,Y),

not(X == Y),mutter(M,X),mutter(M,Y).


Prolog: Graph-Beispiel

ungerichteter Graph.

a b

c d

e f

g

kante(a,b).

kante(a,c).

kante(c,d).

kante(d,b).

kante(b,e).

kante(f,g).


Prolog: Graph-Beispiel

verbunden(X,Y) :- kante(X,Y).

verbunden(X,Y) :- kante(Y,X).

verbunden(X,Z) :- kante(X,Y),verbunden(Y,Z).

verbunden(X,Z) :- kante(Y,X),verbunden(Y,Z).

%%% verbunden2 terminiert

verbunden2(X,Y) :- verb(X,Y,[]).

ungkante(X,Y) :- kante(X,Y).

ungkante(X,Y) :- kante(Y,X).

verb(X,Y,_) :- ungkante(X,Y).

verb(X,Z,L) :- ungkante(X,Y), not(member(Y,L)), verb(Y,Z,[Y|L]).

member(X,[X|_]).

member(X,[_|L]) :- member(X,L).


Prolog: Listen und Mengen

member(X,[X|_]).

member(X,[_|Y]) :- member(X,Y).

append([],X,X).

append([X|R],Y,[X|Z]) :- append(R,Y,Z).

listtoset([],[]).

listtoset([X|R],[X|S]) :- remove(X,R,S1),listtoset(S1,S).

remove(E,[],[]).

remove(E,[E|R],S):- remove(E,R,S).

remove(E,[X|R],[X|S]):- not(E == X), remove(E,R,S).


Prolog: Listen und Mengen

union(X,Y,Z) :- append(X,Y,XY), listtoset(XY,Z).

intersect([],X,[]).

intersect([X|R],S,[X|T]) :- member(X,S),intersect(R,S,T1),

listtoset(T1,T).

intersect([X|R],S,T) :- not(member(X,S)),intersect(R,S,T1),

listtoset(T1,T).

reverse([],[]).

reverse([X|R],Y) :- reverse(R,RR), append(RR,[X],Y).

reversea(X,Y) :- reverseah(X,[],Y).

reverseah([X|Xs],Acc,Y):- reverseah(Xs,[X|Acc],Y).

reverseah([],Y,Y).


Grundlagen der logischen Programmierung:

deklarative Programmierung

Theoretische Basis von Prolog: Pradikatenlogik erster Stufe

Ausfuhrung der Programme: Spezialisierung der Resolution.

logischen Programmie sind spezielle Klauseln:

Horn-Klauseln


Grundlagen der logischen Programmierung

• Eine Hornklausel ist eine Klausel mit maximal einem positiven Li-

teral

• Eine definite Klausel ist eine Klausel mit genau einem positiven

Literal.

D.h. A ∨ ¬B1 ∨ . . . ∨ ¬Bm

oder in Notation der logischen Programmierung:

A ⇐ B1, . . . , Bm bzw. A :- B1, . . . , Bm

Man nennt A den Kopf, {B1, . . . , Bm} den Rumpf der Klausel.



• Eine Klausel ohne positive Literale nennt man definites Ziel (An-

frage,Query,goal). Notation:

⇐ B1, . . . , Bn

Die Bi werden Unterziele (Subgoals) genannt.

• Eine Unit-Klausel (oder Fakt) ist eine definite Klausel mit leerem

Rumpf. Notation: A ⇐.



• Ein definites Programm ist eine Menge von definiten Klauseln.

• Die Menge aller Klauseln, deren Kopfliteral das Pradikat Q hat,

nennen wir Definition von Q.


Beispiele und Negationen

Folgende Literale der Beispiele passen nicht zur Definition

eines definiten Programms:

not(X == Y)

not(member(Y,L))

not(E == X)

not(member(X,S))

(wird noch besprochen)


Modell-Eigenschaft der Definiten Programme

Es gilt:

Zu jedem definiten Programm P

gibt es ein eindeutiges kleinstes Modell MP .

• MP besteht aus allen mit Resolution undInstanziierung herleitbaren Grund-Fakten.

• MP entspricht allen Atomen, die das Programm mit”JA“ beantwortet.


Anfragen an Prolog-Programme

Das definite Ziel

∀x1, . . . , xn : ¬B1 ∨ . . . ∨ ¬Bn

ist aquivalent zu:

¬∃x1, . . . , xn : B1 ∧ . . . ∧Bn

Die Anfrage ist:

∃x1, . . . , xn : B1 ∧ . . . ∧Bn


Anfragen an Prolog-Programme

Es gilt: fur die Resolution auf Hornklausel-Mengen:

im Falle der Herleitung der leeren Klausel

werden die existierenden Objekte ausgerechnet

D.h. Resolution berechnet Substitutionen,

die Antworten auf die Anfrage sind.


Anfragen an Prolog-Programme: Beispiel

Fur nicht-Hornklauselnmengen berechnet Resolution nicht immer eine

(eindeutige) Antwort:

Formel: Q(a) ∨Q(b).

Anfrage: ∃x.Q(x).

Die Klauselmenge dazu ist : {{Q(a) ∨Q(b)}, {¬Q(x)}}

Resolution ergibt die leere Klausel.

{x 7→ a}, {x 7→ b} werden beide verwendet!

Q(a) ∨Q(b) hat kein eindeutiges kleinstes Modell!


SLD-Resolution

SLD-Resolution

ist eine spezielle Resolutionsstrategie

ist die prozedurale Semantik von definiten Programmen.

definiert die Ausfuhrung von logischen Programmen:

S: Selektions-Funktion

L: Lineare Resolution

D: Definite Klauseln


SLD-Resolution

Definition

G = ⇐ A1, . . . , Am, . . . , Ak sei definites Ziel

C = A ⇐ B1, . . . , Bq eine definite Klausel.

Resolutions-Herleitung eines neuen definiten Ziels G′:

• Am ist das selektierte Atom des definiten Ziels G.• θ ist ein allgemeinster Unifikator von Am und A, dem

Kopf von C.• G′ ist das neue Ziel:

θ(A1, . . . , Am−1, B1, . . . , Bq, Am+1, . . . , Ak).

G′ ist eine Resolvente von G und C.

Ableitungsrelation G →P,C,m G′


SLD-Resolution und SLD-Ableitung

Definition

Sei P ein definites Programm und G ein definites Ziel.

Eine SLD-Ableitung von P ∪ {G} ist eine Folge G →C1,m1G1 →C2,m2

G2 . . . von SLD-Schritten

wobei Ci jeweils eine umbenannte Klausel aus P ist

Die SLD-Ableitung ist eine SLD-Widerlegung,

wenn sie mit einer leeren Klausel endet.

Ci nennt man auch die Eingabe-Klauseln.


SLD-Resolution und SLD-Ableitung

erfolgreiche SLD-Ableitung: Wenn es eine SLD-Widerlegung ist.

fehlgeschlagene SLD-Ableitung: Wenn diese nicht fortsetzbar ist.

unendliche SLD-Ableitung


SLD-Ableitung


• Eine korrekte Antwort ist eine Substitution θ,so dass P |= θ(¬G) gilt.

• Eine berechnete Antwort θ fur P ∪ {G}ist eine Substitution:Einschrankung von θn ◦ . . . ◦ θ1 auf die Variablen von G,wobei θ1 . . . θn die allgemeinsten Unifikatoren (in dieser Reihenfolge)zu einer SLD-Widerlegung von G sind.


SLD-Ableitung: Korrektheit

Es gilt:

Korrektheit (Soundness) der SLD-Resolution


Dann ist jede berechnete Antwort θ auch korrekt.

D.h. P |= θ(¬G)


Vollstandigkeit der SLD-Resolution

Wir betrachten verschiedene Vollstandigkeitsaussagen fur die SLD-

Resolution.

Satz (Widerlegungsvollstandigkeit)


Wenn P ∪ {G} unerfullbar ist,

dann gibt es eine SLD-Widerlegung von P ∪ {G}.


Vollstandigkeit der SLD-Resolution

Es gilt ein starkerer Satz uber die Vollstandigkeit der berechneten Ant-

worten:

zu jeder Antwortsubstitution

gibt es eine allgemeinere berechnete Antwort

Satz (Vollstandigkeit der SLD-Resolution)


Zu jeder korrekten Antwort θ

gibt es eine berechnete Antwort σ fur P ∪ {G}und eine Substitution γ

so dass ∀x ∈ FV (G): γσ(x) = θ(x).


Strategien zur Berechnung der Antworten

Breitensuche:

1. Gegeben Programm P und ein Ziel ⇐ A1, . . . , An:

(a) Probiere alle Moglichkeiten aus, ein Unterziel A aus A1, . . . , An

auszuwahlen

(b) Probiere alle Moglichkeiten aus, eine Resolution von A mit einemKopf einer Programmklausel durchzufuhren.

2. Erzeuge neues Ziel B: Loschen von A, Instanziieren des restlichenZiels, Hinzufugen des Rumpfs der Klausel.

3. Wenn B = 2, dann gebe die Antwort aus.

Sonst: mache weiter mit 1. mit dem Ziel B.


Strategien zur Berechnung der Antworten

Breitensuche hat zwei Verzweigungspunkte pro Resolutionsschritt:

• Die Auswahl eines Atoms aus der Anfrage

• Die Auswahl einer Klausel zum Resolvieren

Es gilt: die Auswahl des Atoms ist don’t care

Die Suche bleibt vollstandig, wenn man die Alternativen weglasst.

Z.B. leicht zu losende Atome kann man zuerst auswahlen

Umstellung kann aber unendlich tiefe Suchpfade einfuhren


Strategien

Eine vollstandige Suchstrategie:

• Breitensuche uber die Resolutionsmoglichkeiten• Anfrage als Stack von Atomen• Reihenfolge der Atome wie in definiten Klauseln


Strategien in Prolog-Implementierung

Tiefensuche, d.h. noch deterministischer:

• Anfrage als Stack

• Die Programmklauseln werden in der Reihenfolge abgesucht, in der

sie im Programm stehen.

Prolog benutzt die Tiefensuche

Rechts-Links-Ordnung ist definiert durch die

Reihenfolge der Klauseln im Programm und

die Reihenfolge der Literale in den Rumpfen


Prolog-Implementierung

Weitere Veranderungen gegenuber der theoretischen Fundierung sind:

• Der occurs-check wird i.a. nicht durchgefuhrt.• CUT- Operatoren zum Beeinflussen des Backtracking

zB nur erste Sub-Antwort statt aller Losungen• Assert/Retract: Damit konnen Programmklauseln zum Pro-

gramm hinzugefugt bzw. geloscht werden. I.a, betrifft dies

nur Fakten.• Negation: Negation wird definiert als Fehlschlagen der Su-

che.• Typinformation zu Programmen hinzugefugt.• moded Argumente von Pradikaten haben Markierung I bzw.

O : Input, Output• Pradikat als Funktionen, wenn deterministisch.


Prolog-Implementierung

Vergleich der theoretischen Eigenschaften mit der Implementierung.

Pures Prolog nichtpures Prolog nichtpur,Definite Programme Cut, Negation, ohne occurs-check

Klauselreihenfolge festSLD: korrekt SLD: korrekt SLD: i.a. nicht korrektvollstandig unvollstandig unvollstandig


Implementierung: Beispiele fur Unvollstandigkeit

bei festgelegten Reihenfolge der Klauseln:

P(a,b).

P(c,b).

P(X,Y) :- P(Y,X).

P(X,Z) :- P(X,Y), P(Y,Z).

Die symmetrisch-transitive Hulle kann nicht berechnet werden,

da das Programm in eine Schleifen gerat.

Aber eine SLD-Widerlegung existiert, da diese nicht-deterministisch

vorgehen darf, und insbesondere sich eine Programmklausel aussuchen

darf.


Beispielprogramme und Prolog-Ausfuhrung

likes (maria, essen).

likes(maria,wein).

likes(peter, maria).

likes(peter,wein).

Einfache Anfragen:

> ?- likes(peter,maria)

yes

Konjunktive Anfragen (mit logischem und verknupfte)

> ?- likes(peter,maria), likes(maria,peter)

no


Zuerst wird das erste Unterziel bearbeitet: Antwort:. ja, Dann zweite:

nein.

Konjunktive Anfragen mit Instanziierung.

> ?- likes(peter, X), likes(maria,X)

Abarbeitung: 1. X = maria, likes(maria,maria): no2. X = wein: likes(maria,wein). yes

X = wein

Backtracking ist notwendig (Zurucksetzen) zum Finden weiterer

Losungen.

Beispielprogramm und Prolog-Ausfuhrung

vater(peter,maria).

mutter(susanne,maria).

vater(karl, peter).

mutter(elisabeth, peter).

...

vorfahr(X,Y) :- vater(X,Y).

vorfahr(X,Y) :- mutter(X,Y).

vorfahr(X,Z) :- vorfahr(X,Y),vorfahr(Y,Z).


Prolog-Abarbeitung:

Anfragen:

?- vorfahr(elisabeth,maria)

Abarbeitung :

1. vorfahr(elisabeth,maria)

1.1 vater(elisabeth,maria). nein

1.2 mutter(elisabeth,maria): nein

1.3 vorfahr(elisabeth, X0), vorfahr(X0,maria)

1.3.1 vater(elisabeth, X0), vorfahr(X0,maria): nein

1.3.2 mutter(elisabeth, X0), vorfahr(X0,maria): X0 = peter

1.3.2 vorfahr(peter,maria):

1.3.2.1 vater(peter,maria): ja

usw.


Syntaxkonventionen von Prolog

Namen Aus Großbuchstaben, Kleinbuchstaben, Ziffern und

(Unterstrich) oder nur aus Sonderzeichen

Konstanten: erstes Zeichen ist KleinbuchstabeVariablen: erstes Zeichen ist Großbuchstabe oder

oder nur: (wildcard, joker, Leerstelle)

Terme Funktor(component1,. . . ,componentn)Stelligkeit von Pradikaten/ Funktionen ist nicht variabel.gleicher Funktorname mit verschiedener Stelligkeit ergibt

anderen Funktorz.B. Schreibweise: vater/2


arithmetische Ausdrucke:

Die Operatoren +,−, ∗, /und die Vergleichsoperatoren <=, ... sind erlaubt.

Infix usw. ist teilweise moglich:

z.B. a ∗ b + c steht fur den Term +(∗(a, b), c).

Zahlen sind abhangig von der Implementierung.


Gleichheit

Spezialpradikat = (Gleichheit) kann definiert werden durch

X = X.

Z.B.

?- besitzt(peter, X) = besitzt(peter,buch(lloyd,prolog))

yes; X = buch(lloyd,prolog)

Gleichheitsabarbeitung benutzt Unifikation


Arithmetische Vergleiche

erlaubte Operatoren:

=, \=, <, >, =<, >= , =\=, =:=

Beachte: die Operanden mussen als Zahl ausgewertet seinvor Auswertung des Ausdrucks.

3 + 4 = 7 ergibt: no3 + 4 =:= 7 ergibt yes

D.h., es gibt einen Unterschied zwischen Term und Wert.


Zuweisung und Auswertung

Zuweisung mit gleichzeitiger Auswertung kann man mit is durchfuhren:

X is 3 + 5 danach: X 7→ 8X = 3 + 5 danach X 7→ “3 + 5“


Datenstrukturen und Unifikation in Prolog

Term-Gleichungen werden durch Instanziierung der Variablen gelost:

d.h. durch Unifikation

k(X, a) = k(b, Y ) ergibt X = b, Y = a

Auch Unterstrukturen konnen Wert von Variablen sein:

k(X, h(a, Z)) = k(b, Y ) ergibt X = b, Y = h(a, Z)


Datenstrukturen und Unifikation in Prolog:

Beispiel

k(X, h(a, Z), X) = k(h(Y, b), U, U)

ergibt zunachst:

X = h(Y, b), U = h(a, Z), X = U

Endergebnis:

X = h(a, b), U = h(a, b), Y = a, Z = b


Beispiel Unifikation

Dieses Ergebnis kann man z.B. im Prolog Interpreter direkt verifizieren.

k(X,h(a,Z),X) = k(h(Y,b),U,U).

X = h(a,b)

Z = b

Y = a

U = h(a,b)

yes


Behandlung des occurs-check

k(X, X) = k(Y, h(Y ))

erfordert Unifikation von X = h(X).

Es gibt eine Losung in unendlichen Baume: X = h(h(h(. . .))).

• Prolog-Implementierungen vermeiden den occurs-check.• Oft abgeschaltet: ist nicht korrekt bzgl. PL1-Semantik• Teilweise Elimination durch statische Analyse eliminiert.


Listen in Prolog

Prolog benutzt eine abkurzende Syntax:

[1,2,3] entspricht cons(1,cons(2,cons(3,nil)))

[] entspricht nil


Listen in Prolog: member

Element-Test mittels member

member(X,[X|_]).

member(X,[_|Y]) :- member(X,Y).

Terminiert member in allen moglichen Situationen?

• member(s,t): wenn t keine Variablen enthalt. dann wird t′ beim

nachsten mal kleiner.


member. Terminierung?

• member(Y,Y): Die erste Klausel unifiziert nicht

(aber unifiziert, wenn occurs-check aus ist: Antwort: ja)

Die zweite Klausel ergibt:

member(X_1,[_|Y_1]) :- member(X_1,Y_1).

X_1 = Y = [_|Y_1]

Die neue Anfrage ist: member([_|Y_1] ,Y_1)

Nachste Unifikation ebenfalls mit zweiter Klausel

member(X_2,[_|Y_2]) :- member(X_2,Y_2)

X_2 = [_|Y_1] , Y_1 = [_|Y_2]

usw. Man sieht: das terminiert nicht.


Listen in Prolog: islist

islist([_|X]) :- islist(X).

islist([]).

Diese Funktion terminiert ebenfalls fur Listen ohne Variablen

aber nicht fur islist(X).

Eine Umstellung der Klauseln ergibt:

islist([]).

islist([_|X]) :- islist(X).

Dieses Programm terminiert fur die Anfrage islist(X).

Antwort: X = [], falls die Eingabe eine Liste ist. Antwort ist dann ja.


Listen in Prolog: length

laenge([],0).

laenge([_|X],N) :- laenge(X,N_1), N is N_1 + 1.

Damit kann man folgende Beispiele rechnen:

?- laenge([1,2,3], N).

N = 3.

?- laenge(X,2).

Antwort X = [ 1, 2]. Aber: terminiert in manchen Implementierungen

nicht


Sortiere Listen von Zahlen:

sortiert([]).

sortiert([X]).

sortiert([X|[Y|Z]]) :- X <= Y, sortiert([Y|Z]).

sortiert_einfuegen(X,[],[X]).

sortiert_einfuegen(X,[Y|Z], [X|[Y|Z]]) :- X =< Y.

sortiert_einfuegen (X,[Y|Z], [Y|U]) :- Y < X, sortiert_einfuegen(X,Z,U).

ins_sortiere(X,X) :- sortiert(X).

ins_sortiere([X|Y], Z) :- ins_sortiere(Y,U), sortiert_einfuegen(X,U,Z).


Programmierung von append: in Prolog:

append([],X,X).

append([X|Y],U,[X|Z]) :- append(Y,U,Z).


Documents

Logische Programmierung Einf¨uhrende Beispiele · • Eine Unit-Klausel (oder Fakt) ist eine deﬁnite Klausel mit leerem Rumpf. Notation: A ⇐. KI, SS 06, Fol7, Seite 10, 8. Juni2006