離散數(shù)學(xué)習(xí)題解答格與布爾代數(shù)

1、離散數(shù)學(xué)習(xí)題解答習(xí)題五（第五章 格與布爾代數(shù)）1設(shè)L，是半序集，是L上的整除關(guān)系。問當(dāng)L取下列集合時，L，是否是格。 a) L=1，2，3，4，6，12b) L=1，2，3，4，6，8，12c) L=1，2，3，4，5，6，8，9，101263124解 a) L，是格，因為L中任兩個元素都有上、下確界。 b) L，不是格。因為L中存在著兩個元素沒有上確界。 例如：8Å12=LUB8，12不存在。8631241210c) L，不是格。因為L中存在著兩個元素沒有上確界。842698731510 倒例如：4Å6=LUB4，6不存在。2設(shè)A，B是兩個集合，f是從A到B的映射。證明：

2、S，是2B，的子格。其中S=y|y=f (x)，x2A證 對于任何B1S，存在著A12A，使B1=f（A1），由于f(A1)=y|yB($x)(xA1f (x)=y)B 所以B12B，故此S2B；又B0=f (A)S (因為A2A)，所以S非空；對于任何B1，B2S，存在著A1，A22A，使得B1=f (A1)，B2=f (A2)，從而LBB1，B2=B1B2=f (A1)f (A2) =f (A1A2) （習(xí)題三的8的1）由于A1A2A，即A1A22A，因此f (A1A2)S，即上確界LBB1，B2存在。對于任何B1，B2S，定義A1=f 1(B1)=x|xAf (x)B1，A2=f-1(B

3、2)=x|xAf (x)B2，則A1，A22A，且顯然B1=f (A1)，B2=f (A2)，于是GLBB1，B2=B1B2=f (A1)f (A2)f (A1A2) （習(xí)題三的8的2）又若yB1B2，則yB，且yB2。由于yB1=f (A1)=y|yB($x)(xA1f (x)=y)，于是存在著xA1，使f (x)=y，但是f (x)=yB2。故此xA2=f-1(B2)=x|xAf(x)B2，因此xA1A2，從而y=f (x)f (A1A2)，所以GLBB1，B2=B1B2=f (A1)f (A2) f (A1A2)這說明 GLBB1，B2=B1B2=f (A1)f (A2)=f (A1A2

4、)于是從A1A22A可知f (A1A2)S，即下確界GLBB1，B2存在。因此，S，是2B，的子格。3設(shè)L，是格，任取a，bL且ab。證明B，是格。其中B=x|xL 且 axb證 顯然BL；根據(jù)自反性及abb所以a，bB，故此B非空；對于任何x，yB，則有axb及ayb，由于x，yL，故有z1=xÅy為下確界L存在。我們只需證明z1，z2B即可，證明方法有二，方法一為：由于ax，所以aÅx=x，于是z1=xÅy =(aÅx) Åy （利用aÅx=x） =aÅ (xÅy) （由Å運算結(jié)合律） 因此az1；另

5、一方面，由yb可知yÅb=b，由xb可知xÅb=b，于是z1Åb=(xÅy) Åb=xÅ(yÅb) （由Å運算結(jié)合律）=xÅb （利用yÅb=b）=b （利用xÅb=b）因此 z1b，即 az1b 所以z1B由于ax及ay，所以a*x=a，a*y=a，因而a*z2=a* (x*y)=(a*x) *y （由*運算結(jié)合律）=a*y （利用a*x=a）=a （利用a*y=a）因而az2；又由于yb，所以y*b=y 于是z2=x*y=x* (y*b)=(x*y) *b （利用*運算結(jié)合律）=z

6、2*b從而z2b，即az2b 所以z2B 因此B，是格（是格L，的子格）。方法二：根據(jù)上、下確界性質(zhì)，由ax，ay，可得ax*y，（見附頁數(shù)）4設(shè)L，*，Å是格。"a，bL，證明：（附頁）axÅy，即az2，a又由xb，yb，可得xÅyb，x*yyb，即z1b，z2b所以az1b，az2b，故此z1，z2Ba*ba且a*bbÛa與b是不可比較的。證 先證Þ用反證法，假設(shè)a與b是可比較的，于是有ab或者ba。當(dāng)ab時，a*b=a與a*ba（得a*ba）矛盾；當(dāng)ba時，a*b=b與a*bb（得a*bb）矛盾；因此假設(shè)錯誤，a與b是不可比較

