谭浩强C程序设计第四版精品课件

第2章逻辑代数及

逻辑函数化简2.1逻辑代数的基本运算与公式2.2公式法化简逻辑函数2.3逻辑函数的标准形式2.4图解法(卡诺图)化简（重点）2.5表格法化简(Q-M法)2.6逻辑函数的实现2.1逻辑代数的基本运算与公式逻辑代数：二进制运算的基础。应用代数方法研究逻辑问题。由英国数学家布尔(Boole)和德.摩根于1847年提出，又叫布尔代数，开关代数。逻辑函数的表示：真值表，表达式，逻辑门逻辑函数的生成：逻辑问题的描述，由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现，逻辑设计的第一步。逻辑代数的基本运算：与、或、非 (1)“与”运算，逻辑乘 (2)“或”运算，逻辑加 (3)“非”运算，取反2.1.1逻辑代数的基本运算信息论的创始人香侬(Shannon)在1940年首先建立了用电子线路来实现布尔代数表达式，0，1分别代表电路的开、关状态或高、低电平；命题为真，线路建立连结；命题为假，线路断开连结。开关：“1”闭合，“0”断开；灯：“1”亮，“0”灭真值表：这里若用1表示开关接通和灯亮、用0表示开关断开和灯暗.则可列出真值表.如图2.1所示。把输入所有可能的组合与输出取值对应列成表。逻辑表达式：L=A·B(逻辑乘)逻辑功能口决：有“0”出“0”，全“1”出“1”。2、或运算———至少有一个条件具备，事件就会发生。

开关A与开关B只要有一个接通时，灯L亮，否则暗。输人量A,B与输出量F存在着或逻辑关系。真值表：逻辑表达式：L=A+B（逻辑加）逻辑功能口决：有“1”出“1”，全“0”出“0”3、非运算：—结果与条件相反。某事情发生与否，仅取决于一个条件，而且是对该条件的否定。即条件具备时事情不发生；条件不具备时事情才发生。基本公式2.1.2逻辑代数的基本公式、规则、附加公式基本公式（续）如何验证公式的正确性真值表利用基本定理化简公式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+AC2.反演规则和对偶规则（1）反演规则在逻辑代数中，常将逻辑函数F叫作原函数，将F叫作F的反函数或补函数。将一个逻辑函数表达式F中的“与”、“或”运算符互换，常量0、1互换，原变量与反变量互换，就可得到F的反函数F。这就是反演规则。利用反演规则求反函数F时，不仅要注意运算的优先顺序，而且还要注意只有单个变量的反变量才变为原变量，而对于多个变量组合后的“非”号不能变反。（1）反演规则即:“”,“+”,“0”,“1”,“原变量”,“反变量”“+”,“”,“1”,“0”,“反变量”,“原变量”（1）反演规则反演规则练习（2）对偶规则即:“”,“+”,“0”,“1”,“变量”“+”,“”,“1”,“0”,不变（2）对偶规则（2）对偶规则

3.附加公式附加公式13.附加公式附加公式23.附加公式3.附加公式2.1.3基本逻辑公式4.与非门ABF真值表F=ABABF001001111110实现“与非”逻辑

(NAND——NOT-AND)例：与非门（A、B是输入，F是输出）AFBC5.或非门ABF+实现“或非”逻辑(NOR——NOT-OR)真值表ABF001001111000AFBC6.“与或非”门7.异或门8.同或门2.2逻辑函数化简（1）公式化简法（2）图解化简法（3）表格法2.2.1公式法化简逻辑函数逻辑函数化简的目的:省器件！用最少的门实现相同的逻辑功能，每个门的输入也最少。主要掌握与或表达式的化简：(1)乘积的个数最少(用门电路实现，所用与门的个数最少)(2)在满足(1)的条件下，乘积项中的变量最少(与门的输入端最少)最简的目标不同，达到的效果也不同。如果功耗最小或者可靠性最高是目标，化简的结果完全不同！公式化简法：

（1）合并乘积项法：利用互补律的公式。

与或表达式化简例：展开：结合：互补律：互补律：（2）吸收项法：利用吸收律和包含律等公式来减少“与”项数。与或表达式化简例：反演律:B+C=BC吸收律：A＋AB＝A+B（3）配项法：利用互补律，配在乘积项上，然后在化简。与或表达式化简包含配项展开合并例：与或表达式化简（续）续上页吸收律D+DC＝D＋C分配反演D＋C＝DC吸收律：与或表达式化简（续）与或表达式化简（续）与或表达式化简（续）与或表达式化简（续）与或表达式化简（续）或与表达式化简公式法练习题例：1）表达式中"与项"的个数最少；2）在满足1）的前提下,每个"与项"中的变量个数最少。解：函数表达式一般化简成与或式，其最简应满足的两个条件：例：反演被吸收被吸收配项2.2.2逻辑函数的标准形式逻辑函数可以表示为最小项之和的形式（与或表达式）或者最大项之积的形式（或与表达式）应用最多的是最小项之和的形式，也叫最小项标准式。最小项也是卡诺图化简的基础。1.最小项(MinTerm)逻辑函数有n个变量，由它们组成的具有n个变量的乘积项中，每个变量以原变量或反变量的形式出现且仅出现一次，这个乘积项为最小项。N个变量有2n个最小项。例如：n=3，对A、B、C，有8个最小项最小项(续)对任意最小项，只有一组变量取值使它的值为1，其他取值使该最小项为0为方便起见，将最小项表示为mi n=3的8个最小项为：

