离散数学习题解答(第五章)格与布尔代数.doc

《离散数学习题解答(第五章)格与布尔代数.doc》由会员分享，可在线阅读，更多相关《离散数学习题解答(第五章)格与布尔代数.doc（24页珍藏版）》请在沃文网上搜索。

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中存在着两个元素没有上确界。 例如：812=LUB8，12不存在。8631241210c) L，不是格。因为L中存在着两个元素没有上确界。842698731510 倒例如：46=LUB4，6不存在。2设A，B是两个集合，f是从A到B的映射。证明：S，是2B，的子格。其中

2、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(B2)=x|xAf (x)

3、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)于是从A1A22A可知

4、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=xy为下确界L存在。我们只需证明z1，z2B即可，证明方法有二，方法一为：由于ax，所以ax=x，于是z1=xy =(ax) y （利用ax=x） =a (xy) （由运算结合律） 因此az1；另一方面，由yb可知yb=b，由xb可知xb=b，于是z1b=(xy) b=x(yb) （由运算结合律）=xb （利用yb=b）=b

5、（利用xb=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 （利用*运算结合律）=z2*b从而z2b，即az2b 所以z2B 因此B，是格（是格L，的子格）。方法二：根据上、下确界性质，由ax，ay，可得ax*y，（见附页数）4设L，*，是格。a，bL，证明：（附页）axy，即az2，a又由xb，yb，可得xyb，x*yyb，即z1b，z2b所以

6、az1b，az2b，故此z1，z2Ba*ba且a*bba与b是不可比较的。证 先证用反证法，假设a与b是可比较的，于是有ab或者ba。当ab时，a*b=a与a*ba（得a*ba）矛盾；当ba时，a*b=b与a*bb（得a*bb）矛盾；因此假设错误，a与b是不可比较的。次证由于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)(ab) *

7、(bc) * (ca)证 a) 方法一，根据上、下确界的性质，由a*baac及a*bbbd 所以得到a*b(ac) * (bd)又由 c*dcac及c*ddbd，所以得到c*d(ac) * (bd)因此(a*b) (c*d) (ac) * (bd)方法二 (a*b) (c*d) (ac) * (ad) * (ac) * (bd) （分配不等式，交换律，结合律，保序性） (ac) * (bd) （保序性） b) 方法一，根据上、下确界的性质由a*baab，a*bbbc，a*baca可得 a*b(ab) * (bc) * (ca)同理可得 b*c(ab) * (bc) * (ca)及 c*a(ab

8、) * (bc) * (ca)所以 (ab) (bc) (ca)(ab) * (bc) * (ca) 方法二：(ab) (bc) (ca) b* (ac) (c*a) （交换律，结合律，分配不等式，保序性） b (c*a) * (ac) (c*a)（分配不等式，交换律，） (ab) * (bc) * (ac)（分配不等式，结合律，交换律，吸收律，保序性） (ab) * (bc) * (ca) （结合律）6设I是整数集合。证明：I，min，max是分配格。证 由于整数集合I是全序集，所以任何两个整数的最小者和最大者是存在的，因此I，min，max是格是格是显然的。下面我们来证I，min，max满

9、足分配律对于任何a，b，cI 有a* (bc)=mina，maxb，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

10、，b，mina，c=mina，a=a（b）cab，则 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* (bc)=(ab) * (a c)根据对偶原理，就还有 a (b*c)=(ab) * (ac)因此I，min，max是分配格。7设A，*，max是分配格，a，bA且ab。证明： f (x)=(xa) *b是从A到B的同态函数。其它 B=x|xA且axb证 由于axa，及已知ab，所以a(xa)*b；其次(

11、xa)*bb，所以af (x) b，因而f (x)是从A到B的函数。对于任何x，yA，f(xy)=(xy)a)*b =(xa) (ya) *b（幂等律，交换律，结合律） =(x*a)b)(ya) *b)（分配律） =f (x) f (y)f (x*y) =(x*y) a) *b =(xa) * (ya)*b （分配律） =(xa) *b)(ya) *b) （幂等律，交换律，结合律） =f (x) *f (y)所以，f满足同态公式，因而f 是从A到B的同态函数。8证明：一个格是分配格的充分必要条件是a，b，cL，有(a*b) (b*c) (c*a)=(ab) * (bc) * (ca)证 必要性

