《离散数学第8章节格与布尔代数幻灯片》由会员分享，可在线阅读，更多相关《离散数学第8章节格与布尔代数幻灯片（54页珍藏版）》请在金锄头文库上搜索。
1、第8章 格与布尔代数,8.1 格 8.2 布尔代数,返回总目录,第8章 格与布尔代数,8.1格 8.1.1格的概念和性质 定义8.1.1 设X,是偏序集，如果x,yX，集合x,y都有最小上界和最大下界，则称X,是格。 【例8.1】设S121,2,3,4,6,12是12的因子构成的集合。其上的整除关系R=x,y| xS12yS12x整除y，R是S12上的偏序关系，S12,R是偏序集。写出S12上的盖住关系COV S12，画出哈斯图，验证偏序集S12,R是格。 解：S12上的盖住关系 COV S121,2,1,3,2,4,2,6,3,6, 4,12,6,12， 哈斯图如图8.1所示。从哈斯图中可看
2、出，集合S12的任意两个元素都有最小上界和最大下界，故偏序集S12,R是格。,【例8.2】图8.2中给出了一些偏序集的哈斯图，判断它们是否构成格。 解：它们都不是格。在(a)中，1,2没有下界，因而没有最大下界。在(b)中，2,4虽有两个上界，但没有最小上界。在(c)中，1,3没有下界，因而没有最大下界。在(d)中，2,3虽有三个上界，但没有最小上界。,设X,是格，x,yX，今后用xy表示集合x,y的最小上界，二元运算称为并运算；用xy表示集合x,y的最大下界，二元运算称为交运算。 定义8.1.2 设X,是格，是X上的并运算，是X上的交运算。则称X,是格X,导出的代数系统。 在例4.28中，根
3、据图4.14，集合a,b的最小上界为a,b，即ab=a,b=ab；它的最大下界为，即ab=ab。这个结果可以推广到一般情况。x,yP (A)，xy=xy，xy=xy。这样，格P (A),R导出的代数系统P (A),实际就是代数系统P (A),，所以，二元运算和的运算表如表8.1和表8.2所示。 在例8.1中，根据图8.1，集合4,6的最小上界为12，即46=12=4和6的最小公倍数；它的最大下界为2，即46=2=4和6的最大公约数。同样，这个结果也可以推广到一般情况。即在格S12,R导出的代数系统S12,中，二元运算是求最小公倍数；二元运算是求最大公约数。,下面介绍格的对偶原理。 设X,是偏序
4、集，在X上定义二元关系 =a,b|b,a 可以证明X,也是偏序集。 定义8.1.3 设f是含有格中元素以及符号=,和的命题。将f中的替换成，替换成，替换成，替换成，得到一个新命题，所得的命题叫做f的对偶命题，记为f *。 例如，在格中，f为a(bc)a，则f的对偶命题f *为 a(bc)a 命题f和它的对偶命题f *遵循下列的规则，这规则叫做格的对偶原理。 设f是含有格中元素以及符号=,和的命题。 若f对一切格为真，则f的对偶命题f *也对一切格为真。 格的许多性质都是互为对偶命题的。有了格的对偶原理，在证明格的性质时，只需证明其中的一个就可以了。,定理8.1.1 设X,是格，X,是格X,导出
5、的代数系统。则a,b,cX有 ab=ba， ab=ba (交换律) (ab)c=a(bc) (ab)c=a(bc) (结合律) aa= a， aa= a (幂等律) a(ab)=a a(ab)=a (吸收律) 证明：a,bX，a,b=b,a，所以它们的最小上界相等。即ab=ba，同理可证ab=ba a和b的最大下界一定是a、b的下界，即aba，同理，(ab)cab，所以，(ab)caba 同理有 (ab)cabb 和 (ab)cc,由以上3式得 (ab)cbc和(ab)ca(bc) 类似地可证 a(bc)(ab)c 根据偏序关系的反对称性有(ab)c= a(bc) 由对偶原理得 (ab)c=
6、a(bc) 显然aaa，又由的自反性得aa，从而推出aaa，根据偏序关系的反对称性有aa=a 由对偶原理得aa=a 显然 aa(ab)， 又由aa，aba得a(ab)a，从而得 a(ab)=a。 由对偶原理得a(ab)=a,定理8.1.2 设X,是代数系统，其中,都是二元运算。如果和满足吸收律，则和满足幂等律。 证明：aa=a(a(ab)=a，同理可证aa=a 定理8.1.3 设X,是代数系统，其中,都是二元运算，满足交换律、结合律和吸收律，则可适当定义X的偏序关系，使X,构成一个格。 证明：定义X上的一个二元关系 =a,b|a,bX且ab=a 证明是X上的偏序关系。 由定理8.1.2知满足幂
7、等律，即aa=a，所以aa。故是自反的。 设ab且ba，则ab=a且ba=b，于是a=ab=ba =b。所以是反对称的。 设ab且bc，则ab=a且bc=b，于是ac=(ab)c =a(bc)=ab=a，即ac，故是传递的。 这就证明了是X上的偏序关系。,证明a,bX，ab是集合a,b的最大下界。因为 (ab)a=ab和(ab)b=ab 所以aba且abb，即ab是a,b的下界。 下证ab是a,b的最大下界。 设c是a,b的任一下界，即ca，cb，那么有 ca=c，cb=c 而 c(ab)=(ca)b=cb=c 所以 cab，即ab是a,b的最大下界。 证明ab=a的充分必要条件是ab= b
8、设ab=a，由吸收率可得 ab=(ab)b=b(ba)=b，即ab= b 设ab=b，由吸收率可得 ab=a(ab)=a，即ab=a, 证明a,bX，ab是集合a,b的最小上界。 根据，偏序关系可以等价的定义为： =a,b|a,bX且ab=b， 用这个定义和类似于的方法可以证明ab是集合a,b的最小上界。 因此，X,构成一个格。 根据定理8.1.3，可以给出格的另一个等价定义。 定义8.1.4 设X,*,是代数系统，其中*和都是二元运算，如果*和在X上封闭且满足交换律、结合律和吸收律，则称X,*,为格。 根据定义8.1.4和定理8.1.1，格X,导出的代数系统X,是格，以后不再区分偏序集定义的
9、格和代数系统定义的格，统称为格。,定理8.1.4 设X,是格，是X上的并运算，是X上的交运算。则a,bX有 ab当且仅当ab=a ab当且仅当ab=b 证明： 设ab，下证ab=a 由aa且ab知a是集合a,b的下界，故有aab；另一方面，由于ab是a,b的最大下界，所以是a,b的下界，即aba。根据偏序关系的反对称性得ab=a 设ab=a，下证ab a=abb，即ab 可类似进行证明。,定理8.1.5 设X,是格，是X上的并运算，是X上的交运算。a,b,c,dX，若ab且cd，则acbd， acbd 证明： abbd ，cdbd，因此acbd 类似的可以证明acbd 定理8.1.6 设X,是
10、格，是X上的并运算，是X上的交运算。则a,b,cX有 a(bc) (ab)(ac) (ab)(ac) a(bc) 证明： 根据定理8.1.5，由aa和bcb得 a(bc)ab 又由aa且bcc得 a(bc)ac 从而得到 a(bc)(ab)(ac) 利用对偶原理，即得。 一般地说，格中的和并不满足分配律。,8.1.2子格和格的同态 定义8.1.5 设X,是格，B是X的非空子集，如果B关于运算和也构成格，则称B,是X,的子格。 在例8.1中，令B11,2,3,6，B22,4,6,12，则 B1,和B2,是格S12,的子格。 令B31,2,3,12，由于23=6，而6B3，所以 B3,不是格S12
11、,的子格。 以下定义格的同态。 定义8.1.6 设X1,1,1和X2,2,2是格，其中1, 1,2和2都是二元运算。f是从X1到X2的一个映射，对任意的a,bX1有f(a1b)=f(a)2 f(b)， f(a1b)=f(a)2f(b) 则称f是格X1,1,1到格X2,2,2的格同态。如果f是单射、满射和双射，分别称f是格单同态、格满同态和格同构。称f(X1),2,2是X1,1,1的格同态像。,定理8.1.7 设X1,1和X2,2是格，X1,1,1 和 X2,2,2是它们导出的代数系统。f是格X1,1,1到格X2,2,2的格同态，则a,bX1，如果a1b，必有f(a)2f(b) 证明：设a1b，
12、根据定理8.1.4，a1b=a，由于 f 是格 X1,1,1到格X2,2,2的格同态，所以 f(a)=f(a1b)= f (a)2f (b)，再由定理8.1.4，f (a)2f (b)。 定理8.1.7说明格同态是保序的。一般地说，定理8.1.7的逆并不成立。 【例8.3】设A=a,b,c,d,e，A,是格，其哈斯图如图8.3所示，P(A)是A的幂集合，R=x,y|xP(A)yP (A) xy是P(A)上的偏序关系。P(A), R也是格。作映射 f：AP (A)，定义为：xA，f(x)= y|yA且yx，即： f(a)=a,b,c,d,e=A，f(b)=b,e，f(c)=c,e，f(d)=d,
13、e，f(e)=e。证明f是保序的，但不是格同态。,证明：a,bA，设ab，cf(a)，ca，由偏序关系的传递性得cb，所以cf(b)，即f(a)f(b)，于是f(a)Rf(b)。故f是保序的。 对于b,dA，bd=a f(bd)=f(a)=A f(b)f (d)=b,ed,e =b,d,e f(bd)f(b)f (d) f不是格同态。 但是，当f是格同构时，定理8.1.7的逆成立。,定理8.1.8 设X1,1和X2,2是格，X1,1,1和X2, 2,2是它们导出的代数系统。f 是X1到X2的双射，则 f 是 X1,1,1 到 X2,2,2 的格同构的充分必要条件是 a,bX1，a1bf(a)2f(b) 证明：设f是X1,1,1到X2,2,2的格同构，下证a,bX1，a1bf(a)2f(b) 由定理8.1.7可知，a,bX1，如果a1b，必有f(a)2f(b) 设f(a)2f(b)，由定理8.1.4有f(a)=f(a)2f(b)=f(a1b)，由于f是双射，故a1b=a，所以a1b 这就证明a1bf(a)2f(b) 设a,bX1，a1bf
