Groupe d’études et de recherche en analyse des décisions

G-99-41

A Deductive Approach for Probabilistic Logic Problems

, et

Given a set of logical sentences and probabilities that these sentences are true, the probabilistic logic problem consists in determining whether these probabilities are consistent. When there is consistency, the probabilistic entailment problem is to determine the range of values of the probability associated with an additional logical sentence such that the resulting system of sentences and probabilities remain consistent. The solution of both problems can be obtained after a reformulation as linear programs with an exponential number of variables. Using a column generation technique, efficient solution can be obtained for systems with up to 900 variables and 500 sentences. We propose to explore a new approach based on a deductive method that allows the follow-up of the reasoning when determining the probability of an additional sentence. Computational experience have been performed to compare the deductive method with the column generation technique, and computing time reduction have been obtained with a factor of 10,000 on some problems with up to 1200 sentences and 800 variables.

, 17 pages