《离散数学：ch7习题课》由会员分享，可在线阅读，更多相关《离散数学：ch7习题课（11页珍藏版）》请在装配图网上搜索。
1、1 1设设A A=1,2,3,=1,2,3,R R=|x x,y y A A且且x x+2+2y y 6 6，S S=,=,求求:(1)(1)R R的集合表达式的集合表达式(2)(2)R R 1 1(3)(3)domdom R R,ran,ran R R,fldfld R R(4)(4)R R S S,R R3 3(5)(5)r r(R R),),s s(R R),),t t(R R)1计算机科学与工程学院计算机科学与工程学院(1)(1)R R=,=,(2)(2)R R 1 1=,=,(3)(3)domdomR R=1,2,3,=1,2,3,ranranR R=1,2,=1,2,fldfldR
2、 R=1,2,3 =1,2,3(4)(4)R R S S=,=,R R3 3=,=,(5)(5)r r(R R)=,)=,s s(R R)=,)=,t t(R R)=,)=,2计算机科学与工程学院计算机科学与工程学院2 2设设A A=1,2,3,4=1,2,3,4，在，在A A A A上定义二元关系上定义二元关系R R：,R R x+yx+y=u+vu+v，求求R R导出的划分导出的划分.A A=,根据根据 中的中的 x+y=2,3,4,5,6,7,8 将将A划分成等价类：划分成等价类：A/R=,3计算机科学与工程学院计算机科学与工程学院3设设R是是Z上的模上的模 n 等价关系等价关系,即即
3、x y x y(modn),试给出由试给出由R确定的确定的Z的划分的划分.解解 设除以设除以 n 余数为余数为 r 的整数构成等价类的整数构成等价类 r，则，则 r=kn+r|k Z,r=0,1,n 1 =r|r=0,1,n 1 计算机科学与工程学院计算机科学与工程学院4图114 4设偏序集设偏序集 的哈斯图如图所示的哈斯图如图所示.(1)(1)写出写出A A和和R R的集合表达式的集合表达式(2)(2)求该偏序集中的极大元、极小元、最大元、最小元求该偏序集中的极大元、极小元、最大元、最小元解解(1)A=a,b,c,d,e R=,IA(2)极大元和最大元是极大元和最大元是a,极小元极小元是是d
4、,e；没有最小元没有最小元.abcde5计算机科学与工程学院计算机科学与工程学院5 5设设R R是是A A上的二元关系，上的二元关系，设设 S S=|c c(R R R R).).证明如果证明如果R R是等价关系，则是等价关系，则S S也是等价关系。也是等价关系。证证 R是是A上的等价关系上的等价关系.(1)证自反证自反 任取任取x,x A R x(R R)S(2)证对称证对称 任取任取,S c(R R)c(R R)S(3)证传递证传递 任取任取,S S c(R R)d(R R)R R S6计算机科学与工程学院计算机科学与工程学院6设偏序集设偏序集和和，定义，定义A B上二元关系上二元关系T:
5、T xRu ySv 证明证明T为偏序关系为偏序关系.证证 (1)自反性自反性 任取任取,A B x A y B xRx ySy T(2)反对称性反对称性 任取任取,T T xRu ySv uRx vSy (xRu uRx)(ySv vSy)x=u y=v =(3)传递性传递性 任取任取,T T xRu ySv uRw vSt (xRu uRw)(ySv vSt)xRw ySt T 计算机科学与工程学院计算机科学与工程学院71.1.证明证明R R在在A A上自反上自反 任取任取x x,x x A A .R R 前提前提 推理过程推理过程 结论结论2.2.证明证明R R在在A A上对称上对称 任取
6、任取 ，R R .R R 前提前提 推理过程推理过程 结论结论8计算机科学与工程学院计算机科学与工程学院3.3.证明证明R R在在A A上反对称上反对称 任取任取 ，R R R R .x x=y y 前提前提 推理过程推理过程 结论结论4.4.证明证明R R在在A A上传递上传递 任取任取,，R R R R .R R 前提前提 推理过程推理过程 结论结论9计算机科学与工程学院计算机科学与工程学院7R,S为为A上的关系，证明上的关系，证明 R S t(R)t(S)证证 只需证明对于任意正整数只需证明对于任意正整数n,Rn Sn.对对n归纳归纳.n=1,显然为真显然为真.假设对于假设对于n，命题为
7、真，任取，命题为真，任取 Rn+1 Rn R t(Rn R)t(Sn S)Sn S Sn+1 计算机科学与工程学院计算机科学与工程学院10数学归纳法（主要用于幂运算）数学归纳法（主要用于幂运算）证明中用到关系运算的定义和公式证明中用到关系运算的定义和公式,如：如：x x domdomR R y y(R R)y y ranranR R x x(R R)R R R R 1 1 R R S S t t(R R S S)R R A A x x A A R R y y R R A A x x(x x A A R R)r r(R R)=R=R I IA A s s(R R)=R=R R R 1 1 t t(R R)=R=R R R2 2 11计算机科学与工程学院计算机科学与工程学院
离散数学：ch7习题课
