11 第十一次课(二元关系运算与函数)

离散数学

第三章 --- 二元关系(2)S 与 R 的合成 )

Functions 函数

为 X 到 Z 的关系

合成运算是对关系的二元运算， 合成运算是对关系的二元运算，它能够由两个关 系生成一个新的关系，并可以以此类推。 系生成一个新的关系，并可以以此类推。首先看一个 合成运算的例子， 合成运算的例子，如果 是关系“ 的兄弟” 是关系“是…的兄弟”, 的兄弟 是关系"是 的叔 是关系 是…的叔

是关系“ 的父亲” 是关系“是…的父亲”,那么 的父亲 伯"。 。2011-2-27 Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系如果在关系R和 中各有一个有序对 中各有一个有序对， 如果在关系 和S中各有一个有序对，使 且 而且 ，则 是关系

Functions 函数

的元素。 的元素。

包含全部这样的有序对。 包含全部这样的有序对。

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系

Functions 函数

因为 但不存在y使 但不存在 使

且

,故 ，故没有y使 故没有 使

。虽有 。也没有x使 也没有 使

,

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系设集合A上的关系 上的关系R为 例1 设集合 上的关系 为

Functions 函数

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系设集合N上的关系 上的关系R和 为 例2 设集合 上的关系 和S为

Functions 函数

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系

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. 8

离散数学

第三章 --- 二元关系在非空集合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. 12

2011-2-27

离散数学…… 此处隐藏：2120字，全部文档内容请下载后查看。喜欢就下载吧 ……