離散數(shù)學(xué)II課件：7_3格的性質(zhì)-1

1、7.3 格 的 性 質(zhì),7.3.1 格 的 性 質(zhì) 7.3.2 格的同態(tài)與同構(gòu),7.3.1 格 的 性 質(zhì),定理7.3.1 設(shè)（L，）是一個(gè)格，a，b是L中任 意元素，于是 ab ab = a a b = b 證明： 若ab，因?yàn)閍a，所以a是a，b的下界，故aab。而ab是a，b的最大下界，所以aba。故ab=a。 若ab=a，由吸收律知ab=(ab)b=b,由ab的定義知，b是a，b的 最小上界，顯然有ab。 若ab=b，由ab的定義知，b是a，b的 最小上界，顯然有ab。,定理7.3.2 設(shè)（L，）是一個(gè)格，a，b，c是 L中任意元素， 如果bc，則有 abac abac 證明： 因?yàn)閎

2、c，所以由定理8.3.1知 bc=b 又因?yàn)?ab)(ac)=(aa)(bc) = a(bc) = ab 再由定理8.3.1知：abac。 同理可證得第二個(gè)不等式。,定理7.3.3 設(shè)（L，）是一個(gè)格，a，b，c是L中任意元素。于是有 a（bc） （ab）（ac） a（bc）（ab）（ac） 其中關(guān)系“”是關(guān)系“”的對(duì)偶關(guān)系。 證明：因?yàn)閍ab，aac，所以，由的定義知 a（ab）（ac） （1） 又因?yàn)?bcbab bccac 所以，再由的定義知 bc（ab）（ac） （2） 由的定義及（1），（2）式知 a（bc）（ab）（ac） 對(duì)偶地可證得另一不等式.,Note:在一般格中，分配律不是

3、總成立的，但上 述分配不等式總是成立的。 因?yàn)閍2（a1a3）= a2 （a2a1）（a2a3）=a3 只有對(duì)特殊的格（分配格、模格）分配律才成立,定理7.3.4 設(shè)（L，）是一個(gè)格，a，b，c是L中任意元素，于是， ab a（bc）b（ac） 證明： 若ab，則由定理8.3.1知：ab=b。由定理8.3.3知 a（bc）（ab）（ac） = b（ac） 若a（bc）b（ac），則由的定義知 a（bc）a 由的定義知 b（ac）b 故ab。,7.3.2 格的同態(tài)與同構(gòu),定義. 設(shè)(L,)和(S,)是兩個(gè)格，L到S 內(nèi)的映射g稱(chēng)為(L,)到(S,)的格同態(tài)映 射，如果對(duì)任意a，bL，都有 g（a

4、b）= g（a）g（b） g（ab）= g（a）g（b）. 定義. 格L到L內(nèi)的同態(tài)映射稱(chēng)為格的自同態(tài)映射。 定義. 若g是L到S上的同態(tài)映射,且是一對(duì)一的，則稱(chēng)g是格同構(gòu)映射,并稱(chēng)格L與格S是同構(gòu)的。此時(shí)，對(duì)任意xL，任意yS ，有 g-1(g()=，g(g-1(y)=y。,同態(tài)映射例,例. 設(shè)S=a,b,(S)=,a,b,a,b， 則（S），）是一個(gè)格。 設(shè)L=0，1，規(guī)定01，分別是集合L中兩個(gè)元素在下的最大下界，最小上界運(yùn)算，則（L，）是一個(gè)格。 規(guī)定映射g為： g（a） = 1， g（a，b） = 1， g（b） = 0， g（ ） = 0。 則顯然g是（S）到L上的映射.,往證g是

5、同態(tài)映射。首先證對(duì)任意A,B(s)， g（AB） = g（A） g（B）。 若aAB，則aA，aB，故 g(AB) = 1, g(A) g(B) = 1 1 = 1。 若aAB，則 g(AB) = 0, g(A) g(B) = 綜上，g（AB） = g（A） g（B）。,再證對(duì)任意A,B(s)，g(AB)=g(A)g(B) 若aAB，則 g(AB)=1，g(A)g(B)= 若aAB，則aA，aB，故 g(AB)= 0 ， g(A)g(B)=0 0 = 0。 綜上，g（AB） = g（A） g（B）。 因此，g是(s)到L上的同態(tài)映射。,自同態(tài)映射例,例. 設(shè)S=a,b,(S)=,a,b,a,b

6、， 則(S)，）是一個(gè)格。規(guī)定映射g為： g() = g(a) =， g(b)=g(a，b)= b。 顯然,g為(S)到(S)內(nèi)的映射。往證g是同 態(tài)映射。不難驗(yàn)證對(duì)任意A,B(S),有: 若bAB,則g(AB)=g(A)g(B)=b； 若bAB，則g(AB)=g(A)g(B)=。 若bAB，則g(AB)=g(A)g(B)=b； 若bAB，則g(AB)=g(A)g(B)=。 故 (AB)=g(A)g(B),g(AB)=g(A)g(B)。 g為格（S），）的自同態(tài)映射。,同構(gòu)映射例,例. 設(shè)S=a,b,c, (S)=,a,b,c,a,b,b,c,a,b,c, 則(S),)是一個(gè)格。 （S30，）

7、是一個(gè)格,、分別是求兩個(gè) 正整數(shù)的最高公因、最小公倍。 規(guī)定映射g為： 1, a2, b3, c5,a,b6,a,c10,b,c15,a,b,c30。 則顯然g為(S)到S30上的1-1映射。 不難驗(yàn)證對(duì)任意A,B（S），有： g(AB)=g(A)g(B), g(AB)=g(A)g(B)。 因此，g為(S)到S30上的同構(gòu)映射.,格的同態(tài)映射一定是保序映射,定理7.3.5 設(shè)(L,)和(S,)是兩個(gè)格。 集合L上對(duì)應(yīng)于運(yùn)算，的部分序?yàn)長(zhǎng)， 集合S上對(duì)應(yīng)于運(yùn)算，的部分序?yàn)閟。 如果g是L到S內(nèi)的同態(tài)映射，則g是保序映射， 亦即，對(duì)任意a，bL， 若aLb，則g（a）sg（b）。 證明： 由ab,

