格與布爾代數(shù)

格與布爾代數(shù)第1頁，課件共65頁，創(chuàng)作于2023年2月中的應(yīng)用開創(chuàng)了先河,自此以后布爾代數(shù)在自動(dòng)推理和邏輯電路設(shè)計(jì)的分析和優(yōu)化等問題的討論中都有著最直接的應(yīng)用,作為計(jì)算機(jī)設(shè)計(jì)基礎(chǔ)的《數(shù)字邏輯》就是布爾代數(shù).本章先介紹格,在此基礎(chǔ)上引入分配格和有補(bǔ)格,而把布爾代數(shù)作為一種特殊的格加以討論.第2頁，課件共65頁，創(chuàng)作于2023年2月6.1用偏序集定義的格1.格的第一種定義偏序集(L,

)?Remark偏序集(L,

)中不是任意兩個(gè)元素均存在上確界及下確界的.{c,b},{a,d}?第3頁，課件共65頁，創(chuàng)作于2023年2月Def設(shè)(L,

)是偏序集,若L中任意兩個(gè)元素都存在上確界以及下確界,則稱(L,

)是格(lattice).為了方便,這樣的格可稱為偏序格.(Figure6-3)鉆石格與五角格?課堂練習(xí)習(xí)題6.11.第4頁，課件共65頁，創(chuàng)作于2023年2月例6-1(P170)

證明:(P(X),

)是格,其中P(X)是集合X的冪集.Proof(cf.Chapter1)

A,B

P(X),(1)sup{A,B}=A

B,(2)inf{A,B}=A

B.第5頁，課件共65頁，創(chuàng)作于2023年2月例6-2(P170)

證明:(Dn,|)是格,其中Dn是自然數(shù)n的正因數(shù)組成的集合,|是其上的整除關(guān)系.Proof(cf.Chapter2)第6頁，課件共65頁，創(chuàng)作于2023年2月例6-3(P170)

令F是所有合式公式(WFF)組成的集合,

是公式間的邏輯蘊(yùn)涵關(guān)系,則(F,

)是格.Proof(cf.Chapter3)

A,B

F,(1)sup{A,B}=A

B,(2)inf{A,B}=A

B.第7頁，課件共65頁，創(chuàng)作于2023年2月2.格的性質(zhì)Def設(shè)(L,

)是格,x+y=sup{x,y},x

?

y=inf{x,y}.格中的“+”是求上確界運(yùn)算,可以看作是格的加法運(yùn)算,讀作“加”；同樣,格中的“

”是求下確界運(yùn)算,可以看作是格的乘法運(yùn)算,讀作“乘”.(與環(huán)中的“加”和“乘”,以及數(shù)的“加”和“乘”不同)(與布爾代數(shù)的運(yùn)算一致)第8頁，課件共65頁，創(chuàng)作于2023年2月由于“上確界

上界”以及“下界

下確界”,根據(jù)定義易知Theorem6-1設(shè)(L,

)是格,則對(duì)于任意x,y

L,有(1)x

x+y,y

x+y.(2)x

?y

x,x

?y

y.第9頁，課件共65頁，創(chuàng)作于2023年2月(L,

)與(L,

)?Def

對(duì)于任意關(guān)于格(L,

)的命題,將命題前提和結(jié)論中的(1)

改為

;(2)+改為

;(3)

改為+；(4)0改為1；(5)1改為0所得到的命題稱為原命題的對(duì)偶命題.Theorem6-2對(duì)于任意關(guān)于格(L,

)的真命題,其對(duì)偶命題亦為真.如(1)x

x+y,y

x+y;(2)x

?y

x,x

?y

y.在格的性質(zhì)中,有很多都是成對(duì)(dual)出現(xiàn)的.第10頁，課件共65頁，創(chuàng)作于2023年2月Theorem6-3(保序性)設(shè)(L,

)是格,對(duì)于任意xi,yi

