《離散數(shù)學》課件第九章

1、第8講 布爾代數(shù)Boolean Algebra布爾演算（布爾代數(shù)）數(shù)理邏輯Huntington公理布爾代數(shù)格代數(shù)布爾代數(shù)數(shù)學家布爾在邏輯的數(shù)學分析中建立了“布爾代數(shù)”原型的簡化表示含有二個運算, 以及一個一元運算的集合, 并且有兩個特殊的元素0與1, 該集合中任意元素x, y, z, 滿足如下定律：1) 結(jié)合律：x(yz)=x(yz)； x(yz)=x(yz)2) 交換律：xy=yx； xy=yx3) 分配律：x(yz)=(xy)(xz)；x(yz)=(xy)(xz)4) 同一律：x0=x； x1=x 5) 互補律：xx=1； xx=0事實上, 上述代數(shù)結(jié)構(gòu)還滿足包括De.Morgan律在內(nèi)的

2、很多性質(zhì), 但它們(包括結(jié)合律)都可以從2)-5)四條定律推導(dǎo)出來, 而且可以證明2)-5)這四條定律是相互獨立的。布爾代數(shù)一個代數(shù)結(jié)構(gòu)含有二個運算, 以及一個一元運算的集合, 并且有兩個特殊的元素0與1, 如果該代數(shù)結(jié)構(gòu)滿足上述2)-5)四條定律。 其中, 運算“”、“”也可以用+, *來表示, 可以讀作“加”或“合取”、“乘”或“析取”, 運算“”讀作“補”。 主要內(nèi)容1 格2 格是一種代數(shù)結(jié)構(gòu)3 布爾代數(shù)請回憶：偏序結(jié)構(gòu)偏序集、哈斯圖上界、最小上界下界、最大下界最大下界、最小上界若存在，則唯一？ 1 格？示例 1lub(a,b)=glb(a,b)=elub(a,e)=aglb(a,e)=

3、e lub(c,d)=f glb(c,d)= 1 格？格(Lattice)設(shè)L，是偏序集合，若a，bL，都有最大下界、最小上界;則稱L，是格，且記glb(a,b)=ab,lub(a,b)=ab,并稱它們?yōu)榻缓筒ⅰＷ?: 由于最大下界、最小上界若存在則唯一，所以交、并是二元運算?注2: 稱為由格L，所誘導(dǎo)的代數(shù)系統(tǒng)。 1 格？示例 2 1 格？示例 3設(shè)n是一正整數(shù)，Sn是n的所有因子的集合，D是整除關(guān)系,則是格。82442112631248n=8n=241 格？示例 4設(shè)S是任意集合，P(S)是冪集，偏序集合是格，其中A,BP(S),AB=AB, AB=AB. S=a,b S=1,2,31,2

4、,32,331,321,2a,bba11 格？格的基本性質(zhì)1)自反性 aa 對偶: aa2)反對稱性 ab 且 ab a=b 對偶:ab 且 ab a=b3)傳遞性 ab 且 bc ac 對偶:ab 且 bc ac 1 格？格的基本性質(zhì)4) 最大下界描述之一 aba 對偶 aba abb 對偶 abb5）最大下界描述之二 ca,cb cab對偶 ca,cb cab1 格？格的基本性質(zhì)6) 結(jié)合律 a(bc)=(ab)c 對偶 a(bc)=(ab)c證： 令R=a(b c), R=(ab) c 則由4 Ra, Rbc Ra, Rb, Rc Ra b, R c R(ab) c RR 同理可證：RR

5、 所以 R=R注:格的證明思路：總是利用反對稱性。1 格？格的基本性質(zhì)7)等冪律 aa=a 對偶 aa=a8)吸收律 a(ab)=a 對偶 a(ab)=a證： 因為aab, aa 所以 aa(ab) 又 aa(ab) 所以a= a(ab)1 格？格的基本性質(zhì)9)ab ab=a ab=b證： ab aa, ab aab 又 aab a=ab ab=a 若ba且ba, 則ab=b,矛盾 若a,b不可比較，則與ab=a矛盾 ab1 格？格的基本性質(zhì)10) ac,bd abcd abcd證：aba, ac abc abb, bd abd abcd1 格？格的基本性質(zhì)11）保序性 bc abac aba

