3. 布尔代数与逻辑函数化简

数字电子技术安徽农业大学信息与计算机学院商伶俐第3章布尔代数与逻辑函数化简学习要点：•三种基本运算，基本公式、定理和规则。•逻辑函数及其表示方法。•逻辑函数的公式化简法与卡诺图化简法。•无关项及其在逻辑函数化简中的应用。逻辑函数及其相等概念（1）逻辑表达式：由逻辑变量和与、或、非3种运算符连接起来所构成的式子。在逻辑表达式中，等式右边的字母A、B、C、D等称为输入逻辑变量，等式左边的字母Y称为输出逻辑变量，字母上面没有非运算符的叫做原变量，有非运算符的叫做反变量。（2）逻辑函数：如果对应于输入逻辑变量A、B、C、…的每一组确定值，输出逻辑变量Y就有唯一确定的值，则称Y是A、B、C、…的逻辑函数。记为),,,(CBAfY注意：与普通代数不同的是，在逻辑代数中，不管是变量还是函数，其取值都只能是0或1，并且这里的0和1只表示两种不同的状态，没有数量的含义。（3）逻辑函数相等的概念：设有两个逻辑函数),,,(),,,(21CBAgYCBAfY它们的变量都是A、B、C、…，如果对应于变量A、B、C、…的任何一组变量取值，Y1和Y2的值都相同，则称Y1和Y2是相等的，记为Y1=Y2。若两个逻辑函数相等，则它们的真值表一定相同；反之，若两个函数的真值表完全相同，则这两个函数一定相等。因此，要证明两个逻辑函数是否相等，只要分别列出它们的真值表，看看它们的真值表是否相同即可。ABABABABA+B0001101100011110111001001110BAAB证明等式：3.1基本公式和规则3.1.1逻辑代数的公式和定理与运算：111001010000（1）常量之间的关系（2）基本公式0-1律：AAAA100011AA或运算：111101110000非运算：1001互补律：01AAAA等幂律：AAAAAA双重否定律：AA分别令A=0及A=1代入这些公式，即可证明它们的正确性。（3）基本定理交换律：ABBAABBA结合律：)()()()(CBACBACBACBA分配律：)()()(CABACBACABACBA反演律（摩根定律）：BABABABA.利用真值表很容易证明这些公式的正确性。如证明A·B=B·A：ABA.BB.A0001101100010001（1）用真值表证明，即检验等式两边函数的真值表是否一致。（2）用简单的公式证明略为复杂的公式。函数相等的证明方法：(A+B)(A+C)=AA+AB+AC+BC分配率A(B+C)=AB+AC=A+AB+AC+BC等幂率AA=A=A(1+B+C)+BC分配率A(B+C)=AB+AC=A+BC0-1率A+1=1证明分配率：A+BC=(A+B)(A+C)证明：（4）常用公式吸收律1：ABABAABABA)()(证明：))((BAAABAA吸收律2、3：BABAABABAAABAAABAA)()()(1BABA分配率A+BC=(A+B)(A+C)互补率A+A=10-1率A·1=1冗余律：CAABBCCAAB证明：BCCAABBCAABCCAABBCAACAAB)(互补率A+A=1分配率A(B+C)=AB+AC)1()1(BCACABCAAB0-1率A+1=1试证明：A+AB=A1)列真值表证明2)利用基本公式证明1、A+AB=A+B的推广A+ABC=A+BCAB+ABC=AB+CA+AB=A+BAB+ABC=AB+C=A+B+C2、AB=A+B的推广ABC=A+B+C同理：A+B+C=ABC二、推广举例AB00011011A+AB0+0·0=00+0·1=01+1·0=11+1·1=1A0011A+AB=A(1+B)=A·1=A常用公式的证明与推广一、证明举例例如，已知等式，用函数Y=AC代替等式中的A，根据代入法则，等式仍然成立，即有：3.1.2基本法则（1）代入法则：逻辑等式中的任何变量A，如果将所有出现A的位置都用另一个逻辑函数Z代替，则等式仍然成立。这个规则称为代入法则。BAABCBABACBAC)(作用：可以扩大基本公式的应用范围。（2）对偶法则：对于任何一个逻辑表达式F，如果将表达式中的所有“·”换成“＋”，“＋”换成“·”，“0”换成“1”，“1”换成“0”，而变量保持不变，并保持原先的逻辑优先级，则可得到的一个新的函数表达式G，G称为函数F的对偶式。例如：EDCBAF))((EDCBAGEDCBAFEDCBAG对偶规则：如果两个函数相等，则它们的对偶函数也相等。利用对偶规则,可以使要证明及要记忆的公式数目减少一半。例如：注意：在运用反演规则和对偶规则时，必须按照逻辑运算的优先顺序进行：先算括号，接着与运算，然后或运算，最后非运算，否则容易出错。ACABCBA)())((CABABCAABABAABABA)()(（3）反演法则：对于任何一个逻辑表达式Y，如果将表达式中的所有“·”换成“＋”，“＋”换成“·”，“0”换成“1”，“1”换成“0”，原变量换成反变量，反变量换成原变量，那么所得到的表达式就是函数Y的反函数Y（或称补函数）。这个规则称为反演规则。EDCBAY))((EDCBAYEDCBAYEDCBAY在应用反演规则求反函数时要注意以下两点：（1）保持运算的优先顺序不变，必要时加括号表明。（2）变换中，几个变量（一个以上）的长非号保持不变。意义：利用反演规则，可以非常方便地求得一个函数的反函数。例如：一个逻辑函数的表达式不是唯一的，可以有多种形式，并且能互相转换。一个逻辑函数的表达式可以有与或表达式、或与表达式、与非-与非表达式、或非-或非表达式、与或非表达式5种表示形式。例如：一种形式的函数表达式相应于一种逻辑电路。尽管一个逻辑函数表达式的各种表示形式不同，但逻辑功能是相同的。3.1.3逻辑函数不同形式的转换CAABL与——或表达式))((BACA或——与表达式CAAB与非——与非表达式BACA或非——或非表达式CAAB与——或——非表达式其中，与—或表达式是逻辑函数的最基本表达形式。1.与非-与非表达式CABACABACABAY①在与或表达式的基础上两次取反②用摩根定律去掉下面的非号2.与或非表达式CABAYACBACBACBACABACABAY))((①求出反函数的与或表达式②然后再取反一次即得与或非表达式ACBAY3、或与表达式ACBAY将与或非式用摩根定律展开，即得或与表达式。))((CABAY4、或非-或非表达式CABACABACABACABAY))(())((①求或与表达式②两次取反③用摩根定律展开一次，去掉下面的非号3.2逻辑函数的代数法化简3.2.1逻辑函数与逻辑图3.2.2逻辑函数化简的原则3.2.3与或逻辑函数的化简退出逻辑函数化简的意义：逻辑表达式越简单，实现它的电路越简单，电路工作越稳定可靠。3.2.1逻辑函数与逻辑图CBABCACABABCF1BCCAABF2CAABF3从实际问题中概括出来的逻辑函数，需要落实到实现该函数的逻辑图（即用逻辑门组成的电路图）。同一函数的逻辑表达式有多种形式，或繁或简。简单的形式对应简洁的电路，烦琐的形式对应复杂的电路。&ABC&ABC&ABC&ABC≥1F1CBABCACABABCF1&AB&AC&BC≥1F2BCCAABF2&AB&AC≥1F3CAABF3逻辑图与逻辑函数有直接关系。函数越简单，则实现电路的门数就越少，可以降低系统成本，提高电路的可靠性。3.2.2逻辑函数化简的原则（1）逻辑电路所用的门最少；（2）各个门的输入端最少；（3）逻辑电路所用的级数要少；（4）逻辑电路能可靠地工作。（1）与项最少，即表达式中“+”号最少。（2）每个与项中的变量数最少，即表达式中“·”号最少。最简“与或表达式”的标准一般逻辑函数化简的原则3.2.3与或逻辑函数的化简1、并项法逻辑函数的公式化简法就是运用基本公式和常用公式，再配合并项法、吸收法、配项法来化简逻辑函数。BCCBCBBCCBBCAACBBCAABCY)()(1ABCBCABCAABCCBAABCCABAABCY)()(2若两个乘积项中分别包含同一个因子的原变量和反变量，而其他因子都相同时，则这两项可以合并成一项，并消去互为反变量的因子。运用摩根定律运用分配律运用分配律利用公式，将两项合并为一项，并消去一个变量。ABAAB2、吸收法BAFEBCDABAY)(1BABCDBADABADBCDABADCDBAY)()(2如果乘积项是另外一个乘积项的因子，则这另外一个乘积项是多余的。运用摩根定律（１）利用公式Ａ＋ＡＢ＝Ａ，消去多余的项。（２）利用公式Ａ＋ＡＢ＝ＡＢ，消去多余的变量。CABCABABCBAABCBCAABY)(DCBADBACBADBACBADBACCBADCBDCACBAY)()(如果一个乘积项的反是另一个乘积项的因子，则这个因子是多余的。３、配项法（１）利用公式Ａ＝Ａ（Ｂ＋Ｂ），为某一项配上其所缺的变量，以便用其它方法进行化简。CACBBABBCAACBCBACBABCACBACBACBBACCBACBAACBBABACBCBBAY)()1()1()()(（２）利用公式Ａ＋Ａ＝Ａ，为某项配上其所能合并的项。BCACABBCAABCCBAABCCABABCBCACBACABABCY)()()(４、消去冗余项法利用冗余律ＡＢ＋ＡＣ＋ＢＣ＝ＡＢ＋ＡＣ，将冗余项ＢＣ消去。DCACBAADEDCACBADCADEACBAY)(1CBABFGDEACCBABY)(25、综合化简法DEGHEGBACEGBDCAABADEGHEGBACEGBDCAABDAADFDEGEGBACEGBDCAABDAADF例：化简函数表达式FDEGHEGBBDCAADEGHEGBBDCAEGBBDCA由上例可知，有些逻辑函数的化简结果不是唯一的。解法1：例化简逻辑函数：BACBCBBALCABACBCBBAL（增加多余项）CACABACBBA（消去一个多余项）CB解法2：（增加多余项）CACABACBCBBALCABACBBA（消去一个多余项）CBCACBBA（再消去一个多余项）BA代数化简法的优点：不受变量数目的限制。缺点：没有固定的步骤可循；需要熟练运用各种公式和定理；需要一定的技巧和经验；不易判定化简结果是否最简。CABACB（再消去一个多余项）BA3.3卡诺图化简3.3.1卡诺图化简的基本原理3.3.2最小项3.3.3卡诺图的结构3.3.4逻辑函数的卡诺图表示法3.3.5相邻最小项合并规律3.3.6与或逻辑化简3.3.7逻辑函数的公式化简法3.3.8无关项及其应用3.3.9输入只有原变量的函数化简3.3.10多输出函数的化简退出3.3.1卡诺图化简的基本原理代数化简法没有固定的步骤可循；需要熟练运用各种公式和定理；需要一定的技巧和经验；不易判定化简结果是否最简。吸收律：ABAAB两个逻辑相邻项，可合并成一项，其合并结果保留相同变量，消去取值不同的变量。任何两个相同变量的逻辑项，只有一个变量取值不同，（一项以原变量形式出现，另一项以反变量形式出现）