薛宏熙数字逻辑设计cha课件

1、2008.112008.11薛宏熙数字逻辑设计cha1数字逻辑设计数字逻辑设计- 谨供授课教师参考谨供授课教师参考 - - 欢迎批评指正欢迎批评指正 -清华大学计算机系清华大学计算机系薛宏熙薛宏熙2008.112008.11薛宏熙数字逻辑设计cha2第第1章章 逻辑电路导论逻辑电路导论【课前思考】【课前思考】【学习指南】【学习指南】 1.1开关电路数学表示方法初步开关电路数学表示方法初步1.2逻辑代数逻辑代数1.3用用“与与”门、门、“或门或门”和和“非非”门进行逻辑综合门进行逻辑综合1.4公式法化简逻辑函数公式法化简逻辑函数1.5卡诺图卡诺图1.6逻辑函数的标准形式逻辑函数的标准形式1.7*

2、表格法化简逻辑函数表格法化简逻辑函数1.8解题示例解题示例【本章小结】【本章小结】 2008.112008.11薛宏熙数字逻辑设计cha31.1 开关电路数学表示方法初步开关电路数学表示方法初步 例例1.1 楼梯照明灯的控制电路楼梯照明灯的控制电路 电电源源 a （高高层层） b （低低层层） 灯灯 2008.112008.11薛宏熙数字逻辑设计cha4 楼梯照明灯控制电路的真值表楼梯照明灯控制电路的真值表 自自 变变 量量 a b 函数函数 L false false true false true false true false false true true true 2008.112

3、008.11薛宏熙数字逻辑设计cha5真值表的要点真值表的要点 真值表中的真值表中的 0 和和 1 仅代表逻辑命题的真或假仅代表逻辑命题的真或假，不代表，不代表数值的大小。数值的大小。 设自变量的个数为设自变量的个数为n，则自变量取值的组合有，则自变量取值的组合有2n种。真种。真值表的行数为值表的行数为2n，每一行定义自变量在该种取值组合，每一行定义自变量在该种取值组合下函数的值。由此可以得出下函数的值。由此可以得出2个结论：个结论： （1）真值表可以唯一地定义一个逻辑函数真值表可以唯一地定义一个逻辑函数，若函数，若函数 f与与 g 的真值表相同，则的真值表相同，则 f 与与 g 等价。等价。

4、 （2）当）当 n 的数值很大时，真值表的规模急剧增大，这的数值很大时，真值表的规模急剧增大，这是真值表的缺点。是真值表的缺点。2008.112008.11薛宏熙数字逻辑设计cha6真值表的习惯表示方法真值表的习惯表示方法 输入变量的排序输入变量的排序可由设计者任意指定，如果是变量组可由设计者任意指定，如果是变量组的话，可以采用的话，可以采用升序升序，例如；，例如； 也可以采用也可以采用降序降序，例如，例如2. 真值表的第真值表的第1列（行号）是可有可无的，本书中有时加列（行号）是可有可无的，本书中有时加上行号是为了文字叙述的方便。上行号是为了文字叙述的方便。3. 输入变量取值的组合可以转换为

5、对应的二进制数，可输入变量取值的组合可以转换为对应的二进制数，可令此二进制数和行号对应起来。于是，输入变量取值令此二进制数和行号对应起来。于是，输入变量取值的组合可以表示为的组合可以表示为m i ,其下标其下标 i 恰是对应的行号。恰是对应的行号。 例如，输入变量例如，输入变量a, b取值为取值为10时，可表示为时，可表示为m2。4321xxxx0123xxxx2008.112008.11薛宏熙数字逻辑设计cha7分析与综合分析与综合 分析分析（analysis）：由已知电路推导其电路的功能。）：由已知电路推导其电路的功能。 例例 1.1 楼梯照明灯控制电路导出其功能表，是分析的过程。楼梯照明

