Inferenz in Prädikatenlogik. KI 9-Inferenz in PL2 Überblick Reduktion prädikatenlogischer (PL) Inferenz auf aussagenlogische (AL) Inferenz Generalisierter

Inferenz in Prädikatenlogik

KI 9-Inferenz in PL 2

Überblick

• Reduktion prädikatenlogischer (PL) Inferenz auf aussagenlogische (AL) Inferenz

• Generalisierter Modus Ponens• Unifikation• Vorwärtsverkettung• Rückwärtsverkettung• Resolution


Universelle Instantiierung (UI)

• Aus einem universell quantifizierten Satz folgen alle seine Instantiierungen:

v αSubst({v/g}, α)

für jede Variable v und jeden Grundterm g (Grundterm = Term ohne Variablen).

• Z.B. Aus x König(x) Gierig(x) Böse(x) folgt:König(John) Gierig(John) Böse(John)König(Richard) Gierig(Richard) Böse(Richard)König(Vater(John)) Gierig(Vater(John)) Böse(Vater(John))…

•

•


Existentielle Instantiierung (EI)

• Für jeden Satz α, jede Variable v, und jedes Konstantensymbol k, das nicht an anderer Stelle in der WB auftritt, gilt:

v αSubst({v/k}, α)

v α heißt, dass es ein v gibt, das α erfüllt. Diesem v kann man einen Namen geben, der noch nicht in der WB vorkommt.

• Z.B. x Krone(x) AufKopf(x,John) ergibt:

Krone(C1) AufKopf(C1,John)

wobei C1 eine neues Konstantensymbol ist, genannt Skolem-Konstante.

•

•


Existentielle Instantiierung (EI)

• Beachte: UI wird mehrmals angewendet, EI nur einmal.

• Danach wird existentiell quantifizierter Satz aus WB entfernt.

• Bsp.: – WB enthält: x Ehefrau(x, Paul)

– Füge EI zu WB hinzu: Ehefrau(Anne, Paul).

– Entferne Satz x Ehefrau(x, Paul) aus WB.

• Neue WB ist nicht logisch äquivalent zur alten, denn diese hätte z.B. Ehefrau(Petra, Paul) zugelassen (vorausgesetzt Petra kommt nicht in WB vor).

• Neue WB ist aber inferentiell äquivalent zu alter WB.

6

Reduktion auf aussagenlogische Inferenz

• Idee: Wir sparen uns Inferenzmechanismen für PL, reduzieren einfach auf AL und verwenden die bekannten!

• Bsp.: WB enthält nur die folgenden Sätze: x König(x) Gierig(x) Böse(x)König(John)Gierig(John)Bruder(Richard,John)

• Instantiiere (UI) ersten Satz mit allen möglichen Substitutionen, erhalte neue WB:König(John) Gierig(John) Böse(John)König(Richard) Gierig(Richard) Böse(Richard)König(John)Gierig(John)Bruder(Richard,John)

• Betrachte atomare Sätze Gierig(John) etc. als Aussagensymbole.

• Neue WB ist damit rein aussagenlogisch.

•


Reduktion

• Jede PL-WB kann so in eine aussagenlogische WB umgewandelt werden, dass die logische Konsequenz erhalten bleibt.

• Problem: Für Funktionssymbole gibt es unendlich viele Grundterme,

z.B. Vater(Vater(Vater(John)))

•

•

8

ReduktionTheorem (Herbrand, 1930): Wenn ein Satz α Konsequenz einer PL-WB ist, ist er Konsequenz einer

endlichen Untermenge der aussagenlogischen WB.

Idee: For n = 0 to ∞ do Erzeuge aussagenlogische WB durch Instantiierung mit Termen der Tiefe n. Prüfe ob α Konsequenz dieser WB ist.

Problem: Klappt, falls α aus WB folgt; Schleife falls α nicht folgt !

Theorem (Turing,1936; Church, 1936):Konsequenz ist für PL semientscheidbar:• Es gibt Algorithmen, die jeden aus der WB beweisbaren Satz

beweisen.• Aber es gibt keine Algorithmen, die beweisen, dass ein Satz nicht

Konsequenz der WB ist.• Bekannt als Halteproblem der Turing-Maschine!


Probleme der Umwandlung in AL

• Umwandlung von PL nach AL generiert viele irrelevante Sätze.