7、的。次證Ü由于a*ba，a*bb。如果a*ba，則ab，與a和b不可比較的已知條件矛盾，所以a*ba，故此a*ba；如果a*b=b，則ba，也與a和b不可比較的已知條件矛盾，所以a*bb，故此可得a*bb。5設(shè)L，*，Å是格。證明： a) (a*b) Å (c*d)(aÅ c) * (bÅ d)b) (a*b) Å (b*c)(c Å a)(aÅb) * (bÅc) * (cÅa)證 a) 方法一，根據(jù)上、下確界的性質(zhì)，由a*baaÅc及a*bbbÅd 所以得到a*b(a&#

8、197;c) * (bÅd)又由 c*dcaÅc及c*ddbÅd，所以得到c*d(aÅc) * (bÅd)因此(a*b) Å (c*d) (aÅc) * (bÅd)方法二 (a*b) Å (c*d) (aÅc) * (aÅd) * (aÅc) * (bÅd) （分配不等式，交換律，結(jié)合律，保序性） (aÅc) * (bÅd) （保序性） b) 方法一，根據(jù)上、下確界的性質(zhì)由a*baaÅb，a*bbbÅc，a*bacÅ

9、a可得 a*b(aÅb) * (bÅc) * (cÅa)同理可得 b*c(aÅb) * (bÅc) * (cÅa)及 c*a(aÅb) * (bÅc) * (cÅa)所以 (aÅb) Å (bÅc) Å (cÅa)(aÅb) * (bÅc) * (cÅa) 方法二：(aÅb) Å (bÅc) Å (cÅa) b* (aÅc) Å (c*a) （交換律，結(jié)合律

10、，分配不等式，保序性） bÅ (c*a) * (aÅc) Å (c*a)（分配不等式，交換律，） (aÅb) * (bÅc) * (aÅc)（分配不等式，結(jié)合律，交換律，吸收律，保序性） (aÅb) * (bÅc) * (cÅa) （結(jié)合律）6設(shè)I是整數(shù)集合。證明：I，min，max是分配格。證 由于整數(shù)集合I是全序集，所以任何兩個整數(shù)的最小者和最大者是存在的，因此I，min，max是格是格是顯然的。下面我們來證I，min，max滿足分配律對于任何a，b，cI 有a* (bÅc)=mina，ma

11、xb，c(a*b) Å (a*c)=minmina，b，mina，c（1）若bc時，當(dāng) （a） ab，則ac ，故此 mina，maxb，c=mina，c=a maxmina，b，mina，c=maxa，a=a （b）bac ，則 mina，maxb，c=mina，c=a maxmina，b，mina，c=maxb，a=a （c）ca，則ba，因此 mina，maxb，c=mina，c=c maxmina，b，mina，c=maxb，a=c（2）若cb時，當(dāng) （a）ac，則ab，故此 mina，maxb，c=mina，b maxmina，b，mina，c=mina，a=a（b）cab

12、，則 mina，maxb，c=mina，b=a maxmina，b，mina，c=maxa，c=a （c）ba，則ca，因此 mina，maxb，c=mina，b=b maxmina，b，mina，c=maxb，c=b綜合（1）（2）總有 a* (bÅc)=(aÅb) * (aÅ c)根據(jù)對偶原理，就還有 aÅ (b*c)=(aÅb) * (aÅc)因此I，min，max是分配格。7設(shè)A，*，Å，max是分配格，a，bA且ab。證明： f (x)=(xÅa) *b是從A到B的同態(tài)函數(shù)。其它 B=x|xA且axb證

13、由于axÅa，及已知ab，所以a(xÅa)*b；其次(xÅa)*bb，所以af (x) b，因而f (x)是從A到B的函數(shù)。對于任何x，yA，f(xÅy)=(xÅy)Åa)*b =(xÅa) Å (yÅa) *b（冪等律，交換律，結(jié)合律） =(xÅ*a)b)(yÅa) *b)（分配律） =f (x) Åf (y)f (x*y) =(x*y) Åa) *b =(xÅa) * (yaÅ)*b （分配律） =(xÅa) *b)(yÅ

14、a) *b) （冪等律，交換律，結(jié)合律） =f (x) *f (y)所以，f滿足同態(tài)公式，因而f 是從A到B的同態(tài)函數(shù)。8證明：一個格是分配格的充分必要條件是"a，b，cL，有(a*b) Å (b*c) Å (c*a)=(aÅb) * (bÅc) * (cÅa)證 必要性。對于任何a，b，cL，(a*b) Å (b*c) Å (c*a)=(b* (aÅc) Å (c*a) （交換律，分配律）=(bÅ (c*a) * (aÅc) Å (c*a) （分配律）=(b

