离散数学10省公开课一等奖全国示范课微课金奖课件

第10章格与布尔代数王瑞民iermwang@1第1页背景1935年形成格论是代数学分支用于近代解析几何、半序空间1854年，Boole引进布尔代数格与布尔代数在计算机科学中有直接应用2第2页第10章格与布尔代数10.1格10.2特殊格10.3布尔代数3第3页定义10.1.1格<P,>是偏序集，记为P

若P每一对元素都有上确界与下确界称P

为格4第4页例10.1.1(1)P1={2,3,4,12,24,36}P2={1,2,3,12,18,36}

为整除关系则<P1,>，<P2,>为偏序集P1中：2,3无下界，更无下确界，24,36无上界，更无上确界，不是格P2中：12,18下界为1,2,3，但无下确界，2,3上界为12,18,36，但无上确界，不是格5第5页例10.1.1(2)

为实数集R小于等于关系<R,>，<P2,>为格对x,yRsup{x,y}=max{x,y}inf{x,y}=min{x,y}6第6页例10.1.1(3)

为集合包含关系，(U)为U幂集则<

(U),>为格对A,B

(U)sup{A,B}=ABinf{x,y}=AB7第7页例10.1.1(4)

为正整数集合P整除关系则<P,>为格对a,bPsup{a,b}=lcm(a,b)inf{x,y}=gcd(a,b)8第8页例10.1.1(5)(S)是非空S全体划分所成集合

i,j(S)要求，

i

jiff

i任一分块都是j某一分块子集，<(S),>为偏序集合，为格(称为S划分格)

i,j(S)sup{

i,j}=

i+j称为i与j和，由满足以下三条性质S全体子集T组成：①T是i一个或多个元素并②T是

j一个或多个元素并除T外没有T任何子集满足①②inf{

i,j}=

i

j称为i与j积：以i每个元素与

j每个元素交集为元素集，但不包含空集9第9页定理10.1.1格L

中每个有限非空集S有上确界和下确界证实：设|S|=n，S是L子集若S={a}，则supS=infS=a若S={a,b}，则supS,infS均存在令n是任意正整数，使得当|S|=n结论成立，即当S={t1,…,tn}时，supS=t,infS=t’存在T=SU{tn+1}，令u=sup{t,tn+1}，则ut,utn+1故ut1,t2,…,tn,tn+1v是T上界，则vt1,t2,…,tn,tn+1vt,vtn+1,故vu，即u=supT。T上确界存在对偶地，infT存在10第10页定理10.1.1说明S={x1,x2,…,xn}是L任一有限集时，supS可逐一地得到u1=x1u2={u1,x2}u3={u2,x3}…un={un-1,xn}supS是唯一，最终结果与S元素xi排列次序无关；类似地可结构出infS11第11页定义10.1.2完全格设L

为格若L每个子集都有上确界与下确界，则称L

为完全格。如

(S)

是完全Q

不是完全12第12页推论10.1.1每个有限格是完全13第13页零元、单位元偏序集P

若zP，st.

pP,zp,则z是唯一，称为P

零元，记为0若zP，st.

pP,zp,则z是唯一，称为P

单位元，记为114第14页推论10.1.2每个有限格现有0元，又有单位元证实：有限格每个子集都有上确界与下确界有限格本身也有上确界与下确界上确界为单位元下确界为０元15第15页定理10.1.2若格L

满足以下条件之一，则L

是完全格：(1)L

有单位元1，且L任意非空子集有下确界(2)L

有0元，且L任意非空子集有上确界证实：设(1)成立，B为L非空子集，只须证实supB存在令B*为B上界集合，因1B*，故B*不空由(1)知infB*存在

xB,yB*，xy，即x为B*一个下界由infB*定义，

xB，xinfB*，故infB*B*infB*是B上界中最小，所以supB=infB*由B任意性知L

是完全格同理可证(2)16第16页定义10.1.3保联、保交设L

是格，

x,yL，要求xvy=sup{x,y}，x^y=inf{x,y}称v为格L保联(并、和)运算称^为格L保交(交、积)运算17第17页定理10.1.3格L

中任意元素a,b有(1)a^baavb(2)abiffavb=b(3)abiffa^b=b证实：(1)由定义得证(2)若avb=b，则b=sup{a,b}，所以ab若ab，因bb，avbb；由(1)知道bavb，即avb=b(3)证实同(2)18第18页定义10.1.4对于格L