变量的各组取值ABC0 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 1对应的最小项及其编号最小项编号例：三变量函数的最小项：编号规则:原变量取1,反变量取0。最小项(续)任何逻辑函数均可表示为唯一的一组最小项之和的形式，称为标准的与或表达式某一最小项不是包含在F的原函数中，就是包含在F的反函数中即n个变量的所有最小项之和恒等于1。所以=m2+m6+m3+m7注意：变量的顺序.=m(2,3,6,7)2）当时，。⑵最小项的性质：1）只有一组取值使mi＝1。3）全部最小项之和等于1，即∑mi＝1。最小项的性质(续)5）当函数以最小项之和形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最小项填“1”）。4）n变量的最小项有n个相邻项。一对相邻项之和可以消去一个变量。相邻项：只有一个变量不同（以相反的形式出现）。⑶

最小项表达式的求法一般表达式：→除非号→去括号→补因子真值表除非号去括号补因子方法用真值表求最小项表达式例：函数F=AB+ACABC F000 100 010 110 001 101 011 111 1101其余补00010由一般表达式直接写出最小项表达式例：函数F=AB+AC所以:

F=∑m(1,4,5,6)最小项练习题2.最大项(MaxTerm)n个变量组成的或项，每个变量以原变量或反变量的形式出现且仅出现一次，则称这个或项为最大项

例如：n=3的最大项为变量的各组取值ABC0 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 1对应的最大项及其编号最大项编号例：三变量函数的最大项：编号规则:原变量取0,反变量取1。最大项(续)对任意一个最大项，只有一组变量取值使它的值为0，而变量的其他取值使该项为1将最大项记作Mi任何一个逻辑函数均可表示为唯一的一组最大项之积，称为标准的或与表达式n个变量全体最大项之积必为“0”某个最大项不是含在F的原函数中，就是在F的反函数中所以与最小项类似，有注意：变量顺序.例如：最大项表达式:F⑵最大项的性质：1）只有一组取值使Mi＝0。3）全部最大项之积等于0，即∏Mi＝0。2）当时，。最大项的性质(续)4）n变量的最大项有n个相邻项。一对相邻项之积可以消去一个变量。5）当函数以最大项之积形式表示时，可很容易列出函数及反函数的真值表（在真值表中，函数所包含的最大项填“0”）。

