離散數(shù)學第11章課件-高等教育出版社-屈婉玲-耿素云-張立昂主編

1、1,第十一章 格與布爾代數(shù),主要內(nèi)容格的定義及性質(zhì) 子格分配格、有補格布爾代數(shù),2,11.1 格的定義與性質(zhì),定義11.1 設(shè)是偏序集，如果?x,y?S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序?作成一個格. （偏序關(guān)系P126）求{x,y} 最小上界和最大下界看成 x 與 y 的二元運算∨和∧，,例1 設(shè)n是正整數(shù)，Sn是n的正因子的集合. D為整除關(guān)系，則偏序集構(gòu)成格. ?x,y∈Sn，x∨y是lcm

2、(x,y)，即x與y的最小公倍數(shù). x∧y是gcd(x,y)，即x與y的最大公約數(shù).,3,圖2,例2 判斷下列偏序集是否構(gòu)成格，并說明理由.(1) ，其中P(B)是集合B的冪集.(2) ，其中Z是整數(shù)集，≤為小于或等于關(guān)系.(3) 偏序集的哈斯圖分別在下圖給出.,實例,(1) 冪集格. ?x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y. (2) 是格. ?x,y∈Z，x∨y = max(x,y)，x∧y = mi

3、n(x,y)，(3) 都不是格. 可以找到兩個結(jié)點缺少最大下界或最小上界,4,格的性質(zhì)：算律,定理11.1 設(shè)是格, 則運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律, 即(1) ?a,b∈L 有 a∨b = b∨a, a∧b = b∧a(2) ?a,b,c∈L 有(a∨b)∨c = a∨(b∨c), (a∧b)∧c = a∧(b∧c)(3) ?a∈L 有

4、 a∨a = a, a∧a = a(4) ?a,b∈L 有 a∨(a∧b) = a, a∧(a∨b) = a,5,格的性質(zhì)：序與運算的關(guān)系,定理11.3 設(shè)L是格, 則?a,b∈L有a ? b ? a∧b = a ? a∨b = b 可以用集合的例子來驗證 冪集格，其中P(B)是集合B的冪集.冪集格. ?x,y∈P(B)，x∨y就是x∪y，

5、x∧y就是x∩y.,6,格的性質(zhì)：保序,定理11.4 設(shè)L是格, ?a,b,c,d∈L，若a ? b 且 c ? d, 則 a∧c ? b∧d, a∨c ? b∨d,例4 設(shè)L是格, 證明?a,b,c∈L有 a∨(b∧c) ? (a∨b)∧(a∨c).,證 a∧c ? a ? b, a∧c ?

6、c ? d 因此 a∧c ? b∧d. 同理可證 a∨c ? b∨d,證 由 a ? a, b∧c ? b 得 a∨(b∧c) ? a∨b由 a ?a, b∧c ? c 得 a∨(b∧c) ? a∨c從而得到a∨(b∧c) ? (a∨b)∧(a∨c) （注意最大下界）注意：一般說來, 格中的∨和∧運算不滿足分配律.,7,格作為代數(shù)系統(tǒng)的定義,定理11.4 設(shè)是具有兩個二元運算的代數(shù)系統(tǒng)

7、, 若對于?和?運算適合交換律、結(jié)合律、吸收律, 則可以適當定義S中的偏序 ?,使得 構(gòu)成格, 且?a,b∈S 有 a∧b = a?b, a∨b = a?b.證明省略. 根據(jù)定理11.4, 可以給出格的另一個等價定義.,定義11.3 設(shè)是代數(shù)系統(tǒng), ?和?是二元運算, 如果?和?滿足交換律、結(jié)合律和吸收律, 則構(gòu)成格.,8,11.2 分配格、有補格與布爾代數(shù),定義11.5 設(shè)是

8、格, 若?a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c)  a∨(b∧c) = (a∨b)∧(a∨c) 則稱L為分配格.注意：可以證明以上兩個條件互為充分必要條件,L1 和 L2 是分配格, L3 和 L4不是分配格. 稱 L3為鉆石格, L4為五角格.,實例,9,有界格的定義,定義11.6 設(shè)L是格,(1) 若存在a∈L使得?x∈L有 a ? x, 則稱

9、a為L的全下界(2) 若存在b∈L使得?x∈L有 x ? b, 則稱b為L的全上界 說明：格L若存在全下界或全上界, 一定是惟一的. 一般將格L的全下界記為0, 全上界記為1.定義11.7 設(shè)L是格,若L存在全下界和全上界, 則稱L 為有界格, 一般將有界格L記為.,10,,定理11.6 設(shè)是有界格, 則?a∈L有a∧0 = 0, a∨0 = a, a∧1 = a, a∨1 = 1,注意：有限格L

10、={a1,a2,…,an}是有界格, a1∧a2∧…∧an是L的全下界, a1∨a2∨…∨an是L的全上界. 0是關(guān)于∧運算的零元,∨運算的單位元；1是關(guān)于∨運算的零元,∧運算的單位元.,有界格的性質(zhì),11,有界格中的補元及實例,定義11.8 設(shè)是有界格, a∈L, 若存在b∈L 使得 a∧b = 0 和 a∨b = 1 成立, 則稱b是a的補元.注意：若b是a的補元, 那么a也是b的補元. a和b互為補元

