Computing prime implicates

ABSTRACT

This paper surveys three methods for computing the prime implicates of a set of propositions (ie., minimizing a boolean function) and performs a comparison between them. Data is provided which suggests that methods based on resolution can be as efficient as methods based on matrices and semantic trees. We also discuss the advantages of resolution-based methods for applications in man-machine communication involving abduction (inference to the best explanation) and truth maintenance (belief revision).

REFERENCES

• 1: Douglas Appelt , Kurt Konolige, A practical nonmonotonic theory for reasoning about speech acts, Proceedings of the 26th annual meeting on Association for Computational Linguistics, p.170-178, June 07-10, 1988, Buffalo, New York [doi>10.3115/982023.982044]
• 2: Bibel, W. (1982). A comparative study of several proof Imacedutes. Artificial Intelligence, 18, 269-293.
• 3: Jackson, P. Computing prime implicates incrementally. S ubmitled for publication.
• 4: Jackson, P. (1991). Computing minimal refutations. Proceedings of the 3rd $candanavian Conference on Artificial Intelligence, 107-118, Amsterdam: IOS Pre,~.
• 5: Jackson, P. (1991). Prime implicates: Their computation and use. Proceedings of the l lth International Conference on Expert Systems & Their Applications, 1, 53-64, EC~.
• 6: Jackson, P. (1991). Possibilistic prime implicates and their use in abduction. Proceedings of the AAAI-91 Worskhop on Abduction, 44-50, Anaheim, CA.
• 7: Peter Jackson , John Pais, Computing prime implicants, Proceedings of the tenth international conference on Automated deduction, p.543-557, July 1990, Kaiserslautern, Germany
• 8: Alex Kean , George Tsiknis, An incremental method for generating prime implicants/implicates, Journal of Symbolic Computation, v.9 n.2, p.185-206, Feb. 1990 [doi>10.1016/S0747-7171(08)80029-6]
• 9: Lehner, P. E., Ed. (1991). Associate Technology: Opportunities and Challenges, George Mason University, v ginia.
• 10: McCluskey, E. L. Jr. (1956). Minimization of Boolean functions. Bell Systems Technical Journal, 35, 1417-1444.
• 11: Pais, J. & Jackson, P. (in press). Partial monotonicity and a new version of the Ramsey test. To appear in Studia Logica.
• 12: Quine, W. V. O. (1952). The problem of simplifying truth functions. American Mathematical Monthly, 59, 521-53 i.
• 13: Quine, W. V. O. (1955). A way to simplify truth ftmctions. American Mathematical Monthly, 62, 627-631.
• 14: Quine, W. V. O. (1959). On cores and prime impficants of truth functions. American Mathematical Monthly, 66.
• 15: Reiter, R. & de Kleer, J. (1987). Foundations of assumption-based truth maintenance systems: Preliminary report. Proceedings of the 6th National Conference on Artificial Intelligence (AAAI-87) , 183-188.
• 16: S lagle, J. R., Chang, C.-L., & Lee, R. C. T. (1970). A new algorithm for generating prime implicants. IEEE Transactions on Compmers, C-19(4), 304-310.
• 17: John K. Slaney , Ewing L. Lusk, Parallelizing the closure computation in automated deduction, Proceedings of the tenth international conference on Automated deduction, p.28-39, July 1990, Kaiserslautern, Germany
• 18: Stickel, M. E. (1990). A method for abductive reasoning in natural-language interpretation. AAAI Spring Symposium Series: Automated Abduction, 5-12, Stanford Unive~ty, California.
• 19: Tison, P. (1967). Generalized consensus theory and its application to the minimization of boolean functions. IEEE Transactions on Electronic Computers, EC-16(4), 446-456.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

General Terms:
Algorithms, Measurement, Performance, Theory