资源描述：
《数字逻辑-张少敏课件第2章 第二章第2节.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二节布尔代数的公式、定理和规则根据布尔变量的取值只有0和1以及布尔变量仅有的三种运算的定义,不难推出下列基本公式:交换律A+B=B+A(2.1.1)AB=BA(2.1.2)结合律(A+B)+C=A+(B+C)(2.2.1)(AB)C=A(BC)(2.2.2)一、布尔代数的基本公式分配律A(B+C)=AB+AC(2.3.1)A+BC=(A+B)(A+C)(2.3.2)0-1律A+1=1(2.4.1)A+0=A(2.5.1)A1=A(2.4.2)A0=0(2.5.2)互补律A+A=1(2.6.1)AA=0(2.6.2)等幂律A+A=A
2、(2.7.1)AA=A(2.7.2)吸收律A+AB=A(2.8.1)A(A+B)=A(2.8.2)A+AB=A+B(2.9.1)A(A+B)=AB(2.9.2)对合律(双重否定律)A=A(2.10)以上是布尔代数的基本公式。其中式(2.1.1)～(2.6.1)、式(2.1.2)～(2.6.2)和式(2.10)可以作为布尔代数的公理。公理是代数系统的基本出发点,是客观存在的抽象,它无需证明,但它可以用客观存在来验证。以此为基础,可以推得布尔代数的其他公式(2.7)～(2.9)。例如,式(2.7.1)的证明如下:A+A=(A+A)1(0
3、-1律)=(A+A)(A+A)(互补律)=A+AA(分配律)=A+0(互补律)=A(0-1律)又如,式(2.9.1)的证明如下:A+AB=(A+A)(A+B)(分配律)=1(A+B)(互补律)=A+B(0-1律)必须指出,上述基本公式中,有些公式与普通代数中的相同,但有些公式却是布尔代数中所特有的。这一点请读者在以后使用中注意。二、布尔代数的主要定理定理1德·摩根(DeMorgan)定理(1)x1+x2+…+xn=x1·x2·…·xn(2)x1·x2·…·xn=x1+x2+…+xn这就是说,n个变量的或的非等于各变量的非的与;n个变
4、量的与的非等于各变量的非的或。当变量的数目较少时,该定理可很容易用真值表证明。当变量为n个时,则可以用数学归纳法证明。德·摩根定理是布尔代数中一个很重要且经常使用的定理,它提供了一种变换布尔表达式的简便方法。由于它具有反演特性,即把变量的与运算改成或运算,或运算改成与运算,所以又称反演律。定理2香农(Shannon)定理f(x1,x2,…,xn,0,1,+,·)=f(x1,x2,…,xn,1,0,·,+)这就是说,任何函数的反函数(或称补函数),可以通过对该函数的所有变量取反,并将常量1换为0,0换为1,运算符“+”换为“·”,“·
5、”换为“+”而得到。证明:根据德·摩根定理,任何函数的反函数可写成f(x1,x2,…,xn,0,1,+,·)=f1(x1,x2,…,xn,0,1,+,·)+f2(x1,x2,…,xn,0,1,+,·)=f1(x1,x2,…,xn,0,1,+,·)·f2(x1,x2,…,xn,0,1,+,·)或写成f(x1,x2,…,xn,0,1,+,·)=f1(x1,x2,…,xn,0,1,+,·)·f2(x1,x2,…,xn,0,1,+,·)=f1(x1,x2,…,xn,0,1,+,·)+f2(x1,x2,…,xn,0,1,+,·)其中,f1和f
6、2是f的两个部分函数。对f1和f2重复上述过程,直到使f中的每个变量都用德·摩根定理。由于每对f(或f的部分函数)应用一次德·摩根定理,就将部分函数(或子部分函数)取反,并将与、或运算变换一次,以求得函数f(或部分函数)的反函数。因此,当对每个变量进行德·摩根变换后,其结果必然是f(x1,x2,…,xn,1,0,·,+),证毕。香农定理实际上是德·摩根定理的推广,它可以用在任何复杂函数。例2-1已知函数F=AB+AB(C+D),求其反函数F。解:F=AB+AB(C+D)=ABAB(C+D)=(A+B)(AB+C+D)=(A+B)[(
7、A+B)+CD]利用香农定理,可以直接写出F=(A+B)(A+B+CD)三、布尔代数的重要规则布尔代数有3个重要规则,即代入规则、反演规则和对偶规则,现分别叙述如下。1.代入规则任何一个含有变量X的等式,如果将所有出现X的位置,都代之以一个布尔函数F,则等式仍然成立。这个规则称为代入规则。由于任何一个布尔函数和任何一个变量一样,只有0或1两种取值,显然,以上规则是成立的。例2-2已知等式A+B=A·B,函数F=B+C,若用F代入此等式中的B,则有:A+(B+C)=A·B+CA+(B+C)=A·B·C据此可以证明n变量的德·摩根定理的
8、成立。2.对偶规则任何一个布尔函数表达式F,如果将表达式中的所有的“+”改成“·”,“·”改成“+”,1改成0,0改成1,而变量保持不变,则可得到一个新的函数表达式Fd,称Fd为F的对偶函数。这一规则称为对偶规则。例如,下列为几个原函
