化简开关函数的图论方法

GRAPH THEORY METHODS FOR SIMPLIFICATION OF SWITCHING FUNCTIONS

本文引入了n变量开关函数F(x_1,…,x_n)的伴随图G和伴随超图H的概念,导出了下列方法和算法:(1)求F的所有本原蕴含项的图论方法和分支定界算法BBAPI;(2)应用超图理论求F的最小和表达式的算法AMSHT。这些方法简单、直观;既便于手算,也便于用计算机实现;计算效率高于常用的卡诺图法和Q-M列表法。

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.