十四格與布爾代數(shù).ppt

1、本章內(nèi)容,13.1 格的定義與性質(zhì) 13.3 分配格與有補格 13.4 布爾代數(shù) 本章總結(jié) 作業(yè),復習,1.偏序集,定義3-12.1：設A是一個集合，如果A上的一個關(guān)系R滿足自反性、反對稱性和傳遞性，則稱R是A上的一個偏序關(guān)系，記作 。稱作偏序集。,2. 最大元、最小元 定義3-12.6：設是一個偏序集，且B是A的子集，若有某個元素bB，對于B中的每一個元素x，有xb，則稱b為的最大元；同理，若有某個元素bB，對于B中的每一個元素x，有bx，則稱b為的最小元。,3.哈斯圖 定義3-12.2：在偏序集中，如果x、yA，xy，xy，且沒有其他元素z，使xz，zy，則稱元素y蓋住元素x。記COVA=

2、|x、yA，y蓋住x。,對于給定偏序集，它的蓋住關(guān)系是唯一的，所以可用蓋住的性質(zhì)畫出偏序集合圖，或稱哈斯圖，其作圖規(guī)則為： (1)小圓圈代表元素。 (2)如果xy且xy，將代表y的小圓圈畫在代表x的小圓圈之上。 (3)如果COVA，則在x與y之間用直線連結(jié)。,4. 上界、下界 定義3-12.7：設是一偏序集，對于BA，如有aA，且對任意元素xB，都有xa，則稱a為B的上界。同理，對任意元素xB，都有ax，則稱a為B的下界。,5. 上確界、下確界 定義3-12.8：設是一偏序集且BA，a是B的任一上界，若對B的所有上界y均有ay，則稱a是B的最小上界(上確界)，記作LUBB。同理，b是B的任一下

3、界，若對B的所有下界z均有zb，則稱b是B的最大下界(下確界)，記作GLBB。,13.1 格的定義與性質(zhì),定義13.1 設是偏序集，如果x,yS，x,y都有最小上界和最大下界，則稱S關(guān)于偏序作成一個格(lattice)。 說明：由于最小上界和最大下界的唯一性，可以把求x,y的最小上界和最大下界看成x與y的二元運算和。 xy：表示x與y的最小上界 xy：表示x和y的最大下界。 本章出現(xiàn)的和符號只代表格中的運算，而不再有其它的含義。,格的實例,例13.1 設n是正整數(shù)，Sn是n的正因子的集合。D為整除關(guān)系，則偏序集構(gòu)成格。x,ySn， xy是lcm(x,y)，即x與y的最小公倍數(shù)。 xy是gcd(

4、x,y)，即x與y的最大公約數(shù)。 下圖給出了格，和。,例13.2,例13.2 判斷下列偏序集是否構(gòu)成格,并說明理由。 (1) ，其中P(B)是集合B的冪集。 (2) ，其中Z是整數(shù)集,為小于或等于關(guān)系。 (3) 偏序集的哈斯圖分別在下圖給出。,例13.2,解答 (1)是格。 x,yP(B)，xy就是xy，xy就是xy。 由于和運算在P(B)上是封閉的，所以xy，xyP(B)。 稱,為B的冪集格。 (2)是格。 x,yZ,xymax(x,y)，xymin(x,y)，它們都是整數(shù)。 (3)都不是格。 (a)中的a,b沒有最大下界。 (b)中的b,d有兩個上界c和e,但沒有最小上界。 (c)中的b,

5、c有三個上界d,e,f,但沒有最小上界。 (d)中的a,g沒有最大下界。,例13.3,例13.3 設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的子群格。 易見在L(G)中，H1H2就是H1H2，H1H2就是。,對偶原理,定義13.2 設f是含有格中元素以及符號、和的命題。令f*是將f中的替換成，替換成，替換成，替換成所得到的命題。稱f*為f的對偶命題。 例如 在格中令f是(ab)cc，則f*是(ab)

