離散數(shù)學(xué)課件

格與布爾代數(shù)第七章§7.1

格的基本概念及性質(zhì)如果x,y

S,{x,y}都有最小上界和最大下界,則稱<S,>是一個(gè)格,通常記：{x,y}的最大下界為x

y{x,y}的最小上界為x

y格：設(shè)<S,>是偏序集.例7.1設(shè)n為正整數(shù),Sn是n的正因子的集合,D為整除關(guān)系,驗(yàn)證<Sn,D>是格,并舉例說(shuō)明：解：首先<Sn,D>顯然是自反的,反對(duì)稱的,傳遞的,從而是偏序集；其次

x,y

Sn,由于x與y的最小公倍數(shù)[x,y]仍屬于Sn,x與y的最大公約數(shù)(x,y)仍屬于Sn,且x

y=[x,y]x

y=(x,y)所以<Sn,D>是一個(gè)格,如n=8,6,30時(shí),分別有下圖：<S8,D>8421<S6,D>6231<S30,D>7.2判斷下列偏序集是否構(gòu)成格,說(shuō)明為什么？efdcab(1)解:

不是格,e

f

不存在；解:是格(任何兩個(gè)元素都有最小上界和最大下界)；ebcda(2)解:不是格,d

e

不存在,d,e有三個(gè)下界a,b,c,但沒(méi)有最大的；fdbcea(3)51234(4)解:

不是格,3

2不存在.格的性質(zhì)：(1)設(shè)f為含有格中的元素及符號(hào),,,

,

的關(guān)系式.f

是將f中的“”改成“”,“”改成“”,“

”改成“

”,“

”改成“

”后所得的關(guān)系式,稱之為f的對(duì)偶式.如果f為真,則f

也為真命題–––格的對(duì)偶原理.

(2)設(shè)<A,>是格,a,b,c是A中任意元素,則有：冪等律：

a

a=a,a

a=a交換律：

a

b=b

a,a

b=b

a結(jié)合律：(a

b)

c=a

(b

c),(a

b)

c=a

(b

c)吸收律：

a

(a

b)=a,a

(a

b)=a保序性：

b

c,則a

b

a

c,a

b

a

c分配不等式：a

(b

c)(a

b)

(a

c),a

(b

c)(a

b)

(a

c)(3)a

b

a

b=a,a

b=b(4)A的任意有限子集S均有最大下界和最小上界,我們只證明結(jié)合律、等冪律、吸收律,其他證明可參看教材.證明：(a

b)

c=a

(b

c)由最小上界的定義：(a

b)

c(a

b)a(1)(a

b)

c(a

b)b(2)(a

b)

c

c(3)由(2)(3)可得：(a

b)

c

b

c(4)再由(1)(4)可得：(a

b)

c

a

(b

c)仿照上述過(guò)程,再證：a

(b

c)(a

b)

c從而：(a

b)

c=a

(b

c)類似地,不難證明：(a

b)

c=a

(b

c)證明：a

a=a

a

a=a由最小上界的定義：a

a

a(1)又因?yàn)閍

a

所以a

a

a(2)綜合(1)(2),根據(jù)偏序的反對(duì)稱性知：a

a=a同理可得：a

a=a證明：a

(a

b)=a

a

(a

b)=a首先：a

(a

b)a

顯然成立又由于a

a,a

b

a

所以有a

(a

b)a這樣a

(a

b)

=a同理可證：a

(a

b)=a§7.2特殊格完全格：格<A,>中A的任意子集(不要求有限)均有最大下界和最小上界,則稱<A,>是完全格.如：(1)<S8,D>,其中D為整除關(guān)系,S8為8的所有正因子構(gòu)成的集合.8421<S8,D>6123<S6,D>完全格的性質(zhì)：完全格中,存在唯一最大元和最小元,分別記作1和0.有界格：在格<A,>中,如果存在最大元1和最小元0,則稱之為有界格,并記之為<A,,0,1>.分配格：設(shè)<A,>是格,如果a,b,c

A

有a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)則稱<A,>為分配格.如：<P(s),>是分配格.例7.3試判斷下列圖對(duì)應(yīng)的格是否為分配格：fdbce(2)(3)(4)ahgabcdeabdceba(1)c解：(1)a

b=b,b

c=c,a

c=c；a

b=a,b

c=b；a

c=a

從而可以驗(yàn)證：a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)改變a,b,c的位置同樣成立.所以(1)是分配格.(2)同(1)可以驗(yàn)證(2)是分配格.ba(1)cfdbce(2)ahg(3)由于(3)中a

(b

c)=a

e=a

