華中科技大學(xué)離散課件 11

1、第七章　格一　偏　序　集　1.偏序集 定義7-1 　集合L和定義在 L 上的偏序關(guān)系 “≤” 一起稱(chēng)為偏序集，用表示。,若 是集合A上的偏序關(guān)系，則 的逆關(guān)系也必是Ａ上的偏序關(guān)系，證明如下：,，，和都是偏序集。,１．對(duì)任意的 a Ａ，因?yàn)?自反，所以有 （a,a） ,于是（a,a） ，因此 也是自反的。,２．對(duì)任意 a ,b A ，若（a,b） 且（b,a）

2、， 則有（b,a） 且（a,b） ，必有a = b， 因此 是反對(duì)稱(chēng)的。,３．對(duì)任意a,b,c A,若（a,b） ,(b,c） ， 則有（c,b） 且（b,a） ，必有 （c,a） ，于是（a,c） ，因此 是可傳遞的。 由上證得 也是偏序關(guān)系。,根據(jù)逆關(guān)系的定義 =,由定義 =,例1

3、 設(shè) A= ，定義 A 上的整除關(guān)系 ： 當(dāng)?shù)﹥H當(dāng) a 整除 b 時(shí)，有 。,若是一個(gè)偏序集，則對(duì)于任意元素 1, 2, 3 L，有以下六個(gè)關(guān)系式成立：,1 1 (7- ) 若 1 2 ， 2

4、 1，則 1= 2 (7- ) 若 1 2 ， 2 3，則 1 3 (7- ),注意 在偏序集中，對(duì)任意元素 1， 2 L，若 1 2，則必有 2 1，,若 2 1，則必有 1 2，因此， 1

5、 2等價(jià)于 2 1 。,1 1 （7-1） 若 1 2 ， 2 1，則 1= 2 （7-2） 若 1 2 ， 2

6、3，則 1 3 (7-3),2．最大下界和最小上界定義7-1 設(shè) 1和 2是偏序集中的兩個(gè)元素,元素a L，如果滿(mǎn)足a 1,a 2 ,則稱(chēng)a是 1和 2的下界。,定義7-2 設(shè) 1和 2是偏序集中的兩個(gè)元素，元素　b L ,如果滿(mǎn)足 1 b， 2 b，則稱(chēng) b是 1和 2的上界。,如果元素a是 1和 2的下

7、界。且對(duì)于任意 L，若也是 1和 2的下界，便有 a ,則稱(chēng)a是 1和 2的最大下界，簡(jiǎn)記作a=glb(　　1 , 2).,如果元素 b是 1和 2的上界，且對(duì)于任意 L，若 也是 1和 2的上界，便有b　　，則稱(chēng) b 是　1和　2的最小上界，簡(jiǎn)記作b=lub(　1, 2),lub(2,3)=？，glb(12,18)=?，lub(18,27)=?,有2 6，3

8、6；2 12，3 12；2 18，3 18。,由于6 12，6 18，6 6，因此，lub（2，3）=6。,6 ≤ 12，6 ≤ 18；2 ≤ 12，2 ≤ 18；3 ≤ 12，3 ≤ 18；1 ≤ 12,1 ≤ 18；,因1 ≤ 6，2 ≤ 6，3 ≤ 6，所以glb(12,18)＝6。,例2 設(shè)A= “整除”關(guān)系是A上的偏序關(guān)系

9、，其次序圖如下，因此，它們構(gòu)成一個(gè)偏序集。,試問(wèn) glb(18,12)=?, lub(2,3)=?,2≤18，2 ≤ 12；3 ≤ 18，3 ≤ 12，1 ≤ 18，1 ≤ 12。,但glb(18,12)不存在。,類(lèi)似地，12，18 和 36 均是 2 和 3 的上界，但 lub（2，3）不存在。,例3　設(shè)A=　　　　　　　，整除關(guān)系是A上的偏序關(guān)系，其次序圖如下,定理7-1 設(shè)　和　是偏序集的兩個(gè)元素，如

10、果　和　有g(shù)lb,則glb是唯一的，如果　和 有l(wèi)ub，則lub是唯一的。,證明　　設(shè)　和　都是　和　的glb，,由定義7-1，則 　≤　, 　 ≤　,于是有　=　 。,類(lèi)似地可以證明, 　和　若存在lub，則lub也一定是唯一的。,定理7-2 如果偏序集有最小元素，則最小元素是唯一的。如果有最大元素，則最大元素也是唯一的。,3 最小元素和最大元素 定義7-3 設(shè)是一偏序集。 (1) 如果存在