L,i=1,2:Proof(1)x1+x2是{x1,x2}的上確界;(2)y1+y2是{x1,x2}的上界:Theorem6-4(冪等性)設(shè)(L,

)是格,

x

L,x+x=x,x

?x=x.

第11頁，課件共65頁，創(chuàng)作于2023年2月格的特征性質(zhì).Theorem6-5格(L,

)滿足:(1)交換性.(2)結(jié)合性.(3)吸收性.Proof(3)x

x,x

?y

x

x+(x

?y)

x;顯然,x

x+(x

?y),所以x+(x

?y)=x.x?(x

+y)=x?(仿上;對(duì)偶)第12頁，課件共65頁，創(chuàng)作于2023年2月Theorem6-6設(shè)(L,

)是格,則對(duì)于任意x,y

L,下列三個(gè)命題等價(jià):(1)x

y.(2)x+y=y.(2)x

?y

=x.Proof(1)(2):x

y,y

y

x+y

y.顯然,y

x+y

x+y=y.(2)(3):x

?(x+y)=x

?y

x

?y

=x.(3)(1):x=x

?y

y.第13頁，課件共65頁，創(chuàng)作于2023年2月3.格的保序映射Def設(shè)(L1,

1)和(L2,

2)是格{偏序集即可},若存在

:L1

L2,則稱

為(L1,

1)到(L2,

2)的保序映射.例6-4(P173)?作業(yè)習(xí)題6.13,6,7.第14頁，課件共65頁，創(chuàng)作于2023年2月6.2用代數(shù)結(jié)構(gòu)定義的格1.格的第二種定義Def設(shè)(L,+,?)是代數(shù)結(jié)構(gòu),+和

是L上的兩個(gè)2元運(yùn)算,同時(shí)滿足:(1)交換性.(2)結(jié)合性.(3)吸收性.則稱(L,+,?)為格,稱這樣定義的格為代數(shù)格.由定義知,格是具有兩個(gè)2元運(yùn)算的代數(shù)結(jié)構(gòu).第15頁，課件共65頁，創(chuàng)作于2023年2月為了下面的應(yīng)用,首先證明兩個(gè)命題.命題1設(shè)(L,+,?)是代數(shù)結(jié)構(gòu),+和

是L上的兩個(gè)2元運(yùn)算,若+和

相互可吸收,則+和

具有冪等性.Hint命題2設(shè)(L,+,?)是代數(shù)結(jié)構(gòu),+和

是L上的兩個(gè)2元運(yùn)算,若+和

相互可吸收,則

x,y

L,x

?y=x

x+y=y.第16頁，課件共65頁，創(chuàng)作于2023年2月2.格的兩種定義的等價(jià)性格的這兩種定義是否是一回事?Theorem6-7偏序格(L,

)與代數(shù)格(L,+,?)是等價(jià)的.Proof(

)(

)(1)

是偏序.

自反(命題1).反對(duì)稱.

傳遞.第17頁，課件共65頁，創(chuàng)作于2023年2月(2)對(duì)于任意x,y

L,x

?y是{x,y}的下確界.(3)對(duì)于任意x,y

L,x

+y是{x,y}的上確界.

x,y

L,x

y

x

?y=x

x+y=y(命題2).第18頁，課件共65頁，創(chuàng)作于2023年2月3.子格設(shè)(L,

)是格,

M

L,在M上的限制仍記為.有例子表明,(M,

)不一定是格.例6-5X={a,b},M={,{a},}P(X).(P(X),

).(M,

)不是格.例6-6X={a,b,c},M=P(X)–{c}.(P(X),

).(M,

)是格.第19頁，課件共65頁，創(chuàng)作于2023年2月借助于子代數(shù)給子格下的定義:Def設(shè)(L,+,?)是格,

M

L,若(M,+,?)是格,則稱(M,+,?)為(L,+,?)的子格(sublattice).顯然,(M,+,?)為(L,+,?)的子格