11、.,例7 考慮下圖中的格. 針對不同的元素，求出所有的補元.,12,解答,(1) L1中 a 與 c 互為補元, 其中 a 為全下界, c為全上界, b 沒有 補元.(2) L2中 a 與 d 互為補元, 其中 a 為全下界, d 為全上界, b與 c 也互為補元.(3) L3中a 與 e 互為補元, 其中 a 為全下界, e 為全上界, b 的補 元是 c 和 d ; c 的補元是

12、b 和 d ; d 的補元是 b 和 c ; b, c, d 每個元素都有兩個補元. (4) L4中 a 與 e 互為補元, 其中 a 為全下界, e 為全上界, b 的補 元是 c 和 d ; c 的補元是 b ; d 的補元是 b .,13,有界分配格的補元惟一性,定理11.7 設(shè)是有界分配格. 若L中元素 a 存在補元, 則存在惟一的補元.證 假設(shè) c 是 a 的補元, 則有

13、  a∨c = 1, a∧c = 0, 又知 b 是 a 的補元, 故  a∨b = 1, a∧b = 0 從而得到 a∨c = a∨b, a∧c = a∧b, 由于L是分配格.b=b ∧ (b∨a) = b ∧ (c∨a )= (b ∧ c)∨ (b ∧ a )= (a∨c ) ∧c=c,,注意：在任何有界格中, 全下界0與全上界1互補.對于一般元素, 可能存在補元, 也可能不存在補

14、元. 如果存在補元, 可能是惟一的, 也可能是多個補元. 對于有界分配格, 如果元素存在補元, 一定是惟一的.,14,圖9,有補格的定義,定義11.9 設(shè)是有界格, 若L中所有元素都有補元存在, 則稱L為有補格. 例如, 圖中的L2, L3和L4是有補格, L1不是有補格.,15,布爾代數(shù)的定義與實例,定義11.10 如果一個格是有補分配格, 則稱它為布爾格或布爾代數(shù). 布爾代數(shù)標記為, ?為求補運算.,例8 設(shè) S110

15、 = {1, 2, 5, 10, 11, 22, 55, 110}是110的正因子集合，gcd表示求最大公約數(shù)的運算，lcm表示求最小公倍數(shù)的運算，問是否構(gòu)成布爾代數(shù)？為什么？,解 畫出哈斯圖？ (1) 不難驗證S110關(guān)于gcd 和 lcm 運算構(gòu)成格. (略)(2) 驗證分配律 ?x, y, z∈S110 有 gcd(x, lcm(y, z)) = lcm(gcd(x, y), gcd(x, z)) (3)

16、 驗證它是有補格, 1作為S110中的全下界, 110為全上界, 1和110互為補元, 2和55互為補元, 5和22互為補元, 10和 11互為補元, 從而證明了為布爾代數(shù).,16,布爾代數(shù)的性質(zhì),定理11.8 設(shè)是布爾代數(shù), 則(1) ?a∈B, (a?)? = a .(2) ?a,b∈B, (a∧b)? = a?∨b?, (a∨b) ?= a?∧b? （德摩根律）,證 (1) (a?)?是a?的補元

17、, a也是a?的補元. 由補元惟一性得(a?)?=a. (2) 對任意a, b∈B有  (a∧b)∨(a?∨b?) = (a∨a?∨b?)∧(b∨a?∨b?) = (1∨b?)∧(a?∨1) = 1∧1 = 1, (a∧b)∧(a?∨b?) = (a∧b∧a?)∨(a∧b∧b?) = (0∧b)∨(a∧0) = 0∨0 = 0a?∨b?是a∧b的補元, 根據(jù)補元惟一性有(a∧b)? = a?∨b?, 同

18、理可證 (a∨b)? = a?∧b?. 注意：德摩根律對有限個元素也是正確的.,17,圖11,實例,下圖給出了 1 元, 2 元, 4 元和 8 元的布爾代數(shù).,18,第十一章 習題課,主要內(nèi)容格的兩個等價定義格的性質(zhì)子格特殊格：分配格、有界格、有補格、布爾代數(shù)基本要求能夠判別給定偏序集或者代數(shù)系統(tǒng)是否構(gòu)成格能夠確定一個命題的對偶命題能夠證明格中的等式和不等式能判別格L的子集S是否構(gòu)成子格能夠判別給定的格是否為

19、分配格、有補格能夠判別布爾代數(shù)并證明布爾代數(shù)中的等式,19,解,1．求圖中格的所有子格.,1元子格：{ a },{ b },{ c },{ d },{ e }；2元子格：{ a, b },{ a, c },{ a, d }, { a, e },{ b, c },{ b, d }, { b, e },{ c, e },{ d, e }；3元子格：{ a, b,

20、c },{ a, b, d }, { a, b, e },{ a, c, e }, { a, d, e },{ b, c, e }, { b, d, e }；4元子格：{ a, b, c, e },{ a, b, d, e }, { b, c, d, e }；5元子格： { a, b, c

21、, d, e },練習1,20,L1 L2 L3,圖12,2．針對下圖，求出每個格的補元并說明它們是否為有補格,L1中, a與h互為補元, 其他元素沒補元. L2中, a與g互為補元. b的補元為c, d, f；c的補元為b, d, e, f；d的補元為b, c, e；e的補元為c, d, f；f的補元為b, c, e. L3中, a與h互為補元,