逻辑代数基础.ppt

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