15、97;c) * (bÅa) * (aÅc) （分配律，吸收律）=(aÅb) * (bÅc) * (cÅa) （交換律）充分性，f滿足同態(tài)公式，因而f是從A到B的同態(tài)函數(shù)。8證明：一個格是分配格的充分必要條件是"a，b，cL，有(a*b) Å (b*c) Å (c*a)=(aÅb) * (bÅc) * (cÅa)證 必要性。對于任何a，b，cL，(a*b) Å (b*c) Å (c*a)=(b* (aÅc) Å (c*a) （交換，分配律）=(b&

16、#197; (c*a)( aÅ c) Å (c*a) （分配律）=(bÅc) * (bÅa) * (aÅc) （分配律，吸收律）=(aÅb) * (bÅc) * (cÅa) （交換律）充分性，對于任何a，b，cL aÅ (b*c)=(aÅ (a*c) Å (b*c) （吸收律）=(aÅ (a*b) Å (a*c) Å (b*c) （吸收律）=(a*b) Å (b*c) Å (c*a) Å a （交換律，結(jié)合律）=(aÅ

17、;b) * (bÅc) * (cÅa) Åa （已知條件）=(aÅb) * (aÅc) * (bÅc) Å (bÅc) *a) Å a （交換律，吸收律）=(aÅb) * (aÅc) * (bÅc) Å (bÅc) *a) Å (a* (aÅ b) * (aÅ c) （吸收律）=(aÅb) * (aÅc) Å (bÅc) * (bÅc) Åa) * (aÅ

18、(aÅ b) * (aÅc) （已知條件）=(aÅb) * (aÅc) Å (bÅc) * (aÅbÅc) *(aÅ b)* (aÅc)（因為aÅ (aÅb) * (aÅc)= (aÅb) * (aÅc)=(aÅb) * (aÅc) Å(bÅc) * (aÅb)Åc) *(aÅ b)* (aÅc) （結(jié)合律）=(aÅb) * (aÅc) Å

19、;(bÅc) *(aÅ b)* (aÅc) （吸收律，結(jié)合律）cehabdfig=(aÅ b)* (aÅc) （吸收律）根據(jù)對偶原理 還有a* (bÅc)= (aÅb) * (aÅc)所以格L是分配格。9設(shè)L，是格。其Hasse圖如右 a) 找出格中每個元素的補元；b) 此格是有補格嗎？c) 此格是分配格嗎？解 a)最小元0=i；最大元1=a；故此格為有界格。a和i互為補元；f和C互為補元；其余b，d，e，g，h等都沒有補元。b) 根據(jù)a) 可知，此格不是有補格。c) 此格不是分配格，因為fÅ (g* h

20、)=fÅ i=f (fÅg) * (fÅh)=b* d=d 因為去掉g結(jié)點后所形成的子格與分配格S24，I，GCD，LCM，1，24同構(gòu)，因此若此格不是分配格，則必有子格h * (fÅg)=h*b=ha1a3a2a4a52484213612b1b4b5b3b2(h*f) Å (h*g)=iÅi=IS24，I，GCD，LCM，1，24 兩個不是分配格的特殊格與兩個不是分配格的特殊格同構(gòu)，并且此子格必含有g(shù)點。而特殊不分配格之圖或是含有五個結(jié)點的圈，或是有六個結(jié)點：gebdfi；gebdhi；gehdfi；或是有八個結(jié)：gecabdfi；

