Abstract

Human beings often have to reason and make decisions based on uncertain knowledge of real world problems. Therefore, many artificial intelligence (AI) applications, such as expert systems, must have the ability to understand the way human beings reason from uncertain data or knowledge in order to reach a conclusion. Several approaches have been proposed in this respect to deal with various kinds of uncertainty in AI. Among these approaches, probabilistic theory is used in many research areas such as knowledge-based systems, data mining, etc. Nilsson revisited in 1986 the early work of Boole (1854) and of Hailperin (1976) on logic and probability. He proposed a generalization of logic in which the truth values of sentences are probability values. The main problem addressed by Nilsson is the probabilistic satisfiability ( PSAT) for both propositional and first-order logic: determine, given a set of sentences (i.e., clauses) and probabilities that these sentences are true, whether these probabilities are consistent. Since first-order logic is used in many AI applications due to its expressiveness to represent knowledge over propositional logic, our thesis proposes an extension of the mathematical modeling of PSAT to first-order logic, FOPSAT for short. We next propose an exact algorithm based on delayed column generation technique, to check consistency and, if consistency holds, to entail new probability values for an additional logical sentence to be true and such that the augmented set of sentences remains consistent. We illustrate the proposed algorithm on an example, and discuss its potential to solve medium size FOPSAT instances.