离散数学刘任任课后答案习题2

时间：2025-04-20

离散数学刘任任课后答案湖南科学技术出版社

习题二

1.确定下列二元关系：（2）A 0,1,2,3,4,5,6,8 ,R

（1）A 1,2,3 ,B 1,3,5 ,R x,yx,y A B A B

x,y

x 2y A A

解：(1) R { 1,1 , 1,3 , 3,1 , 3,3 }

(2) R { 1,0 , 2,1 , 4,2 , 8,3 } 2. 请分别给出满足下列要求的二元关系的例子：（1）既是自反的，又是反自反的；（2）既不是自反的，又不是反自反的；（3）既是对称的，又是反对称的；（4）既不是对称的，又不是反对称的. 解：设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）共有多少种定义在A上的不同的二元关系？（2）共有多少种定义在A上的不同的自反关系？（3）共有多少种定义在A上的不同的反自反关系？（4）共有多少种定义在A上的不同的对称关系？（5）共有多少种定义在A上的不同的反对称关系？解：设A n，于是 (1) 共有2

种定义在A上的不同的二元关系；

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

(3) 共有2

n2 nn

种定义在A上的不同的反自反关系；

n(n 1)/2

(4) 共有2 2(5) 共有2

nmk 0

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

n(n 1)

。 2

2m k 2n 3m种定义在A上的不同的反对称关系，其中，m Cm

4. 请分别描述自反关系，反自反关系，对称关系和反对称关系的关系矩阵以及关系图的特征.

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

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

方向相反。

(4) 反对称关系矩阵MR (rij)n n的元素满足：当i j时，rij rji 0。 5．设A 1,2,3,4 ,R ,,,2,4,S ,,2,,2,4,,2，试求R S,S R,R,

及S.

离散数学刘任任课后答案湖南科学技术出版社

解：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. 试举出使

R S T R S R T

S T P S P T P

成立的二元关系R,S,T,P的实例.

解：设R { 3,1 , 3,2 },T { 1,3 , 3,2 },S { 1,2 , 2,3 },P { 2,1 , 3,1 },

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

(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. 设R和S是集合A上的二元关系. 下面的说法正确吗?请说出理由. （1）若R和S是自反的，则R S也是自反的；

（2）若R和S是反自反的，则R S也是反自反的；（3）若R和S是对称的，则R S也是对称的；

（4）若R和S是反对称的，则R S也是反对称的；（5）若R和S是传递的，则R S也是传递的

解：(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) 错

误

。

例

如

，