Journal of Logic and Computation, Volume 11, Issue 2, pp. 229-256: Abstract.
Nonmonotonic Logics and Semantics
School of Engineering and Computer Science, Hebrew University Jerusalem, 91904 Israel. E-mail: email@example.com
Tarski gave a general semantics for deductive reasoning: a formula [alpha] may be deduced from a set A of formulas iff [alpha] holds in all models in which each of the elements of A holds. A more liberal semantics has been considered: a formula [alpha] may be deduced from a set A of formulas iff [alpha] holds in all of the preferred models in which all the elements of A hold. Shoham proposed that the notion of preferred models be defined by a partial ordering on the models of the underlying language. A more general semantics is described in this paper, based on a set of natural properties of choice functions. This semantics is here shown to be equivalent to a semantics based on comparing the relative importance of sets of models, by what amounts to a qualitative probability measure. The consequence operations defined by the equivalent semantics are then characterized by a weakening of Tarski's properties in which the monotonicity requirement is replaced by three weaker conditions. Classical propositional connectives are characterized by natural introduction-elimination rules in a nonmonotonic setting. Even in the nonmonotonic setting, one obtains classical propositional logic, thus showing that monotonicity is not required to justify classical propositional connectives.
Keywords: Nonmonotonic logics, nonmonotonic reasoning, choice functions, qualitative probability measures