Question

离散数学

1. 设集合{1, 2, 3, 4, 5}上关系R的定义为：(x,y)∈R，如果x＝y－1。
(1) 列出R的元素 ; 求R的定义域; 求R的值域；
(2) 列出R-1的元素 ;求R-1的定义域；求R-1的值域；
(3) 关系R是自反的吗？是对称的吗？是反对称的吗？是传递的吗？是一个偏序吗？

2. 关系
R＝{(1,1), (1,2), (2,2), (4,4), (2,1), (3,3)}
是{1, 2, 3, 4}上的等价关系吗？解释原因。

3. 设关系
R1＝{(1,x), (2,x), (2,y), (3,y)}， R2＝{(x,a), (x,b), (y,a), (y,c)}。
(1)求关系R1对应于顺序1, 2, 3；x, y的矩阵A1。
(2)求关系R2对应于顺序x, y；a, b, c的矩阵A2。
(3)求矩阵乘积A1A2。
(4)用练习(3)的结果求关系R2 ◦ R1的矩阵。

4. 求出下面每对数的最大公因子：
（1）315,825
（2）331,993

Answer 1

1. (1) 解R={<1,2>,<2,3>,<3,4>,<4,5>},
R的定义域{1,2,3,4}
R的值域{2,3,4,5}
(2) 解R^-1={<2,1>,<3,2>,<4,3>,<5,4>},
R^-1的定义域{2,3,4,5}
R^-1的值域{1,2,3,4}
(3) 解不是自反，对称和传递的,但是是反对称的,不是一个偏序.
2. 解R是{1, 2, 3, 4}上的等价关系,因为R是自反,对称和传递的.
3. (1)解A1=
1 0
1 1
0 1
(2)解A2=
1 1 0
1 0 1
(3)解A1A2=
1 1 0
2 1 1
1 0 1
(4) 解R1 ◦ R2的关系矩阵(原R2 ◦ R1是错的)=
1 1 0
1 1 1
1 0 1
4. 解用欧几里得辗转相除
(1)825=315×2+195
315=195×1+120
195=120×1+75
120=75×1+45
75=45×1+30
45=30×1+15
30=15×2
故315,825最大公因子15.
(2)993=331×2
故331,993最大公因子331.