Login | Register

An exact algorithm for first order probabilistic logic


An exact algorithm for first order probabilistic logic

Sultana, Razia (2007) An exact algorithm for first order probabilistic logic. Masters thesis, Concordia University.

[thumbnail of MR40954.pdf]
Text (application/pdf)
MR40954.pdf - Accepted Version


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.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Sultana, Razia
Pagination:xi, 116 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Jaumard, Brigitte
Identification Number:LE 3 C66C67M 2007 S85
ID Code:975734
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:13
Last Modified:13 Jul 2020 20:08
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top