《离散数学习题解答(第五章)格与布尔代数》由会员分享，可在线阅读，更多相关《离散数学习题解答(第五章)格与布尔代数（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) (c*a) （分配律）=(bc) * (ba) * (ac) （分配律，吸收律）=(ab) *
