Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
1
Theoretische Grundlagen zu Default Logic
Eric Hildebrand
Logik in der Praxis: Logikprogrammierung und
unscharfes Schließen
WS 08/09
Universität Heidelberg
Seminar für Computerlinguistik
Institut für allgemeine und angewandte
Sprach- und Kulturwissenschaft
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 2
Inhaltsverzeichnis
� Einführung
� Syntax
� Semantik
� Variation
� Beispiele
� Quellennachweis
� Abschluss
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 3
Einführung
� Motivation - Ein typisches Problem…
� Lösungsversuch #1: Restriktionen
� Lösungsversuch #2: Exceptions
� Lösungsversuch #3: Default Logic
� Entstehung
� Einordnung
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 4
Motivation - Ein typisches Problem… (1)
� „Vögel können fliegen“
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 5
Motivation - Ein typisches Problem… (1)
� „Vögel können fliegen“
� klassische Prädikatenlogik:
Vogel(x) � kann_fliegen(x)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 6
Ein typisches Problem… (2)
� Tweety Vogel(x) � kann_fliegen(x)
Vogel(Tweety)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 7
Ein typisches Problem… (2)
� Tweety Vogel(x) � kann_fliegen(x)
Vogel(Tweety)
kann_fliegen(Tweety) ����
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 8
Ein typisches Problem… (3)
� TuxVogel(x) � kann_fliegen(x)
Pinguin(x) ���� Vogel(x)
Pinguin(Tux)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 9
Ein typisches Problem… (3)
� TuxVogel(x) � kann_fliegen(x)
Pinguin(x) ���� Vogel(x)
Pinguin(Tux)
kann_fliegen(Tux) � � � �
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 10
Ein typisches Problem… (4)
� Wo liegt das Problem?
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 11
Ein typisches Problem… (4)
� Wo liegt das Problem?
� ungenaue Formulierung der Ausgangsthese
� � „Typischerweise können Vögel fliegen“
(d.h. es gibt Ausnahmen)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 12
Lösungsversuch #1: Restriktionen
Vogel(x) � kann_fliegen(x)
Pinguin(x) � Vogel(x)
Pinguin(x) ���� ¬kann_fliegen(x)
Pinguin(Tux)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 13
Lösungsversuch #1: Restriktionen
Vogel(x) � kann_fliegen(x)
Pinguin(x) � Vogel(x)
Pinguin(x) ���� ¬kann_fliegen(x)
Pinguin(Tux)
kann_fliegen(Tux)
¬kann_fliegen(Tux)���� INKONSISTENT!
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 14
Lösungsversuch #2: Exceptions
Vogel(x) ^ ¬Pinguin(x) ���� kann_fliegen(x)
Pinguin(x) � Vogel(x)
Pinguin(Tux) ����
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 15
Lösungsversuch #2: Exceptions
� angenommen, wir hätten nun noch
Vogel(x) ^ ¬Pinguin(x) ���� kann_fliegen(x)
Pinguin(x) � Vogel(x)
Pinguin(Tux) ����
Strauß(x) � Vogel(x)
Strauß(Road_Runner)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 16
Lösungsversuch #2: Exceptions
� angenommen, wir hätten nun noch
Vogel(x) ^ ¬Pinguin(x) ���� kann_fliegen(x)
Pinguin(x) � Vogel(x)
Pinguin(Tux) ����
Strauß(x) � Vogel(x)
Strauß(Road_Runner)
� � für jede Ausnahme neue Regeländerung) nötig ����
Vogel(x) ^ ¬Pinguin(x) ^ ¬Strauß(x) ^ … ^ ���� kann_fliegen(x)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 17
Lösungsversuch #3: Default Logic
Vogel(x) : M kann_fliegen(x)
kann_fliegen(x)
W = { Pinguin(x) � Vogel(x),
Pinguin(x) � ¬kann_fliegen(x),
Pinguin(Tux), Vogel(Tweety) }
}D ={
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 18
Lösungsversuch #3: Default Logic
Vogel(x) : M kann_fliegen(x)
kann_fliegen(x)
W = { Pinguin(x) � Vogel(x),
Pinguin(x) � ¬kann_fliegen(x),
Pinguin(Tux), Vogel(Tweety) }
E = W U {Vogel(Tux), ¬kann_fliegen(Tux),
kann_fliegen(Tweety)}
}D ={
����
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 19
Entstehung
� Raymond Reiter (1939-2002) [Reiter 1980]
� Vergleich verschiedener
nicht-monotoner Logiken
� einheitliches Grundschema [Reiter 1978]
� default assignments, closed world assumption, frame
default, exceptions, negation as failure
� heute weit verbreitet, zahlreiche Weiterentwicklungen
[Lifschitz 1999]
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 20
Einordnung
� Logiken
� monoton
� Aussagenlogik
� Prädikatenlogik
� …
� nicht-monoton
� Schlüsse mit Default-Annahmen
� Default Logic
� …
� abduktives Schließen
� …
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 21
Inhaltsverzeichnis
� Einführung
� Syntax
� Semantik
� Variation
� Beispiele
� Quellennachweis
� Abschluss
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 22
Syntax
� Default-Regel
� Voraussetzung (prerequisite)
� Begründung (justification)
� Folgerung (consequent)
� Default-Theorie
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 23
Default-Regel
α(x) : M β1(x), …, M βm(x)
w(x)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 24
Voraussetzung (prerequisite)
α(x) : M β1(x), …, M βm(x)
w(x)
� α(x) heißt Voraussetzung
� α(x) i.A. Ausdruck in Prädikatenlogik
� kann leer sein
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 25
Begründung (justification)
α(x) : M β1(x), …, M βm(x)
w(x)
� M β1(x), …, M β2(x) heißt Begründung
� M ist Metasymbol für Konsistenz mit Wissensbasis
(� Semantik)
� βi(x) i.A. Ausdrücke in Prädikatenlogik
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 26
Folgerung (consequent)
α(x) : M β1(x), …, M βm(x)
w(x)
� w(x) heißt Folgerung
� w(x) i.A. Ausdruck in Prädikatenlogik
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 27
Default-Theorie
� ∆ heißt Default-Theorie
� D ist Menge von Default-Regeln
� W ist Menge von Ausdrücken i.A. in
Prädikatenlogik (Wissensbasis/Fakten)
∆ = (D,W)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 28
Inhaltsverzeichnis
� Einführung
� Syntax
� Semantik
� Variation
� Beispiele
� Quellennachweis
� Abschluss
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 29
Semantik
� Semantik von Default-Regeln
� Konsistenz
� Extensionen von Default-Theorien
� Grundidee
� E. als Fixpunkt
� Konstruktion
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 30
Semantik von Default-Regeln
� w(x) kann gefolgert werden, wenn
� W├ α(x) und
� nicht W ├ ¬β1(x), …, ¬βm(x)
∆ = (D,W)
α(x) : M β1(x), …, M βm(x)
w(x)
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 31
Konsistenz
� nicht W ├ ¬β1(x), …, ¬βm(x)
� was bedeutet das?
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 32
Konsistenz
� nicht W ├ ¬β1(x), …, ¬βm(x)
� was bedeutet das?
� β1(x), …, βm(x) konsistent mit
Wissensbasis W, d.h. steht nicht im
Widerspruch zu den Fakten
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 33
Extensionen: Grundidee
� sei ∆ = (D,W)
� Idee: Extension E einer Default-Theorie komplettiert die
unvollständige Faktenmenge W
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 34
Extensionen: Grundidee
� sei ∆ = (D,W)
� Idee: Extension E einer Default-Theorie komplettiert die
unvollständige Faktenmenge W
� E sei die kleinste Menge, für die gilt:
� W c E
� E ist abgeschlossen unter Deduktion (Th(E)=E)
� sei δ Є D, α Є E und β1(x), …, βm(x) konsistent mit E,
dann w Є E
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 35
Extensionen als Fixpunkt
� sei ∆ = (D,W)
� L =def Menge der wohlgeformten Ausdrücke (wff) in Prädikatenlogik
� für alle S c L sei Γ(S) die kleinste Menge, für die gilt:
� W c Γ(S)
� ThL(Γ(S)) = Γ(S)
� sei δ Є D, α Є Γ(S) und β1(x), …, βm(x) konsistent mit Γ(S),
dann w Є Γ(S)
� eine Menge E wffs ist eine Extension für ∆ � E ist Fixpunkt von Γ
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 36
Extensionen: Konstruktion
� sei ∆ = (D,W)
� E0 = W
� für i ≥ 0:
� Ei+1 = ThL(Ei) U { w|
� mit α Є Ei und ¬β1(x), …, ¬βm(x) Є E }
� E ist Extension von ∆ � E = U Ei
α(x) : M β1(x), …, M βm(x)
w(x)
8
i=0
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 37
Inhaltsverzeichnis
� Einführung
� Syntax
� Semantik
� Variation
� Beispiele
� Quellennachweis
� Abschluss
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 38
Variation
� skeptisch (sceptical)
� ein wff w folgt aus einer Default-Theorie ∆, wenn w in
allen Extensionen Ei von ∆ enthalten ist
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 39
Variation
� skeptisch (sceptical)
� ein wff w folgt aus einer Default-Theorie ∆, wenn w in
allen Extensionen Ei von ∆ enthalten ist
� gutgläubig (credulous)
� (manchmal auch mutig (brave))
� ein wff w folgt aus einer Default-Theorie ∆, wenn w in
mindestens einer Extensionen Ej von ∆ enthalten ist
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 40
Inhaltsverzeichnis
� Einführung
� Syntax
� Semantik
� Variation
� Beispiele
� Quellennachweis
� Abschluss
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 41
Beispiele
� Nixon-Diamant
� Normal Defaults
� Semi-Normal Defaults
� Non-Normal Defaults
� Defaults ohne Extension
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 42
Nixon-Diamant
∆ = (D,W)
D = {Republican(x) : ¬Pacifist(x), Quaker(x) : Pacifist(x)}¬Pacifist(x) Pacifist(x)
W = {Republican(Nixon), Quaker(Nixon)}
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 43
Nixon-Diamant
∆ = (D,W)
D = {Republican(x) : ¬Pacifist(x), Quaker(x) : Pacifist(x)}¬Pacifist(x) Pacifist(x)
W = {Republican(Nixon), Quaker(Nixon)}
E1 = {Republican(Nixon),Quaker(Nixon),¬Pacifist(Nixon)}
E2 = {Republican(Nixon),Quaker(Nixon),Pacifist(Nixon)}
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 44
Normal Defaults
∆ = (D,W)
D = {:M Küken(Tux), :M Pinguin(Tux), :M kann_fliegen(Tux)}
Küken(Tux) Pinguin(Tux) kann_fliegen(Tux)
W = {kann_fliegen(Tux) ^ ¬Küken(Tux) ^ ¬Pinguin(Tux)}
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 45
Normal Defaults
∆ = (D,W)
D = {:M Küken(Tux), :M Pinguin(Tux), :M kann_fliegen(Tux)}
Küken(Tux) Pinguin(Tux) kann_fliegen(Tux)
W = {kann_fliegen(Tux) � ¬Küken(Tux) ^ ¬Pinguin(Tux)}
E1 = Th(W U {Küken(Tux), Pinguin(Tux)})
E2 = Th(W U {kann_fliegen(Tux)})
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 46
Semi-Normal Defaults (1)
∆ = (D,W)
D = {Vogel(x) : kann_fliegen(x) ^ ¬Pinguin(x)}kann_fliegen(x)
W = {Vogel(Tux), Vogel(Tweety),
Pinguin(Tux) v Pinguin(Tweety)}
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 47
Semi-Normal Defaults (1)
∆ = (D,W)
D = {Vogel(x) : kann_fliegen(x) ^ ¬Pinguin(x)}kann_fliegen(x)
W = {Vogel(Tux), Vogel(Tweety),
Pinguin(Tux) v Pinguin(Tweety)}
E = {Vogel(Tux), Vogel(Tweety),
Pinguin(Tux) v Pinguin(Tweety),
kann_fliegen(Tux), kann_fliegen(Tweety)} ����
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 48
Semi-Normal Defaults (2)
D = {Vogel(x) : kann_fliegen(x) ^ ¬Küken(x),kann_fliegen(x)
klein(x) : kreischt(x) ^ Küken(x)}kreischt(x)
W = {Vogel(Tweety), klein(Tweety)}
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 49
Semi-Normal Defaults (2)
D = {Vogel(x) : kann_fliegen(x) ^ ¬Küken(x),kann_fliegen(x)
klein(x) : kreischt(x) ^ Küken(x)}kreischt(x)
W = {Vogel(Tweety), klein(Tweety)}
Ei = {Vogel(Tweety), klein(Tweety),
kann_fliegen(Tweety), kreischt(Tweety)}����
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 50
Non-Normal Defaults
∆ = (D,W)
D = {:M Pinguin(Tux), :M kann_fliegen(Tux), :M Küken(Tux)}
¬kann_fliegen(Tux) ¬Küken(Tux) ¬groß(Tux)
W = Ø
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 51
Non-Normal Defaults
∆ = (D,W)
D = {:M Pinguin(Tux), :M kann_fliegen(Tux), :M Küken(Tux)}
¬kann_fliegen(Tux) ¬Küken(Tux) ¬groß(Tux)
W = Ø
E = Th({¬kann_fliegen(Tux), ¬groß(Tux)})
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 52
Defaults ohne Extension
D = { : Vogel(Tux) }¬Vogel(Tux)
W = Ø
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 53
Defaults ohne Extension
D = { : Vogel(Tux) }¬Vogel(Tux)
W = Ø
E = Ø
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 54
Inhaltsverzeichnis
� Einführung
� Syntax
� Semantik
� Variation
� Beispiele
� Quellennachweis
� Abschluss
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 55
Quellennachweis
�Bibliographie
�Webliographie
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 56
Bibliographie� [Lifschitz 1999] Lifschitz, V. 1999. Success of Default Logic. In Logical Foundations for Cognitive
Agents: Contributions in Honour of Ray Reiter, Springer Verlag, 1999, 208-212.
� [Poole 1988] Poole, D. 1988. A logical framework for default reasoning. Artificial Intelligence, 36(1):27-
47, 1988.
� [Poole 1994] Poole, D. 1994. Default Logic. In D. M. Gabbay, C. J. Hogger J. A. Robinson (eds.)
Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3, Oxford University Press,
1994, 189-215.
� [Reiter 1978] Reiter, R. 1978. On reasoning by default. In Proceedings of the 1978 Workshop on
theoretical Issues in Natural Language Processing (Urbana-Champaign, Illinois, July 25 - 27, 1978).
Theoretical Issues In Natural Language Processing. Association for Computational Linguistics,
Morristown, NJ, 210-218.
� [Reiter 1980] Reiter, R. A logic for default reasoning. Artificial Intelligence, 13(1,2):81-132, 1980.
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 57
Webliographie� Niemelä, I. Default Logic: From Theory to Applications. http://www.tcs.hut.fi/~ini/esslli99/
(accessed February 4, 2009).
� Schmidt, C. F. Default Logic. http://www.rci.rutgers.edu/~cfs/472_html/Logic_KR/DefaultTheory.html
(accessed February 4, 2009).
� Stanford Encyclopedia of Philosophy contributors. Defeasible Reasoning. In Stanford Encyclopedia of
Philosophy, http://plato.stanford.edu/entries/reasoning-defeasible/
(accessed February 4, 2009).
� Stanford Encyclopedia of Philosophy contributors. Non-monotonic Logic. In Stanford Encyclopedia of
Philosophy, http://plato.stanford.edu/entries/logic-nonmonotonic/
(accessed February 4, 2009).
� Wikipedia contributors. Default logic. In Wikipedia, The Free Encyclopedia,
http://en.wikipedia.org/w/index.php?title=Default_logic&oldid=254533181
(accessed February 4, 2009).
Logik in der Praxis: Theoretische Grundlagen zu Default Logic (Eric Hildebrand) 58
Abschluss
Vielen Dank für die
Aufmerksamkeit! ☺
Gibt es Fragen?