发布时间 : 星期四 文章离散数学课后习题答案（左孝凌版）更新完毕开始阅读
3-10.1 设R和R′是集合A上的等价关系，用例子说明：R∪R′不一定是等价关系。 证明 设 A={1，2，3}，S=R∪R′ R={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞} R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，2＞，＜2，3＞} 则R∪R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞，＜3，2＞，＜2，3＞} 因为如＜2，3＞∈S∧＜3，1＞∈S，但＜2，1＞?S，故R∪R′不是传递的，即R∪R′不是A上的等价关系。 3-10.2 试问由4个元素组成的有限集上所有等价关系的个数为多少？ 解 因为集合X上的等价关系与X的划分是一一对应的，所以4个元素的有限集上等价关系证明 设A上定义的二元关系R为：
xu
＜＜x,y＞, ＜u,v＞＞∈R? =
yvxx
① 对任意＜x,y＞∈A，因为 = ，所以
yy＜＜x,y＞, ＜x,y＞＞∈R 即R是自反的。
的数目，与4个元素集合进行划分的数目是相同的，由习题3-9.1可知共有15个不同的等价关系。 3-10.3 给定集合S={1，2，3，4，5}，找出S上的等价关系R，此关系R能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解 我们可用如下方法产生一个等价关系： R1={1，2}×{1，2}={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞} R2={3}×{3}={＜3，3＞} R3={4，5}×{4，5}={＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞} R= R1∪R2∪R3={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞，＜3，3＞，＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞} 关系图如图。 3-10.4 设R是一个二元关系，S={＜a，b＞∣对于某一c，有＜a，c＞∈R∧＜c，b＞∈R}，证明若R是一个等价关系，则S也是一个等价关系。 证明 设R是A上的等价关系： （1） 对任一x∈A，因为R在A上自反，所以＜x，x＞∈R。由S定义，＜x，x＞∈S，所以S是自反的。 （2） 对任意x,y∈A，若＜x，y＞∈S，则存在某个c，使得＜x，c＞∈R∧＜c，y＞∈R，因为R是对称，故有：＜y，c＞∈R∧＜c，x＞∈R，由S的定义，可知＜y，x＞∈S，所以S是对称的。 （3） 对任意x,y,z∈A，若＜x，y＞∈S，及＜y，z＞∈S，则必存在某个c1，使＜x，c1＞∈R，＜c1，y＞∈R。由R的传递性，可知＜x，y＞∈R，同理存在c2，使＜y，c2＞∈R∧＜c2，z＞∈R，由R传递，可知＜y，z＞∈R。再由S定义，得＜x，z＞∈S。故S是传递的。 3-10.5 设正整数的序偶集合A，在A上定义二元关系R如下：＜＜x,y＞, ＜u,v＞＞∈R，当且仅当xv=yu，证明R是一个等价关系。
② 设＜x,y＞∈A，＜u,v＞∈A，若
＜＜x,y＞, ＜u,v＞＞∈R?xy =uv ?uv =x
y ?＜＜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 ?（xuy =v ）∧（uwxwv =s ）?y =s ?＜＜x,y＞, ＜w,s＞＞∈R
故R是传递的，于是R是A上的等价关系。
3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使
＜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）R2
1；
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
所以R2
1是A上自反的。
若＜a,b＞∈R2
1则存在c，使得＜a, c＞∈R1∧＜c,b＞∈R1。因R1对称，故有 ＜b, c＞∈R2
1∧＜c,a＞∈R1?＜b, a＞∈R1 即R2
1是对称的。
若＜a,b＞∈R2
1∧＜b, c＞∈R2
1,则有 ＜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＞∈R21 即R2
1是传递的。 故R21是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>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-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 这就证明了Π?细分Π。
3-10.10 设Rj是表示I上的模j等价关系，Rk是表示I上的模k等价关系，证明I/Rk细分I/Rj当且仅当k是j的整数倍。
证明：由题设Rj={
Rk={
故
a)假设I/Rk细分I/Rj，则Rk ? Rj 因此
b)若对于某个r∈I，有k=rj则：
因此，Rk ? Rj，于是I/Rk细分I/Rj
5-1代数系统的引入 5.1.1设集合A={1，2，3，?，10}，问下面定义的二元运算*关于集合A是否封闭？ a） x*y=max(x,y); b） x*y=min(x,y); c） x*y=GCD(x,y);（最大公约数） d） x*y=LCM(x,y);（最小公倍数） e） x*y=质数p的个数，其中x?p?y。 解：a）封闭。b）封闭。c）封闭。d）不封闭。e）不封闭。 5.1.2在下表所列出的集合和运算中，请根据运算是否在相应集合上封闭，在相应位置上填写“是”或“否”，其中I表示整数集，N表示自然数集合。 是否封闭 集合 I N {x∣0?x?10} {x∣-10?x?10} {2x∣x?I} 解： 是否封闭 集合 I N {x∣0?x?10} {x∣-10?x?10} {2x∣x?I} 5-2运算及其性质 5.2.1对于实数集合R，下表所列的二元运算是否具有左边一列中那些性质，请在相应位置上填写“是”或“否”。 结合律 交换律 有单位元 有零元 解： 结合律 交换律 有单位元 有零元 + 是 是 是 否 - 否 否 否 否 × 是 是 是 是 max min 是 是 否 否 是 是 否 否 ∣x-y∣ 否 是 否 否 + - × max min ∣x-y∣ + 是 是 否 否 是 - 是 否 否 否 是 是 是 是 否 是 + - 运算 ∣x-y∣ max 是 是 是 是 是 min 是 是 是 是 是 ∣x∣ 是 是 是 是 是 运算 ∣x-y∣ max min ∣x∣