离散数学第七章格与布尔代数ppt课件

《离散数学第七章格与布尔代数ppt课件》由会员分享，可在线阅读，更多相关《离散数学第七章格与布尔代数ppt课件（118页珍藏版）》请在金锄头文库上搜索。

1、第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第7章格与布尔代数n7.1 格格 n7.2 格是代数系统格是代数系统n7.3 特殊的格特殊的格n7.4 布尔代数布尔代数第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.1格n在第三章曾讨论过偏序集合,定义了有关的术语。并曾证明过:(1)一个偏序集合的子集,如果存在最小上界(lub),则它是唯一的,如果存在最大下界(glb),则它也是唯一的;(

2、2)如果偏序集合拥有最小元素,则它是唯一的,如果偏序集合拥有最大元素,则它也是唯一的。我们就以这些知识为基础介绍格的概念和有关性质。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.11格的定义n定义7.11设L,是一个偏序集合,如果L中每一对元素a,b,都有最大下界和最小上界,则称此L,为格。n通常用ab表示a,b的最大下界,用ab表示a,b的最小上界。即na*b=glba,bn ab=luba,b第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到

3、的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例1n(a)设D是正整数集合I+中的整除关系,则I+,D是格,因为对任意a,bI+,n a*b=glb a,b =GCDa,b (a,b的最大公因数)nab=luba,b=LCMa,b(a,b的最小公倍数)n(b)设n是一正整数,Sn是n的所有因子的集合。例如S6=1,2,3,6,S8=1,2,4,8,D是整除关 系 ,则 Sn,D 是 格 ,例 如S8,D,S6,D,S30,D的哈斯图如图7.11(a),(b),(c)所示。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的

4、金额为消费者购买商品的价款或接受服务的费用n(c)设S是任意集合,是它的幂集,偏序集合(S),是格,因为对S的任意子集A,B,AB就是A,B的最小上界,AB就是A,B的最大下界。n当集合S仅含有二个或三个元素时,相应的格的哈斯图亦如图7.11(b)和(c)所示。n(d)设S是非空集合,(S)是S的所有划分,(S)中的偏序关系可定义为细分,ij当且仅当i中的每一块都在j的某一块中。于是划分积与划分和+分别是保交和保联。所以(S),是格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例如S=a

5、,b,c,则n(S)=1,2,3,4,5n1=a,b,c,2=a,b,c,n3= a,c , b ,4=a,b,cn5=a,b,cn(S),的哈斯图如图7.11(d)所示。n(e)图7.11(e)所示的哈斯图也是一个格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.11 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.12 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为

6、的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.1.2格的对偶性原理和基本性质n给定一个偏序集合S,的逆关系也是S中的偏序关系,S,也是偏序集合,我们称偏序集合S,和S,互为对偶。从图形上看,后者的哈斯图就是前者哈斯图的上下颠倒。如果AS,则关系的lub(A)和glb(A)就分别等同于关系的glb(A)和lub(A)。因此,如果L,是一个格,则L,也是一个格,我们说这两个格互为对偶。互为对偶的两个格L,和L,有着密切关系:格L,中的保交正是格L,中的保联,第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿

7、其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n而格L,中的保联正是格L,中的保交。因此,给出关于格一般性质的任何有效命题,把关系换成,(或把换成),把保交换成保联,保联换成保交,我们能够得到另一个有效命题,这就是关于格的对偶性原理。n格的基本性质如表7.11所示。如果一个公式的对偶公式是其自身,则对偶式不重复列出。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用表7.11 格的基本性质第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受

8、到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用表7.11 格的基本性质第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n现证明表中各公式。n证n公式(1)(3)是偏序集合定义所要求的,对一切偏序集合均成立,格是偏序集合,所以对一切格也成立。公式(4)(5)是根据保交和保联的定义所得的,所以对一切格成立。n(6)交换律的证明。n由保联的定义得ab=luba,b=lubb,a=ba。n由对偶原理得a*b=b*a。(下边都仅证两对偶恒等式中的一个。)第7章 格与布尔代数经营者提供商品

9、或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(7)结合律的证明。n设R=a(bc)和R=(ab)c,由公式(4)(加撇表示右侧的公式,下同)得Ra,Rbc,根据公式(4)和(3)得Rb和Rc。这样,根据公式(5)得Rab;由Rab和Rc得R(ab)c=R。类似地可证Ra(b c)=R。因此,根据公式(2)n得(ab) c=a(bc)。n结合律说明,无括号表达式a1a2ann和a1*a2*an都是单义的。因此,可以论述任何数目的格的元素的保交和保联。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要