M關(guān)于+和?封閉.Remark設(shè)(L,+,?)是格,

M

L,(M,)是格與(M,)是子格存在差異.正因?yàn)檫@樣,才借助于子代數(shù)對(duì)子格定義.第20頁，課件共65頁，創(chuàng)作于2023年2月4.格的同態(tài)與同構(gòu)可以類似地定義格的同態(tài)與同構(gòu).Def設(shè)(L1,+,?)和(L2,

,⊙)是格,若存在

:L1

L2,分

別保持格的求上確界運(yùn)算和求下確界運(yùn)算,則稱

為(L1,+,?)到(L2,

,⊙)的格同態(tài)映射.格同構(gòu)的直觀意義?Theorem6-8格同態(tài)映射是保序映射.第21頁，課件共65頁，創(chuàng)作于2023年2月Remark格的保序映射不一定是格同態(tài)映射(習(xí)題).可以考慮格同構(gòu)映射與格保序映射之間的關(guān)系.作業(yè)習(xí)題6.21,4,6,8.第22頁，課件共65頁，創(chuàng)作于2023年2月6.3分配格1.分配格(distributivelattice)的定義有例子表明,格不滿足分配性.例

6-9

舉例說明在格(L,)中,格的乘法運(yùn)算“

”和格加法運(yùn)算“+”相互不一定可分配.Solution第23頁，課件共65頁，創(chuàng)作于2023年2月鉆石格?五角格?Theorem6-9(分配不等式)設(shè)(L,)是格,對(duì)于任意x,y,z

L,有(1)x+(y

?z)(x+y)?(x+z).(2)(dual?)

Proof(1)

x+(y

?z)x+y;x+(y

?z)x+z.第24頁，課件共65頁，創(chuàng)作于2023年2月Theorem6-10設(shè)(L,+,?)是格,則格的乘法運(yùn)算“”對(duì)格的加法運(yùn)算“+”可分配格的加法運(yùn)算“+”對(duì)格的乘法運(yùn)算“”可分配.Proof(

)

x,y,z

L:(

)第25頁，課件共65頁，創(chuàng)作于2023年2月Def設(shè)(L,+,?)是格,若格的乘法運(yùn)算“”對(duì)格的加法運(yùn)算“+”可分配(或格的加法運(yùn)算“+”對(duì)格的乘法運(yùn)算“

”可分配),則稱(L,+,?)是分配格.例6-10證明:(P(X),

)是分配格.其他例子?第26頁，課件共65頁，創(chuàng)作于2023年2月鉆石格和五角格是兩個(gè)非常重要的非分配格的例子.我們只給出Theorem6-11設(shè)(L,+,?)是格,則L是分配格的充要條件是L中不含有同構(gòu)于鉆石格和五角格的子格.根據(jù)上述定理有以下兩個(gè)推論.Corollary1小于5個(gè)元素的格為分配格.Corollary2任意鏈?zhǔn)欠峙涓?(可直接證.)第27頁，課件共65頁，創(chuàng)作于2023年2月2.分配格的性質(zhì)Theorem6-12設(shè)(L,+,?)是格,則L是分配格的充要條件是對(duì)于任意x,y,z

L,由x+y=x+z和x

?

y=x

?

z可以推出y=z.Remark由x+y=x+z可以推出y=z?x

?

y=x

?

z?Proof(

)y=y+(x

?z)=(y+x)?(y+z)=(z+x)?(y+z)=(x

?y)+z=(x

?z)+z=z.(

)?判斷一個(gè)格是否分配格?作業(yè)

習(xí)題6.32,5,7,9.第28頁，課件共65頁，創(chuàng)作于2023年2月6.4有補(bǔ)格1.有界格一般來說,格L不一定存在最大元與最小元.例如,實(shí)數(shù)集R關(guān)于數(shù)的小于等于關(guān)系

