离散数学

第三章 --- 二元关系

Functions 函数

在实际问题中， 在实际问题中，我们感兴趣的往往不是一般的关 系，而是具有某些特殊性质的关系。为了更好的处理 而是具有某些特殊性质的关系。 这些关系，有必要深入研究关系的性质。 这些关系，有必要深入研究关系的性质。对A上的关系 上的关系 来说，主要的性质有：自反性、非自反性、对称性、 来说，主要的性质有：自反性、非自反性、对称性、 反对称性、传递性。 反对称性、传递性。

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系上的关系R, 对A上的关系 ，若对任意的 上的关系 上自反的关系； 称R为A上自反的关系；若对任意的 为 上自反的关系 则称R为 上非自反的关系 则称 为A上非自反的关系 这个定义也可以写成： 这个定义也可以写成： 在A上是自反的 上是自反的 在A上是非自反的 上是非自反的2011-2-27 Hongzhi Qiao, XiDian Univ.

Functions 函数

都有 都有

,则 ，

离散数学

第三章 --- 二元关系如果R是 上自反的 上自反的， 如果 是A上自反的，

Functions 函数

则关系矩阵M(R)的主对角线元素都是 (即 的主对角线元素都是1( 则关系矩阵 的主对角线元素都是 1),关系图G(R)的每个顶点都有自圈。 ),关系图 的每个顶点都有自圈。 ),关系图 的每个顶点都有自圈 如果R是A上非自反的， 如果 是 上非自反的， 上非自反的

都

的主对角线元素都是0, 则M(R)的主对角线元素都是 ，G(R)的每个顶点 的主对角线元素都是 的每个顶点 都没有自圈。 都没有自圈。2011-2-27 Hongzhi Qiao, XiDian Univ. 3

离散数学

第三章 --- 二元关系在非空集合A上的恒等关系 例1 在非空集合 上的恒等关系 都是自反的 。 在非空集合A上的空关系 例2 在非空集合 上的空关系 集合N上的小于关系 是非自反的。 集合 上的小于关系 < 是非自反的。

Functions 函数

和全关系

是非自反的。 是非自反的。在

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系例3 在集合 上的关系

Functions 函数

不是自反的，也不是非自反的。 不是自反的，也不是非自反的。 但是在非空集合A上 不存在一个关系， 但是在非空集合 上，不存在一个关系，它是自 反的又是非自反的。 反的又是非自反的。

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系设 R 为集合 A 上的关系 ，对任意的 若 若 这个定义也可以写成 R在A上是对称的 在 上是对称的 R在A上是反对称的 在 上是反对称的2011-2-27 Hongzhi Qiao, XiDian Univ.

Functions 函数

,

上对称的关系； ,则称 R 为 A 上对称的关系； 上反对称的关系。 ,则称R为A上反对称的关系。 则称 为 上反对称的关系

离散数学

第三章 --- 二元

关系反对称性的另一种等价的定义为 R在A上是反对称的 在 上是反对称的

Functions 函数

如果R是 上对称的 上对称的， 是对称矩阵(对任意的 如果 是A上对称的，则M(R)是对称矩阵 对任意的 和j, 是对称矩阵 对任意的i和 ，

)

G(R)中任意两个顶点之间或者没有有向边，或者互有有向边 和 中任意两个顶点之间或者没有有向边， 中任意两个顶点之间或者没有有向边 (不会只有 没有 )。如果 是 上反对称的 上反对称的， )。如果R是A上反对称的，则M(R)是反 如果 是反 ，若 则 ),G(R)中任意 中任意 ),

对称矩阵的( 对称矩阵的(对任意的

两个顶点之间或者没有有向边，或者仅有一条有向边( 两个顶点之间或者没有有向边，或者仅有一条有向边(不会同时有 和 )。Hongzhi Qiao, XiDian Univ. 7

2011-2-27

离散数学

第三章 --- 二元关系

Functions 函数

例4 在非空集合 A 上的全关系是对称的 ，不是反 对称的。 对称的。 例5 在 上的整除关系、 上的整除关系、小于

等于关系、小于关系都是反对称的，且不是对称的。 等于关系、小于关系都是反对称的，且不是对称的。 例6 在非空集合 A 上的恒等关系和空关系都是对 称的，也都是反对称的。 称的，也都是反对称的。

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系例7 在集合 上的关系

Functions 函数

不是对称的，也不是反对称的。 不是对称的，也不是反对称的。

和例7说明 例6和例 说明，对称性和反对称性既可以同时满 和例 说明， 足，也可以都不满足。 也可以都不满足。2011-2-27 Hongzhi Qiao, XiDian Univ. 9

离散数学

第三章 --- 二元关系上的关系， 设 R 为集合 A 上的关系，对任意的 若

Functions 函数

,

上传递的关系； ,则称R为A上传递的关系； 则称 为 上传递的关系 这个定义也可以写成 R在A上是传递的 在 上是传递的

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系

Functions 函数

例8 在集合 A 上 的 全关系 、恒等关系 、空关系都 是传递的。 是传递的。 在 上的整除关系、 上的整除关系、小于等

于关系、小于关系都是传递的。 于关系、小于关系都是传递的。 例9 在集合 不是传递的关系， 不是传递的关系，因为 但是2011-2-27

上的关系 ， ,

。Hongzh …… 此处隐藏：2581字，全部文档内容请下载后查看。喜欢就下载吧 ……