1、1 1第七章格第七章格 格和布爾代數(shù)是二種特殊的代數(shù)機構，它們在有限自動機，開關理論和邏輯設計中用的較多。主要內容如下：7.1偏序集和格7.2格是一種代數(shù)系統(tǒng)7.3分配格和有補格7.4布爾代數(shù)7.5有限布爾代數(shù)的同構2 2 一偏序集一偏序集1.1.偏序集偏序集 定義定義7-1 7-1 集合集合L L和定義在和定義在 L L 上的偏序關系上的偏序關系 “” ” 一起稱為偏序集，用一起稱為偏序集，用L 表示。表示。 假設 是集合A上的偏序關系，那么 的逆關系也必是上的偏序關系，證明如下： R ，I，2U 和和N|都是偏都是偏序集。序集。3 3對任意的對任意的 a a ，因為，因為 自反，所以有自反

2、，所以有 （a,aa,a） , ,于是于是a,aa,a） ，因而，因而 也是自反的。也是自反的。對任意對任意 a ,b A a ,b A ，假設，假設a,ba,b） 且且b,ab,a） ， 則有則有b,ab,a） 且且a,ba,b） ，必有，必有a = ba = b， 因而因而 是反對稱的。是反對稱的。對任意對任意a,b,c A,a,b,c A,假設假設a,ba,b） ,(b,c,(b,c） ， 則有則有c,bc,b） 且且b,ab,a） ，必有，必有 （c,ac,a） ，于是，于是a,ca,c） ，因而，因而 是可傳遞的。是可傳遞的。 由上證得由上證得 也是偏序關系。也是偏序關系。 4 4根

3、據(jù)逆關系的定義根據(jù)逆關系的定義 = = )6 , 6(),3 , 6(),3 , 3(),2 , 6(),2 , 2)(1 , 6(),1 , 3(),1 , 2(),1 , 1 (p 由定義 = ) 6 , 6(),6 , 3 (),3 , 3 (),6 , 2(),2 , 2)(6 , 1 (),3 , 1 (),2 , 1 (),1 , 1 ( 例例1 1 設設 A= A= ，定義，定義 A A 上的整除關系上的整除關系 ：當?shù)﹥H當當?shù)﹥H當 a a 整除整除 b b 時，有時，有 。ba6 , 3 ,2, 1 的次序圖如下 的次序圖如下 p6 61 13 36 62 22 23 31 1

4、5 5假設假設L 是一個偏序集，則對于任意元素是一個偏序集，則對于任意元素 1, 2, 3 L1, 2, 3 L，有以下六個關系式成立：，有以下六個關系式成立： 1 1 (7- ) 假設 1 2 ， 2 1，那么 1= 2 (7- ) 假設 1 2 ， 2 3，那么 1 3 (7- )312注意注意 在偏序集在偏序集L 中，對任意元素中，對任意元素 1 1， 2 L2 L，假設假設 1 21 2，則必有，則必有 2 12 1， 假設假設 2 12 1，則必有，則必有 1 21 2，因而，因而， 1 1 2 2等價于等價于 2 1 2 1 。 1 1 （7-1） 假設 1 2 ， 2 1，那么

5、1= 2 （7-2） 假設 1 2 ， 2 3，那么 1 3 (7-3)6 6 2最大下界和最小上界定義7-1 設 1和 2是偏序集中的兩個元素,元素a L，如果滿足a 1,a 2 ,則稱a是 1和 2的下界。 定義7-2 設 1和 2是偏序集中的兩個元素，元素b L ,如果滿足 1 b， 2 b，則稱 b是 1和 2的上界。 如果元素如果元素a a是是 1 1和和 2 2的下界。且對于任意的下界。且對于任意 L L，假設，假設也是也是 1 1和和 2 2的下界，便有的下界，便有 a ,a ,則稱則稱a a是是 1 1和和 2 2的的最大下界，簡記作最大下界，簡記作a=glb(a=glb(1

6、, 2).1 , 2).aa a如果元素如果元素 b b是是 1 1和和 2 2的上界，且對于任意的上界，且對于任意 L L，假設，假設 也是也是 1 1和和 2 2的上界，便有的上界，便有b b，則稱，則稱 b b 是是1 1和和2 2的的最小上界，簡記作最小上界，簡記作b=lub(b=lub(1, 2)1, 2)bbb7 7lub(2,3)=lub(2,3)=？，？，glb(12,18)=?glb(12,18)=?，lub(18,27)=?lub(18,27)=?有有2 62 6，3 63 6；2 122 12，3 123 12；2 2 1818，3 183 18。 由于6 12，6 18