8、 知ab=a，故g(ab)= g(a), 而 g（ab）= g（a）g（b） = g（a） 故g（a）sg（b）,例子,例 同態(tài)具有保序性，但其逆不一定成立，保序映射不一定是同態(tài)的。下面給出3個(gè)格L1,L2L3。定義映射1, 2和3： 1：L1L2, 1(a)= 1(b)= 1(c)=a1, 1(d)=d1. 2：L1L2, 2(b)= 2(c)= 2(d)=d1, 2(a)=a1. 3：L1L3, 3(a)=a2, 3(b)=b2, 3(c)=c2, 3(d)=d2. d d1 d2 b c b2 a a1 a2 L1 L2 L3,c2,例子,可以看出這3個(gè)映射都是保序的，但都不是同態(tài)的。因

9、為 1(bc)= 1(d)=d1, 1(b) 1(c)= a1 a1=a1, 2(bc)= 2(a)=a1, 2(b) 2(c)= d1 d1=d1, 3(bc)= 3(d)=d2, 3(b) 3(c)=b2 c2=c2,定理7.3.6 設(shè)(L,)是一個(gè)格，g是此格的 自同態(tài)映射，于是g(L)是(L，)的代數(shù) 子格。 證明： 任取a,bg(L),則必有a,bL, 使 a= g（a）， b= g（b） 因?yàn)間是格（L，）的自同態(tài)映射，所以 ab=g(a)g(b)= g(ab)g(L)， ab= g(a)g(b)=g(ab)g(L)。 即在運(yùn)算，下，g（L）是封閉的。 故（g（L）， ，）是（L，

10、）的代 數(shù)子格。,定理7.3.7 設(shè)(L,）,(S,)是兩個(gè)格， 若g是L到S上的同構(gòu)映射， 則g的逆映射g-1是S到L上的同構(gòu)映射。 證明： 顯然g-1是S到L上的一對(duì)一映射。 下面證明g-1是S到L上的同態(tài)映射。 任取a,bS,令g-1(a)=a,g-1(b)=b。于是 g（a）= a， g（b）= b。 g-1(ab)=g-1(g(a)g(b)=g-1(g(ab) = ab =g-1(a)g-1(b)。 g-1(ab)= g-1(g(a)g(b)=g-1(g(ab) = ab= g-1（a）g-1（b）。 故g-1是S到L上的同構(gòu)映射。,推論 若格（L，）和格（S，） 同構(gòu)，g是其同構(gòu)映

11、射，則對(duì)L中任意兩個(gè)元素a，b，有 aLb g（a）sg（b） 其中L，S分別是集合L，S上對(duì)應(yīng)于運(yùn)算， 的部分序關(guān)系。,n維格,設(shè)L=0，1，規(guī)定01。于是，（L，）是格。 令（L，）是與之等價(jià)的代數(shù)格。 令 Ln=(a1，an)aiL，i=1，n 規(guī)定：(a1,an )n ( b1,bn ) aibi (i=1,n) 不難證明：(Ln，n)是一個(gè)格，通常稱(chēng)為n維格。令與(Ln，n)等價(jià)的代數(shù)格為(Ln,)，對(duì)Ln中任意兩個(gè)元素(a1,an)，(b1,bn)，顯然有(a1,an)(b1,bn)=(a1b1,anbn) (a1,an)(b1,bn)=(a1b1,anbn)。,例. 設(shè)S是含n個(gè)元素的集合，(s)是S的冪集 合，則格（(s)，）與格（Ln，n）同構(gòu)。 證明：令S=s1，sn。 令g是(s)到Ln上的映射如下：任取A(s)， g（A）=（a1，an） 其中ai=1 siA，i=1，n。 顯然，g是（s）到Ln上的一對(duì)一映射。,任取A,B(s),令 g(A)=(a1,an),g(B)=(b1,bn)，g(AB)=(c1,cn)，于是由g的定義知：