离散数学(3.6关系性质)
4是自反的、对称的、可传递的。
( 3,3), ( 3,1), ( 3,5),
则
6反自反的、反对称的。
例4 是不自反、反自反的、对称的、反对称、可传递的。 例5 全关系是自反的、对称的、可传递的。
3.4.2 由关系图、关系矩阵判别关系的性质
1. 关系矩阵
若 是自反的,则关系矩阵的主对角线上的所有元素 均为1。 若 是反自反的,则关系矩阵的主对角线上所有元素 均为0。
( 3,3), ( 3,1), ( 3,5),
则 3 自反的、反对称的、可传递的。
例3(续)
4 { a, b | a, b是人, 且a是b的朋友 }
则
则 5 反自反的、反对称的、可传递的。
5 { a, b | (a , b 是人 , 且 a 是 b 的祖先 } 5,1), (5,3), (5,5)} 6 { a, b | a, b是人, 且a是b的父亲 }
例1
设 A {0,1,2,3} ,
(1)自反与反自反
1 { 0,0 , 1,1 , 2,2 , 3,3 }
自反
2 { 0,0 , 1,2 , 1,1 , 2,2 , 2,3 , 3,3 } 自反
3 { 2,1 , 0,0 , 3,3 }
非自反
4 { 0,1 , 2,3 , 1,2 }
3.4.1 集合A上关系的性质
(1)若对于所有的 a A ,均有 aa ,则称 在A 上是自反的(reflexive)。 (2)若对于所有的 a A ,均有 aa ,则称 在A 上是反自反的(antireflexive) 。 (3)对于所有的 a, b A ,若每当有 则称 在 A 上是对称的(symmetric)。
对称不 反对称
可传递
U 反对称 不对称
自反
反自反
既对称又反对称
例2
设
A {1,2,3,4,5} ,A上的关系
{ a, b | a b是偶数}
则
{ 1,1 , 1,3 , 1,5 , 2,2 , 2,4 ,3), 3, , ),3 1,5 ,),3,5 , ( 3, (3 3,1 (,3
因此
是可传递的。
例3
设
1 { a, b | a, b R, 且a b}
则
1是自反的、反对称的、可传递的。
则
2自反的、对称的、反对称的、可传递的。
3 { a, b | a, b N , 且a b}
2 { a, b (|5a , b R , 且 a b } ,1), (5,3), (5,5)}
是反自反的,则关系图中每一结点均没有自环。
若 是对称的,则在关系图中,若两结点之间有边,则必 存在两条方向相反的边。 若 是反对称的,则在关系图中,任意两个不同的结点间 至多只有一条边。
若
向
是可传递的,则在关系图中,若每当有边由
i
,且又有边由 a 指向 a ak k k j
3.7 集合的划分与覆盖(Partition & Cover of Sets)
3.8 等价关系(Equivalent Relations) 3.9 相容关系(Compatibility Relations)
3.10 序关系(Ordered Relations)
第三章 集合与关系(Sets & Relations)
反自反
(2)对称与反对称
5 { 1,1 , 1,2 , 2,1 , 2,3 , 3,2 } 对称,非反对称
6 { 1,1 , 1,2 , 3,1 , 0,2 }
非对称,反对称
,2 ),,(2 77 {( {1 2 ,3 1,2), ,(2 3,3 2), ,( 3 2,,2 2)} } 非对称,非反对称
(4,4 2,), ), (5,1), (1 5,, 3), 5,5 2(4 ,,4 4 ,4 5, 5( ,3 ,)}5,5 }
自反
则
对称
不是反对称
也是偶数。
对于任意的 a, b, c A ,
a b 2m, b c 2n ,
a c (a b) (b c) 2(m n)
若
若
是对称的,则关系矩阵关于主对角线对称。
是反对称的,则关系矩阵中,关于主对角线对称 的元素不同时为1。 1 2 3 4
例如,
1 1 2 0 M 3 0 4 0
1 1 0 0
1 0 1 0
1 1 0 1
2. 关系图
若 是自反的,则关系图中每一结点引出一个指向自身 的单边环(自环)。 若
离散数学(Discrete Mathematics)
张捷
第三章
集合与关系
(Sets and Relations)
3.1 集合及其运算(Sets & Operations with sets) 3.2 序偶与笛卡尔积(Ordered Pairs & Cartesian Product) 3.3 关系 (Relations) 3.4 关系的性质(The Propeties of Relations) 3.5 复合关系与逆关系(Compound Relations & Inverse Relations) 3.6 关系的闭包运算(Closure Operations)
3.4 关系的性质(The properties of
Relations)
3.4.1 集合A上关系的性质(The properties of
Relations on set A)
3.4.2 由关系图、关系矩阵判别关系的性质 A B
AB
第三章 集合与关系(Sets & Relations)
(1) 是自反的,非对称,不是反对称,不可传递
1,2 1, 2,3 1,
1
第三章 集合与关系(Sets & Relations)
小结: 本节介绍了关系的基本性质及其判别 方法。 作业:P113 (1),(4)
定义3.4.1 设
是集合A上的关系
aa
, ab就必有 ba
(5)对于所有的 a, b, c A,若每当有 ab 和 bc 就必有 ac ,则称 在 A 上是可传递的(transitive)。
(4)对于所有的 a, b A,若每当有 ab 和 ba 就 必有 a b ,则称 在 A 上是反对称的(antisymmetric).
指 ,则必有一条边由 a aj 。 ai 指向 a
j
ai
例6
设
A {1,2,3}
,下面分别给出集合A上三个关系
的关系图,试判断它们的性质。
解
但 1,3 1. 2 (2) 非自反,也不是反自反,非对称,反对称, 可传递。 3 (3) 是自反的,对称的,可传递的,不是反自反, 也不是反对称。
8 { 1,1 , 2,2 , 0,0 }
对称,反对称
(3)可传递与不可传递
9 { 0,0 , 0,2 , 2,3 , 0,3 } 可传递
10 { 1,1 , 1,2 , 2,3 , 2,1 } 不可传递
11 { 3,0 , 1,2 , 3,2 }
U
10 {(1,1), (1,2), (2,1), (2,3)}