离散数学及其应用-08 格与布尔代数

8.1格的概念与性质8.2布尔代数的概念与性质第八章

格与布尔代数类似于环和域,格是另外一种具有两个二元运算的特殊代数系统。关于它的定义有两种形式,一种是从代数系统角度的定义,另一种是从偏序集的角度进行定义。格的相关定义设L是非空集合,*和·是L上的两个二元运算,如果*和·满足交换律、结合律和吸收律,则称<L,*,·>构成格(lattice),也称为代数格。8.1格的概念与性质设在自然数集N上定义两个运算*和·,其中x*y=max(x,y),x·y=min(x,y),试证明<N,*,·>构成了一个代数格。证明

(1)证明*和·满足交换律。∀x,y∈Nx*y=max(x,y)=max(y,x)=y*xx·y=min(x,y)=min(y,x)=y·x所以*和·满足交换律。8.1格的概念与性质设在自然数集N上定义两个运算*和·,其中x*y=max(x,y),x·y=min(x,y),试证明<N,*,·>构成了一个代数格。证明（续）

(2)证明*和·满足结合律。∀x,y,z∈N(x*y)*z=max(max(x,y),z)=max(x,max(y,z))=x*(y*z)(x·y)·z=min(min(x,y),z)=min(x,min(y,z))=x·(y·z)所以*和·满足结合律。8.1格的概念与性质设在自然数集N上定义两个运算*和·,其中x*y=max(x,y),x·y=min(x,y),试证明<N,*,·>构成了一个代数格。证明（续）

(3)证明*和·满足吸收律。∀x,y∈Nx*(x·y)=max(x,min(x,y))=xx·(x*y)=min(x,max(x,y))=x所以*和·满足吸收律。综上,<N,*,·>是一个代数格。证毕。8.1格的概念与性质格的相关定义设<A,≼>是偏序集,如果∀a,b∈A,{a,b}都有上确界和下确界,则称<A,≼>构成格,也称为偏序格。由于上确界和下确界的唯一性,可以把求{a,b}的上确界和下确界看成a与b的二元运算∨和∧,即a与b上确界和下确界分别用a∨b,a∧b表示。8.1格的概念与性质判断下列哪些偏序集是格,并说明理由。(1)<P(A),⊆>,其中P(A)是集合A上的幂集合,⊆为包含关系。(2)<N,≽>,其中N是自然数集,≽为大于或等于关系。(3)<S,D>,其中S={2,3,6,8,12},D为整除关系。解

(1)是格。因为∀a,b∈P(B),都有a∨b=a∪b,a∧b=a∩b,又∪和∩运算在P(B)上是封闭的,即a∪b,a∩b∈P(B)。(2)是格。因为∀x,y∈N,x∨y=max(x,y),x∧y=min(x,y),其运算结果都为自然数。(3)不是格。因为在集合S中,不存在一个数既能被6整除,又能被8整除,即{6,8}没有上确界;同理,在集合S中没有一个数既能整除2,又能整除3,即{2,3}没有下确界。8.1格的概念与性质格具有以下性质。定理设<L,≼>是格,则运算∨和∧满足交换律、结合律、幂等律和吸收律,即(1)交换律:∀a,b∈L有a∨b=b∨a,a∧b=b∧a。(2)结合律:∀a,b,c∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)。(3)幂等律:∀a∈L有a∨a=a,a∧a=a。(4)吸收律:∀a,b∈L有a∨(a∧b)=a,a∧(a∨b)=a。8.1格的概念与性质证明

(1)a∨b是{a,b}的上确界,b∨a是{b,a}的上确界。由于{a,b}={b,a},所以a∨b=b∨a,同理可得,a∧b=b∧a。(2)由上确界的定义有:(a∨b)∨c≽a∨b≽a (8.1)(a∨b)∨c≽a∨b≽b (8.2)(a∨b)∨c≽c (8.3)由式(8.2)和(8.3)得(a∨b)∨c≽b∨c (8.4)由式(8.1)和(8.4)得(a∨b)∨c≽a∨(b∨c) (8.5)同理可证(a∨b)∨c≼a∨(b∨c) (8.6)由式(8.5)和(8.6)得(a∨b)∨c=a∨(b∨c)。同理可证(a∧b)∧c=a∧(b∧c)8.1格的概念与性质证明（续）(3)显然a≼a∨a,又由a≼a可得a∨a≼a;根据反对称性有a∨a=a。同理可证,a∧a=a得证。(4)显然a∨(a∧b)≽a (8.7)由a≼a,a∧b≼a可得a∨(a∧b)≼a (8.8)由式(8.7)和(8.8)得a∨(a∧b)=a。同理可证a∧(a∨b)=a。证毕。这个定理说明,格的两个定义本质上是相同的。8.1格的概念与性质接下来讨论几种特殊的格。格的相关定义如果在格<L,≼>中,存在一个元素a∈L,使得∀x∈L均有a≼x(x≼a),则称a为格的全下界(全上界)(相当于偏序集中的最小元、最大元),且记全下界为0,全上界为1。8.1格的概念与性质全下界(全上界)有如下性质。定理全下(上)界如果存在则必唯一。证明

