View
123
Download
3
Category
Preview:
Citation preview
1
Semantik und Pragmatik
Übung 2ModelleFrank Schilder
2
Einführung
Die Aussagen- und Prädikatenlogik ist eine formale Beschreibungsprache zur Darstellung von semantischen Inhalten.
Natürlich-sprachliche Sätze können durch Formeln der Aussagenlogik bzw. Prädikatenlogik beschrieben werden. Peter kommt nicht zur Vorlesung. ÿkommen(Peter,Vorlesung) Alle Vorlesungen sind interessant. "x vorlesung(x) Æ interessant(x)
3
Struktur der Übung
Wie schreibt man ein PROLOG Programm, das Modelle erster Ordnung überprüft? Definition des Vokabulars Repräsentation der Modelle Darstellung der Formeln
Spezifikation der Formel-Evaluierung Erster Ansatz Probleme Lösung
4
Logik erster Ordnung
Warum Logik? Formale Beschreibung von Sachverhalten Entscheidungsverfahren: Wann ist eine Beschreibungen
in einer Situation wahr oder falsch!
Ziel: Entscheiden, ob bestimmte Beschreibungen in einer gegebenen Situation wahr oder falsch sind!¯ Vorgehen: Formeln erster Ordnung erstellen und einen
Evaluierungsprozeß entwickeln.
5
Fragen zur Aussagenlogik
Was ist Erfüllbarkeit?Wie kann der Formalismus in PROLOG programmiert
werden (Model Checker)? Was ist das Vokabular? Wie werden Modelle repräsentiert? Wie können Aussagen ausgewertet werden?
Erste Grundvoraussetzung: Wir benötigen ein Vokabular bestehend aus
n-stelligen Relationen und Konstanten (Namen): {(like,2),(cute,1),(bond,0)...}
6
Modelle
Ein Modell M = (D,F) besteht aus zwei Teilen: Eine Ansammlung an Entitäten, auf die sich das Modell
beziehen soll (die Domäne D). Eine Zuordnung, die uns genau sagt, wie die Symbole
des Vokabulars zu interpretieren sind (die Interpretationsfunktion F ).
Sei D = {d1,d2,d3,d4}Dann kann F wie folgt aussehen:
F(bond) = d1,F(loren)=d2, F(pavarotti)=d3, F(likes)={(d1,d2),(d2,d3)}
7
Logik erster Ordnung
Eine Sprache erster Ordnung ist definiert durch: Alle Symbole des Vokabulars (die nicht-logischen
Symbole) Eine abzählbare Menge an Variablen x, y, z...
Die Boolschen Konnektoren ¬ (Negation), & (Und), (Oder) und (Implikation).
Die Quantoren (All-) und (Existenzquantor) Die Klammern ) und ( und das Komma.
8
Wohlgeformte Formeln
Eine Formel ist wohlgeformt (well formed formula, wff ) nach der Definition: Alle atomaren Formeln sind wffs. Falls und wffs sind, sind es auch
¬ ( & und ( Falls eine wff ist und x eine Variable, dann sind x als auch x wffs.
Das sind alle wffs.
9
Logische Konzepte:Erfüllbarkeit
Erfüllbarkeit ist definiert bezüglich einer Formel einem Modell M = (D,F) und einer Wertzuweisungsfunktion g für Variablen
Sei ein Term, dann wird dieser Term interpretiert als F(), falls eine Konstante ist. als g(), falls eine Variable ist. Allgemein schreiben wir Ig/F()
10
Def. Erfüllbarkeit
M,g R(t1,...,tn) gdw. (Ig/F(t1),...Ig/F(tn)) Œ F(R)M,g ¬ gdw. nicht M,g M,g & gdw. M,g und M,g M,g gdw. M,g oder M,g M,g gdw. nicht M,g oder M,g M,g x gdw. M,g‘ für einige x-
Varianten g‘ von gM,g x gdw. M,g‘ für alle x-
Varianten g‘ von g
11
Freie und gebundene Variablen
Variablen werden durch Quantoren gebunden:¬ (gluecklich(x) x (male(x) & essen(x,ue-eier)))
FREI GEBUNDEN
Eine Formel ohne freie Variablen heißt Satz.Eine freie Variable ist analog zu einem
Pronomen in dem folgenden Satz:Peter ißt sein drittes Ü-ei. Er ist glücklich.
12
Vorgehen
Umsetzung einer formalen Beschreibung in ein PROLOG-Programm
Verstehen des Unifikationmechanismus und des backtracking in PROLOG
Erkennen von Schwierigkeiten bei der Implementation
13
Definition des Vokabulars
Formal besteht ein Vokabular aus n-stelligen Relationen und Konstanten:
{(like,2),(happy,1),(bond,0),(loren,0)}In PROLOG erfolgt die Darstellung als...Klauseln in der Datenbasis: relation(like,2). constant(loren). relation(eat,2). constant(bond). relation(boring,1).constant(pavarrotti). relation(cute,1). constant(peter). relation(happy,1). constant(ue-eier).
14
Repräsentation der Modelle
Können alle Modelle dargestellt werden? Nein, da es unendlich
viele gibt!Wie sieht die Darstellung
der Domäne aus? Alle Elemente der
Domäne erhalten einen Namen!
Die Modelle sind exakt!Wie können finite und
exakte Modelle repräsentiert werden? als Liste: [cute(bond), like(loren,bond)]
Wieviele Individuen?Negatives Wissen?
(z.B. ÿcute(loren))
15
Darstellung der Formeln
Wie werden Variablen dargestellt?
Wie werden Konstanten und Relationensymbole repräsentiert?
Als PROLOG- Variablen: X oder _v
als PROLOG-Atome happy(loren)
16
Formeln: Junktoren
Wie werden die boolschen Junktoren dargestellt? als Operatoren (Neu: In SWI-Prolog 3.3.0 sind
Operatoren lokal in dem Modul definiert!) :- op(900,yfx,user:(>)), op(850,yfx,user:(v)), op(800,yfx,user:(&)), op(750,fx,user:(~)).
Wie werden die Quantoren repräsentiert? forall(X,cute(X)) und exists(Y,boring(Y))
17
Evaluierung der Formeln
Die Formel enthält Fakten, die das Modell zur Verfügung stellt (z.B. glücklich(loren)): satisfy(Formula,Model):- member(Formula,Model).
Der boolschen Junktoren & und v sind in model1.pl definiert als: satisfy(Formula1 & Formula2, Model):- satisfy(Formula1,Model), satisfy(Formula2,Model).
satisfy(Formula1 v Formula2, Model):- satisfy(Formula1,Model); satisfy(Formula2,Model).
18
Evaluierung von negierten Formeln
Die Negation wird mit Hilfe der PROLOG negation \+ überprüft: satisfy(~Formula, Model):- \+satisfy(Formula,Model).
Entsprechend wird die Implikation (A ∫ÆB ÿA⁄B) abgeprüft: satisfy(Formula1 v Formula2, Model):- satisfy(Formula2,Model); \+satisfy(Formula1,Model).
19
Testen der Modelle
Die Modelle sind als als example/2 abgespeichert: example(1,[cute(bond), cute(loren)...]). example(2,[cute(loren),..]).
Der Aufruf erfolgt mit evaluate/2: evaluate(Formula,Example):- example(Example,Model), satisfy(Formula,Model).
20
Problem 1 und Lösung
Was passiert mit ?- evaluate(X,1).
Das Programm landet in einer Unendlichkeits-Schleife
Wieso?
Lösung: Die Klausel evaluate/2 ändern und Variablen abfangen:
evaluate(Formula, Example):- \+var(Formula), example(Example,Model), sem(Formular,Model).
21
Problem 2
Wir testen cute(X) für Modell 1: ?- evaluate(cute(X),1). X=bond; X=loren
Wir testen ~cute(X) für Modell 1: PROLOG antwortet No!
Grund: Negation as failure! Lösung?
Instantiieren der PROLOG-Variablen mit den Konstanten aus dem Modell.
22
Problem 3
Was passiert mit Anfragen, die Symbole beinhalten, die nicht im Modell sind? ?- evaluate(happy(goldfinger),1).
Die Antwort ist No.Aber die Anfrage nach ?- evaluate(~happy(goldfinger),1). wird mit Yes beantwortet!
Lösung? Überprüfen der Wohlgeformtheit der Formel
23
Zusammenfassung
Umsetzung eines Formalismus mittels PROLOG: Repräsentation des Vokabulars Evaluierung der Formeln
Probleme entstanden durch Variablen Negation as failure Unbekannte Konstanten
Lösung der Probleme durch Abprüfen der Wohlgeformtheit der Ausdrücke!
24
Quellen
Literatur: Uwe Schöning. Logik für Informatiker. Spektrum
Akad. Verlag, Oxford, 1995, Kapitel 1. L.T.F. Gamut. Logic, Language, and Meaning, Vol. 1,
Chicago Press, 1991, chapter 2.Sourcecode für exampleModels.pl/model1.pl: /home/wsv_1/schilder/SemPrag/Models
Recommended