第一章开关理论(PPT)

1、1.4 布尔代数布尔代数1.4.1 布尔代数的基本定律布尔代数的基本定律 公理、定律与常用公式公理、定律与常用公式公理公理交换律交换律结合律结合律分配律分配律0-1律律重叠律重叠律互补律互补律非非律非非律摩根律摩根律0 0 = 00 1 =1 0 =0 1 1 = 10 + 0 = 00 + 1 =1 + 0 =1 1 + 1 = 1A B = B A A + B = B + A (A B ) C = A (B C) (A+ B )+ C = A+ (B+ C) 自等律自等律A ( B + C ) = A B+ A C A + B C =( A + B) (A+ C )A 0=0 A+ 1=1

2、A 1=A A+ 0=AA A=0 A+A=1A A=A A+ A=AA B= A+B A+ B=AB A= A吸收律吸收律消因律消因律包含律包含律合并律合并律A B+ A B =A (A+ B) (A+ B) =A A+A B=A A (A+B)=AA+ A B =A+B A (A+ B) =A B AB+ A C +BC= AB+ A C(A+B)( A+ C )(B+C)= (A+B)(A +C)函数证明函数证明 方法方法1利用真值表利用真值表例：用真值表证明摩根定律例：用真值表证明摩根定律A BA BAB A+ BA BA+B000110111110111010001000 A B=

3、A+B A+ B=ABBCCAABB)C(1AC)AB(1CAAB等式右边等式右边 由此可以看出：与或表达式中，两个乘积项分由此可以看出：与或表达式中，两个乘积项分别包含别包含同一因子同一因子的的原原变量和变量和反反变量，而两项的剩余变量，而两项的剩余因子包含在第三个乘积项中，则第三项是多余的。因子包含在第三个乘积项中，则第三项是多余的。CAABBCDECAAB公式可推广：公式可推广：例：证明包含律例：证明包含律CAABBCCAAB成立。成立。BC)AA(CAAB利用基本定律利用基本定律函数证明函数证明 方法方法2ABACABCABC1.4.2 布尔代数的三个基本规则布尔代数的三个基本规则 代

4、入规则代入规则：任何一个含有某变量的等式，如果任何一个含有某变量的等式，如果等等式式中所有出现此中所有出现此变量变量的位置均代之以的位置均代之以一个一个逻辑函数式逻辑函数式，则此等式依然成立，则此等式依然成立例：例： A B= A+BBCBC替代替代B B得得ABCBCACBA由此摩根定律能推广到由此摩根定律能推广到n n个变量：个变量：n 21n 21n 21n 21AAAAAAAAAA A A利用摩根定律（1 1）代入规则）代入规则（2 2）反演规则）反演规则 反演规则反演规则：对于任意一个逻辑函数式对于任意一个逻辑函数式F F，做如下处理：，做如下处理： 若把式中的运算符若把式中的运算符

5、“. .”换成换成“+ +”, “”, “+ +” ” 换成换成“. .”;”; 常量常量“0 0”换成换成“1 1”，“1 1”换成换成“0 0”； 原原变量换成变量换成反反变量，变量，反反变量换成变量换成原原变量变量那么得到的那么得到的新函数式新函数式称为原函数式称为原函数式F F的的反函数式反函数式。注意：注意： 保持原函数的运算次序保持原函数的运算次序-先与后或，必要时适当地加入括号。先与后或，必要时适当地加入括号。 不属于单个变量上的非号有两种处理方法：不属于单个变量上的非号有两种处理方法： 非号保留，而非号下面的函数式按反演规则变换；非号保留，而非号下面的函数式按反演规则变换； 将

6、非号去掉，而非号下的函数式保留不变。将非号去掉，而非号下的函数式保留不变。例：例：F(AF(A、B B、C)C)CBAB )C A(BA 其反函数为其反函数为)CBA(BCA)BA(F或或)CBA(B)CA()BA(F 对偶式对偶式：对于任意一个逻辑函数，做如下处理：对于任意一个逻辑函数，做如下处理：1 1）若把式中的运算符）若把式中的运算符“. .”换成换成“+ +”，“+ +”换成换成“. .”；2 2）常量）常量“0 0”换成换成“1 1”，“1 1”换成换成“0 0”。得到新函数式为原函数式得到新函数式为原函数式F F的对偶式的对偶式FF，也称对偶函数。，也称对偶函数。 对偶规则：对偶

7、规则：如果两个函数式相等，则它们对应的对偶式也相如果两个函数式相等，则它们对应的对偶式也相等。即等。即 若若 F F1 1 = F = F2 2 则则F F1 1= F= F2 2。使公式的。使公式的数目增加一倍。数目增加一倍。 求对偶式时求对偶式时运算顺序不变运算顺序不变，且它只，且它只变变换换运算符运算符和常量和常量，其，其变量变量是是不变不变的。的。注意：注意： 函数式中有函数式中有“ ”和和“”运算符，求反函数运算符，求反函数及对偶函数时，要将运算符及对偶函数时，要将运算符“ ”换成换成“”， “”换成换成“ ”。 例：例：B1CAABF 其对偶式：其对偶式：)B 0() CA ()B