10、求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(8)等幂律的证明。n由 公 式 (1)有 aa,根 据 公 式(5)得aa a。又由公式(4)a aa,因此,根据公式(2)得a a=a。n(9)吸收律的证明。n由公式(1)有aa,由公式(4)有aa*b,因此,根据公式(5)得aa (a*b),但由公式(4)有a (a*b)a,这样,根据公式(2)得a (a*b)=a。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(10)aba*b=aa b=b的证明。n先证

11、aba*b=a,由公式1知aa,由假设ab,所以,由公式5得aa*b,但a*ba。因此,a*b=a。即ab n a*b=a。 现 设 a*b=a,由 公 式 (4)知a*bb,所以ab,既a*b=a ab。n再证a*b=aa b=b由a*b=a得b (a *b)=a b,n即a b=b。反之,若a b=b,则a*(a b)=a*b,即a*b=a。n公式(10)建立了格中偏序关系和保交,保联间的一种联系。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(11)adbca*bd*c和adbca

12、n bdc的证明。n因为ddc,cdc,由传递性得adc,bdnc,由 公 式 5得 a bd c,因 为a*ba,a*bb,由传递性得a*bd,a*bc,由公式(5)得a*bd*c。n(12)保序性的证明。n公式(11)中d取为a即得。n(13)分配不等式的证明。n由aa b和aa c得a(a b)*(a c),n由ba b和ca c得b*c(a b)*(a c)。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n所以,a (b*c)(a b)*(a c)n(14)模不等式的证明。n若ac,

13、则a c=c,代入公式(13)得n a (b*c)(a b)*cn若a(b*c)(a b)*c,由于aa (b*c),(a b)*cc,根据传递性得ac。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.2格是代数系统n7.2.1格n定义7.21设L,*,是代数系统,*和是载体L上的二元运算。如果二元运*算和都是可交换和可结合的,并且满足吸收律和等幂律,则代数系统nL,*,是格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为