以最小项之和的形式表示的函数可以转换成最大项之积的形式，反之亦然。=m(2,6,3,7)F(A,B,C)=m(0,1,4,5)=(A+B+C)(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.图解法(卡诺图)化简逻辑函数卡诺图(KarnaughMap):逻辑函数的图示表示，把最小项填入卡诺图，利用相邻最小项的互补性，消去一个变量，实现化简。卡诺图的构成 (1)、由矩形或正方形组成的图形 (2)、将矩形分成若干小方块，每个小方块对应一个最小项2变量卡诺图(KarnaughMap)2变量卡诺图1整体为1左、右部分表示上、下部分表示2变量卡诺图(KarnaughMap)2变量卡诺图可由代表4个最小项的四个小方格组成m1

m2

m3m0

AB改画成

2变量卡诺图⑴变量卡诺图

二变量卡诺图（A，B）mo

m2m1

m30 101ABmo

m1m2

m30 101BAAB0 101BA0 1013变量KarnaughMap3变量卡诺图由8个最小项组成，对应图中8个小方格

BAC1000110110m1

m0

m3

m2

m5

m4

m7

m6

注意：表中最小项编码按00－01―11－10循环码顺序排列，而不是00－01－10－11（二进制计数的顺序）mo

m1m3

m2m4

m5m7

m60001111001BAC三变量卡诺图0001111001BACBAC什么是循环码相邻两个编码之间只有一位数不同，而且首尾两个编码之间也只有一位数不同，这种编码叫循环码。2位循环码：000111103位循环码：000001011010

110111101100特点：每次只变一位，相邻两数间只有一位不同；用在卡诺图上，可以消去最小项的多余变量。循环码是无权码，而且不是唯一的编码，如：01，00，10，11同样具有2位循环码的性质。4变量KarnaughMapBADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

m1的相邻最小项是m0,m3,m5,m9，其中m9是相对的，其余为相接；同样，m0与m8相对，与m2也相对。0001111000011110BADC01

324

5

76121315148911100001111000011110BADC四变量卡诺图五变量卡诺图000

00101101000011110CBAED110

111101100202123221819171628293130262725241213151410119845762310对称轴n≥5变量的卡诺图，可由n－1变量卡诺图在需要增加变量的方向采用镜像变换而生成。说明：⑴2个或以上变量，按循环码规则排列；⑵每个小方格对应一个最小项；⑶相邻方格的最小项，具有逻辑相邻性，即有一个变量互为反变量；⑷具有逻辑相邻性的方格有： 相接——几何相邻的方格； 相对——上下两边、左右两边的方格； 相重——多变量卡诺图，以对称轴相折叠，重在一齐的方格。逻辑相邻的最小项可以消去互补变量三变量卡诺图逻辑相邻举例0001111001BAC相接相对0001111001BAC四变量卡诺图逻辑相邻举例相接相对相对0001111000011110BADC五变量卡诺图逻辑相邻举例000

00101101000011110CBAED110

111101100202123221819171628293130262725241213151410119845762310相重对称轴⑵函数卡诺图

用卡诺图法对逻辑函数进行化简时，首先要确定函数与卡诺图的关系，将函数用卡诺图的形式表现出来。方法真值表→填卡诺图表达式→一般与或式→填卡诺图化成最小项表达式→填卡诺图真值表、表达式、卡诺图都可以表达一个逻辑函数。由真值表填卡诺图ABC F000 0100 1010 0110 1001 1101 1011 0111 0对应最小项填1其余补0

01

101

1

000001111001BACmo

m1m3

m2m4

m5m7

m60001111001BAC01

324

5

76121315148911100001111000011110BADC1

11

11110001111000011110BADC由表达式→最小项表达式→填卡诺图举例由一般与或式填卡诺图示例:三变量1111

0001111001BAC0001111001BAC1111示例:四变量0001111000011110BADC11111110001111000011110BADC1111111

111111⑶函数的卡诺图化简方法：1）填写函数卡诺图；2）合并最小项，对邻项方格画卡诺圈（含2n方格）；3）消去互补变量，直接写出最简与或式。画圈原则：圈尽量大→消去的变量多圈尽量少→结果乘积项少要有新成份→没有冗余项使用方法：圈1→得到F原函数圈0→得到F反函数画的圈不同，结果的表达式形式可能不同，但肯定是最简的结果。圈1个格→消0个变量圈2→1圈4→2圈8→3

…………0 101AB110 101AB110 101AB111二变量卡诺图的典型合并情况0001111001BAC1111BA0001111001C1111111101BAC00011110三变量卡诺图的典型合并情况10001111000011110BADC11111110001111000011110BADC111111110001111000011110BADC1111111111四变量卡诺图的典型合并情况DCBA0001111000011110不是矩形无效圈示例1无效圈示例2DCBA0001111000011111111111111101没有新变量.无效圈.卡诺图化简的步骤1按照循环码规律指定卡诺图变量取值；2在函数最小项对应的小方块填“1”，其他方块填“0”；3合并相邻填“1”的小方块，两个方块合并消去一个变量（一维块）；4个方块合并消去两个变量（二维块）；4合并过程中先找大圈合并，圈越大消去的变量越多；5使每一最小项至少被合并包含过一次；每个合并的圈中，至少要有一个“1”没有被圈过，否则这个圈就是多余的。“与或”式化简：例1将表达式F=AB+AC填入卡诺图

BAC10001101100

0

10

01

1

1“与或”式化简：例2BADC

110011011000110110“与或”式化简：例2（续）BADC

1111110011011000110110“与或”式化简：例2（续）BADC

111111001101100011011011“与或”式化简：例2（续）BADC

11111100110110001101101111“与或”式化简：例2（续）BADC

11111100110110001101101111“与或”式化简：例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

“与或”式化简：例4BADC00110110001101101

1

1

1

0

0

0

1

0

1

0

0

10

0

0

卡诺图化简卡诺图化简的核心是找到并且合并相邻最小项。相邻三种情况：相接，相对，相重。5变量卡诺图才会出现相重的情况。合并过程中先找大圈合并，圈越大消去的变量越多；使每一最小项至少被合并包含过一次；每个合并的圈中，至少要有一个“1”没有被圈过，否则这个圈就是冗余的。4个变量卡诺图的最小项BADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

m1的相邻最小项是m0,m3,m5,m9，其中m9是相对的，其余为相接；同样，m0与m8相对，与m2也相对。“与或”表达式化简：例3BADC00110110001101100

1

0

1

1

0

1

1

1

1

1

1

11

1

0

“与或”表达式化简：BADC00110110001101100

1

0

1

1

0

1

1

1

1

1

1

11

1

1

此时，图上有13个最小项为1,只有3个最小项为0，写F的表达式更简单。注意：经常是写F比直接写F简单。

CBAED0000010110101101111011000011011111111111110111例题：5变量卡诺图化简化简结果:练习1：卡诺图化简CBA0001111001DC