逻辑函数的无冗余覆盖选择问题

摘要

逻辑函数的最小化算法可分为两大步骤:产生本源蕴涵项和在这些蕴涵项中选择一个最小覆盖.人说后者比前者更加困难,这的确是事实.我们这里提出一个去冗余和选择一个最小覆盖的算法. 给定函数f的一个本源覆盖G,首先将G分为三个子集:实质本源项子集E,完全冗余项子集R和相对冗余项子集P.然后在P中选择一个子集P*,使P*UE为f的一个近似最小覆盖.很明显,后一项任务比前者要复杂得多.所以,我们的讨论侧重于后者.