《谭浩强c程序设计第四版ppt教案资料.ppt》由会员分享，可在线阅读，更多相关《谭浩强c程序设计第四版ppt教案资料.ppt（123页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、谭浩强C程序设计第四版PPT2.1.1 逻辑代数的基本运算n信息论的创始人香侬信息论的创始人香侬(Shannon)在在1940年首先建立了用电子线路来实现布尔代年首先建立了用电子线路来实现布尔代数表达式，数表达式，0，1分别代表电路的开、关分别代表电路的开、关状态或高、低电平；命题为真，线路建状态或高、低电平；命题为真，线路建立连结；命题为假，线路断开连结。立连结；命题为假，线路断开连结。1、与运算 所有条例都具备事件才发生，与运算又叫逻辑乘。开关：“1”闭合，“0”断开；灯：“1”亮，“0”灭 真值表：这里若用1表示开关接通和灯亮、用0表示开关断开和灯暗.则可列出真值表.如图2.1所示。把输
2、入所有可能的组合与输出取值对应列成表。逻辑表达式：L=AB(逻辑乘)逻辑功能口决：有“0”出“0”，全“1”出“1”。2、或运算 至少有一个条件具备，事件就会发生。开关A与开关B只要有一个接通时，灯L亮，否则暗。输人量A,B与输出量F存在着或逻辑关系。真值表：逻辑表达式：L=A+B（逻辑加）逻辑功能口决：有“1”出“1”，全“0”出“0”3、非运算：结果与条件相反。某事情发生与否，仅取决于一个条件，而且是对该条件的否定。即条件具备时事情不发生；条件不具备时事情才发生。基本公式2.1.2逻辑代数的基本公式、规则、附加公式交换律结合律分配律 2.1.2逻辑代数的基本公式、规则、附加公式基本公式（续
3、）如何验证公式的正确性n真值表n利用基本定理化简公式例：真值表验证摩根定律1000AB1110AB1110A B10000 00 11 01 1A BA B如何验证公式的正确性n真值表n利用基本定理化简公式AB+AC+BC=AB+AC (?)（包含律）证明：AB+AC+BC =AB(C+C)+AC(B+B)+BC(A+A)=ABC+ABC+ABC+ABC+ABC+ABC =ABC+ABC+ABC+ABC =AB+AC如何验证公式的正确性AB+AC+BC+BCD=AB+AC+BC(1+D)=AB+AC+BC=AB+ACA+B=A+C B=C AB=AC B=C2.反演规则和对偶规则（1）反演规则
4、 在逻辑代数中，常将逻辑函数F叫作原函数，将F叫作F的反函数或补函数。将一个逻辑函数表达式F中的“与”、“或”运算符互换，常量0、1互换，原变量与反变量互换，就可得到F的反函数F。这就是反演规则。利用反演规则求反函数F时，不仅要注意运算的优先顺序，而且还要注意只有单个变量的反变量才变为原变量，而对于多个变量组合后的“非”号不能变反。（1）反演规则即:“”,“+”,“0”,“1”,“原变量”,“反变量”“+”,“”,“1”,“0”,“反变量”,“原变量”（1）反演规则反演规则练习（2）对偶规则n设F为一个逻辑函数表达式，若将F中的“与”、“或”运算符互换(即变为+，+变为)，常量0、1互换(即0
5、变为1，1变为0)，所得到的新表达式就叫做函数F的对偶式n如果两个逻辑函数表达式相等，那么它们的对偶式也一定相等。这就是对偶规则。（2）对偶规则即:“”,“+”,“0”,“1”,“变量”“+”,“”,“1”,“0”,不变（2）对偶规则对对偶偶规规则则的的意意义义在在于于：如果两个函数相等，则它们的对偶函数也相等。利用对偶规则,可以使要证明及要记忆的公式数目减少一半。例如：注意注意注意注意：在运用反演规则和对偶规则时，必须按照逻辑运算的优先顺序进行：先算括号，接着与运算，然后或运算，最后非运算，否则容易出错。（2）对偶规则（2）对偶规则3.附加公式附加公式13.附加公式3.附加公式附加公式23.
6、附加公式3.附加公式3.附加公式2.1.3基本逻辑公式4.与非门ABF真值表 F=ABA BF0 01 00 11 11110实现实现“与非与非”逻辑逻辑(NANDNOT-AND)(NANDNOT-AND)例：例：与非门与非门（A、B是输入，是输入，F是输出）是输出）AFBC5.或非门 ABF+实现实现“或非或非”逻辑逻辑(NORNOT-OR)(NORNOT-OR)真值表A BF0 01 00 11 11000AFBC6.“与或非”门7.异或门8.同或门2.2逻辑函数化简（1）公式化简法（2）图解化简法（3）表格法2.2.1 公式法化简逻辑函数逻辑函数化简的目的逻辑函数化简的目的:省器件！用最
7、少的门实现省器件！用最少的门实现相同的逻辑功能，每个门的输入也最少。相同的逻辑功能，每个门的输入也最少。主要掌握与或表达式的化简：主要掌握与或表达式的化简：(1)乘积的个数最少乘积的个数最少(用门电路实现，所用与门的用门电路实现，所用与门的个数最少个数最少)(2)在满足在满足(1)的条件下，乘积项中的变量最少的条件下，乘积项中的变量最少(与门的输入端最少与门的输入端最少)最简的目标不同，达到的效果也不同。如果功耗最简的目标不同，达到的效果也不同。如果功耗最小或者可靠性最高是目标，化简的结果完全最小或者可靠性最高是目标，化简的结果完全不同！不同！公式化简法：（1）合并乘积项法：利用互补律的公式。
8、与或表达式化简例：展开：展开：结合：结合：互补律：互补律：互补律：互补律：（2）吸收项法：利用吸收律和包含律等公式来减少“与”项数。与或表达式化简与或表达式化简例：反演律反演律:B+C=BC:B+C=BC吸收律：吸收律：A AABABA+BA+B（3）配项法：利用互补律，配在乘积项上，然后在化简。与或表达式化简包含配项展开合并例：与或表达式化简（续）续上页吸收律吸收律D+DCD+DCD DC C分配反演DCDC吸收律：与或表达式化简（续）与或表达式化简（续）与或表达式化简（续）与或表达式化简（续）与或表达式化简（续）或与表达式化简公式法练习题例：例：1）表达式中表达式中与项与项的个数最少；的个
9、数最少；2）在满足在满足1）的前提下）的前提下,每个每个与项与项中的变量个数最少。中的变量个数最少。解：函数表达式一般化简成函数表达式一般化简成与或式与或式，其最简应满足的两个条件：，其最简应满足的两个条件：例：例：反演反演被吸收被吸收被吸收被吸收配项配项2.2.2 逻辑函数的标准形式逻辑函数可以表示为最小项之和的形式逻辑函数可以表示为最小项之和的形式（与或表达式）或者最大项之积的形式（与或表达式）或者最大项之积的形式（或与表达式）（或与表达式）应用最多的是最小项之和的形式，也叫最应用最多的是最小项之和的形式，也叫最小项标准式。小项标准式。最小项也是卡诺图化简的基础。最小项也是卡诺图化简的基础
10、。1.最小项(MinTerm)逻辑函数有逻辑函数有n个变量，由它们组成的具有个变量，由它们组成的具有n个变量的乘积项中，每个变量以原变个变量的乘积项中，每个变量以原变量或反变量的形式出现且仅出现一次，量或反变量的形式出现且仅出现一次，这个乘积项为最小项。这个乘积项为最小项。N个变量有个变量有2n个个最小项。最小项。例如：n=3，对A、B、C，有8个最小项最小项(续)n对任意最小项，只有一组变量取值使它的值为1，其他取值使该最小项为0n为方便起见，将最小项表示为min=3的8个最小项为：变量的各组取值A B C000100010110001101011111对应的最小项及其编号最小项编 号例：三
11、变量函数的最小项：编号规则编号规则:原变量取原变量取1,反变量取反变量取0。最小项(续)n任何逻辑函数均可表示为唯一的一组最小项任何逻辑函数均可表示为唯一的一组最小项之和的形式，称为标准的与或表达式之和的形式，称为标准的与或表达式n某一最小项不是包含在某一最小项不是包含在F的原函数中，就是包的原函数中，就是包含在含在F的反函数中的反函数中即n个变量的所有最小项之和恒等于1。所以=m2+m6+m3+m7注意：变量的顺序.=m(2,3,6,7)2）当时，。最小项的性质：1）只有一组取值使 mi1。3）全部最小项之和等于1，即mi1。最小项的性质(续)5）当函数以最小项之和形式表示时，可很容易列出函
12、数及反函数的真值表（在真值表中，函数所包含的最小项填“1”）。4）n变量的最小项有n个相邻项。一对相邻项之和可以消去一个变量。相邻项：只有一个变量不同（以相反的形式出现）。最小项表达式的求法最小项表达式的求法一般表达式一般表达式：除非号除非号去括号去括号补因子补因子真值表真值表除非号除非号去括号去括号补因子补因子方法方法用真值表求用真值表求最小项表达式最小项表达式例例：函数 F=AB+AC A B C F0 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 11101其其余余补补00010由一般表达式直接写出由一般表达式直接写出最小项表达式最小项表达式例例：函数 F=A
13、B+AC 所以所以:F=m(1,4,5,6)最小项练习题2.最大项(MaxTerm)nn个变量组成的或项，每个变量以原变量或反变量的形式出现且仅出现一次，则称这个或项为最大项例如：n=3的最大项为变量的各组取值A B C000100010110001101011111对应的最大项及其编号最大项编 号例：三变量函数的最大项：编号规则编号规则:原变量取原变量取0,反变量取反变量取1。最大项(续)n对任意一个最大项，只有一组变量取值使它的值为0，而变量的其他取值使该项为1n将最大项记作Min任何一个逻辑函数均可表示为唯一的一组最大项之积，称为标准的或与表达式nn个变量全体最大项之积必为“0”n某个最
14、大项不是含在F的原函数中，就是在F的反函数中所以与最小项类似，有注意：变量顺序.例如：例如：最大项表达式:F 最大项的性质：1）只有一组取值使 Mi0。3）全部最大项之积等于0，即Mi0。2）当时，。最大项的性质(续)4）n变量的最大项有n个相邻项。一对相邻项之积可以消去一个变量。5）当函数以最大项之积形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最大项填“0”）。以最小项之以最小项之和和的形式表示的函数可以转换成最大项的形式表示的函数可以转换成最大项之之积积的形式，反之亦然。的形式，反之亦然。=m(2,6,3,7)F(A,B,C)=m(0,1,4,5)=(A+B+C)
15、(A+B+C)(A+B+C)(A+B+C)而:所以,有 F(A,B,C)=m(2,3,6,7)=M(0,1,4,5)F(A,B,C)=m(0,1,4,5)=M(2,3,6,7)同理最大项练习题3.最小项与最大项的性质4.图解法(卡诺图)化简逻辑函数卡诺图(Karnaugh Map):逻辑函数的图示表示，把最小项填入卡诺图，利用相邻最小项的互补性，消去一个变量，实现化简。卡诺图的构成(1)、由矩形或正方形组成的图形(2)、将矩形分成若干小方块，每个小方块对应一个最小项2变量卡诺图(Karnaugh Map)n2变量卡诺图1整体为1左、右部分表示上、下部分表示2变量卡诺图(Karnaugh Map
16、)2变量卡诺图可由代表变量卡诺图可由代表4个最小项的四个小方格组成个最小项的四个小方格组成m1 m2 m3m0 AB改画成 2变量卡诺图变量卡诺图变量卡诺图变量卡诺图二变量卡诺图（A，B）mo m2m1 m3 0101ABmo m1m2 m3 0101BAAB 0101BA 01013变量Karnaugh Map 3变量卡诺图由变量卡诺图由8个最小项组成，对应图中个最小项组成，对应图中8个小方格个小方格 BAC1000110110m1 m0 m3 m2 m5 m4 m7 m6 注意：表中最小项编码按注意：表中最小项编码按00011110循环码顺序排列，循环码顺序排列，而不是而不是0001101
17、1（二进制计数的顺序）（二进制计数的顺序）mo m1 m3 m2m4 m5 m7 m600 01 11 1001BAC三变量卡诺图00 01 11 1001BACBAC什么是循环码相邻两个编码之间只有一位数不同，而且首尾两个相邻两个编码之间只有一位数不同，而且首尾两个编码之间也只有一位数不同，这种编码叫循环码。编码之间也只有一位数不同，这种编码叫循环码。2位循环码：位循环码：00011110 3位循环码：位循环码：000001011010 110111101100 特点：每次只变一位，相邻两数间只有一位不同；特点：每次只变一位，相邻两数间只有一位不同；用在卡诺图上，可以消去最小项的多余变量。用
18、在卡诺图上，可以消去最小项的多余变量。循环码是无权码，而且不是唯一的编码，如：循环码是无权码，而且不是唯一的编码，如：01，00，10，11 同样具有同样具有2位循环码的性质。位循环码的性质。4变量Karnaugh Map BADC0011011000110110m1 m0 m3 m2 m5 m4 m7 m6 m13 m12 m15 m14 m9 m8 m11 m10 m m1 1 的相邻最小项是的相邻最小项是m m0 0,m,m3 3,m,m5 5,m,m9 9，其中，其中m m9 9是相对的，其余为是相对的，其余为相接；同样，相接；同样，m m0 0与与m m8 8相对，与相对，与m m2
19、 2也相对。也相对。00 01 11 1000011110BADC 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 1000 01 11 1000011110BADC四变量卡诺图五变量卡诺图000 001 011 01000011110CBAED110 111 101 100202123221819171628293130262725241213151410119845762310对称轴n5 变量的卡诺图，可由n1变量卡诺图在需要增加变量的方向采用镜像变换而生成。说明：2个或以上变量，按循环码规则排列；个或以上变量，按循环码规则排列；每个小方格对应一个最小项；每个小方格对
20、应一个最小项；相邻方格的最小项，具有逻辑相邻性，即有一个变量互为相邻方格的最小项，具有逻辑相邻性，即有一个变量互为反变量；反变量；具有逻辑相邻性的方格有：具有逻辑相邻性的方格有：相接相接几何相邻的方格；几何相邻的方格；相对相对上下两边、左右两边的方格；上下两边、左右两边的方格；相重相重多变量卡诺图，以对称轴相折叠，重在一齐多变量卡诺图，以对称轴相折叠，重在一齐的方格。的方格。逻辑相邻的最小项可以消去互补变量逻辑相邻的最小项可以消去互补变量三变量卡诺图逻辑相邻举例00 01 11 1001B AC相接相对00 01 11 1001B AC四变量卡诺图逻辑相邻举例相接相对相对00 01 11 10
21、00011110BADC五变量卡诺图逻辑相邻举例000 001 011 01000011110CBAED110 111 101 100202123221819171628293130262725241213151410119845762310相重对称轴函数卡诺图函数卡诺图 用卡诺图法对逻辑函数进行化简时，首先要确定函数用卡诺图法对逻辑函数进行化简时，首先要确定函数与卡诺图的关系，将函数用卡诺图的形式表现出来。与卡诺图的关系，将函数用卡诺图的形式表现出来。方法方法真值表真值表 填卡诺图填卡诺图表达式表达式 一般与或式一般与或式 填卡诺图填卡诺图化成最小项表达式化成最小项表达式 填卡诺图填卡诺图真
22、值表、表达式、卡诺图都可以表达一个逻辑函数。真值表、表达式、卡诺图都可以表达一个逻辑函数。由真值表填卡诺图由真值表填卡诺图A B C F0 0 001 0 010 1 001 1 010 0 111 0 110 1 101 1 10对应最小项填1其余补0 0 1 1 0 1 1 0 000 01 11 1001BACmo m1 m3 m2m4 m5 m7 m600 01 11 1001BAC 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 1000 01 11 1000011110BADC 1 1 1 1 1 1 1 00 01 11 1000011110BADC由表达式
23、由表达式 最小项表达式最小项表达式填卡诺图举例填卡诺图举例由一般与或式由一般与或式 填卡诺图示例填卡诺图示例:三变量三变量 11 1 1 00 01 11 1001BAC00 01 11 1001BAC1111示例示例:四变量四变量00 01 11 1000011110BADC111111100 01 11 1000011110BADC111111 1 111111函数的卡诺图化简函数的卡诺图化简方法：方法：1）填写函数卡诺图；）填写函数卡诺图；2）合并最小项，对邻项方格画卡诺圈（含）合并最小项，对邻项方格画卡诺圈（含2n方格）；方格）；3）消去互补变量，直接写出最简与或式。）消去互补变量，直
24、接写出最简与或式。画圈原则：圈尽量大 消去的变量多圈尽量少 结果乘积项少要有新成份没有冗余项使用方法：圈1 得到 F 原函数圈0 得到 F 反函数 画的圈不同，结果的表达式形式可能不同，但肯定是最简的结果。圈1个格消0个变量 圈2 1 圈4 2 圈8 3 0101AB1 1 0101AB1 1 0101AB1 11二变量卡诺图的典型合并情况00 01 11 1001BAC1 11 1BA 00 01 11 1001C1 1 1 11 1 1 101BAC00 01 11 10三变量卡诺图的典型合并情况100 01 11 1000011110BADC111111100 01 11 1000011
25、110BADC111111110001111000 01 11 10 BADC1111111111四变量卡诺图的典型合并情况DCBA0001 11 1000011110不是矩形不是矩形无效圈示例1无效圈示例2DCBA0001 11 1000011111 1111 11111 111101没有新变量.无效圈.卡诺图化简的步骤 1 按照循环码规律指定卡诺图变量取值；按照循环码规律指定卡诺图变量取值；2 在函数最小项对应的小方块填在函数最小项对应的小方块填“1”，其他方，其他方块填块填“0”；3 合并相邻填合并相邻填“1”的小方块，两个方块合并消的小方块，两个方块合并消去一个变量（一维块）；去一个变
26、量（一维块）；4个方块合并消去两个方块合并消去两个变量（二维块）；个变量（二维块）；4 合并过程中先找大圈合并，圈越大消去的变量合并过程中先找大圈合并，圈越大消去的变量越多；越多；5 使每一最小项至少被合并包含过一次；每个合使每一最小项至少被合并包含过一次；每个合并的圈中，至少要有一个并的圈中，至少要有一个“1”没有被圈过，没有被圈过，否则这个圈就是多余的。否则这个圈就是多余的。“与或”式化简：例1将表达式将表达式F=AB+AC 填入卡诺图填入卡诺图 BAC10001101100 0 10 01 1 1“与或”式化简：例2BADC 1 10011011000110110“与或”式化简：例2（续
27、）BADC 1 11 11 10011011000110110“与或”式化简：例2（续）BADC 1 11 11 1001101100011011011“与或”式化简：例2（续）BADC 1 11 11 100110110001101101111“与或”式化简：例2（续）BADC 1 11 11 100110110001101101111“与或”式化简：例2（续）BADC00110110001101100 0 1 1 1 0 0 0 1 1 0 0 01 1 1“与或”式化简：例3BADC00110110001101100 1 0 1 1 0 1 1 1 1 1 1 11 1 0“与或”式化简
28、：例4BADC00110110001101101 1 1 1 0 0 0 1 0 1 0 0 10 0 0 卡诺图化简 卡诺图化简的核心是找到并且合并相邻最小项。卡诺图化简的核心是找到并且合并相邻最小项。相邻三种情况：相接，相对，相重。相邻三种情况：相接，相对，相重。5变量卡诺变量卡诺图才会出现相重的情况。图才会出现相重的情况。合并过程中先找大圈合并，圈越大消去的变量越合并过程中先找大圈合并，圈越大消去的变量越多；使每一最小项至少被合并包含过一次；每多；使每一最小项至少被合并包含过一次；每个合并的圈中，至少要有一个个合并的圈中，至少要有一个“1”没有被圈过，没有被圈过，否则这个圈就是冗余的。否
29、则这个圈就是冗余的。4个变量卡诺图的最小项BADC0011011000110110m1 m0 m3 m2 m5 m4 m7 m6 m13 m12 m15 m14 m9 m8 m11 m10 m m1 1 的相邻最小项是的相邻最小项是m m0 0,m,m3 3,m,m5 5,m,m9 9，其中，其中m m9 9是相对的，其余为是相对的，其余为相接；同样，相接；同样，m m0 0与与m m8 8相对，与相对，与m m2 2也相对。也相对。“与或”表达式化简：例3BADC00110110001101100 1 0 1 1 0 1 1 1 1 1 1 11 1 0“与或”表达式化简：BADC00110
30、110001101100 1 0 1 1 0 1 1 1 1 1 1 11 1 1 此时，图上有此时，图上有13个最小项为个最小项为1,只有只有3个最个最小项为小项为0，写，写F的表达式更简单。的表达式更简单。注意：经常是写注意：经常是写F比比直接写直接写F简单。简单。CBA ED000 001 011 010 110 111 101 1000011011111111111110111例题：例题：5变量卡诺图化简变量卡诺图化简化简结果化简结果:练习练习1：卡诺图化简：卡诺图化简CBA0001111001DCBA0001 11 1000011110练习练习2：化简：化简F(A,B,C,D)=(0
31、,2,3,5,6,8,9,10,11,12,13,14,15)F(A,B,C,D)=m(0,5,7,9,10,12,13,14,15)F(A,B,C,D)=m(2,3,8,9,10,12,13)用卡诺图把逻辑函数 F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)化简成最简或与表达式。CBA0001111001BCBAF=AB+BC练习练习1：卡诺图化简：卡诺图化简F(A,B,C,D)=(0,2,3,5,6,8,9,10,11,12,13,14,15)DCBA0001 11 1000011110D练习练习2：化简：化简DCBA0001 11 1000011110ACD练习
32、练习3：化简：化简F(A,B,C,D)=m(0,5,7,9,10,12,13,14,15)100 01 11 1000011110ABDC11111111解：解：1100 01 11 1000011110BADC1111111练习练习4：用卡诺图化简逻辑函数：用卡诺图化简逻辑函数BA00 01 11 1000011110 DC 111111 1 1100 01 11 1000011110BADC111 1 1不同的圈法，得到不同的最简结果 F(A,B,C,D)=m(2,3,8,9,10,12,13)练习练习5：用卡诺图化简逻辑涵数：用卡诺图化简逻辑涵数最小项互补,即编号互为补充练习练习6：用卡诺图把逻辑函数 F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)化简成最简或与表达式。100 01 11 1000011110BADC011001110000001原函数为0时,反函数为1.此处圈0,应理解为对反函数是圈1.F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