The concepts of associated graph G and associated hypergraph H are introduced for a switching function F(x1,,xn) with n variables. Then, the following methods and algorithms are derived: (1) The graph theory methods and branch-and-bound algorithm BBAPI for finding all prime implicants of F, (2) Algorithm AMSHT for finding a minimal sum for F by hypergraph theory. These methods are simple and intuitive. They are convenient not only for computation by hand but also for realization by a computer. Their computation efficency are higher than that of Karnaugh map method and Q-M tabular method which are customarily used.
Samuel C L. Mo.iern Switching Theory and Digital Design. Englewood Cliffs, N.J.: Prentice-[2]Hall, Inc., 1978.[3]Karnaugh M. Communications and Electronics, 1953, (9): 593-599.[4]Muroga S. Logic Des.ign and Fwitching Theory, New York: John Wiley Sons, 3-4.[5]Quine W V. American Mathematics Monthly, 1952, 59(8): 521-531.[6]McCluskey E J. Bell Systems Technical Journal, 1956, 35(6): 1417-1444.[7]1979, Chapter Swamy M N S,等著,左恺主译.图、网络与算法.北京:高等教育出版社,1988年,第一章.[8]黄汝激.电子科学学刊,1987,9(3): 244-255.
DownLoad: