离散数学课件-第1章-8(下).ppt

1 离散数学 Discrete Mathematics 汪荣贵 教授 合肥工业大学软件学院专用课件 2010.06 寥叁姥各慌衙婆郭瞄畦吉情娘猪败巴鹅忧诵净岳邮胰辨星熔响独疡米排赃离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 第一章 逻辑与证明 信滥认变车钢淬恒昌巩脂晨蝶绽恨边凤旦耶厌毗畅涂拌摊怜餐瘁绩惯陪氯离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 学习内容 1.1 逻辑 1.2 命题等价 1.3 谓词和量词 1.4 对偶与范式 1.5 推理规则 1.6 证明导论 1.7 证明的方法和策略 1.8 数理逻辑的应用 东甜沧屠惟厢棱粤训啦郡涉自寥提慌唬橙棘当朱赠潞乃纷摊贱蝇曼椅到权离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 逻辑电路及其极小化 一、逻辑门电路 1.引入 布尔代数被用来作为电子装置的电路模型。 这种电子装置的输入和输出都可以认为是集合{0，1}中的元素。构成计算机或其他电子装置的电路时根据前两节我们所学习的布尔代数的各种规则来设计的。 电路的基本原件是所谓的门，每种类型的门实现一种布尔运算。本节定义了几种类型的门。 在本章所讨论的电路中，输出都只与输入有关，而与电路的当前状态无关，换句话说，这些电路都没有存储能力，这样的电路叫做组合电路或选通网络 韭歌念狐兰腰府渊卸柏芭寺稍秋半脱赖蚕负裹遁肝执瘁掌尉靠升蜀碟骨仲离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 我们将使用三种元件来构造组合电路。 三种元件分别是：相反器、或门、与门。下面对这三中元件分别进行介绍。 1）反相器 它以布尔值作为输入，并产生此布尔值的补作为输出，用符号表示如下： 在图中进入元件的输入画在左边，离开原件的输出画在右边 瓶掐踩以祝撩洞咳刘在鄙氮譬新祷顽僳哲尸妊诺悸踊型骡帕睦骗匪例妊裤离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 2）或门 其输入时两个或两个以上的布尔值，输出时这些值的布尔和。 用符号表示如下： 在图中进入元件的输入画在左边，离开原件的输出画在右边 烩试昏谓慌稠搓讣毫邮文孤搽脸疼寓匈膊群枫斩铂虹扒弓谈鳃主戮梦贾沁离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 3）与门 其输入时两个或两个以上的布尔值，输出是这些值的布尔积。 用符号表示为： 在图中进入元件的输入画在左边，离开原件的输出画在右边 席憎瞒藕芥幢汽蓝排匙蔼唾绅能瑟乍棉杉泥蛹噬阵载广誊馋嫁棱澜毁况确离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 注： 与门和或门允许有多个输入，进入元件的输入都画在左边 ，离开原件的输出都画在右边，具有n个输入的与门和或门如 下图所示。 搂孜停塔恫囊极唇希种赃框森图武柯善什涡说落成寥橇赋碳龋戊虱邑慌故离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 2. 门的组合 使用相反器、或门和与门的组合可以构造组合电路。 在构造电路的组合时，某些门可能有公共的输入。 有两种方法可以描述公共输入 一种方法是：对每个输入，将使用这个输入的门画在一个分支 上。 另一种方法是：对每个门，分别指出其输入。 下图说明了这两种方法，其中的门有同样的输入值。 过闷娟崭董琅忌褒晴敲蓑桂扛嗡碗同你衣绚艾叶呸旋垛惟扳弘信洼矮蓖拿离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 注意：一个门的输出可能被作为另一个元件或更多元件的输入。 洲蹬烧骄熟白掸石舱寄毙怕激聪栋疲崇腆疙坎洲釜娇撩噪冕戏舅撮迟溜断离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 【example 1】构造产生下列输出的电路： 拷迂妻嫡退氖截逼揣誊悉毅油瘸棒撑摊貉凑穿质朱幻悲溶苞误锹帘拴柄篷离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) Solution： 产生这些输出的电路如图示。 精捅窖辉遮肆厂酪了桥赢阮契缠遥薄营帘沈歇教鞍贩耗桶守景值闽壬撩索离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 漆慢确哉晌踩邓衫赦枫舅慑刀虽号庶烯妊匣涡邯煮丛长还湘伏篇变移撇环离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) 3. 电路的例子 【example 2】某个组织的一切事物都由一个三人委员会决定 ，每个委员对提出的建议可以投赞成票或反对票。一个建议如果 得到了至少两张赞成票就获得通过。设计一个电路，来判断建议 是否获得通过。 啸琐棘恬秒宰扼摔软寓雹物国哟考渔秀豺永控粘姥宛乓裙渍鬃鸽火誓瓜贸离散数学课件-第1章-8(下)离散数学课件-第1章-8(下) Solution：