3-8.1 根据图3-8.1中的有向图，写出邻接矩阵和关系R，并求出R的自反闭包和对称闭包。 解 a M1 1 0 R= 0 0 1 b c 0 1 0 图3-8.1 R={＜a，a＞，＜a，b＞，＜b，c＞，＜c，b＞＝ r（R）= R∪IX ={＜a，a＞，＜b，b＞，＜c，c＞，＜a，b＞，＜b，c＞，＜c，b＞＝ s（R）= R∪RC={＜a，a＞，＜a，b＞，＜b，a＞，＜b，c＞，＜c，b＞} 3-8.2 设集合A={a，b，c，d}A上的关系 R={＜a，b＞，＜b，a＞，＜b，c＞，＜c，d＞} a） 用矩阵运算和作图方法求出R的自反、对称、传递闭包； b） 用Warshall算法，求出R的传递闭包。 解 a） 0 1 0 0 MR= 1 0 1 0 0 0 0 1 0 0 0 0 R的关系图如图所示。 a b d c M0 1 0 0 1 0 0 0 1 1 0 0 R+MIA= 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 + 0 0 1 0 = 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 r（R）= R∪IA ={＜a，a＞，＜a，b＞，＜b，a＞，＜b，b＞，＜b，c＞，＜c，c＞，＜c，d＞，＜d，d＞}（图（a）） a b d c 图（a） 0 1 0 0 0 1 0 0 0 1 0 0 MR+MRc= 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 + 0 1 0 0 = 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 dintin@gmail.com 31
3-9.1 4个元素的集合共有多少不同的划分。 解 整数4可划分为：4，1+3，1+1+2，2+2，1+1+1+1。 1+C12124+C4+2 C4+1=15（种） 3-9.2 设{A1，A2，…，Ak}是集合A的一个划分，我们定义A上的一个二元关系R，使＜a,b＞∈R当且仅当a和b在这个划分的同一块中。证明R是自反的，对称的，和传递的。 证明 设对任意a∈A，则必存在Ai，使a∈Ai，因a与a必可看作在同一块中，故有＜a,a＞∈R。即R是自反的。 设a,b∈A，若有＜a,b＞∈R，则a与b必在同一块，故b与a亦在同一块，＜b, a＞∈R，即R是对称的。 对任意a,b,c∈A， ＜a,b＞∈R∧＜b,c＞∈R ?（?i）（a∈Ai∧b∈Ai）∧（?j）（b∈Aj∧c∈Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧b∈Ai∩Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧Ai∩Aj≠?） ?（?i）（?j）（a∈Ai∧c∈Aj∧i=j）（∵i≠j?Ai∩Aj= ?） ?a,c在同一块 ?＜a,c＞∈R ∴R传递 dintin@gmail.com 32
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个元素的有限集上等价关系的数目，与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是一个等价关系。
证明 设A上定义的二元关系R为：
＜＜x,y＞, ＜u,v＞＞∈R?xu
y =v
① 对任意＜x,y＞∈A，因为xx
y =y ，所以
＜＜x,y＞, ＜x,y＞＞∈R 即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
dintin@gmail.com
33
xuuwxw?（ = ）∧（ = ）? =
yvvsys
?＜＜x,y＞, ＜w,s＞＞∈R
故R是传递的，于是R是A上的等价关系。
3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使
证明 对任意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；
2
c）R1； 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
2
所以R1是A上自反的。
2
若＜a,b＞∈R1则存在c，使得＜a, c＞∈R1∧＜c,b＞∈R1。因R1对称，故有
2
＜b, c＞∈R1∧＜c,a＞∈R1?＜b, a＞∈R1
2
即R1是对称的。
22
若＜a,b＞∈R1∧＜b, c＞∈R1,则有 ＜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传递）
2
?＜a,c＞∈R1
2
即R1是传递的。
2
故R1是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上的等价关系。
dintin@gmail.com
34
**
3-10.8 设C是实数部分非零的全体复数组成的集合，C上的关系R定义为：(a+bi)R(c+di)?ac>0,证明R是等价关系，并给出关系R的等价类的几何说明。
2
证明：(1)对任意非零实数a，有a>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={
故
b)若对于某个r∈I，有k=rj则：
因此，Rk ? Rj，于是I/Rk细分I/Rj
dintin@gmail.com 35