Introduction to Non Monotonic
Reasoning
Master Recherche SIS, Marseille
Nicola Olivetti
Professeur `a la Facult´e Econonomie Appliqu´ee, Universit´e Paul Cezanne
Laboratoire CNRS LSIS
2010-2011a
a
I am indebted to Laura Giordano and Alberto Martelli for having provided me their course material.
Introduction to Non Monotonic Reasoning – p. 1/36
Non-monotonic reasoning
Often available knowledge is incomplete.
However, to model commonsense reasoning, it is
necessary to be able to jump to plausible conclusions
from the given knowledge.
To draw plausible conclusions it is necessary to make
assumptions.
The choice of assumptions is not blind: most of the
knowledge on the world is given by means of general
rules which specify typical properties of objects. For
instance, "birds fly" means: birds typically fly, but there
can be exceptions such as penguins, ostriches, ...
Introduction to Non Monotonic Reasoning – p. 2/36
Non-monotonic reasoning
Nonmonotonic reasoning deals with the problem of
deriving plausible conclusions, but not infallible, from a
knowledge base (a set of formulas).
Since the conclusions are not certain, it must be
possible to retract some of them if new information
shows that they are wrong
Classical logic is inadequate since it is monotonic: if a
formula B is derivable from a set of formulas S, then B
is also derivable from any superset of S:
S ⊢ B implies S ∪ {A} ⊢ B, for any formula A.
Introduction to Non Monotonic Reasoning – p. 3/36
Non-monotonic reasoning
Example: let the KB contain:
Typically birds fly.
Penguins do not fly.
Tweety is a bird.
It is plausible to conclude that Tweety flies.
However if the following information is added to KB
Tweety is a penguin
the previous conclusion must be retracted and, instead,
the new conclusion that Tweety does not fly will hold.
Introduction to Non Monotonic Reasoning – p. 4/36
Non-monotonic reasoning
The statement "typically A" can be read as: "in the
absence of information to the contrary, assume A".
The problem is to define the precise meaning of "in the
absence of information to the contrary".
The meaning could be: "there is nothing in KB that is
inconsistent with assumption A".
Other interpretations are possible
Different interpretations give rise to different
non-monotonic logics
Introduction to Non Monotonic Reasoning – p. 5/36
Inadequacy of Classical Logic
We cannot represent a rule such as "typically birds fly"
as
∀x(bird(x) ∧ ¬exception(x) → fly(x))
and then to add
∀x(exception(x) ↔ penguin(x)∨ostrich(x)∨canary(x)∨. . .)
We do not know in advance all exceptions
In order to conclude that "Tweety"’ fly we should prove
that "‘tweety is not an exception"’, that is:
¬penguin(tweety), ¬ostrich(tweety), . . .
Introduction to Non Monotonic Reasoning – p. 6/36
Inadequacy of Classical Logic
On the contrary we would like to prove that Tweety flies
because we cannot conclude that it is an exception, not
because we can prove that it is not an exception.
Introduction to Non Monotonic Reasoning – p. 7/36
Closed World Assumption
A basic understanding of database logic, is that only
positive information is represented explicitly. Negative
information is not represented explicitly.
If a positive fact is not present in the database (DB), it is
assumed that its negation holds.
This is called Closed World Assumption: the only true
facts are the provable ones.
If DB ⊢ A then DB ⊢CWA ¬A
This inference is not valid in classical logic.
Introduction to Non Monotonic Reasoning – p. 8/36
Closed World Assumption
Example: suppose a DB contains facts of the form
"practice(person, sport)"’, for instance:
practice(anne, tennis)
practice(joe, tennis)
practice(anne, sky)
Then we have
DB ⊢CWA ¬practice(joe, sky)
Trivially CWA is non-monotonic, since adding a fact may
lead to withdraw the negative conclusion:
DB ∪ {practice(joe, sky)} ⊢CWA ¬practice(joe, sky)
Introduction to Non Monotonic Reasoning – p. 9/36
Frame Problem
Problem of representing a dynamic world
How to represent that objects are not affected by state
change?
Example: moving an object does not change its color
In a representation based on a classical-logic , we must
explicitly assert the persistence of object properties.
We need a great number of frame axioms, such as:
∀x∀c∀s∀l(color(x, c, s) → color(x, c, result(move, x, l, s)))
∀x∀c∀s(color(x, c, s) → color(x, c, result(t_light_on, s)))
∀x∀c∀s(color(x, c, s) → color(x, c, result(open_door, s)))
...
Introduction to Non Monotonic Reasoning – p. 10/36
Frame Problem
We would need a general meta-axiom of the form:
∀p∀a∀s(holds(p, s)∧¬exception(p, a, s) → holds(p, result(a, s)))
But then we must be able to conclude that an action is
not an exception to the preservation of a given property,
unless we can show that it actually is.
We need a non-monotonic reasoning mechanism.
Introduction to Non Monotonic Reasoning – p. 11/36
NonMonotonic Logics
Non-Monotonic logics have been proposed at the beginning
of the 80’s, here are historically the most important
proposals:
Non-monotonic logic, by McDermott and Doyle, ’80
Default Logic, by Reiter, ’80
Circumscription, by McCarthy, ’80
Autoepistemic logic, Moore ’84
Introduction to Non Monotonic Reasoning – p. 12/36
Default Logic
Default logic extends classical logic by non-standard
inference rules. These rules allows one to express
default properties.
Example:
bird(x) : fly(x)
fly(x)
that can be interpreted as: "‘if x is a bird and we can
consistently assume that x flies then we can infer that x
flies"’
Introduction to Non Monotonic Reasoning – p. 13/36
Default Logic
More generally we can have rules of the form:
α(x) : β(x)
γ(x)
that can be interpreted as: "‘if α(x) holds and β(x) can
be consistently assumed then we can conclude γ(x)".
terminology:
α(x): the prerequisite
β(x): the justification
γ(x): the consequent
Introduction to Non Monotonic Reasoning – p. 14/36
Default Theory
A default theory is a pair < D, W >, where D is a set of
default rules and W is a set of first-order formulas.
Example: let let < D, W > be
D = {
bird(x) : fly(x)
fly(x)
}
W = {bird(tweety), ∀x(penguin(x) → bird(x)),
∀x(penguin(x) → ¬fly(x))}
Introduction to Non Monotonic Reasoning – p. 15/36
Default Theory
Intuitively, in a default theory < D, W >:
W represents the stable (but incomplete) knowledge of
the world
D rules for extending the knowledge W by plausible
(but defeasible) conclusions.
Notion of extension of a default theory: the theory (=
deductively closed set of logical formulas) obtained by
extending W by the rules in D.
Introduction to Non Monotonic Reasoning – p. 16/36
Default Theory
Example: let < D, W > be as in the previous example
Since bird(tweety) is true, and it is consistent to assume
fly(tweety), then fly(tweety) is true in the (unique)
extension of < D, W >.
Consider now the the default theory < D, W′ >, where
W′
= W ∪ {penguin(tweety)}
then the assumption fly(tweety) is no longer consistent,
and the application of the default rule is blocked.
Introduction to Non Monotonic Reasoning – p. 17/36
Default Theory
Example2: let < D, W > be as follows:
D = {d1 =
Rep(x) : ¬Pac(x)
¬Pac(x)
, d2 =
Quack(x) : Pac(x)
Pac(x)
, }
W = {Rep(Nixon), Quack(Nixon)}
For both default rules di, the prerequisite is derivable
from W. What can be concluded from < D, W >?
If we apply d1, we conclude ¬Pac(Nixon); therefore
Pac(Nixon) cannot be assumed consistently, so that d2
is blocked.
If we apply d2, we conclude Pac(Nixon); therefore
¬Pac(Nixon) cannot be assumed consistently, so that
d1 is blocked.
Introduction to Non Monotonic Reasoning – p. 18/36
Default Theory
There are two extensions: one containing ¬Pac(Nixon)
and the other containing Pac(Nixon).
An extension (to be defined next) represents the set of
plausible conclusions.
As we shall see, a default-theory may have zero, one,
or many extensions.
Introduction to Non Monotonic Reasoning – p. 19/36
Extensions (propositional case)
Given a default theory ∆ =< D, W >, a set of formulas E is
an extension of ∆, if:
E is deductively closed: E = Th(E)
all applicable defaults with respect to E have been
applied, that is for all α : β
γ ∈ D
if α ∈ E and ¬β ∈ E then γ ∈ E
Deductive closure operator: Th(S) = {C ∈ L | S ⊢ C}
Introduction to Non Monotonic Reasoning – p. 20/36
Extensions: semi-inductive definition
Given a default theory ∆ =< D, W >, a set of formulas E is
an extension of ∆, if it can be obtained as follows:
S0 = W
Si+1 = Th(Si) ∪ {γ |
α : β
γ ∈ D, α ∈ Si, ¬β ∈ E}
E = i Si
Introduction to Non Monotonic Reasoning – p. 21/36
Extensions: semi-inductive definition
The definition is not really inductive, since the definition
of Si+1 makes reference to the whole E.
The order in which defaults are considered in step Si+1
is significant: different orders give rise to different
extensions.
In the propositional case every extension can be
"generated" in at most k stages where k is the number
of defaults in the default theory.
Introduction to Non Monotonic Reasoning – p. 22/36
Extensions
Example 1: let ∆ = {b, p → ¬f}, {
b : f
f
}, then there is a
unique extension E = Th({b, p → ¬f, f})
S0 = {b, p → ¬f}
S1 = S0 ∪ {f}, since S0 ⊢ b and ¬f ∈ E
Introduction to Non Monotonic Reasoning – p. 23/36
Extensions
Example 1’: let ∆ = {b, p → ¬f, p}, {
b : f
f
}, then there is a
unique extension E = Th({b, p → ¬f, p})
S0 = {b, p → ¬f, p}
S1 = S0, since S0 ⊢ b but ¬f ∈ E
Introduction to Non Monotonic Reasoning – p. 24/36
Extensions
Example 2: let ∆ = {r, q}, {d1 =
r : ¬p
¬p , d2 =
q : p
p }.
Let E1 = Th({r, q, ¬p})
S0 = {r, q}
S1 = S0 ∪ {¬p}, by applying d1, since S0 ⊢ r and
¬¬p ∈ E1
S2 = S1, since d2 cannot be applied ¬p ∈ E1
for i ≥ 2, Si = S2
Introduction to Non Monotonic Reasoning – p. 25/36
Extensions
Example 2 (continued)
Let E2 = Th({r, q, p})
S0 = {r, q}
S1 = S0 ∪ {p}, by applying d2, since S0 ⊢ q and
¬p ∈ E2
S2 = S1, since d1 cannot be applied: ¬¬p ∈ E2
for i ≥ 2, Si = S2
Introduction to Non Monotonic Reasoning – p. 26/36
Extensions
Example 3 Let ∆ =< W, D >, where W = ∅ and D = { : a
¬a}.
Suppose there is an extension E
if ¬a ∈ E, then it must be ¬a ∈ E (we must apply the
default)
but if ¬a ∈ E, the default become inapplicable: thus it
must be ¬a ∈ E
∆ has no extensions!
Introduction to Non Monotonic Reasoning – p. 27/36
Extensions
Example 4 Let ∆ =< W, D >, where W = ∅ and
D = {d1 =
: ¬p
q , d2 =
: ¬q
p }.
Let E1 = Th({q})
S0 = ∅
S1 = S ∪ {q}, , since ¬¬p ∈ E.
S2 = S1, since d2 becomes inapplicable.
Similarly, we get another extension E2 = Th({p})
Introduction to Non Monotonic Reasoning – p. 28/36
Extensions
Example 4 Let ∆ =< W, D >, where W = ∅ and
D = {a : b
b
, b : a
a }. Then there is a unique extension
E = Th(∅)
S0 = ∅
S1 = S0, since S0 ⊢ a, and S0 ⊢ b
Introduction to Non Monotonic Reasoning – p. 29/36
Normal defaults
A default d is normal if has the form α : β
β
A normal default theory ∆ =< W, D > is a default theory
where all defaults in D are normal
Theorem: A normal default theory has always an
extension.
Introduction to Non Monotonic Reasoning – p. 30/36
Inference relation
Since a default theory ∆ =< W, D > may have multiple
extensions (including none), how to define a notion of
inference? There are two natural notions:
(credulous inference) ∆ ⊢c A if there exists an
extension E of ∆ such that A ∈ E.
(skeptical inference) ∆ ⊢s A if for all extensions E of
∆, we have A ∈ E.
Since a default theory may have no extensions ∆ ⊢s A
does not imply ∆ ⊢c A.
Introduction to Non Monotonic Reasoning – p. 31/36
A simple algorithm
An algorithm to compute any extension of a theory
∆ =< W, D >
(0) Let < S0, D0 >=< W, ∅ >.
(i+1) Let < X, Y, Z >=< Si, ∅, D − Di >
for every d ∈ Z, d =
αd : βd
γd
if Si ∪ X ⊢ αd and Si ∪ X ⊢ ¬βd
then < X, Y >=< X ∪ {γd}, Y ∪ {d} >
let < Si+1, Di+1 >=< Si ∪ X, Di ∪ Y >
stop with the least k such that
< Sk, Dk >=< Sk+1, Dk+1 >
check whether for each d =
αd : βd
γd
∈ Dk, Sk ⊢ ¬βd.
If "yes", return Sk.
Introduction to Non Monotonic Reasoning – p. 32/36
Problems with default logic
Unwanted transitivity: let ∆ =< W, D >, where
W = {student} and
D = {d1 =
student : adult
adult
, d2 =
adult : works
works
}
it is easy to see that ∆ has a unique extension including
{student, works, adult}.
it is rather unintuitive (as students usually do not work).
if we add the default student : ¬work
¬work
, the theory has
then two extensions:
E1 = {student, adult, works}
E2 = {student, adult, ¬works}
But E2 is more plausible than E1
Introduction to Non Monotonic Reasoning – p. 33/36
Problems with default logic
Solution: replace d2 by:
adult : works ∧ ¬student
works
then the only extension is E2 = {student, adult, ¬works}
this default is not normal
it is semi-normal: the justification implies the
consequent
a semi-normal default theory (= a theory where all
default are semi-normal) may have no extensions
Introduction to Non Monotonic Reasoning – p. 34/36
Problems with default logic
Handling specificity: let ∆ =< W, D >, where
W = {user, blacklisted} and
D = {d1 =
user : login
login
, d2 =
user ∧ blacklisted : ¬login
¬login
}
the theory has then two extensions:
E1 = {user, blacklisted, login}
E2 = {user, blacklisted, ¬login}
But of course only E2 is the intended one.
Introduction to Non Monotonic Reasoning – p. 35/36
Problems with default logic
The problem of specificity can be handled by assigning
a priority to defaults on the base of their specificity. The
priority order is taken into account for calculating
extensions.
Reiter’s Default logic has also other problems (e.g.
cumulativity)
Many variants have been proposed, such as Brewka’s
one and Lukaszewicz’s one.
Introduction to Non Monotonic Reasoning – p. 36/36