Logika domniemań w CAKE ’u

na podstawie: P. Doherty, W. Łukaszewicz, A. Skowron, A. Szałas: Knowledge Representation Techniques: A Rough Set Approach, Springer-Verlag, 2006.

Język Ograniczony język logiki I rzędu, tzn.

• brak symboli funkcyjnych i kwantyfikatorów

• postać teorii: disjunction-free, tj.

– warunek wstępny i uzasadnienie domniemania: koniunkcja literałów;

– konsekwencja domniemania: literał (pojedyńczy)

– aksjomaty teorii: literały ukonkretnione (ground).

Reprezentacja teorii normalnych w CAKE ’u

Przykład 1 Rozważmy teorię T = ⟨{B(t)}, {B(x) : F (x)/F (x)}⟩, gdzie B, F, t oznaczają odpowiednio Bird, F lies and T weety i jej CAKE diagram (uwaga: R^{⊕} ≡ ¬R^{−}).

[figure: t; A_{1} : B(x); A_{2} : F (x); A_{2}.F^{−}; A_{1}.B^{+} ∧ A_{2}.F^{⊕}; A_{3} : F (x); A_{2}.F^{+}; +; +; +; −; −; −]

Zbiór reguł związany z powyższym przykładem:

A_{2}.F^{−}(x) → A_{3}.F^{−}(x)  (1)
[A_{2}.F^{+} (x) ∨ [A_{1}.B^{+} (x) ∧ ¬A_{2}.F^{−}(x)]] → A_{3}.F^{+} (x) (2)
A_{1}.B^{+} (t).  (3)

Stratyfikacja: {(3)},{(1),(2)}. Obliczenia:

{} {A_{1}.B^{+} (t)} {A_{1}.B^{+} (t), A_{3}.F^{+} (t)}.

Przykład 2 Rozważmy teorię

T = ⟨{Q(n), R(n)}{Q(x) : P (x)/P (x), R(x) : ¬P (x)/¬P (x)}⟩

i jej CAKE diagram.

[figure: n; A_{1} : Q(x); n; A_{2} : R(x); A_{2}.R^{+} ∧ A_{3}.P^{⊖}; A_{4} : P (x); A_{3}.P^{−}; A_{3} : P (x); M : P (x); A_{3}.P^{+}; A_{5} : P (x); A_{1}.Q^{+} ∧ A_{3}.P^{⊕}; A_{3}.P^{+}; A_{3}.P^{−}; +; +; +; +; +; −; −; −; −; −]

6

Zbiór reguł związany z powyższym przykładem:

A_{1}.Q^{+} (n)

A_{2}.R^{+} (n)

[A_{3}.P^{−}(x) ∨ [A_{2}.R^{+} (x) ∧ ¬A_{3}.P^{+} (x)]] → A_{4}.P^{−}(x)

A_{3}.P^{+} (x) → A_{4}.P^{+} (x)

A_{3}.P^{−} → A_{5}.P^{−}(x)

[A_{3}.P^{+} (x) ∨ [A_{1}.Q^{+} (x) ∧ ¬A_{3}.P^{−}(x)]] → A_{5}.P^{+} (x)

[A_{4}.P^{−}(x) ∨ A_{5}.P^{−}(x)] ∧ ¬[A_{4}.P^{+} (x) ∨ A_{5}.P^{+} (x)] → M.P^{−}(x)

[A_{4}.P^{+} (x) ∨ A_{5}.P^{+} (x)] ∧ ¬[A_{4}.P^{−}(x) ∨ A_{5}.P^{−}(x)] → M.P^{+} (x).

Dwie ostatnie reguły stanowią standardowy mechanizm glosowania (voting). Obliczenia:

{}
{A_{1}.Q^{+} (n), A_{2}.R^{+} (n)}
{A_{1}.Q^{+} (n), A_{2}.R^{+} (n), A_{4}.P^{−}(n), A_{5}.P^{+} (n)}.

Załóżmy, że interesuje nas czy P (n). Sytuacja wygląda następująco: A_{4} odpowiada False , a A_{5} odpowiada True . Jednak jest jeszcze default-moduł, który obsługuje relację P, ale n nie spełnia ani M.P^{+} ani M.P^{−}, więc odpowiedź jest Unknown .

T = ⟨{B(t)}, {B(x) : F (x)/F (x), F (x) : W (x)/W (x)}⟩.