6、灯控制电路导出其功能表，是分析的过程。 引入引入真值表真值表。 综合综合（synthesis）：由给定的功能描述推导其电路实现。）：由给定的功能描述推导其电路实现。 由由真值表真值表推导其电路实现，需要引入其它的数学工具，推导其电路实现，需要引入其它的数学工具， 逻辑代数逻辑代数（布尔代数）便是其中之一。（布尔代数）便是其中之一。 2008.112008.11薛宏熙数字逻辑设计cha81.2 逻辑代数逻辑代数英国数学家乔治英国数学家乔治布尔（布尔（George Boole）提出了逻辑代数的基本形式）提出了逻辑代数的基本形式和概念，将形式逻辑问题归结为一种代数运算，被人们称为和概念，将形式逻辑问

7、题归结为一种代数运算，被人们称为布尔布尔代数代数（Boolean algebra），即我们所说的），即我们所说的逻辑代数逻辑代数。1.2.1 逻辑代数的基本运算：逻辑代数的基本运算： “与与”运算运算 bafbafbaf或或2008.112008.11薛宏熙数字逻辑设计cha9逻辑代数（续）逻辑代数（续）1.2.1 逻辑代数的基本运算：逻辑代数的基本运算： “或或”运算运算 bafbaf或2008.112008.11薛宏熙数字逻辑设计cha10逻辑代数（续）逻辑代数（续）1.2.1 逻辑代数的基本运算：逻辑代数的基本运算： “非非”运算运算 afaf或2008.112008.11薛宏熙数字逻辑

8、设计cha11逻辑代数（续）逻辑代数（续）1.2.1 逻辑代数的基本运算：逻辑代数的基本运算： 逻辑运算符的优先级逻辑运算符的优先级 ： 逻辑运算符的优先级由高到低依次为：逻辑运算符的优先级由高到低依次为：“非非”“与与”“或或”。 在有括号的情况下，先括号内后括号外；先内层后外层。在有括号的情况下，先括号内后括号外；先内层后外层。 与基本运算对应的逻辑门：与基本运算对应的逻辑门： 2008.112008.11薛宏熙数字逻辑设计cha12逻辑代数（续）逻辑代数（续）1.2.2 逻辑函数：逻辑函数： 逻辑函数的表示方法逻辑函数的表示方法 ： 真值表真值表； 由变量、常量以及逻辑运算符构建的由变量

9、、常量以及逻辑运算符构建的逻辑表达式逻辑表达式 。 逻辑函数的等价性逻辑函数的等价性判断：判断： 真值表形式具有唯一性：若函数真值表形式具有唯一性：若函数 f 与与 g 的真值表相同，则的真值表相同，则 f 与与 g 等等价。反之，二者不等价。价。反之，二者不等价。 逻辑表达式不具有唯一性：若函数逻辑表达式不具有唯一性：若函数 f 与与 g 的逻辑表达式相同，则的逻辑表达式相同，则 f 与与 g 等价；反之，若函数等价；反之，若函数 f 与与 g 的逻辑表达式不同，则的逻辑表达式不同，则 f 与与 g 可能可能等价也可能不等价。等价也可能不等价。2008.112008.11薛宏熙数字逻辑设计c

10、ha13逻辑代数（续）逻辑代数（续）1.2.3 逻辑代数的基本公式和运算规则：逻辑代数的基本公式和运算规则： 逻辑代数的基本公式：逻辑代数的基本公式：2008.112008.11薛宏熙数字逻辑设计cha14逻辑代数的基本公式（续）逻辑代数的基本公式（续）2008.112008.11薛宏熙数字逻辑设计cha15逻辑代数的基本公式（续）逻辑代数的基本公式（续）2008.112008.11薛宏熙数字逻辑设计cha16逻辑代数的基本公式（续）逻辑代数的基本公式（续） 上述公式具有上述公式具有对偶性对偶性： 把 a 组公式中的运算符“”替换成“+”，把运算符“+”替换成 “”，把常数 0 替换成 1，把

