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

1、第11章 格与布尔代数,离 散 数 学,中国地质大学本科生课程,.,2,本章内容,11.1 格的定义与性质 11.2 分配格、有补格与布尔代数 本章总结 作业,.,3,11.1 格的定义与性质,定义11.1 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格(lattice)。 说明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x与y的二元运算和。 xy：表示x与y的最小上界 xy：表示x和y的最大下界。 本章出现的和符号只代表格中的运算，而不再有其它的含义。,.,4,格的实例,例11.1 设n是正整数，Sn是n的正因子的集合。D为整除关

2、系，则偏序集构成格。x,ySn， xy是lcm(x,y)，即x与y的最小公倍数。 xy是gcd(x,y)，即x与y的最大公约数。 下图给出了格，和。,.,5,例11.2,例11.2 判断下列偏序集是否构成格,并说明理由。 (1) ，其中P(B)是集合B的幂集。 (2) ，其中Z是整数集,为小于或等于关系。 (3) 偏序集的哈斯图分别在下图给出。,.,6,例11.2,解答 (1)是格。 x,yP(B)，xy就是xy，xy就是xy。 由于和运算在P(B)上是封闭的，所以xy，xyP(B)。 称,为B的幂集格。 (2)是格。 x,yZ,xymax(x,y)，xymin(x,y)，它们都是整数。 (3

3、)都不是格。 (a)中的a,b没有最大下界。 (b)中的b,d有两个上界c和e,但没有最小上界。 (c)中的b,c有三个上界d,e,f,但没有最小上界。 (d)中的a,g没有最大下界。,.,7,例11.3,例11.3 设G是群，L(G)是G的所有子群的集合。即 L(G) H|HG 对任意的H1,H2L(G)，H1H2也是G的子群，而是由H1H2生成的子群（即包含着H1H2的最小的子群）。 在L(G)上定义包含关系，则L(G)关于包含关系构成一个格，称为G的子群格。 易见在L(G)中，H1H2就是H1H2，H1H2就是。,.,8,对偶原理,定义11.2 设f是含有格中元素以及符号、和的命题。令f

4、*是将f中的替换成，替换成，替换成，替换成所得到的命题。称f*为f的对偶命题。 例如 在格中令f是(ab)cc，则f*是(ab)cc。 格的对偶原理 设f是含有格中元素以及符号、和的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真。 例如 对一切格L都有 a,bL，aba (因为a和b的交是a的一个下界) 那么对一切格L都有 a,bL，aba 说明 许多格的性质都是互为对偶命题的。 有了格的对偶原理，在证明格的性质时， 只须证明其中的一个命题即可。,.,9,格的运算性质,定理11.1 设是格，则运算和适合交换律、结合律、幂等律和吸收律，即 (1)交换律 a,bL 有 abba abba

5、 (2)结合律 a,b,cL 有 (ab)ca(bc) (ab)ca(bc) (3)幂等律 aL 有 aaa aaa (4)吸收律 a,bL 有 a(ab)a a(ab)a,.,10,定理11.1,(1)ab和ba分别是a,b和b,a的最小上界。 由于a,bb,a，所以abba。 由对偶原理，abba得证。 (2)由最小上界的定义有 (ab)caba (13.1) (ab)cabb (13.2) (ab)cc (13.3) 由式13.2和13.3有 (ab)cbc (13.4) 再由式13.1和13.4有 (ab)ca(bc) 同理可证 (ab)ca(bc) 根据偏序关系的反对称性有 (ab)

6、ca(bc) 由对偶原理，(ab)ca(bc)得证。,.,11,定理11.1,(3)显然aaa, 又由aa可得 aaa。 根据反对称性有 aaa， 由对偶原理，aaa 得证。 (4)显然 a(ab)a (13.5) 又由 aa，aba 可得 a(ab)a (13.6) 由式13.5和13.6可得 a(ab)a， 根据对偶原理，a(ab)a 得证。,.,12,定理11.2,定理11.2 设是具有两个二元运算的代数系统，若对于*和运算适合交换律、结合律、吸收律，则可以适当定义S中的偏序，使得构成一个格，且a,bS有aba*b，abab。 思路 (1)证明在S中*和运算都适合幂等律。 (2)在S上定

