Truth versus Information in Logic Programming
Lee Naish
Harald Sondergaard
The semantics of logic programs was originally described in terms of two-valued logic.
Soon, however, it was realised that three-valued logic had some natural advantages, as it
provides distinct values not only for truth and falsehood, but also for "undefined". The
three-valued semantics proposed by Fitting and by Kunen are closely related to what is
computed by a logic program, the third truth value being associated with non-termination. A
different three-valued semantics, proposed by Naish, shared much with those of Fitting and
Kunen but incorporated allowances for programmer intent, the third truth value being
associated with underspecification. Naish used an (apparently) novel "arrow" operator to
relate the intended meaning of left and right sides of predicate definitions. In this paper
we suggest that the additional truth values of Fitting/Kunen and Naish are best viewed as
duals. We use Belnap's four-valued logic, also used elsewhere by Fitting, to unify the two
three-valued approaches. The truth values are arranged in a bilattice which supports the
classical ordering on truth values as well as the "information ordering". We note that the
"arrow" operator of Naish (and our four-valued extension) is essentially the information
ordering, whereas the classical arrow denotes the truth ordering. This allows us to shed new
light on many aspects of logic programming, including program analysis, type and mode
systems, declarative debugging and the relationships between specifications and programs,
and successive executions states of a program. This paper is to appear in Theory and
Practice of Logic Programming (TPLP).
Keywords:
Prolog, semantics, many-valued logic, information order, verification, specification,
program analysis, modes, declarative debugging, models of computation.
Lee