A three-valued semantics for deductive databases and logic programs

This paper proposes two principles, justifiability and minimal undefinedness, for a three-valued model-theoretic approach to semantics of logic programs and deductive databases (also called disjunctive logic programs). The former is intimately related to the concept of labeling-based justification in Doyle's truth maintenance system while the latter requires the use of the truth value undefined only when it is necessary. We examine the question why and in what circumstances the undefined is needed under these two principles. We show that these two principles yield a declarative semantics for deductive databases and logic programs, which is called the regular model semantics. Program properties in this semantics are analyzed and results obtained concerning the relationship among regular, stable, and well-founded semantics, which show that the regular model semantics is a natural extension of the latter two semantics