1、8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积 笛卡尔(15961650)，法国数学家、物理学家、哲学家，出生于法国拉哈的律师家庭，他一出世母亲就病故，依靠保姆照料长大。笛卡尔在当时欧洲著名的拉夫雷士学校读书，他虽身体孱弱，但尊敬师长，勤奋刻苦。笛卡尔生活在资产阶级与封建领主、科学与神学进行激烈斗争的时代。从读书始便对僵化的说教有强烈的怀疑批判精神，坚定不移地寻找真理。笛卡尔在获得法学博士学位后，为了“读世界这本大书”，曾到荷兰服役。退伍以后，主要居住在荷兰，也曾回到法国，从事学术研究。1649年应邀去瑞典担任女王的教师，最后因肺炎病逝在异国。8.1
2、8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积 定义 由两个元素 按照一定的次序组成的二元组称为有序偶对有序偶对，简称序偶序偶，记作 ，其中 称为 的第一元素，为 的第二元素。例如，平面上点的坐标 ，；性质：当且仅当 ；当且仅当 ；将上述概念进行推广，即得到任意个元素的有序序列。8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积 定义 将 个元素 按照一定的次序组成的 元组称 为 重有序序组，记作 ，即性质：当且仅当 。定义 设 是两个集合，称集合为集合 与 的笛卡尔积笛卡尔积。8.1 8.1 二元关系及其表示法二元关系及
3、其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积直观地，可以把笛卡儿积看成是平面上点的集合，如下图所示。BA1 12 23 34 4a ab bc cd dDC8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积例 设 ，则结论对两个集合 ，有当 时，有当 时，有任两个集合 ，有8.1 8.1 二元关系及其表示法二元关系及其表示法一、序偶与笛卡儿积一、序偶与笛卡儿积将上述概念进行推广至 个集合之间的笛卡尔积。定义 设 是 个集合，称集合为集合 的笛卡儿积。同样，当 时，容易证明，当 都是有限集时，8.1 8.1 二元关系及其表示法二元关系及其表示法二、关系的引入
4、二、关系的引入 设分别用两个集合 来表示教室里所有椅子的集合和学生的集合，即 。此时，若将它们用坐标描述出来即为右图所示。s1s2smc1c2c3cn0s3 例 假设我们在上“离散数学”课时，教室里共有 把椅子，听课的学生共有 个（），每个学生坐一把椅子。此时，学生与椅子之间有一定的从属关系。8.1 8.1 二元关系及其表示法二元关系及其表示法三、关系的定义三、关系的定义 定义 设 为 个非空集合，称 的任意子集 为以 为基的 元关系关系。特别地，当 时，称 为空关系空关系；当 时，称 为全关系全关系；由于 的任何子集都是一个 元关系，按照子集的定义，共有 个不同的子集，因此，以 为基的不同关
5、系共有 个。8.1 8.1 二元关系及其表示法二元关系及其表示法三、关系的定义三、关系的定义学籍表学号姓名性别英语数学物理040301李晓明男869180040302040330张国庆王薇薇男女768883938590 此关系是以学号学号、姓名姓名、性别性别、英语英语、数学数学、物理物理等六个集合的笛卡儿积为基的。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系 通常情况下研究的关系是两个集之间元素与元素之间的关系或者是一个集合内部两个元素之间的关系，称为二元关系，定义如下：定义 设 为两个非空集合，的任何一个子集 所定义的二元关系称为 到 的二元关系，简称关系。如
6、 是从 到 的二元关系，称 为 上的二元关系。由于 的子集中的元素都是序偶，因此，任何序偶的集合均是一个二元关系。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系 设有一序偶 ，则把这一事实记为 ，读作 对 有关系 ，如果 ，则记为 ，读作 对 没有关系 。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系称 为 的前域，为 的后域，满足称 为 的定义域，为 的值域，记为称为 的域。8.1 8.1 二元关系及其表示法二元关系及其表示法四、二元关系四、二元关系例 设解：8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关
7、系的表示法1、集合表示法 由于关系是一种特殊的集合，所以集合的两种基本表示法也可以用到关系的表示中，即枚举法枚举法和叙述法叙述法。例 设 ，关系 。定义集合 上的“小于等于”关系为8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法2、关系图法 由于关系是一些有序组的集合，因此可以用有向图来刻划关系，这种图称为关系 的关系图。设 ，是从 到 的一个关系，对应于关系 的关系图有如下规定：（1）设 和 分别为图中的结点，用 表示；（2）如 ，则从 到 可用一有向边 相连。对应图中的有向边；8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的
8、表示法2、关系图法 如果 是定义在 上的关系，则对应于关系 的关系图有如下规定：（1）设 为图中的结点，用 表示；（2）如 ，则从 到 可用一有向边 相连。对应图中的有向边；（3）如 ，则从 到 可用一带箭头的小圆圈表示；8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法例 设 是六个人，是三套房间，考虑 到 之间的一种住宿关系 ，如 住房间 ，则有 ，现假设：则此关系 的关系图如下：8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法 例 设 是六个程序，考虑它之间的一种调用关系 ，如 可调用 ，则有 ，现假设则关系 的关系图
9、如下图所示：8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法3、关系矩阵法 设 ，是从 到 的一个二元关系，称矩阵 为关系 的关系矩阵，其中又称 为 的邻接矩阵邻接矩阵。注：在写关系矩阵时，首先应对两个集合中的元素进行排序，不同的排序会得到不同的关系矩阵。当集合以枚举法表示时，如果没有对集合的元素排序，则默认枚举的次序为元素的排序。8.1 8.1 二元关系及其表示法二元关系及其表示法五、关系的表示法五、关系的表示法3、关系矩阵法 例 设 。考虑从 到 的“大于等于”关系 和“小于”关系 。相应的关系矩阵为：8.2 8.2 关系的运算关系的运算一、关系的交、并
10、、补、差运算一、关系的交、并、补、差运算 由于关系是以序偶为元素的集合，因此有关集合的交、并、补、差运算等在关系中也是适合的。设 都是 到 的关系，则 是相对于 的全集，因此，。8.2 8.2 关系的运算关系的运算一、关系的交、并、补、差运算一、关系的交、并、补、差运算例 设则有8.2 8.2 关系的运算关系的运算二、关系的复合运算二、关系的复合运算 定义 设 是从集合 到集合 的二元关系，是从集合 到集合 的二元关系，则 与 的复合关系（合成关系）是从 到 的关系，且 称为复合运算。在复合关系中，的后域一定是 的前域，否则无法复合。规定：8.2 8.2 关系的运算关系的运算二、关系的复合运算
11、二、关系的复合运算例 设有如下关系分别是从 到 和从 到 的关系，其中（1）用集合方法求 ；（2）用关系图法求 ；（3）用关系矩阵求 ；8.2 8.2 关系的运算关系的运算二、关系的复合运算二、关系的复合运算 R RS SR R。S SA AB BC CA AC C1 1。1 1。1 11 1。1 12 2。2 2。2 22 2。2 23 3。3 3。3 33 3。3 34 4。4 4。4 44 4。4 4关系矩阵求法为：8.2 8.2 关系的运算关系的运算二、关系的复合运算二、关系的复合运算设 是整数集合，是 到 的两个关系：则有8.2 8.2 关系的运算关系的运算三、关系的逆运算三、关系的
12、逆运算 定义 设 是一个从集合 到集合 的二元关系，则从 到 的关系 称为 的逆关系逆关系，运算“-1”称为逆运算。注：关系是一种集合，逆关系也是一种集合，但要区别开两个不同的关系 和 。则例 设 ，是从 到 的一个关系，8.2 8.2 关系的运算关系的运算三、关系的逆运算三、关系的逆运算 如果用关系图表示关系，则仅将关系图中的有向边的方向改变成相反方向即得逆关系的关系图。8.2 8.2 关系的运算关系的运算三、关系的逆运算三、关系的逆运算 如果用关系矩阵表示关系，则关系矩阵求转置即得逆关系的关系矩阵，对其进行按位求反即得其补的关系矩阵。注：8.2 8.2 关系的运算关系的运算四、关系运算的性
13、质四、关系运算的性质定理 设 分别是从集合 到集合 ，集合 到集合 ，集合 到集合 的二元关系，则证明：设 ，则至少存在一个 ，使同样，存在 ，使 。因此，有也同样成立，因此有 ，同理 ，因此8.2 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质 定义 设 是集合 上的二元关系，则可定义 的 次幂 ，该 也是 上的二元关系，定义如下：根据上述定义，显然有8.2 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质例 设 ，定义在 上的关系如下：求 。8.2 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质例 设 ，定义在 上的关系如下：求 。8.2
14、 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质 由上例可知，幂集 的基数 并非随着 的增加而增加，而是呈递减趋势而且，当 时，有 定理 设 是有限集合，且 ，是 上的二元关系，则8.2 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质 定理 设 是从集合 到集合 的关系，是从集合 到集合 的关系，是从集合 到集合 的关系，则8.2 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质例 设 ，关系定义如下：可以求出8.2 8.2 关系的运算关系的运算四、关系运算的性质四、关系运算的性质定理 设 分别是从集合 到集合 的二元关系，则8.3 8.3
15、关系的性质关系的性质一、自反性与反自反性一、自反性与反自反性定义 设 是集合 上的二元关系，则称关系 是自反的自反的，当且仅当对 ，都有 ；称关系 是反自反的反自反的，当且仅当对 ，都有 ；例 设 ，8.3 8.3 关系的性质关系的性质一、自反性与反自反性一、自反性与反自反性8.3 8.3 关系的性质关系的性质二、对称性与反对称性二、对称性与反对称性定义 设 是集合 上的二元关系，则称关系 是对称的对称的，如果对 ，都有称关系 是反对称的反对称的，如果 且 ，则必有例 设 ，8.3 8.3 关系的性质关系的性质三、传递性三、传递性 定义 设 是集合 上的二元关系，称其为传递的传递的，如果对任意
16、的 ，如果 且 ，则必有 。例 设 ，8.3 8.3 关系的性质关系的性质自反性；传递性；对称性；反对称性；反自反性；传递性；对称性；反对称性；传递性；对称性；反对称性；8.3 8.3 关系的性质关系的性质不具备任何性质；自反性；传递性；对称性；反自反性；传递性；反对称性；8.3 8.3 关系的性质关系的性质8.3 8.3 关系的性质关系的性质反自反性；传递性；反对称性；反自反性；反对称性；8.3 8.3 关系的性质关系的性质 例 设 是定义在 上的二元关系，是定义在 上的二元关系，试判断它们的性质。自反性；传递性；对称性；反对称性；传递性；反对称性；对称性；8.3 8.3 关系的性质关系的性
17、质四、关系性质的证明四、关系性质的证明 在二元关系中，由于关系的性质的定义全部都是按“如则”来描述的，因此，在证明时，不能采用一般的证明方法，而应采用离散数学中特有的按定义证明方法按定义证明方法，即证明时，首先叙述定义的前半部分“如”，将这部分的内容称为“附加的已知条件”，此时利用该“附加的已知条件”和题目本身所给的已知条件证明出定义的后半部分“则”，这部分的内容称为定义中的结论。这种证明问题的方法在于：证明时不能单纯利用题目所给的已知条件，而应同时利用定义中的同时利用定义中的“已知已知”，推出的并非整个定义，而是定义中的结论定义中的结论。另外，由于关系是特殊的集合，当用集合的手段来描述关系的
18、性质时，其证明的方法也是按集合中的按定义证明方法按定义证明方法来证。总之，在关系这一章中，可以说所有的证明几乎都采用按定义证明方法。8.3 8.3 关系的性质关系的性质五、利用集合运算来判断关系的性质五、利用集合运算来判断关系的性质定理 设 是集合 上的二元关系，则是自反的是反自反的是对称的是反对称的是传递的是反对称的8.3 8.3 关系的性质关系的性质五、利用集合运算来判断关系的性质五、利用集合运算来判断关系的性质证明：是传递的8.3 8.3 关系的性质关系的性质五、利用集合运算来判断关系的性质五、利用集合运算来判断关系的性质证明：8.3 8.3 关系的性质关系的性质六、关系性质的保守性六、
19、关系性质的保守性定理 设 是定义在 上的二元关系，则（1）若 是自反的，则 也是自反的；（2）若 是反自反的，则 也是反自反的；（3）若 是对称的，则 也是对称的；（4）若 是反对称的，则 也是对称的；（5）若 是传递的，则 也是对称的；8.3 8.3 关系的性质关系的性质六、关系性质的保守性六、关系性质的保守性 例 设 是定义在 上的两个二元关系。显然，两个关系都是反自反的、反对称的、传递的；则（1）也具备上述一切性质；（2）也具备上述一切性质；（3）仅是对称的和反自反的，此时不具备传递性和反对称性；（4）仅是传递的和对称的，此时不具备反自反性和反对称性；8.3 8.3 关系的性质关系的性质
20、 例 设有定义在 上的两个二元关系如下：显然，两个关系都是自反的、对称的、传递的；则（1）也具备上述一切性质；（2）也具备上述一切性质；（3）仅是自反的和对称的，不满足传递性；（4）仅是自反的，不具备对称性和传递性；8.4 8.4 关系的闭包运算关系的闭包运算一、关系的限制与扩充一、关系的限制与扩充对于任何一个具备某种性质，特别是那些具备几种性质的组合的关系来说（如自反性，对称性，传递性等），在理论研究与应用上都是十分重要的。但遗憾的是，许多我们要研究的关系并不具有我们所希望的良好性质。为此，我们往往要在已经给定的关系中删去一些多余的元素或者添加一些适量的元素（当然应尽可能少地删除和添加）以改
21、变原有的关系的性质，这就是关系的限制与扩充。8.4 8.4 关系的闭包运算关系的闭包运算一、关系的限制与扩充一、关系的限制与扩充 定义 设 是 上的二元关系，是 的子集，则称关系 为 在 上的限制限制，记为 。显然，因此有时称 为 的子关系。例 设 ，是定义在 上的关系：则有8.4 8.4 关系的闭包运算关系的闭包运算一、关系的限制与扩充一、关系的限制与扩充 定义 设 是 上的二元关系，若 ，称 为关系 的扩充，记为 。显然，。但是如果要求 具备某种性质时，则就会产生这种扩充是否存在是否存在的问题。8.4 8.4 关系的闭包运算关系的闭包运算一、关系的限制与扩充一、关系的限制与扩充（2）显然，
22、当 时，是对称的；且由于 ，因此 绝不会是反对称的；（3）显然，因此 是一个传递关系；例 设 ，问此关系是否存在具备五种性质的补充。（1）显然当 时，为自反的，并且由于 ，因此 绝不会是反自反的。8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包定义 设 是定义在 上的二元关系，若它的一个扩充 满足：（1）是自反的（或对称的、或传递的）；（2）对 的任何扩充 ，若 是自反的（或对称的、或传递的），则 ；则称 为 的自反闭包关系自反闭包关系（或对称闭包对称闭包、或传递闭传递闭包包），记为 （或 、或 ）。8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭
23、包例 设 ，是定义在 上的二元关系，求其自反闭包、对称闭包与传递闭包；8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包（1）求一个关系的自反闭包，即将图中的所有无环的结点加上环，矩阵中对角线上的元素值全变成1；（2）求一个关系的对称闭包，则在图中，任何一对结点之间，若仅存在一条边，则加一条方向相反的边；在矩阵中，若 ，则令 ；（3）求一个关系的传递闭包，则在图中，若 到 有一条边，且 到 有一条边，则从 到 必增加一条边；小 结8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包定理 设 是定义在 上的二元关系，则，若 ，则8.4 8.4 关系的闭包
24、运算关系的闭包运算二、关系的闭包二、关系的闭包 例 设 是四个程序，是定义在 上的调用关系如下：8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包定理 设 是集合 上的关系，则（1）是自反的 ；（2）是对称的 ；（3）是传递的 ；8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包定理 设 是集合 上的关系，且 ，则定理 设 是集合 上的关系，则8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包定理 设 是集合 上的关系，则（1）若 是自反的，则 也是自反的；（2）若 是对称的，则 也是对称的；（3）若 是传递的，则 也是传递的；定义（1）集合 上关系的自反对称闭包自反对称闭包定义为 ；（2）集合 上关系的自反传递闭包自反传递闭包定义为 ；（3）集合 上关系的对称传递闭包对称传递闭包定义为 ；8.4 8.4 关系的闭包运算关系的闭包运算二、关系的闭包二、关系的闭包定理 设 是集合 上的关系，则例 设 ，则
