07.02.00GK Prolog: Prolog und Prädikatenlogik I 1 Prolog und Prädikatenlogik I Prolog Grundkurs WS 99/00 Christof Rumpf [email protected]

07.02.00 GK Prolog: Prolog und Prädikatenlogik I

1

Prolog und Prädikatenlogik IProlog und Prädikatenlogik I

Prolog Grundkurs WS 99/00

Christof Rumpf

[email protected]


2

LogikprogrammierungLogikprogrammierung

Prolog wurde um 1970 von Alain Colmerauer und seinen Mitarbeitern in Marseille mit dem Ziel entwickelt, die Programmierung von Computern mit den Mitteln „der Logik“ zu ermöglichen.


3

Pure PrologPure Prolog

Das sogenannte Pure PrologPure Prolog oder Database-Database-PrologProlog entspricht einer Teilmenge der Sprachdefinition eines praktischen Prolog-Entwicklungssystems und enthält keine extra- oder metalogischen Komponenten wie:– Cut, Type-Checking– Arithmetische Operationen– Datenbasismanipulation zur Laufzeit


4

Prolog und LogikProlog und Logik

Pure Prolog-Programme entsprechen den Ausdrücken der Hornklausellogik, die eine Teilmenge der Prädikatenlogik 1. Stufe ist.

Das Beweisverfahren Resolution ermöglicht Inferenzen aufgrund von Prolog-Programmen oder Hornklauseln.


5

Prädikatenlogik Prädikatenlogik Prolog Prolog

Prädikatenlogik 1. Stufe

Hornklauseln

Prolog

KNF


6

Prädikatenlogik 1. StufePrädikatenlogik 1. Stufe

Inventar der Syntax:

– Individuenkonstanten a, b, c, ...– Individuenvariablen x, y, z, ...

– Prädikate P(Arg1,...,Argn), Argi TERM

– Quantoren , – Junktoren , , , ,

Terme


7

Formeln der PLFormeln der PL11

– Wenn P ein n-stelliges PrädikatPrädikat ist und t1,...,tn

TermeTerme sind, dann ist P(t1,...,tn) ein LiteralLiteral.

– LiteraleLiterale sind FormelnFormeln.

– Wenn und FormelnFormeln sind, dann sind auch ,

, , , FormelnFormeln.

– Wenn eine FormelFormel ist und x eine IndividuenIndividuen-

variablevariable, dann sind auch (x) , (x) FormelnFormeln.


8

KlauselnKlauseln

– Wenn P ein n-stelliges PrädikatPrädikat ist und t1,...,tn

TermeTerme sind, dann ist P(t1,...,tn) ein LiteralLiteral.

– LiteraleLiterale sind KlauselnKlauseln.

– Wenn ein LiteralLiteral ist, dann ist auch eine

KlauselKlausel.

– Wenn und KlauselnKlauseln sind, dann ist auch

eine KlauselKlausel.


9

HornklauselnHornklauseln

Hornklauseln sind Klauseln, die genau ein nicht-negiertes Literal und beliebig viele negierte Literale enthalten.

Vater(x,y) Elternteil(x,y) Männlich(x) Sterblich(sokrates)


10

Konjunktive NormalformKonjunktive Normalform

Eine FormelFormel ist in konjunktiverkonjunktiver Normal-formNormal-form, wenn sie eine KonjunktionKonjunktion von KlauselnKlauseln repräsentiert.

K1 ... Kn, Ki KLAUSEL

Formeln der Prädikatenlogik können durch Anwendung logischer ÄquivalenzregelnÄquivalenzregeln in die konjunktive Normalform gebracht werden.


11

Logische ÄquivalenzregelnLogische Äquivalenzregeln

– Kommutativgesetz– Assoziativgesetz– Distributivgesetz– Konditional- und Bikonditionalgesetz– De Morgan– Komplementarität– Idempotenz– Identität


12

KommutativitätKommutativität

P Q Q P P Q Q P


13

AssoziativitätAssoziativität

(P Q) R P (Q R)

(P Q) R P (Q R)


14

DistributivitätDistributivität

P (Q R) (P Q) (P R)

P (Q R) (P Q) (P R)


15

Konditional- & BikonditionalgesetzKonditional- & Bikonditionalgesetz

P Q P Q

P Q (P Q) (Q P)


16

De MorganDe Morgan

(P Q) P Q (P Q) P Q


17

KomplementaritätKomplementarität

P P 1 (Tautologie, allgemeingültig)

P P 0 (Kontradiktion, Inkonsistenz)

P P (Doppelte Negation)


18

Idempotenz, IdentitätIdempotenz, Identität

P P P

P P P

P 0 P

P 1 1

P 0 0

P 1 P


19

QuantorengesetzeQuantorengesetze

– Negation

– Distribution

– Dependenz

– Bewegung

– Prenex Normalform


20

Quantoren-NegationQuantoren-Negation

x x x x x x x x


21

Quantoren-DistributionQuantoren-Distribution

x ( ) x x x ( ) x x x x x ( ) x ( ) x x


22

Quantoren-DependenzQuantoren-Dependenz

x y y x x y y x x y y x


23

Quantoren-BewegungQuantoren-Bewegung

x x ( ) x x ( )

(x ) x ( )

(x ) x ( )Hier wird vorausgesetzt, daß die quantifizierte Variable nicht frei in der Formel vorkommt, die jeweils außerhalb des Quantorenskopus erscheint.


24

Prenex-NormalformPrenex-Normalform

Eine PL1-Formel befindet sich in Prenex-Normalform, wenn alle Quantoren am Anfang der Formel stehen.

(x F(x)) (y G(y)) Quantorenbewegung, 1.+ 4. Gesetz

y x (F(x) G(y))


25

SkolemisierungSkolemisierung

Existenzquantoren können eleminiert werden, indem existenzquantifizierte Variablen durch Skolemkonstanten substituiert werden.

Liegt ein Existenzquantor im Skopus von Allquantoren, werden die Skolemkonstanten mit den jeweiligen allquantifizierten Variablen durch Parametrisierung in Abhängigkeit gebracht.


26

Skolemisierung: BeispieleSkolemisierung: Beispiele

y x ((man(x) (woman(y)) loves(x,y))

x ((man(x) woman(G)) loves(x,G))

x (man(x) y (woman(y) loves(x,y)))

x (man(x) (woman(G(x)) loves(x,G(x))))


27

AusblickAusblick

Nächste Woche werden wir ein Prolog-Programm behandeln, das PL1-Formeln in Prolog-Programme übersetzt.

Documents

07.02.00GK Prolog: Prolog und Prädikatenlogik I 1 Prolog und Prädikatenlogik I Prolog Grundkurs WS 99/00 Christof Rumpf [email protected]