(a

b)

(a

c)=d

d=d

所以(3)不是分配格.(4)由于(4)中b

(a

c)=b

e=b

(b

a)

(b

c)=d

c=c所以(4)也不是分配格.(3)abcde(4)abdce分配格的判定：設(shè)<A,>是一個(gè)有界格,對(duì)于a

A,如果存在b

A使a

b=1和a

b=0,則稱b是a的補(bǔ)元,顯然b是a的補(bǔ)元時(shí),a也是b的補(bǔ)元.任何全序集(或稱線序集)一定是分配格.補(bǔ)元：例7.4

在下圖對(duì)應(yīng)的格中,哪些元素有補(bǔ)元,哪些元素沒(méi)有補(bǔ)元？gabcdef解：由圖可知,它所對(duì)應(yīng)的格為有界格,b

f=g=1,b

f=a=0所以b與f互補(bǔ)；c

e=g=1,c

e=a=0所以c與e互補(bǔ)；d

e=g=1,d

e=a=0所以d與e互補(bǔ)；b沒(méi)有補(bǔ)元.最大元為g,最小元為a,因此,a,g互為補(bǔ)元,此外：例7.5指出下列有界格中,哪些元有補(bǔ)元？哪些元無(wú)補(bǔ)元？(1)11a1a2a3a3a2a100(2)解：(1)a1,a2,a3都沒(méi)有補(bǔ)元,0與1互補(bǔ)；(2)a1,a2,a3為補(bǔ)元,0與1互補(bǔ).有補(bǔ)格：設(shè)<A,,0,1>是有界格,如果A的每個(gè)元素都至少有一個(gè)補(bǔ)元素,則稱該格為有補(bǔ)格.例如：下面三個(gè)格都是有補(bǔ)格.ab10(1)abcd10(2)10adcb(3)布爾格：如果<A,>既是分配格又是有補(bǔ)格,布爾格的性質(zhì)：<A,

>是布爾格,則：

例如：冪集格<P(A),

>是布爾格.證明：設(shè)a1,a2是a在A中的兩個(gè)補(bǔ)元,則a

a1=1

a

a1=0因而a

a1=a

a2

a

a1=a

a2由于a1=a1

(a

a1)=(a

a2)

(a1

a2)=(a

a2)

a2=a2

所以矛盾.(上述證明過(guò)程說(shuō)明“消去律”成立)a

a2=1

a

a2=0=a1

(a

a2)=(a1

a)

(a1

a2)=(a

a1)

a2

證明：

a

A,由于a與互補(bǔ),所以

證明：只要證：只要利用格的性質(zhì)即可.

證明:

(i)(ii)從而

(ii)(iii)(iii)(i)

§7.3布爾代數(shù)

與

是A上的兩個(gè)二元運(yùn)算,對(duì)于任意的a,b,c

A,如果：(1)交換律：a

b=b

a,a

b=b

a(2)分配律：a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)布爾代數(shù)：設(shè)A是一個(gè)集合,|A|2,(3)同一律：0,1

A,對(duì)于A中任意元素aa

1=a,a

0=a(4)互補(bǔ)律：對(duì)于A中任意元素a,存在,使成立,則稱<A,

,

,,,>為布爾代數(shù),具有有限個(gè)元素的布爾代數(shù)叫做有限布爾代數(shù).

布爾格與布爾代數(shù)：布爾格就是布爾代數(shù).布爾常元：設(shè)<A,

,

,,,>是布爾代數(shù),A中的元素稱為布爾常元.布爾變?cè)涸O(shè)<A,

,

,,,>是布爾代數(shù),在A中取值的變?cè)Q為布爾變?cè)?布爾表達(dá)式：設(shè)<A,

,

,,,>是布爾代數(shù),在這個(gè)布爾代數(shù)上可定義布爾表達(dá)式：(1)A中任何布爾常元是布爾表達(dá)式(2)任何布爾變?cè)且粋€(gè)布爾表達(dá)式(4)只有有限次地使用規(guī)則(1),(2),(3)構(gòu)造的符號(hào)串都是布爾表達(dá)式.(3)如果e1和e2是布爾表達(dá)式,則,(e1

e2),(e1

e2)也是布爾表達(dá)式.n元布爾表達(dá)式：一個(gè)含有n個(gè)相異布爾變?cè)牟紶柋磉_(dá)式,稱為n元布爾表達(dá)式,記作：E(x1,x2,…,xn),其中,x1,x2,…,xn是相異布爾變?cè)?布爾表達(dá)式賦值：用A中的元素作為n元布爾表達(dá)式中變?cè)獂i(i