Default logic (Reiter)

Default:

\frac{Bird(x): F lies(x)}{F lies(x)}

Default theory: Axioms + defaults Definition A default is any expression of the form

\frac{A(x) : B_{1}(x), …, B_{k}(x)}{C(x)}

where A(x), B_{1}(x), …, B_{k}(x) and C(x) are first-order formulas whose free variables are among those of x = (x_{1}, …, x_{n}).

A(x) – the prerequisite; B_{1}(x), …, B_{k}(x) – the justifications; C(x) – the consequent.

Definition A default theory is a pair T = ⟨W,D⟩, where W is a set of first-order sentences and D is a set of defaults.

A set of theorems derivable from a default theory T is called an extension of T.

An extension should include whatever can be inferred from axioms either by ordinary logic or by applying defaults.

If E is an extension of T = ⟨W,D⟩, then:

(1) E should be deductively closed with respect to standard logic: E=Th(E);

(2) E should contain axioms: W⊆E;

(3) E should contain a maximal set of conclusions obtainable by applying defaults from D.

Note:

(1)-(3) imply that an extension of a theory ⟨W,D⟩ is always given by Th(X∪W), where X is a set of conclusions obtainable by applying defaults from D.

Example

W={(1) Basket − P layer(Bill)}; D=\{\frac{Basket−P layer(x): T all(x)}{T all(x)} ,

\frac{Basket−P layer(x): Nimble(x)}{Nimble(x)} \}. E=Th({(1) , T all(Bill), Nimble(Bill)}).

Let T obtain by adding

(2) ¬T all(Bill) ∨ ¬Nimble(Bill).

E1=Th((1),(2),T all(Bill)); E2=Th((1),(2),Nimble(Bill)).

Definition A default A(x):B_{1}(x), …, B_{k}(x)/C(x) is called open iff at least one of A(x), B_{1}(x), …, B_{k}(x), C(x) contains a free variable; otherwise it is called closed. A default theory is said to be open iff it contains at least one open default; otherwise it is said to be closed.

Closed default theories

The following conditions can be naturally imposed on an extension E of a theory ⟨W,D ⟩:

(1) E=Th(E);

(2) W⊆E;

(3) E should contain a maximal set of conclusions obtainable by applying defaults from D.

Notice:

Any conclusion derivable by applying a closed default is just its consequent.

(3’) E should contain the consequent of any applicable default from D.

There still remains the problem of specifying a formal criterion of default’s applicability.

\frac{A : B_{1}, …, B_{k}}{C}

(3”) If (A : B_{1}, …, B_{k}/C) ∈ D, A ∈ E and ¬B_{1} ∉ E, …, ¬B_{k} ∉ E, then C ∈ E.

Closure conditions:

(1) E=Th(E);

(2) W⊆E; (3”) If (A : B_{1}, …, B_{k}/C) ∈ D, A ∈ E and

¬B_{1} ∉ E, …, ¬B_{k} ∉ E, then C ∈ E.

Closure conditions specify what should be in an extension. However, they say nothing about what should be off.

“Definition” E is an extension of a closed default theory iff E is the smallest set satisfying the closure conditions.

“Definition” E is an extension of a closed default theory iff E is a minimal set satisfying the closure conditions.

T = ⟨{P (a)}, {P (a) : Q(a)/Q(a)}⟩ Both Th({P (a), Q(a)}) and Th({P (a), ¬Q(a)}) satisfy the closure conditions.

Problem: Assume that E and Γ(E) denote the same extension of ⟨W,D⟩. How to define Γ(E) by means of E?

Solution: Let Γ(E) be the smallest set satisfying:

(1) Γ(E)=Th(Γ(E));

(2) W⊆ Γ(E);

(3) If (A : B_{1}, …, B_{k}/C) ∈ D, A∈Γ(E) and ¬B_{1} ∉ E, …, ¬B_{k} ∉ E, then C ∈ Γ(E).

Definition Let T = ⟨W,D⟩ be a closed default theory over L_{T}. For any set of sentences S⊆ L_{T}, let Γ(S) be the smallest set of sentences from L_{T} satisfying:

(1) Γ(S)=Th(Γ(S));

(2) W⊆ Γ(S);

(3) If (A : B_{1}, …, B_{k}/C) ∈ D, A∈Γ(S) and ¬B_{1} ∉ S, …, ¬B_{k} ∉ S, then C ∈ Γ(S).

A set of sentences E⊆ L_{T} is an extension of T iff E=Γ(E).

Example Reconsider: T = ⟨{P (a)}, {P (a) : Q(a)/Q(a)}⟩. T gives rise to two minimal sets satisfying the closure conditions: E1=Th({P (a), Q(a)}) and E2=Th({P (a), ¬Q(a)}).

Since Γ(E1)=Th({P (a), Q(a)})=E1 Γ(E2)=Th({P (a)})≠ E2 only E1 is an extension of T.

