《逻辑代数基础》PPT课件.ppt

逻辑代数基础,逻辑代数是英国数学家GeorgeBoole于1847年提出的，所以又称为布尔代数或开关代数，它是分析和设计逻辑电路的重要数学工具。,英国数学家GeorgeBoole于1815年11月生于英格兰的林肯。1847年，发表了著作TheMathematicalAnalysisofLogic。1849年，他被任命位于爱尔兰科克的皇后学院的数学教授。1854年,他出版了TheLawsofThought。布尔撰写了微分方程和差分方程的课本。1864年，布尔死于肺炎。,1.逻辑变量与逻辑函数,在逻辑代数中的变量称为逻辑变量，通常用字母A、B、C等表示。逻辑变量的取值只有两种：真（“1”）和假（“0”）。这里的“1”和“0”并不表示数量的大小，而是表示完全对立的两种状态。,若以逻辑变量作为输入，以运算结果作为输出，那么当输入变量的取值确定之后，输出的取值便随之而定。因此，输出与输入之间乃是一种函数关系。这种函数关系称为逻辑函数，写作Y=F（A，B，C)。,2.逻辑代数中的三种基本运算,逻辑代数的基本运算有与(AND)、或(OR)、非(NOT)三种。它们各自的含义如图中（a）、（b）、（c）所示。,若把开关闭合作为条件，把灯亮作为结果，那么图中的三个电路代表了三种不同的因果关系：,图与、或、非说明电路,（a）逻辑与，也叫逻辑相乘：表示只有决定事物结果的全部条件同时具备时，结果才会发生。记作：Y=AANDB或Y=AB或Y=AB。其逻辑真值表如表。,“与门”的图形符号,与逻辑真值表,（b）逻辑或，也叫逻辑相加：表示决定事物结果的条件中只要有任何一个满足，结果就会发生。记作:Y=AORB或Y=A+B。其逻辑真值表如表。,或逻辑真值表,“或门”的图形符号,（c）逻辑非，也叫逻辑求反：表示只要条件具备了，结果就不会发生，否则结果一定发生。记做：或NOTA。其逻辑真值表如表。,“非门”（或反相器）的图形符号,非逻辑真值表,最常见的复合逻辑运算“与非”（NAND）,图“与非”复合逻辑的图形符号和运算符号,NANDTruthTable,最常见的复合逻辑运算“或非”（NOR）,图“或非”复合逻辑的图形符号和运算符号,N0RTruthTable,最常见的复合逻辑运算“与或非”（AND-NOR）,图“与或非”复合逻辑的图形符号和运算符号,最常见的复合逻辑运算“异或”（EXCLUSIVE-OR）和“同或”（EXCLUSIVE-NOR）,EX-OR,EX-NOR,图“异或”“同或”复合逻辑的图形符号和运算符号,描述逻辑函数的方法有以下六种：一、逻辑表达式（logicfunction）用与、或、非等逻辑运算表示逻辑关系的代数式叫逻辑函数表达式或简称函数式。例：Y=AB+CD,3逻辑函数的描述（即表示方法）,二、真值表（truthtable）将输入变量所有的取值对应的输出值找出来，列成表格，即可得真值表。列真值表时，需注意以下几点：（1）所有的输入的组合不可遗漏，也不可重复；输入组合最好按二进制数递增的顺序排列（完整性）。（2）同一逻辑函数的真值表具有唯一性。例：请列出举重裁判电路Y=A(B+C)的真值表。,例：已知某逻辑函数的真值表如下所示，试写出其逻辑函数式。,从真值表写出逻辑函数的一般方法：1、找出真值表中使逻辑函数Y1的那些输入变量取值的组合；2、每组输入变量取值的组合对应一个乘积项，其中取值为1的写入原变量，取值为0的写入反变量；3、将这些乘积项相或（加），即可得逻辑函数式。,（3）真值表还可作为判断两函数是否相等的依据。,三、逻辑电路图(logicdiagram)用代表逻辑运算的逻辑门符号所构成的逻辑关系图形，叫逻辑电路图，简称逻辑图。例：请画出的逻辑电路图。,四、卡诺图(KarnaughMap)后述。,五、波形图（时序图）(waveformortimingdiagram)指各个逻辑变量的逻辑值随时间变化的规律图。例：试画出举重裁判电路的波形图。,A,B,C,Y,例：试画出举重裁判电路的波形图。,六、文字描述,逻辑函数的各种表示方法可以相互转换。,4逻辑代数的基本公式和常用公式,一、逻辑代数的公理,二、逻辑代数的基本公式（定律）（1）交换律：AB=BA；A+B=B+A（2）结合律：A（BC）=（AB）C；A+（B+C）=（A+B）+C（3）分配律：A（B+C）=AB+AC；A+BC=（A+B）（A+C）（4）01定律：1A=A；0+A=A0A=0；1+A=1（5）互补律：,（6）重叠律：AA=A；A+A=A（7）反演律（De.Morgan定理)：（8）还原律：,注：1、若两个逻辑函数具有完全相同的真值表，则这两个逻辑函数相等。证明以上定律的基本方法均采用真值表法。2、逻辑代数与普通代数是不同的。例：,三、逻辑代数的常用公式（吸收律）,四、异或运算1、异或定义：,AB=,可见：AB=,2、异或运算的性质：（1）交换律：（2）结合律：（3）分配律：,思考：ABC?,在多变量异或运算中，若变量为1的个数为奇数，异或运算结果为1，若变量为1的个数为偶数，异或运算结果为0，与变量为0的个数无关。即:,(一)代入规则,AAA,利用代入规则能扩展基本定律的应用。,将逻辑等式两边的某一变量均用同一个逻辑函数替代，等式仍然成立。,5逻辑代数的三个基本定律,变换时注意：(1)不能改变原来的运算顺序。(2)反变量换成原变量只对单个变量有效，而长非号保持不变。,可见，求逻辑函数的反函数有两种方法：利用反演规则或摩根定律。,原运算次序为,(二)反演规则,对任一个逻辑函数式Y，将“”换成“+”，“+”换成“”，“0”换成“1”，“1”换成“0”，原变量换成反变量，反变量换成原变量，则得到原逻辑函数的反函数。,例：已知，求。,(三)对偶规则,对任一个逻辑函数式Y，将“”换成“+”，“+”换成“”，“0”换成“1”，“1”换成“0”，则得到原逻辑函数式的对偶式Y。,对偶规则：两个函数式相等，则它们的对偶式也相等。,应用对偶规则可将基本公式和定律扩展。,例4：证明该基本公式成立：,例5：,证明两个逻辑式相等，有时可通过证明它们的对偶式相等来完成，因为有些情况下证明其对偶式相等更加容易。,3个规则,代入规则：对任何一个含有原变量A的逻辑等式，如果在所有出现原变量A的位置处都代入一个逻辑函数F，则原逻辑等式仍然成立。反演规则：在一个逻辑函数中，若将函数中所有原来的“与”运算变成“或”运算，所有原来的“或”运算变成“与”运算，原变量变成反变量，反变量变成原变量，同时函数中的所有“1”变成“0”，且“0”变成“1”，这样所得到的一个新函数就称为原函数的反函数。对偶规则：在一个逻辑函数中，若将函数中所有原来的“与”运算变成“或”运算，所有原来的“或”运算变成“与”运算，函数中的所有“1”变成“0”，且“0”变成“1”，但逻辑变量保持不变，这样所得到的一个新函数就称为原函数的对偶函数，用F表示。,逻辑代数基本定律总结表,逻辑函数式化简的意义与标准,化简意义,使逻辑式最简，以便设计出最简的逻辑电路，从而节省元器件、优化生产工艺、降低成本和提高系统可靠性。,不同形式逻辑式有不同的最简式，一般先求取最简与-或式，然后通过变换得到所需最简式。,最简与-或式标准,(1)乘积项(即与项)的个数最少(2)每个乘积项中的变量数最少,用与门个数最少与门的输入端数最少,最简与非式标准,(1)非号个数最少(2)每个非号中的变量数最少,用与非门个数最少与非门的输入端数最少,逻辑式有多种形式，采用何种形式视需要而定。各种形式间可以相互变换。,逻辑函数式的几种常见形式和变换,例如,与或表达式,或与表达式,与非-与非表达式,或非-或非表达式,与或非表达式,转换方法举例,运用逻辑代数的基本定律和常用公式对逻辑式进行化简，消去函数中多余的乘积项和乘积项中的多余变量，使逻辑函数成为最简与-或式。,并项法,运用，将两项合并为一项，并消去一个互补的变量,二、常用的公式化简方法,吸收法,运用A+AB=A和，消去多余的与项。,A+AB=A,A+AB=A(1+B)=A,消去法,运用吸收律，消去多余因子。,配项法,通过乘或加入零项进行配项，然后再化简。,综合灵活运用上述方法,例化简逻辑式,解：,应用,例化简逻辑式,解：,例化简逻辑式,解：,应用,用摩根定律,用门电路实现逻辑函数时，需要使用与门、或门、非门、与或非门等器件，究竟将函数式变换成什么形式，要视所用门电路的功能而定。例1：将逻辑函数化为与非与非形式。例2：试用或非门画出函数的逻辑图。,三、指定器件的逻辑函数化简（*）,注：将最简与或式直接变换为其他类型的逻辑式时，得到的结果不一定也是最简的。,n个变量有2n种组合，可对应写出2n个乘积项，这些乘积项均具有下列特点：包含全部变量，且每个变量在该乘积项中(以原变量或反变量)只出现一次。这样的乘积项称为这n个变量的最小项，也称为n变量逻辑函数的最小项。,1.最小项的定义和编号,最小项的概念与性质,最小项定义逻辑函数中，如果一个与项（乘积项）包含该逻辑函数的全部变量，且每个变量或以原变量或以反变量只出现一次，则该与项称为最小项。对于n个变量的逻辑函数共有2n个最小项。最小项的表示最小项用m表示，通常用十进制数作最小项编号。把最小项中的原变量当作1，反变量当作0，所得的二进制数所对应的十进制数即为最小项的编号。若干最小项之和构成最小项表达式（也叫标准与-或表达式）：,如何编号？,如何根据输入变量组合写出相应最小项？,例如,3变量逻辑函数的最小项有23=8个,将输入变量取值为1的代以原变量，取值为0的代以反变量，则得相应最小项。,简记符号,例如,试分别写出它们的最大项,2.最小项的基本性质,(2)不同的最小项，使其值为1的那组变量取值也不同。,(3)对于变量的任一组取值，任意两个最小项的乘积为0。,(4)对于变量的任一组取值，全体最小项的和为1。,最大项定义逻辑函数中，如果一个或项（和项）包含该逻辑函数的全部变量，且每个变量或以原变量或以反变量只出现一次，则该或项称为最大项。对于n个变量的逻辑函数共有2n个最大项。最大项的表示最大项用M表示，通常用十进制数作最大项编号。把最大项中的原变量当作0，反变量当作1，所得的二进制数所对应的十进制数即为最大项的编号。若干最大项之和构成最大项表达式（也叫标准或-与表达式）：变量数相同时，下标编号相同的最大项和最小项应为互补。,三变量最大项编号表,思考：最大项与最小项之间存在什么关系？,从最大项的定义出发可以证明它具有如下的重要性质：（1）在输入变量的任何取值下必有一个且仅有一个最大项的值为0；（2）全体最大项之积为0；（3）某一最大项若不包含在F中，则必在中；（4）任意两个最大项之和为1；（5）只有一个变量不同的两个最大项的乘积等于各相同变量之和。,二、逻辑函数的“最小项之和”形式标准“与或”表达式利用基本公式，可将任何一个逻辑函数化为最小项之和的标准形式。这种标准形式在逻辑函数的化简以及计算机辅助分析和设计中得到了广泛的应用。例：试将逻辑函数展为最小项之和的形式。,三、逻辑函数的“最大项之积”形式标准“或与”表达式证明：任何一个逻辑函数都可以化成最大项之积的标准形式。例：试将逻辑函数化为最大项之积的标准形式。,一、逻辑函数的卡诺图表示法（一）卡诺图（KarnaughDiagram)卡诺图是由美国工程师卡诺首先提出的一种用来描述逻辑函数的特殊方格图。在这个方格图中，每个小方格代表逻辑函数的一个最小项，而且几何相邻的小方格具有逻辑相邻性，即两相邻小方格所代表的最小项只有一个变量取值不同。,二、三、四、五变量卡诺图为：,8逻辑函数的卡诺图化简,二变量卡诺图,三变量卡诺图,四变量卡诺图,五变量卡诺图,（二）卡诺图的特点：1、卡诺图中的小方格数等于最小项总数，若逻辑函数的变量数为n，则小方格数为个。,2、卡诺图行列两侧标注的0和1表示使对应方格内最小项为1的变量取值。同时，这些0和1组成的二进制数大小就是对应最小项的编号。此外，在卡诺图中，几何相邻的最小项具有逻辑相邻性，因此，变量的取值不能按照二进制数的顺序排列，必须按循环码排列。,3、卡诺图是一个上下、左右闭合的图形，即不但紧挨着的方格是相邻的，而且上下、左右相对应的方格也是相邻的。,1、已知函数式化成最小项之和形式卡诺图中对应最小项格填入“1”得到卡诺图。,（三）用卡诺图表示逻辑函数,例：试用卡诺图表示逻辑函数,2、已知真值表每组变量（即最小项）所对应的函数值填入卡诺图中相应方格化简得到函数式。,3、已知逻辑函数的卡诺图该函数的真值表写出该函数的逻辑函数式。,二、用卡诺图化简逻辑函数（一）用卡诺图化简逻辑函数的依据（基本性质）基本原理：各几何相邻方格的逻辑相邻性。,性质2：卡诺图中四个相邻“1”格的最小项可以合并成一个与项，并消去两个变量。例：,性质3：卡诺图中八个相邻“1”格的最小项可以合并成一个与项，并消去三个变量。例：,推论：在n个变量的卡诺图中，若有个“1”格相邻（k=0，1，2，3，n），它们可以圈在一起加以合并，合并时可以消去k个不同的变量，简化为一个具有（n-k）个变量的与项。若k=n，则合并时可消去全部变量，结果为1。,（二）用卡诺图求最简与或表达式,步骤：1、得到函数的真值表或将函数化为最小项之和的标准形式；2、画出函数的卡诺图；,例1：用卡诺图化简函数,3、合并最小项（即“画圈”）；“画圈”时应注意的问题：“1”格一个也不能漏，否则表达式与函数不等；“1”格允许被一个以上的圈包围，因为A+A=A；,圈的个数应尽可能少，因为一个圈对应一个与项，即与项最少；例：,圈的面积越大越好，但必须为个方格。这是因为圈越大，消去的变量就越多，与项中的变量数就越少。例：,每个圈至少应包含一个新的“1”格，否则这个圈是多余的，即增加了冗余项；例：,总之，即“可以重画，不能漏画，圈数要少，圈面要大，每个圈必有一个新1”。,4、写出最简“与-或”表达式。,例2：试用图形化简法求逻辑函数F（A，B，C，D）=m(1，2，4，9，10，11，13，15）的最简与或表达式。,例3：用卡诺图化简函数Y=m(1，3，6，7，14）,注：卡诺图化简得到的最简与或式不一定唯一。,一、约束项、任意项和逻辑函数式中的无关项约束项在某些情况下，输入变量的取值不是任意的。当限制某些输入变量的取值不能出现时，可以用它们对应的最小项恒等于0来表示。这些恒等于0的最小项叫约束项。任意项有时输入变量的某些取值是1还是0皆可，并不影响电路的功能。在这些变量取值下，其值等于1的那些最小项称为任意项。无关项约束项和任意项统称为逻辑函数中的无关项。“无关”指是否将这些最小项写入逻辑函数式无关紧要，在卡诺图中用“”表示无关项。在化简逻辑函数时，可认为它是1，也可认为它是0。,二、无关项在化简逻辑函数中的应用化简具有无关项的逻辑函数时，如果能合理利用这些无关项，一般都可以得到更加简单的化简结果。合并最小项时，究竟把卡诺图上的“”作为1还是0，应以得到的相邻最小项矩形组合最大，而且矩形组合数目最小为原则。例：试化简逻辑函数,已知约束条件为：,例：试用卡诺图化简逻辑函数,解答：此例有两种解法，从原理而言，两种解法均正确，但就“最简”原则而言，只有一种解法最简单、最可取。因此，在考虑卡诺图化简不唯一性的同时，还应考虑“最简”原则。,思考：由上例可得出什么结论和启示？,思考1：公式化简和卡诺图化简各有何优缺？,