内容发布更新时间 : 2024/12/23 2:09:11星期一 下面是文章的全部内容请认真阅读。

离散数学习题答案

48、设

A,R和B,S为偏序集,在集合A?B上定义关系T如下:

?a1,b1,a2,b2?A?B,a1,b1Ta2,b2?a1Ra2?b1Sb2证明T为A?B上的偏序关系。 证明:(1)自反性:

任取a1,b1?A?B，则：QR为偏序关系，具有自反性，?a1Ra1QS为偏序关系，具有自反性，?b1Sb1?a1Ra1?b1Sb1又a1,b1Ta2,b2?a1Ra2?b1Sb2，?a1,b1Ta1,b1，故T满足自反性(2)反对称性:

任取a1,b1,a2,b2?A?B，若a1,b1Ta2,b2且a2,b2Ta1,b1，则有：a1Ra2?b1Sb2a2Ra1?b2Sb1（1）（2）

?a1Ra2?a2Ra1，又R为偏序关系，具有反对称性，所以a1?a2?b1Sb2?b2Sb1，又S为偏序关系，具有反对称性，所以b1?b2?a1,b1?a2,b2，故T满足反对称性(3)传递性:

任取a1,b1,a2,b2，a3,b3?A?B，若a1,b1Ta2,b2且a2,b2Ta3,b3，则有：a1,b1Ta2,b2?a1Ra2?b1Sb2a2,b2Ta3,b3?a2Ra3?b2Sb3?a1Ra2?a2Ra3,又R为偏序关系，具有传递性，所以a1Ra3?b1Sb2?b2Sb3,又S为偏序关系，具有传递性，所以b1Sb3?a1Ra3?b1Sb3?a1,b1Ta3,b3，故T满足传递性。综合(1)(2)(3)知T满足自反性、反对称性与传递性,故T为A?B上的偏序关系。 习题九及答案:(P179-180) 8、

S=Q?Q,Q为有理数集，为?S上的二元运算，?a,b,x,y?S有a,b?x,y?ax,ay+b(1)?运算在S上是否可交换、可结合？是否为幂等的？

(2)?运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元。

离散数学习题答案

解:(1)

x,y?a,b?xa,xb+y?ax,bx+y?a,b?x,y??运算不具有交换律

?x,y?a,b??c,d?ax,bx+y?c,d?acx,adx+bx+y而x,y??a,b?c,d?x,y*ac,ad+b?xac,xad+xb+y?acx,adx+bx+y??x,y?a,b??c,d??运算有结合律?

任取a,b?s，则有：a,b?a,b?a2,ad?b?a,b??运算无幂等律(2)

令a,b*x,y?a,b对?a,b?s均成立则有：ax,ay+b?a,b对?a,b?s均成立??a?x?1??0?ax?a????对??a,b?成立ay?b?bay?0???

?x?1?0?x?1?必定有????y?0?y?0??运算的右单位元为1，0，可验证1，0也为?运算的左单位元，??运算的单位元为1，0令a,b*x,y?x,y，若存在x,y使得对?a,b?s上述等式均成立，则存在零元，否则不存在零元。由a,b*x,y?x,y?ax,ay+b?x,y???a?1?x?0?ax?x????ay?b?y??a?1?y+b?0???由于?a?1?y+b?0不可能对?a,b?s均成立，故a,b*x,y?x,y不可能对?a,b?s均成立，故不存在零元；

离散数学习题答案

设元素a,b的逆元为x,y，则令a,b*x,y?e?1，01?x???ax?1?a????（当a?0）?ay?b?0?y??b?a??当a?0时，a,b的逆元不存在；当a?0时，a,b的逆元是11

1b,?aa、

设S??1，2，...,10?，问下面的运算能否与S构成代数系统S，??如果能构成代数系统则说明?运算是否满足交换律、结合律，并求?运算的单位元和零元。(3)x?y=大于等于x和y的最小整数; 解:(3)由*运算的定义可知:x?y=max(x,y),

x,y?S,有x?y?S，故?运算在S上满足封闭性，所以?运算与非空集合S能构成代数系统； 任取x,y?S,有x?y=max(x,y)=max(y,x)=y?x,所以?运算满足交换律；

任取x,y,z?S,有(x?y)?z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x?(y?z),所以?运算满足结合律；任取x?S，有x?1=max(x,1)=x=max(1,x)=1?x,所以?运算的单位元是1； 任取x?S，有x?10=max(x,10)=10=max(10,x)=10?x,所以?运算的零元是10；

16、

设V1??1,2,3?,?,1,其中x?y表示取x和y之中较大的数。V2??5,6?,?,6，其中x?y表示取x和y之中较小的数。求出V1和V2的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。解：（1）V1的所有的子代数是：?1,2,3?,?,1,?1?,?,1,?1,2?,?,1,?1,3?,?,1；V1的平凡的子代数是：?1,2,3?,?,1,?1?,?,1；V1的真子代数是：?1?,?,1,?1,2?,?,1,?1,3?,?,1；（2）V2的所有的子代数是：?5,6?,?,6，?6?,?,6；V2的平凡的子代数是： ?5,6?,?,6，?6?,?,6；V2的真子代数是：?6?,?,6。习题十一及答案:(P218-219)

离散数学习题答案

1、图11、11给出了6个偏序集的哈斯图。判断其中哪些就是格。如果不就是格,说明理由 解:(a)、(c)、(f)就是格;因为任意两个元素构成的集合都有最小上界与最大下界; (b)不就是格,因为{d,e}的最大下界不存在; (d)不就是格,因为{b,c}的最小上界不存在; (e)不就是格,因为{a,b}的最大下界不存在。

2、下列各集合低于整除关系都构成偏序集,判断哪些偏序集就是格。 (1)L={1,2,3,4,5}; (2)L={1,2,3,6,12};

解:画出哈斯图即可判断出:(1)不就是格,(2)就是格。 4、设L就是格,求以下公式的对偶式: (2)a?(b?c)?(a?b)?(a?c)

解:对偶式为:a?(b?c)?(a?b)?(a?c),参见P208页定义11、2。 9、针对图11、11中的每个格,如果格中的元素存在补元,则求出这些补元。 解:

(a)图:a,d互为补元,其中a为全下界,d为全上界,b与c都没有补元;

(c)图:a,f互为补元,其中a为全下界,f为全上界,c与d的补元都就是b与e,b与e的补元都就是c与d; (f)图:a,f互为补元,其中a为全下界,f为全上界,b与e互为补元,c与d都没有补元。 10、说明图11、11中每个格就是否为分配格、有补格与布尔格,并说明理由。 解:

(a)图:就是一条链,所以就是分配格,b与c都没有补元,所以不就是有补格,所以不就是布尔格;

(c)图:a,f互为补元,c与d的补元都就是b与e,b与e的补元都就是c与d,所以任何元素皆有补元,就是有补格;Qc?(b?d)?c?a?c, (c?b)?(c?d)?f?d?d?c?(b?d)?(c?b)?(c?d),所以?对?运

算不满足分配律,所以不就是分配格,所以不就是布尔格;

(f)图:经过分析知图(f)对应的格只有2个五元子格:L1={a,c,d,e,f}, L2={a,b,c,d,f}。画出L1与L2的哈斯图可知L1与L2均不同构于钻石格与五角格,根据分配格的充分必要条件(见P213页的定理11、5)得图(f)对应的格就是分配格;c与d都没有补元,所以不就是有补格,所以不就是布尔格。