第13讲分配格教学文稿.ppt

格的性质n定理11.1 ：设为一个格，由它诱导的代数系统为，则对任意的a,b,c,dA,有 n(1) ab=ba; ab=ba(交换律) n(2) a(bc)=(ab)c; a(bc)=(ab)c(结合律) n(3) aa=a; aa=a(幂等律)n(4) a(ab)=a; a(ab)=a(吸收律) Date1格的不等式n（1）保序不等式nab,cd acbd, acbdn（2）分配不等式na(bc)(ab)(ac),na(bc)(ab)(ac)n（3）模不等式nab a(cb)(ac)bDate2不满足分配律的格n钻石格： b (cd) = b a = b (bc) (bd) = ee = en五角格：c(bd)=ca=c(cb)(cd)=ed=dabcdeabcdeDate3分配律的两个形式等价n如果在一个格中交对并可分配，则并对交也可分配，反之亦然n证：a,b,cS,(格)如果a(bc)=(ab)(ac)那么(ab)(ac)=(ab)a)(ab)c)=a(ab)c)=a(ac)(bc)=(a(ac)(bc)=a(bc)反之同理可证 Date5分配格举例neg1: 是由格诱导的，是分配格b,ca,ca,b,cbacb,aeg2:每个链是分配格Date6分配格的判定n有以下结论：n定理11.5：一个格是分配格 iff 该格中没有任何子格与上述两个五元素格中的一个同构。

abcdegf推论1：小于5元的格是分配格Date7每个链是分配格n推论2：每个链是分配格n证：设是链，则必为格a,b,cA， 考虑a(bc)？= (ab)(ac) 分析a,b,c 的关系有如下六种（按大小顺序）：na b cna c bnb a cnb c anc a bnc b aa b cDate8每个链是分配格n定理：每个链是分配格n证（续）：a,b,cA，分以下两种情形：(1)ab或ac(2)ba且ca对于情况(1),无论bc还是cb，都有a(bc)=a和(ab)(ac)=a对于情况(2),总有bca所以，a(bc)=bc而由ba,ca.应有(ab)(ac)bc故得证 Date9分配格性质n性质1：设是一个分配格，那么，对于a,b,cA，若有ab=ac和ab=ac,则有b=c.n证：(ab)c=(ac)c=c而又有(ab)c=(ac)(bc)=(ab)(cb)=(ac)b=(ab)b= b Date10分配格的判定2n设格是一个分配格，当且仅当a,b,cL，若有ab=ac和ab=ac,则有b=c.dcbaedbcaeDate11全上界全下界n定义11.6：格是一个格，若存在a L,使得xL，有a x,则称a为L的全下界。

若存在bL,使得xL，有x b,则称b为L的全上界dcbaegfhDate12有界格n定义11.7：是一个格，若L存在全下界和全上界，则称L 为有界格，并记L为 n全下界0 （唯一, 零元， 单位元）n全上界1 （唯一, 零元， 单位元）n有界格，存在0,1ac10egfbDate13补元n定义11.8：格是有界格， aL，若存在b L，使得ab=0, ab=1, 则称b是a的补元na与b互为补元n 0与1互补Date14补元举例na与b,c互补a, b, c中任两个元素都互补na, b, c 没补元Date15有补格n定义11.9（有补格）：每一个元都有补元的有界格Date16思考：n求补是否为有补格上的一元运算？n每个元素都有补元的有界格（未必唯一）Date17补元唯一性质n定理11.6：有界分配格中的元素a 如果存在补元，则是唯一的n格是一个分配格，当且仅当a,b,cL，若有ab=ac和ab=ac,则有b=c.Date18布尔代数n有补分配格称为布尔格（布尔代数） n求补是布尔格上的一元运算n1,0是布尔格上的零元运算n诱导的代数系统n实例：幂集格b,ca,ca,b,cbacb,aDate19布尔代数的性质n交换律 x y=y x, x y=y xn分配律 x (y z)=(x y) (x z) x (y z)=(x y) (x z)n同一律 x 1=x, x 0=xn补元律 x x=0, x x=1n注：同时也是代数系统做成布尔代数的条件Date20布尔代数的性质n双重否定律(a ) =anD.M律 (a b) = a b (a b) = a bnab a b = 0 a b = 1 a b = a a b = bnab b aDate21格同态n定义：设，是两个格，分别为它们诱导的代数系统，如果存在一个从A到B的映射f, s.t., a1,a2A，有f(a1a2)=f(a1)f(a2)f(a1a2)=f(a1)f(a2)则称f为从A到B的一个格同态，称为的格同态象，当f为双射时，称f为从A到B的格同构，又称与为同构的。

Date22布尔代数的同态n定义 B1,B2 为布尔代数，f :B1B2, 若则称f 为B1 到B2 的同态n同态判定：n三个等式仅需要两个，其中等式1 和2 不独立.Date23作业:nP219:14,15,16,17Date24。