第2章 逻辑代数基础

1、1 第二章第二章 逻辑代数基础逻辑代数基础 Chapter 2 Logic Algebra Basic 本章主要内容本章主要内容 第一节第一节 数制与码制数制与码制 第二节第二节 逻辑代数的基本概念与运算逻辑代数的基本概念与运算 第三节第三节 逻辑函数的公式化简法逻辑函数的公式化简法 第四节第四节 逻辑函数的卡诺图化简法逻辑函数的卡诺图化简法 第五节第五节 具有无关项的逻辑函数及其化简具有无关项的逻辑函数及其化简 2 2.2 逻辑代数基本概念和运算规则逻辑代数基本概念和运算规则 上次授课内容上次授课内容 回顾回顾 布尔代数、真布尔代数、真(“1”)和和假假(“0”)、逻辑变量与逻辑函数逻辑变量

2、与逻辑函数 逻辑代数的基本运算：逻辑代数的基本运算：与、或、非与、或、非及图形符号表示：及图形符号表示： 复合逻辑运算：复合逻辑运算：与非、或非、与或非、同或、异或与非、或非、与或非、同或、异或等。等。 3 上次授课内容上次授课内容 回顾回顾 复合逻辑复合逻辑 运算：运算： 与非、与非、 或非、或非、 与或非、与或非、 同或、同或、 异或异或等。等。 4 上次授课内容上次授课内容 回顾回顾 一、逻辑表达式（函数式）一、逻辑表达式（函数式） 二、真值表二、真值表 三、逻辑电路图三、逻辑电路图 四、卡诺图四、卡诺图 五、波形图（时序图）五、波形图（时序图） 六、文字描述六、文字描述 描述逻辑函数的

3、方法有以下六种：描述逻辑函数的方法有以下六种： 5 逻辑代数基本定律总结表逻辑代数基本定律总结表 定律名称定律名称公公 式式 01律律 自等律自等律 重叠律重叠律 互补律互补律 交换律交换律 结合律结合律 分配律分配律 还原律还原律 反演律反演律 吸收律（一）吸收律（一） 吸收率（二）吸收率（二） 吸收率（三）吸收率（三） 吸收率（四）吸收率（四） 00 A11A AA1AA0 AAAAAA 0 AA1 AA ABBAABBA CBACBA)()(CBACBA)()( ACABCBA)()(CABABCA AA BABABABA AA *) ( ABAAB AABA BABAA CAABBCC

4、AAB ABABA)( ABAA)( ABBAA)( )()()(CABACBCABA 6 二、逻辑代数的三个定理二、逻辑代数的三个定理(规则规则) 1、代入定理、代入定理 2、反演定理、反演定理 3、对偶定理、对偶定理 上次授课内容上次授课内容 回顾回顾 “”换成换成“+”，“+”换成换成“”，“0”换成换成“1”，“1”换换 成成“0”， 原变量换成反变量，反变量换成原变量。原变量换成反变量，反变量换成原变量。 “”换成换成“+”，“+”换成换成“”，“0”换成换成“1”，“1” 换成换成“0” 7 2.3 逻辑函数的公式化简法逻辑函数的公式化简法 一、逻辑函数的最简形式一、逻辑函数的最简

5、形式 例：例： 逻辑式越是简单，它所表示的逻辑关系越明显，逻辑式越是简单，它所表示的逻辑关系越明显， 同时也有利于用最少的电子器件实现这个逻辑函数。同时也有利于用最少的电子器件实现这个逻辑函数。 BAFBABBAF 21 , 一个逻辑函数可以有多种不同的逻辑表达式，如一个逻辑函数可以有多种不同的逻辑表达式，如 与与-或或表达式、表达式、或或-与与表达式、表达式、与非与非-与非与非表达式、表达式、 或非或非-或非或非表达式以及表达式以及与与-或或-非非表达式表达式 （与或式）（与或式） （或与式）（或与式） （与非与非式（与非与非式 ） （或非或非式（或非或非式 ） （与或非式（与或非式 ） D

6、CCA DCCA DCAC DCCA DCACL 8 Y=AB+(A+B)C = AB+ABC = AB+C = AB+C ABC 例：例：Y=AB+AC+BC 化为化为 =（最简与非最简与非-与非式与非式） （最简与或式最简与或式） 着重讨论着重讨论与或表达式与或表达式的化简，因为与或的化简，因为与或 表达式易于从真值表直接写出，且只需运表达式易于从真值表直接写出，且只需运 用一次用一次De. Morgan定律定律就可以从最简就可以从最简与与 或表达式或表达式变换为变换为与非与非-与非与非表达式，从而表达式，从而 可以用可以用与非门与非门电路来实现。电路来实现。 9 二输入四或门二输入四或门

7、74LS32一片一片 只需要：二输入四与非门只需要：二输入四与非门74LS00一片一片 按与按与-或式或式 AB+C 设计此逻辑电路，设计此逻辑电路， 需两块芯片需两块芯片 1 & Y A B C 按与非按与非-与非式与非式 设计此逻辑电路，设计此逻辑电路， ABC C & & A B 二输入四与门二输入四与门74LS10一片一片 10 判别与或表达式是否最简的条件是：判别与或表达式是否最简的条件是： 1、乘积项乘积项(与项与项)最少最少； (所用的门最少所用的门最少) 2、每个乘积项里的因子最少每个乘积项里的因子最少。 (门的输入门的输入 端数最少端数最少) 化简逻辑函数的目的：消去化简逻辑

8、函数的目的：消去多余的乘积项多余的乘积项 和每个和每个乘积项中多余的因子乘积项中多余的因子。 乘积项最少乘积项最少 且且 乘积项中变量因子最少。乘积项中变量因子最少。 11 例：以下例：以下4个个“与或与或”表达式是相等的，即它们表达式是相等的，即它们 表示同一个函数：表示同一个函数： CABACA CACBCA CACBACA CABACBCAF 试判断哪一个是最简试判断哪一个是最简“与或与或”表达式？表达式？ 解：解： 1) 对比可知式对比可知式1含含4个与项，其他个与项，其他3式都只含式都只含3个与项，个与项， 所以式所以式1肯定不是最简；肯定不是最简； 2) 式式3、4中各与项都含中各

