The problem of negative information is widely known in the logic programming community. The main motivation for work in this area is to regain an axiomatic reading of programs with negation. Recently, much work has resulted from the cross-fertilization between this field and research in non-monotonic reasoning. This paper is a contribution toward a logical and algebraic theory of logic programming with negation.

The main steps involve the introduction of a third truth value (indefinite). The proposed three-valued Herbrand interpretations are partial interpretations, in which every atom in the Herbrand base that does not get a truth value in {T,F} is assigned I. The order on {T,I,F} corresponds to the set inclusion order on the set of three-valued interpretations, where T ≥ 1 and F ≥ 1. Interpretations are monotonic in the sense that the truth value of a formula, some of whose atoms have the indefinite truth value, cannot change from T to F or vice versa.

To obtain completeness in the logic, a non-monotonic implication connective “→” is introduced. This connective differs from the Lukasiewicz connective in that (T→I)=F and (I→F)=T. This means that → assumes values in {T,F} and is non-monotonic since ( I , F ) ≤ ( T , F ) but ( I → F ) > ( T → F ). We have a strong model of a set of formulae (every formula assumes the value T) and a weak model (no formula assumes the value F). The authors define a consequence operator such that the least Herbrand model of a program can be characterized as a least fixpoint of this operator. Finally, by syntactic manipulations, three-valued programs can be manipulated by extended two-valued interpreters.

The paper is worth reading for those interested in deductive databases and in nonmonotonic reasoning. It is self-contained, and related work is covered well. Certain idiomatic uses (perhaps artifacts of the translation) and an obscure notation make the paper hard to read, however.