Nonmonotonic Entailment

next up previous
Next: Definitions Up: Semantics Previous: Indexical Entailment

Nonmonotonic Entailment

Recall that the truth value of a sentence is defined relative to an interpretation and a variable assignment . To define the nonmonotonic value of a premise in a rule, we need to select, instead of a single interpretation , a set of interpretations - the interpretations that are considered ``possible''. In the following definition, is a set of interpretations which all have the same universe of discourse , and is a variable assignment with this universe. We consider prerequisites and justifications separately.

The nonmonotonic value of a prerequisite is if and only if it is true at every ``possible'' intepretation.

The nonmonotonic value of a justification is true if and only if its argument is true for at least one ``possible'' intepretation.


be a knowledge base with rules. We define when a set

of interpretations is ``a set of possible worlds'' for

, by means of the following fixpoint construction. Consider a universe of discourse

; by a world we understand an interpretation with the universe

. Let

be the set of all worlds that satisfy the sentences in

. Consider a maximal set

of worlds such that, for each rule

and each variable assignment

with the universe

, the following condition holds. If the nonmonotonic value of every prerequisite of




, and the nonmonotonic value of every justification of



is true, then the nonmonotonic value of the consequent of




. (This

always exists.) If

is maximal, then we say that

is a set of possible worlds for

. Typically, a knowledge base with rules has many sets of possible worlds; it is clear, for instance, that any two interpretations with different universes cannot belong to the same set of possible worlds.

An interpretation

is a nonmonotonic model of

if it belongs to some set of possible worlds for

. We say that a nonmonotonic knowledge base

nonmonotonically entails a sentence

if and only every nonmonotonic model of

is also a model of


Note that the definition of a model for nonmonotonic knowledge bases is ``nonlocal'' - we cannot check whether an interpretation

is a model by looking at each rule in isolation. This feature of the definition is responsible for the nonmonotonic character in this notion of entailment.

next up previous
Next: Definitions Up: Semantics Previous: Indexical Entailment

Vishal I. Sikka
Wed Dec 7 13:23:42 PST 1994