9、与项都含2个变量，而式个变量，而式2中有一个与中有一个与 项含项含3个变量。结论：式个变量。结论：式3、4同为该函数的最简与或同为该函数的最简与或 表达式。表达式。 12 （1）并项法）并项法 利用公式利用公式 可将两项合并为一项可将两项合并为一项. 二、常用的公式化简方法二、常用的公式化简方法 ABAAB =+ 例例: F=ABC +ABC =AB(C +C) =AB 例：例：试用并项法化简下列逻辑函数试用并项法化简下列逻辑函数 Y1=ABCD+ABCD =A(BCD+BCD)=A Y2=AB+ACD+AB+ACD Y3=ABC+AC+BC Y4=BCD+BCD+BCD+BCD =A(B+C

10、D)+A(B+CD) =B+CD =ABC+(A+B)C =B(CD+CD)+B(CD+CD) =B(C D)+B(C D)=B =(AB)C+(AB)C=C 13 ABAAB ABABA)( 吸收律（一）吸收律（一） AABA ABAA)( 吸收律（二）吸收律（二） BABAA ABBAA)( 吸收律（三）吸收律（三） CAABBCCAAB )()()(CABACBCABA 吸收律（四）吸收律（四） 利用吸收律给利用吸收律给 函数式消肿函数式消肿 (2) 吸收法吸收法 14 (2) 吸收法吸收法 利用公式利用公式 A+AB=A 可将可将AB项消去。项消去。 例：例：试用吸收法化简下列逻辑函数

11、试用吸收法化简下列逻辑函数 BCDCBABCAAY DCABABDCABABY )( )( 2 1 Y=AB +ABCD(E+F)=AB (1+CDE+CDF) =AB Y1 = AB = A+BC AB=A+B Y2 = (A+BC)+(A+BC)(A+BC+D) = AD Y3 = (AB+C)ABD+AD = AD+ADB(AB+C) 15 ABAAB AABA BABAA CAABBCCAAB ABABA)( ABAA)( ABBAA)( )()()(CABACBCABA 吸收律（一）吸收律（一） 吸收律（二）吸收律（二） 吸收律（三）吸收律（三） 吸收律（四）吸收律（四） Y = A

12、C+ABCD+ABC+CD+ABD = AC+CD+ABD = AC+CD Y = AC+ABCD+ABC+CD+ABD = AC+CD+ABD AABA CAABBCCAAB Y=AB+AC+BC =AB+(A+B)C = AB+ABC =AB+C BABABABAA 16 A(A+B) Y = A(A+B)(A+C)(B+D)(A+C+E+F)(B+F)(D+E+F) (B+D)(B+F)(D+E+F) (A+C)(A+C+E+F) ABAA)( ABAA)( )()()(CABACBCABA Y = A(A+C)(B+D)(B+F) 解法解法2：将或与式：将或与式 与或式与或式 化简化简

13、 或与式或与式 对偶对偶对偶对偶公式公式 Y* = A+AB+AC+BD+ACEF+BF+DEF = (A+AB)+(AC+ACEF)+(BD+BF+DEF) AABAAABACAABBCCAAB = A+AC+BD+BF =AC(B+D)(B+F) BABAA = A+C+BD+BF Y=(Y*)* = AC(B+D)(B+F) 17 (3) 消项法消项法 利用公式利用公式 将将 BC或或BCD消去。消去。 例：例：用消项法化简下列逻辑函数用消项法化简下列逻辑函数 CAABBCDCAAB CAABBCCAAB 及 Y = AC+AB+B+C = AC+AB+BC BABA = CA+CB+A

14、B = AC+BC CAABBCCAAB 18 EDBCDBCA DBADBAABCCBAY EDCAEBADCBAY 2 1 Y1= (AB)CD+(AB)E+(CD)(E)A = ABCD+ABE CAABBCCAAB Y2 = (AB+AB)C+(AB+AB)D+BCD(A+E) A BA BCAABBCCAAB = (A B)C+ (A B)D DBADBAABCCBA BEEADCBA 19 (4) 消因子法消因子法 利用公式利用公式 消去。中的可将ABABABAA 例：例：试用消因子法化简下列逻辑函数试用消因子法化简下列逻辑函数 DCDAACY BABBAY 2 1 Y1= AB+

15、B+AB = A+B+AB BABAA = A+B Y2= AC+AD+CD+CD CAABBCCAAB = AC+AD+D AABA = AC+D AABA Y2= AC+(A+C)D = AC+ACD = AC+D BABA BABAA 20 (5) 配项法配项法 1、根据基本公式、根据基本公式A+A=A可添加重复项进行化简。可添加重复项进行化简。 例：例：试化简逻辑函数试化简逻辑函数 2、根据基本公式中的、根据基本公式中的 可以在函数式中的可以在函数式中的 某一项上乘以某一项上乘以 进行化简。进行化简。 ABCBCACBAY )(AA 1 AA Y=AB +AC+BC = AB+AC+

16、(A+A) BC =AB+ABC+AC+ABC =AB+AC AABA ABCBCACBAY BCBA ABCBCABCACBA AABCCCBA 21 CBCBBABAY Y = AB +AB(C+C)+BC+(A+A)BC = AB +ABC+ABC+BC+ABC+ABC = AB+BC+AC AABAAABA ABAAB = (AB +ABC)+(BC+ABC)+(ABC+ABC) Y = AB(C+C)+AB+(A+A)BC+BC = ABC+ABC+AB+ABC+ABC+BC AABAAABA ABAAB = AB+BC+AC = (AB+ABC)+(BC+ABC)+(ABC+ABC

17、) 22 AB+BC+AC 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 AB+BC+ACA B CAB+BC+AC AB+BC+AC=? 0 + 0 + 0 = 0 0 + 0 + 1 = 1 0 + 1 + 0 = 1 0 + 0 + 1 = 1 1 + 0 + 0 = 1 1 + 0 + 0 = 1 0 + 1 + 0 = 1 0 + 0 + 0 = 0 0 + 0 + 0 = 0 0 + 1 + 0 = 1 1 + 0 + 0 = 1 1 + 0 + 0 = 1 0 + 0 + 1 = 1 0 + 1 + 0 = 1 0 + 0 + 1

18、 = 1 0 + 0 + 0 = 0 AB+BC+AC AB+BC+AC= 注：公注：公 式化简式化简 的结果的结果 不一定不一定 唯一。唯一。 23 Y=AC+BC+BD+CD+A(B+C)+ABCD+ABDE Y=AC+BC+BD+CD+AB+AC+ABDE =AC+BC+BD+CD+ABC+ABDE =AC+BC+BD+CD+A+ABDE =BC+BD+CD+A =A+BC+BD AABA BABAA AABA CAABBCCAAB =A+BC+BD+AB+AC+ABDE =A+BC+BD AABA CAABBCCAAB 24 All the logic functions introd

19、uced in this chapter are commercially available in integrated circuit (IC) form. For example: Block diagram of 7400 IC chip 25 Some of the available IC gates IC NO.DescriptionPINs 7400Quad 2-input NAND gates14 7402Quad 2-input NOR gates14 7404Hex inverters14 7408Quad 2-input AND gates14 7410Triple 3

20、-input NAND gates14 7427Triple 3-input NOR gates14 7432Quad 2-input OR gates14 7486,74386Quad EX-OR gates14 74135Quad EX-OR/NOR gates14 26 用门电路实现逻辑函数时，需要使用与门、或门、非门、用门电路实现逻辑函数时，需要使用与门、或门、非门、 与或非门等器件，究竟将函数式变换成什么形式，要视所用与或非门等器件，究竟将函数式变换成什么形式，要视所用 门电路的功能而定。门电路的功能而定。 例例1：将逻辑函数将逻辑函数 化为与非与化为与非与 非形式。非形式。 例例2

21、：试用或非门画出函数试用或非门画出函数 的逻辑图。的逻辑图。 BDCBCABY 三、指定器件的逻辑函数化简（三、指定器件的逻辑函数化简（*） 注：注：将最简与或式直接变换为其他类型的逻辑式时，将最简与或式直接变换为其他类型的逻辑式时， 得到的结果不一定也是最简的。得到的结果不一定也是最简的。 CBAY 27 & & & & & & & A B C D Y1 CADCABACADCABAY 1 28 CACDACABA CACDACABACADCABAY 1 & & & & & & A B C D Y1 AC 最简最简 29 本本小节小节内容内容 小结小结 2.3 逻辑函数的公式化简法逻辑函数的

22、公式化简法 着重讨论着重讨论与或表达式与或表达式的化简的化简 一个逻辑函数可以有多种不同的逻辑表达式，如一个逻辑函数可以有多种不同的逻辑表达式，如 与与-或或表达式、表达式、或或-与与表达式、表达式、与非与非-与非与非表达式、表达式、或或 非非-或非或非表达式以及表达式以及与与-或或-非非表达式表达式 乘积项最少且乘积项中变量因子最少。乘积项最少且乘积项中变量因子最少。 常用的公式化简方法常用的公式化简方法 (1) 并项法并项法( 2) 吸收法吸收法( 3) 消项法消项法 (4) 消因子法消因子法( 5) 配项法配项法 注：公式化简的结果不一定唯一。注：公式化简的结果不一定唯一。 30 2.4

23、.1 逻辑函数的两种标准形式逻辑函数的两种标准形式 一、最小项和最大项定义一、最小项和最大项定义 2.4 逻辑函数的卡诺图化简法逻辑函数的卡诺图化简法 任何一个逻辑函数均可化成任何一个逻辑函数均可化成“最小项之和最小项之和”与与“最最 大项之积大项之积”这两种标准形式。这两种标准形式。 1、最小项、最小项 在在n变量逻辑函数中，变量逻辑函数中，若若m为包含为包含n个因子个因子的的乘积项乘积项， 而且这几个变量均以而且这几个变量均以 原变量原变量或或反变量反变量 的形式在的形式在m中中出出 现且仅出现一次现且仅出现一次，则称，则称m为该组变量的为该组变量的最小项最小项。 31 1、二变量的全部最

24、小项、二变量的全部最小项 A B最小项最小项 编号编号 0 0 0 1 1 0 1 1A B m0 A B A B A B m1 m2 m3 2、三变量的全部最小项、三变量的全部最小项 A B C最小项最小项编号编号 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 A B C A B C A B C A B C A B C A B C A B C A B C m1 m2 m3 m4 m5 m6 m7 3、四变量的全部最小项、四变量的全部最小项 编号为编号为 m0 m15（略） 个变量逻辑函数必有且仅有个变量逻辑函数必有且仅有2 2 个最小项

25、 个最小项 N个变量的最小项个变量的最小项 32 表表2-4-1 三变量最小项编号表三变量最小项编号表 33 约定：原变量用约定：原变量用“1”1”表示；表示； 反变量用反变量用“0”0”表示。表示。 注：用编号表示最小项时，变量数注：用编号表示最小项时，变量数 不同，相同编号所对应的最小项名不同，相同编号所对应的最小项名 也不同。也不同。 如，如，6： 对三变量逻辑函数为对三变量逻辑函数为 ABC； 对四变量逻辑函数为对四变量逻辑函数为 ABCD 34 最小项的性质最小项的性质: : 任意一个最小项，只有一组变量取值使其值为任意一个最小项，只有一组变量取值使其值为1 1。 任意两个不同的最小

26、项的乘积必为任意两个不同的最小项的乘积必为0 0。 全部最小项的和必为全部最小项的和必为1 1。 CBACB A 35 从最小项的定义出发可证明它还具有如下性质：从最小项的定义出发可证明它还具有如下性质： 某一最小项若不包含在某一最小项若不包含在 F 中，则必在中，则必在 中中； 具有具有相邻性相邻性的两个最小项的两个最小项之和可以合并成一项并之和可以合并成一项并 消去一对因子消去一对因子。 F 将它们合并，可消去因子: 只有一个因子不同的两个最小项是只有一个因子不同的两个最小项是 具有相邻性的最小项。具有相邻性的最小项。 和 具有逻辑相邻性。例如:ABCBCA BCBCAAABCBCA 最小

27、项的性质最小项的性质: : 36 任何一个逻辑函数都可以表示成唯一的任何一个逻辑函数都可以表示成唯一的 一组最小项之和，称为一组最小项之和，称为标准标准 与或与或 表达式表达式， 也称为也称为最小项表达式最小项表达式。 逻辑函数的最小项表达式逻辑函数的最小项表达式 对于不是最小项表达式的与或表达式，对于不是最小项表达式的与或表达式， 可利用公式可利用公式AA1 和和A(B+C)ABAC 来配项展开成最小项表达式。来配项展开成最小项表达式。 37 =(m0, m2, m3) = m 3+ m 2+ m 0 利用基本公式利用基本公式 可以把任何逻辑可以把任何逻辑 函数化为最小项之和函数化为最小项之

28、和 的标准形式。的标准形式。 1 AA 例例1： 可化为：BABY BAAABY BABAABY 3, 2, 0 2 m 逻辑逻辑 或或 运算运算 逻辑函数的最小项表达式逻辑函数的最小项表达式 38 例例2：Y=AB+C 可化为可化为 = (m1,m3,m5,m6,m7) = m3(1,3,5,6,7) + m 6 + m 7 + m 3 + m 5 + m 1= m 7 逻辑逻辑 或或 运算运算 利用基本公式利用基本公式 可以把任何逻辑可以把任何逻辑 函数化为最小项之和函数化为最小项之和 的标准形式。的标准形式。 1 AA CBBAACCABY CBACBABCAABCCABABC 逻辑函数

29、的最小项表达式逻辑函数的最小项表达式 39 CBAm 2 CBAm 1 如果列出了函数的真值表，则只要将函数值为如果列出了函数的真值表，则只要将函数值为1 1 的那些最小项相加，便是函数的最小项表达式。的那些最小项相加，便是函数的最小项表达式。 A B CY最小项 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 m0 m1 m2 m3 m4 m5 m6 m7 BCAm 3 CBAm 5 5, 3, 2, 1 3 5321 mmmmmY 真值表真值表最小项之和最小项之和 40 2、最大项、最大项 表表2-4-2 三变

30、量最大项编号表三变量最大项编号表 在在n变量函数中，若变量函数中，若M为为n个变量之个变量之和和，且这，且这n 个变量均以原变量或反变量的形式在个变量均以原变量或反变量的形式在M中出现一次，中出现一次， 则称则称M为该组变量的最大项。为该组变量的最大项。 41 从最大项定义出发可证明它具有如下重要性质：从最大项定义出发可证明它具有如下重要性质： 在输入变量的任何取值下在输入变量的任何取值下必有一个且仅有一个必有一个且仅有一个最大项最大项 的值为的值为0； 全体最大项之积为全体最大项之积为0； 某一最大项若不包含在某一最大项若不包含在F中，则必在中，则必在 中中； 任意两个最大项之和为任意两个最大项之和为1； (1) 只有一个变量不同的两个最大项的乘积等于只有一个变量不同的两个最大项的乘积等于各相同各相同 变量之和变量之和。 F CBCBACBA 最大项的性质：最大项的性质： 42 由上面给出的最大项和最小项编号表及示例可知，由上面给出的最大项和最小项编号表及示例可知， 最大项与最小项之间存在如下关系：最大项与最小项之间存在如下关系： iiii MmmM, 最大项与最小项之间的关系最大项与最小项之间的关系 Y=ABC+ABC+ABC+ABC= m3(0,2,3,6) 用最大项之积表示用最大项之积表示 Y=ABC+ABC+ABC+ABC =