资源描述:
《第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是布尔格上的零元运算诱导的代数系统实例