离散数学课件 格与布尔代数2

第十一章格与布尔代数,布尔代数是计算机逻辑设计的基础，它是由格引出的，格又是从偏序集引出的。所以我们先回顾一下偏序集。是偏序集:是A上自反,反对称和传递关系(偏序).偏序集中的元素间的次序可以通过它的Hasse图反映出来.例如A=1,2,3,6,12,24,36,是A上的整除关系其Hasse图如图所示另设有集合BA,且B1.B的极小元与极大元y是B的极小元yBx(xBxy)y是B的极大元yBx(xByx)例如2,3,6的极小元:2,3极大元:6,2.B的最小元与最大元y是B的最小元yBx(xByx)y是B的最大元yBx(xBxy)2,3,6的最小元:无最大元:6B如果有最小元(最大元),则是唯一的。3.B的下界与上界y是B的下界yAx(xByx)y是B的上界yAx(xBxy)2,3,6的下界:1上界:6,12,24,364.B的最大下界(下确界)与最小上界(上确界)y是B的最大下界(下确界)：B的所有下界x,有xy。y是B的最小上界(上确界)：B的所有上界x,有yx。2,3,6下确界:1上确界:6(B若有下(上)确界，则唯一),11-1格(Lattice),一.基本概念1.格的定义是偏序集，如果任何a,bA,使得a,b都有最大下界和最小上界，则称是格。右图的三个偏序集，不是格，因为24,36无最小上界。是格。,这三个偏序集，也都不是格，第一个与第三个是同构的。因为d和e无下界，也无最小上界；b,c虽有下界，但无最大下界。2,3无最大下界，4,5无最小上界。2.平凡格：所有全序都是格，称之为平凡格。因为全序中任何两个元素x,y，要么xy,要么yx。如果xy，则x,y的最大下界为x，最小上界为y。如果yx，则x,y的最大下界为y，最小上界为x。即这x,y的最大下界为较小元素，最小上界为较大元素.,3.由格诱导的代数系统设是格,在A上定义二元运算和为:a,bAab=LUBa,b,a,b的最小上界.LeastUpperBoundab=GLBa,b,a,b的最大下界.GreatestLowerBound称是由格诱导的代数系统.(-并,-交)例如右边的格中ab=b,ab=a,bc=e4.子格：设是格,是由诱导的代数系统。B是A的非空子集，如果和在B上封闭，则称是的子格。是的子格。而不是.bc=dB(运算规则要从格中找),二.格的对偶原理设是格，的逆关系记作，也是偏序关系。也是格，的Hasse图是将的Hasse图颠倒180即可。格的对偶原理：设P是对任意格都为真的命题，如果将P中的换成，换成，换成，就得到命题P,称P为P的对偶命题，则P对任意格也是为真的命题。例如：P:abaa,b的最大下界a由对偶原理P:abaa,b的最小上界a三.格的性质是由格诱导的代数系统。a,b,c,dA1.aab,bab,aba,abb此性质由运算和的定义直接得证。,2.如果ab，cd，则acbd，acbd。证明：如果ab，又bbd,由传递性得abd,类似由cd，dbd，由传递性得cbd,这说明bd是a,c的一个上界而ac是a,c的最小上界所以acbd。类似可证acbd。推论：在一个格中，任何a,b,cA，如果bc，则abac，abac。此性质称为格的保序性。3.和都满足交换律。即ab=ba，ab=ba。此性质由运算和的定义直接得证。,4.和都满足结合律。即(ab)c=a(bc)，(ab)c=a(bc)。证明：先证明(ab)ca(bc)aa(bc),且bbca(bc)(ab)a(bc)cbca(bc)(ab)ca(bc)同理可证a(bc)(ab)c最后由反对称性得(ab)c=a(bc)类似可证(ab)c=a(bc)。5.和都满足幂等律。即aa=a,aa=a证明：由性质1得aaa(再证aaa)又自反得aa,这说明a是a的上界,而aa是a的最小上界,所以aaa。最后由反对称性得aa=a。由对偶原理得aa=a,6.和都满足吸收律。即a(ab)=a，a(ab)=a。证明：显然有aa(ab)再证a(ab)aaaabaa(ab)a最后由反对称得a(ab)=a，类似可证a(ab)=a。,7.和不满足分配律。但有分配不等式：a(bc)(ab)(ac)，(ab)(ac)a(bc)。我们先看右图的例子：d(be)=dc=d(db)(de)=ae=e而de即d(be)(db)(de)证明：aabaaca(ab)(ac)bcbab,bccacbc(ab)(ac)于是有a(bc)(ab)(ac)由对偶原理得a(bc)(ab)(ac)。即(ab)(ac)a(bc)。,8.abab=aab=b证明：先证明abab=a先证abab=a由ab，又aa所以aab又由ab的定义有aba由反对称得ab=a再证ab=aab由ab=a则a=abb。综上得abab=b下面证明abab=b先证abab=b由ab，又bb所以abb又因为bab由反对称得ab=b再证ab=bab由ab=b因aab所以ab。综上得abab=b,四.格的同态与同构,1.定义：设和是两个格，由它们诱导的代数系统分别是和如果存在映射f:A1A2使得对任何a,bA1,有f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)则称f是从到的格同态。也称是的格同态像。如果f是双射的,就称f是到的格同构,也称格和同构。,例如,A=1,2,3,6,是A上整除关系。,E=a,b它们诱导的代数系统分别是和其中和分别是求两个数的最小公倍数和最大公约数.f(23)=f(6)=a,bf(2)f(3)=ab=a,bf(23)=f(1)=f(2)f(3)=ab=f(26)=f(6)=a,bf(2)f(6)=aa,b=a,bf(26)=f(2)=af(2)f(6)=aa,b=a可见它们同构。格同构，它们的哈斯图的形状一定相同。,具有四个素的格分别同构于下面两种格形式之一：具有五个素的格分别同构于下面五种格形式之一：,11-2几个特殊格,一.分配格前面我们介绍一般的格，和只满足分配不等式。a(bc)(ab)(ac)，(ab)(ac)a(bc)。下面介绍的是满足分配律的格-分配格。1.定义：是由格诱导的代数系统。如果对a,b,cA，有a(bc)=(ab)(ac)，a(bc)=(ab)(ac)则称是分配格。,2.二个重要的五元素非分配格2(35)=230=2(23)(25)=11=1c(bd)=ca=c(cb)(cd)=ed=d可见它们都不是分配格。3.分配格的判定：一个格是分配格的充分且必要条件是在该格中没有任何子格与上述两个五元素非分配格之一同构。用此方法判定下面两个格是不是分配格?,4.分配格的性质1.定理7-2.1.在格中，如果对可分配，则对也可分配.反之亦然。证明：设是由格诱导的代数系统。且对可分配。任取a,b,cA，a(bc)=(ab)(ac)而(ab)(ac)=(ab)a)(ab)c)分配=a(ab)c)=a(ac)(bc)吸收、分配=(a(ac)(bc)结合=a(bc)吸收同理可证:如果对可分配，则对也可分配.2.定理11-2.2.所有链均为分配格。证明：显然任何链都不会含有与五元素非分配格之一同构的子格，所以链必是分配格。,3.定理11-2.3.设是分配格，对任何a,b,cA,如果有ab=ac及ab=ac则必有b=c.证明：任取a,b,cA,设有ab=ac及ab=acb=b(ab)(吸收律)=b(ac)(代换)=(ba)(bc)(分配)=(ab)(bc)(交换)=(ac)(bc)(代换)=(ab)c(分配)=(ac)c(代换)=c(吸收律),二.有界格,1.格的全上界与全下界1).全上界:设是格，如果存在元素aA对任何xA,xa,则称a是格的全上界,记作1。(即是A的最大元)定理7-2.4一个格如果有全上界，则是唯一的。(我们已证明过，最大元如果有，则是唯一的)2).全下界:设是格，如果存在元素aA对任何xA,ax,则称a是格的全下界,记作0。(即是A的最小元)定理11-2.5一个格如果有全下界，则是唯一的。从格的图形看：全上界1，就是图的最上边元素(只一个)，全下界0，就是图的最下边元素(只一个)。,2.有界格定义：如果一个格存在全上界1与全下界0，则称此格为有界格。设是有界格，则对任何aA,有因为a1,所以a1=aa1=10a所以a0=0a0=a是否所有格都是有界格？所有有限个元素的格都是有界格而无限个元素的格可能是无界格。例如就是既无全上界与全下界。,三.有补格,回顾：集合的补集，若AB=EAB=则A=B，B=A如E=a,bE=Ea=b,b=a1.元素的补元设是个有界格，aA,如果存在bA,使得ab=1和ab=0则称a与b互为补元。例：右边的格中a的补元：c,eb的补元：无c的补元：a,dd的补元：ce的补元：a0的补元：11的补元：0,2.有补格的定义一个有界格中,如果每个元素都有补元,则称之为有补格.上述有界格中，哪些是有补格？上述有补格中，有些元素的补元不唯一，如(2)中的b,那么什么样的格中元素的补元唯一呢？-有界分配格。请看下面定理：,定理112.6在有界分配格中，如果元素有补元，则补元是唯一的。证明：设是有界分配格，任取aA,假设a有两个补元b和c，则ab=0,ab=1及ac=0,ac=1于是有，ab=acab=ac由分配格的定理112.3得b=ca的补元是唯一的。四.布尔格如果一个格既是分配格又是有补格，则称之为布尔格。布尔格中每个元素都有唯一补元，元素a的补元记作显然是布尔格。,113布尔代数BooleanAlgebra,一.定义由布尔格诱导的代数系统称之为布尔代数。其中是取补元运算。如果B是有限集合，则称它是有限布尔代数。例如：令BF,T，表示合取，析取，否定,就是个布尔代数。如上图所示。也是个布尔代数。如下图所示。,二.布尔代数的性质,设布尔代数,任意x,y,zB,有交换律xy=yxxy=yx结合律x(yz)=(xy)zx(yz)=(xy)z幂等律xx=xxx=x吸收律x(xy)=xx(xy)=x分配律x(yz)=(xy)(xz)x(yz)=(xy)(xz)同一律x0=xx1=x零律x1=1x0=0互补律对合律底摩根定律,上述性质都可以由格，分配格,有界格，布尔格得到。下面只证明底摩根定律。所以类似可证另一个。,三.布尔代数的同构1.定义：令和是两个布尔代数，如果存在映射f:B1B2,对任何a,bB1,有f(a1b)=f(a)2f(b)f(a1b)=f(a)2f(b)则称f是到的同态映射。若f是双射,则称f是到的同构映射。与格同构比较,多了一个关于补运算的同构关系等式.为了引出有限布尔代数的Stone的定理，下面介绍原子的概念。,2.原子定义1:设是布尔代数,元素aB,a0,若对任何元素xB,有xa=a,或xa=0,则称a是原子。定义2:是布尔格,在的哈斯图中称盖住全下界0的元素为原子。例如：,定理11-3.8(Stone定理)设是有限布尔代数，M是B中所有原子构成