8、A(F（3 3）对偶规则）对偶规则 五种常用表达式五种常用表达式F(AF(A、B B、C)C)CAAB“与与或或”式式)BA)(CA(“或或与与”式式CAAB“与非与非与非与非”式式 BACA“或非或非或非或非”式式BACA“与与或或非非”式式基本形式基本形式 表达式形式转换表达式形式转换CA AB F CAABCAAB利用非非律利用非非律利用摩根律利用摩根律1.4.3 利用布尔代数化简逻辑函数利用布尔代数化简逻辑函数补充：逻辑函数的五种常用表达式及其转换补充：逻辑函数的五种常用表达式及其转换函数的简化依据函数的简化依据 逻辑电路所用逻辑门的数量少；逻辑电路所用逻辑门的数量少； 每个逻辑门的输

9、入端个数少；每个逻辑门的输入端个数少； 逻辑电路构成级数少；逻辑电路构成级数少； 逻辑电路保证能可靠地工作。逻辑电路保证能可靠地工作。降低成本降低成本提高电路的工作提高电路的工作速度和可靠性速度和可靠性(1) 要求乘积项的数目最少要求乘积项的数目最少;(2) 满足满足(1)的条件下，每个乘积项中变量个数也最少。的条件下，每个乘积项中变量个数也最少。 总之总之：最简式的标准最简式的标准 首先是式中首先是式中乘积项最少；乘积项最少； 乘积项中含的变量少。乘积项中含的变量少。 与或表达式的化简与或表达式的化简主要化简方法主要化简方法方法：方法： 并项：并项： 利用利用ABAAB将两项并为一项，将两项

10、并为一项，且消去一个变量且消去一个变量B 吸收：吸收： 利用利用A + AB = A消去多余的项消去多余的项AB 配项：利用配项：利用CAABBCCAAB和互补律、和互补律、重叠律先增添项，再消去多余项重叠律先增添项，再消去多余项BC 消去：利用消去：利用BABAA消去多余因子消去多余因子 ACBDBDAACF例：例：简化函数：简化函数：解：解：CBDBDAACF利用摩根律利用摩根律)BA(DCBACABDCBAC配项加配项加ABABABDABCBAC消因律消因律DABCBAC消项消项ABABDCBAC 或与表达式的简化或与表达式的简化F（或与式）（或与式）求对偶式求对偶式 F （与或式）（与

11、或式）简化简化 F （最简与或式）（最简与或式）求对偶式求对偶式 F（最简最简或与式）或与式）例：例：试简化函数试简化函数解：解：)()(CBCABBCACACBABCACABFCACBABCACABF)(BCACABACACABAC 结合律结合律消因律消因律分配律分配律互补律互补律结合、互补律结合、互补律本小节主要讲解布尔代数的定律与规则，本小节主要讲解布尔代数的定律与规则，并利用这些定律和规则化简逻辑函数。并利用这些定律和规则化简逻辑函数。 本小节要求熟记布尔代数的定律与规则，本小节要求熟记布尔代数的定律与规则，掌握利用这些定律和规则化简逻辑函数。掌握利用这些定律和规则化简逻辑函数。 小结

12、小结 作业作业P3031T6、T7 、T81.5 卡诺图卡诺图1.5.1 逻辑函数的最小项表达式逻辑函数的最小项表达式最小项：最小项：n n个变量有个变量有2 2n n个最小项，记作个最小项，记作m mi i。例如：例如：3 3个变量有个变量有2 23 3（8 8）个最小项。个最小项。CBACBAm m0 0m m1 100000101CBABCACBACBACABABC m m2 2m m3 3m m4 4m m5 5m m6 6m m7 7010011100101110111234567n n个变量的逻辑函数中，包括个变量的逻辑函数中，包括全部全部n n个变量个变量的的乘积项乘积项（每个变

13、量必须而且只能以原变（每个变量必须而且只能以原变量或反变量的形式出现一次）。量或反变量的形式出现一次）。（1） 最小项的概念最小项的概念最小项最小项二进制数二进制数十进制数十进制数编号编号最小项编号最小项编号i是指各输入是指各输入变量取值看成二进制数变量取值看成二进制数对应的十进制数对应的十进制数0 0 1A B CA B C0 0 0m m0 0CBAm m1 1m m2 2m m3 3m m4 4m m5 5m m6 6m m7 7CBACBABCACBACBACABABC 1 -n20iimF1000000001000000110 1 00 1 11 0 01 0 11 1 01 1 1

14、000000000000100000010000001000000100000010000001111111三变量的最小项三变量的最小项 （2）最小项）最小项 的性质：的性质： 任意任意两个不同两个不同最小项的最小项的乘积乘积为为0， 即即 mi mj=0 (ij)。 全部全部最小项之最小项之和和为为1，即，即120ii1mn 任意一组变量取值，任意一组变量取值，只有一个只有一个最小最小 项项 的值为的值为1，其它最小项的值均为，其它最小项的值均为0。 标准积之和标准积之和( 最小项）表达式最小项）表达式式中的每一个乘式中的每一个乘积项均为最小项积项均为最小项F(AF(A、B B、C C、D)

15、D)D C BADCBADC B AD C B A8510mmmm)8 5 1 0(m、例：例：求函数求函数F(AF(A、B B、C C、D)D)CB ABA的标准积之的标准积之和表达式和表达式解：解：F(AF(A、B B、C C、D)D)CB ABACB ABACB A)CC(BACB ACBABCA123mmm)3 2 1 (m、利用反演律利用反演律利用互补律，补利用互补律，补上所缺变量上所缺变量C A B C A B C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1mi01234567FMi0123456700010111例：例：已知函数的真值表，写出该

16、函数的标准积之和表达式已知函数的真值表，写出该函数的标准积之和表达式 从真值表找出从真值表找出F为为1的对应最小项的对应最小项解解: 然后将这些项逻辑加然后将这些项逻辑加F(AF(A、B B、C)C)ABCCABCBABCA7653mmmm)7 6 5 3(m、（3）逻辑函数的标准形式逻辑函数的标准形式1.5.2 卡诺图的结构特点卡诺图的结构特点（一）（一） 1 1、2 2、3 3变量卡诺图变量卡诺图排列原则排列原则：任何两个上下或左右相邻的小方格对应的两个任何两个上下或左右相邻的小方格对应的两个 最小项中，有且仅有一个变量发生变化。最小项中，有且仅有一个变量发生变化。 （二）（二） 4 4变

17、量卡诺图变量卡诺图卡卡诺诺图图的的特特点点1.5.3 用卡诺图化简函数用卡诺图化简函数 k k图为方形图。图为方形图。n n个变量的函数个变量的函数-k-k图有图有2 2n n个小方个小方格，分别对应格，分别对应2 2n n个最小项个最小项； k k图中行、列两组变量取值按循环码规律排列，图中行、列两组变量取值按循环码规律排列，使变量各最小项之间具有使变量各最小项之间具有逻辑相邻性逻辑相邻性。上下左右几何相邻的方格上下左右几何相邻的方格内，只有一个因子不同内，只有一个因子不同 有三种几何相邻：有三种几何相邻：邻接、相对（行列两端）和对邻接、相对（行列两端）和对称称（图中以（图中以0 0、1 1

18、分割线为对称轴）方格均属相邻分割线为对称轴）方格均属相邻0001111000011110 m0 m1 m2 m3 m4 m5 m6 m7 m12 m13 m14 m15 m8 m9 m10 m11ABCD四四变变量量卡卡诺诺图图两个相邻格圈在一起，两个相邻格圈在一起，结果消去一个变量结果消去一个变量ABD ADA1四个相邻格圈在一起，四个相邻格圈在一起，结果消去两个变量结果消去两个变量八个相邻格圈在一起，八个相邻格圈在一起，结果消去三个变量结果消去三个变量十六个相邻格圈在十六个相邻格圈在一起，结果一起，结果 mi=1卡诺图化简函数规则：卡诺图化简函数规则： 几何相邻的几何相邻的2i（i = 1

19、、2、3n）个小格）个小格可合可合并在一起构成正方形或矩形圈，消去并在一起构成正方形或矩形圈，消去i个变量，而个变量，而用含用含（n - i）个变量的积项标注该圈个变量的积项标注该圈。例：图中给出输入变量例：图中给出输入变量A、B、C的真值表，填写函数的的真值表，填写函数的 卡诺图。卡诺图。ABCF000 0 0 1 01001110010111011100111000ABC0100011110 1 110 0 0 0 0 010111001110(1) 根据真值表填卡诺图根据真值表填卡诺图例：例：将将F(AF(A、B B、C C、D)D)ACBCADCBABDCA的卡诺图填写出来。的卡诺图填

20、写出来。解：解：0100011110001110CDABAB111111B CD11 ACD ABC11AC1111m14,m15两次填两次填10000(2) 根据函数表达式填卡诺图根据函数表达式填卡诺图(3) 用卡诺图化简逻辑函数的步骤用卡诺图化简逻辑函数的步骤 与或表达式的简化与或表达式的简化步步骤骤(1) 把逻辑函数变换为最小项表达式；把逻辑函数变换为最小项表达式；(2) 用卡诺图表示逻辑函数：最小项表达式中用卡诺图表示逻辑函数：最小项表达式中 各最小项对应的各小方格填入各最小项对应的各小方格填入“1”，其余的，其余的 填填 “0”或不填；或不填；(3) 合并相邻合并相邻“1”方格；方格

21、；(4) 将每个包围圈所表示的乘积项逻辑加，可将每个包围圈所表示的乘积项逻辑加，可 得与或表达式。得与或表达式。(4) 画圈的要领画圈的要领(1) (1) 包围圈越大越好；包围圈越大越好；(2) (2) 包围圈个数越少越好；包围圈个数越少越好；(3) (3) 同一个同一个“1”1”方格可以被圈多次；方格可以被圈多次；(4) (4) 每个包围圈要有新成分；每个包围圈要有新成分；(5) (5) 画包围圈时，先圈大，后圈小；画包围圈时，先圈大，后圈小；(6) (6) 不要遗漏任何不要遗漏任何“1”1”方格。方格。总原则：总原则：在覆盖所有最小项的前提下，卡诺圈在覆盖所有最小项的前提下，卡诺圈 的个数

22、达到最少，每个卡诺圈最大。的个数达到最少，每个卡诺圈最大。例例1：直接给出函数的真值表，求函数的最简与或式。：直接给出函数的真值表，求函数的最简与或式。见例见例1例例2：直接给出函数的：直接给出函数的复杂的运算式复杂的运算式。见例见例2(5) 卡诺图化简函数举例卡诺图化简函数举例 含有含有无关项无关项的函数的化简的函数的化简 填函数的卡诺图时只在无关项对应的格内填函数的卡诺图时只在无关项对应的格内填任意符号填任意符号“”、“d或或“”。无关项无关项对于变量的对于变量的某些取值组合某些取值组合，所对应的，所对应的函数值函数值是不确定的是不确定的。通常。通常约束项和任意项约束项和任意项在逻辑函在逻辑函数中统称为数中统称为无关项无关项。 化简时可根据需要视为化简时可根据需要视为“1”也可视为也可视为“0”，