• Bsp. x König(x) Gierig(x) Böse(x) König(John) y Gierig(y) Bruder(Richard,John)

Es ist offensichtlich Böse(John), aber Umwandlung in AL produziert zahlreiche irrelevante Fakten wie Gierig(Richard).

• Mit p k-stelligen Prädikaten und n Konstanten, gibt es p·nk Instantiierungen.

• Suche „Lifting“ der AL-Inferenzregeln zur PL-Tauglichkeit.

•


• WB: x König(x) Gierig(x) Böse(x)König(John)Gierig(Richard)Gierig(John)

• Folgere Böse(John):– Idee: Suche x, so dass König(x) und Gierig(x), folgere Böse(John).– Formal: Suche Substitution θ: {x / John}.

• Andere WB: x König(x) Gierig(x) Böse(x)König(John) y Gierig(y)

• Folgere Böse(John): Suche Substitution für zwei Variable: {x / John, y / John}.

Unifikation


Unifikation

• Böse(John) kann direkt inferiert werden, wenn wir eine Substitution θ finden, so dass König(x) und Gierig(x) zu König(John) und Gierig(y) passen.

θ = {x/John, y/John} funktioniert.

• Ersetzungsprozess heißt Unifikation.

• Suche Unifikationsalgorithmus: Unify(p,q) = θ wenn pθ = qθ.

Beispiele:p q θ Kennt(John,x) Kennt(John,Jane) {x / Jane}Kennt(John,x) Kennt(y,Richard) {x / Richard, y / John}Kennt(John,x) Kennt(y,Mutter(y)) {y / John, x / Mutter(John)}Kennt(John,x) Kennt(x,Richard) { }

–


Unifikation

Problem:p q θ Kennt(John,x) Kennt(x,Richard) { }

• Offenbar entsteht das Problem durch ungünstige Variablen-Benennung.

• Standardisierung eliminiert Konflikt der Variablen, z.B. Kennt(z,Richard).

•


Allgemeinster Unifikator

• Kennt(John,x) und Kennt(y,z) kann auf verschiedene Arten substituiert werden:– θ = {y/John, x/z },

Ergebnis: Kennt(John,z), Kennt(John,z)– θ = {x/John, y/John, z/John},

Ergebnis: Kennt(John,John), Kennt(John,John)

• Der erste Unifikator ist allgemeiner als der zweite.

• Es gibt für jedes Paar von Ausdrücken nur einen allgemeinsten Unifikator (MGU, most general unifier) der eindeutig ist (bis auf Umbenennung von Variablen).MGU = { y/John, x/z }

–••

–


Unifikationsalgorithmus

• Unify(x,y,θ)• Vergleicht x und y stückweise• Parallel wird Unifikator θ aufgebaut• Problem: Vergleich einer Variablen var mit

komplexem Term x• Occur-Check löst Problem durch Test, ob var in

x vorkommt. Wenn ja, failure.






Generalisierter Modus Ponens (GMP)

Modus Ponens der AL:

p1 , p2 , … , pn , ( p1 p2 … pn q) q



Allgemein:

p1', p2', … , pn', ( p1 p2 … pn q) qθ wobei pi'θ = piθ für alle i



Allgemein:

p1', p2', … , pn', ( p1 p2 … pn q) qθ

p1' ist König(John) p1 ist König(x) p2' ist Gierig(y) p2 ist Gierig(x) θ ist {x/John,y/John} q ist Böse(x) q θ ist Böse(John)

• GMP wird verwendet für WB mit definiten Klauseln (genau ein positives Literal).

• Es wird angenommen, dass alle Variablen universell quantifiziert sind.

•

wobei pi'θ = piθ für alle i


Definite Klauseln erster Stufe

• Disjunktion von Literalen, wobei genau eins positiv ist, bzw.

• Implikation der Form

(Konjunktion positiver Literale) positives Literal

• Unterschied zu AL: Literale dürfen Variable enthalten,

• diese sind implizit universell quantifiziert.


Beispiel

• WB:– Gesetz: Jeder Amerikaner, der Waffen an feindliche Nationen

verkauft, ist ein Verbrecher. – Das Land Nono gehört zu den Feinden Amerikas, …– … und hat Raketen.– Alle Raketen des Landes Nono wurden von Colonel West

verkauft, ...– … der Amerikaner ist.

