第3章-布尔代数与逻辑函数化简.ppt

第三章布尔代数与逻辑函数化简,3.1基本公式和法则3.2逻辑函数的代数法化简3.3卡诺图化简,一、基本公式,3.1基本公式和规则,二、基本定律,普通代数没有！,例1证明等式A+BC=(A+B)(A+C),解：,真值表法,公式法,右式=(A+B)(A+C),用分配律展开,=AA,+AC,+BA,+BC,=A+AC+AB+BC,=A(1+C+B)+BC,=A1+BC,=A+BC,0,0,0,0,=左式,(二)逻辑代数的特殊定理,吸收律,A+AB=A,A+AB=A(1+B)=A,推广公式：,思考：(1)若已知A+B=A+C，则B=C吗？,(2)若已知AB=AC，则B=C吗？,推广公式：,摩根定律,(又称反演律),三、重要规则,(一)代入规则,AAA,利用代入规则能扩展基本定律的应用。,将逻辑等式两边的某一变量均用同一个逻辑函数替代，等式仍然成立。,变换时注意：(1)不能改变原来的运算顺序。(2)反变量换成原变量只对单个变量有效，而长非号保持不变。,可见，求逻辑函数的反函数有两种方法：利用反演规则或摩根定律。,原运算次序为,(二)反演规则,对任一个逻辑函数式Y，将“”换成“+”，“+”换成“”，“0”换成“1”，“1”换成“0”，原变量换成反变量，反变量换成原变量，则得到原逻辑函数的反函数。,(三)对偶规则,对任一个逻辑函数式Y，将“”换成“+”，“+”换成“”，“0”换成“1”，“1”换成“0”，则得到原逻辑函数式的对偶式Y。,对偶规则：两个函数式相等，则它们的对偶式也相等。,应用对偶规则可将基本公式和定律扩展。,四、基本公式应用1.证明等式,例3用公式证明,解,2.逻辑函数不同形式的转换逻辑函数的形式是多种多样的，一个逻辑问题可以用多种形式的逻辑函数来表示，每一种函数对应一种逻辑电路。逻辑函数的表达形式通常可分为五种：与或表达式、与非-与非表达式、与或非表达式、或与表达式、或非-或非表达式。,(3)或与式。将与或非式用摩根定律展开，即得或与表达式如下：,(4)或非-或非式。将或与表达式两次取反，用摩根定律展开一次得或非-或非表达式,图31同一逻辑的五种逻辑图,一、逻辑函数及其表示方法,逻辑函数描述了某种逻辑关系。常采用真值表、逻辑函数式、卡诺图和逻辑图等表示。,1.真值表,列出输入变量的各种取值组合及其对应输出逻辑函数值的表格称真值表。,3.2逻辑函数的代数法化简,0,0,4个输入变量有24=16种取值组合。,2.逻辑函数式,表示输出函数和输入变量逻辑关系的表达式。又称逻辑表达式，简称逻辑式。,逻辑函数式一般根据真值表、卡诺图或逻辑图写出。,(1)找出函数值为1的项。(2)将这些项中输入变量取值为1的用原变量代替，取值为0的用反变量代替，则得到一系列与项。(3)将这些与项相加即得逻辑式。,3.逻辑图,运算次序为先非后与再或，因此用三级电路实现之。,由逻辑符号及相应连线构成的电路图。,例如画的逻辑图,例1图示为控制楼道照明的开关电路。两个单刀双掷开关A和B分别安装在楼上和楼下。上楼之前，在楼下开灯，上楼后关灯；反之，下楼之前，在楼上开灯，下楼后关灯。试画出控制功能与之相同的逻辑电路。,(1)分析逻辑问题，建立逻辑函数的真值表,(2)根据真值表写出逻辑式,解：,方法：找出输入变量和输出函数，对它们的取值作出逻辑规定，然后根据逻辑关系列出真值表。,设开关A、B合向左侧时为0状态，合向右侧时为1状态；Y表示灯，灯亮时为1状态，灯灭时为0状态。则可列出真值表为,(3)画逻辑图,与或表达式(可用2个非门、2个与门和1个或门实现),异或非表达式(可用1个异或门和1个非门实现),二、逻辑函数式化简的意义与标准,化简意义,使逻辑式最简，以便设计出最简的逻辑电路，从而节省元器件、优化生产工艺、降低成本和提高系统可靠性。,不同形式逻辑式有不同的最简式，一般先求取最简与-或式，然后通过变换得到所需最简式。,最简与-或式标准,(1)乘积项(即与项)的个数最少(2)每个乘积项中的变量数最少,用与门个数最少与门的输入端数最少,最简与非式标准,(1)非号个数最少(2)每个非号中的变量数最少,用与非门个数最少与非门的输入端数最少,如直接由该函数式得到电路图，则如图3-3所示。,图3-3F原函数的逻辑图,但如果将函数化简后其函数式为F=AC+B只要两个门就够了，如图3-4所示。,图34函数化简后的逻辑图,三、代数化简法,运用逻辑代数的基本定律和公式对逻辑式进行化简。,并项法,运用，将两项合并为一项，并消去一个变量。,任何两个相同变量的逻辑项，只有一个变量取值不同(一项以原变量形式出现，另一项以反变量形式出现)，我们称为逻辑相邻项(简称相邻项)。如果函数存在相邻项，可利用吸收律，将它们合并为一项，同时消去一个变量。,解,令,解,利用等幂律，一项可以重复用几次。,其中与其余四项均是相邻关系，可以重复使用。,解,所以,吸收法,运用A+AB=A和，消去多余的与项。,消去法,运用吸收律，消去多余因子。,配项法,通过乘或加入零项进行配项，然后再化简。,例1化简,例2化简,综合灵活运用上述方法,例化简逻辑式,解：,应用,例化简逻辑式,解：,应用,应用AB,例化简逻辑式,解：,应用,用摩根定律,作业：书P691(3)，2(1)(4)，3(2)(3)，4(1)(4)，5(2)(6)(8),代数化简法,优点：对变量个数没有限制。缺点：需技巧，不易判断是否最简式。,卡诺图化简法,优点：简单、直观，有一定的步骤和方法易判断结果是否最简。缺点：适合变量个数较少的情况。一般用于四变量以下函数的化简。,一、代数化简法与卡诺图化简法的特点,3.3卡诺图化简,二、卡诺图化简的基本原理,例,解,n个变量有2n种组合，可对应写出2n个乘积项，这些乘积项均具有下列特点：包含全部变量，且每个变量在该乘积项中(以原变量或反变量)只出现一次。这样的乘积项称为这n个变量的最小项，也称为n变量逻辑函数的最小项。,1.最小项的定义,三、逻辑函数的标准式最小项,一个变量A有2个最小项：二个变量AB有4个最小项：,三个变量ABC有8个最小项：,任何形式的逻辑式都可以转化为标准与-或式，而且逻辑函数的标准与-或式是唯一的。,2.逻辑函数的最小项表达式,每一个与项都是最小项的与-或逻辑式称为标准与-或式，又称最小项表达式(不一定由全部最小项组成)。,例如,是最小项表达式。而,不是最小项表达式，而是一般式。,最小项表达式具有唯一性。任何逻辑函数的最小项表达式只有一个。,3.由一般式获得最小项表达式,(1)代数法。对逻辑函数的一般式采用添项法，例如,(2)真值表法。将原逻辑函数A、B、C取不同值组合起来，得其真值表，而该逻辑函数是将F=1那些输入变量相或而成的，如表3-4所示。,表34某逻辑函数的真值表,如何编号？,如何根据输入变量组合写出相应最小项？,例如,3变量逻辑函数的最小项有23=8个,将输入变量取值为1的代以原变量，取值为0的代以反变量，则得相应最小项。,简记符号,例如,4.最小项的编号,5.最小项的基本性质,(2)不同的最小项，使其值为1的那组变量取值也不同。,(3)对于变量的任一组取值，任意两个最小项的乘积为0。,(4)对于变量的任一组取值，全体最小项的和为1。,如何将逻辑式转化为标准与-或式呢？,例将逻辑式化为标准与或式。,(3)利用A+A=A，合并掉相同的最小项。,=m0+m1+m12+m13+m15,=m(0,1,12,13,15),解：(1)利用摩根定律和分配律把逻辑函数式展开为与或式。,AB,+,(2)利用配项法化为标准与或式。,(一)卡诺图的构成,四、逻辑函数的卡诺图表示法,1.相邻最小项,两个最小项中只有一个变量互为反变量，其余变量均相同，称为相邻最小项，简称相邻项。,相邻最小项重要特点：,两个相邻最小项相加可合并为一项，消去互反变量，化简为相同变量相与。,将n变量的2n个最小项用2n个小方格表示，并且使相邻最小项在几何位置上也相邻且循环相邻，这样排列得到的方格图称为n个变量最小项卡诺图，简称变量卡诺图。,2.卡诺图及其构成方法,变量取0的代以反变量取1的代以原变量,二变量卡诺图,01,01,00,01,m0,m1,m2,m3,四变量卡诺图,三变量卡诺图,01,0001,11,10,m6,m7,m4,m2,m3,m0,m5,001,m1,以循环码排列以保证相邻性,变量取0的代以反变量取1的代以原变量,卡诺图特点：循环相邻性,如何写出卡诺图方格对应的最小项？,已知最小项如何找相应小方格？,例如,原变量取1，反变量取0。,1,0,0,1,？,用卡诺图表示逻辑函数举例,已知标准与或式画函数卡诺图,例试画出函数Y=m(0,1,12,13,15)的卡诺图,解：(1)画出四变量卡诺图,(2)填图,逻辑式中的最小项m0、m1、m12、m13、m15对应的方格填1，其余不填。,已知真值表画函数卡诺图,例已知逻辑函数Y的真值表如下，试画出Y的卡诺图。,解：(1)画3变量卡诺图。,(2)找出真值表中Y=1对应的最小项，在卡诺图相应方格中填1，其余不填。,已知一般表达式画函数卡诺图,解：(1)将逻辑式转化为与或式,(2)作变量卡诺图,找出各与项所对应的最小项方格填1，其余不填。,例已知，试画出Y的卡诺图。,AB,+,(3)根据与或式填图,AB对应最小项为同时满足A=1，B=1的方格。,五、用卡诺图化简逻辑函数,化简规律,2个相邻项合并消去1个变量，化简结果为相同变量相与。,4个相邻项合并消去2个变量，化简结果为相同变量相与。,8个相邻项合并消去3个变量,画包围圈规则,包围圈必须包含2n个相邻1方格，且必须成方形。先圈小再圈大，圈越大越是好；1方格可重复圈，但须每圈有新1；每个“1”格须圈到，孤立项也不能掉。,同一列最上边和最下边循环相邻，可画圈；同一行最左边和最右边循环相邻，可画圈；四个角上的1方格也循环相邻，可画圈。,注意,m15,m9,m7,m6,m5,m4,m2,m0,解：(1)画变量卡诺图,例用卡诺图化简逻辑函数Y(A,B,C,D)=m(0,2,4,5,6,7,9,15),(2)填卡诺图,1,1,1,1,1,1,1,1,(3)画包围圈,a,b,c,d,(4)将各图分别化简,圈2个可消去1个变量，化简为3个相同变量相与。,Yb=BCD,圈4个可消去2个变量，化简为2个相同变量相与。,循环相邻,(5)将各图化简结果逻辑加，得最简与或式,解：(1)画变量卡诺图,例用卡诺图化简逻辑函数Y(A,B,C,D)=m(0,2,5,7,8,10,12,14,15),(2)填卡诺图,1,1,1,1,1,1,1,1,(4)求最简与或式Y=,1,消1个剩3个,(3)画圈,消2个剩2个,4个角上的最小项循环相邻,解：(1)画变量卡诺图,(2)填图,1,1,(4)化简,(3)画圈,例用卡诺图化简逻辑函数,Y=,例化简,例已知函数真值表如下，试用卡诺图法求其最简与或式。,注意：该卡诺图还有其他画圈法,可见，最简结果未必唯一。,解：(1)画函数卡诺图,1,1,1,1,1,1,(3)化简,(2)画圈,Y=,六、其它逻辑形式的化简,1.与非逻辑形式所谓与非式，就是全由与非门实现该逻辑，前面讲逻辑函数相互变换时已讲过，将与或式两次求反即得与非式。,2.或与逻辑形式首先从卡诺图上求其反函数，其方法是圈“”方格，然后再用摩根定律取反即得或与式。例求的反函数和或与式。,总结如下：在卡诺图上圈“0”方格，其化简结果：变量为0原变量；变量为1反变量，然后变量再相“或”起来，就得每一或项，最后再将每一或项“与”起来而得或与式。故此例可不通过求反函数，直接由上述过程得到或与式。,其逻辑图如下图所示。,3.或非逻辑形式将或与逻辑两次求反即得或非表示式：,按逻辑表达式即可画出或非逻辑电路图,4.与或非逻辑形式与或非逻辑形式可从两种途径得到：一种是从与或式得到，另一种是求得反函数后，再求一次反，即不用摩根定律处理，也可得与或非式。一般前一种途径所得电路要多用一个反相器，所以常用后一种方法得最简与或非式。,(a),(b),图与或非逻辑图,七、无关项及无关项的应用,逻辑问题分完全描述和非完全描述两种，对应于变量的每一组取值，函数都有定义，即在每一组变量取值下，函数F都有确定的值，不是“”就是“”，如表3-6所示。逻辑函数与每个最小项均有关，这类问题称为完全描述问题。,在实际的逻辑问题中，变量的某些取值组合不允许出现，或者是变量之间具有一定的制约关系。我们将这类问题称为非完全描述。该函数只与部分最小项有关，而与另一些最小项无关，我们用或者用表示。,对于含有无关项逻辑函