gdzie B, F, W i t oznaczają odpowiednio Bird, F lies, HasW ings i T weety oraz jej CAKE diagram

[figure: t; A_{1} : B(x); A_{2} : F (x); A_{1}.B^{+} ∧ A_{2}.F^{⊕}; A_{4} : F (x); A_{4}.F^{+} ∧ A_{3}.W^{⊕}; A_{2}.F^{−}; A_{3}.W^{+}; A_{3} : W (x); A_{5} : W (x); A_{2}.F^{+}; A_{3}.W^{−}; +; +; +; +; +; −; −; −; −; −]

10

Zbiór reguł dla tej teorii A_{1}.B^{+} (t) A_{2}.F^{−}(x) → A_{4}.F^{−}(x) [A_{2}.F^{+} (x) ∨ [A_{1}.B^{+} (x) ∧ ¬A_{2}.F^{−}(x)]] → A_{4}.F^{+} (x) A_{3}.W^{−}(x) → A_{5}.W^{−}(x) [A_{3}.W^{+} (x) ∨ [A_{4}.F^{+} (x) ∧ ¬A_{3}.W^{−}(x)]] → A_{5}.W^{+} (x).

Stratyfikacja: P_{1}, P_{2}, gdzie P_{1} składa sie z pierwszej reguły, a P_{2} z pozostałych. Obliczenia:

{} {A_{1}.B^{+} (t)} {A_{1}.B^{+} (t), A_{4}.F^{+} (t)} {A_{1}.B^{+} (t), A_{4}.F^{+} (t), A_{5}.W^{+} (t)}.

Interesuje nas czy W (t). Ponieważ t spełnia A_{5}.W^{+} , więc odpowiedź jest True .

Formalizacja

Mówimy, że dwa domniemania są podobne, jeśli ich konsekwencje zawierają ten sam symbol relacyjny.

Definicja 1 Niech T = ⟨A, D⟩ będzie normalną teorią domniemań nad językiem L. Diagram teorii T konstruuje się w sposób następujący:

1. Dla każdego symbolu relacyjnego R z języka L, konstruujemy granulkę, zwaną agentem bazodanowym, reprezentującą R. Jeśli R(t) (odp. ¬R(t)) należy do A, krotka t występuje w pozytywnej (odp. negatywnej) części diagramu agenta. Wszystkie pozostałe krotki stałych należą do części granicznej diagramu.^{∗} Każdy agent bazodanowy posiada etykietę name : R, gdzie name jest unikalną nazwą agenta, a R jest obsługiwanym przez niego symbolem relacyjnym.

2. Dla każdego domniemania d ∈ D, konstruujemy defaultagenta reprezentującego d. Agent posiada etykietę name : R, gdzie name jest unikalną nazwą agenta, a R jest symbolem relacyjnym występującym w konsekwencji d. Metody agenta zostaną zdefiniowane w punkcie 6.

3. Wszyscy default-agenci, A_{1}, …, A_{k}, k > 1, reprezentujący domniemania podobne zostają zgrupowani w pojedyńczym module, tzw. default-module. Moduł posiada etykietę name : R, gdzie name jest unikalną nazwą modułu, a R jest symbolem relacyjnym obsługiwanym przez

∗Przypominamy, że część graniczna diagramu nie jest reprezentowana explicite.

agentów A_{1}, …, A_{k}, k > 1. Default-agent, który nie jest zanurzony w żadnym module nazywa się niezależnym, w przeciwnym przypadku nazywa sie zależnym.

4. Niech A będzie niezależnym agentem reprezentującym domniemanie d, którego konsekwencja zawiera symbol relacyjny R. Niech R_{1}, …, R_{n} będą wszystkimi symbolami relacyjnymi występującymi w warunku wstępnym d. Dla każdego 1 ≤ i ≤ k tworzymy strzałkę do A z każdego agenta bazodanowego i z każdego modułu (lub niezależnego default-agenta) reprezentującego R_{i} oraz bazodanowego agenta reprezentującego R.

5. Niech M będzie modułem reprezentującym relację R, a A_{1}, …, A_{n} default-agentami z M, gdzie A_{i} odpowiada domniemaniu d_{i}. Niech R_{1},…, R_{k} będą wszystkimi symbolami relacyjnymi występującymi w warunkach wstępnych d_{1}, …, d_{n}. Prowadzimy strzałkę do M z agenta bazodanowego reprezentującego R_{i} i z modułu reprezentujacego R_{i} dla każdego 1 ≤ i ≤ k, oraz z agenta bazodanowego reprezentującego R.

