离散数学课后习题答案(左孝.docVIP

证明 设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 上的对称和传递关系，证明如果对于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×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＞，＜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)(ac0,证明R是等价关系，并给出关系R的等价类的几何说明。 证明：(1)对任意非零实数a，有a20((a+bi)R(a+bi) 故R在C*上是自反的。 (2) 对任意(a+bi)R(c+di)(ac0, 因ca=ac0((c+di)R(a+bi), 所以R在C*上是对称的。 (3)设(a+bi)R(c+di) ，(c+di)R(u+vi)，则有ac0(cu0 若c0，则a0(u0( au0 若c0，则a0(u0( au0 所以(a+bi)R(u+vi)，即R在C*上是传递的。 关系R的等价类，就是复数平面上第一、四象限上的点，或第二、三象限上的点，因为在这两种情况下，任意两个点(a,b)，(c,d)，其横坐标乘积ac0。 3-10.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|xR(a} 但对每一个x，若xR(a，因R( ( R，故xRa，因此{x|xR(a} ({x|xRa}即[a]R( ([a]R 设S=[a]R,则S(( S 这就证明了Π(细分Π