12、。对于任何a，b，cL，(a*b) (b*c) (c*a)=(b* (ac) (c*a) （交换律，分配律）=(b (c*a) * (ac) (c*a) （分配律）=(bc) * (ba) * (ac) （分配律，吸收律）=(ab) * (bc) * (ca) （交换律）充分性，f满足同态公式，因而f是从A到B的同态函数。8证明：一个格是分配格的充分必要条件是a，b，cL，有(a*b) (b*c) (c*a)=(ab) * (bc) * (ca)证 必要性。对于任何a，b，cL，(a*b) (b*c) (c*a)=(b* (ac) (c*a) （交换，分配律）=(b (c*a)( a c) (

13、c*a) （分配律）=(bc) * (ba) * (ac) （分配律，吸收律）=(ab) * (bc) * (ca) （交换律）充分性，对于任何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 （交换律，结合律）=(ab) * (bc) * (ca) a （已知条件）=(ab) * (ac) * (bc) (bc) *a) a （交换律，吸收律）=(ab) * (ac) * (bc) (bc) *a) (a* (a b) * (a c) （吸收律）=(ab) * (ac) (bc

14、) * (bc) a) * (a (a b) * (ac) （已知条件）=(ab) * (ac) (bc) * (abc) *(a b)* (ac)（因为a (ab) * (ac)= (ab) * (ac)=(ab) * (ac) (bc) * (ab)c) *(a b)* (ac) （结合律）=(ab) * (ac) (bc) *(a b)* (ac) （吸收律，结合律）cehabdfig=(a b)* (ac) （吸收律）根据对偶原理 还有a* (bc)= (ab) * (ac)所以格L是分配格。9设L，是格。其Hasse图如右 a) 找出格中每个元素的补元；b) 此格是有补格吗？c) 此

15、格是分配格吗？解 a)最小元0=i；最大元1=a；故此格为有界格。a和i互为补元；f和C互为补元；其余b，d，e，g，h等都没有补元。b) 根据a) 可知，此格不是有补格。c) 此格不是分配格，因为f (g* h)=f i=f (fg) * (fh)=b* d=d 因为去掉g结点后所形成的子格与分配格S24，I，GCD，LCM，1，24同构，因此若此格不是分配格，则必有子格h * (fg)=h*b=ha1a3a2a4a52484213612b1b4b5b3b2(h*f) (h*g)=ii=IS24，I，GCD，LCM，1，24 两个不是分配格的特殊格与两个不是分配格的特殊格同构，并且此子格必含

16、有g点。而特殊不分配格之图或是含有五个结点的圈，或是有六个结点：gebdfi；gebdhi；gehdfi；或是有八个结：gecabdfi；gecabdhi；或是只有一个四结点的圈：gehi。因此此格绝不会有含g点的子格与两个不是分配格的特殊格同构。10设L，*，是有界格。x，yL，证明： a) 若xy=0，则x=0且y=0。b) 若x*y=1，则x=1且y=1。证 a) 对任何x，yL，若xy=0，则x=x* (xy) （吸收律） =x*0 （xy=0）=0 （01律）y=y* (yx) （吸收律） =y* (xy) （交换律） =y*0 （xy=0） =0 （01律）b) 对任何x，yL，若

17、x*y=1，则 x=x (x*y) （吸收律） =x1 （x*y=1） =1 （01律）y=y (y*x) （吸收律） =y (x*y) （交换律） =y1 （x*y=1） =1 （01律）11在有界格中，0是1的唯一补元，1是0的唯一补元。证 由于10=1，1*0=0，所以0与1互为补元。下面我们先来证0是1的唯一补元：对于任何元素a属于有界格，若a是1的补元，则必有1a=1，及1*a=0，于是必有a=a* (a1) （吸收律） =a* (1a) （交换律） =a*1 （由1a=1） =1*a （交换律） =0 （由1*a=0）从而0是1的唯一补元。次证1是0的唯一补元。对于任何元素a属于有