6. Przypisanie metod default-agentom. Niech agent reprezentuje domniemanie postaci l_{1} ∧ ⋯ ∧ l_{n} : l/l, gdzie n ≥ 0, a R_{1}, …, R_{n}, R są odpowiadającymi im symbolami relacji. Generujemy dwie metody bazodanowe, mianowicie A_{k}.R^{+} i A_{k}.R^{−}, gdzie A_{k} jest agentem bazodanowym odpowiedzialnym za relację R, i umieszczamy je, odpowiednio, w pozytywnej i negatywnej części diagramu. Następnie generujemy default-metodę, którą umieszcza się w pozytywnej części, jeśli l jest literałem pozytywnym, a w negatywnej w przeciwnym przypadku. Konstrukcja metod przebiega w sposób następujący:

(a) Załóżmy najpierw, że żadna z R_{1}, …, R_{n} nie jest reprezentowana przez default-moduł ani przez niezależnego default-agenta. Default-metoda jest postaci

A_{1}.X_{1} ∧ ⋯ ∧ A_{n}.X_{n} ∧ A.X, (4)

gdzie A_{1}, …, A_{n}, A są agentami bazodanowymi odpowiedzialnymi za R_{1}, …, R_{n}, R, odpowiednio, X_{i} jest R_{i}^{+} (jeśli l_{i} jest pozytywny) lub R_{i}^{−} (jeśli l_{i} jest negatywny) a X jest ¬R^{−} (jeśli l jest pozytywny) lub ¬R^{+} (jeśli l jest negatywny).

(b) Załóżmy teraz, że przynajmniej jedna z R_{1}, …, R_{n} jest reprezentowana przez default-moduł lub przez niezależnego default-agenta. Niech R_{i}, … R_{j} będą wszystkimi relacjami spośród R_{1}, …, R_{n}, które są reprezentowane przez default-moduł lub przez niezależnego defaultagenta, a M_{i}, …, M_{j} są odpowiadającymi im modułami. Metoda jest postaci (4) gdzie A_{i}, …, A_{j} są zastąpione odpowiednio przez M_{i}, …, M_{j}.

Z powyższego diagramu generujemy zbiór reguł (CAKE program) stosując standardową metodologię CAKE’a. W przypadku konfliktów stosuje się standardowy mechanizm głosowania (voting), więc nie włącza się tych granulek do defaultmodułów.

Uwaga 1 CAKE program uzyskany z diagramu normalnej teorii domniemań nie musi być stratyfikowalny.

Przykład 4 Rozważmy teorię T = ⟨A, D⟩, gdzie

A = {Q(n)}, a
D = {Q(x) : P (x)/P (x), R(x) : ¬P (x)/¬P (x),
P (x) : Q(x)/Q(x), S(x) : ¬Q(x)/¬Q(x)}

i CAKE diagram

[figure: A_{1} : R(x); A_{2} : P (x); A_{1}.R^{+} ∧ A_{2}.P^{⊖}; A_{2}.P^{−}; N.Q^{+} ∧ A_{2}.P^{⊕}; A_{5} : P (x); A_{3} : Q(x); A_{6} : P (x); A_{8} : Q(x); M.P^{+} ∧ A_{3}.Q^{⊕}; A_{3}.Q^{−}; M : P (x); A_{4} : S(x); A_{3}.Q^{+}; A_{7} : Q(x); A_{2}.P^{−}; A_{3}.Q^{−}; A_{4}.S^{+} ∧ A_{3}.Q^{⊖}; A_{3}.Q^{+}; N : Q(x); A_{2}.P^{+}; A_{2}.P^{+}; +; −; +; +; +; +; +; +; +; −; −; −; −; −; −; −; n]

15