7、，6 6，因而，lub2，3）=6。 6 12，6 18；2 12，2 18；3 12，3 18；1 12,1 18； 因因1 61 6，2 62 6，3 63 6，所以，所以glb(12,18)glb(12,18)6 6。 例例2 2 設設A= “A= “整除關整除關系是系是A A上的偏序關系，其次序圖如下，因而，上的偏序關系，其次序圖如下，因而，它們構成一個偏序集它們構成一個偏序集A 。27,18,12, 9 , 6 , 3 , 2 , 11 11818121227272 23 36 69 98 8 試問試問 glb(18,12)=?, lub(2,3)=? 218，2 12；3 18，3

8、 12，1 18，1 12。 但但glb(18,12)glb(18,12)不存在。不存在。 類似地，12，18 和 36 均是 2 和 3 的上界，但 lub2，3不存在。 例例3 3設設A=A=，整除關系是，整除關系是A A上上的偏序關系，其次序圖如下的偏序關系，其次序圖如下 36,12,18, 3 , 2 ,9 定理定理7-1 7-1 設和是偏序集設和是偏序集L的的兩個元素，假如和有兩個元素，假如和有glb,glb,則則glbglb是唯一的，是唯一的，假如和假如和 有有l(wèi)ublub，則，則lublub是唯一的。是唯一的。121212 證明設和都是和的證明設和都是和

9、的glbglb， 1a2a21由定義由定義7-17-1，那么，那么 , , , ,于是有于是有= = 。1a2a1a2a1a2a 類似地可以證明, 和若存在lub，則lub也一定是唯一的。121010 定理定理7-2 7-2 如果偏序集如果偏序集L有最小元素，有最小元素，則最小元素是唯一的。假如則最小元素是唯一的。假如L有最大元素，有最大元素，則最大元素也是唯一的。則最大元素也是唯一的。3 3 最小元素和最大元素最小元素和最大元素 定義定義7-3 7-3 設設L是一偏序集。是一偏序集。 (1) (1) 如果存在元素如果存在元素a La L，使得，使得對于所有的元素對于所有的元素 L L，有，有

10、a a ，則稱則稱a a是是L的最小元素。的最小元素。 (2) (2) 如果存在元素如果存在元素b Lb L，使得，使得對于所有的元素對于所有的元素 L L，有，有 bb，則稱則稱b b是是L的最大元素。的最大元素。 證明證明 設設 和和 都是都是L的最小元的最小元素，則有素，則有 ，且，且 ，得，得 。 1a2a1a2a2a2a1a1a1111例4 L= 2 , 3 , 6 , 12 , 24 , 36 “”是整除關系。24和36沒有上界；2和3沒有下界。當然沒有最小元，也沒有最大元。2412366321212 二、二、 格格 1 1格的定義格的定義 定義定義7-4 7-4 設設L是一個偏序

11、集，是一個偏序集，如果如果L L中任意兩個元素都存在著最大下界和最中任意兩個元素都存在著最大下界和最小上界，則稱小上界，則稱L是格。是格。 =glb =glb（ ， ），）， =lub=lub（ ， ）。）。12121122 假設是一個格，則意味著也是一個形 為 的代數(shù)系統(tǒng)，其中 和 是L上的兩個二元運算， 對于任意 ， ， 表示在偏序“”意義下， 和 的最小上界， 表示 和 的最大下界。221121L21121313例例5 5 試判斷下列次序圖給出的偏序試判斷下列次序圖給出的偏序集哪些是格？集哪些是格？解解 （a a不是格，不是格， (b)(b)不是格，不是格， (c)是一個格， （d是一個