21、gecabdhi；或是只有一個四結(jié)點的圈：gehi。因此此格絕不會有含g點的子格與兩個不是分配格的特殊格同構(gòu)。10設(shè)L，*，Å是有界格。x，yL，證明： a) 若xÅy=0，則x=0且y=0。b) 若x*y=1，則x=1且y=1。證 a) 對任何x，yL，若xÅy=0，則x=x* (xÅy) （吸收律） =x*0 （xÅy=0）=0 （01律）y=y* (yÅx) （吸收律） =y* (xÅy) （交換律） =y*0 （xÅy=0） =0 （01律）b) 對任何x，yL，若x*y=1，則 x=xÅ (x*

22、y) （吸收律） =xÅ1 （x*y=1） =1 （01律）y=yÅ (y*x) （吸收律） =yÅ (x*y) （交換律） =yÅ1 （x*y=1） =1 （01律）11在有界格中，0是1的唯一補元，1是0的唯一補元。證 由于1Å0=1，1*0=0，所以0與1互為補元。下面我們先來證0是1的唯一補元：對于任何元素a屬于有界格，若a是1的補元，則必有1Åa=1，及1*a=0，于是必有a=a* (aÅ1) （吸收律） =a* (1Åa) （交換律） =a*1 （由1Åa=1） =1*a （交換律） =0 （

23、由1*a=0）從而0是1的唯一補元。次證1是0的唯一補元。對于任何元素a屬于有界格，若a是0的補元，則必有0Åa=1，0*a=0。于是必有 a=a(a*0) （吸收律） =a(0Åa) （交換律） =aÅ0 （由0*a=0） =0Åa （交換律） =1 （由0Åa=1）12設(shè)L，是格，|L|2。證明：L中不存在以自己為補元的元素。證 用反證法，假設(shè)L中存在著以自己為補元的元素，不妨是bL，那么bÅb=1，b*b=0，于是由冪等律，可得b=b*b=0，bÅb=1，從而有0=b=1，即0=1因此，對于任何元素aL，都有a=0=1

24、（因為0a1），從而|L|=1，這與已知|L，|2矛盾。13設(shè)L，是全序集，|L|3。證明：L，是格，但不是有補格。證 由于L，是全序集，那么L中任意兩個元素都可比較，于是L中任意兩個元素都有上確界和下確界，因此L，是格。下面我們來證L，不是有補格，用反證法：否則L，是有補格，則對任何aL，都存在著一個元素bL，使aÅb=1及a*b=0。由于L，是全序集，所以任二元素可比較，從而若ab，則a=a*b=0若ba，則a=aÅb=1因此|L|=2，與已知|L|3矛盾。14在有界的分配格中，證明：具有補元的那些元素組成一個子格。證 設(shè)L，*，Å，0，1是有界分配格，令 L

25、=x|xL($yL)(x*y=0xÅy=1)我們來證L，*，Å，0，1是L，*，Å，0，1的子格： 顯然LL；其次易證0，1L，故此L非空；對于任何a1，a2L，我們來證a1*a2，a1Åa2L為證a1*a2L，只需找出a1*a2的補元即可。由于a1，a2L，故此存在著b1，b2L，使a1*b1=0，a1Åb1=1以及a2*b2=0，a2Åb2=1，于是構(gòu)造出a1*a2補元為b1b2L。這是因為(a1*a2) * (b1Åb2)=(a1*a2) * b1) Å(a1*a2) * b2) （分配律） =(a1*b1)

