Default Logiken

Zhao Li12.12.2007

1

Inhalt1. Motivation2. Das Basis System von Reiter3. Schliessen mit Defaults4. Extensionen5. Ein operationaler Zugang zu Extensionen6. Prozessbäume7. Literatur

2

Motivation

Beispiel: Vögel können typischerweise fliegen.

Diese Regel kann in der klassischer Logik entweder durch “alle Vögel fliegen” ausgedrückt werden, die im Widerspruch zum Fakt, dass Pinguine nicht fliegen, oder durch “Alle Vögel, die nicht Pinguine und nicht Strauβe und ... Fliegen” ausgedrückt werden.

Wir werden im wesentlichen die Default-Logik von Reiter präsentieren.

Bei Default handelt es sich um:Regeln mit Ausnahmen, oderRegeln, die im Allgemeinen, meistens oder typischerweise gelten, oderRegeln, die gelten, solange nicht das Gegenteil explizit bewiesen worden ist.

3

Inhalt1. Motivation2. Das Basis System von Reiter3. Schliessen mit Defaults4. Extensionen5. Ein operationaler Zugang zu Extensionen6. Prozessbäume7. Literatur

4

Default-Theorie

Definition: Default Theorie

Eine Default Theorie ist ein Paar T = < D, W >, mit D ist eine Menge von “Defaults”. W ist eine Menge von prädikatenlogischen Formeln (genannt die Fakten von T)

5

Die Syntax von Defaults

Definition: Default

Ein Default δ hat die Form,

Das bedeutet: Wenn α gilt, β1,…, βm kann konsistent angenommen werden (d.h. ¬β1,…, ¬βm nicht bewiesen werden können), dann gilt w.

wobei α, βi (m≥1) und w aussagenlogische oder geschlossene prädikatenlogische Formeln sind.

α wird als Vorbedingung/precondition (kann leer sein)βm wird als Begründungen/justification (m≥1)w wird als Konsequenz/consequencedes Defaults bezeichnet.

α : β1 ,…, βm

w

6

Inhalt1. Motivation2. Das Basis System von Reiter3. Schliessen mit Defaults4. Extensionen5. Ein operationaler Zugang zu Extensionen6. Prozessbäume7. Literatur

7

Beispiel 1Die Default-Regel "Vögel können typischerweise fliegen " lautet in Default-Schreibweise:

D δ =

Diese Regel bedeutet, wenn X ein Vogel ist, und wenn Fliegen(X)konsistent angenommen werden kann, dass folgt Fliegen(X). und W enthältet einige Fakten über die Vögel.W = { Vogel(Condor), Vogel(Penguin), ¬Fliegen(Penguin), Fliegen(Eagle)}

Begründung existiert für: Fliegen(Condor) Keine Begründung existiert für: Fliegen (Penguin), Vogel(Eagle)

Vogel (X) : Fliegen (X)

Fliegen (X)

8

Beispiel 2

D δ =

W = { Vogel(Tweety), Vogel(Polly), Baby(Polly), ¬Fliegen(Fred) }

Begründung existiert für: Fliegen(Tweety), ¬Baby(Tweety), ¬Vogel(Fred)Keine Begründung existiert für: Fliegen(Polly)

: Vogel(X) → Fliegen(X)¬Baby(X)

Vogel(X) → Fliegen(X)¬Baby(X)

9

Beispiel 3 D δ =

W = { Vogel(Pete), Vogel(Mary), Baby(Pete)Baby(Mary) }

Begründung existiert für: Fliegen(Pete), Fliegen(Mary)Disjunktion ist nicht stark genug, um den Schluss zu blockieren.

Vogel(X): Fliegen(X)¬Baby(X)

Fliegen(X)

10

Inhalt1. Motivation2. Das Basis System von Reiter3. Schliessen mit Defaults4. Extensionen5. Ein operationaler Zugang zu Extensionen6. Prozessbäume7. Literatur

11

ExtensionenDefinition: Operator Г Gegeben eine Default Theorie T = < D, W >, Für jede Menge geschlossener Formeln S sei Г (S) die kleinste Formelmange, die die folgenden drei Bedingungen erfüllt:1. W Г (S)2. Cn ( Г (S)) = Г (S)

3. Wenn ∈D

α (c)∈ Г(S) und alle βi (c)∈S, dann w(c)∈ Г(S).

