离散数学课后习题答案第三章Word文件下载.docx
《离散数学课后习题答案第三章Word文件下载.docx》由会员分享，可在线阅读，更多相关《离散数学课后习题答案第三章Word文件下载.docx（95页珍藏版）》请在冰点文库上搜索。
3设任意＜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上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使<
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）（即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×
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＞，＜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）
⇒＜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）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>
若c>
0，则a>
0∧u>
0⇒au>
若c<
0，则a<
0∧u<
所以（a+bi）R（u+vi），即R在C*上是传递的。
关系R的等价类，就是复数平面上第一、四象限上的点，或第二、三象限上的点，因为在这两种情况下，任意两个点（a,b），（c,d），其横坐标乘积ac>
0。
3-10.9设Π和Π'
是非空集合A上的划分，并设R和R'
分别为由Π和Π'
诱导的等价关系，那么Π'
细分Π的充要条件是R'
⊆R。
若Π'
细分Π。
由假设aR'
b，则在Π'
中有某个块S'
，使得a,b∈S'
，因Π'
细分Π，故在Π中，必有某个块S，使S'
⊆S，即a,b∈S，于是有aRb,即R'
反之，若R'
⊆R，令S'
为H'
的一个分块，且a∈S'
，则S'
=[a]R'
={x|xR'
a}
但对每一个x，若xR'
a，因R'
⊆R，故xRa，因此{x|xR'
a}⊆{x|xRa}即[a]R'
⊆[a]R
设S=[a]R,则S'
⊆S
这就证明了Π'
3-10.10设Rj是表示I上的模j等价关系，Rk是表示I上的模k等价关系，证明I/Rk细分I/Rj当且仅当k是j的整数倍。
由题设Rj={<
x,y>
|x≡y（modj）}
Rk={<
|x≡y（modk）}
故<
∈Rj⇔x-y=c⋅j（对某个c∈I）
<
∈Rk⇔x-y=d⋅k（对某个d∈I）
a）假设I/Rk细分I/Rj，则Rk⊆Rj
因此<
k,0>
∈Rk⇒<
∈Rj
故k-0=1⋅k=c⋅j（对某个c∈I）
于是k是j的整数倍。
b）若对于某个r∈I，有k=rj则：
∈Rk⇔x-y=ck（对某个c∈I）
⇒x-y=crj（对某个c,r∈I）
⇒<
因此，Rk⊆Rj，于是I/Rk细分I/Rj
fjasasdhgaowirghaoghaa;
owghfjasasdhgaowirghaoghaa;
owgfjasasdhgaowirghaoghaa;
升级会员 