Example Let T be a theory with the empty set of axioms and one default

\frac{:p}{¬p}.

T has no extension. To show it, note that the only candidates are

E1=Th({¬p}) and E2=Th({}).

Since

Γ(E1)=Th({})≠E1
Γ(E2)=Th({¬p})≠E2

neither E1 nor E2 is an extension of T.

Open defaults and their instances

An instance of an open default is the result of uniformly replacing all free occurrences of its variables by ground terms.

\frac{Bird(cousin(Bob)): F lies(cousin(Bob))}{F lies(cousin(Bob))}

\frac{Bird(x): F lies(x)}{F lies(x)}

T ⟶ CLOSED(T)

Example Let T consist of:

Bird(T weety) ∧ F ish(Nelly)

\frac{Bird(x):Has−W ings(x)}{Has−W ings(x)} .

CLOSED(T):

Bird(T weety) ∧ F ish(Nelly)

\frac{Bird(T weety):Has−W ings(T weety)}{Has−W ings(T weety)}

\frac{Bird(Nelly):Has−W ings(Nelly)}{Has−W ings(Nelly)} .

Example Let T consist of: F ish(Bob) ∀x.F ish(x) ⊃ F ish(father(x)) \frac{F ish(x):Swims(x)}{Swims(x)} .

CLOSED(T):

F ish(Bob) ∀x.F ish(x) ⊃ F ish(father(x))

\frac{F ish(Bob):Swims(Bob)}{Swims(Bob)}

\frac{F ish(father(Bob)):Swims(father(Bob))}{Swims(father(Bob))}

etc.

Example Let T consist of:

∃x.Butterfly(x)

\frac{Butterfly(x):Brightly−Coloured(x)}{Brightly−Coloured(x)} . We would like to infer ∃x.Butterfly(x) ∧ Brightly − Coloured(x). CLOSED(T):

Butterfly(a)

\frac{Butterfly(a):Brightly−Coloured(a)}{Brightly−Coloured(a)} .

Example Let T consist of:

Birthday(Bill)

\frac{:∃x.F riend(x,Bill)}{∃x.F riend(x,Bill)}

\frac{Birthday(y)∧F riend(x,y):Gives−Gift(x,y)}{Gives−Gift(x,y)}

The first default is replaced by

\frac{:∃x.F riend(x,Bill)}{F riend(b,Bill)}

and then we proceed in the usual way.

Definition A Skolemized form of a sentence A is any universal sentence obtained from any prenex normal form of A by the process of Skolemization.

Definition A Skolemized form of a default

\frac{A(x) : B_{1}(x), …, B_{k}(x)}{C(x)}

obtains by replacing C(x) by any Skolemized form of ∀C(x) and deleting all quantifiers from the consequent of the resulting default.

Definition A Skolemized form of a default theory T is any theory obtained by replacing defaults and axioms of T by their Skolemized forms.

Definition Let T = ⟨W,D ⟩ be a default theory. By TERMS(T) we denote the set of all ground terms constructable using function constants occurring in W and D.

Definition Let T be a default theory. A closure of T, written CLOSED(T), is any theory obtained by the following construction:

1. If T is closed, then put CLOSED(T)=T. Otherwise:

2. Replace T by its Skolemized form, T 1.

3. Let T 2 be the theory obtained from T 1 by replacing all its open defaults by their instances over TERMS(T 1). This is the desired closure of T.

Definition Let T be a default theory over L_{T}. E is an extension of T iff E=E’∩L_{T} and E’ is an extension of CLOSED(T).

Theorem If T = ⟨W,D⟩ is a closed default theory, then a set E of sentences is an extension of T iff E=⋃_{i=0}^{∞} E_{i}, where

E_{0}=W, and for i≥ 0

E_{i+1} =Th(E_{i}) ∪ {C : (A : B_{1}, …, B_{k}/C) ∈ D,

where E_{i} ⊢ A and ¬B_{1}, …, ¬B_{k} ∉ E}.

Corollary A closed default theory ⟨W,D⟩ has an inconsistent extension iff W is inconsistent.

Theorem If E and F are extensions of a closed default theory and E⊆F, then E=F.

Normal default theories

Definition Any default of the form

\frac{A(x):B(x)}{B(x)}

is said to be normal. A theory ⟨W,D⟩ is said to be normal iff every default from D is normal.

Theorem Every closed normal default theory has an extension.

Theorem If a closed normal default theory has distinct extensions E and F, then E∪F is inconsistent.

Example Consider:

W=\{\} D = \{\frac{:p}{¬r}, \frac{:r}{¬p}\}.

T has two extensions:

E=Th({¬r}) and F=Th({¬p}).

Although E∪F is consistent, ¬p and ¬r should not be regarded as coexisting beliefs.

