Well-Founded Semantics Coincides with Three-Valued Stable Semantics¹

Article type: Research Article

Authors: Przymusinski, Teodor

Affiliations: Department of Mathematical Sciences, The University of Texas at El Paso, El Paso, TX 79968, USA, E-mail: teodor%utep.uucp@cs.utexas.edu

Note: [1] The author acknowledges support from the National Science Foundation under grant #IRI-89-10729 and from the Army Research Office under grant #27079-EL-SAH.

Abstract: We introduce 3-valued stable models which are a natural generalization of standard (2-valued) stable models. We show that every logic program P has at least one 3-valued stable model and that the well-founded model of any program P [Van Gelder et al., 1990] coincides with the smallest 3-valued stable model of P. We conclude that the well-founded semantics of an arbitrary logic program coincides with the 3-valued stable model semantics. The 3-valued stable semantics is closely related to non-monotonic formalisms in AI. Namely, every program P can be translated into a suitable autoepistemic (resp. default) theory Pˆ so that the 3-valued stable semantics of P coincides with the (3-valued) autoepistemic (resp. default) semantics of Pˆ. Similar results hold for circumscription and CWA. Moreover, it can be shown that the 3-valued stable semantics has a natural extension to the class of all disjunctive logic programs and deductive databases. Finally, following upon the recent approach developed by Gelfond and Lifschitz, we extend all of our results to more general logic programs which, in addition to the use of negation as failure, permit the use of classical negation.

DOI: 10.3233/FI-1990-13404

Journal: Fundamenta Informaticae, vol. 13, no. 4, pp. 445-463, 1990