Probabilistic Logic of k-Valued Formulaic Events Without Combinatorial Explosion

ABSTRACTIn a k-valued propositional calculus, the truth table of a formula with m variables has 𝑘𝑘𝑚𝑚 rows, so the number of interpretations grows exponentially and gives rise to the problem of combinatorial explosion [1]. As the number of variables and their dependencies increases, the cost of logical and probabilistic inference grows accordingly [5,6,7], and for many-valued systems this exponential growth obstructs the use of traditional truth-table methods in intelligent systems. In general this difficulty is intrinsic rather than incidental: for k-valued (Łukasiewicz) logic, satisfiability and the coherence of probability assessments are NP-complete, and computing the exact probability of a formula is #P-hard.On the basis of discrete probability theory and k-valued logic, this article develops a k-valued discrete-probability logic of event formulas, intended for knowledge representation and probabilistic inference in artificial-intelligence systems, in particular for diagnostic and decision-support tasks whose admissible alternatives are mutually exclusive. The model rests on a single mutually exclusive and exhaustive family of elementary events — exactly one of which occurs — so that every event formula is a combination of these atoms and its probability is obtained from an occurrence table whose size is linear in n, in contrast to the exponentially many rows of the full truth table. The proposed algorithm therefore avoids combinatorial explosion not by accelerating the general problem, but by isolating a tractable fragment of it — the mutually-exclusive, single-partition model — in which the probabilities of k-valued event formulas are computed in polynomial time.