2 examples that violate the monotonicity property of logic (and thus are non-monotonic):

• semantic networks we saw that property inherited by all members of a category in a semantic network could be overridden by more specific information for a subcategory

•  in closed-world assumption:

•   if a proposition α is not mentioned in KB then: 
  KB ⊨ ¬α

• but when α is mentioned then: 
  KB ∧ α ⊨ α

failures of monotonicity are widespread in commonsense reasoning

2 types of non-monotonic logics:

•  circumscription

•  default logic

Circumscription

a more powerful and precise version of the closed world assumption

circumscription can be viewed as an example of a model preference logic. In such logics, a sentence is entailed (with default status) if it is true in all preferred models of the KB, as opposed to the requirement of truth in all models in classical logic. For circumscription, one model is preferred to another if it has fewer abnormal objects

for example, to assert the default rule that birds fly, we introduce a predicate Abnormal1(x) and write

Bird(x) ʌ ¬Abnormal1(x) ⇒ Flies(x)  or in prolog syntax flies(X) :- bird(X), not abnormal(X).

if we say that Abnormal1 is to be circumscribed, a circumscriptive reasoner is entitled to assume ¬Abnormal1(x) unless Abnormal1(x) is known to be true. This allows the conclusion Flies(Tweety) to be drawn from the premise Bird(Tweety), but the conclusion no longer holds if Abnormal1(Tweety) is asserted

Let us see how this idea works in the context of multiple inheritance in semantic networks. The standard example for which multiple inheritance is problematic is called the “Nixon diamond.” It arises from the observation that Richard Nixon was both a Quaker (and hence by default a pacifist) and a Republican (and hence by default not a pacifist). We can write this as follows:

Republican(Nixon) ∧ Quaker(Nixon)Republican(x) ∧ ¬Abnormal2(x) ⇒ ¬Pacifist(x) Quaker(x) ∧ ¬Abnormal3(x) ⇒ Pacifist(x)

If we circumscribe Abnormal2 and Abnormal3, there are two preferred models: one in which Abnormal2(Nixon) and Pacifist(Nixon) hold and one in which Abnormal3(Nixon) and ¬Pacifist(Nixon) hold. Thus, the circumscriptive reasoner remains properly agnostic as to whether Nixon was a pacifist. If we wish, in addition, to assert that religious beliefs take precedence over political beliefs, we can use a formalism called prioritized circumscription to give preference to models where Abnormal3 is minimized.

Default Logic

default logic is a formalism in which default rules can be written to generate contingent, nonmonotonic conclusions

a default rule looks like this:

Bird(x) : Flies(x) / Flies(x)

this rules means that if Bird(x) is true, and if Flies(x) is consistent (causing no contradiction) with knowledge base, then Flies(x) may be concluded by default. 

default rule has the form:

P: J₁, …, J_n / C

where:

§  P is called the prerequisite

§  C is the conclusion

§  J_i are the justifications (if any one of them is proven false, then conclusion cannot be drawn). 

Any variable that appears in J_i and C must also appear in P

the Nixon-diamond example can be represented in default logic with 1 fact and 2 default rules:

Republican(Nixon) ∧ Quaker(Nixon)           # fact
Republican(x) : ¬Pacifist(x) / ¬Pacifist(x)   # default rule
Quaker(x) : Pacifist(x) / Pacifist(x)              # default rule