Theorem (Semi-Monotonicity) Let D and D’ be sets of closed normal defaults such that D’⊆D. Let E’ be an extension of T ’=⟨W,D’⟩ and suppose that T =⟨W,D⟩. Then T has an extension E such that E’⊆E.

What the above theorem says is that any belief derivable from a closed normal theory T cannot be invalidated by augmenting T by a new set of closed normal defaults.

Representational Issues

To what extend normal defaults are sufficient for the purpose of practical applications?

Bill is a high school dropout.

Typically, high school dropouts are adults.

Typically, adults are employed.

W={Dropout(Bill)} D=\{\frac{Dropout(x):Adult(x)}{Adult(x)} ,

\frac{Adult(x):Employed(x)}{Employed(x)} \}.

This theory forces us to believe that Bill is employed.

\frac{Adult(x):Employed(x)∧¬Dropout(x)}{Employed(x)}

Bill is a 21-year-old. All 21-year-olds are adults. Typically, adults are married.

21 − Y ear − Old(Bill) ∀x.21 − Y ear − Old(x) ⊃ Adult(x) \frac{Adult(x):Married(x)}{Married(x)} .

This theory forces the conclusion that Bill is married.

\frac{Adult(x):Married(x)∧¬21−Y ear−Old(x)}{Married(x)}

The general situation: We are given a rule which in isolation is naturally represented by a normal default

\frac{A(x):B(x)}{B(x)} .

When the rule is embedded in the context, there are some exceptional circumstances, say E(x), which make the rule inapplicable. The simplest solution is to replace the normal default by

\frac{A(x):B(x)∧¬E(x)}{B(x)} .

Definition Any default of the form

\frac{A(x):B(x)∧C(x)}{B(x)}

is called semi-normal. A default theory is semi-normal iff all of its defaults are semi-normal. Note that a normal default A : B/B can be identified with the semi-normal default A : B ∧ T rue/B.

Semi-normal default theories may lack extensions:

Let T = ⟨{},D⟩, where D consists of

d1=\frac{:p∧¬q}{¬q}, d2=\frac{:q∧¬r}{¬r}
d3=\frac{:r∧¬p}{¬p}.

In general, semi-normal theories lack the property of semimonotonicity:

Let T = ⟨{},: p ∧ q/q⟩. T has one extension:

E=Th({q}).

Adding : ¬p/¬p to T, we arrive in a theory with one extension given by

F=Th({¬p}).

(1) Are semi-normal theories sufficient to cover all naturally occurring practical applications?

(2) To what extend can the effects obtainable by using seminormal defaults be achieved in the framework of normal representation?

Translation schema

(1) Replace any default of the form

d=\frac{A(x):B(x)}{C(x)}

by the semi-normal default

d1=\frac{A(x):B(x)∧C(x)}{C(x)} .

This step seems to be intuitively sound what leads to the following observation: Any common-sense setting which can be correctly modeled by using single-justification defaults may be expressed by means of semi-normal defaults.

Important: A default and its translation need not be equivalent. Consider d=: p/¬p and its translation d1=: p ∧ ¬p/¬p. While the theory ⟨{}, {d}⟩ lacks an extension, the theory ⟨{}, {d1}⟩ has an extension given by Th({}).

(2) Replace the semi-normal default

d1=\frac{A(x):B(x)∧C(x)}{C(x)}

by the normal default

d1=\frac{A(x):B(x)∧C(x)}{B(x)∧C(x)} .

This works if we accept: “Typically, if A(x) and C(x), then B(x).

\frac{Adult(x):Married(x)∧¬21−Y ear−Old(x)}{Married(x)}

\frac{Adult(x):Married(x)∧¬21−Y ear−Old(x)}{Married(x)∧¬21−Y ear−Old(x)}

Here is an example where the schema does not work.

\frac{Has−Motive(x):Guilty(x)}{Suspect(x)}

\frac{Has−Motive(x):Guilty(x)∧Suspect(x)}{Suspect(x)}

\frac{Has−Motive(x):Guilty(x)∧Suspect(x)}{Guilty(x)∧Suspect(x)}

Advanced topics on default logic, ( not discussed here)

• Semantic characterization of extensions (Łukaszewicz 1985, Etherington 1987).

• Proof theory for DL (Reiter 1980).

• Connections between DL and AEL (Konolige 1988, Marek & Truszczyński 1989).

• Alternative formulations of default logic:

– Łukaszewicz 1984.

– Brewka 1991.

Conclusions

Advantages of DL:

Conceptual clarity. Weaknesses of DL:

(1) Lack of natural semantics.

(2) Some theories lack extensions.

(3) DL cannot deal with reasoning by cases. For instance, given W=\{bird ∨ rocket\} D=\{\frac{bird:flies}{flies}, \frac{rocket:flies}{flies} \}

we intuitively feel that flies should be derivable. Unfortunately, it is not.