12、格 efdcab(a)(a)edbca(b)(b)fhgdebca(c)(c)51210153630(d)(d)1414)57(2132313)47(221121)57(2132313)47(221121,llllllllllllllllllllllllll則若則若。關系式代表了格的定義這十個、)57 ()17 () 57 () 17 (在格在格L L；中有如下四個關系式成立中有如下四個關系式成立: :1515 2 2格的性質格的性質 定理定理7-3 7-3 在格在格L中，對于任意中，對于任意以下三式中若任意一式成立，那么其它兩式也成以下三式中若任意一式成立，那么其它兩式也成立立. .L21,

13、)()();()();()(12221121321llllllll證明證明 = = 設設 ， 121lll,472212llll又由自反性）有由（.57212lll ）于是由（221221,)47(llllll故由反對稱性有由另一方面，1616,221lll = = 設設 (74),12121lllll由即 = 設 ,12ll ,11ll 由自反性,2111llll因此因此11275,lll由（ ）定定理理結結論論得得證證。故故由由反反對對稱稱性性.121lll121.74lll 又由（）1717 定義7-5 設是格，P是包含格的元素和符號=、， ，的命題，將P中的、，和分別替換成、 、 和所

14、得的命題PD稱為P的對偶。 例如例如 的對偶是的對偶是 33213321 對偶原理對偶原理 ： 對于格對于格L上的任一上的任一真命題真命題P P，其對偶，其對偶 PD PD 亦為格亦為格L上的真上的真命題。命題。 181812211221)()(llllblllla定理定理7-47-4交換律）交換律） 設設L是格，則對任意的是格，則對任意的有有: : Lll21,1919定理定理7-5 7-5 （結合律）（結合律） 設設L是格，則對任是格，則對任意的意的 ，有，有Llll321,321321;321321)()()()()()(llllllblllllla,)45(332232,32,1lll

15、lllllala且由,3,2lala由傳遞性,2121llalala）有有和和（又又由由55.,)(55321321balllalalla即即，）和和（和和由由. baab 。于是由反對稱性得。于是由反對稱性得類似的方法可以證明類似的方法可以證明,)(, )(321321lllblllaa令令）（證明證明2020定理定理7-6 7-6 （吸收律）（吸收律）設設L L；是格，則對任是格，則對任意意 ，有，有 Lll21 ,12111211)()(;)()(llllblllla證明證明 (b) (b) 由由7-47-4） )1 ()(1211llll另一方面，由另一方面，由7-17-1）11,11

16、2(74 )lllll由于是，由于是，由7-5） （2）)(2111llll 由由1)1)、(2(2和反對稱性和反對稱性.)(1211llll得2121 定理定理7-7 7-7 （等冪律）（等冪律） 設設L L；是格，則對任是格，則對任意意 ，有，有 Ll .)(;)(lllblllal 證明證明 （a a由定理由定理7-6 ,7-6 ,lll)(lll2222 定理定理7-9 7-9 （格的保序性）（格的保序性） 設 設 L L ； 是 格 ， 則 對 于 任 是 格 ， 則 對 于 任意意 ，有，有Lllll4321,43214321, 42,3131213121,32,lllllllll

17、lllllllllllll則則）若若（則則）若若（21 證明證明 （1 1）331131llllll 又已知又已知 32.132(73 )lllll于是，由 1312121375llllllll（ ），即由由, ,和和432342) 1 (llllll有有，所所以以由由因因為為4321llll由由傳傳遞遞性性，有有（2因為因為 所以由所以由(1)有有31ll 2321llll2323 例例4 4 設設 L = L = ，L L上的上的整除關系整除關系 與與L L構成一個格，記作構成一個格，記作L， 126431,3( 6 4 ) = 3 1= 33( 6 4 ) = 3 1= 3 (36)(3

18、4) = 6 12 = 6 (36)(34) = 6 12 = 6于是于是 3(64)(36)(34)3(64)(36)(34)6(34) = 612 = 66(34) = 612 = 6 (63)(64)= 31= 3 (63)(64)= 31= 3 于是于是 6(34)(63)(64)6(34)(63)(64)1264312424 定理定理7-10 7-10 設設L是格，是格，則對任意則對任意 , ,有有Llll321,)()()()()()()()(31213213121321lllllllbllllllla 證明證明 （a a由由(5-4)(5-4)有有332232llll, 于是，根

19、據(jù)定理5-19有21321lllll)(31321)(lllll又由又由5-45-4有有 )()()(3121321lllllll2525定理定理7-10 7-10 設設是一個代數(shù)系統(tǒng)，其中是一個代數(shù)系統(tǒng)，其中和和都是二元運算，滿足交換律，結合律和吸收律，都是二元運算，滿足交換律，結合律和吸收律，則在則在L L上必存在一偏序關系，使得上必存在一偏序關系，使得是一個是一個格。格。 可以證明關系可以證明關系是是L L上的自反，反對稱和可傳遞的關上的自反，反對稱和可傳遞的關系，因而系，因而是是L L上的偏序關系。上的偏序關系。 在L上定義二元關系：對任意 當且僅當 時，有 。L,2112112 進一

20、步還可以證明，對任意 ， 是在偏序關系意義下 1和 2的最小上界， 1 2 是 1和 2的最大下界。 故是一個格。 L21 ,21 72 格是一種代數(shù)系統(tǒng)格是一種代數(shù)系統(tǒng)一、格的另一種定義形式一、格的另一種定義形式2626 格既可以看作是一個偏序集，也可以看作是一個代數(shù)系統(tǒng)。 定義7-6 設是一個代數(shù)系統(tǒng)， 和 是 L 上的兩個二元運算，如果這兩個運算滿足交換律，結合律和吸收律，則稱 是格。 2727 例例5 5 在全集合在全集合 U U 的冪集的冪集 2U = 2U = 上的包含關系上的包含關系“ ”“ ”是是 2U 2U 上的一偏序關系。上的一偏序關系。 USS| 因為對任意Si 2U，總

21、有Si Si，所以 是自反的。對任意對任意Si , Sj 2U , Si , Sj 2U , 若若Si Sj Si Sj ，且，且Sj Sj Si Si ，則必有則必有Si = Sj Si = Sj ，所以，所以 是反對稱的。是反對稱的。 對任意Si , Sj ，Sk 2U，若Si Sj ，Sj Sk ，則必有Si Sk，所以 是可傳遞的。 因而是一偏序集。2828因此因此SiSjSiSj是是SiSi和和SjSj的上界。的上界。 對于任意對于任意Si , Sj 2USi , Sj 2U，有，有Si SiSjSi SiSj，Sj, Sj, SiSjSiSj， 類似地可以證明，對任意 ，glb(s

22、i,sj)=sisj 因而是一個格 另一方面，集合的并運算和交運算和2U構成代數(shù)系統(tǒng)，因為運算和都滿足交換律，結合律 和吸收律，因而是一個格。 Ujiss2, 則必有SiSj S。因此SiSj是Si和Sj的最小上界。即lub(Si，Sj)= SiSj。 若有若有S 2US 2U，使得，使得 Si S Si S ，Sj Sj S S， 2929 例例6 設設U=a,b,c 則則2U=,a,b,c,a,b,a,c,b,c,a,b,c二二 、子格、子格 定義定義7-7 設設是格，假如是格，假如是是的子代數(shù)，則稱的子代數(shù)，則稱是是的子格。的子格。 格格2U 對應的代數(shù)系統(tǒng)形式的格是對應的代數(shù)系統(tǒng)形式的

23、格是2U.子格也是一個格。子格也是一個格。3030令令 S1=b,a,bb,c,a,b,cS1=b,a,bb,c,a,b,cS2=,a, c,a, cS2=,a, c,a, cS3=,a,c,a,b,a,c,b,c,a,b,cS3=,a,c,a,b,a,c,b,c,a,b,cS1是是2U的子格。的子格。S2也是也是2U的子格。的子格。 S3S3不能與這兩個運算構成不能與這兩個運算構成2U的子格。的子格。a,b,ca,cb,ca,bacb31312 6 112 練習練習5-55-51 1 設設 L = 1L = 1，2 2，3 3，4 4，6 6，1212，在，在L L上上定義定義整除關系，構成

24、偏序集整除關系，構成偏序集。 （1 1） glb(6,4)= ; glb(6,4)= ; lub(2,3)= lub(2,3)= ； （2 2） 該偏序集的最小元素是該偏序集的最小元素是 ， 最大元素是最大元素是 。126432132323 43 41 10 （1） glb(6,9) = ; glb(8,12) = .； （2） glb(9,7) = ; lub(5,10) = .。12 2 2設設L=1L=1，2 2，3 3，1111，1212，在，在L L上上定義定義 整除關系，構成偏整除關系，構成偏序集序集. . 84211056397113333下面給出的三個次序圖，其中哪些是格？在圖

25、下面給出的三個次序圖，其中哪些是格？在圖 下方相應的括號內鍵入下方相應的括號內鍵入“y或或“N表示肯定表示肯定或否定。或否定。( ) ( ) ( )NYY3434Y YY YN NN N 4 4對下圖所給出的格判斷以下子集是否能構成對下圖所給出的格判斷以下子集是否能構成它的它的 子格。在相應的括號內鍵入子格。在相應的括號內鍵入“Y Y或或“N N來回答來回答 （1 1S1=e,c,b ( )S1=e,c,b ( ) （2 2S2=d,b,a ( ) S2=d,b,a ( ) （3 3S3=c,d,b ( )S3=c,d,b ( ) （4 4S4=c,d,a ( )S4=c,d,a ( )e e

26、d dc cb ba a3535 定義7-8 設是一個格，若對于任意的 1, 2， 3 L，有則稱是分配格。 )()()()()()()()(2131213213121321llllllllllllll7 73 3 分配格和有補格分配格和有補格一、分配格一、分配格 1 1分配格的定義分配格的定義dcbaecdbadbca3636 例例1 1 對任意的集合對任意的集合A A，2A 是一是一個分配格，個分配格， = aa =a= aa =a因而因而 b(cd)b(cd)（bcbc）bdbd） 而bc)(bd） 例例2 2 b(cd) = be = b b(cd) = be = bebcda3737

27、 2 2 分配格的判別分配格的判別 定理定理7-12 7-12 在格在格L中，如果交運中，如果交運算對并運算是可分配的，則并運算對交運算也是算對并運算是可分配的，則并運算對交運算也是可分配的；如果并運算對交運算是可分配的，則可分配的；如果并運算對交運算是可分配的，則交運算對并運算也是可分配的。交運算對并運算也是可分配的。)()(321121llllll)(3211llll 證明 設在格中，對任意 1， 2， 3L，有 1 （ 2 3）=（ 1 2） （ 1 3 ）)()(32311lllll)()(3121llll則則)(321lll)()(32311lllll)()(3121321lllll

28、ll）（即即3838 例如例如 設設 L =1L =1，2 2，4 4，1616，3232，64, 64, 定定義在義在L L上的整除關系上的整除關系與與L L構成一個鏈構成一個鏈。 設是一個偏序集，若對于任意的 ， L，或者 ，或者 ，則稱是一個鏈。221ll 112ll6432164213939 例例3 3 每一個鏈每一個鏈都是一個都是一個分配格。分配格。證明證明 （1先證明先證明是一個格。是一個格。 由鏈的定義，對于任意 1， 2L或者 1 2 ，或者 2 1。 假設 1 2，則glb( 1, 2)= 1 ,lub( 1, 2)= 2假設假設 2 12 1，則，則glb( 1, 2)=

29、2 , lub( 1, 2)= glb( 1, 2)= 2 , lub( 1, 2)= 1 1 所以是一個格，可將其表示為。對任意 1, 2 L， 1 2=lub( 1, 2), 1 2=glb( 1, 2)4040(2) (2) 證明證明 L 是一個分配格是一個分配格對任意對任意 1, 2, 3L1, 2, 3L必有必有 2 32 3或者或者 3 23 2，不妨設不妨設 2 32 3， 于是有于是有 1 1 （ 2 32 3）= 1 3= 1 3。又因為又因為 1 2 1 31 2 1 3， 所以（所以（ 1 2） （ 1 3）= 1 3 因而因而 1 1 （ 2 32 3）= =（ 1 2

30、1 2） （ 1 1 3 3）假設假設 3 23 2，其證明方法類似，因此鏈，其證明方法類似，因此鏈是一是一個個分配格。分配格。 4141)()(1232llll)(123lll3133)(llll)(132lll 3分配格的性質 定理7-13 設 1， 2， 3是分配格中的任意三個元素， 那么 當且僅當323121,3121llllllll時時，有有證明證明 假設假設 ，則顯然，則顯然32ll3121, 3121llllll且且反之，設反之，設3121,3121llllll且且)()(1323llll)(1222llll那那么么4242 對于非分配格，定理713不成立。 c d = c b

31、, c d = c b ， 但但 b d 。例如，例如，e ed db bc ca a4343二二 有補格有補格 1 1最小元素最小元素0 0和最大元素和最大元素1 1 例例4 I4 是一個格，但這個是一個格，但這個格既無最小元素，又無最大元素。格既無最小元素，又無最大元素。N這個格有最小元素，但沒有最大元素。這個格有最小元素，但沒有最大元素。 格格2U 中無論中無論U U是什么樣的集合，是什么樣的集合，均有最小元素均有最小元素和最大元素和最大元素U U。4444具有最小元素和最大元素的格稱為有界格。具有最小元素和最大元素的格稱為有界格。 在有界格在有界格L中，對任意中，對任意L L，有，有0

32、 0 ， 1.1.于是由定理于是由定理7-37-3，對任意，對任意 ，有，有 11L1000 4545 2 2補元素補元素 定義定義7-9 7-9 設設L 是一個是一個有界格，有界格， L L，若存在元素，若存在元素 L L，使得，使得 =1=1 = 0 = 0，則稱，則稱 是是 的補元素。的補元素。 在任一有界格中0和1互為補元素。例例5 51 1a ab bc cd d0 01 1a ab bc cd de eg g0 0f f4646 因為對任意因為對任意S2US2U， 所以所以S S的補集的補集 是是S S的補元素。的補元素。SssUss, 例例6 6 格格 是是一個有補格，一個有補格

33、， ,;U2 3 3有補格有補格 定義定義7-10 7-10 設設L 是一個有是一個有界格，如果界格，如果L L中每一個元素都有補元素，中每一個元素都有補元素，則稱則稱L 是有補格。是有補格。 4747 (a)是分配格，但不是有補格， (c)既是有補格，又是分配格；例例7 7 是有補是有補分配格。分配格。 ,;U2三、有補分配格三、有補分配格 若格若格既是分配格，又是有補既是分配格，又是有補格，則稱格，則稱為有補分配格為有補分配格(d)是有補格，但不是分配格。是有補格，但不是分配格。)()()(cabacba (b)既不是分配格，又不是有補格；),()()(beaebae(a)(a)(b)(b

34、)(c)(c)(d)(d)1acb01ab01ab0c1acb0de4848 有補分配格有如下一些性質：有補分配格有如下一些性質： 定理定理7-14 在有補分配格在有補分配格中，任一元素的中，任一元素的補元素是唯一的。補元素是唯一的。使得使得 , , ， , ,11011202 于是于是 ， ， 由定理由定理 7-13 .212121 我們記我們記 的補元素為的補元素為 。1 證明證明 假設假設 有兩個補元素有兩個補元素 和和 ， 24949 定理定理7-15 7-15 （對合律）（對合律） 在有補分配格在有補分配格L 中，對每一中，對每一個個 ， 有有 。 L 證明證明 因為因為 ，由，由交

35、換律有交換律有 . . 0, 101,所以所以 是是 的補元素，由補元素的唯一性的補元素，由補元素的唯一性,故有故有 。 5050 定理7-16 （德摩根定律） 在有補分配格中，對于任意的 (a) (b) L21,21212121證明證明 （a a） )()(2121)()(2121由補元素的唯一性有由補元素的唯一性有2121)()(212211000)()(2211211115151證明：證明： 設設 ，那么，那么 （定理（定理7-3）定理定理7-17：在有補分配格：在有補分配格中，對任意的中，對任意的12,L 121212(1)()(2)(0)(3)(1)(1)(2)1212112122(

36、)122()100 于是于是所以所以120(2)(3)設設120由定理由定理7-15、7-16得：得：1011212即即1215252(3)(1)設設121那么那么111112()1112()()120()12即即121由定理由定理7-3得得125353練習練習5-65-61 1、填空、填空 （1 1下圖所表示的格中下圖所表示的格中 d d 有有 個補元素，它們分別是個補元素，它們分別是_. _. a a 有有 個補元素，它們是個補元素，它們是 . . b b 的補元素是的補元素是 。 3 a、b、c 1 d d1 1c cb bd da a0 05454B BB B A A(2) (2) 判

37、斷下列次序圖所表示的格是什么性質的格。判斷下列次序圖所表示的格是什么性質的格。 令令A A分配格；分配格；B B有補格；有補格；C C有補分配格；有補分配格； D D非分配格，非有補格非分配格，非有補格 在各次序圖下相應的括號內填入字母在各次序圖下相應的括號內填入字母 A A、B B、C C 或或D D。1 1c cb bd da a0 01 1c cb bd da a0 01 1c cb bd da a0 0( )( )( )55557.4 7.4 布爾代數(shù)布爾代數(shù)一一 布爾代數(shù)的定義布爾代數(shù)的定義 定義定義7-10 7-10 如果一個格是有補分如果一個格是有補分配格，則稱其為布爾代數(shù)，一般

38、記作配格，則稱其為布爾代數(shù)，一般記作 -。（1 1交換律：交換律： xyyxxyyx,（3) 3) 等冪律：等冪律：xxxxxx,（4 4吸收律：吸收律： xyxxxyxx)(,)(（2 2結合律：結合律： zyxzyx)()(zyxzyx)()( 布爾代數(shù)布爾代數(shù) B -具有如下性質，對于具有如下性質，對于B B中中任意元素任意元素x x，y y，z z，有，有5656（5 5分配律：分配律： )()()(zxyxzyx)()()(zxyxzyx（6 6同一律：同一律： xxxx1,0（7 7零一律：零一律： 00,11xx（8 8互補律：互補律： 0,1xxxx（9 9對合律：對合律： x

39、x （1010德德摩根定律：摩根定律： yxyxyxyx,5757 例例8 8 全集合全集合 U U 的冪集的冪集 2U 2U 上定義的集合的上定義的集合的并，交和補運算與并，交和補運算與 2U 2U 構成的代數(shù)系統(tǒng)構成的代數(shù)系統(tǒng)2U,稱作集合代數(shù)，它是一個布爾代數(shù)，稱作集合代數(shù)，它是一個布爾代數(shù)， 定義定義7-11 7-11 設設B-是一個代數(shù)系統(tǒng)，是一個代數(shù)系統(tǒng)， 和和 是是B B上的二元運算，上的二元運算，- - 是一元運算，是一元運算，若這些運算滿足交換律，分配若這些運算滿足交換律，分配律，同一律和互補律，則稱律，同一律和互補律，則稱B-是布爾代數(shù)。是布爾代數(shù)。 例例 設設 是一布爾代

40、數(shù)，是一布爾代數(shù)，,cbaU ,;2Ua,b,ca,cb,ca,bacb其次序圖如下：其次序圖如下：5858定理定理7-177-17：設：設B B是一個定義了一個一元運算是一個定義了一個一元運算“”和和兩個二元運算兩個二元運算、得得 集合，且這三個運算滿足交集合，且這三個運算滿足交換律、分配律、同一律和互補律，那么換律、分配律、同一律和互補律，那么 B ;是一布爾代數(shù)，且其余的六條性質也成立。是一布爾代數(shù)，且其余的六條性質也成立。定理定理7-18:7-18:任意任意x ,y Bx ,y B有有(1)11x 00 x(2)()xxyx()xxyx(3)xxxxxx（零一律）（零一律）（吸收律）（

41、吸收律）（等冪律）（等冪律）5959證明：（證明：（1x0（x 0）0同一）同一）（x 0）（x ）（互補）（互補）x （ 0 ） （分配律）（分配律） x （同一律）（同一律）0互補）互補）xxx（2x（x y）（）（x0） （x y） （同一律）（同一律）x （0 y）（分配律）（分配律）x 0 （零一律）（零一律）x （同一律）（同一律）6060證明：因為證明：因為x y）（ y）y （ x）y 0 y（x z） （ z） z （ x）z 0 z引理：對任意引理：對任意x，y，z B，若，若x yx z， y z則則 yz。xxxxxx所以所以yz定理定理7-197-19：對任意的：對任

42、意的x x，y y，z Bz B，有有（1x （y z）（）（x y） z（2x （y z）（）（x y） z（結合律）（結合律）6161證明：（證明：（2令令L x （y z ), M (x y） z 那么那么x Lx (x （y z )x （吸收律）（吸收律）x Mx (x y） z ) (x (x y）) (x z)（分配律）（分配律）x (x z) （吸收律）（吸收律） （吸收律）（吸收律）x所以所以x L x M類似可得類似可得 L Mxx再由引理即知再由引理即知LM。6262二、布爾代數(shù)的性質二、布爾代數(shù)的性質 定理定理7-20 布爾代數(shù)的每一子代數(shù)都是布爾代布爾代數(shù)的每一子代數(shù)都

43、是布爾代數(shù)。數(shù)。 定理定理7-21 7-21 布爾代數(shù)的每一滿同態(tài)象也是布布爾代數(shù)的每一滿同態(tài)象也是布爾代數(shù)。爾代數(shù)。 例例9 9 設設 ,cbaU ,;, ,cba ,那么 和等都是例等都是例8中中 的子代數(shù)的子代數(shù). ,;, ,cbacab ,;2U63637.57.5有限布爾代數(shù)的同構有限布爾代數(shù)的同構一、布爾代數(shù)的原子表示一、布爾代數(shù)的原子表示定義定義7-117-11：設：設 B ;是布爾代數(shù)，如是布爾代數(shù)，如果元素果元素a0a0，且對任意的，且對任意的x Bx B，有，有x ax aa a或或x x a a0 0，則稱，則稱a a是原子。是原子。定理定理7-227-22：設：設 B

44、;是一有限布爾代是一有限布爾代數(shù)，則對任意的數(shù)，則對任意的 x B x B 且且 x 0 x 0，一定存在，一定存在一個原子一個原子a a ，使得，使得x ax aa a或或a xa x）。）。定理定理7-237-23：如果：如果a1a1和和a2a2是布爾代數(shù)是布爾代數(shù) B ;的原子，且的原子，且a1 a2 0 a1 a2 0 ，則，則a1a1a2a2。6464定理定理7-247-24：設：設 B ; 是一有限布爾代數(shù)，是一有限布爾代數(shù)，對任意對任意x Bx B，x0 x0， a1a1，a2a2，.，anan是是 B ;中滿足中滿足ai xai x的所有原子，則的所有原子，則x xa1 a2

45、a1 a2 . an. an。注：此定理是說，注：此定理是說，B中任意非零元，均可由小于等于它的原中任意非零元，均可由小于等于它的原子的并表示。子的并表示。定理定理7-25：設：設 是一有限布爾代數(shù)是一有限布爾代數(shù) ，x是是B的的任意非零元素，任意非零元素， a1 ，a2 ，. ，an是是中滿中滿足足ai x的所有原子，則的所有原子，則xa1 a2 . an是將是將x表示成表示成原子的并的唯一方式。原子的并的唯一方式。定理定理7-26：設：設 是一有限布爾代數(shù)，是一有限布爾代數(shù)，M表示表示該代數(shù)系統(tǒng)中所有原子的集合，則該代數(shù)系統(tǒng)中所有原子的集合，則V1 與與V2同構。同構。6565推論：每一有

46、限布爾代數(shù)都有推論：每一有限布爾代數(shù)都有2nnZ個元素，元素個個元素，元素個數(shù)相同的布爾代數(shù)必同構。數(shù)相同的布爾代數(shù)必同構。6666 練習5-7 1 在下列各題后面的括號中鍵入“Y或“N來回答 各題中相應的問題。 （1） 設是一個五元素的分配格，問該格 是有補格嗎？（） （2） 設是一個九元素的有補格，問該格 是分配格嗎？ （） （3） U=a,b,c，2U ；是布爾代數(shù)嗎？( ) (4) 上題的2U； 的子代數(shù)是布爾代數(shù)嗎？ ( ) , , N NN NY YY Y6767 1證明在一個獨異點中所有左可逆元的集合形成一個子獨異點。證明證明 設設H H是獨異點是獨異點S; 中所有左可逆元的中所有左可逆元的集合，集合， e 是的單位元。因為e*e=e，所以e是左可逆元，故eH且H非空。 有a*bH, 故是的子獨異點。 設設a,bHa,bH，則必存在元素，則必存在元素 ， SS，使得，使得 * * a = e , a = e , * * b = e ,