• Beweise, dass Col. West ein Verbrecher ist!•

–


Beispiel

Jeder Amerikaner, der Waffen an feindliche Nationen verkauft, ist ein Verbrecher:Amerikaner(x) Waffe(y) Verkauft(x,y,z) Feindlich(z)

Verbrecher(x)Das Land Nono gehört zu den Feinden Amerikas …

Feind(Nono,Amerika)… und hat Raketen:

x Hat(Nono,x) Rakete(x): Hat(Nono,R1) Rakete(R1)Alle Raketen des Landes Nono wurden von Colonel West verkauft, ...

Rakete(x) Hat(Nono,x) Verkauft(West,x,Nono)… der Amerikaner ist.

Amerikaner(West)

••


Beispiel






Amerikaner(West)

Was fehlt ??

••


Beispiel






Amerikaner(West)Ein Feind von Amerika ist feindlich:

Feind(x,Amerika) Feindlich(x)Raketen sind Waffen:

Rakete(x) Waffe(x)

•••


• Gegeben: WB in Form definiter Klauseln

• Idee: Verwende Vorwärtsverkettung, um nacheinander passende Ersetzung(en) zu finden, so dass aus bekannten Fakten neue abgeleitet werden können.

• Prinzip:1. Sammle alle bekannten Fakten.2. Alle Regeln ausführen, deren Prämissen erfüllt sind.3. Schlüsse den bekannten Fakten hinzufügen.4. Falls zu beweisender Satz dabei: Erfolg, Ende.5. Falls keine neuen Fakten: Failure, Ende.6. Goto 2.

Vorwärtsverkettung: Algorithmus


Vorwärtsverkettung: Algorithmus


WB des Beispiels

• Amerikaner(x) Waffe(y) Verkauft(x,y,z) Feindlich(z)

Verbrecher(x)

• Feind(Nono,Amerika)

• Hat(Nono,R1) Rakete(R1)

• Rakete(x) Hat(Nono,x) Verkauft(West,x,Nono)

• Amerikaner(West)

• Feind(x,Amerika) Feindlich(x)

• Rakete(x) Waffe(x)


WB des Beispiels


Verbrecher(x)








Vorwärtsverkettung Beispiel


WB des Beispiels


Verbrecher(x)












WB des Beispiels


Verbrecher(x)










Eigenschaften der Vorwärtsverkettung

• Korrekt und vollständig für definite Klauseln 1. Stufe.

• Datalog– Datenbank-Programmiersprache– Definite Klauseln 1. Stufe, aber keine Funktionen– Keine Anwendungen

• Vorwärtsverkettung terminiert für Datalog nach endlicher Zahl von Iterationen.

• Terminiert u.U. nicht, falls α keine Konsequenz ist, denn

• Konsequenz ist für definite Klauseln nur halbentscheidbar.

•


Effiziente Vorwärtsverkettung: Beschränkung der Regelkomplexität

• Problem: Reihenfolge bei Auswertung von Konjunkten• Bsp.: Rakete(x) Hat(Nono,x) Verkauft(West,x,Nono)

– Teste für alle Raketen, ob Nono sie besitzt; oder:

– Teste für alle Objekte, die Nono sie besitzt, ob sie Raketen sind.

Reihenfolge 1 besser, falls es weniger Raketen gibt, als Nono Objekte besitzt.

• Ermittlung optimaler Reihenfolge NP-hart.• Abhilfe:

– Heuristiken wie most constrained variable– Beschränkung der Länge der Regeln und Stelligkeit der

Prädikate.


Effiziente Vorwärtsverkettung: Inkrementelle Vorwärtsverkettung

• Problem: Regeln werden wiederholt verglichen.

• Idee: „Inkrementelle Vorwärtsverkettung“

• Bei Iteration k muss eine Regel nicht verglichen werden, wenn nicht eine ihrer Prämissen bei Iteration k-1 hinzugefügt wurde.


Rückwärtsverkettung: Algorithmus

SUBST(COMPOSE(θ1, θ2), p) = SUBST(θ2, SUBST(θ1, p))


Rückwärtsverkettung: Beispiel














Eigenschaften der Rückwärtsverkettung

• Tiefensuche zum Beweis eines Satzes: Speicherbedarf

linear in Beweisgröße

