(36)--4.10 特殊格离散数学离散数学.ppt

特殊格分配格：分配格：设设是格，若对是格，若对 a,b,c L有有 a (b c)=(a b)(a c)a (b c)=(a b)(a c)成立，则称成立，则称为分配格。为分配格。分配格bedcadcbabadcbaced钻石格钻石格五角格五角格L1和L2是分配格,L3和L4不是分配格.在L3中,d(cb)=d，(dc)(db)=a在L4中,c(bd)=c，(cb)(cd)=d分配格分配格的判定定理格是分配格当且仅当它不含有与五角格或钻石格同构的子格。例：判断下列格是否为分配格。cafedbcaedbfcaedbgfcahefbgd分配格推论推论(1)小于五元的格都是分配格。小于五元的格都是分配格。(2)任何一条链都是分配格。任何一条链都是分配格。分配格有界格：有界格：全下界全下界(或全上界或全上界)：设设为为格，格，若若存在存在a L，对对 b L有有ab(或或ab)，则称则称a为格为格的全下界的全下界(全上界全上界)格格L 若存在全下界或全上界若存在全下界或全上界,一定是惟一的一定是惟一的.记全下界为记全下界为0，全上界为，全上界为1。有界格：有界格：具有全上界和全下界的格。具有全上界和全下界的格。记作记作。所有的有限元的格都是有界格。所有的有限元的格都是有界格。有补格补元：补元：设设是有界是有界格，格，a L，若若 b L，使得使得a b=0，a b=1，则称则称b为为a 的补元。的补元。若若b 是是a 的补元的补元,那么那么a 也是也是b 的补元。的补元。a 和和b 互为补元。互为补元。补元可能存在或不存在，存在亦可能不唯一。补元可能存在或不存在，存在亦可能不唯一。有补格例:求补元解：L1中a,c互补,b没补元。L2中a,d互补,b,c互补。L3中a,e互补,b 的补元是c和d,c 的补元是b和d,d 的补元是b和c。L4中的a,e互补,b 的补元是c和d,c 的补元是b,d 的补元是b。有补格：有补格：设设是有界是有界格，格，若对若对 a L，在在L中都存在中都存在a的补元，的补元，则称则称是有补格。是有补格。有补格布尔格：布尔格：如果格如果格是有补分配格，是有补分配格，则称则称为布尔格，为布尔格，也叫做布尔代数。也叫做布尔代数。布尔代数也可记为布尔代数也可记为，表示求补运算。表示求补运算。如：集合的幂集格如：集合的幂集格是是布尔代数，布尔代数，逻辑代数逻辑代数是是布尔代数。布尔代数。布尔代数布尔代数的性质：设是布尔代数，则有(1)a L，a的补元唯一(2)a L，(a)=a(3)a,b L，(a b)=a b，(a b)=a b布尔代数例S是36的正因子集合，即S=1，2，3，4，6，9，12，18，36，为整除关系。（1）作出的哈斯图；（2）中最大元，最小元；（3）中，B S，设B=3，4，求B的上确界，下确界；（4）是否为格？说明理由；（5）是否为分配格？有补格？布尔格？说明理由。解（1）的哈斯图如图所示；（2）中最大元36，最小元1；（3）B的上确界12，下确界1；（4）是格，因为S中任意两个元素之间均有上确界与下确界；（5）为分配格，因为该格不含有与钻石格或五角格同构的子格；不是有补格，因为图中并非每个元素都有补元，如6无补元；不是布尔格，因为布尔格要求格中每个元素都有唯一补元。THANKYOU