Definition: ExtensionEine Menge geschlossener Formeln E heiβt Extension einer Default-TheorieT = < D, W >, wenn gilt Г (E) = E. d.h. E ist ein Fixpunkt des Operators Г ist.

α : β1 ,…, βm

w

12

Beispiel 5 Extension

D δ = { }

W = { Wassertier(Pete) }

E1 erfüllt die alle drei Bedingungen der Definition von Operator Г .Г(E1) = Cn( {Wassertier(Pete), Fisch(Pete)} ) = E1

E1 = Cn( {Wassertier(Pete), Fisch(Pete)} ) als Extension

aber E2 = Cn( {Wassertier(Pete), ¬Fisch(Pete)} ) ist keine Extension, obwohl die alle drei Bedingungen der Definition von Operator Г erfüllt .doch es ist Г(E2) = Cn( {Wassertier(Pete)} ) ≠ E2

13

Fisch(X)

Wassertier(X) : Fisch(X)

Berechnung von Extension

Gegeben eine Default Theorie T = < D, W >, Sei E eine Formelmenge,Sei E0, E1,… eine Folge von Formelmengen, für die gilt:

1. E0 = W

2. Ei+1= Ei { w| ∈D, α∈Ei, und ¬βi,…,¬βnE}

Sei E =Cn(i Ei), dann ist E eine Extension von T.

14

α: β1,…, βm

w

Beispiel 6 Berechnung

D δ =

W = S0 = { Vogel(Tweety), Vogel(Polly), Baby(Polly), ¬Fliegen(Fred) }S1 = S0 { Fliegen(Tweety) } S = S1

E = Cn (S)

15

Vogel(X): Fliegen(X)¬Baby(X)

Fliegen(X)

Beispiel 7 Auto-Diamond

D δ1 = { } δ2 = { } δ3 = { } δ4 = { }

W = S0 = { Green(Pete), ADACmemb(Pete) }S1 = S0 { ¬LikesCars(Pete), DiscussCars(Pete) }S = S2 = S1

E = Cn(S)S1’ = S0 { LikesCars(Pete), DiscussCars(Pete) }S’ = S2’ = S1’E’ = Cn(S’)

16

Green(X) : ¬ LikesCars(X)

¬ LikesCars(X)

ADACmemb(X) : LikesCars(X)

LikesCars(X)

Green(X) : DiscussCars(X)

DiscussCars(X)

ADACmemb(X) : DiscussCars(X)

DiscussCars(X)

Zwei alternative Extensionen

δ1, δ3

δ2, δ4

Argumentieren mit Defaults

Definition: von Beispiel 7

Skeptische Argumentation (sceptical argumentation)

Die Default-Theorie T= < D, W > liefert eine skeptische Begründung einer Formel α, wenn α in allen Extensionen von T enthalten ist. Beispiel Auto-Diamond: discussCar(Pete).

Mutige Argumentation (brave argumentation)

Die Default-Theorie T = < D, W > liefert eine mutige Begründung einer Formel α, wenn α in einer Extension von T enthalten ist.Beispiel Auto-Diamond: discussCar(Pete), likesCar(Pete) oder discussCar(Pete), ¬ likesCar(Pete).

17

Inhalt1. Motivation2. Das Basis System von Reiter3. Schliessen mit Defaults4. Extensionen5. Ein operationaler Zugang zu Extensionen6. Prozessbäume7. Literatur

18

Default-Folge

Definition: Default-Folge

Gegeben eine Default Theorie T = < D, W >,Sei ∏ = ( δ0, δ1,… ) eine endliche oder unendliche Folge von Defaults aus T.∏[k] bezeichnet die Teilfolge der ersten k Defaults von ∏.Es gilt also ∏[k] = (δ0, δ1,… δk-1), wobei ∏[0]=() die leere Folge ist.

∏ stellt eine Ordnung von Defaults dar, Unabhängig davon, ob die Defaults angewendet werden können.

19

In- & Out- Mengen

Definition: In- und Out- Mengen

Zu jeder Folge ∏ von T = < D, W > existieren zwei Mengen von Formeln In(∏) und Out (∏).

In(∏) = Cn(M), wobei M = W∪ {cons(δ) |δ aus ∏ }cons(δ) bezeichnet die Konsequenz mit Default δ.In(∏) sammelt die Formeln, die durch Anwendung von Defaults aus T entstehen.und In(∏[0]) = Cn(W)

