当前位置:文档之家 > 《应用离散数学》方景龙版-3.3 二元关系的性质与闭包

《应用离散数学》方景龙版-3.3 二元关系的性质与闭包

§3.3 二元关系的性质与闭包

习题3.3

1. 确定下列整数集合上的关系R 是否是自反的、反自反的、对称的、反对称的和传递的,其中R y x >∈<,,当且仅当 (1)y x ≠

(2)1≥xy

(3)11-=+=y x y x 或

(4))7(mod y x ≡

(5)2

y x =

(6)2

y x ≥

(7)x 是y 的倍数

(8)x 与y 都是负的或都是非负的

解 (2)、(4)、(6)、(8)略

(1)不是自反的,是反自反的,是对称的,不是反对称的,不是传递的。 (3)不是自反的,是反自反的,是对称的,不是反对称的,不是传递的。 (5)不是自反的,不是反自反的,不是对称的,是反对称的,不是传递的。 (7)是自反的,不是反自反的,不是对称的,是反对称的,是传递的。

2. 设}{d c b a A ,,,=,

(1)给出A 上的一个关系R ,要求R 既不是自反的又不是反自反的; (2)给出A 上的一个关系R ,要求R 既是对称的又是反对称的; (3)给出A 上的一个关系R ,要求R 既不是对称的又不是反对称的; (4)给出A 上的一个关系R ,要求R 是传递的但1

-R R 不是传递的。

解 略

3. 设A 是一个n 元集合,问A 上有多少个关系?这其中又有多少个关系是

(1)对称的? (2)反对称的?

(3)非对称的?

(4)反自反的?

(5)自反的和对称的?

(6)既不是自反的也不是反自反的?

解 (2)、(4)、(6)略

A 是一个n 元集合,所以A A ⨯有2

n 个元素,它的子集的个数为2

2n ,所以A
上有2

2n ,所以A 上有2

2n

个关系。

(1)将A A ⨯中的元素分为三部分:第一部分是n 个>

))((102/)1(2/)1(12/)1(02/)1(n

n n n n n n n n n n n C C C C C C ++++++=----

n n n 22

2

/)1(⋅=-2/)1(2+=n n

(2)A 上反对称关系的个数与A 上对称关系的个数相等2

/)1(2+=n n 。

3

A 上对称关系的个数为

))((102/)1(2/)1(1

2

/)1(02/)1(n

n n n n n n n n n n n C C C C C C ++++++---- ,其中又是自反的仅为