在1996年发表的这篇论文中,作者王晓东、万旭和杨凡提出了一个新方法,通过子降维图和子卡诺图对多变量逻辑函数进行化简。该方法建立在传统的降维图化简技术基础上,旨在解决变量数量增多时,卡诺图规模急剧增大导致化简困难的问题。新方法的核心在于对降维图中的逻辑函数进一步进行降维处理,即创建子降维图或子卡诺图,从而有效简化高维卡诺图的规模,并便于通过图形化方法进行逻辑函数化简。
在深入探讨该方法前,我们首先需要了解降维图和卡诺图的概念以及它们在逻辑函数化简中的应用。降维图是一种图形化工具,用于直观表示逻辑函数,通过将逻辑函数中的变量进行分组来降低维度,从而简化逻辑函数的图形表示。卡诺图是一种特殊的降维图,它基于变量的二进制性质,使用二维表格形式直观展示逻辑函数的真值表,并利用图形法进行逻辑函数的简化。
传统的卡诺图在变量数量较少时(例如3个或4个变量)操作较为简单,但当变量数量超过4个时,卡诺图的规模迅速增长,使得化简过程变得复杂,易于产生错误和冗余项。为了克服这一局限,作者们提出了子降维图和子卡诺图的概念。子降维图是在原始降维图的基础上,对每个小格中包含的逻辑函数进行再次降维处理。通过这样的方法,可以将高维的逻辑函数问题转化为多个低维的逻辑函数问题,从而达到降低问题复杂度的目的。
在该论文中,具体描述了如何通过以下步骤实现多变量逻辑函数的降维图化简:
1. 首先将逻辑函数转换为求和项之积(SOP)形式。
2. 确定收缩变量和降维维数。在SOP表达式中,出现次数较少的变量应被选定为收缩变量,而出现次数较多的变量则作为标注变量。降维图的维数最好不要超过4维,因为维数更低的卡诺图化简起来更为直观和简单。
3. 作降维图。对于那些无收缩变量的项应先填入降维图,以在小格中得到更多的常量。
4. 检查得到的降维图是否最简。若不最简,则需要进一步作出子降维图或子卡诺图。若子降维图中的逻辑函数仍不最简,则继续构建更小子降维图,直至化简完成。
5. 读降维图,目的是化简逻辑函数。首先读取子降维图或子卡诺图,直至原降维图上的逻辑函数化简为最简形式。在阅读降维图时,应遵循特定的规则和步骤,如优先圈选含收缩变量较多的项,并对逻辑或的小格进行单独考虑。
以上方法不仅在理论上提供了对多变量逻辑函数进行图形化简的新途径,而且在实际应用中,特别是在逻辑电路设计和数字系统分析方面,具有重要的实用价值。通过有效降低卡诺图规模,这一方法大大扩展了图形化简技术的应用范围,并提高了化简的效率。此外,这一技术对于计算机科学、电子工程、人工智能以及其他依赖于逻辑函数分析的领域来说,是一个重要的理论贡献和实践工具。