设1和1'均是全上界,则因为1是全上界,所以1'≼1;又因为1'是全上界,所以1≼1'。由≼的反对称性,所以1=1'。同理可证全下界唯一。证毕。在格<P(A),∪,∩>中,A是全上界,⌀是全下界。8.1格的概念与性质格的相关定义如果<L,∧,∨>中既有全上界1,又有全下界0。称0,1为格L的界(bound),并称格L为有界格(boundedlattice)。设<L,∧,∨>是格,如果∀a,b,c∈L,都有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称<L,∧,∨>为分配格(distributivelattice)。<P(A),∪,∩>是分配格,<Z,max,min>也是分配格。8.1格的概念与性质下面我们讨论补格。格的相关定义设<L,∧,∨>是有界格,a为L中任意元素,如果存在元素b∈L使a∨b=1,a∧b=0,则称b是a的补元或补(complements)。补元有下列性质:(1)补元是相互的,即若b是a的补,那么a也是b的补。(2)并非有界格中每个元素都有补元,而有补元也不一定唯一。(3)全下界0与全上界1互为补元且唯一。8.1格的概念与性质格的相关定义如果有界格<L,∧,∨>中每个元素都至少有一个补元,则称L为有补格(complementedlattice)。定理设<L,∧,∨>是有补分配格,若L中某个元素a存在补元,则存在唯一的补元。证明假设a有两个补元b和c,则有a∨b=1,a∧b=0,a∨c=1,a∧c=0。8.1格的概念与性质定理设<L,∧,∨>是有补分配格,若L中某个元素a存在补元,则存在唯一的补元。证明（续）故a∨b=a∨c,a∧b=a∧c。由于L是分配格,b=b∨(b∧a)=b∨(a∧c)=(a∨b)∧(b∨c)=(a∨c)∧(b∨c)=(a∧b)∨c=(a∧c)∨c=c。由此可见,假设不成立。命题得证。证毕。8.1格的概念与性质8.1格的概念与性质8.2布尔代数的概念与性质第八章

格与布尔代数布尔代数相关定义设B是至少有两个元素的有补分配格,则称B是布尔代数(Booleanalgebra)。布尔代数通常记为<B,∨,∧,',0,1>,其中“'”为求补运算。由前面的讨论可知,布尔代数<B,∨,∧,',0,1>具有如下性质:(1)交换律:∀a,b∈B,a∨b=b∨a,a∧b=b∧a。(2)结合律:∀a,b,c∈B,(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)。8.2布尔代数的概念与性质（续）(3)幂等律:∀a∈B,a∨a=a,a∧a=a。(4)吸收律:∀a,b∈B,a∨(a∧b)=a,a∧(a∨b)=a。(5)分配律:∀a,b,c∈B,a∨(b∧c)=(a∨b)∧(a∨c),a∧(b∨c)=(a∧b)∨(a∧c)。(6)零一律:∀a∈B,a∨1=1,a∧0=0。(7)同一律:∀a∈B,a∨0=a,a∧1=a。(8)互补律:∀a∈B,a∨a'=1,a∧a'=0。(9)否定律:∀a∈B,(a')'=a。(10)德·摩根律:∀a,b∈B,(a∨b)'=a'∧b',(a∧b)'=a'∨b'。8.2布尔代数的概念与性质布尔代数这10个运算律并不是独立的,可以由交换律、分配律、同一律和互补律推出其他运算律。由此也可以从代数系统的角度给出布尔代数的定义。布尔代数相关定义设<B,*,·>是一个格代数系统,*和·是B上的两个代数运算,如果*和·满足交换律、分配律、同一律和互补律,则称<B,*,·>为布尔代数。8.2布尔代数的概念与性质设B为任意集合,证明<P(B),∪,∩,~,