离散数学耿素云PPT（第5版）ppt课件.ppt

《离散数学耿素云PPT（第5版）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.5联结词全功能集联结词全功能集与非联结词,或非联结词1联结词的全功能集定义设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.设S1,S2是两个联结词集合，且S1S2.若S1是全功能集，则S2也是全功能集.反之，若S2不是全功能集，则S1也不是全功能集.2联结词全功能集实例定理{,∧,∨}、{,∧}、{,∨}、{,→}都是联结词全功能集.证明每一个真值函数都可以用一个主析取范式表示,故{,∧,∨}是联

2、结词全功能集.p∨q(p∧q)，故{,∧}是全功能集.p∧q(p∨q)，故{,∨}是全功能集.p→qp∨q,故{,→}也是全功能集.3复合联结词与非式:pq(pq)或非式:pq(pq)和与,∧,∨有下述关系:p(p∧p)ppp∧q(p∧q)(pq)(pq)(pq)p∨q(p∧q)(p)(q)(pp)(qq)4pppp∧q(pp)(qq)p∨q(pq)(pq)定理{},{}是联结词全功能集.可以证明:{∧,∨}不是全功能

3、集,从而{∧},{∨}也不是全功能集.复合联结词(续)5例例将公式p∧q化成只含下列各联结词集中的联结词的等值的公式.(1){，∨}；(2){，→}；(3){↑}；(4){↓}.解(1)p∧q(p∨q).(2)p∧q(p∨q)(p→q).(3)p∧qp∧(q↑q)((p∧(q↑q)))(p↑(q↑q))(p↑(q↑q))↑(p↑(q↑q)).(4)p∧q(p∨q)(p)↓q(p↓p)↓q.61.6组合电路组合电路逻辑门与门,或门,非门,与非门,或非门奎因-莫可拉斯基方法7组合电路逻辑门:实

4、现逻辑运算的电子元件.与门,或门,非门.组合电路:实现命题公式的由电子元件组成的电路.与门或门非门xx∧yx∨yxyxyx8组合电路的例子(x∨y)∧x的组合电路xyxyx第一种画法第二种画法9例例楼梯的灯由上下2个开关控制,要求按动任何一个开关都能打开或关闭灯.试设计一个这样的线路.解x,y:开关的状态,F:灯的状态,打开为1,关闭为0.不妨设当2个开关都为0时灯是打开的.F=m0∧m3=(x∧y)∨(x∧y)10例(续)11设计组合电路步骤:1.构造输入输出表(问题的真值函数),2.写出主析取范式,3.化简.最简展开式:包含最少运算

5、的公式例当且仅当x=y=z=1或x=y=1且z=0时输出1.F=m6∨m7=(x∧y∧z)∨(x∧y∧z)4个与门,1个或门和一个非门Fx∧y一个与门12奎因-莫可拉斯基方法1.合并简单合取式生成所有可能出现在最简展开式中的项.2.确定最简展开式中的项.例求下述公式的最简展开式:F=(x1∧x2∧x3∧x4)∨(x1∧x2∧x3∧x4)∨(x1∧x2∧x3∧x4)∨(x1∧x2∧x3∧x4)∨(x1∧x2∧x3∧x4)∨(x1∧x2∧x3∧x4)∨(x1∧x2∧x3∧x4)13例(续)解编号极小项角码标记1x1∧x2

6、∧x3∧x41110*2x1∧x2∧x3∧x41011*3x1∧x2∧x3∧x40111*4x1∧x2∧x3∧x41010*5x1∧x2∧x3∧x40101*6x1∧x2∧x3∧x40011*7x1∧x2∧x3∧x40001*14例(续)标记*表示该项已被合并第一批第二批合并项项表示串标记合并项项表示串(1,4)x1∧x3∧x4110(3,5,6,7)x1∧x401(2,4)x1∧x2∧x3101(2,6)x2∧x3∧x4011(3,5)x1∧x2∧x4011*(3,6)x1∧x3∧x4011*

7、(5,7)x1∧x3∧x4001*(6,7)x1∧x2∧x4001*15例(续)选择(1,4),(2,4)和(3,5,6,7),或者(1,4),(2,6)和(3,5,6,7).最简展开式为F(x1∧x3∧x4)∨(x1∧x2∧x3)∨(x1∧x4)或F(x1∧x3∧x4)∨(x2∧x3∧x4)∨(x1∧x4)项覆盖运算符数x1∧x3∧x4(1,4)3x1∧x2∧x3(2,4)3x2∧x3∧x4(2,6)3x1∧x4(3,5,6,7)216