A_{3}.Q^{+} (n) [A_{2}.P^{−}(x) ∨ (A_{1}.R^{+} (x) ∧ ¬A_{2}.P^{+} (x))] → A_{5}.P^{−}(x) A_{2}.P^{+} (x) → A_{5}.P^{+} (x) A_{2}.P^{−}(x) → A_{6}.P^{−}(x) [A_{2}.P^{+} (x) ∨ (N.Q^{+} (x) ∧ ¬A_{2}.P^{−}(x))] → A_{6}.P^{+} (x) A_{3}.Q^{−}(x) → A_{7}.Q^{−}(x) [A_{3}.Q^{+} (x) ∨ (M.P^{+} (x) ∧ ¬A_{3}.Q^{−}(x))] → A_{7}.Q^{+} (x) A_{3}.Q^{−}(x) → A_{8}.Q^{−}(x) [A_{3}.Q^{+} (x) ∨ (A_{4}.S^{+} (x) ∧ ¬A_{3}.Q^{−}(x))] → A_{8}.Q^{+} (x) [A_{5}.P^{−}(x) ∨ A_{6}.P^{−}(x)] ∧ ¬[A_{5}.P^{+} (x) ∨ A_{6}.P^{+} (x)] → M.P^{−}(x) [A_{5}.P^{+} (x) ∨ A_{6}.P^{+} (x)] ∧ ¬[A_{5}.P^{−}(x) ∨ A_{6}.P^{−}(x)] → M.P^{+} (x) [A_{7}.Q^{−}(x) ∨ A_{8}.Q^{−}(x)] ∧ ¬[A_{7}.Q^{+} (x) ∨ A_{8}.Q^{+} (x)] → N.Q^{−}(x) [A_{7}.Q^{+} (x) ∨ A_{8}.Q^{+} (x)] ∧ ¬[A_{7}.Q^{−}(x) ∨ A_{8}.Q^{−}(x)] → N.Q^{+} (x).

Powyższy zbiór reguł nie jest stratyfikowalny.

17

Definicja 2 Stratyfikowalną teorią domniemań (normalną lub nie) nazywamy teorię, której CAKE program jest stratyfikowalny.

Definicja 3 Niech T będzie stratyfikowalną teorią domniemań, a Π CAKE programem teorii T. Ukonkretniony (ground) literał postaci P (c̄) (odpowiednio ¬P (c̄)) jest wyprowadzalny z T wtedy i tylko wtedy, gdy X.P^{+} (c̄) (odpowiednio X.P^{−}(c̄)), gdzie X jest nazwą agenta bazodanowego, niezależnego defaultagenta lub default-modułu, należy do lfp(CS_{Π}).

Definicja 4 Niech T będzie stratyfikowalną normalną teorią domniemań. Rozszerzeniem T jest zbiór ukonkretnionych literałów wyprowadzalnych z T.

Własność semi-monotoniczności na ogół nie zachodzi w CAKE logice domniemań. Jako przykład rozważmy teorię normalną

T = ⟨\{Q(n), R(n)\}, \{\frac{Q(x) : P (x)}{P (x)} \}⟩ .

która ma rozszerzenie E = {Q(n), R(n), P (n)}.

Jesli dodamy nowe domniemanie \frac{R(x):¬P (x)}{¬P (x)} , to rozszerzenie otrzymanej teorii jest E′ = {Q(n), R(n)}.

Twierdzenie 1 W CAKE logice domniemań każda stratyfikowalna normalna teoria domniemań ma jedno rozszerzenie.

Można by się spodziewać, że rozszerzenie to odpowiada przecięciu rozszerzeń w logice Reitera. Niestety, tak nie jest.

Przykład 5 Rozważmy teorię T = ⟨A, D⟩, gdzie

A = {Q(n), R(n)}

D = \{\frac{Q(x) : P (x)}{P (x)} , \frac{R(x) : ¬P (x)}{¬P (x)} , \frac{P (x) : V (x)}{V (x)} , \frac{¬P (x) : V (x)}{V (x)} \} .

W logice Reitera są dwa rozszerzenia

E_{1} = Cn({Q(n), R(n), V (n), P (n)})
E_{2} = Cn({Q(n), R(n), V (n), ¬P (n)}).

CAKE diagram tej teorii:

[figure: n; A_{1} : Q(x); n; A_{2} : R(x); A_{2}.R^{+} ∧ A_{3}.P^{⊖}; A_{3}.P^{−}; A_{1}.Q^{+} ∧ A_{3}.P^{⊕}; A_{5} : P (x); A_{3} : P (x); A_{6} : P (x); A_{8} : V (x); M.P^{−} ∧ A_{4}.V^{⊕}; A_{4}.V^{−}; M : P (x); A_{4} : V (x); A_{4}.V^{+}; A_{7} : V (x); A_{3}.P^{−}; A_{4}.V^{−}; M.P^{+} ∧ A_{4}.V^{⊕}; A_{4}.V^{+}; N : V (x); A_{3}.P^{+}; A_{3}.P^{+}; +; −; +; +; +; +; +; +; +; −; −; −; −; −; −; −]