11、元素a L，使得對(duì)于所有的元素 L，有a ≤ ，則稱(chēng)a是的最小元素。 (2) 如果存在元素b L，使得對(duì)于所有的元素 L，有 ≤b，則稱(chēng)b是的最大元素。,證明 設(shè) 和 都是的最小元素，則有 ≤ ，且 ≤ ，得 ＝ 。,二、 格 1．格的定義 定義7-4 設(shè)是一個(gè)偏序集，如果L中任意兩個(gè)元素都存在著最大下界

12、和最小上界，則稱(chēng)是格。,=glb（ ， ）， =lub（ ， ）。,若是一個(gè)格，則意味著也是一個(gè)形 為 的代數(shù)系統(tǒng)，其中 和 是L上的兩個(gè)二元運(yùn)算， 對(duì)于任意 ， ， 表示在偏序“≤”意義下， 和 的最小上界， 表示 和 的最大下界。,例5 試判斷下列次序圖給出的偏序集哪些是格？,解 （a）不是格， (b)不是格，,(c)是一個(gè)格， （d）是

13、一個(gè)格,在格＜L；≤>中有如下四個(gè)關(guān)系式成立:,2．格的性質(zhì) 定理7-3 在格中，對(duì)于任意以下三式中若任意一式成立，那么其它兩式也成立.,證明 ① =＞ ② 設(shè) ，,② => ③ 設(shè),③ => ① 設(shè),定義7-5 設(shè)是格，P是包含格的元素和符號(hào)=、≤、≥，∧ ，∨的命題，將P中的≤、≥，∧和∨分別替換成≥、 ≤、 ∨和∧所得的命題PD稱(chēng)為P的對(duì)偶。,例

14、如 的對(duì)偶是,對(duì)偶原理 ： 對(duì)于格上的任一真命題P，其對(duì)偶 PD 亦為格上的真命題。,定理7-4（交換律） 設(shè)是格，則對(duì)任意的有:,定理7-5 （結(jié)合律） 設(shè)是格，則對(duì)任意的 ，有,證明,定理7-6 （吸收律）設(shè)＜L；≤＞是格，則對(duì)任意 ，有,證明 (b) 由（5

15、-4）,另一方面，由（5-1）,于是，由（5-5） （2）,由（1)、(2）和反對(duì)稱(chēng)性,定理7-7 （等冪律） 設(shè)＜L；≤＞是格，則對(duì)任意 ，有,證明 （a）由定理7-6 ,,定理7-9 （格的保序性） 設(shè)＜L；≤＞是格，則對(duì)于任意 ，有,由①,②和,因?yàn)?

16、 所以由(1)有,例4 設(shè) L = ，L上的整除關(guān)系 與L構(gòu)成一個(gè)格，記作，,3∨( 6 ∧ 4 ) = 3 ∨ 1= 3,(3∨6)∧(3∨4) = 6 ∧ 12 = 6,于是 3∨(6∧4)≠(3∨6)∧(3∨4),6∧(3∨4) = 6∧12 = 6,(6∧3)∨(6∧4)= 3∨1= 3,于是 6∧(3∨4)≠(6∧3)∨(6∧4),定理7-10 設(shè)

17、是格，則對(duì)任意 ,有,證明 （a）由(5-4)有,于是，根據(jù)定理5-19有,又由（5-4）有,7．2 格是一種代數(shù)系統(tǒng) 定理7-10 設(shè)是一個(gè)代數(shù)系統(tǒng)，其中∨和∧都是二元運(yùn)算，滿(mǎn)足交換律，結(jié)合律和吸收律，則在L上必存在一偏序關(guān)系，使得是一個(gè)格。,可以證明關(guān)系≤是L上的自反，反對(duì)稱(chēng)和可傳遞的關(guān)系，因此≤是L上的偏序關(guān)系。,進(jìn)一步還可以證明，對(duì)任意 ， 是在偏序關(guān)

