第二章逻辑代数

1、2 .逻辑代数与硬件描述语言基础逻辑代数与硬件描述语言基础2.1 逻辑代数逻辑代数 2.2 逻辑函数的卡诺图化简法逻辑函数的卡诺图化简法 教学基本要求教学基本要求1 1、熟悉逻辑代数常用基本定律、恒等式熟悉逻辑代数常用基本定律、恒等式和规则。和规则。2 2、掌握逻辑代数的变换和卡诺图化简法；、掌握逻辑代数的变换和卡诺图化简法； 2.1.1 逻辑代数的基本定律和恒等式逻辑代数的基本定律和恒等式2.1 逻辑代数逻辑代数2.1.3 逻辑函数的变换及代数化简法逻辑函数的变换及代数化简法2.1.2 逻辑代数的基本规则逻辑代数的基本规则1 1、基本公式基本公式交换律：交换律： A + B = B + AA

2、 B = B A结合律：结合律：A + B + C = (A + B) + C A B C = (A B) C 分配律：分配律：A + BC = ( A + B )( A + C )A ( B + C ) = AB + AC A 1 = AA 0 = 0A + 0 = AA + 1 = 10 0、1 1律：律：A A = 0A + A = 1互补律：互补律：2.2.1.11.1逻辑代数的基本定律和恒等式逻辑代数的基本定律和恒等式AA 还原律还原律: 普通代数没有！普通代数没有！ 重叠律重叠律：A + A = AA A = A反演律：反演律：AB = A + B A + B = A BAA BA

3、B() ()ABACABCABAAAABA()吸收律吸收律 其它常用恒等式其它常用恒等式 ABACBCAB + ACABACBCDAB + AC2、基本公式的证明基本公式的证明例例 证明证明ABA BABA B，列出等式、右边的函数值的真值表列出等式、右边的函数值的真值表( (真值表证明法真值表证明法) )011 = 001+1=00 01 1110 = 101+0=00 11 0101 = 100+1=01 00 1100 = 110+0=11 10 0A+BA+BA B A BABA BA+AB = A ， A(A+B) = AA+ B = A+B，A( +B ) = AB , AAA +

4、 AB = A (1 + B) = A()()AABAA ABABABABA()ABABA BBA()()ABABA()()AB ABABBA例例 证明证明CAABBCDECAABCAABBCCAAB 在在 “与或与或”逻辑式中，一个与项包含了另外两个含有逻辑式中，一个与项包含了另外两个含有互为反变量的与项的其余部分，则该与项是多余的（项）。互为反变量的与项的其余部分，则该与项是多余的（项）。 例例 证明证明 2.1.2 逻辑代数的基本规则逻辑代数的基本规则 代入规则代入规则 ： 在包含变量在包含变量A逻辑等式中，如果用另一逻辑等式中，如果用另一个函数式代入式中所有个函数式代入式中所有A的位置

5、，则等式仍然成立。这一规的位置，则等式仍然成立。这一规则称为代入规则。则称为代入规则。例例：B (A + C) = BA+BC用用A + D代替代替A A，得得B (A +D) +C = B(A +D) + BC = BA + BD + BC代入规则可以扩展所有基本公式或定律的应用范围代入规则可以扩展所有基本公式或定律的应用范围例如，在反演律中用例如，在反演律中用BC去代替等式中的去代替等式中的B，则，则新的等式仍成立：新的等式仍成立：ABABCBABCAABC 对于任意一个逻辑表达式对于任意一个逻辑表达式L，若将其中所有的与（，若将其中所有的与（ ）换成）换成或（或（+），或（），或（+）换

