Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes

Olivier Coudert; Jean-Christophe Madre

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1994)

  • Volume: 28, Issue: 2, page 125-149
  • ISSN: 0988-3754

How to cite


Coudert, Olivier, and Madre, Jean-Christophe. "Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 28.2 (1994): 125-149. <http://eudml.org/doc/92470>.

author = {Coudert, Olivier, Madre, Jean-Christophe},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {prime implicant computation procedures},
language = {fre},
number = {2},
pages = {125-149},
publisher = {EDP-Sciences},
title = {Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes},
url = {http://eudml.org/doc/92470},
volume = {28},
year = {1994},

AU - Coudert, Olivier
AU - Madre, Jean-Christophe
TI - Une approche intentionnelle du calcul des implicants premiers et essentiels des fonctions booléennes
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1994
PB - EDP-Sciences
VL - 28
IS - 2
SP - 125
EP - 149
LA - fre
KW - prime implicant computation procedures
UR - http://eudml.org/doc/92470
ER -


  1. 1. S. B. AKERS, Binary Decision Diagrams, IEEE Trans. on Computers, 1978, vol. C-27. Zbl0377.94038
  2. 2. T. C. BARTEE, I. L. LEBOW, I. S. REED, Theory and Design of Digital Machines, McGraw-Hill, 1962. Zbl0114.06504MR154452
  3. 3. J.-P. BILLON, Perfect Normal Forms for Discrete Functions, BULL Research Report n° 87019, juin 1987. 
  4. 4. N. N. BISWAS, Introduction to Logic and Switching Theory, Gordon & Breach Science, 1975. Zbl0314.94021
  5. 5. R. E. BRAYTON, G. D. HACHTEL, C. T. MCMULLEN, A. L. SANGIOVANNI-VINCENTELLI, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, 1984. Zbl0565.94020
  6. 6. F. M. BROWN, Boolean Reasoning, Kluwer Academic Publishers, 1990. Zbl0719.03002MR1166188
  7. 7. R. E. BRYANT, Graph-Based Algorithms for Boolean Functions Manipulation, IEEE Trans. on Computers, 1986, vol. C35. Zbl0593.94022
  8. 8. R. E. BRYANT, On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication, Carnegie Mellon University Research Report, September 1988. 
  9. 9. K. M. BUTLER, D. E. ROSS, R. KAPUR, M. R. MERCER, Heuristics to Compute Variable Orderings for Efficient Manipulations of Ordered Binary Decision Diagrams, in Proc. of 28th Design Automation Conference, San Francisco, California, June 1991, 417-420. 
  10. 10. O. COUDERT, J. C. MADRE, A Unified Framework for the Formal Verification of Sequential Circuits, Proc. of ICCAD '90, novembre 1990, Santa Clara CA, U.S.A. Zbl0747.68072
  11. 11. O. COUDERT, S.I.A.M.: Une boîte à outils pour la preuve formelle de systèmes séquentiels, Thèse de troisième cycle, École Nationale Supérieure des Télécommunications, Paris, France, octobre 1991. 
  12. 12. O. COUDERT, J. C. MADRE, A New Method to Compute Prime and Essential Prime Implicants of Boolean Functions, Proc. of Brown/MIT Conference on Advanced Research in VLSI and Parallel Systems, mars 1992, Cambridge MA, U.S.A. 
  13. 13. O. COUDERT, J. C. MADRE, Implicit and Incremental Computation of Primes and Essential Primes of Boolean Functions, Proc. of 29th DAC, juin 1992, Anaheim CA, U.S.A. 
  14. 14. O. COUDERT, J. C. MADRE, A New Implicit DAG Based Prime and Essential Prime Computation Technique, Proc. of International Symposium on Information Sciences, juillet 1992, Fukuoka, Japon. 
  15. 15. M. DAVIS, H. PUTNAM, A Computing Procedure for Quantification Theory, Journal of the ACM, 1960, vol. 7, 201-215. Zbl0212.34203MR134439
  16. 16. S. J. FRIEDMAN, K. J. SUPOWIT, Finding the Optimal Variable Ordering for Binary Decision Diagrams, IEEE Trans. on Computer, 1990, vol. C-39, 710-713. MR1059769
  17. 17. D. F. HASL, Advanced Concepts in Fault Tree Analysis, Proc. of System Safety Symposium, juin 1965, Seatle. 
  18. 18. S. J. HONG, S. MUROGA, Absolute Minimization of Completely Specified Switching Functions, IEEE Trans. on Computers, 1991, vol. 40, 53-65. MR1093496
  19. 19. H. R. HWA, A Method for Generating Prime Implicants of a Boolean Expression, IEEE Trans. on Computers, 1974, 637-641. Zbl0281.94025MR441563
  20. 20. H. Y. HWANG, D. S. CHAO, M. E. VALDEZ, A New Technique for the Minimization of Switching Functions, IEEE Southeastcon'85, 1985, 299-304. 
  21. 21. J. DE KLEER, An Assumption-Based TMS, Artificial Intelligence, 1986, vol. 28, 127-162. 
  22. 22. J. DE KLEER, B. C. WILLIAMS, Diagnosing Multiple Faults, Artificial Intelligence, 1987, vol. 32, 97-130. Zbl0642.94045
  23. 23. M. C. LOUI, G. BILARDI, The Correctness of Tison's Method for Generating Prime Implicants, Report R-952, UILU-ENG 82-2218, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1982. 
  24. 24. E. L. Jr. MCCLUSKEY, Minimization of Boolean Functions, Bell System Techniques, 1959, vol. 35, 1417-1444. MR82876
  25. 25. J. C. MADRE, J. P. BILLON, Proving Circuit Correctness Using Formal Comparison Between Expected and Extracted Behaviour, Proc. of the 25th DAC, juillet 1988, Anaheim CA, U.S.A. 
  26. 26. J. C. MADRE, O. COUDERT, A Logically Complete Reasoning Maintenance System Based on Logical Constrain Solver, Proc. of IJCAI'91, août 1991, Sydney, Australia. Zbl0747.68072
  27. 27. S. MALIK, A. R. WANG, R. K. BRAYTON, A. SANGIOVANNI-VINCENTELLI, Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment, Proc. of ICCAD'88, Santa Clara, 1988, U.S.A. 
  28. 28. S. MINATO, N. ISHIURA, S. YAJIMA, Shared Binary Decision Diagrams with Attributed Edges for Efficient Boolean Function Manipulation, Proc. of the 27 th Design Automation Conference, June 1990, Las Vegas, Nevada, 52-57. 
  29. 29. A. PAGÈS, M. GONDRAN, Fiabilité des systèmes, Eyrolles, 1980. Zbl0491.90029MR596408
  30. 30. W. V. O. QUINE, The Problem of Simplifying Truth Functions, American Mathematics Monthly, 1952, vol. 59, 521-531. Zbl0048.24503MR51191
  31. 31. W. V. O. QUINE, A Way to Simplify Truth Functions, American Mathematics. Monthly, 1955, vol. 62, 627-631. Zbl0068.24209MR75886
  32. 32. W.V. O. QUINE, On Cores and Prime Implicants of Truth Functions, American Mathematics Monthly, 1959, vol. 66. Zbl0201.32203MR108439
  33. 33. R. REITER, A Theory of Diagnosis From First Principles, Artificial Intelligence, 1987, vol.32. Zbl0643.68122MR884192
  34. 34. R. REITER, J. de KLEER, Foundation of Assumption-Based Truth Maintenance Systems: Preliminary Report, Proc. of 6th AAAI, 1987, 183-188. 
  35. 35. V. T. RHYNE, P. S. NOE, M. H. MCKINNEY, U. W. POOCH, A New Technique for the Fast Minimization of Switching Functions, IEEE Trans, on Computers, 1977, vol. C-26/8, 757-764. Zbl0365.94048MR530246
  36. 36. J. A. ROBINSON, A Machine-Oriented Logic Based on the Resolution Principle, Journal of ACM, 1965, vol. 12, 23-41. Zbl0139.12303MR170494
  37. 37. J. P. ROTH, Algebraic Topological Methods for the Synthesis of Switching Systems, Trans. of American Mathematical Society, 1958, vol. 88/2, 301-326. Zbl0083.13103MR97285
  38. 38. R. L. RUDELL, A. L. SANGIOVANNI-VINCENTELLI, Multiple Valued Minimization for PLA Optimization, IEEE Trans. on CAD, 1987, vol 6, 727-750. 
  39. 39. T. SASAO, An Application of Multiple-Valued Logic to a Design of Programmable Logic Arrays, Proc. of 8th Int'l Symposium on Multiple Valued Logic, 1978. MR565416
  40. 40. J. R. SLAGE, C. L. CHANG, R. C. T. LEE, Completeness Theorems for Semantics Resolution in Consequence Finding, Proc. of IJCAI'69, 1969, 281-285. 
  41. 41. J. R. SLAGE, C. L. CHANG, R. C. T. LEE, A New Algorithm for Generating Prime Implicants, IEEE Trans, on Computers, 1970, vol. C-19(4), 304-310. Zbl0197.14601MR456994
  42. 42. M. STONE, The Theory of Representations for Boolean Algebra, Trans. Amer. Math. Soc., 1936, vol. 40, 37-111. Zbl0014.34002MR1501865JFM62.0033.04
  43. 43. P. TISON, Generalized Consensus Theory and Application to the Minimization of Boolean Functions, IEEE Trans, on Electronic Computers, 1967, vol. EC-16/4, 446-456. Zbl0158.16102
  44. 44. A. VILLEMEUR, Sûreté de fonctionnement des systèmes industriels, Eyroles, 1988. 
  45. 45. S. YANG, Logic Synthesis and Optimization Benchmarks User Guide, Microelectronics Center of North Carolina, January 1991. 

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.