Out(∏) =δ∈∏ Out(δ), wobei Out (δ) = {¬β |β ∈ just(δ)}just(δ) bezeichnet die Menge der Begründungen.

23

anwendbar & Prozess

Definition: anwendbar“δ ist anwendbar in einer Formelmenge M”, gdw.prec(δ)∈Cn(M)Out(δ)Cn(M)= Ø

Definition: ProzessSei T = < D, W > eine Default Theorie.Eine Default-Folge ∏=(δ0, δ1,…) ist ein Prozess von T genau dann, wenn gilt:Jedes δk (aus ∏) ist in In(∏[k]) anwendbar.

21

Beispiel 8 anwendbar & Prozess

D δ1 = { } δ2 = { }

W = { Green(Pete) } Zeigen: ∏= (δ1[Pete], δ2[Pete]) ist kein Prozess von T.

1. In(∏[0]) = Cn(W) = Cn(Green(Pete))prec(δ1) = Green(Pete)∈ In(∏[0]))Out(δ1) = {LikesCars(Pete)} → Out(δ1) In(∏[0]) = Ø

Also: δ1 anwendbar in In(∏[0])

2. In(∏[1]) = Cn({Green(Pete), ¬LikesCars(Pete)})prec(δ2) = LikesCars(Pete)In(∏[1]))Also: δ2 nicht anwendbar in In(∏[1])Also: ∏ ist kein Prozess von T

22

Green(X) : ¬ LikesCars(X)

¬ LikesCars(X)

LikesCars(X) : DiscussCars(X)

DiscussCars(X)

Prozess: Eigenschaften

Definition:Sei ∏=(δ0, δ1,…) ein Prozess von T= < D, W >

1. ∏ ist erfolgreich, gdw. In(∏)∩Out(∏) = Ø; anderenfalls ist ∏ Fehlschlag.

2. ∏ ist abgeschlossen, gdw. jedes δ∈D, das in In(∏) anwendbar ist, in ∏ vorkommt.

23

Extensionen einer Default-Theorie

Definition: (von Antoniou)

Eine Formelmenge E ist eine Extension einer Default-Theorie T = < D, W > genau dann, wenn es eine abgeschlossene und erfolgreiche Prozess ∏ von T gibt, so dass E= In(∏).

24

Inhalt1. Motivation2. Das Basis System von Reiter3. Schliessen mit Defaults4. Extensionen5. Ein operationaler Zugang zu Extensionen6. Prozessbäumen7. Literatur

25

Prozessbäumen

Prozessbaum zu T = < D, W >

Kanten haben Defaults als Markierung.

Knoten sind markiert mit:• In-Menge, • Out-Menge, • gegebenfalls Information über erfolgreich & abgeschlossen

Wurzel ist Markiert mit In = Cn(W), Out = Ф

26

ProzessbäumenAufbau des Prozessbaums:N ein Knoten mit In & Out• N wird nur dann expandiert, wenn In Out = Ф; sonst : Fehlschlag.• Falls In Out = Ф aber kein anwendbarer Default existiert: geschlossen &

erfolgereich• Nachfolger N(δ) für alle δ, die bisher(auf dem Weg zu N) nicht auftreten, und

die in In anwendbar sind.• Nachfolger N(δ) ist markiert mit In(N(δ)) = Cn(In {cons(δ)}) Out(N(δ)) = Out Out(δ)

27

In ● Out

Cn(In cons(δ)) ● Out Out(δ)

δ

Beispiel 9 Prozessbäumen

D δ1 = { } δ2 = { }

mit W = Ø

28

: reliable(X)

¬ fired(X)

: fired(X)

pb_bonus(X)

Cn(Ø) ● Ø

Cn(¬fired(p)) ● {¬reliable(p)}

δ1[p]

Cn(pb_bonus(p)) ● {¬ fired(p)}

δ2[p]

geschlossen & erfolgereich

Fehlschlag

Cn({pb_bonus(p), {¬ fired(p)}) ● {¬ fired(p), ¬reliable(p)}

δ1[p]

Literatur

• Christoph Beierle/Gabriele Kern-Isberner: Methoden Wissensbasierter System

• “Default Logic” von Wikipedia

• Christopher Habel: Vorlesung über Wissensrepräsentation

29