6、成与（）换成与（）；原变量换为反变量，反变）；原变量换为反变量，反变量换为原变量；将量换为原变量；将1换成换成0，0换成换成1；则得到的结果就是原；则得到的结果就是原函数的反函数。函数的反函数。2. 2. 反演规则：反演规则：)(1)(DCBADCB)(AL 0 CDBAL例例2.1.1 试求试求 的非函数的非函数解：按照反演规则，得解：按照反演规则，得 在应用反演规则求反函数时要注意以下两点：（1）保持运算的优先顺序不变，必要时加括号表明；（2）变换中，几个变量（一个以上）的公共非号保持不变。LABCDELLABCDE求的非函数 。（）LABAC 对于任何逻辑函数式，若将其中的与（对于任何逻

7、辑函数式，若将其中的与（ ）换成或（）换成或（+），或（），或（+）换成与（换成与（）；并将）；并将1换成换成0，0换成换成1；那么，所得的新的函数式就；那么，所得的新的函数式就是是L的对偶式，记作的对偶式，记作 。 L()()LAB A C例例: 逻辑函数逻辑函数 的对偶式为的对偶式为3. 3. 对偶规则：对偶规则：同一个逻辑函数可以有多种表达形式，比如：同一个逻辑函数可以有多种表达形式，比如：()()1 ()AABAA ABABAB 2.1.3 逻辑函数的代数变换与化简逻辑函数的代数变换与化简逻辑函数化简的目的：1、尽可能简化电路、节约成本。2、在条件不成熟时，使用替代电路完成任务。如：如

8、果实验室中只有与非门，如何实现LAB+AC注意：没有与门、没有或门，所以注意：没有与门、没有或门，所以这个电路无法这样制造。这个电路无法这样制造。考虑到要用到非关系，我们可以使用还原律，变换。如下：LABACABACAB AC上面一个非号不变，下面一个非号利用摩根定律展开。这时，所有的关系都是“与非”了，可以焊接完成了！“或或-与与”表达式表达式“与非与非-与非与非”表达式表达式 “与与- -或或- -非非”表达式表达式“或非或非或非或非” ” 表达表达式式“与与- -或或” ” 表达式表达式 2.1.3 逻辑函数的代数法化简逻辑函数的代数法化简 DCACL DC A C = )DC)(CA(

9、 )C+D()CA( DCCA 1 1、逻辑函数的最简与、逻辑函数的最简与- -或表达式或表达式其中，与其中，与或表达式是逻辑函数的最基本表达形式。或表达式是逻辑函数的最基本表达形式。一个逻辑函数的表达式不是唯一的，除了与一个逻辑函数的表达式不是唯一的，除了与或式外，还有或或式外，还有或与式、与式、与非与非与非式、或非与非式、或非或非及与或非及与或或非式。可以有多种形式，非式。可以有多种形式，并且能互相转换。例如：并且能互相转换。例如：与或式 与非式LACCDACCDAC CD下面重点讨论与或式，该形式最容易获得，而且只需要利用一次摩下面重点讨论与或式，该形式最容易获得，而且只需要利用一次摩根

10、定律就可以变形成为与非与非式，从而比较容易用与非门实现根定律就可以变形成为与非与非式，从而比较容易用与非门实现但是，并不是所有的与或式都是最简的，因此有：逻辑函数的最简但是，并不是所有的与或式都是最简的，因此有：逻辑函数的最简“与与或表达式或表达式” 逻辑函数的最简逻辑函数的最简“与与或表达式或表达式” ” 的标准的标准 表达式中表达式中与项与项最少。（最少。（“+”+”越少越好）越少越好） 每个每个与项与项中的变量数最少。中的变量数最少。2、逻辑函数的化简：即化简成最简与或表达式、逻辑函数的化简：即化简成最简与或表达式 化简的主要方法：化简的主要方法：公式法（代数法）公式法（代数法）图解法（

11、卡诺图法）图解法（卡诺图法）代数化简法：代数化简法： 运用逻辑代数的基本定律和恒等式进行化简的方法。运用逻辑代数的基本定律和恒等式进行化简的方法。 1AA并项法并项法: : CBA CBAL BA)CC(BA )()(CBCBACBBCAL 例：例：CBACABCBAABC )()(CCBACCAB BAAB ABBA )(1 AAABBA 吸收法：吸收法： A + AB = A 消去法消去法： BABAA CABAB CAB 配项法配项法： CA=AB BAFEBCDABAL )(CBAAB)( CBCAABL A+AB=A+BCBCAABL CBAACAAB)( CBACABCA=AB )

12、()(BCACACABAB 例例 化简化简EFBEFBABDCAABDAADL 解：解：EFBEFBABDCAABAL EFBBDCAA （利用（利用A+AB=A）EFBBDCA （利用（利用 ）BABAA 代数化简法：代数化简法：优点：优点：不受变量数目的限制。不受变量数目的限制。缺点：缺点：没有固定的步骤可循；需要熟练运用各种公式和定理；需要一定没有固定的步骤可循；需要熟练运用各种公式和定理；需要一定的技巧和经验；不易判定化简结果是否最简。的技巧和经验；不易判定化简结果是否最简。)CC(DBADBA)DD(ABL DBADBA=AB )(DDBAAB BAAB BAAB BAAB CDBA

13、DCBAABDDBADABL 例例2.1.7 已知逻辑函数表达式为已知逻辑函数表达式为，要求：（要求：（1）最简的与）最简的与-或逻辑函数表达式；或逻辑函数表达式； （2）仅用与非门画出最简表达式的逻辑图。）仅用与非门画出最简表达式的逻辑图。解：解：) B A L AB BA & & & & & CBACBA CBACBA CBACBA B L CBA 1 1 1 A C CBA 1 1 1 CBACBAL 例例2.1.8 试对逻辑函数表达式试对逻辑函数表达式进行变换，仅用或非门画出该表达式的逻辑图。进行变换，仅用或非门画出该表达式的逻辑图。解：解： C

14、BACBAL 2.2 逻辑函数的卡诺图化简法逻辑函数的卡诺图化简法2.2.2 逻辑函数的最小项表达式逻辑函数的最小项表达式2.2.1 最小项的定义及性质最小项的定义及性质2.2.4 用卡诺图化简逻辑函数用卡诺图化简逻辑函数2.2.3 用卡诺图表示逻辑函数用卡诺图表示逻辑函数1.逻辑代数与普通代数的公式易混淆，化简过程要求对所逻辑代数与普通代数的公式易混淆，化简过程要求对所有公式熟练掌握；有公式熟练掌握；2.代数法化简无一套完善的方法可循，它依赖于人的经验代数法化简无一套完善的方法可循，它依赖于人的经验和灵活性；和灵活性；3.用这种化简方法技巧强，较难掌握。特别是对代数化简用这种化简方法技巧强，

15、较难掌握。特别是对代数化简后得到的逻辑表达式是否是最简式判断有一定困难。后得到的逻辑表达式是否是最简式判断有一定困难。卡诺图法可以比较简便地得到最简的逻辑表达式。卡诺图法可以比较简便地得到最简的逻辑表达式。代数法化简在使用中遇到的困难：代数法化简在使用中遇到的困难：n个变量个变量X1, X2, , Xn的最小项是的最小项是n个因子的乘积，每个变量个因子的乘积，每个变量都以它的原变量或非变量的形式在乘积项中出现一次，且仅出都以它的原变量或非变量的形式在乘积项中出现一次，且仅出现一次。一般现一次。一般n个变量的最小项应有个变量的最小项应有2n个。个。 BAACBA、 、A(B+C)等则不是最小项。

16、等则不是最小项。例如，例如，A、B、C三个逻辑变量的最小项有（三个逻辑变量的最小项有（23 8 ）个，即）个，即 CBACBACBABCACBACBACABABC、1. 最小项的意义最小项的意义2.2 .1 最小项的定义及其性质最小项的定义及其性质对于变量的任一组取值，全体最小项之和为对于变量的任一组取值，全体最小项之和为1 1。对于任意一个最小项，只有一组变量取值使得它的值为对于任意一个最小项，只有一组变量取值使得它的值为1 1； 对于变量的任一组取值，任意两个最小项的乘积为对于变量的任一组取值，任意两个最小项的乘积为0 0；CBABCACBACBACBACABABCCBAABC0 00 0

17、0 01 10 00 00 00 00 00 00 00 00 01 10 01 10 00 00 00 00 00 00 01 10 00 00 01 10 00 00 00 00 01 10 00 00 00 00 00 01 10 00 00 00 01 11 10 00 00 01 10 00 00 00 01 10 01 10 00 00 00 00 01 10 00 01 11 10 00 00 00 00 00 00 01 10 01 11 11 10 00 00 00 00 00 00 01 1三个变量的所有最小项的真值表三个变量的所有最小项的真值表 2、最小项的性质最小项的性

18、质 3、最小项的编号最小项的编号 三个变量的所有最小项的真值表三个变量的所有最小项的真值表 m0m1m2m3m4m5m6m7最小项的表示：通常用最小项的表示：通常用mi表示最小项，下标表示最小项，下标i为最小项编号。为最小项编号。 ABC0 00 00 01 10 00 00 00 00 00 00 00 00 01 10 01 10 00 00 00 00 00 00 01 10 00 00 01 10 00 00 00 00 01 10 00 00 00 00 00 01 10 00 00 00 01 11 10 00 00 01 10 00 00 00 01 10 01 10 00 00

19、 00 00 01 10 00 01 11 10 00 00 00 00 00 00 01 10 01 11 11 10 00 00 00 00 00 00 01 1CBABCACBACBACBACABABCCBA 2.2.2 逻辑函数的最小项表达式逻辑函数的最小项表达式 ( ,)()()L A B CAB CCA BB Cl 为为“与或与或”逻辑表达式；逻辑表达式； l 在在“与或与或”式中的每个乘积项都是最小项。式中的每个乘积项都是最小项。例例1 1 将将( , ,)L A B CABAC化成最小项表达式化成最小项表达式ABCABCABCABC= m7m6m3m5 (7, 6 3 5)m,

20、 ,()L ABCABCABCABCABC逻辑函数的最小项表达式：逻辑函数的最小项表达式：利用逻辑代数的基本公式利用逻辑代数的基本公式, ,可以把任一个逻辑函数化成若可以把任一个逻辑函数化成若干个最小项之和的形式干个最小项之和的形式, ,称为最小项表达式称为最小项表达式( , ,)()L A B CABABC AB 例例2 将将 化成最小项表达式化成最小项表达式 a.去掉非号去掉非号()()L A,B,CABABCAB()AB AB CAB()()AB AB CABb.去括号去括号ABCABCAB()ABCABCAB CCABCABCABCABC3576(3,5,6,7)mmmmm2.2.3

21、用卡诺图表示逻辑函数用卡诺图表示逻辑函数1、卡诺图的引出卡诺图的引出卡诺图：将卡诺图：将n变量的全部最小项都用小方块表示，并使具有变量的全部最小项都用小方块表示，并使具有逻辑相邻的最小项在几何位置上也相邻地排列起来，这样逻辑相邻的最小项在几何位置上也相邻地排列起来，这样, ,所得到的图形叫所得到的图形叫n变量的卡诺图。变量的卡诺图。逻辑相邻的最小项：如果两个最小项只有一个变量互为反变逻辑相邻的最小项：如果两个最小项只有一个变量互为反变量，那么，就称这两个最小项在逻辑上相邻。量，那么，就称这两个最小项在逻辑上相邻。如最小项如最小项m6=ABC、与与m7 =ABC 在逻辑上相在逻辑上相邻邻m6m7

22、AB10100100011110 m0 m1 m2 m3 m4 m5 m6 m7 m12 m13 m14 m15 m8 m9 m10 m110001111000011110ABCD三变量卡诺图三变量卡诺图四变量卡诺图四变量卡诺图BABABAAB两变量卡诺图两变量卡诺图m0m1m2m3ACCCBABCACBABCACBACBACBAABCCAB m0 m1 m2 m3 m4 m5 m6 m7ADBBm0m1m3m2m4m5m7m6m12m13m15m14m8m9m11m10DCBADCBACDBADCBADCBADCBABCDADBCADCABDCABABCDDABCDCBADCBACDBADC

23、BA CD 00 01 11 10 AB 00 01 11 10四变量卡诺图四变量卡诺图卡诺图具有很强的相邻性：卡诺图具有很强的相邻性：l 直观相邻性，只要小方格直观相邻性，只要小方格在几何位置上相邻（不管上在几何位置上相邻（不管上下左右），它代表的最小项下左右），它代表的最小项在逻辑上一定是相邻的。在逻辑上一定是相邻的。 对边相邻性，即与中心轴对边相邻性，即与中心轴对称的左右两边和上下两边对称的左右两边和上下两边的小方格也具有相邻性的小方格也具有相邻性。 2、卡诺图的特点、卡诺图的特点几何相邻必逻辑相邻几何相邻必逻辑相邻3. 已知逻辑函数画卡诺图已知逻辑函数画卡诺图当逻辑函数为最小项表达式时

24、，在卡诺图中找出和表达式中当逻辑函数为最小项表达式时，在卡诺图中找出和表达式中最小项对应的小方格填上最小项对应的小方格填上1，其余的小方格填上，其余的小方格填上0（有时也可（有时也可用空格表示），就可以得到相应的卡诺图。任何逻辑函数都用空格表示），就可以得到相应的卡诺图。任何逻辑函数都等于其卡诺图中为等于其卡诺图中为1的方格所对应的最小项之和。的方格所对应的最小项之和。例例1：画出逻辑函数：画出逻辑函数L(A, B, C, D)= m(0, 1, 2, 3, 4, 8, 10, 11, 14, 15)的卡诺图的卡诺图 1 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 10 11

25、01 00 CD 00 01 11 10 AB L DABDADBA DBACDBADCBA BDABCDADCBA m0 m1 m3 m2 m4 m5 m7 m6 m12 m13 m15 m14 m8 m9 m11 m10 AB CD 00 01 11 10 00 01 11 10 ADABDDBA DADDA 相邻项相加时，反复应用相邻项相加时，反复应用 公式，函数表达式的项数和每公式，函数表达式的项数和每项所含的因子数就会减小，逻辑表达式就得到简化，这就是卡诺图项所含的因子数就会减小，逻辑表达式就得到简化，这就是卡诺图化简函数的基本原理。化简函数的基本原理。1 AA 2.3.4 用卡诺图

26、化简逻辑函数用卡诺图化简逻辑函数 1卡诺图化简函数(合并最小项)的依据 : 在卡诺图中处于相邻位置的最小项均可以合并为一项，消去了不同的因子。2、化简的步骤、化简的步骤用卡诺图化简逻辑函数的步骤如下：用卡诺图化简逻辑函数的步骤如下：(4) 将所有包围圈对应的乘积项相加。将所有包围圈对应的乘积项相加。(1) 将逻辑函数写成最小项表达式将逻辑函数写成最小项表达式(2) 按最小项表达式填卡诺图，凡式中包含了的最小项，按最小项表达式填卡诺图，凡式中包含了的最小项，其对应方格填其对应方格填1，其余方格填，其余方格填0。(3) 圈组圈组:找出可以合并的最小项，即将相邻的找出可以合并的最小项，即将相邻的1方

27、格圈成方格圈成一组一组(包围圈包围圈)，每一组含，每一组含2n个方格，对应每个包围圈写个方格，对应每个包围圈写成一个新的乘积项。本书中包围圈用虚线框表示。成一个新的乘积项。本书中包围圈用虚线框表示。画包围圈时应遵循的原则：画包围圈时应遵循的原则： （1 1）包围圈内的方格数一定是）包围圈内的方格数一定是2n个，且包围圈必须呈矩形。个，且包围圈必须呈矩形。（2）循环相邻方格包括上下底相邻，左右边相邻和四角相邻。循环相邻方格包括上下底相邻，左右边相邻和四角相邻。 （3）同一方格可以被不同的包围圈重复包围多次，但新增的包围圈同一方格可以被不同的包围圈重复包围多次，但新增的包围圈 中一定要有原有包围圈

28、未曾包围的方格。中一定要有原有包围圈未曾包围的方格。 （4） 一个包围圈的方格数要尽可能多一个包围圈的方格数要尽可能多( (即乘积项中变量最少即乘积项中变量最少),), 包围圈的数目要尽可能少包围圈的数目要尽可能少( (即乘积项少即乘积项少) )。 m0 m1 m3 m2 m4 m5 m7 m6 m12 m13 m15 m14 m8 m9 m11 m10 00 01 11 10 AB CD 00 01 11 10 m0 m1 m3 m2 m4 m5 m7 m6 m12 m13 m15 m14 m8 m9 m11 m10 00 01 11 10 AB CD 00 01 11 10 DBBDL B

29、D 例例 :用卡诺图法化简下列逻辑函数用卡诺图法化简下列逻辑函数（2）合并最小项，得最简与）合并最小项，得最简与-或表达式或表达式 解：解：(1) 由由L 画出卡诺图画出卡诺图 m)D,C,B,A(L(0，2，5，7，8，10，13，15) L C 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 D A B DB 1 1 1 00 AB L 01 10 11 CD 11 00 00 01 10 011 1111111111110( , , ,)(03,57,811,1315)L A B C DmLDCBB例例: : 用卡诺图化简用卡诺图化简 1 1 1 00 AB L 01 1

30、0 11 CD 11 00 00 01 10 011 1111111111110CD圈圈0LBCDLDCB圈圈12.2.5 含无关项的逻辑函数及其化简含无关项的逻辑函数及其化简1 1、什么叫无关项：、什么叫无关项：在真值表内对应于变量的某些取值下，函数的值可以是任意的，或者这些变量在真值表内对应于变量的某些取值下，函数的值可以是任意的，或者这些变量的取值根本不会出现，这些变量取值所对应的最小项称为无关项或任意项。的取值根本不会出现，这些变量取值所对应的最小项称为无关项或任意项。在含有无关项逻辑函数的卡诺图化简中，它的值可以取在含有无关项逻辑函数的卡诺图化简中，它的值可以取0 0或取或取1 1，具体取什么值，具体取什么值，可以根据使函数尽量得到简化而定。可以根据使函数尽量得到简化而定。例如例如 8421 码中，码中，1010 1111这这 6 种