21

Reguły:

A_{1}.Q^{+} (n) A_{2}.R^{+} (n) {A_{3}.P^{−}(x) ∨ [A_{2}.R^{+} (x) ∧ ¬A_{3}.P^{+} (x)]} → A_{5}.P^{−}(x)

A_{3}.P^{+} (x) → A_{5}.P^{+} (x) A_{3}.P^{−}(x) → A_{6}.P^{−}(x) {A_{3}.P^{+} (x) ∨ [A_{1}.Q^{+} (x) ∧ ¬A_{3}.P^{−}(x)]} → A_{6}.P^{+} (x)

A_{4}.V^{−}(x) → A_{7}.V^{−}(x) {A_{4}.V^{+} (x) ∨ [M.P^{−}(x) ∧ ¬A_{4}.V^{−}(x)]} → A_{7}.V^{+} (x)

A_{4}.V^{−}(x) → A_{8}.V^{−}(x) {A_{4}.V^{+} (x) ∨ [M.P^{+} (x) ∧ ¬A_{4}.V^{−}(x)]} → A_{8}.V^{+} (x)

[A_{5}.P^{−}(x) ∨ A_{6}.P^{−}(x)] ∧ ¬[A_{5}.P^{+} (x) ∨ A_{6}.P^{+} (x)] → M_{.}P^{−}(x) [A_{5}.P^{+} (x) ∨ A_{6}.P^{+} (x)] ∧ ¬[A_{5}.P^{−}(x) ∨ A_{6}.P^{−}(x)] → M_{.}P^{+} (x) [A_{7}.V^{−}(x) ∨ A_{8}.V^{−}(x)] ∧ ¬[A_{7}.V^{+} (x) ∨ A_{8}.V^{+} (x)] → N_{.}V^{−}(x) [A_{7}.V^{+} (x) ∨ A_{8}.V^{+} (x)] ∧ ¬[A_{7}.V^{−}(x) ∨ A_{8}.V^{−}(x)] → N_{.}V^{+} (x).

Obliczenia:

{}
{A_{1}.Q^{+} (n), A_{2}.R^{+} (n)}
{A_{1}.Q^{+} (n), A_{2}.R^{+} (n), A_{5}.P^{−}(n), A_{6}.P^{+} (n)}.

Tak więc N.V^{+} (n) nie należy do rozszerzenia tej teorii, podczas gdy V (n) należy do obu rozszerzeń tej teorii w wersji Reitera.

Logika domnieman z mocnymi warunkami wstępnymi

Standardowa logika domniemań nie posiada mechanizmów pozwaląjacych rozróżniać pomiędzy wnioskami wyprowadzonymi z aksjomatów (mocnymi), a wnioskami wyprowadzonymi za pośrednictwem domniemań (słabymi).

Przykład 6

John jest osobą.

Na ogół ludzie są uczciwi.

Na ogół, osobie, o której wiadomo, że jest uczciwa, można bezpiecznie pożyczyć pieniądze.

Teoria domniemań reprezentująca te zdania jest następująca:

W = \{P (j)\} D = \{\frac{P (x) : H(x)}{H(x)} , \frac{H(x) : M(x)}{M(x)} \} .

i jej diagram

[figure: j; A_{1} : P (x); A_{2} : H(x); A_{5} : M(x); A_{3} : M(x); A_{1}.P^{+} ∧ A_{2}.H^{⊕}; A_{4}.H^{+} ∧ A_{3}.M^{⊕}; +; A_{3}.M^{+}; A_{2}.H^{−}; A_{3}.M^{−}; A_{2}.H^{+}; A_{4} : H(x); +; +; +; +; −; −; −; −; −]

Teoria ta pozwala wywnioskować M(j), co jest niezgodne z intuicją. Wniosek H(j) jest akceptowalny, ale ponieważ wynika z domniemania, więc wydaje się za słaby, żeby wywnioskować M(j).

