离散数学习题解答格与布尔代数

1、离散数学习题解答习题五（第五章 格与布尔代数）1设L，是半序集，是L上的整除关系。问当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设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) （习题三的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) （习题三的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设L，是格，任取a，bL且ab。证明B，是格。其中B=x|xL 且 axb证 显然BL；根据自反性及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) （由Å运算结合律） 因此az1；另

5、一方面，由yb可知yÅb=b，由xb可知xÅb=b，于是z1Åb=(xÅy) Åb=xÅ(yÅb) （由Å运算结合律）=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 （由*运算结合律）=a*y （利用a*x=a）=a （利用a*y=a）因而az2；又由于yb，所以y*b=y 于是z2=x*y=x* (y*b)=(x*y) *b （利用*运算结合律）=z

6、2*b从而z2b，即az2b 所以z2B 因此B，是格（是格L，的子格）。方法二：根据上、下确界性质，由ax，ay，可得ax*y，（见附页数）4设L，*，Å是格。"a，bL，证明：（附页）axÅy，即az2，a又由xb，yb，可得xÅyb，x*yyb，即z1b，z2b所以az1b，az2b，故此z1，z2Ba*ba且a*bbÛa与b是不可比较的。证 先证Þ用反证法，假设a与b是可比较的，于是有ab或者ba。当ab时，a*b=a与a*ba（得a*ba）矛盾；当ba时，a*b=b与a*bb（得a*bb）矛盾；因此假设错误，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设L，*，Å是格。证明： a) (a*b) Å (c*d)(aÅ c) * (bÅ d)b) (a*b) Å (b*c)(c Å a)(aÅb) * (bÅc) * (cÅa)证 a) 方法一，根据上、下确界的性质，由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) （分配不等式，交换律，结合律，保序性） (aÅc) * (bÅd) （保序性） b) 方法一，根据上、下确界的性质由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) （交换律，结合律

10、，分配不等式，保序性） bÅ (c*a) * (aÅc) Å (c*a)（分配不等式，交换律，） (aÅb) * (bÅc) * (aÅc)（分配不等式，结合律，交换律，吸收律，保序性） (aÅb) * (bÅc) * (cÅa) （结合律）6设I是整数集合。证明：I，min，max是分配格。证 由于整数集合I是全序集，所以任何两个整数的最小者和最大者是存在的，因此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时，当 （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时，当 （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)根据对偶原理，就还有 aÅ (b*c)=(aÅb) * (aÅc)因此I，min，max是分配格。7设A，*，Å，max是分配格，a，bA且ab。证明： f (x)=(xÅa) *b是从A到B的同态函数。其它 B=x|xA且axb证

13、由于axÅa，及已知ab，所以a(xÅa)*b；其次(xÅa)*bb，所以af (x) b，因而f (x)是从A到B的函数。对于任何x，yA，f(xÅy)=(xÅy)Åa)*b =(xÅa) Å (yÅa) *b（幂等律，交换律，结合律） =(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) （幂等律，交换律，结合律） =f (x) *f (y)所以，f满足同态公式，因而f 是从A到B的同态函数。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满足同态公式，因而f是从A到B的同态函数。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 （交换律，结合律）=(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) （结合律）=(aÅb) * (aÅc) Å

19、;(bÅc) *(aÅ b)* (aÅc) （吸收律，结合律）cehabdfig=(aÅ b)* (aÅc) （吸收律）根据对偶原理 还有a* (bÅc)= (aÅb) * (aÅc)所以格L是分配格。9设L，是格。其Hasse图如右 a) 找出格中每个元素的补元；b) 此格是有补格吗？c) 此格是分配格吗？解 a)最小元0=i；最大元1=a；故此格为有界格。a和i互为补元；f和C互为补元；其余b，d，e，g，h等都没有补元。b) 根据a) 可知，此格不是有补格。c) 此格不是分配格，因为fÅ (g* h

20、)=fÅ i=f (fÅg) * (fÅh)=b* d=d 因为去掉g结点后所形成的子格与分配格S24，I，GCD，LCM，1，24同构，因此若此格不是分配格，则必有子格h * (fÅg)=h*b=ha1a3a2a4a52484213612b1b4b5b3b2(h*f) Å (h*g)=iÅi=IS24，I，GCD，LCM，1，24 两个不是分配格的特殊格与两个不是分配格的特殊格同构，并且此子格必含有g点。而特殊不分配格之图或是含有五个结点的圈，或是有六个结点：gebdfi；gebdhi；gehdfi；或是有八个结：gecabdfi；