• Unvollständig, da u.U. Endlosschleifen:– Abhilfe: Vergleiche gegenwärtiges Ziel mit allen Zielen auf

Stack.

• Ineffizient, da Wiederholung der Teilziele (sowohl bei

Erfolg als auch failure)– Abhilfe: Caching früherer Resultate.

• Weit verbreitet für Logikprogrammierung.

–

–

•

•


Logikprogrammierung: Prolog

• Programming in Logic• Weit verbreitet in Europa und Japan

(Basis des 5th Generation Project)• Programm = Menge von Hornklauseln =

Kopf :- Literal1, … Literaln.

Verbrecher(X) :- Amerikaner(X), Waffe(Y), Verkauft(X,Y,Z), Feindlich(Z).

• Anfragen an die WB werden durch Tiefensuche und links-nach-rechts Rückwärtsverkettung beantwortet.

• Eingebaute Prädikate für Arithmetik etc., z.B. X is Y*Z+3• Eingebaute Prädikate mit Nebeneffekten (z.B. Eingabe- und

Ausgabe-Prädikate, assert/retract zur Veränderung der WB)• Closed-world assumption: Alles, was nicht als wahr deklariert ist

oder bewiesen werden kann, ist falsch (Gegensatz zu PL!).


Prolog

• Da Kontrolle durch Schleifen (for, while etc.) fehlt, werden Schleifen durch Rekursion auf Listen programmiert.

• Verkettung zweier Listen zu einer dritten:

append([],Y,Y).

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

• Anfrage: append(A,B,[1,2]) ?

• Antworten: A=[] B=[1,2]

A=[1] B=[2]

A=[1,2] B=[]

••


Resolution

• PL-Version:l1 ··· lk, m1 ··· mn

Subst(θ, l1 ··· li-1 li+1 ··· lk m1 ··· mj-1 mj+1 ··· mn)

wobei Unify(li, mj) = θ.

• Die zwei Klauseln müssen dabei standardisiert sein, d.h. keine gemeinsame Variable haben.

• Bsp.: Reich(x) Unglücklich(x) , Reich(Ken)Unglücklich(Ken)

mit θ = {x/Ken}

• Anwendung der Resolution analog AL: KNF(WB α)

•

•

•


Konversion nach KNF

Jeder, der alle Tiere liebt, wird von jemand geliebt:x [y Tier(y) Liebt(x,y)] [y Liebt(y,x)]

1. Eliminiere Bikonditionale und Implikationen:x [y Tier(y) Liebt(x,y)] [y Liebt(y,x)]

2. Schiebe nach innen (x p ≡ x p, x p ≡ x p):x [y (Tier(y) Liebt(x,y))] [y Liebt(y,x)] x [y Tier(y) Liebt(x,y)] [y Liebt(y,x)] x [y Tier(y) Liebt(x,y)] [y Liebt(y,x)]

3. Standardisiere Variable: Jeder Quantor muss andere Variable verwenden

x [y Tier(y) Liebt(x,y)] [z Liebt(z,x)]

–•

–


Konversion nach KNF

4. Skolemisierung: Jede existentiell quantifizierte Variable wird durch Skolem-Funktion der allquantifizierten Variablen ersetzt:

x [Tier(F(x)) Liebt(x,F(x))] Liebt(G(x),x)

Beachte: Ohne die Abhängigkeiten des (Tiers) F und der (Person) G von x würde der Satz heißen: „Alle (Personen) x lieben ein bestimmtes (Tier) F nicht oder werden von einer bestimmten (Person) G geliebt.“

5. Alle verbleibenden Variablen sind allquantifiziert, Allquantoren weglassen:[Tier(F(x)) Liebt(x,F(x))] Liebt(G(x),x)

6. Konjunktion zwischen Klauseln herstellen („Klammern ausmultiplizieren“) :

[Tier(F(x)) Liebt(G(x),x)] [Liebt(x,F(x)) Liebt(G(x),x)]

–


Resolutionsbeweis

• Analog AL

• Um zu zeigen, dass Satz Konsequenz aus WB ist, wird gezeigt, dass WB unerfüllbar ist.


Resolutionsbeweis: Beispiel

Documents

Inferenz in Prädikatenlogik. KI 9-Inferenz in PL2 Überblick Reduktion prädikatenlogischer (PL) Inferenz auf aussagenlogische (AL) Inferenz Generalisierter