逻辑代数和逻辑函数化简.doc

.第2章 逻辑代数和逻辑函数化简基本概念：逻辑代数是有美国数学家George Boole 在十九世纪提出,因此也称布尔代数,是分析和设计数字逻辑电路的数学工具。也叫开关代数，是研究只用0和1构成的数字系统的数学。2.1 基本逻辑运算和复合逻辑运算基本逻辑运算：“与”、“或”、“非”。复合逻辑运算：“与非”、“或非”、“与或非”、“异ABF220V或”、“同或”等。2.1.1 基本逻辑运算1.“与”运算逻辑含义：当决定事件成立的所有条件全部具备时，事件才会发生。运算电路：开关A、B都闭合，灯F才亮。表示逻辑功能的方法：真值表开关A、B的状态代表输入：“0”表示断开；“1”表示闭合。AB灯F的状态代表输出：“0”表示亮；“1”表示灭。F000010100111表达式：F=AB逻辑符号：&ABF国家标准ABF以前的符号ABF欧美符号功能说明：有0出0，全1出1。在大规模集成电路可编程逻辑器件中的表示符号：&FFFABABAB通过“”接入到此线上的输入信号都是该与门的一个输入端。推广：当有n个变量时：F=A1A2 A3An“与”运算的几个等式：00=0，01=0，11=1A0=0（0-1律），A1=A（自等律），AA=A（同一律），AAA=A（同一律）。ABF220V2.“或”运算逻辑含义：在决定事件成立的所有条件中，只要具备一个，事件就会发生。运算电路：开关A、B只要闭合一个，灯F就亮。表示逻辑功能的方法：逻辑功能：有1出1，全0出0。真值表：（略）表达式：F=A+B逻辑符号：1ABF国家标准ABF以前的符号ABF欧美符号+推广：当有n个变量时：F=A1+A2+ A3+An“或”运算的几个等式：0+0=0，0+1=1，1+1=1A+0=A（自等律）A+1=1（0-1律），A+A=A（同一律）。上次课小结：与、或的功能、表达式等，几个等式。3“非”运算AF220VR逻辑含义：当决定事件的条件具备时，事件不发生；当条件不具备时，事件反而发生了。运算电路：开关A闭合，灯F不亮。表示逻辑功能的方法：逻辑功能：入0出1，入1出0。真值表：（略）表达式：F=逻辑符号：欧美符号AF以前的符号AF国家标准1AF “非”运算的几个等式：=A（还原律）；A+=1、A=0（互补律）。2.1.2 复合逻辑运算1“与非”运算“与”和“非”的组合。有专门实现这种运算的实际器件（如TTL与非门等）。逻辑符号：&ABF国家标准ABF以前的符号ABF欧美符号表达式：F=；真值表：（略），逻辑功能为：有0出1，全1出0。2“或非”运算“或”和“非”的组合。也有专门实现这种运算的实际器件（如TTL、CMOS与非门等）。逻辑符号：1ABF国家标准ABF以前的符号ABF欧美符号+表达式：F=；真值表：（略），逻辑功能为：有1出0，全0出1。3“与或非”运算逻辑符号：国家标准1ABFCD&以前的符号+ABFCD欧美符号FABCD表达式：F=；真值表：（略）。4“异或”运算逻辑功能：两变量状态相异出1，相同出0。真值表：（略）。表达式：F=AB=B + A逻辑符号：=1ABF国家标准ABF以前的符号ABF欧美符号“异或”运算的几个等式：A 0 = A；A 1 =；A =1；A A= 05“同或”运算逻辑功能：两变量状态相异出0，相同出1。逻辑符号：=1ABF国家标准ABF以前的符号ABF欧美符号与“异或”运算正好相反，也称“异或非”运算。“异或”运算的几个等式（略）。2.2 逻辑代数的基本定律及规则2.2.1 逻辑代数的基本定律或者称为基本公式：0-1律：1A=A； 0+A=A。0A=0； 1+A=1。交换律：AB=BA； A+B=B+A。结合律：A（BC）=（AB）C；A+（B+C）=（A+B）+C。分配律：A（B+C）=AB+AC；A+BC=（A+B）（A+C）。互补律：A=0；A+=1。重叠律：AA=A；A+A=A。还原律：=A；反演律：=；=吸收律1：A+AB= A；A（A+B）= A。吸收律2：A+B= A+B；A（+B）= AB。吸收律3：AB+ A= A；（A+B）（A+）= A。冗余定理：AB+C+BC= AB+C；（A+B）（+C）（B+C）=（A+B）（+C）。证明：左边=AB+C+BC（A+）= AB+C+ABC+BC= AB（1+C）+C（1+B）= AB+C=右边 （证毕）冗余定理指出：当某变量以互补形式出现在两个与项中时，这两个与项的其余因子组成的第三项为多余项。推论：AB+C+BC f (a，b，c，)= AB+C 多余项2.2.2 逻辑代数的基本规则1代入规则将逻辑等式中的某一变量都代之以另一个逻辑函数，此等式仍成立。例：=。用BC代替等式中的B得=反复运用代入规则可得：=。扩大了等式的应用范围。2对偶规则如果将任一逻辑函数式F=f (A，B，C，)中所有的所得到的新函数F就是F的对偶式。此即对偶规则。运用时注意：原运算顺序不变（可运用扩号保证）。原式的长短非号保持不变！换成 + 换成 0 换成 11 换成 0例：求F=的对偶式。解：=F与互为对偶，=F。还要注意到：对偶关系不是相等的关系，即F。运用对偶规则可以使要记忆的公式减少一半。观察P27中的基本公式可以发现，只要记住左半部分，运用对偶规则就能得到右半部分。3反演规则 如果将任一逻辑函数式F=f (A，B，C，)中所有的换成 +所得到的新函数就是F的反函数。此即反演规则。运用时注意：原运算顺序不变（可运用扩号保证）。原式的公共非号保持不变。+ 换成 0 换成 11 换成 0原变量 换成 反变量反变量 换成 原变量例：求F=的反函数。解：=公共非号也可以改变，但在消去公共非号的同时，公共非号下面的子函数保持原状。如上例：=CD，与=C+D相等。（应用摩根定律）从原函数求反函数的过程叫做反演。摩根定律是进行反演重要工具。例如，将F=两边同时取反并反复运用摩根定律的：=当函数较简单时，可以用摩根定律求反，当函数比较复杂时，用反演规则求反比较方便。2.3 逻辑函数的表示方法及其转换除用文字描述以外，还有四种描述形式：真值表、表达式、卡诺图、逻辑图2.3.1 逻辑表达式完备函数的概念：我们已经学习过三种最基本的逻辑运算：逻辑与；逻辑或；逻辑非，用他们，可以解决所有的逻辑运算问题，因此可以称之为一个“完备逻辑集”。一.逻辑表达式的类型每种函数对应一种逻辑电路。同一个函数逻辑有多种表达形式：F= =AC+BC+AA+=（冗余定理、互补律）= （还原律、摩根定律）= （还原律、摩根定律）= （反演规则再求反）= = 用互补律配项二逻辑函数的标准形式1最小项（1）定义：对于N个变量，如果P是一个含有N个因子的乘积项，而且在P中每个变量都以原变量或反变量的形式作为一个因子出现，且仅出现一次，则称P是N个变量的一个最小项。简单地说：最小项就是包含全部变量的与项。例如：、都是三个变量的最小项。而、AB都是两个变量的最小项，而对于三个或者三个以上的变量来说，它们就是一般乘积项。所以：提及最小项一定要说明变量的数目。N个变量共有2n 个最小项。(2) 性质取三个变量的全体最小项观察：、对应的取值组合： 000 001 010 011 100 101 110 111每个最小项都对应了一组变量取值。对任一最小项，只有与之对应的那一组变量取值才是它的值为 “1”；任意两个不同最小项之积恒为0；全体最小项的逻辑和恒为1； 两个逻辑相邻的最小项可以合并为一项，从而消去一个因子。(3) 最小项标准表达式任何一个逻辑函数都能表示成最小项之和的形式，而且这种表示形式是唯一的，这就是标准与或式，也叫最小项标准表达式。由一般式标准与或式的变换步骤：用公式把一般式化为一般与或式；若式中的某一项缺少某个变量，就用该变量的原变量和反变量之和去乘这一项，然后拆成两项，直到补齐所缺变量为止。冗余例：写出 F= 的标准与或式。（F=）解：化为一般与或式 F=补齐所缺变量 F=也可以由F=列出真值表，直接写出最小项标准表达式。最小项标准表达式的另一种表示形式：、对应的取值组合： 000 001 010 011 100 101 110 111二进制换十进制 0 1 2 3 4 5 6 7记为 m0 m1 m2 m3 m4 m5 m6 m7F=还可以表示成：F= m0+ m4+ m3+ m2 或者写成 F=m（0，2，3，4）根据逻辑函数的特点，这种表示方法便于转换成卡诺图；便于写出反函数。比如F=m（0，2，3，4）的反函数=m（1，5，6，7）。2.3.2 真值表真值表：输入变量各种可能的取值组合及其对应的函数值，排列在一起而组成的表格。例如：奥运会举重比赛，有三个裁判A、B、C（多数表决。）ABCF00000010010001111000101111011111分析：输入变量：A、B、C，个人认为通过，取值为“1”，否则，为“0”输出函数：F，结果通过，取值为“1”，否则，为“0”。列出所有可能的情况，得到真值表。F =优点：直观明了，便于将实际逻辑问题抽象成数学表达式缺点：难以用公式和定理进行运算和变换；变量较多时，列函数真值表较繁琐。2.3.3 卡诺图优点：便于求出逻辑函数的最简与或表达式。缺点：只适于表示和化简变量个数比较少的逻辑函数，也不便于进行运算和变换。10111001ABC01A00011110CBF2.3.4 逻辑图逻辑图：用基本逻辑单元和逻辑部件的逻辑符号构成的变量流程图。优点：最接近实际电路。缺点：不能进行运算和变换，所表示的逻辑关系不直观。2.3.5 波形图输入变量和对应的输出变量随时间变化的波形，已知A、B的波形，画Y=AB的波形。优点：形象直观地表示了变量取值与函数值在时间上的对应关系。缺点：难以用公式和定理进行运算和变换，当变量个数增多时，画图较麻烦。2.3.6 逻辑函数表示方法间的相互转换逻辑函数有四种表示方法，它们之间的相互转换，是分析、设计逻辑电路的关键。1.真值表函数表达式曾写过多数表决问题(上例)的表达式，归纳如下：把表中函数值为“1”的变量组合挑出来；F=1的组合有四种（顺序ABC）：011 101 110 111把取值为“1”的变量写成原变量，为“0”的写成反变量，得乘积项；对应的乘积项： 把所得的乘积项加起来，即得标准的与或式。F=+再看一例：奇偶性判别问题的真值表。2.表达式真值表F1 、F2的真值表ABCF1F20000000111010110111110011101111101111100把逻辑变量各种可能的取值组合分别代入式中计算，求出相应的函数值并填入表中。例：已知F1=，F2=，说明F1、F2的关系。三个变量，将八种组合代入计算，得真值表。由真值表可知：F1= F2（F1的三项可以写成：= =对F2可以做同样的处理。）3.逻辑图表达式每一张逻辑图的输入输出之间都有一定的逻辑关系，这一逻辑关系可以用一个逻辑函数表示。所以，逻辑图也是逻辑函数的一种表示方法。逻辑图与实际电路接近，这是它的突出优点。每个门电路（或逻辑部件）都有一个反映输入输出关系的表达式。所以，可根据给出的逻辑图，从输入到输出逐级写出输出端的表达式。例：写出右图所示逻辑图的表达式。解1： F1=，F3=，F2=4表达式逻辑图ABF函数表达式由“与”“或”“非”等运算组成。所以只要用“与门”“或门”“非门”等门电路来实现这些运算，就能得到与逻辑表达式对应的逻辑图。例：画出与F=对应的逻辑图。2.4 逻辑函数的化简法2.4.1 关于逻辑函数化简的几个问题1化简的意义：对于一个逻辑函数来说，如果表达式比较简单，那么实现这个逻辑函数所需要的元件（门电路）就比较少。所以化简的意义是：节约器材、降低成本、提高可靠性。2什么是最简与或式理论分析原则：在与或表达式中，若与项个数最少，且每个与项中变量的个数也最少，则该式就是最简与或式。表达式最简，不一定就节约了器材，还有个利用率的问题（经济问题）、可靠性问题、工作速度问题、消除竞争冒险问题等等。2.4.2 逻辑函数的代数化简法用基本公式和常用公式进行推演的化简方法叫做公式化简法。能否快速准确地得到最简结果，与对公式的掌握的熟练程度及化简经验密切相关（熟能生巧，实践出真知）。大致可归纳为以下几种方法：1并项法：利用A+A=1，将两项合并为一项，消去一个变量。(或者利用全体最小项之和恒为“1”的概念，把2n 项合并为一项，消去n个变量。)例1：=C 两个变量的全体最小项或者：=C或者：=ABC+ABC+ABC+ ABC =AC(B+B)+AC(B+B)= AC+AC=C根据吸收律A+AB=A+B得：(AB+A+B)C=(B+A+B)C=(1+A)C= C 互补律 0-1律例2：=反演律=2吸收法：利用A+AB=A吸收多余项。例3：F=AC+ABCD(E+F) = AC+ ACBD(E+F)= AC例4：F= =()+ =3消去法：利用A+AB=A+B消去多余的因子。例5：F= AB+C4消项法：利用AB+AC+BC =AB+AC消去多余的项。消项法与吸收法类似，都是消去一个多余的项。只是前者运用冗余定理，后者利用吸收律()。例5：F= A+AC+D+ADE = A+AC+D 5配项法：利用A=AB+AB将一项变为两项，或者利用冗余定理增加冗余项，然后（配项目的）寻找新的组合关系进行化简。例6： =+AC （冗余定理） =+ AC+ =+或者： （前2项变为4项）= =在实际化简时，上述方法要综合利用。公式法化简的优点是没有任何局限性；缺点是化简结果是否最简不易看出。互补律例7：F= 吸收律() 反演律 吸收法 =AB+ = ABC公式法化简时采用与或式比较方便，基本公式比较容易记忆和套用（习惯问题）。当遇到或与式的时候，可以利用对偶规则，将或与式转换为与或式。化为最简式后，再利用对偶规则换回或与式（原函数的最简式）。例如上例：F= = +CD =A+B+C+ CD =A+B+C =ABC2.4.3 逻辑函数的卡诺图化简法真值表是描述逻辑功能的重要工具，但作为运算工具就不太方便。卡诺图是美国工程师卡诺（Karnaugh）和维奇(Veiitch)首先提出的一种作图方法，卡诺图既保留了真值表的特性，又便于作逻辑运算。也称为真值图。一、逻辑函数的卡诺图表示法1什么是卡诺图把逻辑函数的最小项填入特定的方格内排列起来，让他们不仅几何位置相邻，而且逻辑上也相邻，这样得到的阵列图叫做卡诺图。2卡诺图的构成变量卡诺图一般画成正方形或长方形，对于n个变量，分割出2n个小方格；变量的取值顺序按格雷码(循环码)排列，并作为每个小方格的编号。设B3B2B1B0是二进制码，G3G2G1G0是格雷码，则Gi=BiBi+1 。A BA BA BA BABBA0101m0m1m3m2m4m5m7m6ABC01A00011110CB两个变量的最小项。用编号表示最小项。当B3B2B1B0=0000，G3G2G1G0=0000，当B3B2B1B0=0001，G3G2G1G0=0001下面依次画出25变量的卡诺图。0132457612131514891110CDAB0001111000011110ABDC013267548911101415131224252726303129281617191822232120CDEAB00011110A000001011010110111101100BCDEEF的真值表ABCF000000110101011010011010110011113从真值表卡诺图卡诺图是真值表的阵列图形式，仅排列方式不同，故他们的对应关系十分明显。01011010ABC01A00011110CBF4表达式卡诺图求函数的标准与或式，并编号；画卡诺图；在图中找到与函数所对应的最小项方格并填“1”，其余的添“0”。例：将F=填入卡诺图。10011001ABC01A00011110CBF解：F= =m(0，2，4，6)“额外收获”：通过卡诺图方便地求反函数。如本例F的反函数为=m(1，3，5，7)方便地求最大项表达式。得到反函数后，两边求反得：= F=用摩根定律得：F=再用一次摩根定律可得原函数的最大项表达式：F=1111011101111111CDAB0001111000011110ABDCF实用中，当给出的表达式是一般与或式时，通常采用“观察法”直接填入卡诺图。例：将F=填入卡诺图。C统辖的方格为右边两列，填“1”；BD共辖的方格为中间两行和中间两列的交汇处，填“1”；剩余的方格填“0”。二、利用卡诺图化简逻辑函数1卡诺图化简函数的依据逻辑相邻的2n个最小项相加，能消去n个变量。逻辑相邻：相同变量的两个最小项只有一个因子不同，则他们在逻辑上相邻。例如：ABC+AB=AB CD+CD+ABCD+CD=CD 0D 1C D 3C 2B 4BD 5B C D 7B C 6A B 12AB D 13A B C D 15A B C 14A 8AD 9AC D 11AC 10C DA BABCD在卡诺图中合并最小项的规律（以四个变量为例）相邻的两个最小项可以合并为一项，消去一个变量（挨着，一行两端，一列两端）。相邻的四个最小项可以合并为一项，消去两个变量（组成方块，一行，一列，两行末端，两列末端，四角）。相邻的八个最小项合并为一项，消去三个变量（两行，两列，两边的两行或者两列）。例：m(0,8)= （一列的两端） m(0,2,8,10)= （四角） m(4,6,12,14)= B（两行末端） m(4,6,12,14) =B（一行）m(1,3,5,7,9,11,13,15) =D（两列）m(0,1,2,3,8,9,10,11) =（两边的两行）2化简步骤画函数 F 的卡诺图； 把可以合并的最小项的分别圈出，每个包围圈中的最小项可合并为一项；把各个合并项加起来即可。例1：把F(A,B,C,D)=m(0,6,8,9,10,11,12,13)化为最简与或式。1000000111001111CDAB0001111000011110ABDCF解：把四个包围圈对应的乘积项加起来F(A,B,C,D)=也可以圈“0”，但得出的是：=3化简注意事项所有为1的最小项必须在某一个包围圈中，且圈中1的个数必须是2n个；包围圈中1的个数越多越好（变量少），而包围圈的个数越少越好（乘积项少）；卡诺图中的1可以重复使用（重叠律），但每个包围圈中应至少含一个新1！否则，该乘积项就是多余的；圈1得原函数，圈0得反函数。0110001101100011CDAB0001111000011110ABDCF1101011100110000CDAB0001111000011110ABDCF蓝色包围圈是正确的圈法，化简结果含三个与项。而红色包围圈是错误的，结果含四个与项。红色包围圈中的四个1都被圈过，所以与红色包围圈对应的CD项是多余的。如果给出的是或与式，可以先用对偶规则化为与或式，再填入卡诺图化简。为获得原函数，对化简结果运用一次对偶规则即可。2.4.4 具有约束的逻辑函数的化简1什么叫约束、约束项、约束条件各逻辑变量取值之间的相互制约关系叫做约束。例如教材2.4.1中所举的液位控制例子：液位控制系统真值表ABCMSML00000001010011100101011100111111A(40m)、B(30m)、C(20m)分别代表不同的液位高度，高于某点取“0”，低于某点取“1”。MS、ML代表两台电动机，“1”转“0”停。ABC=000，液位40m，MS、ML均为“0”；ABC=001，表示液位低于20m，又高于30m(或者40 m)，显然，这种情