View
7
Download
1
Category
Preview:
Citation preview
Université Paris 5 – René DescartesLIPADE
Non-Monotonic ReasoningIntroduction
Jean-Guy Mailly (jean-guy.mailly@parisdescartes.fr)
2017
1
Administration
I Jean-Guy Mailly : jean-guy.mailly@parisdescartes.fr– Bureau 814 I
I 30h de cours/TD : lundi, 12h15–15h00I Modalités de contrôle de connaissances :
I Un contrôle (' mi-semestre)I Un examen (fin de semestre)I Note finale : max(EX , EX+CC
2 )
I Moodle : Cours Raisonnement Non Monotonehttps:
//moodle.parisdescartes.fr/course/view.php?id=6631
J.-G. Mailly | Intro to NMR
2
Aims
Non-Monotonic ReasoningReasoning with information which is: contradictory, uncertain,imprecise, revisable, with exceptions. . .
Common sense reasoning
Hot research topicI Mainly since the 80sI A lot of publications in major AI conferences (IJCAI, ECAI, AAAI,
KR,. . . )I Dedicated workshop on even years: International Workshop on
Non-Monotonic Reasoning
J.-G. Mailly | Intro to NMR
3
Plan
I Introduction to NMR - Background KnowledgeI Non-monotonic inference relations
I Maximal consistent subsetsI Closed World AssumptionI Default logic
I Introduction to Belief change (BC)I Belief RevisionI Links between inference and BC
J.-G. Mailly | Intro to NMR
4
Outline
Introduction to NMR
Background on Propositional Logic
Short Introduction to First Order Logic
J.-G. Mailly | Intro to NMR
5
Introduction to NMRThe usual example
Does Tweety fly?I Tweety is a bird
(b)
I Birds fly
(b → f )
I Tweety is a penguin
(p)
I Penguins don’t fly
(p → ¬f )
Propositional logicK = {b,b → f ,p,p → ¬f}
K ` fK ` ¬f
K is inconsistent: we can deduce anything from K (e.g. K ` ¬b)
J.-G. Mailly | Intro to NMR
5
Introduction to NMRThe usual example
Does Tweety fly?I Tweety is a bird (b)I Birds fly (b → f )I Tweety is a penguin (p)I Penguins don’t fly (p → ¬f )
Propositional logicK = {b,b → f ,p,p → ¬f}
K ` fK ` ¬f
K is inconsistent: we can deduce anything from K (e.g. K ` ¬b)
J.-G. Mailly | Intro to NMR
5
Introduction to NMRThe usual example
Does Tweety fly?I Tweety is a bird (b)I Birds fly (b → f )I Tweety is a penguin (p)I Penguins don’t fly (p → ¬f )
Propositional logicK = {b,b → f ,p,p → ¬f}K ` f
K ` ¬f
K is inconsistent: we can deduce anything from K (e.g. K ` ¬b)
J.-G. Mailly | Intro to NMR
5
Introduction to NMRThe usual example
Does Tweety fly?I Tweety is a bird (b)I Birds fly (b → f )I Tweety is a penguin (p)I Penguins don’t fly (p → ¬f )
Propositional logicK = {b,b → f ,p,p → ¬f}K ` fK ` ¬f
K is inconsistent: we can deduce anything from K (e.g. K ` ¬b)
J.-G. Mailly | Intro to NMR
5
Introduction to NMRThe usual example
Does Tweety fly?I Tweety is a bird (b)I Birds fly (b → f )I Tweety is a penguin (p)I Penguins don’t fly (p → ¬f )
Propositional logicK = {b,b → f ,p,p → ¬f}K ` fK ` ¬f
K is inconsistent: we can deduce anything from K (e.g. K ` ¬b)
J.-G. Mailly | Intro to NMR
6
Monotonicity
IntuitivelyA formalism is monotonic if we can’t lose consequences when weadd new information
Formally∀K a set of formulas and ∀α, β formulas, if
K ` α
thenK ∪ {β} ` α
I This property is satisfied by classical logicI Not suitable for common sense reasoning
J.-G. Mailly | Intro to NMR
6
Monotonicity
IntuitivelyA formalism is monotonic if we can’t lose consequences when weadd new information
Formally∀K a set of formulas and ∀α, β formulas, if
K ` α
thenK ∪ {β} ` α
I This property is satisfied by classical logicI Not suitable for common sense reasoning
J.-G. Mailly | Intro to NMR
7
Solutions
I Define new formalisms which don’t satisfy monotonicity
I Non-monotonic inference relations
I Not « just » add the new piece of information when it bringsinconsistency
I Belief Change
J.-G. Mailly | Intro to NMR
7
Solutions
I Define new formalisms which don’t satisfy monotonicityI Non-monotonic inference relations
I Not « just » add the new piece of information when it bringsinconsistency
I Belief Change
J.-G. Mailly | Intro to NMR
8
Outline
Introduction to NMR
Background on Propositional Logic
Short Introduction to First Order Logic
J.-G. Mailly | Intro to NMR
9
Syntax of Propositional Logic
I Boolean variables V = {x1, . . . , xn}I can receive the value 0 (false, F, ⊥) or 1 (true, T, >)I set of connectives, usually {¬,∨,∧}
A (well-formed) formula:I ϕ = xi , for xi ∈ V , is a formula; it is called an atomI if ϕ is a formula, then ¬ϕ is a formula; it is called the negation ofϕ
I if ϕ and ψ are formulas, then ϕ ∧ ψ is a formula; it is called theconjunction of ϕ and ψ
I if ϕ and ψ are formulas, then ϕ ∨ ψ is a formula; it is called thedisjunction of ϕ and ψ
J.-G. Mailly | Intro to NMR
10
Semantics of Propositional Logic
Interpretation: mapping ω from formulas to {0,1}. An interpretationsatisfies a formula ϕ if:
I ϕ = xi , and ω(xi) = 1I ϕ = ¬ϕ′, and ω(ϕ′) = 0I ϕ = ϕ′ ∧ ϕ′′, and ω(ϕ′) = ω(ϕ′′) = 1I ϕ = ϕ′ ∨ ϕ′′, and ω(ϕ′) = 1 or ω(ϕ′′) = 1
When ω(ϕ) = 1, ω is a model of ϕ, denoted ω |= ϕ
I Alternative notations: Set of atoms {xi ∈ V | ω(xi) = 1}Vector of bits ω(x1), ω(x2), . . . , ω(xn)
I Set of models of ϕ: mod(ϕ)I ϕ′ is a consequence of ϕ if mod(ϕ) ⊆ mod(ϕ′): ϕ ` ϕ′
I ϕ′ is equivalent to ϕ if mod(ϕ) = mod(ϕ′): ϕ ≡ ϕ′
I A formula ϕ is called consistent when mod(ϕ) 6= ∅
J.-G. Mailly | Intro to NMR
10
Semantics of Propositional Logic
Interpretation: mapping ω from formulas to {0,1}. An interpretationsatisfies a formula ϕ if:
I ϕ = xi , and ω(xi) = 1I ϕ = ¬ϕ′, and ω(ϕ′) = 0I ϕ = ϕ′ ∧ ϕ′′, and ω(ϕ′) = ω(ϕ′′) = 1I ϕ = ϕ′ ∨ ϕ′′, and ω(ϕ′) = 1 or ω(ϕ′′) = 1
When ω(ϕ) = 1, ω is a model of ϕ, denoted ω |= ϕ
I Alternative notations: Set of atoms {xi ∈ V | ω(xi) = 1}Vector of bits ω(x1), ω(x2), . . . , ω(xn)
I Set of models of ϕ: mod(ϕ)I ϕ′ is a consequence of ϕ if mod(ϕ) ⊆ mod(ϕ′): ϕ ` ϕ′
I ϕ′ is equivalent to ϕ if mod(ϕ) = mod(ϕ′): ϕ ≡ ϕ′
I A formula ϕ is called consistent when mod(ϕ) 6= ∅
J.-G. Mailly | Intro to NMR
11
Additional Connectives
I Implication: ϕ→ ϕ′ ≡ ¬ϕ ∨ ϕ′
I Equivalence: ϕ↔ ϕ′ ≡ (ϕ→ ϕ′) ∧ (ϕ′ → ϕ)
I Exclusive or: ϕ⊕ ϕ′ ≡ (ϕ ∧ ¬ϕ′) ∨ (¬ϕ ∧ ϕ′)
J.-G. Mailly | Intro to NMR
12
Truth Tables
To determine the models of a formula:I Split it into simpler formulasI Apply the semantics of the connectives on these simpler
formulasE.g. ϕ = (a ∨ b) ∧ (¬a ∨ c)
a b c a ∨ b ¬a ∨ c ϕ0 0 0 0 1 00 0 1 0 1 00 1 0 1 1 10 1 1 1 1 11 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1
J.-G. Mailly | Intro to NMR
13
Inference Rules
Modus Ponensϕ,ϕ→ ψ
ψ: If ϕ is true and ϕ→ ψ is true, then we deduce ψ
Modus Tollens¬ψ,ϕ→ ψ¬ϕ : If ψ is false and ϕ→ ψ is true, then we deduce ¬ϕ
RefutationProving that ϕ ` ψ is equivalent to prove that ϕ ∧ ¬ψ ` ⊥
J.-G. Mailly | Intro to NMR
14
Models of Conjunction/Disjunction
Computing models of a complex formula ϕ can be simplified bysplitting ϕ in sub-formulas:
I if ϕ = ϕ1 ∧ ϕ2, then mod(ϕ) = mod(ϕ1) ∩mod(ϕ2)
I if ϕ = ϕ1 ∨ ϕ2, then mod(ϕ) = mod(ϕ1) ∪mod(ϕ2)
J.-G. Mailly | Intro to NMR
15
Distributivity of Connectives
Disjunction and conjunction can be distributed/factorized:I ϕ ∧ (ψ1 ∨ ψ2) ≡ (ϕ ∧ ψ1) ∨ (ϕ ∧ ψ2)
I ϕ ∨ (ψ1 ∧ ψ2) ≡ (ϕ ∨ ψ1) ∧ (ϕ ∨ ψ2)
J.-G. Mailly | Intro to NMR
16
De Morgan’s Laws
I ¬(ϕ1 ∨ ϕ2) ≡ ¬ϕ1 ∧ ¬ϕ2
I ¬(ϕ1 ∧ ϕ2) ≡ ¬ϕ1 ∨ ¬ϕ2
J.-G. Mailly | Intro to NMR
17
Normal Forms
I A literal is an atom x ∈ V or its negation ¬x , with x ∈ VI A clause is a disjunction of literals l1 ∨ · · · ∨ lnI A cube (or term) is a conjunction of literals l1 ∧ · · · ∧ ln
Disjunctive Normal Form (DNF)A formula ϕ is in DNF if it is a disjunction of cubes
Conjunctive Normal Form (CNF)A formula ϕ is in CNF if it is a conjunction of clauses
TheoremAny propositional formula can be rewritten into an equivalent DNF orCNF formula
J.-G. Mailly | Intro to NMR
18
Outline
Introduction to NMR
Background on Propositional Logic
Short Introduction to First Order Logic
J.-G. Mailly | Intro to NMR
19
Syntax of First Order Logic (1/3)
In Propositional Logic, there is a single kind of “data”: propositions,represented as Boolean variables. First Order Logic generalizes PL:
I P: infinite set of predicatesI F : infinite set of functionsI V : infinite set of variables (any kind of variables, not Boolean)I The usual set of connectives: {¬,∧,∨} (and also→,⇔,⊕, . . . )I Quantifiers : ∀,∃
J.-G. Mailly | Intro to NMR
20
Syntax of First Order Logic (2/3)
PredicateA predicate p is a mapping from a list of variables x1, . . . , xn to {0,1}.When all the variables are instanciated, p(x1, . . . , xn) is “equivalent” to aproposition from PL.
I n = 0, p is a propositionI n = 1, p(x) gives a property of x (e.g. prime(x))I n = 2, p(x , y) defines a binary relation (e.g. smallerThan(x , y))
FunctionA function f is a mapping from a list of variables x1, . . . , xn to aconstant.
I n = 0, f is a constantI n = 1, (e.g. square(x) = x2)I n = 2, (e.g. sum(x , y) = x + y )
J.-G. Mailly | Intro to NMR
20
Syntax of First Order Logic (2/3)
PredicateA predicate p is a mapping from a list of variables x1, . . . , xn to {0,1}.When all the variables are instanciated, p(x1, . . . , xn) is “equivalent” to aproposition from PL.
I n = 0, p is a propositionI n = 1, p(x) gives a property of x (e.g. prime(x))I n = 2, p(x , y) defines a binary relation (e.g. smallerThan(x , y))
FunctionA function f is a mapping from a list of variables x1, . . . , xn to aconstant.
I n = 0, f is a constantI n = 1, (e.g. square(x) = x2)I n = 2, (e.g. sum(x , y) = x + y )
J.-G. Mailly | Intro to NMR
21
Syntax of First Order Logic (3/3)
TermI Any variable is a termI For any terms t1, . . . , tn, and f a n-ary function, f (t1, . . . , tn) is a
term (in particular, constants are terms)
FormulasI For any terms t1, . . . , tn, and p a n-ary predicate, p(t1, . . . , tn) is a
formulaI Connectives: usual rules (negation, conjunction, disjunction)I If ϕ is a formula and x ∈ V , then ∀x , ϕ and ∃x , ϕ are formulas
J.-G. Mailly | Intro to NMR
21
Syntax of First Order Logic (3/3)
TermI Any variable is a termI For any terms t1, . . . , tn, and f a n-ary function, f (t1, . . . , tn) is a
term (in particular, constants are terms)
FormulasI For any terms t1, . . . , tn, and p a n-ary predicate, p(t1, . . . , tn) is a
formulaI Connectives: usual rules (negation, conjunction, disjunction)I If ϕ is a formula and x ∈ V , then ∀x , ϕ and ∃x , ϕ are formulas
J.-G. Mailly | Intro to NMR
22
ExampleSocrates
Socrates is a man. All men are mortals.Can we deduce that Socrates is mortal?
In PLs, s → man,man→ mortal
In FOLman(s) ∧ (∀x ,man(x)→ mortal(x))
J.-G. Mailly | Intro to NMR
22
ExampleSocrates
Socrates is a man. All men are mortals.Can we deduce that Socrates is mortal?
In PLs, s → man,man→ mortal
In FOLman(s) ∧ (∀x ,man(x)→ mortal(x))
J.-G. Mailly | Intro to NMR
23
ExampleDistances
Given a set V , a mapping d on V is a distance iff
(∀x ,equals(d(x , x),0)) ∧ (∀x , y ,equals(d(x , y),d(y , x)))∧(∀x , y , z,greaterOrEquals(add(d(x , y),d(y , z)),d(x , z)))
J.-G. Mailly | Intro to NMR
24
Semantics of FOL (1)
Interpretation In FOLω = (D, ωc , ωv ) with
I D = {d1, . . . ,dn} is the non-empty domainI ωc is defined as
I ωc(f ) maps f (d1, . . . , dm) to an element of DI ωc(P) maps P(d1, . . . , dm) to an element of {0, 1}
I ωv maps variables x to an element of D
J.-G. Mailly | Intro to NMR
25
Semantics of FOL (2)
Truth Value In FOLI If x is a free variable (non quantified), then ω(x) = ωv (x)
I ω(f (t1, . . . , tn)) = (ωc(f ))(ω(t1), . . . , ω(tn))I ω(P(t1, . . . , tn)) = (ωc(P))(ω(t1), . . . , ω(tn))I If ϕ,ψ are formulas, then ¬ϕ,ϕ ∧ ψ,ϕ ∨ ψ are interpreted like in
PLI If ϕ is a formula, then ω(∀x , ϕ) = 1 iff ωx←d (ϕ) = 1 for all d ∈ DI If ϕ is a formula, then ω(∃x , ϕ) = 1 iff ωx←d (ϕ) = 1 for at least
one d ∈ D
J.-G. Mailly | Intro to NMR
25
Semantics of FOL (2)
Truth Value In FOLI If x is a free variable (non quantified), then ω(x) = ωv (x)I ω(f (t1, . . . , tn)) = (ωc(f ))(ω(t1), . . . , ω(tn))
I ω(P(t1, . . . , tn)) = (ωc(P))(ω(t1), . . . , ω(tn))I If ϕ,ψ are formulas, then ¬ϕ,ϕ ∧ ψ,ϕ ∨ ψ are interpreted like in
PLI If ϕ is a formula, then ω(∀x , ϕ) = 1 iff ωx←d (ϕ) = 1 for all d ∈ DI If ϕ is a formula, then ω(∃x , ϕ) = 1 iff ωx←d (ϕ) = 1 for at least
one d ∈ D
J.-G. Mailly | Intro to NMR
25
Semantics of FOL (2)
Truth Value In FOLI If x is a free variable (non quantified), then ω(x) = ωv (x)I ω(f (t1, . . . , tn)) = (ωc(f ))(ω(t1), . . . , ω(tn))I ω(P(t1, . . . , tn)) = (ωc(P))(ω(t1), . . . , ω(tn))
I If ϕ,ψ are formulas, then ¬ϕ,ϕ ∧ ψ,ϕ ∨ ψ are interpreted like inPL
I If ϕ is a formula, then ω(∀x , ϕ) = 1 iff ωx←d (ϕ) = 1 for all d ∈ DI If ϕ is a formula, then ω(∃x , ϕ) = 1 iff ωx←d (ϕ) = 1 for at least
one d ∈ D
J.-G. Mailly | Intro to NMR
25
Semantics of FOL (2)
Truth Value In FOLI If x is a free variable (non quantified), then ω(x) = ωv (x)I ω(f (t1, . . . , tn)) = (ωc(f ))(ω(t1), . . . , ω(tn))I ω(P(t1, . . . , tn)) = (ωc(P))(ω(t1), . . . , ω(tn))I If ϕ,ψ are formulas, then ¬ϕ,ϕ ∧ ψ,ϕ ∨ ψ are interpreted like in
PL
I If ϕ is a formula, then ω(∀x , ϕ) = 1 iff ωx←d (ϕ) = 1 for all d ∈ DI If ϕ is a formula, then ω(∃x , ϕ) = 1 iff ωx←d (ϕ) = 1 for at least
one d ∈ D
J.-G. Mailly | Intro to NMR
25
Semantics of FOL (2)
Truth Value In FOLI If x is a free variable (non quantified), then ω(x) = ωv (x)I ω(f (t1, . . . , tn)) = (ωc(f ))(ω(t1), . . . , ω(tn))I ω(P(t1, . . . , tn)) = (ωc(P))(ω(t1), . . . , ω(tn))I If ϕ,ψ are formulas, then ¬ϕ,ϕ ∧ ψ,ϕ ∨ ψ are interpreted like in
PLI If ϕ is a formula, then ω(∀x , ϕ) = 1 iff ωx←d (ϕ) = 1 for all d ∈ D
I If ϕ is a formula, then ω(∃x , ϕ) = 1 iff ωx←d (ϕ) = 1 for at leastone d ∈ D
J.-G. Mailly | Intro to NMR
25
Semantics of FOL (2)
Truth Value In FOLI If x is a free variable (non quantified), then ω(x) = ωv (x)I ω(f (t1, . . . , tn)) = (ωc(f ))(ω(t1), . . . , ω(tn))I ω(P(t1, . . . , tn)) = (ωc(P))(ω(t1), . . . , ω(tn))I If ϕ,ψ are formulas, then ¬ϕ,ϕ ∧ ψ,ϕ ∨ ψ are interpreted like in
PLI If ϕ is a formula, then ω(∀x , ϕ) = 1 iff ωx←d (ϕ) = 1 for all d ∈ DI If ϕ is a formula, then ω(∃x , ϕ) = 1 iff ωx←d (ϕ) = 1 for at least
one d ∈ D
J.-G. Mailly | Intro to NMR
26
ExampleSocrates
Socrates is a man. All men are mortals.Can we deduce that Socrates is mortal?
In FOLman(s) ∧ (∀x ,man(x)→ mortal(x))
I D = {Socrates,Plato,MickeyMouse}I ωv (s) = SocratesI ωc(man) = fman s.t. fman(x) = 1 iff x ∈ {Socrates,Plato}I ωc(mortal) = fmortal s.t. fmortal(x) = 1
J.-G. Mailly | Intro to NMR
27
ExampleDistances
In FOL
(∀x ,equals(d(x , x),0)) ∧ (∀x , y ,equals(d(x , y),d(y , x)))∧(∀x , y , z,greaterOrEquals(add(d(x , y),d(y , z)),d(x , z)))
I D = R+ = {x ∈ R | x ≥ 0}I ωv : no free variables so nothing to doI ωc(equals) = f= s.t. f=(x , y) = 1 iff x = yI ωc(greaterOrEquals) = f≥ s.t. f≥(x , y) = 1 iff x ≥ yI ωc(add) = f+ s.t. f+(x , y) = x + yI ωc(d) = fd
What is fd?I fd can be any mapping from x , y to a positive real numberI if for a given fd , the formula is true, then d is a distance
J.-G. Mailly | Intro to NMR
27
ExampleDistances
In FOL
(∀x ,equals(d(x , x),0)) ∧ (∀x , y ,equals(d(x , y),d(y , x)))∧(∀x , y , z,greaterOrEquals(add(d(x , y),d(y , z)),d(x , z)))
I D = R+ = {x ∈ R | x ≥ 0}I ωv : no free variables so nothing to doI ωc(equals) = f= s.t. f=(x , y) = 1 iff x = yI ωc(greaterOrEquals) = f≥ s.t. f≥(x , y) = 1 iff x ≥ yI ωc(add) = f+ s.t. f+(x , y) = x + yI ωc(d) = fd
What is fd?
I fd can be any mapping from x , y to a positive real numberI if for a given fd , the formula is true, then d is a distance
J.-G. Mailly | Intro to NMR
27
ExampleDistances
In FOL
(∀x ,equals(d(x , x),0)) ∧ (∀x , y ,equals(d(x , y),d(y , x)))∧(∀x , y , z,greaterOrEquals(add(d(x , y),d(y , z)),d(x , z)))
I D = R+ = {x ∈ R | x ≥ 0}I ωv : no free variables so nothing to doI ωc(equals) = f= s.t. f=(x , y) = 1 iff x = yI ωc(greaterOrEquals) = f≥ s.t. f≥(x , y) = 1 iff x ≥ yI ωc(add) = f+ s.t. f+(x , y) = x + yI ωc(d) = fd
What is fd?I fd can be any mapping from x , y to a positive real numberI if for a given fd , the formula is true, then d is a distance
J.-G. Mailly | Intro to NMR
Recommended