CAKE pozwala nam łatwo zablokować niepożądane konkluzje. Wystarczy usunąć strzałkę z A_{4} do A_{5} i dodać strzałkę z A_{2} do A_{5}. Dostajemy diagram

[figure: j; A_{1} : P (x); A_{2} : H(x); A_{4} : H(x); A_{5} : M(x); A_{1}.P^{+} ∧ A_{2}.H^{⊕}; A_{2}.H^{+} ∧ A_{3}.M^{⊕}; A_{3} : M(x); A_{3}.M^{+}; A_{2}.H^{−}; A_{3}.M^{−}; A_{2}.H^{+}; +; +; +; +; +; −; −; −; −; −]

Formalizacja

Rozszerzamy język: dodajemy operator K, który może wystąpić przed literałem i Kl oznacza “wiadomo, że l jest prawdziwe”. Tak więc, będziemy rozważać domniemania postaci

\frac{B_{1} ∧ ⋯ ∧ B_{n} : l}{l}

i każde B_{i} jest l lub Kl, gdzie l jest literałem. Zdefiniujemy teraz diagramy SP-logiki domniemań.

Definicja 5 Niech T = ⟨A, D⟩ będzie normalną SP-teorią domniemań nad językiem L. Diagram teorii T konstruuje się jak w definicji 1, gdzie punkty 4, 5 i 6 są zastąpione przez

4. Niech A będzie niezależnym agentem reprezentującym domniemanie d, którego konsekwencja zawiera symbol relacyjny R. Niech R_{1}, …, R_{n} będą wszystkimi symbolami relacyjnymi występującymi w warunku wstępnym d i niech R′_{1}, … R′_{l} będą tymi spośród R_{1},…, R_{k}, które nie są poprzedzone operatorem K. Dla każdego 1 ≤ i ≤ k tworzymy strzałkę do A z każdego agenta bazodanowego reprezentującego R_{i} i dla każdego 1 ≤ i ≤ l tworzymy strzałke z każdego modułu (lub niezależnego default-agenta) reprezentującego R′_{i} oraz bazodanowego agenta reprezentującego R.

5. Niech M będzie modułem reprezentującym relację R, a A_{1}, …, A_{n} default-agentami z M, gdzie A_{i} odpowiada domniemaniu d_{i}. Niech R_{1},…, R_{k} będą wszystkimi symbolami relacyjnymi występującymi w warunkach wstępnych d_{1}, …, d_{n} i niech R′_{1}, … R′_{l} będą tymi spośród R_{1},…, R_{k}, które nie są poprzedzone operatorem K. Prowadzimy strzałkę do M z agenta bazodanowego reprezentującego R_{i} dla każdego 1 ≤ i ≤ k i strzałkę z modułu reprezentujacego R′_{i} dla każdego 1 ≤ i ≤ l oraz z agenta bazodanowego reprezentującego R.

6. Przypisanie metod default-agentom. Niech agent reprezentuje domniemanie postaci B_{1}∧⋯∧B_{n} : l/l, gdzie n ≥ 0, a R_{1}, …, R_{n}, R są odpowiadającymi im symbolami relacji. Niech B′_{1}, …, B′_{k} są tymi czynnikami spośród B_{1} ∧⋯∧B_{n}, które nie są poprzedzone przez K a R′_{1}, …, R′_{k} są symbolami relacji występującymi w B′_{1}, …, B′_{k}. Generujemy dwie metody bazodanowe, mianowicie A_{k}.R^{+} i A_{k}.R^{−}, gdzie A_{k} jest agentem bazodanowym odpowiedzialnym za relację R, i umieszczamy je, odpowiednio, w pozytywnej i negatywnej części diagramu. Następnie generujemy default-metodę, którą umieszcza się w pozytywnej części, jeśli l jest literałem pozytywnym, a w negatywnej w przeciwnym przypadku. Konstrukcja metod przebiega w sposób następujący:

(a) Załóżmy najpierw, że żadna z R′_{1}, …, R′_{k} nie jest reprezentowana przez default-moduł ani przez niezależnego default-agenta. Default-metoda jest postaci

A_{1}.X_{1} ∧ ⋯ ∧ A_{n}.X_{n} ∧ A.X, (5)

