逻辑代数化简的计算机实现
【摘　要】本文阐述了化简逻辑代数的基本原理,在代数法和卡诺图法化简逻辑代数的基础上,提出运用计算机软件实现化简逻辑代数的方案。详细介绍利用计算机软件来实现化简模块的设计与实施过程。通过此方法可以使化简更准确、高效。
【关键词】逻辑代数；卡诺图；最小项；质蕴涵项
在实际的电路设计中,往往要根据逻辑函数要求，归纳出表达式及画出相应的逻辑电路。但直接得出的表达式往往不是最简形式,这样会使电路复杂,所需电子元器件也随之增加。因此需对逻辑代数进行必要的化简,使每个逻辑单元相对简单化、合理化。
通常,人们采用代数法和卡诺图法化简。用代数法化简需熟练掌握逻辑代数的基本定律,而且需要一些化简技巧,特别是每次经代数法化简后，得到的表达式是否为最简式较难掌握。卡诺图法虽然可以解决上述问题,但卡诺圈易圈漏、圈错或产生逻辑覆盖。为消除这种人为引起的错误,本文提出基于卡诺图原理用计算机编程实现逻辑代数化简的方法。而本文着重分析的是其中“化简逻辑代数”的部分。它对于整个化简过程有着承上启下的作用。
1　卡诺图化简的基本原理
&笔者按照列表法的化简思路来进行分析，而列表法化简源于卡诺图法化简，因而在此介绍一下卡诺图化简的原理。
&&&卡诺图是逻辑函数的一种图形表示。一个逻辑函数的卡诺图就是将此函数的最小项表达式中的各最小项相应地填入一个方格图内，此方格图称为卡诺图。卡诺图的构造特点使卡诺图具有一个重要性质：可以从图形上直观地找出相邻最小项。两个相邻最小项可以合并为一个与项并消去一个变量。
例如：给定一组待化简的逻辑函数F(A,B,C,D)=∑m(0,3,5,6,7,10,11,13,15)，其卡诺图化简过程为：
如图1（１）中所描述的是函数F中所对应的数值,其间标有“1方格”的项就是函数中各个数值在卡诺圈中的描述；而图1（２）中有五个卡诺圈,所描述的就是全部质蕴涵项；在图1（３）中标有带有“*”号的最小项为必要最小项，它们分别是最小项m0，m3，m5，m6，m10，m13。由此可见,卡诺图上圈出的五个质蕴涵项均为必要质蕴涵项。最后的结果即为：F(A,B,C,D)=ＡＢＣＤ+ＡBC+AＢC+BD+CD
图1　函数F(A,B,C,D)的卡诺图化简流程图
由此可知卡诺图化简逻辑函数的一般步骤为：首先做出函数的卡诺图，然后在卡诺图上圈出函数的全部质蕴涵项，接着从全部质蕴涵项中找出所有必要质蕴涵项，最后若函数的所有必要质蕴涵项尚不能覆盖卡诺图上的所有“1方格”，则从剩余质蕴涵中找出最简的所需质蕴涵项，使它和必要质蕴涵项一起构成函数的最小覆盖，即最简的质蕴涵项集。
2　系统运行(化简逻辑代数部分)流程图
图2　化简流程图
３　计算机实现逻辑代数化简的主要流程
３.１　十进制表示的最小项转换为二进制表示的最小项程序设计
在化简前将给定的逻辑代数表达式（一般为十进制数）转换为二进制数。用数组num[i]来接受输入的一组十进制数,然后由trans()函数实现十进制到二进制的转换，最后输出。
算法1：十进制转换为二进制算法
{ for(i=0;i
num[i]动态存贮所输入的数据；
{trans(num[i])&&
实现转换过程的核心;q++控制转换的过程的循环;&&&&
while(n!=0)在trans()函数中运用bin[i++]=n%2及n=n/2来实现转换操作; };
}转换完 (j=i-1;j&=0;j--) 来控制二进制数输出时的循环;
3.2　全部质蕴涵项程序设计
算法思想：逐个检查标1方格的合并方向,先圈没有或只有一个合并方向的标1小方格,后圈可能合并方向较少的标1小方格,最后圈那些可能合并方向较多的标1小方格,这样所得的卡诺圈都是质蕴涵项。即画卡诺圈时，先画大圈，再画小圈，而且大圈中不再有小圈。
在算法2中,Remainder[]存放待处理元素集,Rlength存放待处理元素集长度,Combination[]存放合并结果集,Clength存放合并集长度,notsingle标志有无相邻项。
算法2：化简算法
　　{ notsingle=0;
　　　element=Remainder[1];
在Remainder[]集中查找所有与element相邻项,若找到,则依次合并,并置ntsingle=1;
　　　if(合并结果未出现在Combination[]集中)合并结果加入到Combination[]集;
　　if(notsingle==0,element未出现在结果集中)将element加入到Combination[]集;
　　　i=i+1;
３.3　求必要质蕴涵项
将每个素蕴涵项中所包含的最小项求出。若某个素蕴涵项所包含的最小项至少有一个未被其它素蕴涵项包括,那么它就是实质素蕴涵项；若实质素蕴涵项集包含了所有标1小方格,那么它就为所求的最小覆盖,否则就需求最小覆盖。
３.4　求最小覆盖
最小覆盖就是要覆盖全部最小项，又要使质蕴涵项数目达到最少。这样必要质蕴涵项就是必须选用的质蕴涵项。最终化简的结果通常为最简与或表达式。
在覆盖所有最小项的前提下,卡诺圈的个数达到最少，每个卡诺圈达到最大。
４　实现计算机逻辑代数化简的实现重点
在用C++的描述中，多次涉及到数组，函数调用以及For循环的使用,因而必须有清晰的思路，才能得以程序的实现。要清晰的知道二进制数在转换过程中各个位的存储原理，以及多次循环赋值的描述，空间的申请与释放等。
逻辑代数化简过程中的实现：求“全部质蕴涵项程序的实现”是一难点.根据列表法的化简思想，必须将一组二进制数多次分组，多次循环对比，然后在对比的基础上找出这一组二进制数中有且仅有一位相异的，然后再进行相消合并处理。
５　结束语
利用计算机软件化简逻辑代数克服了代数法和卡诺图法以及列表法化简的不足,可适于多个变量的逻辑代数化简,而且对于化简结果不单一的逻辑表达式,可输出所有的化简结果。使用该方法化简逻辑代数结果准确、高效。
【参考文献】
［1］王玉龙.数字逻辑[Ｍ].北京:高等教育出版社,1987.
［2］毛法尧.数字逻辑[Ｍ].武汉:华中科技大学出版社,1996.
［3］郭京蕾.软件法化简逻辑代数[J].武汉理工大学学报:信息与管理工程版,2003(03).
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。谈逻辑代数的化简_论文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
谈逻辑代数的化简
中国最大最早的专业内容网站|
总评分0.0|
&&电路的化简可以降低成本、优化生产工艺,是生产中的重要部分。通过对两种化简方法的比较,总结出卡诺图法化简的优势。
试读已结束，如果需要继续阅读或下载，敬请购买
定制HR最喜欢的简历
你可能喜欢
您可以上传图片描述问题
联系电话：
请填写真实有效的信息，以便工作人员联系您，我们为您严格保密。文档分类：
下载后只包含 1 个 DOC 格式的文档，没有任何的图纸或源代码，
下载前请先预览，预览内容跟原文是一样的，在线预览图片经过高度压缩，下载原文更清晰。
您的浏览器不支持进度条
下载文档到电脑，查找使用更方便
还剩?页未读，继续阅读
播放器加载中，请稍候...
该用户其他文档
下载所得到的文件列表逻辑代数化简练习.doc
文档介绍：
逻辑代数化简练习
一、选择题
1. 以下表达式中符合逻辑运算法则的是。
A.C·C=C2 B.1+1=10 C.0&1 D.A+1=1
2. 逻辑变量的取值1和0可以表示: 。
A.开关的闭合、断开 B.电位的高、低 C.真与假 D.电流的有、无
3. 当逻辑函数有n个变量时,共有个变量取值组合?
A. n B. 2n C. n2 D. 2n
4. 逻辑函数的表示方法中具有唯一性的是。
A .真值表 B.表达式 C.逻辑图 D.卡诺图
5.F=A+BD+CDE+D= 。
A. B. C. D.
6.逻辑函数F= = 。
A.B B.A C. D.
7.求一个逻辑函数F的对偶式,可将F中的。
A .“·”换成“+”,“+”换成“·”
B.原变量换成反变量,反变量换成原变量
C.变量不变
D.常数中“0”换成“1”,“1”换成“0”
E.常数不变
8.A+BC= 。
A .A+B B.A+C C.(A+B)(A+C) D.B+C
9.在何种输入情况下,“与非”运算的结果是逻辑0。
A.全部输入是0 B.任一输入是0 C.仅一输入是0 D.全部输入是1
10.在何种输入情况下,“或非”运算的结果是逻辑0。
A.全部输入是0 B.全部输入是1 C.任一输入为0,其他输入为1 D.任一输入为1
二、判断题(正确打√,错误的打×)
1. 逻辑变量的取值,1比0大。( )。
2. 异或函数与同或函数在逻辑上互为反函数。( )。
3.若两个函数具有相同的真值表,则两个逻辑函数必然相等。( )。
4.因为逻辑表达式A+B+AB=A+B成立,所以AB=0成立。( )
5.若两个函数具有不同的真值表,则两个逻辑函数必然不相等。( )
6.若两个函数具有不同的逻辑函数式,则两个逻辑函数必然不相等。( )
7.逻辑函数两次求反则还原,逻辑函数的对偶式再作对偶变换也还原为它本身。( )
8.逻辑函数Y=A+B+C+B已是最简与或表达式。( )
9.因为逻辑表达式A+B +AB=A+B+AB成立,所以A+B= A+B成立。( )
10.对逻辑函数Y=A+B+C+B利用代入规则,令A=BC代入,得Y= BC+B+C+B=C+B成立。( )
三、填空题
1. 逻辑代数又称为代数。最基本的逻辑关系有、、三种。常用的几种导出的逻辑运算为、、、、。
2. 逻辑函数的常用表示方法有、、。
3. 逻辑代数中与普通代数相似的定律有、、。摩根定律又称为。
4. 逻辑代数的三个重要规则是、、。
5.逻辑函数F=+B+D的反函数= 。
6.逻辑函数F=A(B+C)·1的对偶函数是。
7.添加项公式AB+C+BC=AB+C的对偶式为。
8.逻辑函数F=+A+B+C+D= 。
9.逻辑函数F== 。
10.已知函数的对偶式为+,则它的原函数为。
四、思考题
1. 逻辑代数与普通代数有何异同?
2. 逻辑函数的三种表示方法如何相互转换?
3. 为什么说逻辑等式都可以用真值表证明?
4. 对偶规则有什么用处?
5.化简逻辑函数表达式的意义是什么?什么叫最简的与或表达式?
6.公式化简法有什么优点和缺点?
7.什么叫最小项?最小项有什么性质?你能根据逻辑函数的定义说明函数最小项与或表达式的唯一性吗?
8.什么叫卡诺图?卡诺图上变量取值的排列有什么规律?
9.卡诺图中最小项(小方块)合并的规律是什么?几何位置上相邻的三、五、六、七、九、十、十五个最小项(小方块)能够合并在一起吗?为什么?
10.在卡诺图中约束项一般是怎样处理的?为什么?
11.在化简具有约束的逻辑函数时,充分利用约束条件有什么好处?
12.利用约束条件(或约束项)化简得到的函数表达式成立的先决条件是什么?
五、练习题
1.为使F=A ,则B应为何值(高电平或低电平)?
2.指出图中各TTL门电路的输出是什么状态(高电平、低电平、高阻)?
3.指出图中各CMOS门电路的输出是什么状态?
4. 用公式法将下列函数化为最简与或表达式。
1) Y=AB+C+AC+B
2)Y= AC+BC+BD+CD+A(B+C)+ABCD+ABDE
3)Y=AC+ABC+ACD+CD
4)Y= A(C⊕D)+BCD+ACD+ABCD
5. 用卡诺图化简法将函数化为最简与或表达式。
1)Y=BD+ABCD+ABC D+ABC D+ABCD
2)Y(A,B,C,D)=∑(m3,m5,m6,m7,m10)
给定约束条件为m0+m1+m2+m4+m8=0
3)Y=BC D+AB+AC D+ABC
4)Y(A,B,C,D)=∑(m1,m4,m8,m9,m12)
6. 根据要求完成下列各题:
内容来自淘豆网www.taodocs.com转载请标明出处.
文件大小：1.25 MB
下载次数：第四章：逻辑代数及其化简（5)ppt下载_爱问共享资料
第四章：逻辑代数及其化简（5).ppt
第四章：逻辑代数及其化简（5).ppt
第四章：逻辑代数及其化简（5).ppt
简介：本文档为《第四章：逻辑代数及其化简（5)ppt》，可适用于高等教育领域，主题内容包含前面所学的函数化简均假定输入信号既提供原变量又提供反变量。在实际逻辑电路设计中只有原变量输入没有反变量输入。因此在函数化简时采取适当方法就能得到只有符等。
侵权或盗版
*若权利人发现爱问平台上用户上传内容侵犯了其作品的信息网络传播权等合法权益时，请按照平台要求书面通知爱问！
赌博犯罪类
添加成功至
资料评价：
所需积分：0}