Nonmonotonic logics and semantics

Abstract: Tarski gave a general semantics for deductive reasoning: a formula a may be deduced from a set A of formulas iff a holds in all models in which each of the elements of A holds. A more liberal semantics has been considered: a formula a may be deduced from a set A of formulas iff a 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.

Review text

Tarski's general semantics for logical deduction is well known: a formula ``\(a\) is deduced from a set of formulas \(A\) iff ``\(a\) holds in ``all the models such that all the formulas of \(A\) hold. In Tarski's semantic framework, the consequence operators satisfy inclusion, idempotence and monotony properties. NEWLINENEWLINENEWLINEIn this work, Daniel Lehmann considers two different semantics generalizing Tarski's one. NEWLINENEWLINENEWLINEThe first one involves a choice function on the set of models. The choice function is inspired by a function used in research in Social Choice. This function allows to consider not all the models of a set of formulas, but a subset of them (the more relevant models). The choice function satisfies ``natural properties. NEWLINENEWLINENEWLINEThe second semantics considered by the author is based on comparing the ``importance (qualitative measure) of the set of models by defining a strict partial order relation that satisfies certain properties. NEWLINENEWLINENEWLINEBoth of them are presented as ``natural semantics. NEWLINENEWLINENEWLINEEven when these semantics are different, it is proved that they are equivalent (under a simplifying assumption). NEWLINENEWLINENEWLINEIn this semantic framework, the consequence operations satisfy inclusion and idempotency properties. They are nonmonotonic; the usual monotony property is replaced by three properties of weak monotony. NEWLINENEWLINENEWLINEMoreover, an additional requirement on the choice function (a laziness property) is equivalent to a new property of the quality measure and it ensures a new property of weak monotony of the consequence operations. NEWLINENEWLINENEWLINEFinally, the classical propositional connectives are characterized by using properties of the nonmonotonic deduction operations. That is, it is shown that the nonmonotonic logic of the classical connectives is the classical propositional logic.

Recommendations

Cited in

(25)

This page was built for publication: Nonmonotonic logics and semantics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2720313)