6、c證： 因為aa, bc 由性質(zhì)10) 知 abac 得證。1 格？格的基本性質(zhì)12） 分配不等式 a(bc)(ab)(ac) 對偶 a(bc)(ab)(ac)證:aab, aac a(ab)(ac) bab, cac bc(ab)(ac)（性質(zhì)10） a(bc)(ab)(ac) 1 格？ 將代數(shù)結(jié)構(gòu)的有關(guān)概念應(yīng)用于格2 格是代數(shù)結(jié)構(gòu)偏序集（格）：代數(shù)結(jié)構(gòu)？代數(shù)結(jié)構(gòu)：偏序集（格）？定理9.2 設(shè)是代數(shù)結(jié)構(gòu)，,是L上二個二元運算，若二元運算,均滿足結(jié)合律交換律吸收律(a(ab)=a,a (ab)=a)等冪律(aa=a,aa=a)，則是格。注：定義中的等冪律可以消除，因它可由吸收律得到： aa=

7、a( a( aa) =a2 格是代數(shù)結(jié)構(gòu)偏序集合的格、代數(shù)結(jié)構(gòu)的格等價要證明代數(shù)結(jié)構(gòu)是格，需要證明L中存在一偏序關(guān)系,對a,bL ，有l(wèi)ub(a,b)=ab, glb(a,b)=ab.2 格是代數(shù)結(jié)構(gòu)如何定義偏序關(guān)系？在集合L上定義二元關(guān)系如下： a,bL，若ab ab=a(或：a,bL，若ab ab=b)如何證明？1) 是L上的偏序關(guān)系？2）a,bL, a,b的最大下界存在， 且glb(a,b)=ab。3）a,bL, a,b的最小上界存在， 且lub(a,b)=ab2 格是代數(shù)結(jié)構(gòu)1) 證明是L上的偏序關(guān)系自反性：aL，由等冪律aa=a,有aa反對稱性：a,bL, 若ab, ba，即ab=a

8、,ba=b，于是由交換律，有a=ab=ba=b傳遞性：a,b,cL,若ab,bc，即ab=a, bc=b于是，由ac=(ab)c = a(bc)= ab=a 得ac2 格是代數(shù)結(jié)構(gòu)2)證明 a,bL,a,b的最大下界存在，且glb(a,b)=ab i)下界存在,其一為ab： 由(ab)a=(aa)b=ab 有：aba 同理，abb 從而，ab 是a,b的下界。ii) ab為最大下界： 設(shè)c 是a,b 的任一下界， 即cb, ca, 由c(ab)= (ca)b=cb=c 有：cab所以，ab 是a,b的最大下界。2 格是代數(shù)結(jié)構(gòu)3) 同理可證?a,bL, a,b的最小上界存在，且lub(a,b)

9、=ab綜上1）2）3）知:是格。注：以后可根據(jù)需要，隨意使用這二種定義和記法或 2 格是代數(shù)結(jié)構(gòu) 格是一種特殊的代數(shù)結(jié)構(gòu), 自然就可以討論它的特殊元素的存在性, 它的子格以及格之間的同態(tài)、同構(gòu)關(guān)系等, 從而能夠把代數(shù)結(jié)構(gòu)的有關(guān)結(jié)論應(yīng)用于格。 但需要注意的是, 格代數(shù)與一般代數(shù)結(jié)構(gòu)的不同之處主要在于格特別地關(guān)注元素間的次序關(guān)系。 2 格是代數(shù)結(jié)構(gòu)子格(subLattice)是個格，SL, 若S對運算和封閉，則稱是的子格。例5已知右圖所示格 下列結(jié)構(gòu)是否為其子格？ dca b2 格是代數(shù)結(jié)構(gòu)格同態(tài)?，是兩個格,f: LS,且a,bL 有f(ab)=f(a)*f(b) f(ab)=f(a)+f(b)