任意元素a1,a2,…an,要求：vk:1nak=a1va2v…van=sup{a1,a2,…an}^k:1nak=a1^a2^…^an=inf{a1,a2,…an}运算满足交换律若L={a1,a2,…an}vk:1nak=a1va2v…van=sup{a1,a2,…an}=1^k:1nak=a1^a2^…^an=inf{a1,a2,…an}=019第19页对偶性原理对于集合S中任何偏序关系

，其逆关系也是S中偏序关系偏序关系<S,>与<S,

>是互为对偶<L,>是格，<L,

>也是格设v是格<L,>中运算，^是格<L,

>中运算，则v，^相互代替，

，相互代替，则关于格<L,>与<L,

>定理都有效20第20页定理10.1.4在格<L,>中，对于任何元素a,b,c都有(L1)ava=a,a^a=a(等幂律)(L2)avb=bva,a^b=b^a(交换律)(L3)av(bvc)=(avb)vca^(b^c)=(a^b)^c(结合律)(L4)av(a^b)=a,a^(avb)=a(吸收律)证实：ava=sup{a,a}=a；另二分之一由对偶原理得证avb=sup{a,b}=sup{b,a}=bva(avb)vc=sup{sup{a,b},c}=sup{a,b,c}=sup{a,{b,c}}=sup{sup{b,c},a}=(bvc)va=av(bvc)aa,a^ba知av(a^b)a，而aav(bvc)，故av(a^b)=a21第21页引理10.1.1在每个集L上定义10.1.3满足(L1),(L2),(L3),(L4)两个运算v和^时，则avb=aiffa^b=b证实：若a=avb，则a^b=(avb)^b=b^(bva)=b若b=a^b，则avb=av(a^b)=a22第22页定理10.1.5满足(L1),(L2),(L3),(L4)两个运算v和^每个集L是格证实：先证L是偏序集，再证avb=sup{a,b}，最终证a^b=inf{a,b}由(L1)知，ava=aiffaa，自反性成立若ab且ba，即avb=b且bva=a，由(L2)：a=bva=avb=b，反对称性成立若ab且bc，即avb=b且bvc=c，由(L2)与(L3)：c=bvc=(avb)vc=av(bvc)=avc，传递性成立23第23页定理10.1.5满足(L1),(L2),(L3),(L4)两个运算v和^每个集L是格证实：再证avb=sup{a,b}，最终证a^b=inf{a,b}av(avb)=(ava)vb=avb，bv(avb)=(avb)vb=av(bvb)=avbavba,avbb,故avb是{a,b}上界若ua,ub，则avu=u,bvu=u故(avb)vu=av(bvu)=avu=u,avb=sup{a,b}24第24页定理10.1.5满足(L1),(L2),(L3),(L4)两个运算v和^每个集L是格证实：最终证a^b=inf{a,b}(a^b)va=av(a^b)=a，(a^b)vb=bv(a^b)=bv(b^a)=b故a^b是{a,b}下界若sa,sb，则sva=a,svb=b故s^(a^b)=(s^a)^b=s^b=s,sv(a^b)=a^b故sa^b，即a^b=inf{a,b}25第25页定义10.1.1’格设[L,^,v]是满足(L1),(L2),(L3),(L4)代数系统，则L为格26第26页推论10.1.3定义10.1.1与定义10.1.1’等价由定理10.1.4与定理10.1.5得证27第27页定义10.1.1”格设[L,^,v]是满足(L2),(L3),(L4)代数系统，则L为格28第28页推论10.1.4定义10.1.1’与定义10.1.1”等价证实：a=av[a^(avb)]=avaa^a=a^[av(a^b)]=a29第29页定理10.1.6在格<L,>中，a,b,c,dL，有ab且aciffab^cac且bciffavbcab且cd则avcbvd，a^cb^d若abc且d^c=a则d^b=a;若abc且dvc=a则dvb=a证实(略)30第30页定义10.1.5子格设[L,^,v]是格，SL，S若a,bS，有a^bS，avbS则称[S,^,v]是[L,^,v]子格31第31页例10.1.2设U={a,b,c}，

(U)={,{a},{b},…,U}<

(U),>是格P1={{a}}P2={,{a},{b}}P3={,{a},{b},{a,b}}P4={,{a},{c},{b,c},U}<Pi,>,i=1,3,4时为格，i=2时不为格i=1,3为<

(U),>子格，i=4不是子格：{a}v{c}={a,c}P4可补充为格：{a}{c}=U,其它元素

