Skip Navigation

Journal of Logic and Computation 1998 8(2):135-145; doi:10.1093/logcom/8.2.135
© 1998 by Oxford University Press
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by SHINY, A. K.
Right arrow Articles by PUJARI, A. K.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Original Articles

Computation of Prime Implicants using Matrix and Paths

A. K. SHINY and ARUN K. PUJARI

Artificial Intelligence Laboratory, Department of Computer & Information Sciences, University of Hyderabad Hyderabad 500046, India. E-mail: akscsakpcs{at}uohyd.ernet.in

In this paper, an efficient algorithm to compute the set of prime implicants of a propositional formula in Conjunctive Normal Form (CNF) is presented. The proposed algorithm uses a concept of representing the formula as a binary matrix and computing paths through the matrix as implicants. The algorithm finds the prime implicants as the prime paths using the divide-and-conquer technique. The proposed algorithm can be used for knowledge compilation, Clause Maintenance Systems where the knowledge base is propositional formulae. Moreover, the algorithm is easily adaptable to the incremental mode of computation where an earlier formula is updated by a set of clauses.

Keywords: Prime implicants; propositional logic


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.