6、cc。 格的對偶原理 設f是含有格中元素以及符號、和的命題。若f對一切格為真，則f的對偶命題f*也對一切格為真。 例如 對一切格L都有 a,bL，aba (因為a和b的交是a的一個下界) 那么對一切格L都有 a,bL，aba 說明許多格的性質(zhì)都是互為對偶命題的。 有了格的對偶原理，在證明格的性質(zhì)時，只須證明其中的一個命題即可。,格的運算性質(zhì),定理13.1 設是格，則運算和適合交換律、結(jié)合律、冪等律和吸收律，即 (1)交換律 a,bL 有 abbaabba (2)結(jié)合律 a,b,cL 有 (ab)ca(bc)(ab)ca(bc) (3)冪等律 aL 有 aaaaaa (4)吸收律 a,bL 有

7、a(ab)aa(ab)a,定理13.1,(1)ab和ba分別是a,b和b,a的最小上界。 由于a,bb,a，所以abba。 由對偶原理，abba得證。 (2)由最小上界的定義有 (ab)caba (13.1) (ab)cabb (13.2) (ab)cc (13.3) 由式13.2和13.3有(ab)cbc(13.4) 再由式13.1和13.4有(ab)ca(bc) 同理可證(ab)ca(bc) 根據(jù)偏序關(guān)系的反對稱性有(ab)ca(bc) 由對偶原理，(ab)ca(bc)得證。,定理13.1,(3)顯然aaa, 又由aa可得 aaa。 根據(jù)反對稱性有 aaa， 由對偶原理，aaa 得證。 (

8、4)顯然a(ab)a(13.5) 又由 aa，aba 可得 a(ab)a (13.6) 由式13.5和13.6可得 a(ab)a， 根據(jù)對偶原理，a(ab)a 得證。,定理13.2,定理13.2 設是具有兩個二元運算的代數(shù)系統(tǒng)，若對于*和運算適合交換律、結(jié)合律、吸收律，則可以適當定義S中的偏序，使得構(gòu)成一個格，且a,bS有aba*b，abab。 思路 (1)證明在S中*和運算都適合冪等律。 (2)在S上定義二元關(guān)系R，并證明R為偏序關(guān)系。 (3)證明構(gòu)成格。 說明通過規(guī)定運算及其基本性質(zhì)可以給出格的定義。,定理13.2,aS，由吸收律得,(1)證明在S中*和運算都適合冪等律。,a*a, a*(

9、a(a*a), a,同理有 aaa。,(2)在S上定義二元關(guān)系R，,a,bS 有,R abb,下面證明R在S上的偏序。,根據(jù)冪等律，,aS都有aaa，,即R，,所以R在S上是自反的。,a,bS 有,aRb且bRa, abb且baa, abaabb (由于a b=ba),所以R在S上是反對稱的。,定理13.2,a,b,cS 有 aRb且bRc abb 且 bcc aca(bc) ac(ab)c acbcc aRc 這就證明了R在S上是傳遞的。 綜上所述，R為S上的偏序。 以下把R記作。,定理13.2,(3) 證明構(gòu)成格。 即證明abab，aba*b 。,a,bS 有,a(ab)(aa)bab,b

10、(ab)a(bb)ab,根據(jù)的定義有 aab和bab，,所以ab是a,b的上界。,假設 c為a,b的上界，,則有acc和bcc，,從而有,(ab)c, a(bc), ac, c,這就證明了abc，,所以ab是a,b的最小上界，即,abab,為證a*b是a,b的最大下界，,先證,首先由abb 可知,a*b,a*(ab),a,反之由a*ba 可知,ab,(a*b)b,b(b*a),b,再由式(13.7)和的定義有 ab a*ba，,依照前邊的證明,類似地可證 a*b是a,b的最大下界，,即 aba*b。,abb a*ba(13.7),格的等價定義,根據(jù)定理13.2，可以給出格的另一個等價定義。 定

11、義13.3 設是代數(shù)系統(tǒng)，*和是二元運算，如果*和滿足交換律，結(jié)合律和吸收律，則構(gòu)成一個格(lattice)。 說明格中的冪等律可以由吸收律推出。 以后我們不再區(qū)別是偏序集定義的格，還是代數(shù)系統(tǒng)定義的格，而統(tǒng)稱為格L。,格的性質(zhì),定理13.3 設L是格，則a,bL 有 ab aba abb 證明 先證 ab aba 由aa和ab可知，a是a,b的下界， 故aab。顯然又有aba。 由反對稱性得aba。 再證 aba abb。 根據(jù)吸收律有 bb(ba) 由aba得 bba, 即abb。 最后證abb ab。 由aab得 aabb。,格的性質(zhì),定理11.4 設L是格，a,b,c,dL，若ab且c

12、d，則 acbd，acbd 證明 acab accd 因此， acbd。 同理可證 acbd。,例13.4,例13.4 設L是格，證明 a,b,cL 有 a(bc)(ab)(ac) 證明由 aa，bcb 得 a(bc)ab 由 aa，bcc 得 a(bc)ac 從而得到 a(bc)(ab)(ac) 說明在格中分配不等式成立。 一般說來，格中的和運算并不是滿足分配律的。,本節(jié)小結(jié),偏序集構(gòu)成格的條件：任意二元子集都有最大下界和最小上界。 格的實例：正整數(shù)的因子格，冪集格，子群格。 格的性質(zhì)：對偶原理，格中算律（交換、結(jié)合、冪等、吸收），保序性，分配不等式。 格作為代數(shù)系統(tǒng)的定義。 格的證明方法,

13、13.2 子格與格同態(tài),定義13.4 設是格，S是L的非空子集，若S關(guān)于L中的運算和仍構(gòu)成格，則稱S是L的子格。,例13.5 設格L如右圖所示。令,S1a,e,f,g S2a,b,e,g,則S1不是L的子格，S2是L的子格。 因為對于e和f,有efc， 但cS1。,13.3 分配格與有補格,一般說來，格中運算對滿足分配不等式， 即a,b,cL，有 a(bc)(ab)(ac) 但是不一定滿足分配律。滿足分配律的格稱為分配格。 定義13.7 設是格，若a,b,cL，有 a(bc)(ab)(ac) a(bc)(ab)(ac) 則稱L為分配格。 說明上面兩個等式互為對偶式。 在證明L為分配格時，只須證

14、明其中的一個等式即可。,例13.8,L1和L2是分配格，L3和L4不是分配格。,在L3中，b(cd),beb,(bc)(bd),aaa,在L4中,c(bd),cac,(cb)(cd),edd,鉆石格,五角格,分配格的判別,定理13.6 設L是格，則L是分配格當且僅當L中不含有與鉆石格或五角格同構(gòu)的子格。 證明略。 推論(1) 小于五元的格都是分配格。 (2) 任何一條鏈都是分配格。,例13.9,說明下圖中的格是否為分配格，為什么？,L1, L2和L3都不是分配格。 a,b,c,d,e是L1的子格，并且同構(gòu)于鉆石格。 a,b,c,e,f是L2的子格，并且同構(gòu)于五角格。 a,c,b,e,f是L3的

15、子格，也同構(gòu)于鉆石格。,定理13.7,定理13.7 格L是分配格 當且僅當 a,b,cL，abac且abac bc。 證明 必要性。a,b,cL，有 b b(ab)(吸收律,交換律) b(ac)(已知條件代入) (ba)(bc) (分配律) (ac)(bc)(已知條件代入,交換律) (ab)c (分配律) (ac)c (已知條件代入) c (交換律,吸收律),定理13.7,充分性。假若a,b,cL，有 abac且abac bc 成立，而L不是分配格。 根據(jù)定理13.6，L中必含有與鉆石格或五角格同構(gòu)的子格。 假設L中含有與鉆石格同構(gòu)的子格，且該子格為u,v,x,y,z，其中u為它的最小元，v為

16、它的最大元。,從而推出 xyxzu，xyxzv 但yz，與已知矛盾。 對五角格的情況同理可證。,定理13.7的應用,使用定理13.7也可以判別一個格是否為分配格。 例如下圖中的三個格都不是分配格。,在L1中有 bcbd，bcbd，但cd。 在L2中有 bcbe，bcbe，但ce。 在L3中有 cbcd，cbcd，但bd。,格的全下界和全上界,定義13.8 設L是格， 若存在aL使得xL有ax，則稱a為L的全下界； 若存在bL使得xL有xb，則稱b為L的全上界。 命題格L若存在全下界或全上界，一定是唯一的。 證明以全下界為例，假若a1和a2都是格L的全下界, 則有a1a2和a2a1。 根據(jù)偏序關(guān)

17、系的反對稱性必有a1a2。 記法將格L的全下界記為0，全上界記為1。,有界格,定義13.9 設L是格，若L存在全下界和全上界，則稱L為有界格，并將L記為。 說明有限格L一定是有界格。 舉例 設L是n元格，且La1,a2,an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是有界格。 對于無限格L來說，有的是有界格，有的不是有界格。 如集合B的冪集格，不管B是有窮集還是無窮集，它都是有界格。它的全下界是空集，全上界是B。 整數(shù)集Z關(guān)于通常數(shù)的小于或等于關(guān)系構(gòu)成的格不是有界格，因為不存在最小和最大的整數(shù)。,有界格的性質(zhì),定理13.8 設是有界格，則aL有 a00a0a a1aa1

18、1 證明由 a00 和 0a0 可知 a00。 說明 在有界格中， 全下界0是關(guān)于運算的零元，運算的單位元。 全上界1是關(guān)于運算的零元，運算的單位元。 對偶原理 對于涉及到有界格的命題，如果其中含有全下界0或全上界1，在求該命題的對偶命題時，必須將0替換成1，而將1替換成0。 例如a00 和 a11 互為對偶命題， a0a 和 a1a 互為對偶命題。,有界格中的補元,定義13.10 設是有界格，aL， 若存在bL 使得 ab0 和 ab1 成立，則稱b是a的補元。 說明若b是a的補元，那么a也是b的補元。 換句話說，a和b互為補元。,例13.10,考慮下圖中的四個格。,L1中的a與c互為補元，

19、其中a為全下界，c為全上界，b沒有補元。 L2中的a與d互為補元，其中a為全下界，d為全上界，b與c也互為補元。 L3中的a與e互為補元，其中a為全下界，e為全上界，b的補元是c和d，c的補元是b和d，d的補元是b和c。b,c,d每個元素都有兩個補元。 L4中的a與e互為補元。其中a為全下界。e為全上界。b的補元是c和d，c的補元是b，d的補元是b。,有界格中補元的說明,在任何有界格中， 全下界0與全上界1互補。 對于其他元素，可能存在補元，也可能不存在補元。 如果存在，可能是唯一的，也可能是多個補元。 對于有界分配格，如果它的元素存在補元，一定是唯一的。,有界分配格中補元的唯一性,定理13.

20、9 設是有界分配格。 若aL，且對于a存在補元b，則b是a的唯一補元。 證明假設cL也是a的補元，則有 ac1，ac0 又知b是a的補元，故 ab1，ab0 從而得到 acab，acab 由于L是分配格，根據(jù)定理13.7，bc。,有補格的定義,定義13.11 設是有界格，若L中所有元素都有補元存在，則稱L為有補格。,L2,L3和L4是有補格， L1不是有補格。,L2和L3是有補格， L1不是有補格。,本節(jié)小結(jié),如果格中一個運算對另一個運算是可分配的，稱這個格是分配格。 分配格的兩種判別法： 不存在與鉆石格或五角格同構(gòu)的子格； 對于任意元素a,b,c,有 abac且abacbc。 有界格的定義及

21、其實例。 格中元素的補元及其性質(zhì)（分配格中補元的唯一性）。 有補格的定義。,13.4 布爾代數(shù),定義13.12 如果一個格是有補分配格，則稱它為布爾格或布爾代數(shù)。 說明在布爾代數(shù)中，每個元素都存在著唯一的補元。 可以把求補元的運算看作是布爾代數(shù)中的一元運算。 可以把一個布爾代數(shù)標記為， 為求補運算, aB，a是a的補元。,例13.11,例13.11 設S1101,2,5,10,11,22,55,110是110的正因子集合。令gcd,lcm分別表示求最大公約數(shù)和最小公倍數(shù)的運算。問是否構(gòu)成布爾代數(shù)？為什么？ 解答 證明構(gòu)成格。,容易驗證x,y,zS110，有 gcd(x,y)S110 lcm(x

22、,y)S110 gcd(x,y)gcd(y,x) lcm(x,y)lcm(y,x) gcd(gcd(x,y),z)gcd(x,gcd(y,z) lcm(lcm(x,y),z)lcm(x,lcm(y,z) gcd(x,lcm(x,y)x lcm(x,gcd(x,y)x,二元運算,交換律,結(jié)合律,吸收律,例13.11,證明 是分配格。 易驗證 x,y,zS110 有 gcd(x,lcm(y,z)lcm(gcd(x,y),gcd(x,z) 證明 是有補格。 1 為S110中的全下界 110為S110中的全上界 1和110互為補元，2和55互為補元， 5和22互為補元，10和11互為補元。 綜上所述，

23、為布爾代數(shù)。,例13.12,例13.12 設B為任意集合,證明B的冪集格構(gòu)成布爾代數(shù)，稱為集合代數(shù)。 證明P(B)關(guān)于和構(gòu)成格，因為 和運算滿足交換律、結(jié)合律和吸收律。 由于和互相可分配，因此P(B)是分配格， 且全下界是空集,全上界是B。 根據(jù)絕對補的定義，取全集為B， xP(B)，x是x的補元。 從而證明P(B)是有補分配格，即布爾代數(shù)。,布爾代數(shù)的性質(zhì),定理13.10 設是布爾代數(shù)，則 (1) aB，(a)a (2) a,bB，(ab)ab,(ab)ab 說明(1)稱為雙重否定律。 (2)稱為德摩根律。 命題代數(shù)與集合代數(shù)的雙重否定律與德摩根律實際上是這個定理的特例。 可以證明德摩根律對

24、有限個元素也是正確的。 證明(1) (a)是a的補元，a也是a的補元。 由補元的唯一性得(a)a。,定理13.10(2)的證明,(2) a,bB，(ab)ab,(ab)ab (ab)(ab) (aab)(bab) (1b)( a1) 11 1 (ab)(ab) (aba)(abb) (0b)(a0) 000 所以ab是ab的補元，根據(jù)補元的唯一性有 (ab)ab 同理可證(ab)= ab。,布爾代數(shù)作為代數(shù)系統(tǒng)的定義,定義13.13 設是代數(shù)系統(tǒng)，*和是二元運算。 若*和運算滿足： (1)交換律，即a,bB 有 a*bb*a，abba (2)分配律，即a,b,cB有 a*(bc)(a*b)(a

25、*c) a(b*c)(ab)*(ac) (3)同一律，即存在0,1B，使得aB 有 a*1a，a0a (4)補元律，即aB,存在aB，使得 a*a0，aa1 則稱是一個布爾代數(shù)。,關(guān)于布爾代數(shù)定義的說明,所謂同一律就是指運算含有單位元的性質(zhì)，這里的1是*運算的單位元，0是運算的單位元。 可以證明1和0分別也是和*運算的零元。 aB有 a1 (a1)*1 （同一律） 1*(a1) （交換律） (aa)*(a1) （補元律） a(a*1) （分配律） aa （同一律） 1 （補元律） 同理可證 a*00。,關(guān)于布爾代數(shù)定義的說明,為證明以上定義的是布爾代數(shù)，只需證明它是一個格，即證明*和運算滿足結(jié)

26、合律和吸收律。 證明吸收律，a,bB有 a(a*b) (a*1)(a*b)（同一律） a*(1b)（分配律） a*1 （1是運算的零元) a （同一律） 同理有 a*(ab)a。,關(guān)于布爾代數(shù)定義的說明,為證結(jié)合律，先證以下命題： a,b,cB，abac 且 abac bc 由 abac 且 abac 可得 (ab)*(ab)(ac)*(ac) 由分配律和交換律得 (a*a)b(a*a)c 由補元律得 0b0c 由同一律和交換律得 bc,關(guān)于布爾代數(shù)定義的說明,使用這個命題，為證明 (a*b)*ca*(b*c)，只需證明以下兩個等式： (1) a(a*b)*c)a(a*(b*c) (2) a(

27、a*b)*c)a(a*(b*c) 先證明第一個等式，由吸收律有 a(a*(b*c)a a(a*b)*c) (a(a*b)*(ac)(分配律) a*(ac)(吸收律) a 所以(1)式成立。,關(guān)于布爾代數(shù)定義的說明,下面證明(2)式： a(a*b)*c)a(a*(b*c) a(a*(b*c) (aa)*(a(b*c) (分配律) 1*(a(b*c) (交換律,補元律) a(b*c) (交換律,同一律) a(a*b)*c) (a(a*b)*(ac) (分配律) (aa)*(ab)*(ac)(分配律) (1*(ab)*(ac) (交換律,補元律) (ab)*(ac) (交換律,同一律) a(b*c)

28、(分配律) 所以（2）式成立。,布爾代數(shù)的子代數(shù),定義13.14 設是布爾代數(shù)，S是B的非空子集，若0,1S，且S對,和運算都是封閉的，則稱S是B的子布爾代數(shù)。,例13.13,例13.13 設是布爾代數(shù)，a,bB，且ab。令 Sx|xB，且axb 稱S為B中的區(qū)間，可簡記為a,b。 可以證明a,b是一個布爾代數(shù)。 顯然S是B的非空子集，且a和b分別為S的全下界和全上界。 對任意的x,yS都有 axb，ayb 從而有 axyb, axyb S關(guān)于和運算是封閉的。 易見和運算在S上適合交換律和分配律。,例13.13,對任意的 xS，,令 y(ax)b (下面證明y為x得補元。),由于 aax，ab

29、，,故 a(ax)b。,同時(ax)bb，,因此 yS。,又,xy x(ax)b) x(ab)(xb)(分配律) xa(xb) (ab) x(xb) (ax) (xx)(xb) (分配律) 1(xb) (補元律) xb (交換律，同一律) b(xb),例13.13,xy x(ax)b) x(ax) (xb,交換律) (xa)(xx) (分配律) (xa)0 (補元律) xa (同一律) a (ax) 根據(jù)定義13.13，構(gòu)成布爾代數(shù)。 其全上界是a，全下界是b。 xa,b，x關(guān)于這個全上界和全下界的補元是(ax)b。 當a0且b1時，a,b是B的子布爾代數(shù)。 但當a0或b1時，a,b不是B的子

30、布爾代數(shù)。,例13.14,考慮110的正因子集合S110關(guān)于gcd,lcm運算構(gòu)成的布爾代數(shù)。 它有以下的子布爾代數(shù)： 1,110 1,2,55,110 1,5,22,110 1,10,11,110 1,2,5,10,11,22,55,110,布爾代數(shù)的同態(tài)映射,定義13.15 設和是兩個布爾代數(shù)。這里的,-泛指布爾代數(shù)B2中的求最大下界、最小上界和補元的運算。和E分別是B2的全下界和全上界。: B1B2。如果對于任意的a,bB1 有 (ab) (a)(b) (ab) (a)(b) (a) -(a) 則稱是布爾代數(shù)B1到B2的同態(tài)映射，簡稱布爾代數(shù)的同態(tài)。 說明類似于其它代數(shù)系統(tǒng)，也可以定義布

31、爾代數(shù)的單同態(tài)、滿同態(tài)和同構(gòu)。,例13.15,例13.15 設和是布爾代數(shù)。: B1B2。若a,bB1有 (ab) (a)(b) (a) -(a) 證明是B1到B2的同態(tài)。 證明只須證明a,bB1 有 (ab)(a)(b)成立即可。 (ab) (ab)(雙重否定律) -(ab) (已知) -(ab)(德摩根律) -(a)(b) (已知) -(-(a)-(b) (已知) -(-(a)-(-(b) (德摩根律) (a)(b)(雙重否定律),有限布爾代數(shù)的結(jié)構(gòu),定義13.16 設L是格，0L，aL，若 bL 有 0ba ba 則稱a是L中的原子。,考慮右圖中的幾個格。 L1的原子是a。 L2的原子是

32、a,b,c。 L3的原子是a和b。,若L是正整數(shù)n的全體正因子關(guān)于整除關(guān)系構(gòu)成的格，則L的原子恰為n的全體質(zhì)因子。 若L是集合B的冪集合，則L的原子就是由B中元素構(gòu)成的單元集。,引理,引理1設是格，a,b是中的原子，若ab，則ab0。 證明假設ab0，則有 0aba 和 0abb 由于a,b是原子，則有 aba 和 abb， 從而有ab，與已知矛盾。,引理,引理設B是有限的布爾代數(shù)，xB，x0，令 T(x)a1,a2,an 是B中所有小于或等于x的原子構(gòu)成的集合，則 xa1a2an 稱這個表示式為x的原子表示，且是唯一的表示。 這里的唯一性是指：若 xa1a2an，xb1b2bn 都是x的原子

33、表示，則有 a1,a2,anb1,b2,bn,引理2的證明,令ya1a2an。,由于aix，i1,2,n，,所以必有yx。,由此可知t1是原子，且t1x和t1y。,假如xy0，,則存在B中元素t1,t2,ts，,現(xiàn)證明xy0。,使得t1覆蓋0，t2覆蓋t1，ts覆蓋ts-1，且tsxy。,由t1x可知t1T(x)。,即存在aiT(x)，使得t1ai。,又由t1y可知t1yt1，從而有,t1t1y,aiy,ai(a1a2an),ai(a1a2aian),(aiai)(a1ai-1ai+1an),0a1ai-1ai+1an0,這與t1覆蓋0矛盾。,從而證明了xy0。,引理,由 yy0,(yx)(y

34、y),y(xy),(yx)1,yx,可知 xy。,綜合上述得xy，,即xa1a2an。,設xb1b2bm是x的另一個原子表示，,任取aia1,a2,an，,假若aib1,b2,bm。,由引理1 必有aibj0，j1,2,m。,又由于aix，于是,aiaix,ai(b1b2bn),(aib1)(aib2)(aibm),0000,這與ai是原子矛盾。,從而證明了aib1,b2,bm。,同理可證， bjb1,b2,bm，必有bja1,a2,an， 于是a1,a2,anb1,b2,bm。,有限布爾代數(shù)的表示定理,定理13.11 (有限布爾代數(shù)的表示定理) 設B是有限布爾代數(shù)，A是B的全體原子構(gòu)成的集合

35、，則B同構(gòu)于A的冪集代數(shù)P(A)。 證明任取xB，令T(x)a|aB,a是原子且ax 則T(x)A，定義函數(shù) ：BP(A)，(x)T(x)，xB 下面證明是B到P(A)的同構(gòu)映射。 任取x,yB，b 有 bT(xy) bA 且 bxy (bA且bx) 且 (bA且by) bT(x)且bT(y) bT(x)T(y) 從而有 T(xy)T(x)T(y)， 即x,yB 有 (xy)(x)(y)。,定理13.11證明,任取x,yB，設 xa1a2an， yb1b2bm 是x,y的原子表示，則 xya1a2anb1b2bm 由引理2可知 T(xy)a1,a2,an,b1,b2, ,bm 又由于 T(x)

36、a1,a2, ,an， T(y)b1,b2, ,bm 所以 T(xy)T(x)T(y) 即(xy)(x)(y),定理13.11證明,任取xB，存在xB 使得 xx1， xx0 因此有 (x)(x)(xx)(1)A (x)(x)(xx)(0) 而和A分別為P(A)的全下界和全上界， 因此(x)是(x)在P(A)中的補元，即 (x)(x) 綜上所述，是B到P(A)的同態(tài)映射。,定理13.11證明,下面證明為雙射。 假設(x)(y)，則有 T(x)T(y)a1,a2, ,an 由引理2可知 xa1a2any 于是為單射。 任取b1,b2, ,bmP(A)， 令xb1b2bm ，則 (x)T(x)b1,b2, ,bm 于是為滿射。 定理得證。,例子,考慮110的正因子的集合S110關(guān)于gcd, lcm運算構(gòu)成的布爾代數(shù)。 它的原子是2、5和11，因此原子的集合A2,5,