所作成的格(R,

).Def設(shè)(L,

)是格,若L存在最大元素1以及最小元素0,則稱(L,

)為有界格(boundedlattice).第29頁，課件共65頁，創(chuàng)作于2023年2月例6-12

證明:對(duì)任意集合X,(P(X),

)是有界格.Hint最大元素:X;最小元素:

.顯然,任意有限格是有界格(?).第30頁，課件共65頁，創(chuàng)作于2023年2月2.補(bǔ)元

有補(bǔ)格Def設(shè)(L,+,?)是有界格,a

L,若存在b

L,使得a+b=1且a

?b=0,則稱b為a的補(bǔ)元(complement).顯然,在任意有界格中,若b為a的補(bǔ)元,則a為b的補(bǔ)元；0與1互為補(bǔ)元.但對(duì)于有界格,不是每個(gè)元素均有補(bǔ)元,同時(shí)一個(gè)元素的補(bǔ)元未必唯一.因此,不能定義1元運(yùn)算.第31頁，課件共65頁，創(chuàng)作于2023年2月第32頁，課件共65頁，創(chuàng)作于2023年2月Def

設(shè)(L,+,?)是有界格,若L中每個(gè)元素都有補(bǔ)元,則稱(L,+,?)為有補(bǔ)格(latticecomplemented).例6-14

證明:對(duì)任意集合X,(P(X),

)是有補(bǔ)格.Hint

A

P(X),X-A

P(X):A(X-A)=X,A(X-A)=.右圖是有補(bǔ)格,不是分配格.第33頁，課件共65頁，創(chuàng)作于2023年2月幾個(gè)重要結(jié)論.Theorem6-13在分配格中,若一個(gè)元素存在補(bǔ)元,則補(bǔ)元是唯一的.Clearly.根據(jù)定理6-13知,在有補(bǔ)分配格中,每個(gè)元素都有唯一的補(bǔ)元.正因?yàn)槿绱?在有補(bǔ)分配格中可以定義一個(gè)元素的補(bǔ)運(yùn)算“”，它是其上的1元代數(shù)運(yùn)算.

第34頁，課件共65頁，創(chuàng)作于2023年2月下述定理是有補(bǔ)分配格的重要性質(zhì).Theorem6-14設(shè)(L,+,?)是有補(bǔ)分配格,則DeMorgan律成立,即對(duì)于任意x,y

L,有(1)(2)Proof(1)(2)?第35頁，課件共65頁，創(chuàng)作于2023年2月Theorem6-15設(shè)(L,+,?)是有補(bǔ)分配格,則對(duì)于任意x,y

L,有Proof顯然,(1)x

y:(2)作業(yè)習(xí)題6.4,4,5,6,7.第36頁，課件共65頁，創(chuàng)作于2023年2月6.5布爾代數(shù)1.布爾代數(shù)的格定義Def元素個(gè)數(shù)

2

的有補(bǔ)分配格(B,

)稱為布爾代數(shù)(Booleanalgebra)或布爾格.偏序集與各種格之間的相互關(guān)系?僅1個(gè)元素的有補(bǔ)分配格是布爾代數(shù)的退化情形，一般不作為布爾代數(shù)考慮，可參見布爾代數(shù)的公理化定義.顯然，在任何布爾代數(shù)或布爾格中有兩個(gè)特殊元素，一個(gè)是其最小元0，一個(gè)是其最大元1.當(dāng)然01.第37頁，課件共65頁，創(chuàng)作于2023年2月在任意布爾代數(shù)(B,

)中可以定義3種代數(shù)運(yùn)算:對(duì)于任意x,y

B,(a)布爾加“+”:x+y=sup{x,y}.(b)布爾乘“

”:x?

y=inf{x,y}.(c)布爾補(bǔ)“”:x的補(bǔ)元.例6-16

設(shè)|X|1,證明:(P(X),

)是布爾代數(shù),稱為集合代數(shù):

