考試時(shí)間：5月6日周五950地點(diǎn)：Z2108教室PPT課件

1、v考試時(shí)間：考試時(shí)間：5月月6日日(周五周五)9:50v地點(diǎn)：地點(diǎn)： Z2108教室教室v定理定理17.6: 是格是格L到格到格S的一一對應(yīng)的一一對應(yīng), 則則 是是同構(gòu)映射同構(gòu)映射,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng):對任何對任何a,b L,ab當(dāng)且當(dāng)且僅當(dāng)僅當(dāng) (a) (b)。v證明證明:(1) 是格是格L到格到格S的同構(gòu)映射的同構(gòu)映射,對任何對任何a,b L,ab當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (a) (b)v由由定理定理17.5知知 是保序映射是保序映射,因此對任何因此對任何a,b L, 當(dāng)當(dāng)ab,必有必有 (a) (b).v若對任何若對任何a,b L,有有 (a) (b),則由則由定義知定義知 (a)(b)= (b)

2、,v因?yàn)橥瑯?gòu)因?yàn)橥瑯?gòu),故有故有 (a b)= (b)v且且a b=b,v因此由因此由定義得定義得abv(2) 是格是格L到格到格S的一一對應(yīng)的一一對應(yīng), 且對任何且對任何a,b L,ab當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (a) (b)v主要證明主要證明 是同態(tài)映射是同態(tài)映射,即即v (a b)= (a)(b), (a b)= (a)(b)v分別證明分別證明 (a b) (a)(b)v (a)(b) (a b)2 有補(bǔ)格及分配格有補(bǔ)格及分配格v一、有補(bǔ)格一、有補(bǔ)格v定義定義17.8:一個(gè)具有最大元一個(gè)具有最大元1和最小元和最小元0的格的格L; , 稱為有界格。稱為有界格。v定理定理17.8:L; , 為有界格為

3、有界格, 則任則任a L有有:a 1=1; a 0=0;a 1=a;a 0=a。v定義定義17.8:L; , 為有界格為有界格,對對a L,如果如果存在存在b L,使使a b=1,a b=0,則稱則稱b為為a的補(bǔ)的補(bǔ)元元,記記b為為a。若若L中的每個(gè)元有補(bǔ)元中的每個(gè)元有補(bǔ)元, 則則稱稱L為有補(bǔ)格。為有補(bǔ)格。v例例:S=1,2,3,4,5,其偏序關(guān)系由下圖所示其偏序關(guān)系由下圖所示,則則S是有界格是有界格,且為有補(bǔ)格且為有補(bǔ)格.v由此可知補(bǔ)元不唯一由此可知補(bǔ)元不唯一.v二、分配格二、分配格v定理定理(習(xí)題習(xí)題17.9)：對任意格成立分配不等：對任意格成立分配不等式式, 即格即格L; , 中任中任a

4、,b,c L,有有:v(1)a (b c)(a b) (a c);v(2)(a b) (a c)a (b c)。v但等式不一定成立。但等式不一定成立。v例例: :如下圖所示的格分配等式不成立如下圖所示的格分配等式不成立. .v例：例：S S,P(S);,P(S);,滿足分配等式。滿足分配等式。v分配格分配格v定義定義17.9:L; , 為格為格,當(dāng)對其任意元當(dāng)對其任意元a,b,c L成立分配律成立分配律,即即v(1)a (b c)=(a b) (a c);v(2)(a b) (a c)=a (b c)。v則稱該格為分配格。則稱該格為分配格。v定理：設(shè)定理：設(shè)S是分配格，是分配格，a,x,y S