10、稱f是到的格同態(tài)；若f是雙射,則和是同構(gòu)的。2 格是代數(shù)結(jié)構(gòu) 分配格 如果格滿足分配律,即對任意a,b,cL, a(bc)=(ab)(ac) (1) a(bc)=(ab)(ac) (2) 稱格為分配格(Distributive lattice)。3 布爾代數(shù) 需要說明的是, 上述定義中的兩個等式事實上是等價的, 因此可以去掉其中一個。因為根據(jù)等式(1)有, a(bc)=(a(ac)(bc)=a(ac)(bc)=a(ab)c)=(ab)a)(a c)(ab)(ac),即等式(2)。反之, 也可以由(2)得到等式(1)。 3 布爾代數(shù) 例6 1) 設(shè)A是任意的集合, 則冪集格為分配格。由集合的并和

11、集合的交的性質(zhì)容易得到此結(jié)論； 2) 次序圖為右圖的格不是分配格。因為在圖(a)中，c(bd)=ca=c, (cb) (cd)=ed=d。所以該圖所表示的格不是分配格。在圖(b)中, 因為b(cd)=ba=b, 而(bc)(bd)=ee=e。所以該圖所表示的格也不是分配格。 3 布爾代數(shù)（a）（b） 例7 設(shè)是一個分配格, 對于任意的a,b,cS,如果ab=ac, ab=ac, 則有b=c。 證明 b=b(ba)=b(ca) =(bc)(ba)=(cb)(ca) =c(ba)=c(ca)=c。 3 布爾代數(shù)有界格 設(shè)是一個格, 如果存在一個元素aS, 對于任意的xS, 均有xa (或ax),

12、則稱a是格S的一個最大(或最小)元。當一個格中最大元、最小元均存在時, 則稱S是個有界格。 格的最大元、最小元，分別記為1、0。3 布爾代數(shù)1、0是唯一的嗎？0是的單位元，1是的單位元？例8 設(shè)S=2，3，4，100，對于普通的數(shù)之間的小于或等于關(guān)系，S；是一個格，其最大元素1=100，最小元素0=2。3 布爾代數(shù)補元 設(shè)是有界格，aL，若存在bL，有ab=0,ab=1，則稱b為a的補元，記為a。1 若a是b的補元，則b也是a的補元。2 有界格中，0，1互為補元。3 補元可以不存在，可以不惟一。3 布爾代數(shù) 例9 a) a的補元是b,c， b的補元是a,c, c的補元是a,b b) a,b,c

13、 均不存在補元 c1b0a1bc0 a3 布爾代數(shù)有補格若在一個有界格中，每個元素至少有一個補元，則稱此格為有補格。有補分配格若一個格既是有補格，又是分配格，則此格稱為有補分配格，又稱布爾代數(shù)(Boolean Algebra) 。3 布爾代數(shù) 有限布爾代數(shù) 如果一個布爾代數(shù)的元素是有限的, 則稱它是一個有限布爾代數(shù)。 如冪集格就是一個有補分配格。根據(jù)例7的結(jié)論容易證明有補分配格中每個元素的補都是惟一的。于是, 求補運算“”是一個布爾代數(shù)S中的一個一元運算。這樣, 布爾代數(shù)L是一具有兩個二元運算, , 一個一元運算(求補)的代數(shù)結(jié)構(gòu)。以后用或來表示布爾代數(shù)。也常常用或來表示布爾代數(shù), 其中0, 1分別為最小元、最大元。 3 布爾代數(shù)例10 設(shè)是布爾代數(shù),則有:1) aL, (a)=a2) a,bL,(ab)=ab 2) 證明 (ab)(ab)=(aba)(abb) = (aa)b)(a(bb) = (1b)(a1)=1, (ab)(ab) = (aab)(bab) = (aa)b)(bb)a) = (0b)(0a) = 0所以 ab 是 ab 的補元,即 (ab)= ab同理可證 (ab)= ab 3 布爾代數(shù)示例：布爾代數(shù)集合代數(shù)，命題代數(shù)，開關(guān)代數(shù)為布爾代數(shù)(因為滿足結(jié)合律、交換律、吸收律、分配律、存在補元及0，1）1) 集合