离散数学课件-第1章-8(下).ppt
《离散数学课件-第1章-8(下).ppt》由会员分享,可在线阅读,更多相关《离散数学课件-第1章-8(下).ppt(89页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1离散数学Discrete Mathematics 第一章第一章 逻辑与证明逻辑与证明&学习内容学习内容1.1 1.1 逻辑逻辑逻辑逻辑1.2 1.2 命题等价命题等价命题等价命题等价1.3 1.3 谓词和量词谓词和量词谓词和量词谓词和量词 1.4 1.4 对偶与范式对偶与范式对偶与范式对偶与范式1.5 1.5 推理规则推理规则推理规则推理规则1.6 1.6 证明导论证明导论证明导论证明导论1.7 1.7 证明的方法和策略证明的方法和策略证明的方法和策略证明的方法和策略1.8 1.8 数理逻辑的应用数理逻辑的应用数理逻辑的应用数理逻辑的应用&逻辑电路及其极小化路及其极小化一、逻辑门电路一、逻辑
2、门电路 1.引入引入布尔代数被用来作为电子装置的电路模型。布尔代数被用来作为电子装置的电路模型。这种电子装置的输入和输出都可以认为是集合这种电子装置的输入和输出都可以认为是集合00,1 1中的元素。构中的元素。构成计算机或其他电子装置的电路时根据前两节我们所学习的布尔代成计算机或其他电子装置的电路时根据前两节我们所学习的布尔代数的各种规则来设计的。数的各种规则来设计的。电路的基本原件是所谓的电路的基本原件是所谓的门门,每种类型的门实现一种布尔运算。本,每种类型的门实现一种布尔运算。本节定义了几种类型的门。节定义了几种类型的门。在本章所讨论的电路中,输出都只与输入有关,而与电路的当前在本章所讨论
3、的电路中,输出都只与输入有关,而与电路的当前状态无关,换句话说,这些电路都没有存储能力,这样的电路叫做状态无关,换句话说,这些电路都没有存储能力,这样的电路叫做组合电路组合电路或或选通网络选通网络我们将使用三种元件来构造组合电路。我们将使用三种元件来构造组合电路。三种元件分别是:三种元件分别是:相反器、或门、与门相反器、或门、与门。下面对这三中元。下面对这三中元件分别进行介绍。件分别进行介绍。1)反相器)反相器 它以布尔值作为输入,并产生此布尔值的补作为输出,用它以布尔值作为输入,并产生此布尔值的补作为输出,用符号表示如下:符号表示如下:在图中进入元件的输入画在左边,离开原件的输出画在右边在图
4、中进入元件的输入画在左边,离开原件的输出画在右边2)或门)或门 其输入时两个或两个以上的布尔值,输出时这些值的布尔和。其输入时两个或两个以上的布尔值,输出时这些值的布尔和。用符号表示如下:用符号表示如下:在图中进入元件的输入画在左边,离开原件的输出画在右边在图中进入元件的输入画在左边,离开原件的输出画在右边3)与门)与门 其输入时两个或两个以上的布尔值,输出是这些值的布尔积。其输入时两个或两个以上的布尔值,输出是这些值的布尔积。用符号表示为:用符号表示为:在图中进入元件的输入画在左边,离开原件的输出画在右边在图中进入元件的输入画在左边,离开原件的输出画在右边注:注:与门和或门允许有多个输入,进
5、入元件的输入都画在左边与门和或门允许有多个输入,进入元件的输入都画在左边,离开原件的输出都画在右边,具有,离开原件的输出都画在右边,具有n个输入的与门和或门如个输入的与门和或门如下图所示。下图所示。2.门的组合门的组合使用相反器、或门和与门的组合可以构造组合电路。使用相反器、或门和与门的组合可以构造组合电路。在构造电路的组合时,某些门可能有公共的输入。在构造电路的组合时,某些门可能有公共的输入。有两种方法可以描述公共输入有两种方法可以描述公共输入 一种方法是:对每个输入,将使用这个输入的门画在一个分支一种方法是:对每个输入,将使用这个输入的门画在一个分支 上。上。另一种方法是:对每个门,分别指
6、出其输入。另一种方法是:对每个门,分别指出其输入。下图说明了这两种方法,其中的门有同样的输入值。下图说明了这两种方法,其中的门有同样的输入值。注意:注意:一个一个门的的输出可能被作出可能被作为另一个元件或更多元件的另一个元件或更多元件的输入。入。【example 1】构造产生下列输出的电路:构造产生下列输出的电路:Solution:产生这些输出的电路如图示。产生这些输出的电路如图示。3.电路的例子电路的例子【example 2】某个组织的一切事物都由一个三人委员会决定某个组织的一切事物都由一个三人委员会决定,每个委员对提出的建议可以投赞成票或反对票。一个建议如果,每个委员对提出的建议可以投赞成
7、票或反对票。一个建议如果得到了至少两张赞成票就获得通过。设计一个电路,来判断建议得到了至少两张赞成票就获得通过。设计一个电路,来判断建议是否获得通过。是否获得通过。Solution:如果第一个委员投赞成票,则令如果第一个委员投赞成票,则令x=1;如果这个委员投反对如果这个委员投反对票,则令票,则令x=0。如果第二个委员投赞成票,则令。如果第二个委员投赞成票,则令y=1;若其投反若其投反对票,则令对票,则令y=0。同样道理,第三个委员投赞成票。同样道理,第三个委员投赞成票 则令则令z=1,反反之,之,z=0。必须设计一个电路使得对于输入必须设计一个电路使得对于输入x、y、z,如果其中至少有,如果
8、其中至少有两个为两个为1,则此电路产生输入,则此电路产生输入1。具有这样的输出值的一个布。具有这样的输出值的一个布尔函数表示是尔函数表示是xy+yz+xz。实现这个函数的电路如下图所示。实现这个函数的电路如下图所示。【example 3】有时候灯具需要由多个开关来控制,因此有有时候灯具需要由多个开关来控制,因此有必要设计这样的电路:当灯市关闭时,敲击任何一个开关都必要设计这样的电路:当灯市关闭时,敲击任何一个开关都可以打开此灯;反之,当灯市打开时,敲击任何一个开关都可以打开此灯;反之,当灯市打开时,敲击任何一个开关都可以关闭此灯。在有两个开关或三个开关两种情形下,设计可以关闭此灯。在有两个开关
9、或三个开关两种情形下,设计电路来完成这个任务。电路来完成这个任务。18Solution:首先设计使用两个开关的电路来控制灯具。首先设计使用两个开关的电路来控制灯具。当第一个开关关闭时,令当第一个开关关闭时,令x=1;当它打开时,令;当它打开时,令x=0。当第二。当第二个开关关闭时,令个开关关闭时,令y=1,当它打开时,令当它打开时,令y=0.当灯市打开时,令当灯市打开时,令F(x,y)=1;当灯是关闭时,令当灯是关闭时,令F(x,y)=0。我们可以随意地假定:当两个开关都是关闭时,灯是打开的我们可以随意地假定:当两个开关都是关闭时,灯是打开的,即,即F(x,y)=1.这个假定决定了这个假定决定
10、了F的所有其他值:当两个开关中的所有其他值:当两个开关中有一个是打开的时候,灯变灭了,故有一个是打开的时候,灯变灭了,故F(1,0)=F(0,1)=0;当第二;当第二个开关也被打开的时候,灯又变亮了,故个开关也被打开的时候,灯又变亮了,故F(0,0)=1.下表列出了这些值,我们可以看到下表列出了这些值,我们可以看到 实现这个函数的电路如下所示。实现这个函数的电路如下所示。19 现在设计有三个开关的电路。现在设计有三个开关的电路。设设x、y和和z是三个布尔变元,它们分别指出这三个开关是否是关闭是三个布尔变元,它们分别指出这三个开关是否是关闭的。当第一个开关处于关闭时,令的。当第一个开关处于关闭时
11、,令x=1;当它处于接通时,令当它处于接通时,令x=0.当第当第二个开关处于关闭时,令二个开关处于关闭时,令y=1;当它处于接通时,令当它处于接通时,令y=0.当第三个开关当第三个开关处于关闭时,令处于关闭时,令z=1;当它处于接通时,令当它处于接通时,令z=0。灯亮时,令灯亮时,令F(x,y,z)=1;灯不亮时,令;灯不亮时,令F(x,y,z)=0.当所有开关都关当所有开关都关闭时,我们可以随意指定灯是亮的,即闭时,我们可以随意指定灯是亮的,即F(1,1,1)=1,这确定了这确定了F的其他值的其他值。当一个开关被接通时,灯就变灭,故。当一个开关被接通时,灯就变灭,故F(1,1,0)=F(1,
12、0,1)=F(0,1,1)=0.当又一个开关被接通时,灯又变亮了,当又一个开关被接通时,灯又变亮了,F(1,0,0)=F(0,1,0)=F(0,0,1)=1.最后当三个开关都接通时,灯又变灭了,故最后当三个开关都接通时,灯又变灭了,故F(0,0,0)=0.这个函数的值如下表所示。这个函数的值如下表所示。函数函数F可以表示成积之和展开式:可以表示成积之和展开式:实现这个函数的电路如下所示实现这个函数的电路如下所示4.加法器加法器 一下我们将说明如何用逻辑电路从两个正整数的二进制编码一下我们将说明如何用逻辑电路从两个正整数的二进制编码来执行加法。来执行加法。我们的方法是先构造一些分支电路,然后再从
13、这些分支电路我们的方法是先构造一些分支电路,然后再从这些分支电路来构造加法电路。来构造加法电路。首先构造电路来计算首先构造电路来计算x+yx+y,其中,其中x x和和y y是两个二进制数字。因为是两个二进制数字。因为x x和和y y的值为的值为0 0或或1 1,此电路的输入就是,此电路的输入就是x x和和y y输出由两个二进制数输出由两个二进制数字字s s和和c c构成,其中构成,其中s s和和c c分别是和位与进位。分别是和位与进位。因为这种电路具有多个输出,故称为因为这种电路具有多个输出,故称为多重输出电路多重输出电路。又由于。又由于此电路只是将两个二进制数字相加,而没有开率以前加法所产生
14、此电路只是将两个二进制数字相加,而没有开率以前加法所产生的进位,所以这样的电路称为的进位,所以这样的电路称为半加法器半加法器。右表显示了半加法器的右表显示了半加法器的输入和输出,由此表可以输入和输出,由此表可以看出看出c=xy且且下图显示的电路计算了下图显示的电路计算了x和和y的和位的和位s与进位与进位c。当两个二进制数字与一个进位当两个二进制数字与一个进位相加时,我们用相加时,我们用全加法器全加法器来计算和来计算和位与进位。位与进位。全加法器的输入时这两个二进制全加法器的输入时这两个二进制数字数字x和和y以及此进位以及此进位ci,输出是和,输出是和位位s与新的进位与新的进位ci+1.全加法器
15、的输全加法器的输入和输出如右表所示入和输出如右表所示 全加法器的两个输出(和位全加法器的两个输出(和位s与进位与进位ci+1)可分别由积之和展开式)可分别由积之和展开式 和和表示。但我们并不直接构造全加法器,而是使用半加法器来产生所需表示。但我们并不直接构造全加法器,而是使用半加法器来产生所需的输出。的输出。使用半加法器构造全加法器的方法如下图所示使用半加法器构造全加法器的方法如下图所示 最后下图说明了怎样用全加法器和半加法器来计算两个最后下图说明了怎样用全加法器和半加法器来计算两个3位二位二进制整数进制整数(x2x1x0)2与与(y2y1y0)2和和(s3s2s1s0)2.注意,和中的最高位
16、注意,和中的最高位s3是由进位是由进位c2产生的。产生的。【练习练习】求以下所给电路的输出。求以下所给电路的输出。使用反相器、与门和或门构造产生下列输出的电路。使用反相器、与门和或门构造产生下列输出的电路。二、电路的极小化二、电路的极小化1.引入引入组合电路的有效性依赖于门的个数及安排。组合电路的有效性依赖于门的个数及安排。在组合电路的设计过程中,首先构造一个表,对于每种可能在组合电路的设计过程中,首先构造一个表,对于每种可能的输入值,此表说明对应的输出值。对于任一个电路,总可以用的输入值,此表说明对应的输出值。对于任一个电路,总可以用“积之和展开式积之和展开式”找到一组逻辑门来实现这个电路。
17、找到一组逻辑门来实现这个电路。但是,积之和展开式可能包含许多不必要的项。在一个积之但是,积之和展开式可能包含许多不必要的项。在一个积之和展开式中,若其中的一些项只在一个变元处不一样,即在某个和展开式中,若其中的一些项只在一个变元处不一样,即在某个项中此变元本身出现,而在另一个项中次变元的补出现,则这些项中此变元本身出现,而在另一个项中次变元的补出现,则这些项可以合并。项可以合并。例如,考虑这样的电路,它输出例如,考虑这样的电路,它输出1当且仅当当且仅当x=y=z=1,或或x=z=1且且y=0.此电路的积之和展开式为此电路的积之和展开式为 在这个展开式的两在这个展开式的两个积中,只有一个变元以不
18、同的形式出现,即个积中,只有一个变元以不同的形式出现,即y。它们可以如下。它们可以如下合并:合并:这样,这样,xz也是一个表示这个电路的布尔表达式,但包含更少也是一个表示这个电路的布尔表达式,但包含更少的算子。下面画出这个电路的两种不同实现的图进行比较,第二的算子。下面画出这个电路的两种不同实现的图进行比较,第二个电路只使用一个门,但第一个却使用了三个门和一个反相器。个电路只使用一个门,但第一个却使用了三个门和一个反相器。这个例子个例子说明,在一个明,在一个电路的路的积之和展开式中,将一些之和展开式中,将一些项合并会合并会导出出这个个电路的更路的更简单的表达式。的表达式。下面我们将描述化简积之
19、和展开式的两个不同的方法。下面我们将描述化简积之和展开式的两个不同的方法。1.卡诺图(或卡诺图(或k图)图)(在少于在少于6个变量的最小化电路中非常有用个变量的最小化电路中非常有用)2.奎因奎因-莫可拉斯基方法。莫可拉斯基方法。这两种方法的目的都是为了产生布尔积的布尔和,使其所包含这两种方法的目的都是为了产生布尔积的布尔和,使其所包含的文字之积的个数最少,从而使得这些积中在表示布尔函数的积的文字之积的个数最少,从而使得这些积中在表示布尔函数的积之和中所包含的文字个数最少。寻求这种积之和的过程称为之和中所包含的文字个数最少。寻求这种积之和的过程称为布尔布尔函数的最小化函数的最小化。2.卡诺图卡诺
20、图对于表示电路的一个布尔表达式,为了减少其中项的个数,对于表示电路的一个布尔表达式,为了减少其中项的个数,有必要去发现可以合并的项。如果布尔函数所包含的变元相有必要去发现可以合并的项。如果布尔函数所包含的变元相对较少,可以用一种图形来发现能被合并的项,此法称为对较少,可以用一种图形来发现能被合并的项,此法称为卡卡诺图诺图。卡诺图给出了一种化简积之和展开式的可视化方法,但此法卡诺图给出了一种化简积之和展开式的可视化方法,但此法不适用于将化简过程机械化。不适用于将化简过程机械化。下面首先说明怎么用卡诺图来化简包含两个变元的布尔函数下面首先说明怎么用卡诺图来化简包含两个变元的布尔函数的展开式。的展开
21、式。在具有两个变元在具有两个变元x和和y的布尔函数的积之和展开式种,有四种可能的的布尔函数的积之和展开式种,有四种可能的小项。具有这两个边缘的布尔函数的卡诺图由四个方格组成,如果一小项。具有这两个边缘的布尔函数的卡诺图由四个方格组成,如果一个小项在此展开式中出现,则表示这个小项的方格就被放置个小项在此展开式中出现,则表示这个小项的方格就被放置1,如果一,如果一些方格所表示的小项只在一个处不一样,则称这些方格是些方格所表示的小项只在一个处不一样,则称这些方格是相邻的相邻的。例如,表示例如,表示 的方格与表示的方格与表示xy的方格及表示的方格及表示 的方格都相邻。的方格都相邻。四个方格及其表示的项
22、如右图所示。四个方格及其表示的项如右图所示。【example 1】找出下列各式的卡诺图:找出下列各式的卡诺图:Solution:当一个方格所表示的小项在积之和展开式中出现时,我们就在这当一个方格所表示的小项在积之和展开式中出现时,我们就在这个方格中放置一个个方格中放置一个1.三个卡诺图如图所示三个卡诺图如图所示 我们可以从卡诺图中识别出能够合并的小项。在卡诺图中,一旦我们可以从卡诺图中识别出能够合并的小项。在卡诺图中,一旦两个方格式相邻的,则由这两个方格所表示的小项就可被合并成一个两个方格式相邻的,则由这两个方格所表示的小项就可被合并成一个积,且此积只涉及其中的一个变元。积,且此积只涉及其中的
23、一个变元。例如例如 和和 是由两个相邻的方格表示的他们可以合并成是由两个相邻的方格表示的他们可以合并成一个项,即布尔表达式一个项,即布尔表达式1,它不涉及任何变元。,它不涉及任何变元。在卡诺图中如果一些小项能够合并,则在卡诺图中,我们将在卡诺图中如果一些小项能够合并,则在卡诺图中,我们将表示这些小项的方格所组成的块用圆圈圈起来,然后找出对应的表示这些小项的方格所组成的块用圆圈圈起来,然后找出对应的积之和,其目的是找出可能最大的块,以及以最少的块来覆盖所积之和,其目的是找出可能最大的块,以及以最少的块来覆盖所有的有的1,在此过程中,首先使用最大的块,并总是使用可能最大,在此过程中,首先使用最大的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课件
限制150内