18、界格，若a是0的补元，则必有0a=1，0*a=0。于是必有 a=a(a*0) （吸收律） =a(0a) （交换律） =a0 （由0*a=0） =0a （交换律） =1 （由0a=1）12设L，是格，|L|2。证明：L中不存在以自己为补元的元素。证 用反证法，假设L中存在着以自己为补元的元素，不妨是bL，那么bb=1，b*b=0，于是由幂等律，可得b=b*b=0，bb=1，从而有0=b=1，即0=1因此，对于任何元素aL，都有a=0=1（因为0a1），从而|L|=1，这与已知|L，|2矛盾。13设L，是全序集，|L|3。证明：L，是格，但不是有补格。证 由于L，是全序集，那么L中任意两个元素都可

19、比较，于是L中任意两个元素都有上确界和下确界，因此L，是格。下面我们来证L，不是有补格，用反证法：否则L，是有补格，则对任何aL，都存在着一个元素bL，使ab=1及a*b=0。由于L，是全序集，所以任二元素可比较，从而若ab，则a=a*b=0若ba，则a=ab=1因此|L|=2，与已知|L|3矛盾。14在有界的分配格中，证明：具有补元的那些元素组成一个子格。证 设L，*，0，1是有界分配格，令 L=x|xL($yL)(x*y=0xy=1)我们来证L，*，0，1是L，*，0，1的子格： 显然LL；其次易证0，1L，故此L非空；对于任何a1，a2L，我们来证a1*a2，a1a2L为证a1*a2L，

20、只需找出a1*a2的补元即可。由于a1，a2L，故此存在着b1，b2L，使a1*b1=0，a1b1=1以及a2*b2=0，a2b2=1，于是构造出a1*a2补元为b1b2L。这是因为(a1*a2) * (b1b2)=(a1*a2) * b1) (a1*a2) * b2) （分配律） =(a1*b1) *a2) (a1*(a2 * b2) （交换律） =(0*a2) (a1*0)（由a1*b1=0，a2b2=0） =00 （由01律） =0(a1*a2) (b1b2)=(a1 (b1 b2) * (a2 (b1 b2)（分配律） =(a1b2) b2) * (a2b2) b1)（交换律，结合律）

21、 =(1b2)* (1b1)（由a1b1=1及a2b2=1） =1*1（由01律） =1为证a1a2L只需找出a1a2的补元即可。由于a1，a2的补元是b1，b2，故构造出a1a2的补元为b1*b2L。这是因为 (a1a2) * (b1*b2)=(a1* (b1* b2) (a2* (b1* b2)（分配律） =(a1*b2) *b2) (a2*b2) *b1)（交换律，结合律） =(0*b2) (0*b1)（由a1*b1=0及a2*b2=0） =00（由01律） =0 (a1a2) (b1*b2)=(a1a2) b1) * (a1a2) b2)（分配律）= (a1b1) a2) * (a1

22、(a2b2)（交换律，结合律）=(1a2) * (a11)（由a1b1=1及a2b2=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的图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，

23、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，有(ab) *ca (b*c)证 必要性对任何a，b，cL (ab) *c=(a*c) (b*c) （分配律） a (b*c) （由a*ca，及保序性）充分性一方面，由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

24、) *b)（交换律）a (a (c*b)（已知条件(ac)*ba (c* b)及保序性）=(aa) (b*c)（结合律，交换律）=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非空，则

25、有aL1，从而有b=f (a)f (L1)故f (L1)非空。对于任何b1，b2f (L1)，存在着a1，a2L1，使b1=f (a1)，b2=f (a2)，从而 b1 2b2=f (a1) 2f (a2)110102221555=f (a11a2)（同态公式）f (L1)（因L1，R1是格，故1运算封闭，从而a11a2L1）因此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，LCM是分配

26、格，只需证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，不是布尔代数。因

27、为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)=abb) a* (ab)=a*bc) (a*c) (a*b) (b*c)=(a*c) (a*b)d) (a b) * (b c) * (c a)=(a b) * (b c) * (c a)e) (a b) * (b c) *