gdzie A_{1}, …, A_{n}, A są agentami bazodanowymi odpowiedzialnymi za R_{1}, …, R_{n}, R, odpowiednio, X_{i} jest R_{i}^{+} (jeśli l_{i} jest pozytywny) lub R_{i}^{−} (jeśli l_{i} jest negatywny) a X jest ¬R^{−} (jeśli l jest pozytywny) lub ¬R^{+} (jeśli l jest negatywny).

(b) Załóżmy teraz, że przynajmniej jedna z R′_{1}, …, R′_{k} jest reprezentowana przez default-moduł lub przez niezależnego default-agenta. Niech R′_{i}, … R′_{j} będą wszystkimi relacjami spośród R_{1}, …, R_{n}, które są reprezentowane przez default-moduł lub przez niezależnego defaultagenta, a M_{i}, …, M_{j} są odpowiadającymi im modułami. Metoda jest postaci (5) gdzie A_{i}, …, A_{j} są zastąpione odpowiednio przez M_{i}, …, M_{j}.

Jak poprzednio, z powyższego diagramu generujemy zbiór reguł (CAKE program) stosując standardową metodologię CAKE’a. W przypadku konfliktów stosuje się standardowy mechanizm głosowania (voting), więc nie włącza się tych granulek do default-modułów.

Twierdzenie 2 Zbiór reguł normalnej SP-teorii domniemań, gdzie wszystkie warunki wstępne są mocne jest stratyfikowalny.

Przykład 7 John jest osobą. Na ogół ludzie są uczciwi. Na ogół, osobie, o której wierzymy, że jest uczciwa, można bezpiecznie pożyczyć niewielka kwotę pieniądzy. Na ogół, osobie, o której wiadomo, że jest uczciwa, można bezpiecznie pożyczyć dużą kwotę pieniądzy.

Teoria domniemań reprezentująca te zdania: A = {P (j)}

D = \{\frac{P (x) : H(x)}{H(x)} , \frac{H(x) : SM(x)}{SM(x)} , \frac{KH(x) : LM(x)}{LM(x)} \} .

i jej diagram

[figure: j; A_{1} : P (x); A_{2} : H(x); A_{5} : H(x); A_{6}: SM(x); A_{1}.P^{+} ∧ A_{2}.H^{⊕}; A_{3}: SM(x); A_{5}.H^{+} ∧ A_{3}.SM^{⊕}; A_{3}.SM^{+}; A_{2}.H^{−}; A_{3}.SM^{−}; A_{7}: LM(x); A_{2}.H^{+} ∧ A_{4}.LM^{⊕}; A_{4}.LM^{−}; A_{2}.H^{+}; A_{4}: LM(x); A_{4}.LM^{+}; +; +; +; +; +; +; +; −; −; −; −; −; −; −]

32

Reguły:

A_{1}.P^{+} (j) A_{2}.H^{−}(x) → A_{5}.H^{−}(x) [A_{2}.H^{+} (x) ∨ [A_{1}.P^{+} (x) ∧ ¬A_{2}.H^{−}(x)]] → A_{5}.H^{+} (x) A_{3}.SM^{−}(x) → A_{6}.SM^{−}(x) [A_{3}.SM^{+} (x) ∨ [A_{5}.H^{+} (x) ∧ ¬A_{3}.SM^{−}(x)]] → A_{6}.SM^{+} (x) A_{4}.LM^{−}(x) → A_{7}.LM^{−}(x) [A_{4}.LM^{+} (x) ∨ [A_{2}.H^{+} (x) ∧ ¬A_{4}.LM^{−}(x)]] → A_{7}.LM^{+} (x).

i obliczenia:

{} {A_{1}.P^{+} (j)} {A_{1}.P^{+} (j), A_{5}.H^{+} (j)} {A_{1}.P^{+} (j), A_{5}.P^{+} (j), A_{6}.SM^{+} (j)}.

SM(j) należy do rozszerzenia teorii T, a LM(j) nie.

Semi-normalne teorie logiki domniemań

Domniemanie nazywamy semi-normalnym, jeśli jest postaci

\frac{l_{1} ∧ ⋯ ∧ l_{n} : l′_{1} ∧ ⋯ ∧ l′_{k} ∧ l}{l}

gdzie l_{1}, …, l_{n}, l′_{1}, …, l′_{k}, l są literałami. Przykład 8 Rozważmy T = ⟨A, D⟩, gdzie

A = \{D(b)\} and D = \{\frac{D(x) : A(x)}{A(x)} , \frac{A(x) : ¬D(x) ∧ E(x)}{E(x)} \} .