11、常数 1 替换成 0，将得到 b 组的对应公式。 对 b 组中的公式作同样的替换，将得到 a 组的对应公式。2008.112008.11薛宏熙数字逻辑设计cha17公式证明举例公式证明举例 【例【例1.2】 用用真值表法真值表法证明公式（证明公式（1- 9b）的正确性。）的正确性。 令等式两边的逻辑表达式分别用函数令等式两边的逻辑表达式分别用函数 f 和和 g 表示：表示： )9b-1)(（yxyxxyxgyxxf, x y x yx yxxf 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 0 1 x y yxg 0 0 0 0 1 1 1 0 1 1 1 1 （a）

12、函数 f 的真值表 （b）函数 g 的真值表 完全相同 2008.112008.11薛宏熙数字逻辑设计cha18公式证明举例（续）公式证明举例（续） 【例【例1.3】 用用公式法公式法证明公式（证明公式（1- 13a）的正确性。）的正确性。 【证】【证】)13a-1（zxyxzyzxyxb1016a1)()()()(b71 )()(a111 )()(）（）（）（）（根据公式根据公式根据公式根据公式zxyxyzxzxzyxyxzyxzxzyxyxzyxzyxzxyxzyzxyx2008.112008.11薛宏熙数字逻辑设计cha19逻辑代数的基本规则逻辑代数的基本规则对偶规则的应用对偶规则的应用

13、 ： 设函数设函数 f 的对偶式记作的对偶式记作 f，函数，函数 g 的对偶式记作的对偶式记作g。若函数。若函数 f 与与g 等价，则等价，则其对偶式其对偶式 f与与 g也等价。也等价。 对函数对函数 f 执行执行2 次对偶变换，将得到函数次对偶变换，将得到函数 f 本身。本身。代入规则代入规则： 对于一个已经成立的等式，若将其中某个变量对于一个已经成立的等式，若将其中某个变量 x 用另一个逻辑表达式用另一个逻辑表达式 f 代替，代替，则等式仍然成立。则等式仍然成立。分解规则：分解规则：香农展开定理（香农展开定理（Shannons Expansion Theorem）可称为分解规则，即任）可称

14、为分解规则，即任何一个逻辑函数何一个逻辑函数 都可以重新表示为都可以重新表示为 ),.,.,(1121niiixxxxxxf),., 1 ,.,(),., 0 ,.,(),.,.,(11211112101121niiiniiiniiixxxxxfxxxxxxfxxxxxxxf 子函数（子函数（f0, f1）的变量个数减少！）的变量个数减少！2008.112008.11薛宏熙数字逻辑设计cha20逻辑代数的基本规则（续）逻辑代数的基本规则（续） 分解规则应用举例：分解规则应用举例： x1 x2 x3 f 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 1

15、1 1 0 x1 x2 x3 f0 0 0 1 0 1 0 1 0 1 0 1 1 1 x1 x2 x3 f1 0 0 0 0 1 0 1 0 1 1 1 1 0 3232320 xxxxxxf 321xxf 11013213232321321321321321fxfxxxxxxxxxxxxxxxxxxxxxxxf）（）（ 2008.112008.11薛宏熙数字逻辑设计cha21逻辑代数的基本规则（续）逻辑代数的基本规则（续） 反演规则反演规则：德：德摩根定律的一般形式称为反演规则摩根定律的一般形式称为反演规则 121121.xxxxxxxxxxinninn121121.xxxxxxxxxxi

16、nninn2008.112008.11薛宏熙数字逻辑设计cha221.3 用与门、或门和非门进行逻辑综合用与门、或门和非门进行逻辑综合 实例实例： 待综合函数的真值表待综合函数的真值表 逻辑表达式逻辑表达式 逻辑表达式逻辑表达式 电路图电路图 )161 ( yxyxyxf)171 ( yxf )171 ()161 (yxfyxyxyxf 优化结果优化结果 2008.112008.11薛宏熙数字逻辑设计cha231.4 公式法化简逻辑函数公式法化简逻辑函数 求求最简的最简的“积之和积之和”表达式：表达式： 表达式中含乘积项个数最少。表达式中含乘积项个数最少。 在满足上述条件下，每个乘积项所含变量

17、个数最少。在满足上述条件下，每个乘积项所含变量个数最少。 举例：举例：1. 合并乘积项法：利用基本公式（合并乘积项法：利用基本公式（111a） 2. 吸收法：利用基本公式（吸收法：利用基本公式（110b） 3. 消去法：利用基本公式（消去法：利用基本公式（19b）yxyxzyxzyxzyxzyxf)()()(yxyxvwzyxyxvwzyxyxf)( )()()()(zyxzyxyxf)(2008.112008.11薛宏熙数字逻辑设计cha24公式法化简逻辑函数（续）公式法化简逻辑函数（续） 举例：举例：4. 添加项法：利用基本公式（添加项法：利用基本公式（14b）5. 配项法：利用互补律，基

18、本公式（配项法：利用互补律，基本公式（15b） ）（）（）（式吸收律合并乘积项，结合律，式添加项a)()()(11-17b1zyzxxyzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxzyxf）吸收率，式结合律，式式配项法），（10b1()7b1(5b-1)()()(zxyxzyxzyxzyxyxzyxzyxzyxyxxxzyzyxyxzyzyxyxf2008.112008.11薛宏熙数字逻辑设计cha25公式法化简逻辑函数（续）公式法化简逻辑函数（续） 优点：优点：用逻辑表达式描述数字电路的功能，是理论上的重大贡献。用逻辑表达式描述数字电路的功能，是

19、理论上的重大贡献。优化逻辑表达式优化逻辑表达式 优化逻辑电路。优化逻辑电路。 缺点：缺点：化简过程无一定规律可循，需要经验和技巧，灵活、交替地化简过程无一定规律可循，需要经验和技巧，灵活、交替地使用各种方法。使用各种方法。不易判断是否已经达到最简形式不易判断是否已经达到最简形式 。 需要寻找更好的方法。需要寻找更好的方法。 2008.112008.11薛宏熙数字逻辑设计cha261.5 卡诺图卡诺图 化简逻辑函数化简逻辑函数 卡诺图是真值表的图形表示卡诺图是真值表的图形表示卡诺图中卡诺图中1个小方格对应于真值表中的个小方格对应于真值表中的1行。行。2008.112008.11薛宏熙数字逻辑设计

20、cha27卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续） 名词术语：名词术语：乘积项（乘积项（product term，简称积项），简称积项） 变量以原变量或反变量的形式出现，多个变量之间执行变量以原变量或反变量的形式出现，多个变量之间执行“与与”操作而操作而构成乘积项。构成乘积项。文字（文字（literal） 乘积项中的变量或该变量的反变量称作一个文字。乘积项中的变量或该变量的反变量称作一个文字。最小项（最小项（minterm） 对于对于n 变量的逻辑函数来说，若某个乘积项中包含的文字个数为变量的逻辑函数来说，若某个乘积项中包含的文字个数为 n，则称该乘积项为最小项。换句话说，若每一个变

21、量或以原变量形式、则称该乘积项为最小项。换句话说，若每一个变量或以原变量形式、或以反变量形式在一个乘积项中出现或以反变量形式在一个乘积项中出现 1 次、且仅出现次、且仅出现 1 次，则该乘积次，则该乘积项是最小项。项是最小项。 最小项对应于卡诺图中的一个小方格，它可以表示为最小项对应于卡诺图中的一个小方格，它可以表示为 n 个变量之积，个变量之积，也可以记作也可以记作 m i 。 例如最小项例如最小项 的另一个等价表示形式是的另一个等价表示形式是 m1。最大项（最大项（maxterm） 对于对于n 变量的逻辑函数来说，若某个变量的逻辑函数来说，若某个“或或”项中包含的文字个数为项中包含的文字个

22、数为 n，则称该则称该“或或”项为最大项。项为最大项。 12xx2008.112008.11薛宏熙数字逻辑设计cha28 2 个 0 维块合并为 1 个 1 维块x3x2 11X 2 个 0 维块合并为 1 个 1 维块x2 x1 X10 卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）举例：举例：最小项的性质：最小项的性质：全体最小项之和（“或”运算）为1。任意2个最小项互不相交，故任意2个最小项之积（“与”运算）为0。若2个最小项之间只有1个文字不同，即在一个最小项中该文字为原变量，而在另一个最小项中该文字为反变量，则称这2个最小项“逻辑相邻”。根据公式（1-11a），逻辑相邻的2个最小

23、项可以合并为1个乘积项，并且合并所得乘积项中的文字个数减少1个。卡诺图是把逻辑相邻的最小项尽量安排成几何位置相邻，通过观察即可判定哪些最小项可以合并。2008.112008.11薛宏熙数字逻辑设计cha29 x2x1 x4x3 2 个相邻的 0 维块合并为 1 个 1 维块 001X 2 个相邻的 1 维块合并为 1 个 2 维块 1XX1 “X”表示该变量因 块的合并而被消去 卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续） 举例：举例：2008.112008.11薛宏熙数字逻辑设计cha30 x4x3 x2x1 14xx 1XX0 ( a ) x4x3 13xx X0X0 x2x1 (

24、b ) 123xxx X010 卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续） 逻辑相邻与几何相邻：逻辑相邻与几何相邻：2个逻辑相邻的乘积项在卡诺图中表现为几何位置的相邻，使我们通过观察图形即可实现块的合并，达到化简逻辑函数的目的。可以把卡诺图想象为一张图纸，将其卷成一个圆筒，则原来两边不相邻的部分就变成相邻的部分了。 2008.112008.11薛宏熙数字逻辑设计cha31卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续） 5变量卡诺图：变量卡诺图：变量个数 5时，很难画出对应的卡诺图！2008.112008.11薛宏熙数字逻辑设计cha32卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（

25、续）概念提升概念提升： 蕴含项（蕴含项（implicant）若某乘积项能指明输入变量的取值组合可使给定逻辑函数若某乘积项能指明输入变量的取值组合可使给定逻辑函数 f 取值取值为为1，则该乘积项是函数，则该乘积项是函数 f 的蕴含项。的蕴含项。 蕴含项的包含关系（蕴含项的包含关系（contain）设蕴含项设蕴含项 A 由相邻最小项集合由相邻最小项集合 Sa 合并而成，蕴含项合并而成，蕴含项 B 由相邻最由相邻最小项集合小项集合 Sb 合并而成。若，即合并而成。若，即 Sa 中的每一个最小项都存在于中的每一个最小项都存在于Sb中，则称蕴含项中，则称蕴含项B包含蕴含项包含蕴含项A，记作，记作 。 质

26、蕴含项（质蕴含项（prime implicant）若某蕴含项不被其他任何一个蕴含项所包含，则该蕴含项是质蕴若某蕴含项不被其他任何一个蕴含项所包含，则该蕴含项是质蕴含项。在卡诺图中，若某个由相邻最小项构成的块已经是维数最含项。在卡诺图中，若某个由相邻最小项构成的块已经是维数最大的块，不被其它任何一个块所包含，则该块对应的乘积项是质大的块，不被其它任何一个块所包含，则该块对应的乘积项是质蕴含项。蕴含项。BA 2008.112008.11薛宏熙数字逻辑设计cha33卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）概念提升概念提升： 特征最小项和必要质蕴含项（特征最小项和必要质蕴含项（essenti

27、al prime implicant）若某最小项仅被唯一的一个质蕴含项所包含，则该最小项称为特若某最小项仅被唯一的一个质蕴含项所包含，则该最小项称为特征最小项，包含特征最小项的质蕴含项称为必要质蕴含项。征最小项，包含特征最小项的质蕴含项称为必要质蕴含项。 1 ： 特征最小项 ：必要质蕴含项 ：质蕴含项 ：非质蕴含项 x4 x3 x2 x1 2008.112008.11薛宏熙数字逻辑设计cha34卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）概念提升：概念提升：覆盖（覆盖（cover）若一个蕴含项的集合能说明给定逻辑函数若一个蕴含项的集合能说明给定逻辑函数 f 为为 1 的所有情况，则称此蕴

28、含的所有情况，则称此蕴含项集合是函数项集合是函数 f 的覆盖。覆盖和函数的的覆盖。覆盖和函数的“积之和积之和”表达式相对应。表达式相对应。最小覆盖（最小覆盖（minimal cover）函数的最小覆盖和成本最低的函数的最小覆盖和成本最低的“积之和积之和”表达式相对应，其要求为：表达式相对应，其要求为： 1. 最小覆盖中包含的蕴含项个数最少。最小覆盖中包含的蕴含项个数最少。 2. 每一个蕴含项的文字个数尽量少，即蕴含项的维数尽量大。每一个蕴含项的文字个数尽量少，即蕴含项的维数尽量大。 必要质蕴含项必定是最小覆盖的元素。必要质蕴含项必定是最小覆盖的元素。无冗余覆盖（无冗余覆盖（non-redund

29、ant cover） 1. 覆盖中每一个蕴含项必须是质蕴含项。覆盖中每一个蕴含项必须是质蕴含项。 2. 覆盖中不含冗余项。覆盖中不含冗余项。 当变量个数很多时，若求解函数的最小覆盖有困难，可退而求其次，当变量个数很多时，若求解函数的最小覆盖有困难，可退而求其次，转而求无冗余覆盖。转而求无冗余覆盖。2008.112008.11薛宏熙数字逻辑设计cha35 x4x3 x2x1 : 冗余蕴含项 : 必要质蕴含项 卡诺图卡诺图 化简逻辑函数（续）化简逻辑函数（续）概念提升：概念提升：冗余项（冗余项（redundant term）设设 A 是覆盖是覆盖 C 中的一个蕴含项，若中的一个蕴含项，若 A 所包

30、含的每一个最小项皆存在于所包含的每一个最小项皆存在于 C 中其它的蕴含项之中，则称中其它的蕴含项之中，则称 A 是相对于覆盖是相对于覆盖 C 的冗余项。换句话说，的冗余项。换句话说，没有独立贡献的蕴含项是冗余项。没有独立贡献的蕴含项是冗余项。 2008.112008.11薛宏熙数字逻辑设计cha361.6 逻辑函数的标准形式逻辑函数的标准形式 函数的函数的积之和积之和表达式表达式: :式（式（1 -19）和）和 式（式（1 -20）都是积之和表达式。）都是积之和表达式。式（式（1 -19）中每一个乘积项都是最小项，被称为积之和的标准形式。）中每一个乘积项都是最小项，被称为积之和的标准形式。积之

31、和标准形式的另一种表示方法：积之和标准形式的另一种表示方法：)191 (123123123xxxxxxxxxf)201 (12312xxxxxf)221 (7, 6, 2)(762123123123mmmmxxxxxxxxxf2008.112008.11薛宏熙数字逻辑设计cha371.6 逻辑函数的标准形式逻辑函数的标准形式 函数的函数的和之积和之积与与积之和积之和表达式表达式: :将反演规则施加于式（将反演规则施加于式（1-19） ：若函数若函数 ，则，则)191 (123123123xxxxxxxxxf)()()(123123123123123123123123123xxxxxxxxxxx

32、xxxxxxxxxxxxxxxxffg )()()(123123123xxxxxxxxxg和之积和之积表达式表达式2008.112008.11薛宏熙数字逻辑设计cha38逻辑函数的标准形式（续）逻辑函数的标准形式（续） 最大项与最小项的对应关系最大项与最小项的对应关系 ：2008.112008.11薛宏熙数字逻辑设计cha39逻辑函数的标准形式（续）逻辑函数的标准形式（续） 最大项与最小项的对应关系最大项与最小项的对应关系 ： 和之积标准形式的另一种表示方法：和之积标准形式的另一种表示方法：)7, 6, 2()()()(762123123123MMMMxxxxxxxxxg2008.112008

33、.11薛宏熙数字逻辑设计cha40包含无关项的逻辑函数的化简包含无关项的逻辑函数的化简 【例【例1.10】父亲、母亲为小女儿买一件衣服，是否购买取决于父亲、母亲为小女儿买一件衣服，是否购买取决于3个个人对该商品的态度：人对该商品的态度：3人全部赞成则购买；人全部赞成则购买；2人赞成则可买可不买；人赞成则可买可不买；1人赞成或无人赞成则不买。人赞成或无人赞成则不买。 行号行号 x3 x2 x1 f 解解 释释 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 不买 3 0 1 1 d 2 人赞成，可买可不买 4 1 0 0 0 不买 5 1 0 1 d 2 人赞成，可买可不买 6 1

34、1 0 d 2 人赞成，可买可不买 7 1 1 1 1 必买 符号“d ”表示函数 f 的取值任意，即无关项。 )261 ()6, 5, 3()7(dmf2008.112008.11薛宏熙数字逻辑设计cha41包含无关项的逻辑函数的化简（续）包含无关项的逻辑函数的化简（续） 用卡诺图化简不完全确定的逻辑函数用卡诺图化简不完全确定的逻辑函数 d 的取值可为的取值可为 0 也可为也可为 1，以简化效果最佳为目的。，以简化效果最佳为目的。 本例化简结果为：本例化简结果为：)261 ()6, 5, 3()7(dmf x3x2 x1 1 维块 X11，对应于x2 x1 12xxf 2008.112008

35、.11薛宏熙数字逻辑设计cha42包含无关项的逻辑函数的化简（续）包含无关项的逻辑函数的化简（续）【例【例1.11】 假定用假定用 4 位二进制代码表示位二进制代码表示 1 位十进制数，判断此种位十进制数，判断此种十进制数的值是否大于等于十进制数的值是否大于等于 5。 2008.112008.11薛宏熙数字逻辑设计cha43包含无关项的逻辑函数的化简（续）包含无关项的逻辑函数的化简（续）【例【例1.11】 逻辑表达式逻辑表达式 化简结果：化简结果： )721 ()151413121110()98765(，dmfzzzzzzzzzzzzzzzzzzzzzzz x3x1 x4x3 x2x1 x3x

36、2 x4 13234xxxxxf2008.112008.11薛宏熙数字逻辑设计cha441.7 *表格法化简逻辑函数表格法化简逻辑函数 Willared Quine和和Edward McCluskey在二十世纪五十年代提出了在二十世纪五十年代提出了表格法化简逻辑函数，表格法也因而被称为表格法化简逻辑函数，表格法也因而被称为Quine-McCluskey法，法，简称简称Q-M法。法。 表格法的优点：表格法的优点： 变量的个数不受限制，适合于多变量逻辑函数的化简。变量的个数不受限制，适合于多变量逻辑函数的化简。 规律性很强，可以写出严格的算法。规律性很强，可以写出严格的算法。 表格法的缺点：表格法

37、的缺点： 当函数的变量很多时，手工操作仍不胜其烦。当函数的变量很多时，手工操作仍不胜其烦。 计算机程序擅长于处理多重循环和复杂的操作，所以它适合于编写计算机程序擅长于处理多重循环和复杂的操作，所以它适合于编写逻辑综合软件。逻辑综合软件。 与其它逻辑综合算法相比较，表格法出现较早，不是最高效的却是与其它逻辑综合算法相比较，表格法出现较早，不是最高效的却是最简单的。最简单的。 学习表格法的目的：学习表格法的目的： 了解了解EDA 工具的工作原理，从而更好地使用工具的工作原理，从而更好地使用EDA工具。工具。 有助于学习更先进的逻辑综合算法。有助于学习更先进的逻辑综合算法。 2008.112008.

38、11薛宏熙数字逻辑设计cha45表格法化简逻辑函数（续）表格法化简逻辑函数（续） 表格法化简逻辑函数的步骤：表格法化简逻辑函数的步骤：1. 从函数的真值表描述求出其全部质蕴含项的集合，记从函数的真值表描述求出其全部质蕴含项的集合，记作作Z。2 . 从质蕴含项集合从质蕴含项集合Z中挑选出一个子集中挑选出一个子集M，要求，要求M是最小是最小覆盖。即覆盖。即（1）M覆盖全部最小项。至于无关项，属于可覆盖、可覆盖全部最小项。至于无关项，属于可覆盖、可 不覆盖之列。不覆盖之列。（2）M的成本最低。的成本最低。2008.112008.11薛宏熙数字逻辑设计cha46求质蕴含项集合求质蕴含项集合Z 的算法流

39、程图的算法流程图 2008.112008.11薛宏熙数字逻辑设计cha47用表格法求函数的质蕴含项集合用表格法求函数的质蕴含项集合Z 的实例（例的实例（例1.12）step1 建立初始表格（表建立初始表格（表1.10 ）：）：求质蕴含项集合时，可对最小项和无关项不加区分，一律用求质蕴含项集合时，可对最小项和无关项不加区分，一律用m i 表示。表示。 按按 0 维块中含维块中含“1”的个数将其分组，组号即该的个数将其分组，组号即该 0 维块中含维块中含“1”的个数，分组的个数，分组的目的是为了提高的目的是为了提高“逐对逐对”比较的效率，因为相邻块只可能在相邻组中出现。比较的效率，因为相邻块只可能

40、在相邻组中出现。 )28(1)10()15,13,12,11, 8, 4, 0(),(1234dmxxxxf，若某个 0 维块被后续形成的1 维块包含， 则用“ ”作标记。2008.112008.11薛宏熙数字逻辑设计cha48用表格法求函数的质蕴含项集合用表格法求函数的质蕴含项集合Z 的实例（续）的实例（续）step2 相邻块合并：相邻块合并： 表表1.11 若某个 1 维块被后续形成的2 维块包含， 则用“ ”作标记。2008.112008.11薛宏熙数字逻辑设计cha49用表格法求函数的质蕴含项集合用表格法求函数的质蕴含项集合Z 的实例（续）的实例（续）step2 相邻块继续合并：相邻块

41、继续合并： 表表1.12 凡是没有标记凡是没有标记“”的蕴含项都是质蕴含项，从而构成全部质蕴的蕴含项都是质蕴含项，从而构成全部质蕴含项集合含项集合Z。为了下一步求最小覆盖的方便，我们用速记符标记。为了下一步求最小覆盖的方便，我们用速记符标记每一个质蕴含项，分别写在表每一个质蕴含项，分别写在表1.11和表和表1.12的第的第4列。即列。即 P1, P2, P3, P4, P5, P6 2008.112008.11薛宏熙数字逻辑设计cha50*求最小覆盖求最小覆盖2008.112008.11薛宏熙数字逻辑设计cha51求最小覆盖的实例（例求最小覆盖的实例（例1.13）例例 1.12 已经求出了函数

42、已经求出了函数 f 的质蕴含项集合的质蕴含项集合Z，现在求其最，现在求其最小覆盖小覆盖。step1 建立初始表格：建立质蕴含项覆盖表（表建立初始表格：建立质蕴含项覆盖表（表1.13）。）。每一个质蕴涵项在表中占据一行，每一个应被覆盖的最小项在表中占每一个质蕴涵项在表中占据一行，每一个应被覆盖的最小项在表中占据一列，然后用标志符据一列，然后用标志符“”指明该最小项被哪些质蕴涵项所覆盖。指明该最小项被哪些质蕴涵项所覆盖。 表表 1.13 蕴含项覆盖表蕴含项覆盖表 待覆盖的最小项待覆盖的最小项 质蕴含项质蕴含项 m0 m4 m8 m11 m12 m13 m15 P 1 = 10X0 P 2 = 10

43、1X P 3 = 110X P 4 = 1X11 P5 = 11X1 P6 = XX00 2008.112008.11薛宏熙数字逻辑设计cha52求最小覆盖的实例（续）求最小覆盖的实例（续） Step2 选优：选优：如果表如果表1.13某列中只有一个标志符某列中只有一个标志符“”，则覆盖该最小项的质，则覆盖该最小项的质蕴涵项是必要质蕴涵项，它必须被包含在所求的最小覆盖中。蕴涵项是必要质蕴涵项，它必须被包含在所求的最小覆盖中。对于本例，对于本例， p6 是必要质蕴涵项，将是必要质蕴涵项，将p6加入加入M。将对应于必要质蕴涵项将对应于必要质蕴涵项 p6 的行以及被的行以及被 p6 覆盖的列（覆盖的列（m0，m4 ，m8，m12）从表中删除，）从表中删除， 2008.112008.11薛宏熙数字逻辑设计cha53求最小覆盖的实例（续）求最小覆盖的实例（续） Step2 选优继续：选优继续：删除必要质蕴含项删除必要质蕴含项 P6