Probalistic 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 Ln. 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. We especially introduce the proof theory of many­valued logic programming in Pr*n and show its soundness and completeness.