,X).第38頁，課件共65頁，創(chuàng)作于2023年2月例6-17證明:(F,

)是布爾代數(shù),其中F是所有合式公式組成的集合,

是公式間的邏輯蘊(yùn)涵關(guān)系,稱為邏輯代數(shù),F中的元素是邏輯表達(dá)式:特別地,令G是所有命題公式組成的集合,則稱(G,

)為命題代數(shù).令H是僅含命題變?cè)猵1,p2,…,pn的所有命題公式組成的集合,則(H,

)是布爾代數(shù),這時(shí)由于集合代數(shù)和邏輯代數(shù)都是布爾代數(shù),因此它們有完全相似的性質(zhì).第39頁，課件共65頁，創(chuàng)作于2023年2月2.布爾代數(shù)的性質(zhì)Theorem6-16設(shè)(B,

)是布爾代數(shù),I.(B,

)是格;II.(B,

)是分配格;III.(B,

)是有補(bǔ)格;IV.(B,

)是有補(bǔ)分配格.第40頁，課件共65頁，創(chuàng)作于2023年2月以下是布爾代數(shù)的特征性質(zhì),參見下面的布爾代數(shù)的公理化定義.交換律.分配律.幺元律：有補(bǔ)律：第41頁，課件共65頁，創(chuàng)作于2023年2月3.布爾代數(shù)的公理化定義Def(E.V.Hungtington)設(shè)B是集合,|B|2,“+”和“

”是B上的兩個(gè)2元代數(shù)運(yùn)算,“”是B上的1元代數(shù)運(yùn)算,且滿足(1)交換律.(2)分配律.(3)幺元律:(4)有補(bǔ)律:則稱是布爾代數(shù).Remark按這種定義需強(qiáng)調(diào)兩個(gè)0元運(yùn)算.第42頁，課件共65頁，創(chuàng)作于2023年2月Theorem6-17布爾代數(shù)的兩種定義是等價(jià)的.

Proof只需證明:滿足定義6-13條件的代數(shù)結(jié)構(gòu)是格且0和1分別是其最小元素和最大元素即可,因?yàn)楦鶕?jù)(2)分配律和(4)有補(bǔ)律知是B有補(bǔ)分配格.首先注意,由于定義中的條件是對(duì)偶出現(xiàn)的,所以在該代數(shù)結(jié)構(gòu)中,對(duì)偶原理成立.其次,

x

B,x+1=1.第43頁，課件共65頁，創(chuàng)作于2023年2月再其次,(B,+,?)是格:(1)交換性.(2)吸收性.(3)結(jié)合性.B上定義:第44頁，課件共65頁，創(chuàng)作于2023年2月4.子布爾代數(shù)由于布爾代數(shù)中有兩個(gè)0元運(yùn)算:0和1,有必要對(duì)子布爾代數(shù)給出定義.Def設(shè)是布爾代數(shù),

C

B,若是布爾代數(shù),則稱是的子布爾代數(shù).顯然,對(duì)于布爾代數(shù),

C

B,則C是B的子布爾代數(shù)

0,1

C且C關(guān)于運(yùn)算+,,封閉.第45頁，課件共65頁，創(chuàng)作于2023年2月5.布爾代數(shù)的同態(tài)與同構(gòu)定義兩個(gè)布爾代數(shù)的同態(tài)與同構(gòu)時(shí),同樣要注意布爾代數(shù)中的兩個(gè)0元運(yùn)算:0和1.Def設(shè)和是布爾代數(shù),若存在映射

:B1

B2且

