# Reasoning About Minimal Belief And Negation As Failure

## Riccardo Rosati

Dipartimento di Informatica e Sistemistica Universita di Roma "La Sapienza" Via Salaria 113, 00198 Roma, Italy R OSATI @DIS. UNIR O MA 1. IT

## Abstract

We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF.

In particular, we show that skeptical entailment in propositional MBNF is Π 2 -complete, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.

## 1. Intro Duction

Research in the formalization of commonsense reasoning has pointed out the need of formalizing agents able to reason introspectively about their own knowledge and ignorance
(Moore, 1985; Levesque, 1990). Modal epistemic logics have thus been proposed, in which modalities are interpreted in terms of knowledge or belief. Generally speaking, the conclusions an introspective agent is able to draw depend on both what she knows and what she does not know. Hence, any such conclusion may be retracted when new facts are added to the agent's knowledge. For this reason, many nonmonotonic modal formalisms have been proposed in order to characterize the reasoning abilities of an introspective agent.

Among the nonmonotonic modal logics proposed in the literature, the logic of minimal belief and negation as failure MBNF (Lifschitz, 1991, 1994) is one of the most studied formalisms (Chen, 1994; Bochman, 1995; Beringer & Schaub, 1993). Roughly speaking, such a logic is built by adding to first-order logic two distinct modalities, a "minimal belief" modality B and a "negation as failure" modality not. The logic thus obtained is characterized in terms of a nice model-theoretic semantics. MBNF has been used in order to give a declarative semantics to very general classes of logic programs (Lifschitz & Woo, 1992; Schwarz & Lifschitz, 1993; Inoue & Sakama, 1994), which generalize the stable model semantics of negation as failure in logic programming (Gelfond & Lifschitz, 1988, 1990, 1991). Also, MBNF can be viewed as an extension of the theory of epistemic queries to databases (Reiter, 1990), which deals with the problem of querying a first-order database about its own knowledge. Due to its ability of expressing many features of nonmonotonic logics (Lifschitz, 1994; Schwarz & Lifschitz, 1993), MBNF is generally considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming.