第13讲_分配格.ppt

《第13讲_分配格.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、格的性质定理11.1：设为一个格，由它诱导的代数系统为，则对任意的a,b,c,d∈A,有(1)a∨b=b∨a;a∧b=b∧a－－(交换律)(2)a∨(b∨c)=(a∨b)∨c;a∧(b∧c)=(a∧b)∧c——(结合律)(3)a∨a=a;a∧a=a——(幂等律)(4)a∨(a∧b)=a;a∧(a∨b)=a——(吸收律)2021/7/251格的不等式（1）保序不等式a≼b,c≼d⇒a∧c≼b∧d,a∨c≼b∨d（2）分配不等式a∨(b∧c)≼(a∨b)∧(a∨c),a∧(b∨c)≽(a∧b)∨(a∧c)（3

2、）模不等式a≼b⇔a∨(c∧b)≼(a∨c)∧b2021/7/252不满足分配律的格钻石格：b∨(c∧d)=b∨a=b(b∨c)∧(b∨d)=e∧e=e五角格：c∧(b∨d)=c∧a=c(c∧b)∨(c∧d)=e∨d=dabcdeabcde2021/7/253分配格定义定义11.5：设是由格所诱导的代数系统，如果对任意的a,b,c∈A，满足a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)则称是分配格。2021/7/254分配律的两个形式等价如果在一个格中交对并可分配

3、，则并对交也可分配，反之亦然。证：a,b,c∈S,(格)如果a∧(b∨c)=(a∧b)∨(a∧c)那么(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))=(a∨(a∧c))∨(b∧c)=a∨(b∧c)反之同理可证2021/7/255分配格举例eg1:是由格诱导的，是分配格{b,c}{a,c}{a,b,c}φ{b}{a}{c}{b,a}eg2:每个链是分配格2021/7/256分配格的判定有以下结论：定理11.5：一个格是分配

4、格iff该格中没有任何子格与上述两个五元素格中的一个同构。abcdegf推论1：小于5元的格是分配格。2021/7/257每个链是分配格推论2：每个链是分配格。证：设是链，则必为格a,b,c∈A，考虑a∧(b∨c)？=(a∧b)∨(a∧c)分析a,b,c的关系有如下六种（按大小顺序）：a≼b≼ca≼c≼bb≼a≼cb≼c≼ac≼a≼bc≼b≼aabc2021/7/258每个链是分配格定理：每个链是分配格。证（续）：a,b,c∈A，分以下两种情形：(1)a≼b或a≼c(2)b≼a且c≼a对于情况(1),无论b≼c还是

5、c≼b，都有a∧(b∨c)=a和(a∧b)∨(a∧c)=a对于情况(2),总有b∨c≼a所以，a∧(b∨c)=b∨c而由b≼a,c≼a.应有(a∧b)∨(a∧c)＝b∨c故得证2021/7/259分配格性质性质1：设是一个分配格，那么，对于a,b,c∈A，若有a∧b=a∧c和a∨b=a∨c,则有b=c.证：(a∧b)∨c=(a∧c)∨c=c而又有(a∧b)∨c=(a∨c)∧(b∨c)=(a∨b)∧(c∨b)=(a∧c)∨b=(a∧b)∨b=b2021/7/2510分配格的判定2设格是一个分配格，当且

6、仅当a,b,c∈L，若有a∧b=a∧c和a∨b=a∨c,则有b=c.dcbaedbcae2021/7/2511全上界全下界定义11.6：格是一个格，若存在a∈L,使得x∈L，有a≼x,则称a为L的全下界。若存在b∈L,使得x∈L，有x≼b,则称b为L的全上界。dcbaegfh2021/7/2512有界格定义11.7：是一个格，若L存在全下界和全上界，则称L为有界格，并记L为。全下界0　　（唯一,∧零元，∨单位元）全上界1（唯一,∨零元，∧单位元）有界格，存在0,1ac10egfb

7、2021/7/2513补元定义11.8：格是有界格，a∈L，若存在b∈L，使得a∧b=0,a∨b=1,则称b是a的补元。a与b互为补元。0与1互补2021/7/2514补元举例a与b,c互补a,b,c中任两个元素都互补a,b,c没补元2021/7/2515有补格定义11.9（有补格）：每一个元都有补元的有界格。2021/7/2516思考：求补是否为有补格上的一元运算？每个元素都有补元的有界格（未必唯一）2021/7/2517补元唯一性质定理11.6：有界分配格中的元素a如果存在补元，则是唯一的。格

8、是一个分配格，当且仅当a,b,c∈L，若有a∧b=a∧c和a∨b=a∨c,则有b=c.2021/7/2518布尔代数有补分配格称为布尔格（布尔代数）　　　求补是布尔格上的一元运算1,0是布尔格上的零元运算诱导的代数系统实例