集合锐积的组合算法及其应用

A COMBINATORIAL ALGORITHM FOR SET-SHARP-PRO-DUCT OPERATION AND ITS APPLICATIONS

本文提出计算在n维布尔空间上定义的一多维体对另一多维体集合锐积的组合算法。这个方法将该锐积计算简化为寻找定义在n′维(n′≤n)布尔空间的2n′个n′-1维体的极小有效组合集问题,而后者又等价为寻找一个行相关矩阵的极小有效列覆盖集的问题。该算法保证所得的均为质多维体,且有较高的计算效率,它还为锐积运算更有效地运用于逻辑最小化的过程创造了条件。

This paper presents a combinatorial algorithm for calculating the sharp-product of a cube with respect to a set of cubes in an n-dimensional Boolean space. This approach simplifies the calculation to the searching for 2n' minimal, effective combination sets of (n'-1)-dimensional cubes defined in an n'-dimensional Boolean space with n'≤n, which is equivalent to the searching for the set of minimal effective colunin covers of a row incidence matrix. This algorithm guarantees the primality of the resultant cubes and is more efficient than the traditional way. It also provides conditions for the sharp-product to be used more efficiently in logic minimization.