離散數(shù)學(xué)第十一章.ppt

1,第十一章 格與布爾代數(shù),主要內(nèi)容 格的定義及性質(zhì) 子格 分配格、有補(bǔ)格 布爾代數(shù),2,11.1 格的定義與性質(zhì),定義11.1 設(shè)是偏序集，如果x,yS，x,y都有最小上 界和最大下界，則稱S關(guān)于偏序作成一個(gè)格. 求x,y 最小上界和最大下界看成 x 與 y 的二元運(yùn)算和，,例1 設(shè)n是正整數(shù)，Sn是n的正因子的集合. D為整除關(guān)系，則 偏序集構(gòu)成格. x,ySn，xy是lcm(x,y)，即x與y的 最小公倍數(shù). xy是gcd(x,y)，即x與y的最大公約數(shù).,3,圖2,例2 判斷下列偏序集是否構(gòu)成格，并說明理由. (1) ，其中P(B)是集合B的冪集. (2) ，其中Z是整數(shù)集，為小于或等于關(guān)系. (3) 偏序集的哈斯圖分別在下圖給出.,實(shí)例,(1) 冪集格. x,yP(B)，xy就是xy，xy就是xy. (2) 是格. x,yZ，xy = max(x,y)，xy = min(x,y)， (3) 都不是格. 可以找到兩個(gè)結(jié)點(diǎn)缺少最大下界或最小上界,4,實(shí)例：子群格,例3 設(shè)G是群，L(G)是G 的所有子群的集合. 即 L(G) = H | HG ， 對任意的H1, H2L(G)，H1H2是G 的子群，是由 H1H2生成的子群（即包含著H1H2的最小子群）. 在L(G)上定義包含關(guān)系，則L(G)關(guān)于包含關(guān)系構(gòu)成一個(gè) 格，稱為G的子群格. 在 L(G)中， H1H2 就是 H1H2 H1H2 就是 ,5,格的性質(zhì)：對偶原理,定義11.2 設(shè) f 是含有格中元素以及符號 =, , ,和的命題. 令 f*是將 f 中的替換成,替換成,替換成,替換成 所得到的命題. 稱 f* 為 f 的對偶命題. 例如, 在格中令 f 是 (ab)cc, f*是 (ab)cc .,格的對偶原理 設(shè) f 是含有格中元素以及符號=,和等的命題. 若 f 對 一切格為真, 則 f 的對偶命題 f*也對一切格為真. 例如, 如果對一切格L都有 a,bL, aba，那么對一切格L 都有 a,bL, aba 注意：對偶是相互的，即 ( f*)*= f,6,格的性質(zhì)：算律,定理11.1 設(shè)是格, 則運(yùn)算和適合交換律、結(jié)合律、 冪等律和吸收律, 即 (1) a,bL 有 ab = ba, ab = ba (2) a,b,cL 有 (ab)c = a(bc), (ab)c = a(bc) (3) aL 有 aa = a, aa = a (4) a,bL 有 a(ab) = a, a(ab) = a,7,證明,(1) ab是 a, b 的最小上界, ba是 b, a 的最小上界. 由于 a, b = b, a , 所以 ab = ba. 由對偶原理, ab = ba.,(2) 由最小上界的定義有 (ab)caba (1) (ab)cabb (2) (ab)cc (3) 由式(2)和(3)有 (ab)cbc (4) 由式(1)和(4)有 (ab)ca(bc) 同理可證 (ab)ca(bc) 根據(jù)反對稱性 (ab)c = a(bc) 由對偶原理, (ab)c = a(bc),8,證明,(3) 顯然 a aa, 又由 a a 可得 aa a. 根據(jù)反對稱性有aa = a . 由對偶原理, aa = a 得證. (4) 顯然 a(ab) a (5) 由 a a, ab a 可得 a(ab) a (6) 由式(5)和(6) 可得 a(ab) = a, 根據(jù)對偶原理, a(ab) = a,9,格的性質(zhì)：序與運(yùn)算的關(guān)系,定理11.2 設(shè)L是格, 則a,bL有 a b ab = a ab = b,證 (1) 先證 a b ab = a 由 a a 和 a b 可知 a 是 a,b 的下界, 故 a ab. 顯然有ab a. 由反對稱性得 ab = a. (2) 再證 ab = a ab = b 根據(jù)吸收律有 b = b(ba) 由 ab = a 和上面的等式得 b = ba, 即 ab = b. (3) 最后證 ab = b ab 由 a ab 得 a ab = b,10,格的性質(zhì)：保序,定理11.3 設(shè)L是格, a,b,c,dL，若a b 且 c d, 則 ac bd, ac bd,例4 設(shè)L是格, 證明a,b,cL有 a(bc) (ab)(ac).,證 ac a b, ac c d 因此 ac bd. 同理可證 ac bd,證 由 a a, bc b 得 a(bc) ab 由 a a, bc c 得 a(bc) ac 從而得到a(bc) (ab)(ac) 注意：一般說來, 格中的和運(yùn)算不滿足分配律.,11,格作為代數(shù)系統(tǒng)的定義,定理11.4 設(shè)是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng), 若對于 和運(yùn)算適合交換律、結(jié)合律、吸收律, 則可以適當(dāng)定義S中 的偏序 ,使得 構(gòu)成格, 且a,bS 有 ab = ab, ab = ab. 證明省略. 根據(jù)定理11.4, 可以給出格的另一個(gè)等價(jià)定義.,定義11.3 設(shè)是代數(shù)系統(tǒng), 和是二元運(yùn)算, 如果 和滿足交換律、結(jié)合律和吸收律, 則構(gòu)成格.,12,子格及其判別法,定義11.4 設(shè)是格, S是L的非空子集, 若S關(guān)于L中的運(yùn)算和仍構(gòu)成格, 則稱S是L的子格.,例5 設(shè)格L如圖所示. 令 S1=a, e, f, g, S2=a, b, e, g S1不是L的子格, 因?yàn)閑, fS1 但 ef = cS1. S2是L的子格.,13,11.2 分配格、有補(bǔ)格與布爾代數(shù),定義11.5 設(shè)是格, 若a,b,cL,有 a(bc) = (ab)(ac) a(bc) = (ab)(ac) 則稱L為分配格. 注意：可以證明以上兩個(gè)條件互為充分必要條件,L1 和 L2 是分配格, L3 和 L4不是分配格. 稱 L3為鉆石格, L4為五角格.,實(shí)例,14,分配格的判別及性質(zhì),定理11.5 設(shè)L是格, 則L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格 或五角格同構(gòu)的子格. 證明省略. 推論 (1) 小于五元的格都