离散数学（刘任任版）习题2

习 题 二

1、 (1) R?{?1,1?,?1,3?,?3,1?,?3,3?}

(2) R?{?1,0?,?2,1?,?4,2?,?8,3?}

2、 设R是定义在集合A上的二元关系。

(1) 令A??，则R??，于是R既是自反又是反自反的；

(2) 令A?{1,2},R?{?1,1?}，于是R既不是自反又不是反自反的；

(3) 令A?{1,2},R?{?1,1?,?2,2?}，于是R既是对称又是反对称的；

(4) 令A?{1,2,3},R?{?1,2?,?2,1?,?1,3?}，于是R既不是对称又不是反对称的。

3、 设A?n，于是 (1) 共有2n2种定义在A上的不同的二元关系；

2(2) 共有2n?n种定义在A上的不同的自反关系；

(3) 共有2n2?nnn种定义在A上的不同的反自反关系；

n(n?1)/2(4) 共有2?2m?2n(n?1)/2 种定义在A上的不同的对称关系；

n(n?1)。 2(5) 共有2k?0?kCm?2m?k 种定义在A上的不同的反对称关系，其中，m? 关系矩阵中

4、 (1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。

(2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈。

(3) 对称关系矩阵为对称矩阵; 而关系图中任何两个结点之间的有向弧是成对出现的,

方向相反。

(4) 反对称关系矩阵MR?(rij)n?n的元素满足：当i?j时，rij?rji?0。 5、R?S?{?1,4?,?1,3?},S?R?{?3,4?}

R2?{?1,1?,?1,2?,?1,4?},S2?{?2,2?,?3,4?,?3,3?}。 6、 设

,

于是, 有S?T??,R?(S?T)??,R?S?{?3,2?,?3,3?},R?T?{?3,3?}, 因此,

R?{?3,1?,?3,2?},T?{?1,3?,?3,2?},S?{?1,2?,?2,3?},P?{?2,1?,?3,1?}(R?S)?(R?T)?{?3,3?}??, 从而, R?(S?T)?(R?S)?(R?T)。 又，(S?T)?P??,S?P?{?1,1?},T?P?{?3,1?,?1,1?}，因此， (S?P)?(T?P)?{?1,1?}??，从而, (S?T)?P?(S?P)?(T?P)。 7、 (1) 正确。因为对任意x?A，有xR,xSx，所以x(R?S)x。故R?S是自反的。

(2) 错误。例如，设x,y?A,x?y，且xRy,ySx，于是x(R?S)x。故R?S不是自

反的。

(3) 错误。例如，设对称关系R?{?x,z?,?z,x?},S?{?z,y?,?y,z?}。于

是，?x,y??R?S，但?y,x??R?S。故R?S不是对称的。

(4) 错误。例如，设反对

R?{?x,z?,?y,w?},S?{?z,y?,?w,x?},x?y?x,y?,?y,x??R?S。故R?S不是反对称的。

(5) 错

误

。

例

如

，

设

传

称。

关于

是系，系，

递

R?{?x,w?,?y,v?},S?{?w,y?,?v,z?},w?v。x(R?S)y,y(R?S)z，但因为w?v，所以，?x,z??R?S。

关于是

8、 (1) r(R1?R2)?(R1?R2)?(R1?R2)0

0 ?(R1?R2)?(R1?R20)

0 ?(R1?R1)?(R2?R20) ?r(R1)?r(R2)

(2) s(R1?R2)?(R1?R2)?(R1?R2)?1 ?(R1?R2)?(R1?1?R2?1) ?(R1?R1?1)?(R2?R2?1) ?s(R1)?s(R2) (3) 由定义，

22t(R1)?R1?R1??,t(R2)?R2?R2??,t(R1?R2)?(R1?R2)?(R1?R2)2??, 于是，

t(R1)?t(R2)?R1?R12???R2?R22???(R1?R2)?(R12?R22)??。

下证对任意n?1，有R1n?R2n?(R1?R2)n。

nnn任取?x,y??R1?R2，不妨设?x,y??R1。于是，存在z1,z2,?zn?A, 使得

?x,z1??R1?R1?R2,?z1,z2??R1?R1?R2,?,?zn?1,zn??R1?R1?R2,?zn,y??从而， ?x,y??(R1?R2)n。举例说明“?”成立。设A?{1,2,3},R1?{?1,2?},R2?{?2,3?}，于是，

t(R1?R2)?{?1,2?,?1,3?,?2,3?}?t(R1)?t(R2)?{?1,2?,?1,3?}。

错误: {<1,2>,<2,3>}

9、设R1和R2是集合A上的二元关系。注意到R1?R2?(R1?R2)0，于是， (1) r(R1?R2)?(R1?R2)?(R1?R2)0 =(R1?R2)?R1 =(R1?R1)?(R2?R1) =(R1?R1)?(R2?R2) =t(R1)?t(R2)

(2) s(R1?R2)?(R1?R2)?(R1?R2)?1, s(R1)?R1?R1,s(R2)?R2?R2?1?10000000,

s(R1)?s(R2)?(R1?R1?1)?(R2?R2?1)。任取

?x,y??s(R1?R2)?(R1?R2)?(R1?R2)?1，

(i) 若?x,y??(R1?R2), 则?x,y??R1?R1?R1?1, 且

?x,y??R2?R2?R2?1, 从而，

?x,y??(R1?R1?1)?(R2?R2?1?s(R1)?s(R2)； (ii) 若?x,y??(R1?R2)?1, 则?y,x??(R1?R2), 即

?y,x??R1,且?y,x??R2, 从而，

?x,y??R1?1?R1?R1?1, 且?x,y??R2?1?R2?R2?1, 于是，

?x,y??(R1?R1?1)?(R2?R2?1?s(R1)?s(R2) 故 s(R1?R2)?s(R1)?s(R2)。举例说明“?”成立。

设A?{1,2},R1?{?1,2?},R2?{?2,1?}，于是，

s(R1?R2)?(R1?R2)?(R1?R2)?1?????1??，而

s(R1)?R1?R1?1?{?1,2?,?2,1?},s(R2)?R2?R2?1?{?1,2?,?2,1?}， 因此，s(R1)?s(R2)?{?1,2?,?2,1?},故s(R1?R2)?s(R1)?s(R2)。

22（3）证明：因为 t(R1)?R1?R1??,t(R2)?R2?R2??,2 t(R1?R2)?(R1?R2)?(R1?R2)??,22lm 于是t(R1)?t(R2)?(R1?R1??)?(R2?R2??)??(R1?R2) ??x,y??t(R?R)?(R?R)?(R?R)2??,121122

则存在i,有?x,y??（R1?R2)i也就有z1,z2,...,zi使得?x,z1??R1?R2，

...,?x,zi??R1?R2，因为R1?R2?R1且 ?x,z2??R1?R2，?x,z2??R1，...,?x,zi??R1， R1?R2?R2，所以就有?x,z1??R1， 所以有?x,y??Ri1同时也有?x,z??R，...,?x,zi??R2，12?x,z2??R2，

所以也有?x,y??Ri2就有?x,y??Ri1?Ri2，即（R1?R2)i?Ri1?Ri2，

iilm又因为R1?R2??(R1?R2),所以结论成立。 l,m?1 错误：

又设 A= {1, 2, 3} ,

l,m?1R1?{?1,2?,?2,3?},R2?{?1,3?}，于是，

R1?R2??,t(R1?R2)??, 而，

t(R1)?{?1,2?,?2,3?,?1,3?},t(R2)?R2?{?1,3?},t(R1)?t(R2)?{?1,3?}故 t(R1?R2)?t(R1)?t(R2).

10、 说法不正确。 对任意x?A, 对称性并不要求一定有?x,y??R，

因此也就不一定有。于是 ?R。

11、 设R是等价关系。若 , ?R , 则由R的对称性知, ?R。

再由R的传递性有?R。

反之, 假设只要, ?R, 就有?R。

(1) 对称性。 设< x, y >?R，由自反性有?R。于是?R。

(2) 传递性。 设, ?R。 由对称性有?R, 再由假设有?R。 12、 设 R1?R2, 则显然 A/R1?A/R2。

反之, 设A/R1?A/R2。若 R1?R2, 则不妨设?R1 但?R2 . 于是[x]R1?[y]R1 , [x]R2?[y]R2 .

由划分之定义得知 A/R1?A/R2, 矛盾.。故R1?R2。 13、 设 R= { | x≡y(mod 5)}.于是

[0] [1] [2] [3] [4]

R={…-15,-10,-5,0,5,10,15…} ={…-14,-9,-4,1,6,11,16,…} ={…-13,-8,-3,2,7,12,17,…} ={…-12,-7,-2,3,8,13,18,…} ={…-11,-6,-1,4,9,14,19,…}

,[1]

,[2]

,[3]

,[4]

} .

RRRRA/R = {[0]

RRRRR14. 证明: ?S?{Ai?Bi|Ai?Bi??}.

(1) 由S 定义知, Ai?Bi??;

(2) 任取Ai?Bi?S和Al?Bm?S, 1<=i ,j<=r, 1<=j,m<=s .

(Ai?Bi)?(Al?Bm)?(Ai?Am)?(Bj?Bm)??????

(3)

??????(A1?....?Ar)?(Bj?...?Bm) ?1?i,j?r1?j?s?(A?B)??(A?B)?Sijij1?i?r1?j?sAi?Bj??

故 S 是?的一个划分.

14、 设 A={1,2, 3,4} , 则A上的等价关系数目即A上的划分的数目共有15个. (1) 最大划分 { {1},{2},{3},{4} } . (2) 最小划分 { {1,2,3,4} } .

(3) 将 A 分成两个集合 S={A1,A2}, 由两种可能:

(i)

2|A1|=|A2|=2 .共 1/2C4=3种, 即

{ {1,2},{3,4} }, { {1,3},{2,4} },{ {1,4},{2,3} } . (ii)

3|A1|=1,|A2|=3 . 共 C4=4 种.即

{ {1},{2,3,4} },{{2},{…} },{ {3},{…}},{{4},{…}}.

2(4) 将A分成3个集合,则恰有一个集合为2个元素,故共有C4?6种分法.即

{{1},{2},{3,4}},{{2},{3},{1,4}},{{1},{3},{2,4}},{{2},{4},{1,3}} {{3},{4},{1,2}},{{1},{4},{3,2}} .

15、 设A={1,2,3,4},则A上的等价关系数目即A上的划分的数目共有15个.

(1) 最大划分 { {1}, {2}, {3} ,{4} } (2) 最小划分 {{1 ,2, 3 ,4}}

(3) 将A分成两个集合S={A1,A2} , 共有两种可能：

(i) |A1| = |A2| ，共有1/2C4?3种, 即

{{1, 2} , {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}。

2