Semantic Minimization of 3-Valued Propositional Formulae

Thomas Reps, Alexey Loginov, and Mooly Sagiv

This paper presents an algorithm for a non-standard logic-minimization problem that arises in 3-valued propositional logic. The problem is motivated by the potential for obtaining better answers in applications that use 3-valued logic. An answer of 0 or 1 provides precise (definite) information; an answer of 1/2 provides imprecise (indefinite) information. By replacing a formula j with a ``better'' formula y, we may improve the precision of the answers obtained. In this paper, we give an algorithm that always produces a formula that is ``best'' (in a certain well-defined sense).

Keywords: 3-valued logic, minimization, prime implicant, sum of products, supervaluational semantics

(Click here to access the paper: PostScript, PDF.)