离散数学-耿素云(第5版)1.5-6学习资料_第1页
离散数学-耿素云(第5版)1.5-6学习资料_第2页
离散数学-耿素云(第5版)1.5-6学习资料_第3页
离散数学-耿素云(第5版)1.5-6学习资料_第4页
离散数学-耿素云(第5版)1.5-6学习资料_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

11.5联结词全功能集

联结词全功能集与非联结词,或非联结词第一页,共16页。2联结词的全功能集定义设S是一个联结词集合,如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示,则称S是联结词全功能集.说明(shuōmíng):若S是联结词全功能集,则任何命题公式都可用S中的联结词表示.设S1,S2是两个联结词集合,且S1S2.若S1是全功能集,则S2也是全功能集.反之,若S2不是全功能集,则S1也不是全功能集.第二页,共16页。3联结词全功能集实例(shílì)定理{,∧,∨}、{,∧}、{,∨}、{,→}都是联结词全功能集.证明每一个真值函数都可以(kěyǐ)用一个主析取范式表示,故{,∧,∨}是联结词全功能集.p∨q(p∧q),故{,∧}是全功能集.p∧q(p∨q),故{,∨}是全功能集.p→qp∨q,故{,→}也是全功能集.第三页,共16页。4复合(fùhé)联结词与非式:pq(pq)或非式:pq(pq)和与,∧,∨有下述关系(guānxì):p(p∧p)ppp∧q(p∧q)(pq)(pq)(pq)p∨q(p∧q)(p)(q)(pp)(qq)第四页,共16页。5pppp∧q(pp)(qq)p∨q(pq)(pq)定理{},{}是联结词全功能集.可以证明(zhèngmíng):{∧,∨}不是全功能集,从而{∧},{∨}也不是全功能集.复合(fùhé)联结词(续)第五页,共16页。6例例将公式(gōngshì)p∧q化成只含下列各联结词集中的联结词的等值的公式(gōngshì).(1){,∨};(2){,→};(3){↑};(4){↓}.解(1)p∧q(p∨q).(2)p∧q(p∨q)(p→q).(3)p∧qp∧(q↑q)((p∧(q↑q)))(p↑(q↑q))(p↑(q↑q))↑(p↑(q↑q)).(4)p∧q(p∨q)(p)↓q(p↓p)↓q.第六页,共16页。71.6组合(zǔhé)电路组合电路逻辑(luójí)门与门,或门,非门,与非门,或非门奎因-莫可拉斯基方法第七页,共16页。组合(zǔhé)电路逻辑门:实现逻辑运算的电子元件.与门,或门,非门.组合(zǔhé)电路:实现命题公式的由电子元件组成的电路.8与门或门非门xx∧yx∨yxyxyx第八页,共16页。组合电路(diànlù)的例子9(x∨y)∧x的组合(zǔhé)电路xyxyx第一种画法(huàfǎ)第二种画法第九页,共16页。例例楼梯的灯由上下2个开关控制,要求(yāoqiú)按动任何一个开关都能打开或关闭灯.试设计一个这样的线路.解x,y:开关的状态,F:灯的状态,打开为1,关闭为0.不妨设当2个开关都为0时灯是打开的.

F=m0∧m3=(x∧y)∨(x∧y)10第十页,共16页。例(续)11第十一页,共16页。设计(shèjì)组合电路步骤:1.构造输入输出表(问题的真值函数),2.写出主析取范式,3.化简.最简展开式:包含最少运算(yùnsuàn)的公式例当且仅当x=y=z=1或x=y=1且z=0时输出1.F=m6∨m7=(x∧y∧z)∨(x∧y∧z)4个与门,1个或门和一个非门Fx∧y一个与门12第十二页,共16页。奎因-莫可拉斯基方法(fāngfǎ)1.合并简单合取式生成(shēnɡchénɡ)所有可能出现在最简展开式中的项.2.确定最简展开式中的项.13例求下述公式(gōngshì)的最简展开式: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)第十三页,共16页。例(续)解14编号

极小项

角码

标记

1x1∧x2∧x3∧x4

1110*2x1∧x2∧x3∧x41011*3x1∧x2∧x3∧x40111*4x1∧x2∧x3∧x41010*5x1∧x2∧x3∧x40101*6x1∧x2∧x3∧x40011*7x1∧x2∧x3∧x40001*第十四页,共16页。例(续)标记*表示(biǎoshì)该项已被合并15第一批

第二批合并项

表示串

标记

合并项

表示串(1,4)x1∧x3∧x4110(3,5,6,7)x1∧x40

1(2,4)x1∧x2∧x3101(2,6)x2∧x3∧x4

011(3,5)x1∧x2∧x4011*(3,6)x1∧x3∧x4011*(5,7)x1∧x3∧x4001*(6,7)x1∧x2∧x4001*第十五页,共16页。例(续)选择(xuǎnzé)(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)16项覆盖运算符数

x1∧x3∧x4(1,4)

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论