ECAI-2000 Logo

ECAI-2000 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Equivalent Sets of Formulas for Circumscriptions

Yves Moinard, Raymond Rolland

Circumscription is a way of using classical logic in order to modelize rules with exceptions and implicit knowledge. Formula circumscription is easier to use in order to modelize a given situation. We describe when two sets of formulas give the same result when circumscribed, introducing two kinds of equivalence. For ordinary equivalence, the two sets give the same circumscription, and for the strong equivalence, when completed by any arbitrary set, the two sets give the same circumscription. The strong equivalence corresponds simply to having the same closure for logical ``and'' and ``or''. For the ordinary equivalence, there exists also always a greatest set. Our answer to these two equivalence problems for the case of propositional formula circumscription is exhaustive. This gives rise to various notions of formulas positive with respect to a given set of formulas. When starting from ordinary propositional circumscription, things remain simple enough, and we provide a syntactical description of all these equivalent sets, even in the infinite case.

Keywords: Nonmonotonic reasoning, Knowledge representation, Automatic reasoning

Citation: Yves Moinard, Raymond Rolland: Equivalent Sets of Formulas for Circumscriptions. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.479-483.

[prev] [tofc] [next]

ECAI-2000 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Humboldt University on behalf of Gesellschaft für Informatik.