数字逻辑(毛法尧)第二章.ppt

1,第二章逻辑代数基础,逻辑代数是描述/分析/设计数字逻辑电路的数学工具。运用逻辑运算可以设计最简逻辑电路。,2,2.1逻辑代数的基本概念,逻辑代数：是由逻辑变量集、常量“0”、“1”及“与”、“或”、“非”等运算符号、函数、表达式等构成的代数系统。利用逻辑代数可以描述任何复杂的电路中条件与输出结果间的逻辑关系。逻辑代数中也用字母表示变量,这种变量称为逻辑变量。但变量的取值只能是1或0，代表逻辑电路中的两种不同的逻辑状态，如开关的闭合与打开，电路的导通与截止，电压与电流的有或无等。,3,1、基本逻辑运算1）逻辑“与”运算,对于逻辑问题，如果决定某一事件发生的多个条件必须同时具备，事件才能发生，则这种因果关系称之为“与”逻辑。逻辑代数中，“与”逻辑关系用“与”运算描述。“与”运算又称为逻辑乘，其符号为“”、“”、“AND”。逻辑表达式：F=AB=AB=,1(A、B均为1)0(A、B中任一为0),4,举例,5,2）逻辑“或”运算,对于逻辑问题，如果决定某一事件发生的多个条件中，只要有一个或一个以上条件成立，事件便可发生，则这种因果关系称之为“或”逻辑。逻辑代数中，“或”逻辑关系用“或”运算描述。“或”运算又称为逻辑加，其符号为“+”、“”、“OR”。逻辑表达式：F=A+B=AB=,1(A、B中任一为1)0(A、B均为0),6,3）逻辑“非”运算,对逻辑问题，如果某一事件的发生取决于条件的否定，即事件与事件发生的条件之间构成矛盾，则这种因果关系称为“非”逻辑。逻辑“非”又称为逻辑反运算.运算符号：“”（上面加横线）逻辑表达式为：F=,A,1（A=0）0（A=1）,7,3、逻辑函数,在数字电路中，如果某一输出变量与一组输入变量存在着一定对应关系，即输入变量取任意一组确定的值，输出变量的值也就唯一地被确定，则称这种关系为逻辑函数关系。设输入变量为A1,A2,An,输出变量为F，则：F=f(A1,A2,An)。注意：1.无论自变量或函数均只能取0或1两值。函数和自变量的关系只能由“与”、“或”、“非”三种基本运算来定义。2.设F1=f1(A1,A2,An)，F2=f2(A1,A2,An)，若对应于A1,A2,An的任何一组取值，F1和F2的值都相同，则称函数F1和F2相等，记成F1=F2。,8,2.2逻辑代数的公理、定理及规则,1.公理系统：(满足一致性、独立性和完备性)交换律：A+B=B+A，AB=BA；结合律：(A+B)+C=A+(B+C);(AB)C=A(BC)分配律：A+(BC)=(A+B)(A+C)A(B+C)=AB+AC0-1律：A+0=A，A1=A；A+1=1，A0=0互补律：A+A=1，AA=0问题：用开关电路表达这些公理（0、1在开关电路中分别代表什么？）,Back,9,2.基本定理(由上述公理推出下述基本定理),定理1：0+0=0，1+0=1，0+1=1，1+1=100=0，10=0，01=0，11=1证明：由公理4(0-1律)，分别以0和1代替A，可得上述各式。推论：1=0，0=1证明：由公理5(互补律)，分别以0和1代替A，可得上述两式。,10,定理2：A+A=A，AA=A（重叠律）,证明：A+A=(A+A)1公理4（0-1律）=(A+A)(A+A)公理5（互补律）=A+(AA)公理3（分配律）=A+0公理5=A公理4证明：AA=AA+0公理4=AA+AA公理5=A(A+A)公理3=A公理4,11,定理3：A+AB=A（吸收律）证明：A+AB=A1+AB公理4（0-1律）=A(1+B)公理3（分配律）=A1公理4=A公理4A(A+B)=A证明：A(A+B)=AA+AB公理3=A+AB=A,12,定理4：,A+AB=A+B证明：A+AB=(A+A)(A+B)(分配律)=1(A+B)(互补律)=A+B(0-1律)A(A+B)=AB证明:A(A+B)=AA+AB(分配律)=0+AB(互补律)=AB(0-1律),13,定理5：,A=A（还原律）证明:由公理5可以得出A=A,14,定理6：(摩根定理)(是最重要和有用的定理),A+B=ABAB=A+B证明:定义两组逻辑式为A+B和AB，则(AB)+(A+B)=(AB+A)+B结合律=(A+AB)+B交换律=(A+A)(A+B)+B分配律=1(A+B)+B=(A+B)+B=A+1=1(AB)(A+B)=ABA+ABB分配律=B0+A0互补律=0+0=0,15,因此，根据公理5,可得到：A+B=AB，或是A+B=AB即得证同理，可证明：AB=A+B,16,定理7：,AB+AB=A(A+B)(A+B)=A证明：AB+AB=A(B+B)公理3=A1公理5=A公理4(A+B)(A+B)=A+(BB)公理3=A+0公理5=A公理4,17,定理8：,AB+AC+BC=AB+AC(A+B)(A+C)(B+C)=(A+B)(A+C),18,3.逻辑代数三条重要规则,规则1：代入规则任何一个含有变量A的逻辑等式，如果将所有出现A的位置都代之以同一个逻辑函数F，则等式仍然成立。用途：利用代入规则，可以将逻辑代数公理、定理中的变量用任意函数代替，从而推导出更多的等式。,19,规则2：反演规则：,将逻辑函数式F中所有的“”变成“+”，“+”变成“”，“0”变成“1”，“1”变成“0”，原变量变成反变量，反变量变成原变量，则所得到的新函数表达式为原函数F的反函数F。例：F=AB+BCD，则F=(A+B)(B+C+D)用途：利用反演规则，可以方便地求出一个函数的反函数。,20,规则3：对偶规则：,如果将逻辑函数式F中所有的“”变成“+”，“+”变成“”，“0”变成“1”，“1”变成“0”，而逻辑变量保持不变，则所得到的新函数表达式称为原函数F的对偶式，记作F。对偶规则:若F和G相等,则F和G也相等。即若两函数相等，则其对偶式也相等。用途：根据对偶规则,若某两个逻辑函数表达式相等,则它们的对偶式也必定相等。可使定理和公式的证明减少一半。（如定理7、8等）,21,2.3逻辑函数的表达形式与转换,2.3.1逻辑函数的表示方法：1、逻辑表达式：即由逻辑变量、逻辑常量和运算符所构成的式子。前面已经通过逻辑表达式讨论了公理、定理和规则。注意：非运算可以不加括号、与运算符通常省略、运算优先级由高到低为非、与、或,22,逻辑函数表达式的基本形式,1.“积之和”是指一个函数表达式中包含着若干个“积”项，每个“积”项中可有一个或多个以原变量或反变量形式出现的字母，所有这些“积”项的“和”就表示了一个函数。例如：B、AB、ABC均为“积”项，而它们的“积”之“和”就构成了一个函数：F=B+AB+ABC“积之和”又被称为“与-或表达式”。,23,最小项表达式：,一个具有n个变量的函数的“积”项如果包含全部n个变量，每个变量都以原变量或反变量形式出现，且仅出现一次，则这个“积”项被称为最小项。例如三变量最小项：ABC、ABC、ABC等等。如果一个函数完全由最小项组成，则称该函数为标准“积之和”表达式，即最小项表达式。,24,问题：由n个变量组成的最小项总共可有多少个？,因为最小项中每个变量可以用原变量和反变量两种形式出现，所以n个变量共可以组成2n个最小项，即3个变量可以组成8个最小项，例如：由A、B、C三个变量组成的最小项可以有如下8个：ABC、ABC、ABC、ABC、ABC、ABC、ABC、ABC。通常用mi表示最小项，下标i是怎样确定的呢？当ABC确定后，如果将原变量看成1，反变量看成0，则1和0就排列成一个二进制数，与这个二进制数相对应的十进制数，就是最小项的下标i的值。例如：ABC(011)2=(3)10m3,3个变量的最小项有如下8个：m0、m1、m2、m3、m4、m5、m6、m7,25,所以函数F(A、B、C)=ABC+ABC+ABC+ABC=m(2、3、6、7)注意：等式左边括号内变量的顺序非常重要，与最小项的编号有关，切记！任何一个逻辑函数都可以表示成若干个最小项的“和”。,26,推论：n个变量的2n个最小项不是包含在F的标准“积之和”之中，便是被包含在F的标准“积之和”之中。推论：n个变量的2n个最小项之和恒等于1。,27,2.“和之积”,指一个函数表达式中包含着若干个“和”项，每个“和”项中可有一个或多个以原变量或反变量形式出现的字母，所有这些“和”项的“积”就表示了一个函数。例如：(A+B)、(B+C)、(A+B+D)均为“和”项，而它们的“和”之“积”就构成了一个函数：F=(A+B)(B+C)(A+B+D)“和之积”又被称为“或-与表达式”。,28,最大项表达式：,一个具有n个变量的函数的“和”项如果包含全部n个变量，每个变量都以原变量或反变量形式出现，且仅出现一次，则这个“和”项被称为最大项。例如：A+B+C、A+B+C、A+B+C等等。如果一个函数完全由最大项组成，则称该函数为标准“和之积”表达式，即最大项表达式。,29,问题：由n个变量组成的最大项总共可有多少个？,因为最大项中每个变量可以用原变量和反变量两种形式出现，所以n个变量共可以组成2n个最大项，即3个变量可以组成8个最大项，例如：由A、B、C三个变量组成的最大项可以有如下8个：A+B+C、A+B+C、A+B+C、A+B+C、A+B+C、A+B+C、A+B+C、A+B+C。通常用Mi表示最大项，i是怎样确定的呢？当ABC确定后，如果将原变量看成0，反变量看成1，则0和1就排列成一个二进制数，与这个二进制数相对应的十进制数，就是最大项的下标i的值。例如：A+B+C(101)2=(5)10M5,30,所以函数F(A、B、C)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)=M(0、1、4、5)注意：等式左边括号内变量的顺序非常重要，与最大项的编号有关，切记！任何一个逻辑函数都可以表示成若干个最大项的“积”的形式。,31,推论：n个变量的2n个最大项不是包含在F的标准“和之积”之中，便是被包含在F的标准“和之积”之中。推论：n个变量的2n个最大项之积恒等于0。,32,问题：最小项和最大项有什么关系？,下标相同的最小项和最大项之间存在互补关系。即：Mi=mimi=Mi例如：m3=ABC，则M3=A+B+C因为M3=A+B+C，所以M3=A+B+C=ABC=m3,33,3.其它形式,F=(AB+D)(AB+CD)显然，上式既不是“与或”表达式，也不是“或与”表达式，但通过一定的运算，可以转换成“与或”表达式或“或与”表达式。F(A+D)(B+D)(AB+C)(AB+D)=(A+D)(B+D)(A+C)(B+C)(A+D)(B+D)=(A+D)(B+D)(A+C)(B+C)即得“或与”表达式，同理可得“与或”表达式,34,2.3.4逻辑函数表达式的转换：,逻辑表达式的形式很多，通常都转换成标准形式(最小项或最大项):1.转换成最小项-利用逻辑代数的公理、定理和规则对表达式进行逻辑变换。过程如下：将表达式转换成一般“与或表达式”。将表达式中非最小项的“与”项都扩展成最小项。,35,例：将F=A+BC转换成最小项之和,F=A+BC=A(B+B)(C+C)+(A+A)BC=ABC+ABC+ABC+ABC+ABC+ABC=ABC+ABC+ABC+ABC+ABC=m(1,4,5,6,7),36,例：将F=(AB+AB+C)AB转换成最小项之和,37,2.转换成最大项-利用逻辑代数的公理、定理和规则对表达式进行逻辑变换。过程如下：将表达式转换成一般“或与表达式”。将表达式中非最大项的“或”项都扩展成最大项。,38,例如2.3：将F=AB+AC转换成最大项之积。,F=AB+AC=ABAC=(A+B)(A+C)=(A+B+CC)(A+BB+C)=(A+B+C)(A+B+C)(A+B+C)(A+B+C)=M6M7M1M3=M(1,3,6,7),39,由逻辑变量的所有可能取值的组合及其对应的逻辑函数值所构成的表格。是一种输入变量的穷举表。对应每一个逻辑函数的表达式可以列出其真值表，由每一个真值表也可以写出其对应的逻辑函数表达式。,2、真值表：,40,真值表转换为逻辑表达式：,转换成最小项-当列出真值表后，只要将真值表中取值为1的最小项或起来，就可以得到函数的与或表达式这样得到的一般是最小项表达式。问题：真值表是如何作出的？只要将输入变量的全部组合分别一一代入函数式，就可以求出此真值表。,41,由真值表求函数最大项之积的形式,转换成最大项-当列出真值表后，只要将真值表中取值为0的最大项与起来，就可以得到函数的表达式。,42,3、卡诺图：,即逻辑关系的一种图形表示形式。同时也是化简逻辑表达式的一种非常有效的方法。卡诺图是一种直观的平面方块图。它根据输入变量的数量n将平面划分为2n个方格，用来表示全部输入变量组合项或者表示全部输出项。后面详细讨论。,43,2.4逻辑函数的化简,为什么要讨论逻辑函数的化简?一般地说,逻辑函数表达式愈简单,则其对应的逻辑电路也就愈简单,工作就愈可靠,成本就愈低,虽然同一个逻辑函数可以有不同的表达式的形式,但是它们的逻辑功能都是相同的,所以人们必须对逻辑函数进行化简,求得最简的逻辑表达式。,44,什么样的逻辑函数表达式算是最简的呢？,1.如果最后得到的式子是“与-或”形式的，则在满足“与”项必须为最少的条件下，每个“与”项中的变量个数必须为最少。2.如果最后得到的式子是“或-与”形式的，则在满足“或”项必须为最少的条件下，每个“或”项中的变量个数必须为最少。问题：最小项表达式是否为最简与或表达式？,45,2.4.1代数化简法：,利用逻辑代数的公理、定理和规则对表达式进行逻辑化简。1.“与-或”表达式的化简(1)并项法:ABC+ABC=AB(2)吸收法:B+ABD=B(3)消去法:A+AB+DE=A+B+DE(4)配项法:AB+AC+BC=AB+AC,46,2.“或-与”表达式的化简,如何对“或-与”表达式进行化简？利用逻辑代数的公理、定理和规则对表达式进行逻辑化简。如果对“或-与”不太熟悉，则可用两次求对偶的方法。先将“或-与”求对偶转换成“与-或”，然后化简得出最简式，最后再求一次对偶，即可得到最简的“或-与”表达式。,47,总结：逻辑代数化简要求对逻辑代数的公理、定理和规则非常熟悉，技巧性很强，有一定的难度，优点是化简时不受逻辑变量数目的约束。,48,1.卡诺图的构成：,n个变量的卡诺图是一种由2n个方格构成的图形，每个方格表示逻辑函数的一个最小项，由于任何函数都可以表示成“最小项之和”形式，所以逻辑函数可由卡诺图中若干个方格组成的区域来表示。,2.4.2卡诺图化简法：,49,1,A,A,A+A=1,B,B,B+B=1,一变量卡诺图,50,两变量卡诺图,如下：,A,B,01,01,m0,m2,m1,m3,A,B,AA01,AB,AB,AB,AB,B0B1,只有一个变量不同的任何两个最小项称为相邻。每一个方格和2个方格相邻.,51,三变量卡诺图下图为三变量卡诺图。卡诺图的左边、上边书写自变量的可能取值，规则是相邻只有一位变。方格中间则表明最小项。,AB,C,00011110,01,m0m2m6m4m1m3m7m5,m1和m0、m3和及m5及相邻。每一个方格和3个方格相邻。,ABCABCABCABCABCABCABCABC,AB,C,01,00011110,A,C,B,52,四变量卡诺图,CD,AB,00,01,11,10,00,01,11,10,A,D,B,C,每一个方格和4个方格相邻。,53,五变量卡诺图,实际上，将ABCDE分成两组，(ABC)一组在上面，(DE)另一组在左边,共有32个方格。,54,六变量卡诺图,由两个五变量卡诺图构成，除了注意左、右四变量卡诺图的重合关系外，还要注意上、下四变量卡诺图的重合关系。例如最小项31和23、27，29、30及15相邻外，还与63相邻。每一个方格和6个方格相邻。,55,总结：,一个含有n个变量的卡诺图由2n个方格组成，每个方格代表一个最小项，在n个变量的卡诺图中，能直观、方便地找到每个最小项(方格)的n个相邻最小项(方格)。所谓相邻，就是最小项只含有一个不同的变量。,56,2.逻辑函数在卡诺图上的表示：,如果逻辑函数已经转换成“最小项”之和的形式，则只要在卡诺图上找到这些最小项的方格，并标以1，其它方格，标以0，就得到该函数的卡诺图。例如：F=m1+m2+m3,A,B,01,01,0111,57,又如：F(A.B.C)=m(0,3,5),画出对应的卡诺图如下：,AB,C,00011110,01,10000101,58,再如：F(A.B.C.D)=m(0,3,5,7,10,11,12,14),画出对应的卡诺图如下：,AB,CD,00011110,00011110,1010010011010011,59,如果逻辑函数是“与-或”表达式，则要将各“与”项分别表示在卡诺图上，然后填入1。,如：F(A.B.C)=AC+AB+ABC+BC,AB,C,00011110,01,AB,AC,BC,ABC,01001111,60,3.卡诺图上最小项的合并：,卡诺图上合并最小项的基本原理是根据逻辑代数定理7：AB+AB=A，因为它表明，如果两个“与”项(最小项)只有一个变量不同，其余变量都相同，则这两个“与”项可以合并，并消去这个不同的变量。由于卡诺图的每个方格代表一个最小项，两个相邻方格仅有一个变量不同，因而可以合并成一个较大的区域，并用一个“与”项来表示。下面画出了两变量卡诺图的三种典型相邻方格合并的情况。,61,二变量卡诺图的三种典型相邻方格的合并图,A,B,01,01,两个最小项合并,A,B,01,01,A,B,01,01,0011,1010,1110,AB+AB=BAB+AB=AAB+AB+AB=A+B消去一个变量消去一个变量,其中AB分别和AB及AB相邻,合并消去两个变量,62,三变量卡诺图的两种典型相邻方格的合并图,四个最小项合并,AB,C,00011110,01,AB,C,00011110,01,0011001,01100110,m0、m1、m4、m5相邻，m2、m3、m6、m7相邻，合并成B(消去2个变量)合并成B(同左),63,请看示例：,C,1111,AB,00011110,01,仍以前面所述的三人表决逻辑为例。根据真值表得到的逻辑表达式为：F(A,B,C)=ABC+ABC+ABC+ABC=m3+m5+m6+m7,AB,BC,AC,根据卡诺图化简结果：F=AB+BC+AC,相邻的方格可以合并。,64,四变量卡诺图的三种典型相邻方格的合并图,四个相邻最小项合并的三种情况，消去2个变量,AB,CD,00011110,00011110,AB,CD,00011110,00011110,AB,CD,00011110,00011110,001011001101001,0110100110010110,0100010011110100,m0+m2+m8+m10=BDm5+m7+m13+m15=BD,m1+m3+m9+m11=BDm4+m6+m12+m14=BD,m4+m5+m6+m7=ABm3+m7+m11+m15=CD,65,四变量卡诺图的两种典型相邻方格的合并图,八个相邻最小项合并的两种情况，消去3个变量,AB,CD,00011110,00011110,AB,CD,00011110,00011110,0110011001100110,1001100110011001,F=B,F=B,66,推论：,在n个变量组成的卡诺图中，2n个标以1的相邻方格都可以进行合并，即由2n个相邻方格所表示的最小项并成一项(为1)，并且消去n个变量。,67,4.用卡诺图化简逻辑函数：,任何两个标“1”的相邻单元可以形成一个圈，从而消去一个变量；部分四个标“1”的相邻单元可以形成一个圈，从而消去两个变量；部分八个标“1”的相邻单元可以形成一个圈，从而消去三个变量；卡诺图化简的过程就是在卡诺图上找出能够覆盖给定函数全部为1的单元的圈，它应该满足个数最少、同时覆盖面尽可能大。然后写出其对应的逻辑表达式。,68,CD,AB,00011110,00011110,1,1,1,1,1,1,1,1,例：试用卡诺图化简下面的逻辑表达式。解：根据逻辑表达式做出卡诺图如下：根据卡诺图化简规则，最后得到化简后的结果：,69,CD,AB,00011110,1,1,1,1,00011110,1,1,1,1,例：试用卡诺图化简下面的逻辑表达式。解：根据逻辑表达式做出卡诺图如下：根据卡诺图化简规则，最后得到化简后的结果：,70,问题：有时要求函数的最简“或与”表达式，如何求呢？,合并卡诺图上的1方格（最小项）可以得到最简与或表达式，那么合并卡诺图上的0方格（最大项）则可以得到最简或与表达式,71,用卡诺图求函数F=AC+AD+BC+BD的最简“或与”表达式,AB,CD,00011110,00011110,101101110110000,1.先作函数F的卡诺图。2.对图中的0方格进行合并，合并时直接写成或与形式，得到F的最简“或与”表达式：F=(A+B)(C+D),72,2.4.3逻辑函数化简中有关问题的考虑：,1.包括无关最小项的逻辑函数的化简：有时在实际问题中会遇到虽然大多数最小项有确定的值，但是另一些最小项就没有确定的值，也就是说，它们既可以为1，也可以为0。这是因为：某些输入变量组合不允许出现，或者根本不可能出现，所以没有必要考虑其值为0或1。虽然每种输入变量组合都可能出现，但是人们对其中某些输入组合究竟使函数值为1还是0并不关心。如果遇到这类