Probabilistic and Truth−Functional Many−Valued Logic Programming

Abstract

We introduce probabilistic many-valued logic programs in which the implication connective is interpreted as material implication. We show that probabilistic many-valued logic programming is computationally more complex than classical logic programming. More precisely, some deduction problems that are P-complete for classical logic programs are shown to be co-NP-complete for probabilistic many-valued logic programs. We then focus on many-valued logic programming in Pr_n* as an approximation of probabilistic many-valued logic programming. Surprisingly, many-valued logic programs in Pr_n* have both a probabilistic semantics in probabilities over a set of possible worlds and a truth-functional semantics in the finite-valued Lukasiewicz logics L_n. Moreover, many-valued logic programming in Pr_n* has a model and fixpoint characterization, a proof theory, and computational properties that are very similar to those of classical logic programming.