Generalized knowledge-based semantics for multi-valued logic program

A generalized logic programming system is presented which uses bilattices as the underlying framework for the semantics of programs. The two orderings of the bilattice reflect the concepts of truth and knowledge. Programs are interpreted according to their knowledge content, resulting in a monotonic semantic operator even in the presence of negation. A special case, namely, logic programming based on the four-valued bilattice is carefully studied on its own right. In the four-valued case, a version of the Closed World Assumption is incorporated into the semantics. Soundness and Completeness results are given with and without the presence of the Closed World Assumption. The concepts studied in the four-valued case are then generalized to arbitrary bilattices. The resulting logic programming systems are well suited for representing incomplete or conflicting information. Depending on the choice of the underlying bilattice, the knowledge-based logic programming language can provide a general framework for other languages based on probabilistic logics, intuitionistic logics, modal logics based on the possible-worlds semantics, and other useful non-classical logics. A novel procedural semantics is given which extends SLDNF-resolution and can retrieve both negative and positive information about a particular goal in a uniform setting. The proposed procedural semantics is based on an AND-parallel computational model for logic programs. The concept of substitution unification is introduced and many of its properties are studied in the context of the proposed computational model. Some of these properties may be of independent interest, particularly in the implementation of parallel and distributed logic programs. Finally, soundness and completeness results are proved for the proposed logic programming system. It is further shown that for finite distributive bilattices (and, more generally, bilattices with the descending chain property), an alternate procedural semantics can be developed based on a small subset of special truth values which turn out to be the join irreducible elements of the knowledge part of the bilattice. The algebraic properties of these elements and their relevance to the corresponding logic programming system are extensively studied.