18、系≤意義下 1和 2的最小上界， 1 2 是 1和 2的最大下界。 故是一個(gè)格。,格既可以看作是一個(gè)偏序集，也可以看作是一個(gè)代數(shù)系統(tǒng)。,定義7-6 設(shè)是一個(gè)代數(shù)系統(tǒng)， 和 是 L 上的兩個(gè)二元運(yùn)算，如果這兩個(gè)運(yùn)算滿(mǎn)足交換律，結(jié)合律和吸收律，則稱(chēng) 是格。,例5 在全集合 U 的冪集 2U = 上的包含關(guān)系“ ”是 2U 上的一偏序關(guān)系。,因?yàn)閷?duì)任意Si

19、 2U，總有Si Si，所以 是自反的。,對(duì)任意Si , Sj 2U , 若Si Sj ，且Sj Si ，則必有Si = Sj ，所以 是反對(duì)稱(chēng)的。,對(duì)任意Si , Sj ，Sk 2U，若Si Sj ，Sj Sk ，則必有Si Sk，所以 是可傳遞的。 因此是一偏序集。,因此Si∪Sj是Si和Sj的上界。,對(duì)于任意Si , S

20、j 2U，有Si Si∪Sj，Sj, Si∪Sj，,類(lèi)似地可以證明，對(duì)任意 ，glb(si,sj)=si∩sj 因此是一個(gè)格 另一方面，集合的并運(yùn)算和交運(yùn)算和2U構(gòu)成代數(shù)系統(tǒng)　　，因?yàn)檫\(yùn)算∪和∩都滿(mǎn)足交換律，結(jié)合律 和吸收律，因此是一個(gè)格。,則必有Si∪Sj S。因此Si∪Sj是Si和Sj的最小上界。即lub(Si，Sj)= Si∪Sj。,若有S

21、2U，使得 Si S ，Sj S，,例6 設(shè)U={a,b,c} 則2U={φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}},二 、子格 定義7-7 設(shè)是格，如果是的子代數(shù)，則稱(chēng)是的子格。,格對(duì)應(yīng)的代數(shù)系統(tǒng)形式的格是.,子格也是一個(gè)格。,令 S1={,{a,b}{b,c},{a,b,c}}S2={φ,{a},{ c},{a, c}}S3={φ,{a},{

22、c},{a,b},{a,c},{b,c},{a,b,c}},是的子格。,也是的子格。,S3不能與這兩個(gè)運(yùn)算構(gòu)成的子格。,2 6,112,3 4,1 10,（1） glb(6,9) = ; glb(8,12) = .； （2） glb(9,7)

23、= ; lub(5,10) = .。,12,YY,NN,定義7-8 設(shè)是一個(gè)格，若對(duì)于任意的 1, 2， 3 ∈ L，有則稱(chēng)是分配格。,7．3 分配格和有補(bǔ)格一、分配格 1．分配格的定義,例1 對(duì)任意的集合A，是一個(gè)分配格，,= a∨a =a因此 b∧(c∨d)≠（b∧c）∨b∧d）,而（b∧c)∨(b∧d）,2． 分配格的判別,定理7-12 在

24、格中，如果交運(yùn)算對(duì)并運(yùn)算是可分配的，則并運(yùn)算對(duì)交運(yùn)算也是可分配的；如果并運(yùn)算對(duì)交運(yùn)算是可分配的，則交運(yùn)算對(duì)并運(yùn)算也是可分配的。,證明 設(shè)在格中，對(duì)任意 1， 2， 3∈L，有 1 （ 2 3）=（ 1 2） （ 1 3 ）,例如 設(shè) L ={1，2，4，16，32，64}, 定義在L上的整除關(guān)系≤與L構(gòu)成一個(gè)鏈。,設(shè)是一個(gè)偏序集，若對(duì)于任意的 ， ∈L，或者 ，或者

25、 ，則稱(chēng)是一個(gè)鏈。,例3 每一個(gè)鏈都是一個(gè)分配格。,證明 （1）先證明是一個(gè)格。,由鏈的定義，對(duì)于任意 1， 2∈L或者 1≤ 2 ，或者 2≤ 1。,若 1≤ 2，則glb( 1, 2)= 1 ,lub( 1, 2)= 2,若 2≤ 1，則glb( 1, 2)= 2 , lub( 1, 2)= 1,所以是一個(gè)格，可將其表示為。對(duì)任意 1, 2

26、L， 1 2=lub( 1, 2), 1 2=glb( 1, 2),(2) 證明 是一個(gè)分配格,對(duì)任意 1, 2, 3∈L必有 2≤ 3或者 3≤ 2，不妨設(shè) 2≤ 3，,于是有 1 （ 2 3）= 1 3。,又因?yàn)?1 2 ≤ 1 3，,所以（ 1 2） （

