计算机智能化简多变量逻辑函数的算法分析

计算机智能化简多变量逻辑函数的算法分析摘要：
在设计逻辑电路图时，由真值表直接得到的函数往往比较复杂。

代数法和卡诺图法等方法对于变量数目较多的逻辑函数则效果不佳，本文介绍一种可编程化简复杂逻辑函数的方法──q-m法(也叫表格法)，该方法可以对变量数目较多的逻辑函数进行计算机智能化简。

关键词：
逻辑表达式结构体链表结构体数组化简合并比较研究真值表
蕴涵表
在清楚本论文的基本原理后，我们将整个化简过程划分为四个模块，并针对每个模块进行相应的设计，最后通过一个主函（main）调用实现化简功能。

这四个模块为
第一模块，输入与建立最小项模块：建立c/c++的输入界面，将一般的逻辑函数和最小项表达式输入，并转换成计算机可识别的形式，若含约束项则一并输入，建立同下面模块的联系，保存最小项表达式和约束项表达式，将其代入下一模块操作中。

第二模块，调整最小项和约束项模块：用相应算法将逻辑函数表达式化成最小项的与-或式，若存在约束条件，则将最小项表达的约束项传给化简合并模块。

将传入的最小项与约束项链表重新用一个内容更丰富的结构体指针接受，并按“1”个数的多少进行排
序，为q-m化简作准备。

第三模块，化简合并模块：用q-m法化简逻辑表达式和约束项表达式，得到本质蕴含表。

第四模块，优化及输出模块：在本原蕴含表上采用行、列归并法对结果进行优化；若答案不唯一，则将多个答案全部输出；在答案中去掉单纯由约束项构成的蕴含项。

一、算法的具体实现：
输入与建立最小项模块
针对用户可能输入的情况进行判断。

如果用户想输入的是逻辑表达式（例如f=a+b+cd）则告诉用户以规定的形式——逻辑“与”用”&&”;“或”用“！！”；“非”用“！”；括号一律用“（”，“）”表示，刚才的例子可写成f=!(!(a+b)!!(c&&d))的形式。

如果用户想输入的是最小项，则在规定的范围内（如0 ~ 1023）允许输入，无论是那种情况都应该之后建立最小项表，并提示用户是否对输入约束项进行选择，输入的方法同上。

妥善保管好约束项，并把最小项和约束项传给下一模块。

（二）调整最小项和约束项模块
我们之所以要把这一模块提出来单独研究，是因为原有的tab 链表中所存在的信息确实有限，不能满足合并最小项，求质蕴涵的需求。

根据我们之前介绍的原理不难发现，在化简过程中，我们必须记住一些内容，比如每项中“1”的个数，是否参加合并，生成
项的来源？等等。

这些问题不解决或者不能很好的解决，我们的化简就会出现问题，优化则无从下手。

针对源程序代码分析，我们这里重新定义了一个结构体table，值得注意的是这里sco的作用，该结点链接的是该项合并前每项的信息纪录。

要把tab中的每个结点依次加入到table中，之后，再把约束项tab1的内容加在已有的table中，组成一个新的完整的table表。

我们通过语句：table1=table；把table1用来存放下步操作的结构体链表，空出table来存放tab1（约束项）的内容。

（三）化简合并模块
这一模块是我们整个程序的核心部分，他体现着q-m法的精髓，是对计算机能否成功化简多变量逻辑函数的有力证明，是整个程序的关键所在。

我们仔细读过该模块的原程序后就会发现：整个合并过程是分三个大的循环进行的。

最外层进行的是合并次数的循环，当所有可合并的最小项都不能再合并的时候（最后形成的临时链表t4为空），该层循环结束，这也标志着合并的结束；中间层次的循环是合并列的循环。

（四）优化及输出模块
这是整个程序的最后一个模块，操作的对象仍然是table1结构体链表。

我们要去掉其约束项，以数组的形式行列进行化简，并输出正确形式的信息显示给用户。

具体算法如下：
首先，为了体现比较友好的人机交流的氛围，程序作到这里我们可以将table1表所包含的质蕴涵信息输出一下,把每个结点的信息就显示给用户。

其次，对于table1表，我们还要多一种考虑，如果每项a[i]的信息中，合并后都不再有“0”或“1”的存在，说明了什么？是的，这种情况下就根本没有质蕴涵项，证明输入到计算机的逻辑表达式本身就是最简的，我们只需将其原原本本的输出就可以了（或输出一条语句，告诉用户“输入即输出”也可以）。

第三，这里我们将输入时所合并过来的约束项从table1表中删去。

具体做法：将table1表中来源在tab1中的去掉，并将tab中不在table1的最小项去掉。

将tab作为列（即源程序中的n）；table1作为行（即源程序中的m）,对新生成的二维数组行列合并，化简为最简形式。

最后，行列合并化简部分实质是对一个二维数组线性操作的过程，在次段程序里可以看出：a[i][j]我们是用(*(a+i*(n+1)+j))形式表示的，这里不在多讲。

优势评价
1、不同模块，不同类型数据链表过度自然。

2、针对具体问题具体分析，算法合理，问题解决较得当。

3、基本实现计算机智能化简多变量逻辑函数的任务.
4、模块设计合理.
5、同一问题,多种思路,多种算法进行研究取得了很好的效果.
三、编程中值得注意的问题
1、注意和“”的区别. 指的是从源程序文件中调用的内容; “”则是指从用户文件中调用的内容。

2、程序中多次定义全局变量(extern struct ),也多次调用,注意其作用.
3、“<<”左移位运算.在程序中通过它完成二进制取位信息的任务. 例:!2=!((n<<i1)&1).
4、注意“空”和“假”的区别。

在我们table的结构体中，我们用a[i]数组存放结点的信息，其中用“3”表示“空”；用“0”表示“假”。

“0”是指一个“假”的信息；而“空”则说明该位置没有信息。

请看例子：
for(i=1;i<n+1;i++)
{for(j=1;j<n+1;j++)
if(*(a+i*(n+1)+j)==1)k++;(i是行，j是列)
……}
我们在后面的程序中运用的就是通过这种方式构建二维数组的，这里的*(a+i*(n+1)+j)相当于a[i][j]。