离散数学

第三章 --- 二元关系(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

离散数学

第三章 --- 二元关系

Functions 函数

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

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

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系例7 在

集合 上的关系

Functions 函数

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

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

离散数学

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

Functions 函数

,

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

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第三章 --- 二元关系

Functions 函数

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

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

上的关系 ， ,

。Hongzhi Qiao, XiDian Univ. 16

离散数学

第三章 --- 二元关系

Functions 函数

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第四章 --- 函数

Functions 函数

"数学的进步及其活力总是依赖于抽象对具体的帮 数学的进步及其活力总是依赖于抽象对具体的帮 助以及具体对抽象的哺育。  助以及具体对抽象的哺育。" -- M. Kac 函数是一个基本的数学概念。通常的实函数是在 函数是一个基本的数学概念。 实数集合上讨论的。这里推广了实函数概念， 实数集合上讨论的。这里推广了实函数概念，讨论在 任意集合上的函数。 任意集合上的函数。

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第四章 --- 函数函数定义

Functions 函数

函数建立了从一个集合到另一个集合的一种变换 关系，计算机执行任何类型的程序就是这样一种变换。 关系，计算机执行任何类型的程序就是这样一种变换。 例如编译程序可以把一个源程序变换成一个机器 语言的指令集合----目标程序。 语言的指令集合 目标程序。 目标程序

2011-2-27

Hongzhi Qiao, XiDian Univ.

离散数学

第四章 --- 函数对集合A 到集合B 对集合 到集合 的关系 (1) 对任意的 使 (2) 则称 的书称2011-2-27

Functions 函数

,若满足下列条件： 若满足下列条件： ,

,存在唯一的

成立； 成立；

为从A到 的函数 的函数， 为从 到B的函数，或称

映射到B 把A映射到 (有 映射到

为全函数、映射、变换)。 为全函数、映射、变换)。Hongzhi Qiao, XiDian Univ. 20

离散数学

第四章 --- 函数一个从A到 的函数 一个从 到B的函数 这时若 ，则可记作 ，可以写成 ： 或 ：

Functions 函数

。 。

函数的两个条件可以写成 (1) (2)2011-2-27 Hongzhi Qiao, XiDian Univ.