5、,若若a x=a y,且且a x=a y，則則x=y。vL1L4v上述兩個(gè)圖所代表的格都不是分配格上述兩個(gè)圖所代表的格都不是分配格v可以證明對于任意的格，若可以證明對于任意的格，若|L| 4,則一定則一定是分配格。而所有非分配格，一定含有是分配格。而所有非分配格，一定含有子格是與子格是與M5或或N5同構(gòu)的同構(gòu)的。v定理定理17.9:L; , 為任意格為任意格, 則下述條件則下述條件等價(jià)等價(jià):v(1)對任意對任意a,b,c L,有有 a (b c)=(a b) (a c) v(2)對任意對任意a,b,c L,有有va (b c)=(a b) (a c)v(3)對任意對任意a,b,c L,有有v(

6、a b) (a c) (b c)=(a b) (a c) (b c)v(4)不含與不含與M5或或N5同構(gòu)的子格。同構(gòu)的子格。v(1) (2)v(1),(2)(3)v左左=(a b) (b c) (a c)=(a (b c) (b (b c) (c a)=(a (b c) b) (c a)=(a b) (a c) b) (c a)=(b (a b) (a c) (c a)=(b (a c) (c a)v(3)(1)v1.ca時(shí)時(shí),必有必有va (b c)=?(a b) (a c)=(a b) cv2.一般情況一般情況v利用利用ca時(shí)的結(jié)論時(shí)的結(jié)論v(1),(2)(4)v(4)(1)v反證反證,若

7、若L不是分配格不是分配格,推出存在推出存在與與M5或或N5同構(gòu)的子格同構(gòu)的子格v約定約定:ab,且且a b,記為記為abv基本設(shè)想是在基本設(shè)想是在L中構(gòu)造中構(gòu)造5個(gè)元素的子格個(gè)元素的子格,使使其與其與M5或或N5同構(gòu)同構(gòu)va,e,d,b,0是是M5v分兩種情況分兩種情況v1.存在存在a,b,c L,當(dāng)當(dāng)ca時(shí)時(shí),有有v(a b) c=(a b) (a c)a (b c)vu=a (b c),v=(a b) c,vuvv b=u bvv b=u bvu,v,b,v b,u b, v2.對任意對任意a,b,c L,當(dāng)當(dāng)ca時(shí)時(shí),有有v(a b) c=(a b) (a c)=a (b c)v關(guān)鍵是構(gòu)

8、造關(guān)鍵是構(gòu)造M5,N5v由此定理可以判定一個(gè)格是否為分配格由此定理可以判定一個(gè)格是否為分配格.3 布爾格與布爾代數(shù)布爾格與布爾代數(shù)v一、布爾代數(shù)一、布爾代數(shù)v定義定義17.10:有補(bǔ)分配格稱為有補(bǔ)分配格稱為布爾布爾(Boole)格格, 習(xí)慣上寫成習(xí)慣上寫成(B;)。v有補(bǔ)格：有界有補(bǔ)格：有界(有最大元有最大元1和最小元和最小元0)，且每，且每個(gè)元素有補(bǔ)元個(gè)元素有補(bǔ)元vb是是a的補(bǔ)元：的補(bǔ)元：a b=1,a b=0v定理定理17.10:布爾格布爾格(B;)中任中任a,b B,有有:v(1)a的補(bǔ)元是唯一的。的補(bǔ)元是唯一的。v(2)(a b)=a b,(a b)=a b。v(3)a b=0ab。v

9、(4)(a)=av由由(B;)定義了定義了 , 運(yùn)算，而運(yùn)算，而a的補(bǔ)元的補(bǔ)元a也也是是B中的元素，且分配格補(bǔ)元唯一中的元素，且分配格補(bǔ)元唯一v看作為看作為B上的一元運(yùn)算。上的一元運(yùn)算。vB; , ,為代數(shù)系統(tǒng)，又稱為為代數(shù)系統(tǒng)，又稱為布爾代數(shù)布爾代數(shù)。v作業(yè)作業(yè)P356 : 14,15,16,17, 18(2)(3)v考試時(shí)間：考試時(shí)間：5月月6日日(周五周五)9:50v地點(diǎn)：地點(diǎn)： Z2108教室教室vL1冪等律冪等律:a a=a,a a=a;vL2交換律交換律:a b=b a,a b=b a;vL3結(jié)合律結(jié)合律:a (b c)=(a b) c,v a (b c)=(a b) c;vL4吸收律吸收律:a (a b