等同于v32第32页交集格L子格L1,L2，作为集合交，有L1L2若a,bL1L2,则avb,a^bL1L2若L1L2不空，则L1L2是L子格L1L2未必是格，更不可能是L子格图10-3L1={0,a,b}，L2={a,c}L1L2={0,a,b,c}不是格33第33页定理10.1.7若A为格L非空子集，则在L中包含A最小子格存在证实：设m为L中包含A格全体，因AL且L是格，故Lm，m不空设L(A)=L’mL’若a,bL(A)，则a^b,avbL(A)，从而L(A)是L子格若L’m，则L(A)L’；故L(A)是包含A最小子格34第34页定义10.1.6格同态设[L,^,v]，[S,^S,vS]是格，若

a,bL有(1)g(a^b)=g(a)^Sg(b)(2)g(avb)=g(a)vSg(b)称g:LS为格同态称满足(1)或(2)映射g为从格L到格S交(或并)同态对于格同态g:LS，若g是单(满)射，则称格同态g为单一(满)同态；若g是双射，称为格同构35第35页例10.1.3L={1,2,3,6}，

a,bL，a^Lb=gcd{a,b}，avLb=lcm{a,b}S={7,8}，

a,bS，a^Sb=min{a,b}，avSb=max{a,b}g1:LS，g1(1)=g1(2)=g1(3)=7,g1(6)=8g2:LS，g2(1)=7,g2(2)=g2(3)=g1(6)=8g3:LS，g3(1)=g3(2)=7,g3(3)=g3(6)=8g1交同态;g2并同态;g3同态36第36页例10.1.3续L={1,2,3,6}，

a,bL，a^Lb=gcd{a,b}，avLb=lcm{a,b}S={7,8,9,10}，

a,bS，a^Sb=min{a,b}，avSb=max{a,b}g4:LS，g4(1)=7,g4(2)=8,g4(3)=9,g4(6)=10g4非交同态，也非并同态g:LL，g(1)=1,g(2)=2,g(3)=3,g(6)=6，g是格同构37第37页定理10.1.8g:LL是格同态，则[g(L),^L,vL]是L子格证实：a,bLg(a)^Lg(b)=g(a^Lb)g(L)g(a)vLg(b)=g(avLb)g(L)38第38页定义10.1.7保序映射设<P,

P>与<Q,Q>是偏序集，若映射g:PQ满足：a,bP由aPb能推出g(a)Qg(b)则称g为保序映射39第39页定理10.1.9设<L,

L>与<S,S>是格，其对应代数系统为[L,^L,vL]与[S,^S,vS]，若g:LS是交或并同态，则g是保序映射证实：a,bL，若a

Lb，则g(a)^Sg(b)=g(a^Lb)=g(a)iffg(a)

Sg(b)g(a)vSg(b)=g(avLb)=g(b)iffg(a)

Sg(b)注：反之不真例10.1.3，g4是保序映射，也是双射，但非交、非并同态；g4-1:LS非保序映射，因为8

S9，但2

L340第40页定理10.1.10[L,^L,vL]与[S,^S,vS]是格，若g:LS是双射，且两个格对应偏序关系分别为L和S，则g是格同构iffg是序同构(g与g-1均为保序映射)

证实):定理10.1.9表明，格同构，则g为保序映射因g(a^Lb)=g(a)^Sg(b)=g(a)且g是双射故a^Lb=a，即a

Lb，即g-1为保序映射):只需证实，序同构能得到交同态。即g(a^Lb)=

g(a)^Sg(b)iffg(a^

Lb)是g(a)与g(b)最大下界若a,bL，L是格，则a^LbL，且(a^Lb)Lag保序，故g(a^Lb)Sg(a)；同理g(a^Lb)Sg(b)设g(c)S且g(c)Sg(a),g(c)Sg(b)g-1是保序映射，故c

La,c

Lb，即(a^Lb)是{a,b}下确界即c

L{a,b}推出g(c)Sg(a^Lb)41第41页例10.1.4B={0,1}，要求01，则[B,]是格设[B,^,v]为等价代数格令Bn={<a1,…,an>|aiB,i=1,2,…,n}，要求：<a1,…,an>n<b1,…,bn>iffaibi(i=1,2,…,n)则<Bn,n>是格(n维格)设[Bn,,*]为对应代数格，则<a1,…,an>*<b1,…,bn>=<a1^b1,…,an^bn><a1,…,an><b1,…,bn>=<a1vb1,…,anvbn>42第42页结论含有1、2、3个元素格分别同构于含有1、2、3个元素链43第43页结论4个元素格同构于44第44页结论5个元素格同构于45第45页结论6个元素格同构于p197图10-746第46页第10章格与布尔代数10.1格10.2特殊格10.3布尔代数47第47页定义10.2.1设L

