离散数学课后习题答案(第三章)

离散数学课后习题答案(第三章)

ID:3412133

大小:580.00 KB

页数:10页

时间:2017-11-21

离散数学课后习题答案(第三章)_第1页
离散数学课后习题答案(第三章)_第2页
离散数学课后习题答案(第三章)_第3页
离散数学课后习题答案(第三章)_第4页
离散数学课后习题答案(第三章)_第5页
资源描述:

《离散数学课后习题答案(第三章)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、证明:设A上定义的二元关系R为:<<x,y>,<u,v>>∈RÛ=①对任意<x,y>∈A,因为=,所以<<x,y>,<x,y>>∈R即R是自反的。②设<x,y>∈A,<u,v>∈A,若<<x,y>,<u,v>>∈RÞ=Þ=Þ<<u,v>,<x,y>>∈R即R是对称的。③设任意<x,y>∈A,<u,v>∈A,<w,s>∈A,对<<x,y>,<u,v>>∈R∧<<u,v>,<w,s>>∈RÞ(=)∧(=)Þ=Þ<<x,y>,<w,s>>∈R故R是传递的,于是R是A上的等价关系。3-10.6设R是集合A上的对称和传递关系,

2、证明如果对于A中的每一个元素a,在A中同时也存在b,使在R之中,则R是一个等价关系。证明:对任意a∈A,必存在一个b∈A,使得<a,b>∈R.因为R是传递的和对称的,故有:<a,b>∈R∧<b,c>∈RÞ<a,c>∈RÞ<c,a>∈R由<a,c>∈R∧<c,a>∈RÞ<a,a>∈R所以R在A上是自反的,即R是A上的等价关系。3-10.7设R1和R2是非空集合A上的等价关系,试确定下述各式,哪些是A上的等价关系,对不是的式子,提供反例证明。a)(A×A)-R1;b)R1-R2;c)R12;d)r(R1-R2)

3、(即R1-R2的自反闭包)。解a)(A×A)-R1不是A上等价关系。例如:A={a,b},R1={<a,a>,<b,b>}A×A={<a,a>,<a,b>,<b,a>,<b,b>}(A×A)-R1={<a,b>,<b,a>}所以(A×A)-R1不是A上等价关系。b)设A={a,b,c}R1={<a,b>,<b,a>,<b,c>,<c,b>,<a,c>,<c,a>,<a,a>,<b,b>,<c,c>}R2={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}R1-R2={<a,b>,<b,a>,<a,c>,<

4、c,a>}所以R1和R2是A上等价关系,但R1-R2不是A上等价关系。c)若R1是A上等价关系,则<a,a>∈R1Þ<a,a>∈R1○R1所以R12是A上自反的。若<a,b>∈R12则存在c,使得<a,c>∈R1∧<c,b>∈R1。因R1对称,故有<b,c>∈R1∧<c,a>∈R1Þ<b,a>∈R12即R12是对称的。若<a,b>∈R12∧<b,c>∈R12,则有<a,b>∈R1○R1∧<b,c>∈R1○R1Þ($e1)(<a,e1>∈R1∧<e1,b>∈R1)∧($e2)(<b,e2>∈R1∧<e2,c>∈R1)Þ

5、<a,b>∈R1∧<b,c>∈R1(∵R1传递)Þ<a,c>∈R12即R12是传递的。故R12是A上的等价关系。d)如b)所设,R1和R2是A上的等价关系,但r(R1-R2)=(R1-R2)∪IA={<a,b>,<b,a>,<a,c>,<c,a>,<a,a>,<b,b>,<c,c>}不是A上的等价关系。3-10.8设C*是实数部分非零的全体复数组成的集合,C*上的关系R定义为:(a+bi)R(c+di)Ûac>0,证明R是等价关系,并给出关系R的等价类的几何说明。证明:(1)对任意非零实数a,有a2>0Û(a+bi)

6、R(a+bi)故R在C*上是自反的。(2)对任意(a+bi)R(c+di)Ûac>0,因ca=ac>0Û(c+di)R(a+bi),所以R在C*上是对称的。(3)设(a+bi)R(c+di),(c+di)R(u+vi),则有ac>0Ùcu>0若c>0,则a>0Ùu>0Þau>0若c<0,则a<0Ùu<0Þau>0所以(a+bi)R(u+vi),即R在C*上是传递的。关系R的等价类,就是复数平面上第一、四象限上的点,或第二、三象限上的点,因为在这两种情况下,任意两个点(a,b),(c,d),其横坐标乘积ac>0。3-1

7、0.9设Π和Π¢是非空集合A上的划分,并设R和R¢分别为由Π和Π¢诱导的等价关系,那么Π¢细分Π的充要条件是R¢ÍR。证明:若Π¢细分Π。由假设aR¢b,则在Π¢中有某个块S¢,使得a,b∈S¢,因Π¢细分Π,故在Π中,必有某个块S,使S¢ÍS,即a,b∈S,于是有aRb,即R¢ÍR。反之,若R¢ÍR,令S¢为H¢的一个分块,且a∈S¢,则S¢=[a]R¢={x

8、xR¢a}但对每一个x,若xR¢a,因R¢ÍR,故xRa,因此{x

9、xR¢a}Í{x

10、xRa}即[a]R¢Í[a]R设S=[a]R,则S¢ÍS这就证明了Π¢

11、细分Π。3-10.10设Rj是表示I上的模j等价关系,Rk是表示I上的模k等价关系,证明I/Rk细分I/Rj当且仅当k是j的整数倍。证明:由题设Rj={

12、x≡y(modj)}Rk={

13、x≡y(modk)}故∈RjÛx-y=c×j(对某个c∈I)∈RkÛx-y=d×k(对某个d∈I)a)假设I/Rk细分I/

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。