保持所有布爾代數(shù)中的運(yùn)算(1)(2)(3)(4)(5)第46頁，課件共65頁，創(chuàng)作于2023年2月布爾代數(shù)之間的同態(tài)(構(gòu))又稱為布爾同態(tài)(構(gòu)),它要求(1)—(5)都要成立,但實(shí)際上,其中的一些條件可以從別的條件推導(dǎo)出來,見本節(jié)習(xí)題8,9,10.由布爾代數(shù)的同構(gòu)定義容易知道,2個(gè)元素的布爾代數(shù)是最簡單的布爾代數(shù),任意布爾代數(shù)都有同構(gòu)于2個(gè)元素的布爾代數(shù)的子布爾代數(shù).作業(yè)習(xí)題6.51—6,8,9,10.第47頁，課件共65頁，創(chuàng)作于2023年2月6.6有限布爾代數(shù)的結(jié)構(gòu)有限布爾代數(shù)與無限布爾代數(shù)?對(duì)于集合代數(shù)(P(X),

),當(dāng)|X|=n1有限時(shí)P(X)有限,(P(X),

)是有限布爾代數(shù).Theorem(M.H.Stone)設(shè)是有限布爾代數(shù),則存在有限集合X使得與集合代數(shù)

,X)同構(gòu).第48頁，課件共65頁，創(chuàng)作于2023年2月實(shí)際上,集合X是由有限布爾代數(shù)的所有原子組成的集合,先定義一般格上的原子的概念.Def設(shè)(L,

)是格,其最小元素為0,對(duì)于a

L,若a蓋住0,則a稱為格的原子(atom).例子(圖6-16)?第49頁，課件共65頁，創(chuàng)作于2023年2月Property1(P187)Property2(P188)Property3(P188)第50頁，課件共65頁，創(chuàng)作于2023年2月Property4(P188)Property5(P188)Property6(P188)第51頁，課件共65頁，創(chuàng)作于2023年2月ProofoftheStonetheorem:令集合X是由有限布爾代數(shù)的所有原子組成的集合.

(0)=,

單射?

滿射?

保持運(yùn)算?第52頁，課件共65頁，創(chuàng)作于2023年2月由Stone定理有Corollary1任意有限布爾代數(shù)的元素個(gè)數(shù)為2n,其中n為正整數(shù).Corollary2在同構(gòu)意義下,2n個(gè)元素的有限布爾代數(shù)是唯一的,其中n為正整數(shù).作業(yè)習(xí)題6.61—4.第53頁，課件共65頁，創(chuàng)作于2023年2月6.7布爾表達(dá)式布爾表達(dá)式的化簡及其主范式表示在理論研究和實(shí)際應(yīng)用中都有十分重要的意義.1布爾表達(dá)式的定義Def

設(shè)是布爾代數(shù)，則B上的布爾表達(dá)式(Booleanexpression)遞歸定義如下:(1)B中的元素a,b,c等是布爾表達(dá)式.(2)取值于B的變?cè)獂1,x2,…等是布爾表達(dá)式.(3)若e1和e2是布爾表達(dá)式，則,e1+e2,

e1?e2布爾表達(dá)式.(4)有限次使用(1)(2)(3)得到的字符串是僅有的布爾表達(dá)式.第54頁，課件共65頁，創(chuàng)作于2023年2月例

設(shè)B={0,a,b,1},是布爾代數(shù),則等是B上的布爾表達(dá)式.含n個(gè)變?cè)獂1,x2,…,xn的布爾表達(dá)式記為E(x1,x2,…,xn).因此,上例中的兩個(gè)布爾表達(dá)式分別記為邏輯代數(shù)上的布爾表達(dá)式常稱為邏輯表達(dá)式.第55頁，課件共65頁，創(chuàng)作于2023年2月設(shè)B={0,1},是布爾代數(shù),它是最簡單的邏輯代數(shù).在計(jì)算機(jī)邏輯電路設(shè)計(jì)中,B中元素的0和1稱為邏輯常量,B上的變?cè)Q為邏輯變量,B上的布爾表達(dá)式稱為邏輯表達(dá)式,它就是命題公式.例如

等是B上的布爾表達(dá)式.第56頁，課件共65頁，創(chuàng)作于2023年2月2.布爾表達(dá)式的化簡大家知道,在邏輯電