26、 *a2) Å(a1*(a2 * b2) （交換律） =(0*a2) Å(a1*0)（由a1*b1=0，a2b2=0） =0Å0 （由01律） =0(a1*a2) Å (b1Åb2)=(a1Å (b1Å b2) * (a2Å (b1Å b2)（分配律） =(a1Åb2) Åb2) * (a2Åb2) Åb1)（交換律，結(jié)合律） =(1Åb2)* (1Åb1)（由a1Åb1=1及a2Åb2=1） =1*1（由01律） =1為證a

27、1Åa2L只需找出a1Åa2的補元即可。由于a1，a2的補元是b1，b2，故構(gòu)造出a1Åa2的補元為b1*b2L。這是因為 (a1Åa2) * (b1*b2)=(a1* (b1* b2) Å(a2* (b1* b2)（分配律） =(a1*b2) *b2) Å (a2*b2) *b1)（交換律，結(jié)合律） =(0*b2) Å (0*b1)（由a1*b1=0及a2*b2=0） =0Å0（由01律） =0 (a1Åa2) Å (b1*b2)=(a1Åa2) Åb1) * (a1

28、97;a2) Åb2)（分配律）= (a1Åb1) Åa2) * (a1Å (a2Åb2)（交換律，結(jié)合律）=(1Åa2) * (a1Å1)（由a1Åb1=1及a2Åb2=1）=1*1 （由01律）=1124213615求S12，1的所有子格，其中，S12是12的所有因子的集合1是S12上的整除關(guān)系。 解 一個結(jié)點：1，2，3，4，6，12 二個結(jié)點：1，2，1，3，1，4，1，6，1，122，4，2，6，2，123，6，3，124，126，12三個結(jié)點：1，2，4，1，2，6，1，2，12S12，1的圖

29、1，3，6，1，3，121，4，121，6，122，4，12，2，6，123，6，12四個結(jié)點：1，2，4，12，1，2，6，12，1，3，6，121，2，3，6，2，4，6，12，1，3，4，12五個結(jié)點：1，2，4，12，1，2，3，6，12六個結(jié)點：S12=1，2，3，4，6，12都是S12，1的子格。16證明：一個格L，分配格的充分必要條件是"a，b，cL，有(aÅb) *caÅ (b*c)證 必要性對任何a，b，cL (aÅb) *c=(a*c) Å (b*c) （分配律） aÅ (b*c) （由a*ca，及保序性）充分性一

30、方面，由aÅ (b*c)aÅ b （根據(jù)b*cb及保序性）和aÅ (b*c)aÅ c （根據(jù)b*cc及保序性）及上、下確界的性質(zhì)可得 aÅ (b*c)(aÅ b) * (aÅ c)另一方面(aÅ b) * (aÅ c) aÅ (b* (aÅ c)（已知條件）=aÅ (aÅ c) *b)（交換律）aÅ (aÅ (c*b)（已知條件(aÅc)*baÅ (c* b)及保序性）=(aÅa) Å (b*c)（結(jié)合律，

31、交換律）=aÅ (b*c)（冪等律）所以，綜合這兩方面，得到分配律 aÅ (b*c)=(aÅ b) * (aÅ c)根據(jù)對偶原理，可得另一分配律 a* (bÅ c)=(a*b) Å (a*c)所以格L，是分配格。17設(shè)L1，R1和L2，R2是兩個格，f：L1L2是從L1，R1到L2，R2的同態(tài)函數(shù)。證明：f的同態(tài)象是L2，R2的子格。證 f的同態(tài)象f (L1) = y : yL2($xL1) (f(x)=y)我們來證f (L1)，R2是L2，R2的子格：顯然f (L1)L2；若L1非空，則有aL1，從而有b=f (a)f (L1)故f

32、 (L1)非空。對于任何b1，b2f (L1)，存在著a1，a2L1，使b1=f (a1)，b2=f (a2)，從而 b1 Å2b2=f (a1) Å2f (a2)110102221555=f (a1Å1a2)（同態(tài)公式）f (L1)（因L1，R1是格，故Å1運算封閉，從而a1Å1a2L1）因此f（L1），R1是L2，R2子格。18設(shè)B=1，2，5，10，11，22，55，110。證明：B，GCD，LCM是布爾代數(shù)。其中，GCD是求最大公約數(shù)，LCM是求最小公倍數(shù)，x=110/x。 證 我們已證過N，GCD，LCM，是分配格，故此為證B，GCD

33、，LCM是分配格，只需證B，GCD，LCM是N，GCD，LCM，的子格即可。易于驗證，對于任何a，bB，恒有GCDa，b，LCMa，bB故此兩個運算GCD，LCM關(guān)于B封閉。因而B，GCD，LCM是分配格。又由于1和110互為補元；2和55互為補元；5和22互為補元；10和11互為補元，所以B，GCD，LCM，是有補的分配格，故此B，GCD，LCM，是布爾代數(shù)。19設(shè)L1=1，2，3，4，6，12，L2=1，2，3，4，6，8，16，24。2412631248 a) L1，GCD，LCM，是布爾代數(shù)嗎？為什么？b) L2，GCD，LCM，是布爾代數(shù)嗎？為什么？解 a) L1，GCD，LCM，不

