Functional Many-valued Logic and Global Predicate Compression

Abstract. Knowledge-base systems must typically deal with imperfection in knowl-edge, in particular, in the form of incompleteness and uncertainty. Extensions to many-valued logic programming and deductive databases for handling incom-pleteness/uncertainty are numerous. They can broadly be characterized into non-probabilistic and probabilistic formalisms. In this paper we show how the higher types of Herbrand interpretations for logic programs, where it is not possible to associate a fixed logic value (a constant from a given domain of truth values) to a given ground atom of a Herbrand base, arise often in practice when we have to deal with uncertain or imprecise information. They arise also in the compres-sion of databases, that is, in a kind of database encapsulation where some number of attributes of its relations are hidden from users. In this paper we present the canonical transformation of standard many-valued logics into functional many-valued logics with higher-order Herbrand interpretation types, and their flatten-ing into 2-valued logics with the ordinary Herbrand interpretations. We show that the global predicate compression and decompression are mutually inverse in the Galois connection. We define the semilattice of higher order Herbrand interpre-tations and show that they are the result of the application of the observational equivalence to the ordinary Herbrand interpretation semilattice.