7、义二元关系R，并证明R为偏序关系。 (3)证明构成格。 说明 通过规定运算及其基本性质可以给出格的定义。,.,13,定理11.2,aS，由吸收律得,(1)证明在S中*和运算都适合幂等律。,a*a, a*(a(a*a), a,同理有 aaa。,(2)在S上定义二元关系R，,a,bS 有,R abb,下面证明R在S上的偏序。,根据幂等律，,aS都有aaa，,即R，,所以R在S上是自反的。,a,bS 有,aRb且bRa, abb且baa, abaabb (由于a b=ba),所以R在S上是反对称的。,.,14,定理11.2,a,b,cS 有 aRb且bRc abb 且 bcc aca(bc) ac(

8、ab)c acbcc aRc 这就证明了R在S上是传递的。 综上所述，R为S上的偏序。 以下把R记作。,.,15,定理11.2,(3) 证明构成格。 即证明abab，aba*b 。,a,bS 有,a(ab)(aa)bab,b(ab)a(bb)ab,根据的定义有 aab和bab，,所以ab是a,b的上界。,假设 c为a,b的上界，,则有acc和bcc，,从而有,(ab)c, a(bc), ac, c,这就证明了abc，,所以ab是a,b的最小上界，即,abab,为证a*b是a,b的最大下界，,先证,首先由abb 可知,a*b,a*(ab),a,反之由a*ba 可知,ab,(a*b)b,b(b*a

9、),b,再由式(13.7)和的定义有 ab a*ba，,依照前边的证明,类似地可证 a*b是a,b的最大下界，,即 aba*b。,abb a*ba (13.7),.,16,格的等价定义,根据定理11.2，可以给出格的另一个等价定义。 定义11.3 设是代数系统，*和是二元运算，如果*和满足交换律，结合律和吸收律，则构成一个格(lattice)。 说明 格中的幂等律可以由吸收律推出。 以后我们不再区别是偏序集定义的格， 还是代数系统定义的格，而统称为格L。,.,17,格的性质,定理11.3 设L是格，则a,bL 有 ab aba abb 证明 先证 ab aba 由aa和ab可知，a是a,b的下

10、界， 故aab。显然又有aba。 由反对称性得aba。 再证 aba abb。 根据吸收律有 bb(ba) 由aba得 bba, 即abb。 最后证abb ab。 由aab得 aabb。,.,18,格的性质,定理11.4 设L是格，a,b,c,dL，若ab且cd，则 acbd， acbd 证明 acab accd 因此， acbd。 同理可证 acbd。,.,19,例11.5,例11.5 设L是格，证明 a,b,cL 有 a(bc)(ab)(ac) 证明 由 aa，bcb 得 a(bc)ab 由 aa，bcc 得 a(bc)ac 从而得到 a(bc)(ab)(ac) 说明 在格中分配不等式成立

11、。 一般说来，格中的和运算并不是满足分配律的。,.,20,本节小结,偏序集构成格的条件：任意二元子集都有最大下界和最小上界。 格的实例：正整数的因子格，幂集格，子群格。 格的性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。 格作为代数系统的定义。 格的证明方法,.,21,子格,定义11.4 设是格，S是L的非空子集，若S关于L中的运算和仍构成格，则称S是L的子格。,例11.6 设格L如右图所示。令,S1a,e,f,g S2a,b,e,g,则S1不是L的子格，S2是L的子格。 因为对于e和f,有efc， 但cS1。,.,22,11.2 分配格、有补格与布尔代数,一般说来，

12、格中运算对满足分配不等式， 即a,b,cL，有 a(bc)(ab)(ac) 但是不一定满足分配律。满足分配律的格称为分配格。 定义11.5 设是格，若a,b,cL，有 a(bc)(ab)(ac) a(bc)(ab)(ac) 则称L为分配格。 说明 上面两个等式互为对偶式。 在证明L为分配格时，只须证明其中的一个等式即可。,.,23,例11.7,L1和L2是分配格，L3和L4不是分配格。,在L3中， b(cd),beb,(bc)(bd),aaa,在L4中, c(bd),cac,(cb)(cd),edd,钻石格,五角格,.,24,分配格的判别,定理11.5 设L是格，则L是分配格当且仅当L中不含有

13、与钻石格或五角格同构的子格。 证明 略。 推论 (1) 小于五元的格都是分配格。 (2) 任何一条链都是分配格。,.,25,例11.8,说明下图中的格是否为分配格，为什么？,L1, L2和L3都不是分配格。 a,b,c,d,e是L1的子格，并且同构于钻石格。 a,b,c,e,f是L2的子格，并且同构于五角格。 a,c,b,e,f是L3的子格，也同构于钻石格。,.,26,格的全下界和全上界,定义11.6 设L是格， 若存在aL使得xL有ax，则称a为L的全下界； 若存在bL使得xL有xb，则称b为L的全上界。 命题 格L若存在全下界或全上界，一定是唯一的。 证明 以全下界为例，假若a1和a2都是

14、格L的全下界, 则有a1a2和a2a1。 根据偏序关系的反对称性必有a1a2。 记法 将格L的全下界记为0，全上界记为1。,.,27,有界格,定义11.7 设L是格，若L存在全下界和全上界，则称L为有界格，并将L记为。 说明 有限格L一定是有界格。 举例 设L是n元格，且La1,a2,an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是有界格。 对于无限格L来说，有的是有界格，有的不是有界格。 如集合B的幂集格，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集，全上界是B。 整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。,.,28

15、,有界格的性质,定理（补充） 设是有界格，则aL有 a00 a0a a1a a11 证明 由 a00 和 0a0 可知 a00。 说明 在有界格中， 全下界0是关于运算的零元，运算的单位元。 全上界1是关于运算的零元，运算的单位元。 对偶原理 对于涉及到有界格的命题，如果其中含有全下界0或全上界1，在求该命题的对偶命题时，必须将0替换成1，而将1替换成0。 例如 a00 和 a11 互为对偶命题， a0a 和 a1a 互为对偶命题。,.,29,有界格中的补元,定义11.8 设是有界格，aL， 若存在bL 使得 ab0 和 ab1 成立，则称b是a的补元。 说明 若b是a的补元，那么a也是b的补

16、元。 换句话说，a和b互为补元。,.,30,例11.9,考虑下图中的四个格。,L1中的a与c互为补元，其中a为全下界，c为全上界，b没有补元。 L2中的a与d互为补元，其中a为全下界，d为全上界，b与c也互为补元。 L3中的a与e互为补元，其中a为全下界，e为全上界，b的补元是c和d，c的补元是b和d，d的补元是b和c。b,c,d每个元素都有两个补元。 L4中的a与e互为补元。其中a为全下界。e为全上界。b的补元是c和d，c的补元是b，d的补元是b。,.,31,有界格中补元的说明,在任何有界格中， 全下界0与全上界1互补。 对于其他元素，可能存在补元，也可能不存在补元。 如果存在，可能是唯一的

17、，也可能是多个补元。 对于有界分配格，如果它的元素存在补元，一定是唯一的。,.,32,有界分配格中补元的唯一性,定理11.6 设是有界分配格。 若aL，且对于a存在补元b，则b是a的唯一补元。 证明 假设cL也是a的补元，则有 ac1，ac0 又知b是a的补元，故 ab1，ab0 从而得到 acab，acab 由于L是分配格，根据定理13.7，bc。,.,33,有补格的定义,定义11.9 设是有界格，若L中所有元素都有补元存在，则称L为有补格。,L2,L3和L4是有补格， L1不是有补格。,L2和L3是有补格， L1不是有补格。,.,34,本节小结,如果格中一个运算对另一个运算是可分配的，称这

18、个格是分配格。 分配格的两种判别法： 不存在与钻石格或五角格同构的子格； 对于任意元素a,b,c,有 abac且abacbc。 有界格的定义及其实例。 格中元素的补元及其性质（分配格中补元的唯一性）。 有补格的定义。,.,35,布尔代数,定义11.10 如果一个格是有补分配格，则称它为布尔格或布尔代数。 说明 在布尔代数中，每个元素都存在着唯一的补元。 可以把求补元的运算看作是布尔代数中的一元运算。 可以把一个布尔代数标记为， 为求补运算, aB，a是a的补元。,.,36,例11.10,例11.10 设S1101,2,5,10,11,22,55,110是110的正因子集合。令gcd,lcm分别

19、表示求最大公约数和最小公倍数的运算。问是否构成布尔代数？为什么？ 解答 证明构成格。,容易验证x,y,zS110，有 gcd(x,y)S110 lcm(x,y)S110 gcd(x,y)gcd(y,x) lcm(x,y)lcm(y,x) gcd(gcd(x,y),z)gcd(x,gcd(y,z) lcm(lcm(x,y),z)lcm(x,lcm(y,z) gcd(x,lcm(x,y)x lcm(x,gcd(x,y)x,二元运算,交换律,结合律,吸收律,.,37,例11.10,证明 是分配格。 易验证 x,y,zS110 有 gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z)

20、 证明 是有补格。 1 为S110中的全下界 110为S110中的全上界 1和110互为补元，2和55互为补元， 5和22互为补元，10和11互为补元。 综上所述，为布尔代数。,.,38,例11.10（2）,例11.10（2） 设B为任意集合,证明B的幂集格构成布尔代数，称为集合代数。 证明 P(B)关于和构成格，因为 和运算满足交换律、结合律和吸收律。 由于和互相可分配，因此P(B)是分配格， 且全下界是空集,全上界是B。 根据绝对补的定义，取全集为B， xP(B)，x是x的补元。 从而证明P(B)是有补分配格，即布尔代数。,.,39,布尔代数的性质,定理11.7 设是布尔代数，则 (1)

21、aB，(a)a (2) a,bB，(ab)ab,(ab)ab 说明 (1)称为双重否定律。 (2)称为德摩根律。 命题代数与集合代数的双重否定律与德摩根律实际上 是这个定理的特例。 可以证明德摩根律对有限个元素也是正确的。 证明 (1) (a)是a的补元，a也是a的补元。 由补元的唯一性得(a)a。,.,40,定理11.7(2)的证明,(2) a,bB，(ab)ab,(ab)ab (ab)(ab) (aab)(bab) (1b)( a1) 11 1 (ab)(ab) (aba)(abb) (0b)(a0) 000 所以ab是ab的补元，根据补元的唯一性有 (ab)ab 同理可证(ab)= ab

22、。,.,41,布尔代数作为代数系统的定义,定义11.11 设是代数系统，*和是二元运算。 若*和运算满足： (1) 交换律，即a,bB 有 a*bb*a， abba (2) 分配律，即a,b,cB有 a*(bc)(a*b)(a*c) a(b*c)(ab)*(ac) (3) 同一律，即存在0,1B，使得aB 有 a*1a， a0a (4) 补元律，即aB,存在aB，使得 a*a0， aa1 则称是一个布尔代数。,.,42,关于布尔代数定义的说明,所谓同一律就是指运算含有单位元的性质，这里的1是*运算的单位元，0是运算的单位元。 可以证明1和0分别也是和*运算的零元。 aB有 a1 (a1)*1

23、（同一律） 1*(a1) （交换律） (aa)*(a1) （补元律） a(a*1) （分配律） aa （同一律） 1 （补元律） 同理可证 a*00。,.,43,关于布尔代数定义的说明,为证明以上定义的是布尔代数，只需证明它是一个格，即证明*和运算满足结合律和吸收律。 证明吸收律，a,bB有 a(a*b) (a*1)(a*b) （同一律） a*(1b) （分配律） a*1 （1是运算的零元) a （同一律） 同理有 a*(ab)a。,.,44,关于布尔代数定义的说明,为证结合律，先证以下命题： a,b,cB，abac 且 abac bc 由 abac 且 abac 可得 (ab)*(ab)(a

24、c)*(ac) 由分配律和交换律得 (a*a)b(a*a)c 由补元律得 0b0c 由同一律和交换律得 bc,.,45,关于布尔代数定义的说明,使用这个命题，为证明 (a*b)*ca*(b*c)，只需证明以下两个等式： (1) a(a*b)*c)a(a*(b*c) (2) a(a*b)*c)a(a*(b*c) 先证明第一个等式，由吸收律有 a(a*(b*c)a a(a*b)*c) (a(a*b)*(ac) (分配律) a*(ac) (吸收律) a 所以(1)式成立。,.,46,关于布尔代数定义的说明,下面证明(2)式： a(a*b)*c)a(a*(b*c) a(a*(b*c) (aa)*(a(

25、b*c) (分配律) 1*(a(b*c) (交换律,补元律) a(b*c) (交换律,同一律) a(a*b)*c) (a(a*b)*(ac) (分配律) (aa)*(ab)*(ac) (分配律) (1*(ab)*(ac) (交换律,补元律) (ab)*(ac) (交换律,同一律) a(b*c) (分配律) 所以（2）式成立。,.,47,有限布尔代数的结构,定义11.12 设L是格，0L，aL，若 bL 有 0ba ba 则称a是L中的原子。,考虑右图中的几个格。 L1的原子是a。 L2的原子是a,b,c。 L3的原子是a和b。,若L是正整数n的全体正因子关于整除关系构成的格，则L的原子恰为n的

26、全体质因子。 若L是集合B的幂集合，则L的原子就是由B中元素构成的单元集。,.,48,有限布尔代数的表示定理,定理11.8 (有限布尔代数的表示定理) 设B是有限布尔代数，A是B的全体原子构成的集合，则B同构于A的幂集代数P(A)。 证明 任取xB，令T(x)a|aB,a是原子且ax 则T(x)A，定义函数 ：BP(A)，(x)T(x)，xB 下面证明是B到P(A)的同构映射。 任取x,yB，b 有 bT(xy) bA 且 bxy (bA且bx) 且 (bA且by) bT(x)且bT(y) bT(x)T(y) 从而有 T(xy)T(x)T(y)， 即x,yB 有 (xy)(x)(y)。,.,4

27、9,定理11.8证明,任取x,yB，设 xa1a2an， yb1b2bm 是x,y的原子表示，则 xya1a2anb1b2bm 由引理2可知 T(xy)a1,a2,an,b1,b2, ,bm 又由于 T(x)a1,a2, ,an， T(y)b1,b2, ,bm 所以 T(xy)T(x)T(y) 即 (xy)(x)(y),.,50,定理11.8证明,任取xB，存在xB 使得 xx1， xx0 因此有 (x)(x)(xx)(1)A (x)(x)(xx)(0) 而和A分别为P(A)的全下界和全上界， 因此(x)是(x)在P(A)中的补元，即 (x)(x) 综上所述，是B到P(A)的同态映射。,.,5

28、1,定理11.8证明,下面证明为双射。 假设(x)(y)，则有 T(x)T(y)a1,a2, ,an 由引理2可知 xa1a2any 于是为单射。 任取b1,b2, ,bmP(A)， 令xb1b2bm ，则 (x)T(x)b1,b2, ,bm 于是为满射。 定理得证。,.,52,例子,考虑110的正因子的集合S110关于gcd, lcm运算构成的布尔代数。 它的原子是2、5和11，因此原子的集合A2,5,11。 幂集P(A),2,5,11,2,5,2,11,5,11,2,5,11。 幂集代数是。 只要令 : S110P(A)， (1)， (2)2， (5)5， (11)11， (10)2,5， (22)2,11， (55)5,11, (110)A， 那么f就是定理13.11中从S110到幂集P(A)的同构映射。,.,53,推论1,推论1 任何有限布尔代数的基数为2n，nN。 证明 设B是有限布尔代数，A是B的所有原子构成的集合， 且|A|n，nN。 由