27、 1 3）= 1 3,因此 1 （ 2 3）=（ 1 2） （ 1 3）,若 3≤ 2，其證明方法類(lèi)似，因此鏈?zhǔn)且粋€(gè)分配格。,3．分配格的性質(zhì) 定理7-13 設(shè) 1， 2， 3是分配格中的任意三個(gè)元素， 那么 當(dāng)且僅當(dāng),證明 若 ，則顯然,反之，設(shè),則,對(duì)于非分配格，

28、定理7－13不成立。,c　 d = c b , c d = c b ， 但 b ≠ d 。,二 有補(bǔ)格 1．最小元素0和最大元素1,例4 是一個(gè)格，但這個(gè)格既無(wú)最小元素，又無(wú)最大元素。,這個(gè)格有最小元素，但沒(méi)有最大元素。,格中無(wú)論U是什么樣的集合，均有最小元素φ和最大元素U。,具有最小元素和最大元素的格稱(chēng)為有界格。,在有界格中，對(duì)任意L，有0≤ ，

29、 ≤1.,于是由定理7-3，對(duì)任意 ，有,2．補(bǔ)元素 定義7-9 設(shè)是一個(gè)有界格， L，若存在元素 L，使得 =1 = 0，則稱(chēng) 是 的補(bǔ)元素。,因?yàn)閷?duì)任意S∈2U， 所以S的補(bǔ)集 是S的補(bǔ)元素。,例6 格 是一個(gè)有補(bǔ)格，,3．有補(bǔ)格 定義7-10 設(shè)是一個(gè)有界格，如果L中每一個(gè)元素都有補(bǔ)

30、元素，則稱(chēng)是有補(bǔ)格。,(a)是分配格，但不是有補(bǔ)格，,(c)既是有補(bǔ)格，又是分配格；,例7 是有補(bǔ)分配格。,三、有補(bǔ)分配格 若格既是分配格，又是有補(bǔ)格，則稱(chēng)為有補(bǔ)分配格,(d)是有補(bǔ)格，但不是分配格。,(b)既不是分配格，又不是有補(bǔ)格；,有補(bǔ)分配格有如下一些性質(zhì)： 定理7-14 在有補(bǔ)分配格中，任一元素的補(bǔ)元素是唯一的。,使得 , ，

31、 ,,于是 ， ， 由定理 7-13 .,我們記 的補(bǔ)元素為 。,證明 假設(shè) 有兩個(gè)補(bǔ)元素 和 ，,定理7-15 （對(duì)合律） 在有補(bǔ)分配格中，對(duì)每一個(gè) ， 有 。,證明 因?yàn)?

32、 ，由交換律有 .,所以 是 的補(bǔ)元素，由補(bǔ)元素的唯一性,故有 。,定理7-16 （德·摩根定律） 在有補(bǔ)分配格中，對(duì)于任意的 (a) (b),證明 （a）,由補(bǔ)元素的唯一性有,練習(xí)5-61、填空 （1）下圖所表示的格中    ①

33、 d 有 個(gè)補(bǔ)元素，它們分別是___________. ② a 有 個(gè)補(bǔ)元素，它們是 . ③ b 的補(bǔ)元素是 。,3 　 a、b、c,1 d,d,B,B,A,7.4 布爾代數(shù)一 布爾代數(shù)的定義 定義7-10 如果一個(gè)格是有補(bǔ)分配格，

34、則稱(chēng)其為布爾代數(shù)，一般記作。,（1）交換律：,（3) 等冪律：,（4）吸收律：,（2）結(jié)合律：,布爾代數(shù)具有如下性質(zhì)，對(duì)于B中任意元素x，y，z，有,（5）分配律：,（8）互補(bǔ)律：,（9）對(duì)合律：,（10）德·摩根定律：,例8 全集合 U 的冪集 2U 上定義的集合的并，交和補(bǔ)運(yùn)算與 2U 構(gòu)成的代數(shù)系統(tǒng)稱(chēng)作集合代數(shù)，它是一個(gè)布爾代數(shù)，,定義7-11 設(shè)是一個(gè)代數(shù)系統(tǒng)， 和 是B上的二元運(yùn)算，- 是一元運(yùn)算，若

