发布时间 : 星期一 文章离散数学习题答案（耿素云屈婉玲）更新完毕开始阅读
⑦ ⑧ ⑨ ⑩
G(c)?H(c) ③⑥合取引入 ?x(G(x)?H(x)?I(x)) 前提引入 G(c)?H(c)?I(c) ⑧UI规则 I(c) ⑦⑨假言推理
习题七及答案：（P132-135） 22、给定
A??1,2,3,4?，A上的关系R??1,3,1,4,2,3,2,4,3,4?，试
（1）画出R的关系图； （2）说明R的性质。 解：（1）
● ●
1 ● ● 2 3 4 （2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；
R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；
R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是
传递的。 26 设
A??1,2,3,4,5,6?，R为A上的关系，R的关系图如图7.13所示：
2（1）求R,R3的集合表达式；
??1,5,2,5,3,1,3,3,4,5（2）求r(R), s(R), t(R)的集合表达式。 解：（1）由R的关系图可得R所以R可得R2?
?，
?R?R??3,1,3,3,3,5?，R3?R2?R??3,1,3,3,3,5n??3,1,3,3,3,5?,当n>=2；
??1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6（2）r(R)=R?IA?，
s(R)?R?R?1??1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4?
t(R)?R?R2?R3?...?R?R2??1,5,2,5,3,1,3,3,4,5,3,546、分别画出下列各偏序集（1）R??
A,R?的哈斯图，并找出A的极大元、极小元、最大元和最小元。
??a,d,a,c,a,b,a,e,b,e,c,e,d,e??IA
解：哈斯图如下：
e b c d a
A的极大元为e、极小元为a； A的最大元为e、最小元为a。 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，则：?R为偏序关系，具有自反性，?a1Ra1?S为偏序关系，具有自反性，?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???ax?x??a?1?x?0???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?0b??y???a??当a?0时，a,b的逆元不存在；当a?0时，a,b的逆元是11
1b,?aa、
设S??1，2，...,10?，问下面的运算能否与S构成代数系统S，??如果能构成代数系统则说明?运算是否满足交换律、结合律，并求?运算的单位元和零元。