Alternatywne logiki domniemań

1

Wady klasycznej logiki domniemań

1. Czasem brak rozszerzeń

T = ⟨∅, \{\frac{:p}{¬p}\}⟩

2. Brak półmonotoniczności

Przykład 1 Teoria T = ⟨\{A\}, \{\frac{A:B∧¬C}{B} \}⟩ ma jedno rozszerzenie E = T h({A, B}).

Dodajmy domniemanie: Teoria T′ = ⟨\{A\}, \{\frac{A:B∧¬C}{B} , \frac{A:C}{C} \}⟩ ma jedno rozszerzenie E′ = T h({A, C}). I E ⊈ E′.

Uwaga 1 Rozszerzenie teorii T′ jest intuicyjne, ale ta teoria powinna mieć drugie rozszerzenie E′′ = T h({A, B}).

3. Brak kumulatywności

Przykład 2 Teoria

T = ⟨∅, \{\frac{: A}{A}, \frac{A ∨ B : ¬A}{¬A}\}⟩

ma jedno rozszerzenie E = T h({A}), do którego należy A ∨ B.

Natomiast teoria

T′ = ⟨\{A ∨ B\}, \{\frac{: A}{A}, \frac{A ∨ B : ¬A}{¬A}\}⟩

ma dwa rozszerzenia E_{1} = T h({A}) i E_{2} = T h({¬A, B}).

4. Brak ”commitment to assumptions”

Rozważmy teorię T = ⟨∅, \{\frac{:B}{C} , \frac{:¬B}{D} \}⟩. Teoria ta ma rozszerzenie E = T h({C, D}).

Panuje przekonanie, że jest ono niewłaściwe. Klasyczny przykład mający to potwierdzić:

A - lewa ręka sprawna C - prawa ręka sprawna B - lewa ręka złamana D - prawa ręka złamana I teoria:

T = ⟨\{B ∨ D\}, \{\frac{:A∧¬B}{A} , \frac{:C∧¬D}{C} \}⟩ ma rozszerzenie E = T h({B ∨ D, A, C}).

Konkluzja: obie ręce są sprawne, chociaż wiemy, że jedna jest złamana.

To wygląda źle, ale problem jest natury semantycznej. Aby tę semantykę reprezentować, powinniśmy dopisać aksjomat, że jeśli ręka jest złamana, to nie jest sprawna. Czyli do T dodajemy

B ⇒ ¬A, D ⇒ ¬C.

Otrzymana teoria T′ ma dwa rozszerzenia i wynik jest zgodny z intuicją.

5. Brak kontrapozycji

T = ⟨\{¬F \}, \{\frac{B:F}{F} \}⟩ ma rozszerzenie E = T h(\{¬F \}). Nie możemy wywnioskować ¬B.

Niech B – Tweety jest ptakiem F – Tweety lata

Skoro “Jeśli tweety jest ptakiem, to przez domniemanie lata” i “Tweety nie lata”, to chcielibyśmy przez domniemanie wywnioskować, że Tweety nie jest ptakiem.

Generalnie, kontrapozycję chcielibyśmy mieć przy wnioskowaniu prototypowym. Natomiast przy innych formach wnioskowania niemonotonicznego nie jest wskazana.

Kontrprzykład: B – Jan jest podejrzany F – Jan jest niewinny Z tego, że Jan jest winny nie chcemy wnioskować, że nie jest podejrzany.

6. Brak wnioskowania “przez przypadki”

T = ⟨\{ptak ∨ samolot\}, \{\frac{ptak:lata}{lata}, \frac{samolot:lata}{lata}\}⟩

Mamy tu rozszerzenie E = T h({ptak ∨ samolot}). Nie możemy wywnioskować “lata”, choć intuicyjnie byśmy chcieli.

Rozwiązania Justified DL (W. Łukaszewicz)

Definicja 1 (rozszerzenia) Niech T = ⟨A, D⟩ będzie zamkniętą teorią domniemań. Dla dowolnej pary zbiorów formuł (S, W) niech Γ(S, W) będzie parą najmniejszych zbiorów formuł (S′, W′) takich, że

1. A ⊆ S′.

2. T h(S′) = S′.