21、gecabdhi；或是只有一个四结点的圈：gehi。因此此格绝不会有含g点的子格与两个不是分配格的特殊格同构。10设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设L，是格，|L|2。证明：L中不存在以自己为补元的元素。证 用反证法，假设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设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在有界的分配格中，证明：具有补元的那些元素组成一个子格。证 设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，于是构造出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)（交换律，结合律） =(1Åb2)* (1Åb1)（由a1Åb1=1及a2Åb2=1） =1*1（由01律） =1为证a

27、1Åa2L只需找出a1Åa2的补元即可。由于a1，a2的补元是b1，b2，故构造出a1Åa2的补元为b1*b2L。这是因为 (a1Åa2) * (b1*b2)=(a1* (b1* b2) Å(a2* (b1* b2)（分配律） =(a1*b2) *b2) Å (a2*b2) *b1)（交换律，结合律） =(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)（交换律，结合律）=(1Åa2) * (a1Å1)（由a1Åb1=1及a2Åb2=1）=1*1 （由01律）=1124213615求S12，1的所有子格，其中，S12是12的所有因子的集合1是S12上的整除关系。 解 一个结点：1，2，3，4，6，12 二个结点：1，2，1，3，1，4，1，6，1，122，4，2，6，2，123，6，3，124，126，12三个结点：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四个结点：1，2，4，12，1，2，6，12，1，3，6，121，2，3，6，2，4，6，12，1，3，4，12五个结点：1，2，4，12，1，2，3，6，12六个结点：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 （根据b*cb及保序性）和aÅ (b*c)aÅ c （根据b*cc及保序性）及上、下确界的性质可得 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)（结合律，

31、交换律）=aÅ (b*c)（幂等律）所以，综合这两方面，得到分配律 aÅ (b*c)=(aÅ b) * (aÅ c)根据对偶原理，可得另一分配律 a* (bÅ c)=(a*b) Å (a*c)所以格L，是分配格。17设L1，R1和L2，R2是两个格，f：L1L2是从L1，R1到L2，R2的同态函数。证明：f的同态象是L2，R2的子格。证 f的同态象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)（同态公式）f (L1)（因L1，R1是格，故Å1运算封闭，从而a1Å1a2L1）因此f（L1），R1是L2，R2子格。18设B=1，2，5，10，11，22，55，110。证明：B，GCD，LCM是布尔代数。其中，GCD是求最大公约数，LCM是求最小公倍数，x=110/x。 证 我们已证过N，GCD，LCM，是分配格，故此为证B，GCD

33、，LCM是分配格，只需证B，GCD，LCM是N，GCD，LCM，的子格即可。易于验证，对于任何a，bB，恒有GCDa，b，LCMa，bB故此两个运算GCD，LCM关于B封闭。因而B，GCD，LCM是分配格。又由于1和110互为补元；2和55互为补元；5和22互为补元；10和11互为补元，所以B，GCD，LCM，是有补的分配格，故此B，GCD，LCM，是布尔代数。19设L1=1，2，3，4，6，12，L2=1，2，3，4，6，8，16，24。2412631248 a) L1，GCD，LCM，是布尔代数吗？为什么？b) L2，GCD，LCM，是布尔代数吗？为什么？解 a) L1，GCD，LCM，不