14、消费者购买商品的价款或接受服务的费用n定义中等幂律可以删除,因为a*a=a*(a (a a)=a,由吸收律可推出等幂律。类似地可证a a=a。n这一定义和上节的定义实际上是等价的,下述定理说明这一点。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.21如果L,*,是一个格,那么,L中存在一偏序关系,在此偏序关系作用下,对所有a,bL有n a b=luba,b(1)n a*b=glba,b(2)n证首先我们在L上定义一个关系。对任意a,bLn aba*b=an现在我们证明是偏序关系。因

15、为,第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(1)对任一元素aL,由等幂律a*a=a,有aa,即是自反的。n(2)对某一a,bL,如果ab和ba,那 么 a*b=a和 b*a=b。 但 a*b=b*a,所 以a=b。即是反对称的。n(3)对某一a,b,cL。如果ab和bc,那么a*b=a和b*c=b,于是na*c=(a*b)*c=a*(b*c)=a*b=an所以,ac,即是传递的。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔

16、偿的金额为消费者购买商品的价款或接受服务的费用n7.2.2子格,格同态和格的积代数n定义7.22L,*,是一个格,S L,如果S对运算和封闭,那么称S,*,是L,*,的子格。n子格本身是一个格,因为交换律,结合律,吸收律都是继承的。显然,不是L的任意子集都可构成子格。例如图7.21所示的格中,a,b,d,是子格,b,c,不是子格,因为b,c对运算不封闭。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.21 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加

17、赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.23 L, *, 和S,是两个格。n定义一个映射f:LS,如果对于任何a,bL,有nf (a*b)=f (a)f(b)n和nf (a*b)=f (a)f (b)n则称f是从L,*,到S,的格同态。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.22第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.2

18、2 L, *, 和S,是两个格,n在集合L和S中,对应于保交和保联运算的偏序关系 分别是和,如果f:LSn是格同态,则对任何a,bL,且ab,必有f (a)f (b)。n证根据aba*b=a有nf (a*b)=f (a)f (b)=f (a)n所以,f (a)f (b)。证毕第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n在定义7.23中,若f是双射函数,则称f是格同构。或说L,*,和S,两个格同构。由于同构是相互的,又是保序的,所以对任何a,bL有,n abf (a)f (b)n和n f

19、(a)f (b)abn这说明同构的两个格的哈斯图是一样的,只是各结点的标记不同而已。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 图 7.23 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例1n(a)设L1=a,b,c,L2=(a,b,c),如图7.23n所示。f:a,b,c(a,b,c),f (x)=y|yx。n因为f (x1*x2)=f (minx1,x2)=y|yminx1,x

20、2n=y|yx1y|yx2n=f(x1)f(x2)n f (x1x2)=f (maxx1,x2)n=y|ymaxx1,x2n=y|yx1y|yx2=f (x1)f (x2)n所以,f是L1到L2的格同态。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(b)具有一,二,三个元素的格,分别同构于一、二,三个元素的链。四个元素的格必同构于图7.24(a)和(b)之一,五 个 元 素 的 格 必 同 构 于 图7.25(a),(b),(c),(d),(e)之一。 图 7.24 第7章 格与布尔代数

21、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.25第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定 义 7.24设 L,*, 和S,是两个格。定义一个代数系统LS,+如下:对任意a1,b1,na2,b2LS,有na1,b1。a2,b2=a1*a2,b1b2n a1,b1 + a2,b2 = a1a2,b1b2n我们称LS,*,+是格L,*,和S,的直接乘积或积代数。n第7章 格与布尔代数经营者提供商

22、品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例2n(a)图7.26给出了格1,2,4,D和1,3,D的积代数。这个积代数和格S12,D的图完全一样,只不过前者结点用a,b标记,后者结点用ab标记而已。n(b)记L=0,1,考虑格L,自身的积代数。这里是通常意义的“小于或等于”。这些积代数是nL2,2,L3,3Ln,n。一般地说,在格nLn,n中,任意元素a,b有以下形式:第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用

23、n a=a1,a2,ann b=b1,b2,bnn这里的ai,bi是0或1。n anba1b1a2b2anbnn也不难定义出Ln上的运算*和。我们称格nLn,n为0,1n重组的格。n图7.27给出了格L,L2,2和nL3,3的哈斯图,一般地说,格Ln,n的图是一个n维立方体。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.26第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.27

24、 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.3特殊的格n7.3.1分配格n任何格的元素都能满足分配不等式,但某些特殊格,其所有元素都能满足分配律。n定义7.31设L,*,是一个格,如果对于任何a,b,cL,有n a*(b c)=(a*b) (a*c) (1)n a (b*c)=(a b)*(a c)(2)n则称L,*,是一个分配格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定

25、理7.31分配格是模格。n证由于a (b*c)=(a b)*(a c),若ac,则a c=c,n代入上式得n a (b*c)=(a b)*c 证毕。n格可分为模格和非模格,本定理和以下例子说明,模格又可分为分配格和非分配格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例1n(a)如图7.31所示的格不是分配格,因为n a*(b c)=a*1=ana*b a*c=0 0=0n所以,a*(b c)(a*b)(a*c)但可以验证它是模格。n注意,格中某些元素满足分配律,但这不能保证是分配格。n

26、(b)图7.32所示的格不是分配格,因为它不是模格。图中n ba但b (c*a)(b c)*a第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图7.31 图7.32 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.32每个链都是分配格。n证 设 L, 是 一 个 链 ,且a,b,cL,考察下述可能情况:(1)ab或ac;(2)ab和ac。n对于情况(1)有n a*(b c)=a和(a

27、*b)(a*c)=an对于情况(2)有n a*(bc)=b c和(a* b)(a*c)=b cn这就证明了元素a,b,c满足分配律(1)。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.33分配格的子格是分配格;两个分配格的积代数是分配格。从子格和积代数的定义易知定理成立。n定理7.34设L,*,是一个分配格。对于任何元素a,b,cL有n(a*b=a*c)(a b=a c)b=cn证(a*b)c=(a*c)c=cn(a*b)c=(a c)*(b c)=(a b)*(b c)n=b (

28、a*c)=b (a*b)=bn证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.3.2有界格和有补格n设L,*,是一个格,格中每一对元素都有最小上界和最大下界。用归纳法不难证明,格中每一个有穷子集,也都有一个最小上界和一个最大下界。n设S=a1,a2,an是有穷子集,一般地说,S的最大下界和最小上界可表示为:第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.32如果在格L,中

29、存在 一 个 元 素 a,对 于 任 何 元 素 b,都 有ab(ba),则称a为格L,的全下界(全上界)。n定理7.35一个格L,的全下界(全上界)是唯一的。n证用反证法。如果有两个全下界a和b,a,bL且ab。因为a是全下界,所以ab。又因为b是全下界,所以ba。因此,a=b,得出矛盾。类似地,可证全上界的唯一性。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例2n(a)在格(S),中,S是全上界,是全下界。n(b)在图7.33所示的格中,a是全上界,h是全下界。n定义7.33如果一个

30、格中存在全下界和全上界,n则把它们称为格的界,并分别用0和1来表示。有0和1的格称为有界格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.33第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.36设L,是一个有界格,对任意元素aL,必有:n a 0=a a*1=a (3)n a 1=1a*0=0(4)n证由于0a1,所以上述各式显然成立。证毕。n式(3)说明,对,0是么元;对

31、,1是么元。式(4)说明,对,1是零元;对,0是零元。这两式还说明在有界格中,0和1互为对偶。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.34设L,*,0,1是一有界格。对于L中的一个元素a,如果存在元素bL,使n a*b=0a b=1n则称元素b是元素a的补元或补,记为a。n上述定义中,a和b是对称的,如果b是a的补元,则a也是b的补元。一般地说,一个元素aL,可以不存在补元;如果存在补元则补元也未必是唯一的。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费

32、者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例4观察图7.34中各格的元素的补元。n在(a)中a,b,c三个结点都无补元。n在(b)中a,b,c都互为补元,补元不唯一。n在(c)中,c的补元是a和b;a的补元是c;b的补元是c。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.34第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.37在有界

33、格L,*,0,1中,0和1互为补元,且是唯一的。n证因为0*1=0,01=1,所以0和1互为补元。若0的补元不唯一,另有补元c,则n0*c=0,0c=1n但0c=c,c=1,得出矛盾。类似地可证1的补元也是唯一的。证毕。n定理7.38在分配格中,如果元素aL有一个补元,则此补元是唯一的。n证假定b和c都是a的补元,则n a*b=0=a*ca b=1=a cn由定理7.34得b=c。证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.35如果在一个有界格中,每个元素都至少有一个补元素

34、,则称此格为有补格。图7.34的(b)和(c)都是有补格。n定义7.36如果一个格,既是有补格,又是分配格,则称此格为有补分配格,又称布尔格。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.3.3有补分配格的性质n定理7.39有补分配格L,*,中,任何元素aL的补元a是唯一的。n定理7.310 有补分配格L,*, 中,对于每一个aL,都有n(a)=an证由于a*a=0,a a=1和(a)*an=0,(a)a=1,而补元是唯一的,所以,(a)=a。证毕。第7章 格与布尔代数经营者提供商品或

35、者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.311有补分配格L,*,中,对于所有a,bL,有n(1)(a b)=a*bn(2)(a*b)=abn此即德摩根定律。n证(a b)(ab)=aabb*a*b=0n(a b)a*b=(a b a)(a b b)=1n所以,(a b)=a*b。n根据对偶性原理得(a*b)=a b。证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.312有补分配格L,*, 中,对

36、所有a,bL,有n aba*b=0ab=1n证由于aba*b=aa b=bn根据德摩根定律得nabab=bab=an因而ab a * b=0n ab=1第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n反之,a*b=0b (a*b)=bnb a=bnabnab=1a*(ab)=an(a*a)(a*b)=ana*b=an abn 证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用7.4布尔代

37、数n7.4.1布尔代数n上节已指出,布尔代数就是有补分配格,常记以B,*,0,1,现将其性质综合如下:n1.B,*,是一个格,满足n(L-1)a*a=an(L-1)a a=an(L-2)a*b=b*a第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(L-2)a b=b an(L-3)(a*b)*c=a*(b*c)n(L-3)(a b)c=a (b c)n(L-4)a*(a b)=an(L-4)a (a*b)=a第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔

38、偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n2.B,*,是一个分配格,满足n(D-1)a*(b c)=(a*b)(a*c)n(D-1)a (b*c)=(a b)*(a c)n(D-2)(a*b)(b*c)(c*a)=(a b)*(b c)*(c a)n(D-3)(a*b=a*c)(a b=a c)b=c第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n3.B,*,0,1是一个有界格,满足n(B-1)0a1n(B-2)a*0=0n(B-2)a 1=1n(B-3)a*1=

39、an(B-3)a 0=a第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n4.B,*,0,1是一个有补格,满足n(C-1)a*a=0n(C-1)a a=1n(C-2)0=1n(C-2)1=0n5.B,*,0,1是一个有补分配格,满足n(C-3)(a*b)=abn(C-3)(a b)=a*b第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n6.在集合B上存在偏序,满足n(P-1)a*b=glba

40、,bn(P-1)a b=luba,bn(P-2) ab a*b=a a b=b n(P-3) ab a*b=0 a b=1ban以上公式,不都是独立的,可以从其中选定一些作为基本公式,推出其它公式。也就是说,可以用这些基本公式定义布尔代数。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例1n(a)设B=0,1,B上的运算*,由下面的表定义:*0101000101010111xx0110 代数B,*, ,0,1能满足定义7.41的要求。所以它是布尔代数,它是二元素布尔代数。二元素布尔代数是图

41、为链的唯一布尔代数。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(b)设S是非空集合。(S)是它的幂集,n(S),-,S能满足定义7.41的要求,所以是布尔代数。如果S有n个元素,则(S)有2n个元素,该布尔代数的图形是n维立方体。图7.41给出了S=a,S=a,b,S=a,b,c时布尔代数的图形。若S是空集,则(S)仅有一个元素,于是=0=1,我们称它为退化了的布尔代数,我们不研究它。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加

42、赔偿的金额为消费者购买商品的价款或接受服务的费用 图 7.41 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(c)用S表示含有n个命题变元的命题公式集合。代数系统S,F,T是一布尔代数,其中,和分别是合取,析取和否定运算,F和T是永假式和永真式,并把互为等价的两个命题公式看成是相等的。对应于运算和,偏序关系是永真蕴含。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(d)设Bn是0和1

43、组成的n重组集合,记n a=a1,a2,anb=b1,b2,bnn0n=0,0,01n=1,1,1na,b为Bn中的任意元素,定义n a*b= a1b1,a2b2,anbnn a b=a1b1,a2b2,anbnn a= a1,a2,an第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.4.2子布尔代数n定义7.42设B,*,0,1是一个布尔代数,SB。如果S含有元素0和1,并且在运算*,和的作用下封闭,则称S,*, ,0,1是B,*, ,0,1的子布尔代数。n实际检测一个子集S是否是子布

44、尔代数,不需要按定义进行,只须该子集对运算集合*,或,封闭就可以了。因为n a b=(a*b),1=(a*a)和0=a*a第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.41子布尔代数是一个布尔代数。n证设S,*,0,1是B,*,0,1的子布尔代数。则0和1属于S;由于S对*,和是封闭的,所以,如果aS,则aS,于是定义7.41中的第3和4条显然在S中成立;又交换律和分配律是继承的,所以S,*,0,1是一个布尔代数。证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按

45、照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例2考察图7.42所示的布尔代数nB,*,0,1。n(a)S1=a,a,0,1,由于S1含有0和1,且对运算*、,封闭。所以,S1,*,0,1是B,*,0,1的子布尔代数。这个子布尔代数也可以说由元素a生成的。一般地说,B的任意非空子集都可以生成B,*,0,1的子布尔代数。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.42 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的

46、要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(b)S2=c,b,a,1,S2不包含特异元素0,所以不是B,*,0,1的子布尔代数。但若补运算是对1(作为全上界)和c(作为全下界)定义的,则S2,*,c,1是布尔代数。n(c)S3=0,b,a,1对运算不封闭,所以S3不能构成布尔代数,当然也不能成为子布尔代数。n(d)对任意布尔代数B,*,0,1子集0,1和B总能构成子布尔代数,这两种子布尔代数称为平凡的。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.

47、4.3布尔同态n定义7.43设A,*,0,1和B,-,是两个布尔代数。定义一个映射f:AB,如果在f的作用下能够保持布尔代数的所有运算,且常数相对应,亦即对于任何a,bA有:n f (a*b)=f (a)f(b)n f (a b)=f (a)f(b)n f (a)=f (a)n f (0)=n f (1)=n则称映射f:AB是一个布尔同态。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.4.4有限布尔代数的原子表示n本小节研究有限布尔代数的一个重要性质,就是任何有限布尔代数B,*,0,1

48、都同构于某一集合S的幂集代数(S),-,S。n我们探讨这一问题的思路是这样的:n第一步:介绍B中的特殊元素原子及其性质。n第二步:证明B中除0外的每一元素x,都可唯一地表示成原子的保联,即x=a1a2ak(ai是原子)n第三步:证明上述断言。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.44设a,b是一个格中的两个元素,如果ba且ba,即ba,并且在此格中再没有别的元素c,使得bc和ca,则称元素a覆盖元素b。n定义7.45设B,*,0,1是一布尔代数,aB,如果a复盖0,则称元素

49、a是该布尔代数的一个原子。n定 理 7.42元 素 a是 布 尔 代 数B,*,0,n1的原子,当且仅当a0时,对任意元素xB,有n x*a=a 或x*a=0n证必要性。因为x*aa,而a是原子,所以,x*a=a或x*a=0。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n充分性。若a0不是原子,则存在一元素xB,合ax0,于是有x*a=x,这与假设“a0时对任意xB有x*a=a或x*a=0”相矛盾。所以,a是原子。证毕n推论7.42 a是布尔代数B,*, ,0,1的原子,x是B的任意元素,

50、则或者ax,或者ax,但不能同时成立。n证由于n x*a=aax,x*a=0axn所以,根据定理7.42,如果a是原子,x是B的任意元素,有nax 或 axn若两者同时成立,则ax*x=0,这与a0矛盾。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.42及其推论说明:原子是这样的元素,它把B中的元素分为两类,第一类是与自己可比较的(包括自身),它小于等于这一类中的任一元素。第二类是与自己不可比较的或是0,它小于等于这一类中任一元素的补元。n为了加深对原子和定理7.42的认识,试考察

51、图7.43,(a)中,a1是原子;(b)中,a1和a2是原子;(c)中,a1,a2和a3是原子。在(a),(b)崐和(c)三图中,虚线都是表示原子a1将B的元素划分成两类。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.43 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.43设B,*,0,1是一个有限布尔代数,则对于每一个非零元素xB,至少存在一个原子a,使x*a=a(即a

52、x)。n证若x是原子,则x*x=x,此x就是所求的原子a。若x不是原子,因为x0,所以,从x下降到0有一条路径,又由于B是有限的,此路径所经过的结点是有限的,不妨设为n xa1a2ak0n则ak覆盖0,而x*ak=ak,此ak就是所求的原子a。证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.44如果元素a1和a2是布尔代数B,*,0,1中的两个原子,且a1*a20,则a1=a2。n证 由 定 理 7.42有 a1*a2=a2和a2*a1=a1,所以a1=a2。本定理的逆反是:若

53、a1a2,则a1*a2=0,它是关于原子的重要性质。下面进行第二步。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.45设B,*,0,1是有限布尔代数,x是B中任意非0元素,a1,a2,ak是满足aix的所有原子(i=1,2,k),则n x=a1a2akn证记a1a2ak=y,n因为aix(i=1,2,k)n所以,yx。如果能进一步证明xy,那么问题就解决了。由定理7.312知,只需证明x*y=0就可以了。为此,我们用反证法。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应

54、当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n设x*y0,于是必有一原子a,使ax*y,又因x*yx和x*yy,所以,由传递性得n ax 和ayn因为a是一原子,且满足ax,所以a必是a1,a2,ak中的一个,因此ay。但这与ay矛盾。故x*y=0,即xy。证毕。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.46定理7.45中的表示式n x=a1a2akn是唯一的。n证若另有一种表示式为n x=b1b2btn其中b1,b2,bt是B中

55、不同的原子。n第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n因为x是b1,b2,bt的最小上界,所以,bix(i=1,2,t)。n而 a1,a2,ak是 B中 满 足aix(i=1,2,k)的 所 有 原 子 。 所 以,b1,b2,bta1,a2,ak且tk。n如果tk,那么a1,a2,ak中必有一ai与b1,b2,bt全不相同。于是,由nai*(b1 b2 bt)=ai*(a1a2ak)n得0=ain于是得到矛盾。所以,只有t=k,b1,b2,bt就是a1,a2,ak。证毕。n现在进行

56、第三步。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.47设B,*,0,1是一个有限布尔代数,S是此代数中的所有原子的集合,则B,*,0,1同构于幂集代数(S),-,S。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n推论7.47(a)B,*,0,1与 (S), -, ,S 同 构,|(S)|=2|s|,所以,|B|=2|s|,故任一有限布尔代数载体的基数是2的幂。n(b)任一有

57、限布尔代数和它的原子集合S构成的幂集集合代数(S),-,S同构,但后者又与任一基数相同的幂集集合代数同构。故具有相同载体基数的有限布尔代数都同构。n注意,定理7.47对无限布尔代数并不成立。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n命题演算(集合论)中的极小项就是由n元命题公式构成的布尔代数的原子。除0外,每一公式都可化成极小项的析取(并)是大家已知的事实。n此外,还可用布尔代数的反原子的保交来表示布尔代数的元素。反原子是被最大元素1所复盖的元素。事实上,一个反原子是一个原子的补,所以

58、称为反原子。根据对偶性原理,若把和,0和1,和,原子和反原子互换,重复上面的全部讨论,就可得出相应的结论。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用图 7.44第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.4.5布尔代数的积代数n定义7.46设U=A,*,01,11和nV=B,02,12是两个布尔代数。定义一个布尔代数nW=AB,+,-,03,13如下,其中“”“.”“-”都是求

59、补运算。对于任何a1,b1,a2,b2AB,第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用na1,b1a2,b2=a1a2,b1b2na1,b1+a2,b2=a1a2,b1b2na1,b1=a1,b1n则称W是U和V的积代数。记为W=UV。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.48布尔代数的积代数是一布尔代数。n证因为交换律,分配律,公式(B-3)(B-3)(C-1)和(

60、C-1)均成立,符合定义7.41,所以,布尔代数的积代数是一布尔代数。证毕。n我们用An=Bn,*,0,1表示具有n个元素的布尔代数。由推n论7.47知,这里的n必定是2的幂。因此,最小的布尔代数是nA2=B2,*,0,1n这里B2=0,1,运算表如例1(a)所定义。其次是nA4=B4,*,0,1n设B4=0,a,b,1,其运算表如下表所示:第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 表 7.4-1第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到

61、的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用表 7.42 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定理7.49布尔代数和同构,且每一有限布尔代数都同构于某一个。n证和基数相同,所以同构。任一布尔代数的基数为2n,所以必与同构。证毕。n本定理说明,只要对研究清楚了,一切有限布尔代数也就清楚了。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例4n(a)A4与 A22同

62、 构 ,对 比 运 算 表7.41和运算表7.42即知。n(b)设E=a1,a2,an,则布尔代数n(E),-,E和An2同构。同构f 可以这样作出:n f:(E)Bn2n f (S)=1,2,n当 时 当 时 这里 例如,n=4时, f (a1,a3,a4)=1,0,1,1第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n7.4.6布尔函数nB,*,0,1是一个布尔代数,现在考虑一个从Bn到B的函数。n设B=0,1,表7.43给出了一个从B3到B的函数。n设B=0,a,b,1,表7.44给出

63、了一个从B2到B的函数。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 表 7.43 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用表 7.44 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.47设B,*,0,1是一个布尔代数,取值于B中元素的变元称为布尔变元;B中的元素称为布

64、尔常元。n定义7.48设B,*,0,1是一个布尔代数,这个布尔代数上的布尔表达式定义如下:n(1)单个布尔常元是一个布尔表达式;单个布尔变元是一个布尔表达式。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(2)如果e1和e2是布尔表达式,则(e1),(e1e2),(e1*e2)也是布尔表达式。n(3)除了有限次应用条款1和2形成的表达式外,没有其它字符串是布尔表达式。布尔表达式一般用f,g表示,或更明确地表示成f (x1,x2,xn),n称 为 n元 布 尔 表 达 式 ,其 中x1,x2

65、,xn是式中可能含有的布尔变元。布尔表达式中的某些圆括号可以省略,约定类似于命题公式。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例5设0,a,b,1,*,0,1是布尔代数,则nf1=an f 2=0*xn f 3=(1*x1)x2n f 4=(a b)(x1x2)*(x1*x2)n都是这个布尔代数上的布尔表达式。n布尔表达式中的符号,和,就是相应布尔代数中,和三种运算,它们满足布尔代数的所有公式,可以按照这些公式进行计算。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照

66、消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.49布尔代数B,*,0,1上的布尔表达式f (x1,x2,xn)的值指的是:将B的元素作为变元xi(i=1,2,n)的值而代入表达式以后,计算出来的表达式的值。n例6n(a)取x1=a,x2=b,则例5中的f3的值是n f3=(1*a)b=a b=1n(b)设 布 尔 代 数 0,1 ,*, ,0,1上的表达式nf (x1,x2,x3)=(x1*x2)(x1x2)(x2x3),则n f (1,0,1)=(0*1)(01)*(01)=0*1*1=0第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的

67、，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.410布尔代数B,*, ,0,1 上 两 个 n元 布 尔 表 达 式f1(x1,x2,xn)和 f2(x1,x2,xn),如 果对n个变元的任意指派,f1和f2的值均相等,则称这两个布尔表达式是等价的或相等的。n记作f1(x1,x2,xn)=f2(x1,x2,xn)。n在实践上,如果能有限次应用布尔代数公式,将一个布尔表达式化成另一个表达式,就可以判定这两个布尔表达式是等价的。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额

68、为消费者购买商品的价款或接受服务的费用n定义7.410给出的等价关系将n元布尔代数表达式集合划分成等价类,处于同一个等价类中的表达式都相互等价。可以证明等价类数目是有限的。为此,我们考察以下定义。n定义7.411给定n个布尔变元x1,x2,xn,表达式n称为极小项。这里 表示xi或xi两者之一。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.412nn型式的布尔表达式称为主析取范式。n这 里 mi是 极 小 项 ,i是 布 尔 常 元 。(i=0,1,2,2n-1)。n因为i有|B|

69、种取法,故不同的主析取范式有个。特别,B=0,1时有个。n任何一个n元布尔表达式都唯一地等价于一个主析取范式。把一个n元布尔表达式化成等价的主析取范式,主要应用德摩根定律等,其方法与“数理逻辑”和“数字逻辑”中化成主析取范式的方法完全一致。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n2n个极小项最多只能造出个不同的主析取范式,所以,一个n元布尔表达式必等价于这个主析取范式之一。平行地可讨论极大项和合取范式。n定义7.413给定n个布尔变元x1,x2,xn。表达式称为极大项。这里 表示xi

70、或xi两者之一。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n显然,有2n个不同的极大项。分别记为M0,M1,M2,足标是二进制数a1,a2,an的十进制表示。当 时 当 时 (i=1,2,n) 注意:足标规定与极小项不同。极大项满足以下性质:时 第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.414n型式的布尔表达式称为主合取范式。这 里 Mi是 极 大 项 ,i是 布 尔 常

71、 元,(i=0,1,2,2n-1)。n任何一个n元布尔表达式都唯一地等价于一个主合取范式。2n个极大项最多只能造出个不同的主合取范式。所以,一个n元布尔表达式必等价于这个主合取范式之一。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.413 给定n个布尔变元x1,x2,xn。表达式 称为极大项。这里 表示xi或xi两者之一。 显然,有2n个不同的极大项。分别记为 M0,M1,M2, ,足标是二进制数a1,a2,an的十进制表示。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，

72、应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n极大项满足以下性质:时第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.414n(0M0)*(1M1)*( )型式的布尔表达式称为主合取范式。这里Mi是极大项,i是布尔常元,(i=0,1,2,2n-1)。n任何一个n元布尔表达式都唯一地等价于一个主合取范式。2n个极大项最多只能造出个不同的主合取范式。所以,一个n元布尔表达式必等价于这 个主合取范式之一。第7章 格与布尔代数经营者提供商品或者

73、服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例7(a)将布尔代数n上的布尔表达式n化成主析取范式。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n(b)将布尔代数0,1,*,0,1 上 的 布 尔 表 达 式 f (x1,x2,x3)=x1x2x3化成主合取范式。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n一个n元布

74、尔表达式,对n个变元的每一指派,都可得到相应的表达式的值,这值属于B。所以,每一布尔表达式都代表一个函数。但n个变元的主析取范式(或主合取范式)最多只有个,所以,至多只能代表个不同的函数。从Bn到B的函数共有个。现分情况讨论:n(1)B=0,1时,从Bn到B的函数共有个,主析取范式也有个,恰好每一主范式代表一个函数。所以,在B=0,1时,每一函数均可用布尔表达式表示。n第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n例如,表7.43所表示的函数可表达为 (2) B0,1时,例如B=0,a,b

75、,1时,从Bn到B的函数共有 个,但主析取范式仍只有 个,所以,不是每一函数都可用布尔表达式表示。第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n定义7.415设B,*,0,1是一个布尔代数,一个从Bn到B的函数,如果能够用该布尔代数上的n元布尔表达式表示,那么这个函数就称为布尔函数。n例如,表7.44所示的函数不是布尔函数。若不然,不妨设这里Cij取值于0,a,b,1,根据表的第一行 f(0,0)=C22*1*1=C22=1第7章 格与布尔代数经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用n根据表的第二行 不管C21取什么值,上式都不可能成立。所以,布尔 表达式表示不了这个函数,它不是布尔函数。