34、是布爾代數(shù)。因為L1，GCD，LCM，雖是分配格（N，1，GCD，LCM，的子格）但不是有補格，元素2，6沒有補元。所以不是布爾代數(shù)。 b) L2，GCD，LCM，也不是布爾代數(shù)。因為雖然L2，GCD，LCM，是分配格（N，1，GCD，LCM，的子格），但不是有補格，元素2，4，6，12沒有補元。所以也不是布爾代數(shù)。20設(shè)B，*，Å，是布爾代數(shù)。證明下列布爾恒等式。 a) aÅ (a*b)=aÅbb) a* (aÅb)=a*bc) (a*c) Å (a*b) Å (b*c)=(a*c) Å (a*b)d) (aÅ

35、b) * (bÅ c) * (cÅ a)=(aÅ b) * (bÅ c) * (cÅ a)e) (aÅ b) * (bÅ c) * (cÅ a)=(a*b) Å (b*c) Å (c*a)證 a) aÅ (a*b)=(aÅa) * (aÅb)（分配律）=1* (aÅb) （由aÅa=1）=aÅb （01律） b) a (aÅb)=(a*a) Å (a*b)（分配律）=1Å (a*b) （由a*a=0）= a

36、*b （01律） c)由于(a*c) Å (a*b) =(aÅa) * (aÅb)* (a*c) * (b*c)（分配律，結(jié)合律，交換律）= (aÅb)* (aÅc) * (bÅc) （由aÅa=1）并且因為b*aÅb，c*aÅc，從而由保序性，得到b*c(aÅb) * (aÅc)又由b*cbÅc及下確界的性質(zhì)，得到b*c(aÅb) * (aÅc) * (bÅc)所以b*c(a*c) Å (a*b)所以(a*c) Å (a*b

37、) Å (b*c)= (a*c) Å (a*b) d) 令B=(aÅb) * (bÅc) * (cÅa)，C=(aÅb) * (bÅc) * (cÅa) 于是為證B=C，根據(jù)布爾代數(shù)的性質(zhì)：消去律。 = a*b*c （交換律）所以 a*B=a*c從而由消去律，有B=C 即 (aÅb) * (bÅc) * (cÅa)=(aÅb) * (bÅc) * (cÅa) e) 令B=(aÅb) * (bÅc) * (cÅa) C=(a*

38、b)Å(b* c)Å(c* a) 由于a* B=a* (aÅb) * (bÅc) * (cÅa) =a* (bÅc) * (cÅa) （吸收律） =a* (aÅc) * (bÅc) （交換律） =a* (bÅc)（吸收律） a* C=a* (a* b)Å(b* c)Å(c* a) =(a* a* b)Å(a* b* c)Å(a* a* c) （分配律，交換律） =(a* b)Å(a* b* c)Å(a* c) （冪等律） =(a* b)

39、Å(a* c) （分配律）所以 a* B=a* C又由于 a* B=a* (aÅb) * (bÅC) * (cÅa) = a* b* (bÅc) * (cÅa) （反身性，及本題b） = a* b*(cÅa) （吸收律） = a* b* c （交換律，反身律，本題b） a*C= a(a* b)Å(b* c)Å(c* a)=(a* a* b)Å(a* b* c)Å(a* a* c)（分配律，交換律）=(0* b)Å(a* b* c)Å(0* c) （由a* a=0）=

40、0Å(a* b* c)Å0 （11律）=a* b* c只需證a* B=a* C和a* B=a* C 即可由于 a* B=a* (aÅb) * (bÅc) * (cÅa)= a* (bÅc) * (cÅa) （吸收律）= a*(aÅ c) * (bÅc) （交換律）=a* c* (cÅb) （本題b）及交換律）=a* c* b （本題b）=a* b* c （交換律）a* C=a* (aÅb) * (bÅC) * (cÅa)=a* b* (bÅC) * (c&

41、#197;a) （本題b）=a* b* c* (cÅa) （本題b）=a* b* c* a （本題b）=a* a* b* c （交換律）=a* b* c （冪等律）所以 a* B=a* C又由于 a* B=a* (aÅb) * (bÅc) * (cÅa)=a* (a) Åb) * (bÅc) * (cÅa) （反身性）=a* b* (b)Åc) * (cÅa) （本題b）及反身性）=a* b* c* (c)Åa) （本題b）及反身性）=a* b* c* a （本題b）=a* a* b* c （交

42、換律）=a* b* c （冪等性）a*C= a* (aÅb) * (bÅc) * (cÅa)= a* (bÅc) * (cÅa) （吸收律）= a* (a) Åc) * (bÅc) （交換律及反身性）= a* c* (c)Åb) （本題b）及反身性交換律）= a* c* b （本題b）所以 a* B=a* C故根據(jù)消去律得到B=C，即(aÅb) * (bÅC) * (cÅa)=(a* b)Å(b* c)Å(c* a)21設(shè)B，*，Å，是布爾代數(shù)，簡化下列布