34、是布尔代数。因为L1，GCD，LCM，虽是分配格（N，1，GCD，LCM，的子格）但不是有补格，元素2，6没有补元。所以不是布尔代数。 b) L2，GCD，LCM，也不是布尔代数。因为虽然L2，GCD，LCM，是分配格（N，1，GCD，LCM，的子格），但不是有补格，元素2，4，6，12没有补元。所以也不是布尔代数。20设B，*，Å，是布尔代数。证明下列布尔恒等式。 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)（分配律，结合律，交换律）= (aÅb)* (aÅc) * (bÅc) （由aÅa=1）并且因为b*aÅb，c*aÅc，从而由保序性，得到b*c(aÅb) * (aÅc)又由b*cbÅc及下确界的性质，得到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，根据布尔代数的性质：消去律。 = 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故根据消去律得到B=C，即(aÅb) * (bÅC) * (cÅa)=(a* b)Å(b* c)Å(c* a)21设B，*，Å，是布尔代数，简化下列布

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设B，*，Å，是布尔代数。在B上定义二元运算如下"a，bB，ab=(a*b)(a*b)证明：B，Ä是交换群证 封闭性对于任何a，bB，由于*，Å，运算的封闭性，可知ab=(a*b)Å(a*)B，因此运算具有封闭性。结合律对于任何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)所以运算具有结合律交换律对任何a，bB，ab=(a*b)Å(a*b)=(a*b)Å(a*b) （Å运算交换律）=(b*a)(b*a) （*运算交换律）=ba 所以运算具有结合律有幺元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设B，*，是一个交换群。如下"a，bB，a+b=(a*b)Å(ab)a·b=a*b a) 证明：B，+，·是环 b) 找出关于·的幺元；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，十是交换群。 其次·运算就是运算，故此具有封闭性及结合律，因此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，+，·是环（实际上是含幺交换环） 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)（分配律，结合律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) 根据a) 的证明，分配律已成立。24设A，和B，是两个

52、布尔代数，f是从A，到B，的满同态函数。证明：f(OA)=OB f(1A)=1B其中，OA和OB分别是A，B中的最小元，1A和1B分别是A，B中的最大元。证 对于任何aA，由于A是布尔代数，所以存在着补元A使得OA=a 及1A=a （互补律）又由于B是布尔代数，f是从A到B的同态函数，从而有f()=(f(a) （同态公式）于是f(OA)=f(a)=f(a)f() （同态公式）=f(a)(f(a)=OB （互补律）f(1A)=f(a)=f(a)f() （同态公式）=f(a)(f(a)=1B25设a，b，b2，br是布尔代数B，*，Å，的原子。证明：ab1Åb1Å&#

53、197;br的充分必要条件是存在i（1ir），使a=bi。证 必要性 用反证法。假设对每个i，1ir，都有abi，那么由a，bi（1ir）都是原子，因此a*bi=0（否则有a=a*bi=bi，与假设abi矛盾）。从而 a* (b1Åb2ÅÅbr) =(a*b1)Å(a*b2)ÅÅ(a*br) （分配律） =0Å0ÅÅ0 =0 (0-1律)但是由已知ab1Åb2Å Åbr，从下确界的性质可知 a* (b1Åb2Åbr)=a从而得到a=0，这与已知a是原子，a

54、0矛盾，充分性若对某个i。1i0r，使a=bi0。则由上确界的性质可知ab1Åb2ÅÅ -1ÅaÅ +1ÅÅbr=b1Åb2ÅÅ-1Å +1Åbr（因为a=）26设b1，b2，br是有限布尔代数B，*，Å，的所有原子。证明：y=0的充分必要条件"i（1ir），都有y*bi=0证 必要性对于任何bi（1ir） y*bi=0*bi=0总是成立，因为y=0充分性根据布尔代数的元素的原子表示定理，可知y= 这里S(y)=bi :1irbiy因此，y=y*y （幂等

55、律） =y = （分配律） =0 （因为对任何i，1ir，都有y*bi=0） =0 （0-1律）27设0，1，*，Å，是布尔代数。写出下列布尔表达式的析取范式和合取范式。 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函数，则其运算表为x1x2x3f (x1，x2，x3)00000011010001111000101111011111 根据f (x1，x2，x3)=0的元组可构造出f的合取范式为 (x1Åx2Åx3)* (x1Å Åx3)(x2 Å Åx3)=M3* M5* MT 根据 f (x1，x2，x3)=1的元组可构造出f的析取范式为 (Å Åx3) Å(Å x2Åx3)Å=m1Åm3Åm5Åm6Åm7b) 令g(x1，x2，x3