Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
COMP4418: Knowledge Representation and Reasoning
Nonmonotonic Reasoning
Maurice Pagnucco
School of Computer Science and Engineering The University of New South Wales Sydney, NSW, 2052
Thursday 1 October, 2020
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Nonmonotonic Reasoning
Suppose you are told “Tweety is a bird” What conclusions would you draw?
Now, consider being further informed that “Tweety is an emu”
What conclusions would you draw now? Do they differ from the conclusions that you would draw without this information? In what way(s)?
Nonmonotonic reasoning is an attempt to capture a form of commonsense reasoning
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
1 Nonmonotonicity
2 Closed World Assumption
3 Predicate Completion
4 Circumscription
5 Default Logic
6 Nonmonotonic Consequence KLM Systems
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Nonmonotonic Reasoning
In classical logic the more facts (premises) we have, the more conclusions we can draw
This property is known as Monotonicity
If ∆ ⊆ Γ, then Cn(∆) ⊆ Cn(Γ)
(where Cn denotes classical consequence)
However, the previous example shows that we often do not
reason in this manner
Might a nonmonotonic logic—one that does not satisfy the Monotonicity property—provide a more effective way of reasoning?
Maurice Pagnucco UNSW COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Why Nonmonotonicity?
Problems with the classical approach to consequence
It is usually not possible to write down all we would like to
say about a domain
Inferences in classical logic simply make implicit knowledge explicit; we would also like to reason with tentative statements
Sometimes we would like to represent knowledge about something that is not entirely true or false; uncertain knowledge
Nonmonotonic reasoning is concerned with getting around these shortcomings
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Makinson’s Classification
Makinson has suggested the following classification of nonmonotonic logics:
Additional background assumptions Restricting the set of valuations Additional rules
David Makinson, Bridges from Classical to Nonmonotonic Logic, Texts in Computing, Volume 5, King’s College Publications, 2005.
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Nonmonotonicity
Classical logic satisfies the following property Monotonicity: If ∆ ⊆ Γ, then Cn(∆) ⊆ Cn(Γ)
(equivalently, Γ ⊢ φ implies Γ ∪ ∆ ⊢ φ)
However, we often draw conclusions based on ‘what is
normally the case’ or ‘true by default’
More information can lead us to retract previous conclusions
We shall adopt the following notation
⊢ classical consequence relation
|∼ nonmonotonic consequence relation
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Consequence Operation Cn
Other properties of consequence operation Cn: Inclusion ∆ ⊆ Cn(∆)
Cumulative Transitivity ∆ ⊆ Γ ⊆ Cn(∆) implies Cn(Γ) ⊆ Cn(∆) Compactness If φ ∈ Cn(∆) then there is a finite ∆′ ⊆ ∆ such
that φ ∈ Cn(∆′) Disjunction in the Premises
Cn(∆ ∪ {a}) ∩ Cn(∆ ∪ {b}) ⊆ Cn(∆ ∪ {a ∨ b})
Note: ∆⊢φiffφ∈Cn(∆) alternatively: Cn(∆) = {φ : ∆ ⊢ φ}
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Example
Suppose I tell you ‘Tweety is a bird’ You might conclude ‘Tweety flies’
I then tell you ‘Tweety is an emu’ You conclude ‘Tweety does not fly’
bird(Tweety) |∼flies(Tweety)
bird(Tweety) ∧ emu(Tweety) |∼ ¬flies(Tweety)
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
The Closed World Assumption
A complete theory is one in which for every ground atom in the language, either the atom or its negation appears in the theory
The closed world assumption (CWA) completes a base (non-closed) set of formulae by including the negation of a ground atom whenever the atom does not follow from the base
In other words, if we have no evidence as to the truth of (ground atom) P, we assume that it is false
Given a base set of formulae ∆ we first calculate the assumption set
¬P ∈∆asm iffforgroundatomP, ∆̸⊢P CWA(∆) = Cn{∆ ∪ ∆asm}
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Example
∆ = {P(a),P(b),P(a)→Q(a)}
∆asm = {¬Q(b)}
Theorem: The CWA applied to a consistent set of formulae ∆ is inconsistent iff there are positive ground literals L1, . . . , Ln suchthat∆|=L1 ∨…∨Ln but∆̸|=Li fori =1, …, n.
Note that in the example above we limited our attention to the object constants that appeared in ∆ however the language could contain other constants. This is known as the Domain Closure Assumption (DCA)
Another common assumption is the Unique-Names Assumption (UNA).
If two ground terms can’t be proved equal, assume that they are not.
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Predicate Completion
Idea: The only objects that satisfy a predicate are those that must
For example, suppose we have P(a). Can view this as ∀x. x = a → P(x)
the if-half of a definition Can add the only if part:
∀x. P(x) → x = a
Giving:
∀x. P(x) ↔ x = a
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Predicate Completion
Definition: A clause is solitary in a predicate P if whenever the clause contains a postive instance of P, it contains only one instance of P.
For example, Q(a) ∨ P(a) ∨ ¬P(b) is not solitary in P Q(a) ∨ R(a) ∨ P(b) is solitary in P
Completion of a predicate is only defined for sets of clauses solitary in that predicate
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Predicate Completion
Each clause can be written:
∀y.Q1 ∧…∧Qm →P(t)(P notcontainedinQi) ∀y.∀x.(x=t)∧Q1∧…∧Qm →P(x)
∀x.(∀y.(x =t)∧Q1 ∧…∧Qm →P(x))(normalformof clause)
Doing this to every clause gives us a set of clauses of the form:
∀x. E1 → P(x)
…
∀x. En → P(x)
Grouping these together we get:
∀x.E1∨…∨En →P(x)
Completion becomes: ∀x. P(x) ↔ E1 ∨ . . . ∨ En
and we can add this to the original set of formulae
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Example
Suppose ∆ = {∀x. Emu(x) → Bird(x), Bird (Tweety ),
¬Emu(Tweety )} We can write this as
∀x. (Emu(x) ∨ x = Tweety) → Bird(x)
Predicate completion of P in ∆ becomes
∆ ∪ {∀x. Bird(x) → Emu(x) ∨ x = Tweety}
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Circumscription
Idea: Make extension of predicate as small as possible
Example:
∀x.Bird(x) ∧ ¬Ab(x) → Flies(x)
Bird (Tweety ), Bird (Sam), Tweety ̸= Sam, ¬Flies(Sam)
Want to be able to conclude Flies(Tweety) but ¬Flies(Sam)
Accept interpretations where Ab predicate is as “small” as possible
That is, we minimise abnormality
Maurice Pagnucco UNSW
COMP4418: Knowledge Representation and Reasoning
Outline Nonmonotonicity Closed World Assumption Predicate Completion Circumscription Default Logic Nonmonotonic Cons
Circumscription
Given interpretations I1 = ⟨D, I1⟩, I2 = ⟨D, I2⟩, I1 ≤ I2 iff for every predicate P ∈ P, I1[P] ⊆ I2[P].
Γ |=circ φ iff for every interpretation I such that I |= Γ, either I|=φorthereisaI′