która ma diagram

[figure: A_{1} : A(x); b; A_{2} : D(x); A_{2}.D^{+} ∧ A_{1}.A^{⊕}; A_{4} : A(x); A_{4}.A^{+} ∧ A_{2}.D^{⊖} ∧ A_{3}.E^{⊕}; A_{1}.A^{−}; A_{3}.E^{+}; A_{1}.A^{+}; A_{3} : E(x); A_{3}.E^{−}; A_{5} : E(x); +; +; +; +; +; −; −; −; −; −]

35

W przypadku domniemań semi-normalnych musimy jeszcze uwzględnić dodatkowe czynniki występujące w uzasadnieniu. W rozważanym przykładzie metoda domniemania odwołuje się do relacji D.

Reguły dla tego przykładu

A_{2}.D^{+} (b) A_{1}.A^{−}(x) → A_{4}.A^{−}(x) {A_{1}.A^{+} (x) ∨ [A_{2}.D^{+} (x) ∧ ¬A_{1}.A^{−}(x)]} → A_{4}.A^{+} (x)

A_{3}.E^{−}(x) → A_{5}.E^{−}(x) {A_{3}.E^{+} (x) ∨ [A_{4}.A^{+} (x) ∧ ¬A_{2}.D^{+} (x) ∧ ¬A_{3}.E^{−}(x)]} → A_{5}.E^{+} (x).

i obliczenia

{} {A_{2}.D^{+} (b)} {A_{2}.D^{+} (b), A_{4}.A^{+} (b)}.

Jeśli interesuje nas czy E(b), to widać, że ani A_{5}.E^{+} (b), ani A_{5}.E^{−}(b) nie należy do punktu stałego, więc odpowiedź jest Unknown .

Konstrukcja diagramu jest analogiczna jak w przypadku teorii normalnych. Należy jedynie uwzględnić odwołania do dodatkowych czynników w uzasadnieniu.

Niestratyfikowalne teorie domniemań

Jeśli teoria domniemań nie jest stratyfikowalna, do obliczenia rozszerzenia stosujemy semantykę well-founded. Postępujemy w sposób następujący:

1. zbiór reguł teorii jest CAKE programem Π_{T}.

2. liczymy well-founded model S _{∗}^{∗} programu Π_{T}.

3. na podstawie otrzymanego modelu wyznaczamy rozszerzenie.

Definicja 6 Niech T będzie teorią domniemań, a Π_{T} CAKE programem teorii T. Ukonkretniony (ground) literał postaci P (c̄) (odpowiednio ¬P (c̄)) jest wf-wyprowadzalny z T wtedy i tylko wtedy, gdy X.P^{+} (c̄) (odpowiednio X.P^{−}(c̄)), gdzie X jest nazwą agenta bazodanowego, niezależnego default-agenta lub default-modułu, należy do well-founded modelu S _{∗}^{∗} programu Π_{T}.

Definicja 7 Niech T będzie teorią domniemań. Wf-rozszerzeniem T jest zbiór ukonkretnionych literałów wyprowadzalnych z T.

Wracamy do przykładu 4. Wf-model dla tego przykładu jest

{ N.Q^{+} (n), A_{3}.Q^{+} (n), A_{7}.Q^{+} (n), A_{8}.Q^{+} (n), ¬N.Q^{−}(n), ¬A_{3}Q^{−}(n), ¬A_{7}.Q^{−}(n), ¬A_{8}.Q^{−}(n), M.P^{+} (n), A_{6}.P^{+} (n), ¬M.P^{−}(n), ¬A_{2}.P^{−}(n), ¬A_{2}.P^{+} (n), ¬A_{5}.P^{−}(n), ¬A_{5}.P^{+} (n), ¬A_{6}.P^{−}(n), ¬A_{1}.R^{+} (n), ¬A_{4}.S^{+} (n) }.

Tak więc, teoria T ma wf-rozszerzenie

E = {P (n), Q(n)}.

Twierdzenie 3 Niech T będzie stratyfikowalną teorią domniemań. E jest rozszerzeniem teorii T wtedy i tylko wtedy, gdy jest wf-rozszerzeniem T.

Twierdzenie 4 Obliczenie rozszerzenia teorii T jest wielomianowe względem liczby reguł CAKE programu tej teorii.