Embedding negation as failure into minimal knowledge

Recent studies in nonmonotonic reasoning have shown that many of the best known nonmonotonic logics are based on the same two fundamental principles, i.e. minimal knowledge and negation as failure (or negation by default). In this paper we prove that it is possible to express negation as failure in terms of minimal knowledge. Specifically, we present a polynomial, non-faithful, modular embedding of Lifschitz's logic of minimal knowledge and negation as failure MKNF into Halpern and Moses' logic of minimal knowledge S5(G). From the theoretical viewpoint, this result implies that minimal knowledge has the same expressive power of negation as failure, hence it is possible to embed all the best known propositional nonmonotonic formalisms, in particular default logic, autoepistemic logic, and circumscription, into S5(G). From the perspective of knowledge-based systems, the proposed embedding allows in principle for realizing negation as failure in systems without a negation as failure construct, as e.g. positive disjunctive deductive databases.