28、(c a)=(a*b) (b*c) (c*a)证 a) a (a*b)=(aa) * (ab)（分配律）=1* (ab) （由aa=1）=ab （01律） b) a (ab)=(a*a) (a*b)（分配律）=1 (a*b) （由a*a=0）= a*b （01律） c)由于(a*c) (a*b) =(aa) * (ab)* (a*c) * (b*c)（分配律，结合律，交换律）= (ab)* (ac) * (bc) （由aa=1）并且因为b*ab，c*ac，从而由保序性，得到b*c(ab) * (ac)又由b*cbc及下确界的性质，得到b*c(ab) * (ac) * (bc)所以b*c(a*c

29、) (a*b)所以(a*c) (a*b) (b*c)= (a*c) (a*b) d) 令B=(ab) * (bc) * (ca)，C=(ab) * (bc) * (ca) 于是为证B=C，根据布尔代数的性质：消去律。 = a*b*c （交换律）所以 a*B=a*c从而由消去律，有B=C 即 (ab) * (bc) * (ca)=(ab) * (bc) * (ca) e) 令B=(ab) * (bc) * (ca) C=(a* b)(b* c)(c* a) 由于a* B=a* (ab) * (bc) * (ca) =a* (bc) * (ca) （吸收律） =a* (ac) * (bc) （交换

30、律） =a* (bc)（吸收律） 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)(a* c) （分配律）所以 a* B=a* C又由于 a* B=a* (ab) * (bC) * (ca) = a* b* (bc) * (ca) （反身性，及本题b） = a* b*(ca) （吸收律） = a* b* c （交换律，反身律，本题b） a*C= a(a* b)(b* c)(c* a)=(a* a* b)(a* b* c)(a* a* c)（

31、分配律，交换律）=(0* b)(a* b* c)(0* c) （由a* a=0）=0(a* b* c)0 （11律）=a* b* c只需证a* B=a* C和a* B=a* C 即可由于 a* B=a* (ab) * (bc) * (ca)= a* (bc) * (ca) （吸收律）= a*(a c) * (bc) （交换律）=a* c* (cb) （本题b）及交换律）=a* c* b （本题b）=a* b* c （交换律）a* C=a* (ab) * (bC) * (ca)=a* b* (bC) * (ca) （本题b）=a* b* c* (ca) （本题b）=a* b* c* a （本题b

32、）=a* a* b* c （交换律）=a* b* c （幂等律）所以 a* B=a* C又由于 a* B=a* (ab) * (bc) * (ca)=a* (a) b) * (bc) * (ca) （反身性）=a* b* (b)c) * (ca) （本题b）及反身性）=a* b* c* (c)a) （本题b）及反身性）=a* b* c* a （本题b）=a* a* b* c （交换律）=a* b* c （幂等性）a*C= a* (ab) * (bc) * (ca)= a* (bc) * (ca) （吸收律）= a* (a) c) * (bc) （交换律及反身性）= a* c* (c)b) （本

33、题b）及反身性交换律）= a* c* b （本题b）所以 a* B=a* C故根据消去律得到B=C，即(ab) * (bC) * (ca)=(a* b)(b* c)(c* a)21设B，*，是布尔代数，简化下列布尔表达式。 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) * (ab) * c解 a) (a* b)(a* b* c)(b* c)= (a* b) (b* c) （因为吸收律）=b* (ac) （分配律） b) (a* b)(a* b* c)(b* c)=(a*

34、b)(a* b)b)* 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 *( aa)* (ac)(b* c) （分配律） =(b* (a c)(b* c) （互补aa=1） =b* (acc) （分配律） =b （互补cc=1）d) (a* b)c) * (ab) * C =(a* b)c) * c* (ab) （交换律） =c* (ab) （吸收律）22设B，*，是布尔代数。在B上定义二元运算如下a，bB，ab=

35、(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)(a*b)*c) =(a*b*c)(a*b*c)(ab) * (ab) *c) （分配律，deMorgan律，反身律） =(a*b*c)(a*b*c)(a*b) (ab) *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*