Home Online Resources Table of Contents

Journal of Logic and Computation, Volume 8, Issue 2: April 1998.

Computation of prime implicants using matrix and paths

AK Shiny and AK Pujari

Artificial Intelligence Laboratory, Department of Computer & Information Sciences, University of Hyderabad, Hyderabad 500046, India. E-mail: {akscs,akpcs}@uohydernet.in

In this paper, an efficient algorithm to compute the set of prime implicants of a prepositional 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 prepositional 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, prepositional logic.

Pages 135-145


This page is run by Oxford University Press, Great Clarendon Street, Oxford OX2 6DP, UK
as part of the OUP Journals World Wide Web service.
Comments and feedback: www-admin@oup.co.uk
URL: http://www.oup.co.uk/logcom/hdb/Volume_08/Issue_02/080135.sgm.abs.html
Last modification: 4 June 1998.
Copyright© Oxford University Press, 1998.