3. dla dowolnego domniemania d = \frac{α:β}{ω} ∈ D, jeśli α ∈ S′ i S ∪ {ω} ∪ {γ} ⊬ ⊥ dla dowolnego γ ∈ W ∪ {β}, to ω ∈ S′ i β ∈ W′.

Zbiór formuł E jest rozszerzeniem teorii T względem zbioru formuł J wtedy i tylko wtedy, gdy Γ(E, J) = (E, J).

Przykład 3 T = ⟨∅, \{\frac{:p}{¬p}\}⟩

W JDL teoria ta ma rozszerzenie E = T h(∅). Jest to rozszerzenie względem pustego zbioru formuł.

Definicja rozszerzenia może wydawać się skomplikowana. Różnica polega na tym, że u Reitera najpierw stosujemy domniemanie, a potem robimy test niesprzeczności. Tutaj odwrotnie. Innymi słowy, te domniemania są stosowalne, dla których powiedzie się test niesprzeczności.

Własności JDL

1. Każda teoria domniemań ma rozszerzenie.

2. Dla dowolnych teorii zachodzi własność półmonotoniczności.

Przykład 4 (przykład 2) Teoria T = ⟨\{A\}, \{\frac{A:B∧¬C}{B} \}⟩ ma jedno rozszerzenie E = T h({A, B}).

Teoria T′ = ⟨\{A\}, \{\frac{A:B∧¬C}{B} , \frac{A:C}{C} \}⟩ ma dwa rozszerzenia E = T h({A, B}) i E′ = T h({A, C}).

3. Dla teorii normalnych rozszerzenia Reitera i J-rozszerzenia są identyczne.

4. Jeśli E jest rozszerzeniem Reitera, to jest J-rozszerzeniem.

Przykład 5

1. Zwykle w niedzielę chodzę na ryby, chyba że obudzę się późno.

d_{1} = \frac{niedz : na − ryby ∧ ¬późno}{na − ryby}

2. Zwykle na wakacjach budzę się późno.

d_{2} = \frac{wakacje : późno}{późno}

3. Aksjomaty: wakacje, niedz

W logice Reitera: E_{1} = T h({niedz, wakacje, późno}). W JDL: E_{1} i E_{2} = T h({niedz, wakacje, na − ryby}).

5. Logika JDL nie ma własności kumulatywności, “commitment to assumptions”, kontrapozycji i wnioskowania przez przypadki.

Constraint DL(Delgrande, Schaub, Jackson)

Pomysł: zbiór wszystkich uzasadnień zastosowanych domniemań + rozszerzenie ma być niesprzeczny. To rozwiązuje “commitment to assumptions”.

Definicja 2 (rozszerzenie) Niech T = ⟨A, D⟩ będzie zamkniętą teorią domniemań. Dla dowolnego zbioru formuł W niech Γ(W) będzie parą najmniejszych zbiorów formuł (S′, W′) takich, że

1. A ⊆ S′ ⊆ W′.

2. T h(S′) = S′ i T h(W′) = W′

3. dla dowolnego domniemania d = \frac{α:β}{ω} ∈ D, jeśli α ∈ S′ i W ∪ {ω} ∪ {β} ⊬ ⊥, to ω ∈ S′ i β ∧ ω ∈ W′.

Para zbiorów formuł (E, C) jest C-rozszerzeniem teorii T wtedy i tylko wtedy, gdy Γ(C) = (E, C).

T = ⟨\{B ∨ D\}, \{\frac{: A ∧ ¬B}{A} , \frac{: C ∧ ¬D}{C} \}⟩

Mamy dwa rozszerzenia:

(E_{1}, C_{1}) = (T h({A, B ∨ D}), T h({A ∧ ¬B, D}))
(E_{2}, C_{2}) = (T h({C, B ∨ D}), T h({C ∧ ¬D, B}))

Własności CDL

1. Każda teoria ma rozszerzenie.

2. Dla dowolnych teorii zachodzi własność półmonotoniczności.

3. Jeśli (A,D) jest normalną teorią domniemań i E jest Rrozszerzeniem tej teorii, to (E, E) jest jej C-rozszerzeniem.

4. Logika CDL nie ma własności kumulatywności, kontrapozycji i wnioskowania przez przypadki.