是格，若

x,y,zL，有x^[yv(x^z)]=(x^y)v(x^z)(M1)称L

是模格若x,y,z有一个为0或1，或者x,y,z中有两个相等，则(M1)成立48第48页例10.2.1不是模格取x=a,y=c,z=ba^[cv(a^b)]=a^[cvb]=a^1=a(a^c)v(a^b)=0vb=b1ab0c49第49页例10.2.2模格x=a,y=b,z=cx=a,y=c,z=bx=b,y=a,z=cx=b,y=c,z=ax=c,y=b,z=ax=c,y=a,z=b均使得M1成立1ab0c50第50页定理10.2.1设L

是模格iffxzx^(yvz)=(x^y)vz,

yL(M2)证实)：L是模格，则M1成立；xz则z=x^z。对yL，x^(yvz)=x^[yv(x^z]=(x^y)v(x^z)=(x^y)vz

)：xz和M2知，yL，x^[yv(x^z)]=x^(yvz)=(x^y)vz=(x^y)v(x^z)M1成立51第51页定理10.2.2设L

是模格iff不含有如图五边形子格证实)：若L含有如图子格由例10.2.1知L不是模格

)：若L不是模格由定理10.2.1知，存在元素x,y,z及x>z，使得x^(yvz)(x^y)vzzyvz,x^yyyvz，故x^(yvz)(x^y)x^(yvz)(x^y)vz，由假设知等号不成立故x>z,x^(yvz)>(x^y)vz(*)1ab0c52第52页定理10.2.2续设L

是模格iff不含有如图五边形子格

)：x>z,x^(yvz)>(x^y)vz(*)则yvz,x^(yvz),(x^y)vz,x^y,y组成如图子格yvzy，若yvz=y则由(*)有x^y>(x^y)vz，矛盾。故yvz>y，同理y>x^y(**)(x^y)vzx^y，若(x^y)vz=x^y则zy，故yvz=z，与(**)矛盾。故(x^y)vz>x^y若yvz=x^(yvz)则y=y^(yvz)=y^(x^(yvz))=x^(y^(yvz))=x^y，与(**)矛盾。故yvz>x^(yvz)故五边形成立yvz(x^y)vzx^yyx^(yvz)53第53页定理10.2.2续设L

是模格iff不含有如图五边形子格

)：y与x^(yvz)或(x^y)vz不可比[x^(yvz)]^y=x^[y^(yvz)]=x^y由定理10.1.6(4)知[(x^y)vz]^y=x^y所以二者不可比且x^y是五边形0元[(x^y)vz]vy=[(x^y)vy]vz=yvz再由定理10.1.6知[(x^(yvz)]vy=yvz，从而yvz是五边形单位元素因为关于v与^计算均在L

中，所以该五边形是L

子格yvz(x^y)vzx^yyx^(yvz)54第54页定义10.2.2设L

是格，若

a,b,cL，有a^(bvc)=(a^b)v(a^c)(D1)称L

是分配格格L中，a,b,c只要有一个0或1时或a,b,c中任何两格相等时,D1成立例10.2.1不是分配格：a^(bvc)=a^1，而(a^b)v(a^c)=bv0=b例10.2.2不是分配格：a^(bvc)=a^1，而(a^b)v(a^c)=0v0=055第55页例10.2.3分配格1ab0c1ab0cd0e1f1ab0cd56第56页引理10.2.1a^(bvc)=(a^b)v(a^c)(D1)av(b^c)=(avb)^(avc)(D2)(avb)^(bvc)^(cva)=(a^b)v(b^c)v(c^a)(D3)三式之一成立格L

是模格证实：若D1成立，则a^(bv(a^c)]=(a^b)v(a^(a^c))=(a^b)v(a^c)若D2成立，设ac，即avc=a,a^c=c则a^(bvc)=(avc)^(bvc)=(cva)^(cvb)=cv(a^b)=(a^b)vc若D3成立，设ac，即avc=a,a^c=c则a^(bvc)=[a^(avb)]^(bvc)=[(avc)^(avb)]^(bvc)=(avb)^(bvc)^(cva)=(a^b)v(b^c)v(c^a)=(a^b)v[(b^c)vc]=(a^b)vc57第57页定理10.2.3格L是分配格iffa,b,cL,D1,D2,D3之一成立证实D1D2：由对偶性得证D2D3：(a^b)v(b^c)v(c^a)=[((a^b)vb)^((a^b)vc)]v(c^a)L3,D2=[b^((