35、這些運(yùn)算滿(mǎn)足交換律，分配律，同一律和互補(bǔ)律，則稱(chēng)是布爾代數(shù)。,二、布爾代數(shù)的性質(zhì) 定理7-21 布爾代數(shù)的每一子代數(shù)都是布爾代數(shù)。,定理7-23 每一有限布爾代數(shù)都有2n（n∈Z）個(gè)元素，元素個(gè)數(shù)相同的布爾代數(shù)必同構(gòu)。,定理7-22 布爾代數(shù)的每一滿(mǎn)同態(tài)象也是布爾代數(shù)。,例9 設(shè),,則 和,等都是例8中 的子代數(shù).

36、,練習(xí)5-7 1．  在下列各題后面的括號(hào)中鍵入“Y”或“N”來(lái)回答 各題中相應(yīng)的問(wèn)題。 （1）      設(shè)是一個(gè)五元素的分配格，問(wèn)該格 是有補(bǔ)格嗎？　　　　　?。ā　。?（2）  設(shè)是一個(gè)九元素的有補(bǔ)格，問(wèn)該格

37、 是分配格嗎？ 　　　　 （　?。?（3）       U={a,b,c}，<2U ；　　　　是布爾代數(shù)嗎？( ) (4) 上題的<2U； 　的子代數(shù)是布爾代數(shù)嗎？ (

38、 ),N,N,Y,Y,1．證明在一個(gè)獨(dú)異點(diǎn)中所有左可逆元的集合形成一個(gè)子獨(dú)異點(diǎn)。,證明 設(shè)H是獨(dú)異點(diǎn)中所有左可逆元的集合，,e 是的單位元。因?yàn)閑*e=e，所以e是左可逆元，故e∈H且H非空。,有a*b∈H, 故是的子獨(dú)異點(diǎn)。,設(shè)a,b∈H，則必存在元素 ， ∈S，使得 * a = e , * b = e ,于是,（ * )*（a*b）= *( *a)*b = *b = e

39、 因此元素 a * b 也存在左逆元 * ，,例 題,2．下列的代數(shù)系統(tǒng)中，哪些構(gòu)成群？在是 群的情況下，指出其單位元并確定每個(gè)元素的逆元。 （1） G={1,3,4,5,9}，* 是按模11的乘法 （2） G=Q，* 是通常的加法； （3） G=Q，* 是通常的乘法； （4） G=I，* 是通常的減法；,解 （1） 是群，其中1是單位元，3與4互為逆元，

40、 5與9互為逆元，1以自身為逆元。,是群，其中0是單位元，任一有理數(shù)q的 逆元是 -q 。,(3) 不是群，因?yàn)?沒(méi)有逆元。,(4) 不是群，因?yàn)?不可結(jié)合。,3． 試證明在一個(gè)有限群里，周期大于2的元素 個(gè)數(shù) 一定是偶數(shù)個(gè)。,證明 設(shè)是一有限群，若元素a的周期 大于2，則a2≠e,因而a≠a-1 ，即a不 以自己為逆元，,而且a-1也是周期大于2的元素，又

41、由逆元的唯一性，因此周期大于2的元素必成對(duì)出現(xiàn)，故個(gè)數(shù)必為偶數(shù)。,4． 設(shè)和是偏序集，按下面方式定義 L1 ×L2上的關(guān)系≤：對(duì)于所有的（ 1 ， 2）， （ 1 ， 2）∈L1 ×L2，有(（ 1 ， 2）≤（ 1 ， 2）) ? ( 1≤ 1， 2≤ 2 ) 試證明是偏序集。,證明 對(duì)于任意的（ 1 ， 2）∈ L1 × L2 ，

42、 因?yàn)?1 ≤ 1 ， 2 ≤ 2 所以（ 1 ， 2）≤（ 1 ， 2）,對(duì)于任意的（ 1 ， 2）,（ 1， 2）∈L1×L2 ，如果（ 1， 2）≤( 1， 2）且（ 1 ， 2）≤（ 1 ， 2），則有 1 ≤ 1， 2 ≤ 2 且 1≤ 1， 2 ≤ 2 ， 由反對(duì)稱(chēng)性得 1= 1 ， 2= 2，