关系的性质(牛连强)

第4章  关    系   77

4.3 关系的性质

很多关系具有一定的特殊性，这使其表现为某种特殊的关系。在一些应用中，常常希望关系具有这些性质，也需要正确判定一个关系是否具有这些性质。

4.3.1 自反与反自反关系

[定义4-8] 设R 是X 上的二元关系。若对所有的x ∈X ，有∈R ，则称R 是X 上的自反关系（reflexive relation）。符号描述为：

R 是X 上的自反关系⇔∀x (x ∈X →∈R  )

[辨析] 定义要求对所有的x ∈X ，都有∈R ，或者说只要x ∈X ，就有∈R 。其他性质也都类似。

[定义4-9] 设R 是X 上的二元关系。若对所有的x ∈X ，有∉R ，则称R 是X 上的反自反关系（irreflexive relation）。符号描述为：

x >∉R  ) R 是X 上的反自反关系⇔∀x (x ∈X →

例如，实数集上的≥、≤、=关系，集合上的=、⊆关系，以及任何集合X 上的恒等关系I X 都是自反关系，整数集上的>、≠关系和集合上的⊂关系都是反自反关系。

定义中的“任意性”要求非常关键。例如，A ={a ,  b ,  c }，R ={, }不是自反的，因为缺少序偶，S ={, , , }才是自反的。

[理解] 如何判定一个关系具有某种性质？其实，每个性质的定义都由一个条件句命题来描述，只要证明此命题为真。而如果条件句的前件为0，则命题必为1，故定义满足。

例4-12 找出一个关系，既不是自反的，也不是反自反的。能再找出一个关系，既是自反的，也是反自反的吗？

解  若A ={1,2,3}，则R ={,}既不是自反的，也不是反自反的。

比较自反性和反自反性定义的两个条件句：

x ∈X →∈R

x ∈X →∉R

显然，两个条件句的后件是矛盾的。因此，要使它们同时为真，只有使前件x ∈X 为假，唯一的选择是X =Ø。此时，关系R 也必然是空集。可见，只有定义在空集合Ø上的空关系Ø才既是自反，也是反自反的。

[辨析] 使一个定义中条件句的前件为假，从而使定义得到满足是一个常见且十分重要的问题，也是能够正确判定一个性质是否被满足的基本保证。

[辨析] “反自反”不等于“不自反”。满足自反性要求关系包含所有形如的序偶，满足反自反性要求关系不能包含任何一个形如的序偶。仅包含部分而不是全部就什么都

78

不是。 工科离散数学

4.3.2 对称与反对称关系

[定义4-10] 设R 是X 上的二元关系。对任意的x , y ∈X ，若∈R ，就有∈R ，则称R 是X 上的对称关系（symmetric relation）。符号表示为：

R 是X 上的对称关系⇔∀x ∀y ((x ∈X ∧y ∈X ∧∈R →∈R  )

例如，任何集合上的空关系是对称关系，而定义在集合A ={1,2,3}上的关系R ={, ,

∉S 。 }是对称关系，但S ={>2,1不是对称关系，因为1,

例4-13 设A ={2,3,5,7}，A 上的关系R ={|x (-y ) /是偶数2}

和对称关系。

证明  对∀x ∈A ，有(x -x )/2=0，即∈R ，故R 是自反的。

对∀x , y ∈A ，若∈R ，则有偶数k ，使(x -y )/2=k 。因为-k 也是偶数，且有

(y -x ) /2=-k

知∈R 。故R 是对称的。

[定义4-11] 设R 是X 上的二元关系。对任意的x , y ∈X ，若∈R 且x ≠y ，x >∉R ，则称R 是X 上的反对称关系（antisymmetric relation）。符号表示为：

R 是X 上的反对称关系⇔∀x ∀y ((x ∈X ∧y ∈X ∧∈R ∧x ≠y →∉R  )

日常使用的大量关系都是反对称关系，如≤、≥和⊆等。例如，对于≤，满足

只要a ≤b ，且a ≠b ，必有b a

不过，对这种性质更一般的描述为

只要a ≤b 且b ≤a ，则a =b 。

这是因为

(∈R ∧x ≠y →∉R

⇔┐(∈R ∧x ≠y ∨) ∉R

⇔┐(∈R ∧∈R ∨x ) =y

⇔(∈R ∧∈R →) x =y

由此，可以将原定义转换成另一种等价的描述方式：

R 是X 上的反对称关系⇔∀x ∀y ((x ∈X ∧y ∈X ∧∈R ∧∈R →) x =y  )

[辨析] 在实际证明时，后一种定义描述形式常常更容易叙述。

例4-14 正整数集Z +上的整除关系| ={|x , y ∈Z +且y 能被x 整除}是反对称关系。 证明  若a |b 且b |a ，则有

a ≤b ，且b ≤a

于是，有a =b 。所以，|是反对称关系。

第4章  关    系

此外，整除关系|也是自反的，因为任何整数都能整除自己。   79

例4-15 找出一个关系，既不是对称的，也不是反对称的；再找出一个关系，既是对称的，又是反对称的。

解  A ={a , ，}R ={, 既不是对称的，也不是反对称的。因为缺少,

，破坏了对称性，而包含成对序偶和破坏了反对称性。 

任意一个集合上的空关系既是对称的，也是反对称的。这是因为定义中的∈R 为假，条件句∈R ∧x ≠y →∉R 都为真。 y >∈R →∈R 和(

集合A ={1,2}上的R ={和任意集合}

为R 和I A 仅含有形如的序偶，条件句∈R →∈R 为真，而反对称定义中的条

y >∈R ∧x ≠y →∉R 为真。 件句前件∈R ∧x ≠y 为假，故条件句(

[辨析] “反对称”不等于“不对称”。一个关系R 中形如的序偶与对称性和非对称性都无关联。 

4.3.3 传递关系

[定义4-12] 设R 是X 上的二元关系。对任意的x , y z , ∈X ，若∈R 且∈R ，就有∈R ，则称R 是X 上的（可）传递关系（transitive relation）

R 是X 上的传递关系⇔∀x ∀y ∀z ((x ∈X ∧y ∈X ∧z ∈X ∧xRy ∧yRz ) →xRz )  

实数集R 上的≤、、=和集合的包含关系⊆都是传递关系，通常的描述是 

若a ≤b 且b ≤c ，则a ≤c  

若A ⊆B 且B ⊆C ，则A ⊆C

例4-16 若A ={a , ，那么，，r 4={，}r 3={, a > , b c , }

，r 5={, ,  ,

解 r 1和r 3是传递关系，因为不存在具有相同y 的一对序偶，定义中条件句的前件xRy ∧yRz 为假，故xRy ∧yRz →xRz 为真。r 2是传递关系，相当于定义中x =y =z =a 。r 4不是传递关系，

a >和，但不存在。r 5是传递关系，相当于定义中x =y =a ，z =b 或因为存在

c 。

[理解] 对传递关系的通俗解释就是，所有可连接的序偶其连接后的结果都属于此关系。

4.3.4 特殊关系的判定

1．充分必要条件

在理论上容易总结出几种关系性质应满足的条件，依据这些条件可以对关系是否具有某种性质进行判定。

[定理4-9] 设R 是A 上的二元关系，则

(1) R 是自反关系当且仅当I A ⊆R 。

80 工科离散数学

(2) R 是反自反关系当且仅当R I A =Ø。

(3) R 是对称关系当且仅当R =R -1。

(4) R 是反对称关系当且仅当R R -1⊆I A 。

(5) R 是传递关系当且仅当R R ⊆R ，即R 2⊆R 。

证明  (1) ① R 是自反关系 I A ⊆R ，即推证集合包含。

对∀，有

∈I A ⇒x =y ⇒(R 的自反性)∈R

② I A ⊆R R 是自反关系，即验证自反性。

对∀x ，有

x >∈I A ⇒(I A ⊆R ) ∈R  x ∈A ⇒

(2) ① R 是反自反关系 R I A =Ø，即推证集合相等（互相包含）。

y >∈R I A ，则∈I A （即x =y ）若有∈R ，与反自反性矛y >∈R 且

盾，故R I A =Ø。

② R I A =Ø R 是反自反关系，即验证反自反性。

对∀x ，有

x ∈A ⇒(I A 定义)∈I A ⇒(R I A =∅) ∉R

(3) ① R 是对称关系 R =R -1，即推证集合互相包含。

对∀，有

∈R ⇔(R 的对称性)∈R ⇔(R -1的定义), ∈R -1

② R =R -1 R 是对称关系，即验证对称性。

对∀，有

∈R ⇒(R =R -1) ∈R -1⇔(R -1的定义), ∈R

(4) ① R 是反对称关系 R R -1⊆I A ，即推证集合包含。

对∀，有

∈R R -1⇒(集合交定义)∈R ∧∈, R -1

y >∈R ∧∈R                                   ⇒(R -1的定义)

⇒(R 的反对称性) x =y

⇒∈I A

对∀，有  ② R R -1⊆I A R 是反对称关系，即验证反对称性。

∈R ∧∈R ⇒(R -1的定义), ∈R ∧∈, R -1

y >∈R R -1                                     ⇒(集合交定义)

第4章  关    系

⇒(R R -1⊆I ) ∈I A  A   81

⇒x =y

(5) ① R 是传递关系 R R ⊆R ，即推证集合包含。

对∀，有

∈R R ⇒(复合关系定义)∃t ∈R ∧∈, R ⇒(R 的) 传递性)∈, R

② R R ⊆R R 是传递关系，即验证传递性。

对∀，有 y >和

∈R ∧∈R ⇒(复合关系定义) , ∈R R ⇒(R R ⊆R ) ∈, R

例4-17 若有整数m ≥2和二元关系R ，使得

∈R ，∈, R ，∈, R  -2>∈R ，

可以得到什么结论？若R 是传递关系，又可得到什么结论？

y >∈R m 。 解  对于一般的关系R ，逐次利用关系复合运算，可推出结论

若R 具有传递性时，可推出结论∈R 。

事实上，若R 是传递关系，R m ⊆R 对所有整数m ≥1成立。这说明一个传递关系自身的复合不可能产生新的序偶。

2．利用关系图的性质判别

(1) 自反关系的每个元素都有自环，反自反关系的每个元素都没有自环。仅有部分而非全部自环时既不是自反关系也不是反自反关系。

(2) 对称关系的连线都是成对的，反对称关系的连线都是不成对的。同时包含成对和不成对连线的关系既不是对称关系，也不是反对称关系；没有不相同元素之间连线时既是对称关系，也是反对称关系。

(3) 传递关系表现为，对任何两个元素x 和y ，如果可以通过一条“路”从x 到达y ，则直接有x 与y 的连线。图4-4显示了几种关系的关系图示例，A ={a , 。

} b c ,

图4-4

3．利用关系矩阵的性质判别

(1) 自反关系的关系矩阵的主对角线都是1，反自反关系矩阵主对角线都是0。主对角线元素同时存在1和0时既不是自反关系也不是反自反关系。

82 工科离散数学

(2) 对称关系的关系矩阵为对称矩阵，反对称关系的关系矩阵则关于主对角线严格不对称。主对角线元素与对称性和反对称性无关，因为它是“轴”。

图4-5说明了几种关系的关系矩阵特点。

图4-5