43、爾表達式。 a) (a* b)Å(a* b* c)Å(b* c)b) (a* b)Å(a* b* c)Å(b* c) c) (a* b)Å(a* b* c)Å(b* c)d) (a* b)Åc) * (aÅb) * c解 a) (a* b)Å(a* b* c)Å(b* c)= (a* b)Å (b* c) （因為吸收律）=b* (aÅc) （分配律） b) (a* b)Å(a* b* c)Å(b* c)=(a* b)Å(a* b)Åb)

44、* c （分配律）=(a* b)Å(a* b)* c) （20題a）=(a* b)Å(a* c) Å (b* c) （分配律）c) (a* b)Å(a* b* c)Å(b* c) =( b *( aÅ(a* c)Å(b* c) （分配律） =( b *( aÅa)* (aÅc)Å(b* c) （分配律） =(b* (aÅ c)Å(b* c) （互補aÅa=1） =b* (aÅcÅc) （分配律） =b （互補cÅc=1）d) (a* b

45、)Åc) * (aÅb) * C =(a* b)Åc) * c* (aÅb) （交換律） =c* (aÅb) （吸收律）22設(shè)B，*，Å，是布爾代數(shù)。在B上定義二元運算如下"a，bB，ab=(a*b)(a*b)證明：B，Ä是交換群證 封閉性對于任何a，bB，由于*，Å，運算的封閉性，可知ab=(a*b)Å(a*)B，因此運算具有封閉性。結(jié)合律對于任何a，b，cB， (ab)c (ab)*c)Å(ab)*c) =(a*b)Å(a*b) *c)Å(a*b)Å(

46、a*b)*c) =(a*b*c)Å(a*b*c)Å(aÅb) * (aÅb) *c) （分配律，deMorgan律，反身律） =(a*b*c)Å(a*b*c)Å(a*b) Å (aÅb) *c) （分配律，互補律，01律） =(a*b*c)Å(a*b*c)Å(a*b*c) Å (a*b*c) =(a*b*c)Å(a*b*c)Å(a*b*c) Å (a*b*c)（交換律） a(bc) =(a* (bc)Å(a* (bc) =(a*(bÅc

47、) * (bÅc)Å(a* b*c) Å(a* b*c) （de Morgam 律，反身律，分配律） =(a* (b*c)Å(b*c)Å(a*b*c)Å(a*b*c) （分配律）所以 (ab)c=a(bc)所以運算具有結(jié)合律交換律對任何a，bB，ab=(a*b)Å(a*b)=(a*b)Å(a*b) （Å運算交換律）=(b*a)(b*a) （*運算交換律）=ba 所以運算具有結(jié)合律有幺元0：首先0B，其次 a0=(a*0)Å(a*0) =(a*1)(a*0) （由0=1） =aÅ0 （0

48、1律） =a （01律）由運算交換律也有0a=a 即 0a=a0=a所以0是運算的幺元。于任何aB，其逆元是a自己，因為aa=(a*a)Å(a*a)=0Å0 （互補律）=0 （冪等律）因此，B，是一個交換群。23設(shè)B，*，是一個交換群。如下"a，bB，a+b=(a*b)Å(ab)a·b=a*b a) 證明：B，+，·是環(huán) b) 找出關(guān)于·的幺元；c) 證明："aB，a+a=0，a+0=a，a+1=a；d) 證明："a，bB，（a+b）+b=a；e) 證明："a，b，cB，a·（b+c）

49、=(a·b)+（a·c）證 a) 由于這里定義的十運算與22題的運算的定義相同，因此B，十是交換群。 其次·運算就是運算，故此具有封閉性及結(jié)合律，因此B，·是半群。 對任何a，b，cB，由于 a·(b+c)=a* (b*c)Å(b*c) =(a*b*c)Å(a*b*c) （分配律） (a·b)+(a·c)=(a*b) *(a*c)(a*b)* (a*c)=(a*b) * (aÅc)Å(aÅb) * (a*c)（deMorgan律）=(a*b*c)Å(a*b*c)（分

50、配律，互補律，01律）所以a·（b+c）=（a·b）+（a·c）由于·和十運算都有交換律，故另一分配律不需證所以B，+，·是環(huán)（實際上是含幺交換環(huán)） b) ·的幺元是1，因為 1·a=1*a=a=a*1=a·1 c) 對任何aB，a+a=0在22題的證明已證； a+0=a在22題的證明中已證；a+1+=(a*1)Å(a*1)=(a*0)Å(a*1) （由1=0）=0Åa（01律）=a （01律）d) 對任何a，bB （a+b）+b=(a+b) *b)Å(a+b)*b)=(a*

51、b)Å (a*b) *b)Å(a*b) * (a*b)*b)=(a*b*b)Å(a*b*b)Å(aÅb) * (aÅb) *b)（分配律，結(jié)合律de Morgan律，反身律）=(a*b)Å(a*b)Å(a*b) *b)（冪等律，互補律0-1律，分配律，交換律）=(a*b)Å(a*b*b)Å(a*b*b)（分配律）=(a*b)Å(a*b)（冪等，互補律，0-1律）=a* (bÅb) （分配律）=a （互補律，0-1律）e) 根據(jù)a) 的證明，分配律已成立。24設(shè)A，和B，是兩個

