(书后作业)集合论与图论 下载本文

P50习题

15. 设X?{a,b,c},Y?{0,1},Z?{2,3},f:X?Y,f(a)?f(b)?0,

f(c)?1;g:Y??,g(0)?2,g(1)?3,试求gf。

P55习题

17.设N?{1,2,3,},试构造两个映射f和g:N?N,使得

(1)fg?IN,但gf?IN;(2)gf?IN,但fg?IN。

18.设f:X?Y则

(1)若存在唯一的一个映射g:Y?X,使得gf?IX,则f是可逆的吗? (2)若存在唯一的一个映射g:Y?X,使得fg?IY,则f是可逆的吗?

11

19.设f:X?Y,X?m,Y?n,则

(1)若f是左可逆的,则f有多少个左逆映射? (2)若f是右可逆的,则f有多少个右逆映射?

20. 是否有一个从X到X的一一对应f,使得f?f?1,但f?IX?

P63习题

?12345??12345??1?121.设?1???,?2=??,求?1?2,?2?1,?1,?2。

?43215??32514?

?123456789?22.将置换??分解成对换的乘积。

?791652348?

3.设?是任一n次置换,试证:?与??1的奇偶性相同。

12

第三章 关系习题

P86习题

1.给出一个既不是自反的又不是反自反的二元关系?

2.是否存在一个同时不满足自反性,对称性,反对称性,传递性和反自反性的 二元关系?

3.设R,S是X上的二元关系,下列命题哪些成立: a)若R与S是自反的,则RS,RS分别也是自反的; b) 若R与S是对称的,则RS,RS分别对称的; c) 若R与S是传递的,则RS也是传递的;

d) 若R与S不是自反的,则RS也不是自反的;

e) 若R与S是反自反的,则RS,RS也是反自反的; f) 若R是自反的,则Rc也是反自反的;

g) 若R与S是传递的,则R\\S是传递的。 答案:

4.实数集合上的“小于”关系?是否是反自反的?集合X的幂集上的“真包含”关系?是否是反自反的?为什么?

5.设R、S是X上的二元关系。证明:

(1)(R?1)?1?R; (2)(RS)?1?R?1S?1; (3)(RS)?1?R?1S?1; (4)若R?S,则R?1?S?1;

13

6.设R是X上的二元关系,证明:RR?1是对称的二元关系。

7.设R为X上的是反自反的和传递的二元关系,证明:R是反对称的。

8.设R是X上的任一二元关系,证明:R是反对称的?R?R?1?IX。

9.有人说:“若R是X上的二元关系,只要R是对称的和传递的,则R必是自反的。”他的证明如下:若xRy,则由R的对称性便知有yRx。于是由xRy和yRx以及R的传递性即得xRx。所以,R是自反的。他的推论错在什么地方?这个结论是否对呢?

P92习题

9.“父子“关系的平方是什么关系?

10.设X={1,2,3,4},R={(1,2),(2,2),(3,4)},S={(2,3),(3,1),(4,2)}

试求:RS,SR,R2,S2,R(SR),(RS)R。

14

11.设R与S为X上的任两个二元关系,下列命题哪些为真?

a)若R,S都是自反的,则RS也是自反的; b)若R,S都是对称的,则RS也是对称的; c)若R,S都是反自反的,则RS也是反自反的; d)若R,S都是反对称的,则RS也是反对称的; e)若R,S都是传递的,则RS也是传递的。 答案:

12.设R1是A到B,R2和R3是B到C的二元关系,则一般情况下:

R1(R2\\R3)?(R1R2)\\(R1R3)。

但有人声称等号成立,他的证明如下:设(a,c)?R1(R2\\R3),则?b?X,使得(a,b)?R1且(b,c)?R2\\R3。于是(b,c)?R2且(b,c)?R3。从而(a,c)?R1R2且

(b,c)?R1R3,所以(a,c)?(R1R2)\\(R1R3),即R1(R2\\R3)?(R1R2)\\(R1R3)。同理可证相反的包含关系成立,故等式成立,这个证明错在什么地方?

13.设R,S是X上的满足RS?SR的对称关系,证明RS?SR。

P98习题

16.设R是X上的二元关系,试证:

(1)(R?)??R?,(2)(R*)*?R*,(3)RR*?R*R?R?,(4)(R?)*?(R*)??R?。

15