An Anytime Deduction Algorithm for the Probabilistic Logic and Entailment Problems

We study two basic problems of probabilistic reasoning: the probabilistic logic and the probabilistic entailment problems. The first one can be defined as follows. Given a set of logical sentences and probabilities that these sentences are true, the aim is to determine whether these probabilities are consistent or not. Given a consistent set of logical sentences and probabilities, the probabilistic entailment problem consists in determining the range of the possible values of the probability associated with additional sentences while maintaining a consistent set of sentences and probabilities. This paper proposes a general approach based on an anytime deduction method that allows the follow-up of the reasoning when checking consistency or determining the probability intervals for the probabilistic logic and entailment problems. Considering a series of subsets of sentences and probabilities, the approach proceeds by computing increasingly narrow probability intervals that either show a contradiction or that contain the tightest entailed probability interval. Computational experience have been performed to compare the anytime deduction method with an exact one using column generation techniques, both with respect to the range of the probability intervals and the computing times