52、布爾代數(shù)，f是從A，到B，的滿同態(tài)函數(shù)。證明：f(OA)=OB f(1A)=1B其中，OA和OB分別是A，B中的最小元，1A和1B分別是A，B中的最大元。證 對于任何aA，由于A是布爾代數(shù)，所以存在著補元A使得OA=a 及1A=a （互補律）又由于B是布爾代數(shù)，f是從A到B的同態(tài)函數(shù)，從而有f()=(f(a) （同態(tài)公式）于是f(OA)=f(a)=f(a)f() （同態(tài)公式）=f(a)(f(a)=OB （互補律）f(1A)=f(a)=f(a)f() （同態(tài)公式）=f(a)(f(a)=1B25設(shè)a，b，b2，br是布爾代數(shù)B，*，Å，的原子。證明：ab1Åb1Å&#

53、197;br的充分必要條件是存在i（1ir），使a=bi。證 必要性 用反證法。假設(shè)對每個i，1ir，都有abi，那么由a，bi（1ir）都是原子，因此a*bi=0（否則有a=a*bi=bi，與假設(shè)abi矛盾）。從而 a* (b1Åb2ÅÅbr) =(a*b1)Å(a*b2)ÅÅ(a*br) （分配律） =0Å0ÅÅ0 =0 (0-1律)但是由已知ab1Åb2Å Åbr，從下確界的性質(zhì)可知 a* (b1Åb2Åbr)=a從而得到a=0，這與已知a是原子，a

54、0矛盾，充分性若對某個i。1i0r，使a=bi0。則由上確界的性質(zhì)可知ab1Åb2ÅÅ -1ÅaÅ +1ÅÅbr=b1Åb2ÅÅ-1Å +1Åbr（因為a=）26設(shè)b1，b2，br是有限布爾代數(shù)B，*，Å，的所有原子。證明：y=0的充分必要條件"i（1ir），都有y*bi=0證 必要性對于任何bi（1ir） y*bi=0*bi=0總是成立，因為y=0充分性根據(jù)布爾代數(shù)的元素的原子表示定理，可知y= 這里S(y)=bi :1irbiy因此，y=y*y （冪等

55、律） =y = （分配律） =0 （因為對任何i，1ir，都有y*bi=0） =0 （0-1律）27設(shè)0，1，*，Å，是布爾代數(shù)。寫出下列布爾表達式的析取范式和合取范式。 a) (x1*x2)Å(x2*x3)Å(*x3) b) (x1*x2*)Å(x1*x4)Å(x2*) 解 a) 令f(x1，x2，x3)=(x1*x2)Å(x2*x3)Å(*x3)是0，13到0，1函數(shù)，則其運算表為x1x2x3f (x1，x2，x3)00000011010001111000101111011111 根據(jù)f (x1，x2，x3)=0的元組可構(gòu)造出f的合取范式為 (x1Åx2Åx3)* (x1Å Åx3)(x2 Å Åx3)=M3* M5* MT 根據(jù) f (x1，x2，x3)=1的元組可構(gòu)造出f的析取范式為 (Å Åx3) Å(Å x2Åx3)Å=m1Åm3Åm5Åm6Åm7b) 令g(x1，x2，x3