离散数学课件第四章—二元关系和函数.ppt

刘师少 Tel 86613747 h E mail lss 授课 51学时 教学目标 知识 能力 素质 DiscreteMathematics 第四章二元关系和函数 4 1集合的笛卡尔积与二元关系 4 2关系的运算 4 3关系的性质 4 4关系的闭包 4 5等价关系和偏序关系 4 4函数的定义和性质 4 4函数的复合和反函数 4 4例题分析 说起关系这个词 对我们并不陌生 世界上存在着各种各样的关系 人与人之间的 同志 关系 同学 关系 朋友 关系 师生 关系 上下级 关系 父子 关系 两个数之间有 大于 关系 等于 关系和 小于 关系 两个变量之间有一定的 函数 关系 计算机内两电路间有导线 连接 关系 程序间有 调用 关系等等 所以对关系进行深刻的研究 对数学与计算机科学都有很大的用处 再如 电影票与座位之间有对号关系 设 X表示电影票的集合Y表示座位的集合 则 对于任意的x X和y Y 必有x与y有对号 对号 关系则上述问题可表达为xRy或xRy 亦可记为 x y R或 x y R因此我们可以看到对号关系R是序偶的集合 在这一章我们要研究集合内元素间的关系以及集合之间元素之间的关系 这就是 关系 与 函数 它们是很重要的基本数学概念 在数学领域中均有很大的作用 并且对研究计算机科学中的许多问题如数据结构 数据库 情报检索 算法分析 计算理论等都是很好的数学工具 关系的引入例4 0设一旅馆有n个房间 每个房间可住两个旅客 所以一共可住2n个旅客 在旅馆内 旅客与房间有一定关系 用R表示 某旅客住在某房间 这种关系 设n 3表示旅馆共有3个房间 分别记以1 2 3可住6个旅客分别记以a b c d e f 这些旅客住的房间如右下图所示 1 2 3 a b c d e f 满足R的所有关系可看成是一个有序偶的集合 这个集合可叫RR 若令A a b c d e f B 1 2 3 则例中关系的每一元素均属于A B亦即R是A B的子集 并称此关系为从A到B的关系R 4 1集合的笛卡尔积与二元关系 定义4 1由两个元素x y 允许x y 按一定顺序排列成的二元组叫做一个有序对或序偶 记作 其中x是它的第一元素 y是它的第二元素 有序对具有以下性质 1 当x y时 2 x w y v例4 1 已知 求x和y 解 由有序对相等的充要条件得x 3 y 7y 2 3y x解得x 6 y 2 4 1集合的笛卡尔积与二元关系 定义4 2一个有序n元组 n 3 是一个有序对 其中第一个元素是一个有序n 1元组 一个有序n元组记作 即 xn 例如 空间直角坐标系中点的坐标 等都是有序3元组 n维空间中点的坐标或n维向量都是有序n元组 形式上也可以把看成有序1元组 定义4 3设A B为集合 用A中元素为第一元素 B中元素为第二元素构成有序对 所有这样的有序对组成的集合叫做A和B的笛卡儿积 记作A B 笛卡儿积的符号化表示为 A B x A y B 例如 若A 1 2 B a b c 则A B B A 易知 若 A m 即集合A的元素的个数 B n 则 A B B A mn 4 1集合的笛卡尔积与二元关系 主菜鱼香肉丝家常豆腐宫保鸡丁酸辣土豆丝蒜茸油麦菜 汤紫菜蛋花汤鱼头豆腐汤鸡蛋西红柿汤酸辣蔬菜汤 由前面的定义可知 有序对就是有顺序的数组 如 x y的位置是确定的 不能随意放置 注意 有序对 以a b为元素的集合 a b b a 有序对 a a 有意义 而集合 a a 不成立 因为它只是单元素集合 应记作 a 笛卡儿积是一种集合合成的方法 把集合A B合成集合A B 规定A B x A y B 由于有序对中x y的位置是确定的 因此A B的记法也是确定的 不能写成B A 笛卡儿积也可以多个集合合成A1 A2 An 笛卡儿积的运算性质 笛卡儿积的性质 1 对任意集合A 根据定义有A A 2 一般来说 笛卡儿积不满足交换律 即A B B A 当A BB A 时 3 笛卡儿积不满足结合律 即 A B C A B C 当A B C 时 4 笛卡儿积运算对并和交运算满足分配律 即A B C A B A C B C A B A C A A B C A B A C B C A B A C A 4 1集合的笛卡尔积与二元关系 例4 2证明 B C A B A C A 对于 B C A x B C y A x B x C y A x B x C y A y A x B y A x C y A B A C A B A C A B C A B A C A 4 1集合的笛卡尔积与二元关系 例4 3 设A C B D为任意集合 判断以下命题是否为真 并说明理由 1 A B A C B C 2 A B C A B A C 3 存在集合A 使得A A A 解 1 不一定为真 反例A B C为任意不相等的非空集合 2 不一定为真 反例A 1 B 2 C 3 3 为真 当A 时成立 定义4 4设A1 A2 An 是集合 n 2 它们的n阶笛卡儿积记作A1 A2 An 其中A1 A2 An x1 A1 x2 A2 xn An 当A1 A2 An A时 将起n阶笛卡儿积记作An例如 A a b 则A3 A A A a b a b a b 4 1集合的笛卡尔积与二元关系 例4 6设集合A a b B 1 2 3 C d 求A B C B A 解先计算A B A B C d B A 例4 7设集合A 1 2 求A P A 解P A 1 2 1 2 A P A 1 2 1 2 1 2 定义4 5如果一个集合符合以下条件之一 1 集合非空 且它的元素都是有序对 2 集合是空集则称该集合为一个二元关系 记作R 简称为关系 对于二元关系R 若 R 可记作xRy 如果 R 则记作xRy 例 R1 R2 5 6 7 aR1b 1R12 5R16 4 1集合的笛卡尔积与二元关系 二元关系是两种客体之间的联系 例如某学生学习语文 数学 外语 表示为A 语文 数学 外语 功课的成绩分四个等级 记作B A B C D 于是该生成绩的全部可能为A BA B 而该生的实际成绩P 可以看出P是A B的一个子集 它表示了功课与其成绩的一种关系 由此可见 两个集合之间的二元关系 实际上就是两个元素之间的某种相关性 再如 若A B 1 2 3 求A B B A A A B B A B B A 解 A B 1 2 3 1 2 3 B A 1 1 2 2 3 3 A A B B 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 A B B A 由上例可看出 A B B A 程序实现 定义4 6设A B为集合 A B的任何子集所定义的二元关系叫做从A到B的二元关系 特别当A B时则叫做A上的二元关系 例4 7 若A a b B 2 5 8 则A B 令R1 R2 R3 因为R1 A B R2 A B R3 A B 所以R1 R2和R5均是由A到B的二元关系因为只讨论二元关系 所以今后无特别声明 术语 关系 皆指二元关系 又例 若A a b B 2 5 8 则B A 令R4 R5 因为R4 B A R5 B A 所以R4和R5均是由B到A的关系又B B 令R6 R7 因为R6 B B R7 B B 所以R6和R7均是集合B上的关系 若集合 A n 则集合A上的二元关系有多少个 答曰 A n 则 A A n2 A A的任一个子集就是A上的二元关系 即P A 2n个 例4 8A 1 2 则A A有n2个不同的二元关系A A 1 2 1 2 A A的任一个子集就是A A的幂集 即P A P A 集合中的元素不分顺序 若集合A a b c 则A的幂集 P A 为P A a b c a b a c b c a b c 注 a a a b b b c c c 三类特殊的关系对于任何集合A 空集 是A A的子集 叫做A上的空关系定义EA x A y A A A为全域关系定义IA x A 为恒等关系例 若A 1 2 则EA IA 除上述三类特殊的关系外 还有一些常用的关系 如 LA x y A x y A R 为实数集上的小于等于关系 DA x y A x整除y A Z 为非正整数集上的整除关系 R x y A x y A是集合族 为集合上的包含关系 类似地还可以定义大于等于关系 大于关系 小于关系 真包含关系等 4 1集合的笛卡尔积与二元关系 例4 9 设A 1 2 3 4 请表示下列关系 1 R x是y的倍数 2 R x y 2 A 3 R x除y是素数 4 R x y 4 1集合的笛卡尔积与二元关系 解 1 DA 2 R 3 DA 4 R 例4 9 1设A 1 2 3 B 4 5 6 并定义R1 R2为从A到B的关系 R3为从B到A的关系 a A b B 1 当且仅当 a能整除b时 aR1b 2 当且仅当 a是b的整数倍时 aR2b 3 当且仅当 b是a的整数倍时 bR3a 试写出R1 R2 R3 解 R1 1 4 1 5 1 6 2 4 2 6 3 6 R2 R3 4 1 5 1 6 1 4 2 6 2 6 3 A n B m A B中的元素已按一定的次序排列若A x1 x2 xn B y1 y2 ym 且R A B 若1若xiRyjrij i 1 2 nj 1 2 m 0若xiRyj则称矩阵M R rij n m为R的关系矩阵 有穷集合上的二元关系的三种表示方法 集合表示法 前已使用 关系矩阵法关系图关系矩阵是表示关系的另一种有效的方法 其优点是可以利用矩阵作为研究关系的手段 而且这样做便于计算机进行处理 设R A B A和B都是有限集 且 设A B为集合 A B的任何子集Ri A B则称Ri所定义的二元关系叫做从A到B的二元关系 特别当A B时则叫做A上的二元关系 则r11r12 r1n rij r21r22 r2n rn1rn2 rnn是R的关系矩阵 记作MR 关系矩阵法若A x1 x2 xn B y1 y2 yn 则R的关系矩阵是一个n行n列矩阵M R rij n n 其中元素rij为 1若xiRyjrij i j 1 2 n 0若xiRyj 0111MR 001100010000 例4 10A 1 2 3 4 R为A上的小于关系 则R为 R R的关系矩阵为 1234 1234 例4 11设集合A 2 3 4 B 8 9 12 14 R是由A到B的二元关系 定义 R a整除b 写出R的表达式和关系矩阵 解R 89121421011R的关系矩阵为 MR 3011041010 关系图关系图是表示关系的一种直观形象的方法 设R A B A和B都是有限集 A x1 x2 xn B y1 y2 ym 关系R的有序偶可用图中从结点xi到yj的有向边表示 这样即可将关系用图表示之 例4 12设R A B A x1 x2 x3 x4 B y1 y2 y3 R R的关系如下图所示 x1 x2 x3 x4 y1 y2 y3 关系图关系图是表示关系的一种直观形象的方法 设R A B A和B都是有限集 A x1 x2 xn B y1 y2 ym 关系R的有序偶可用图中从结点xi到yj的有向边表示 这样即可将关系用图表示之 例4 13设R A A A a b c d R R的关系如下图所示 a b c d 其中c到c的边称为环 定义4 8设R是二元关系 1 R中所有的有序对的第一元素构成的集合称为R的定义域 记作domR 形式化表示为 domR x y R 2 R中所有的有序对的第二元素构成的集合称为R的值域 记作ranR 形式化表示为 ranR y x R 3 R的定义域和值域的并集称为R的域 记作fldR 形式化表示为 fldR domR ranR 4 2关系的运算 例4 14下列关系都是整数集Z上的关系 分别求出它们的定义域和值域R1 x y Z x y 2 R2 x y Z x2 y2 1 3 R3 x y Z y 2x R4 x y Z x y 3 解 1 domR1 ramR1 ZR2 domR2 0 1 1 ramR2 0 1 1 3 domR3 ZramR3 2z z Z 即偶数集 4 domR4 3 3 ramR4 3 3 1 0 1 1 0 1 domR2 ramR2 R2 210 1 2 43210 1 2 3 4 domR3 Z ramR3 R3 例4 15设R1 R2 求其定义域和值域解题目没有告诉我们R1和R2是由什么集合到什么的关系 这对于我们解此题是无关紧要的 事实上 不论R1和R2是定义在何种集合上的关系 据定义域和值域的定义domR x y R ranR y x R 有domR1 1 2 3 domR2 1 2 4 ramR1 2 4 3 ramR2 3 4 2 规律 集合R1和R2中序偶中的第一个元素的集合即为其定义域 序偶中的第二个元素的集合即为其值域 如果此题再加上求R1 R2及R1 R2定义域和值域 则因为R1 R2 R1 R2 所以domR1 domR2 1 2 3 4 ramR1 ramR2 2 3 4 定义4 9设F G为任意的关系 A为集合 则 1 F的逆记作F 1 F 1 yFx 2 F与G的合成记作F G 其中F G z xGz zFy 或F G z xFz zGy p87 3 F在A上限制记作F AF A xFy x A 4 A在F下的象记作F A F A ran F A 4 2关系的运算 逆关系 设R是一个X到Y的关系 则Y到X的关系R 1 R 1 R 称为R的逆关系 例4 16设X 1 2 3 Y a b c 且设R是从X到Y的关系R 则R 1 例4 17设X x1 x2 x3 Y y1 y2 y3 且设R是从X到Y的关系R 的逆关系R 1 如下图所示 x1 x2 x3 y1 y2 y3 y1 y2 y3 x1 x2 x3 R R 1 合成关系 或复合关系 设R是一个X到Y的关系 S是一个Y到Z的关系 则R与S的合成关系 或复合关系 R S为 R S z xSz zRy 例4 18设X x1 x2 x3 Y y1 y2 y3 Z z1 z2 z3 从X到Z的关系S 从Z到Y的关系R 则X到Y的关系R S XZYXY R S R S x1 x2 x3 z1 z2 z3 y1 y2 y3 x1 x2 x3 y1 y3 y2 例4 19设有集合A 4 5 8 15 B 3 4 5 9 11 C 1 6 8 13 F是由A到B的关系 G是由B到C的关系 分别定义为F b a 1 G b c 2或 b c 4 求合成关系G F和F G解先求G F 由题意知F G G F 例4 19 续 设有集合A 4 5 8 15 B 3 4 5 9 11 C 1 6 8 13 F是由A到B的关系 G是由B到C的关系 分别定义为F b a 1 G b c 2或 b c 4 求合成关系G F和F G解再求F G 由题意知G F F G 例4 20 设A 2 3 G R 则R 1 R G G R R A R R A R 分别是R 1 R G G R R A xRy x A R R A ran R A 2 R 注意 逆运算的优先级高于其他运算 而所有的关系运算都优于集合运算 例4 21 设F 求F F F a F a 解因为F F 所以F F 由公式F A xFy x A 有F a 由公式F A ran F A 有F a ran F a ran a 定义域 值域 综上所述 两个关系的合成 如F与G的合成记作F G 其中F G z xGz zFy 称为关系的合成运算 它是对关系的一种二元运算 通过这种运算 可由两个已知关系产生一个新的关系 例4 22设A 1 2 3 4 B 2 3 4 C 1 2 3 且R1 a A b B a b 5 R2 b B c C b c 2 求R1 R2 解 由题意知 R1 R2 R1 R2 例4 23设R1 R2 求R1 R2 R2 R1 R1 R1 R1 R2 R1 R1 R2 R1 解 R2 R1 R1 R2 不满足交换律 R1 R1 R1oR2 R1 R1 R2oR1 满足结合律 定理4 1设F G H是任意关系 则 1 F 1 1 F 2 dom F 1 ranF ranF 1 domF 3 F G H F G H 4 F G 1 G 1 F 1证明 1 任取 由逆的定义有 F 1 1 F 1 F F 1 1 F 2 任取x x ranF 1 y F 1 y F x domF ranF 1 domF同理可证dom F 1 ranF 定理4 2设F G H是任意关系 则 1 F G H F G F H 2 G H F G F H F 3 F G H F G F H 4 G H F G F H F本定理对有限个关系的并和交都成立 R R1 R2 Rn R R1 R R2 R Rn R1 R2 Rn R R1 R R2 R Rn RR R1 R2 Rn R R1 R R2 R Rn R1 R2 Rn R R1 R R2 R Rn R 定义4 10设R是A上的关系 n为自然数 则R的n次幂规定如下 1 R0 x A 2 Rn Rn 1 Rn 1由定义可以知道R0就是A上的恒等关系IA 不难证明下面的等式R R0 R R0 R由这个等式立即可以得到R1 R0 R R例4 24设A a b c d R 求R0 R1 R2 R3 R4和R5 解R0 R1 R0 R R2 R R R3 R2 R R4 R3 R R5 R4 R 例4 25设A 1 2 3 4 A上的关系R a A b A a b 1 求 R2 R3 R4解 因为R 所以R2 R3 R4 定理4 3设R是A上的关系 m n为自然数 则下面的等式成立 1 Rm Rn Rm n 2 Rm n Rmn证明 1 任给m 对n作归纳法 n 0时 Rm R0 Rm Rm 0 假设Rm Rn Rm n 那么Rm Rn 1 Rm Rn R1 Rm Rn R1 Rm n R1 Rm n 1 Rm n 1 2 任给m 对n作归纳法 n 0时 Rm 0 R0 Rm 0 假设 Rm n Rmn 那么 Rm n 1 Rm n Rm Rmn Rm Rmn m Rm n 1 011001101110M2 MM 10001000 0110011001101110000000000000 111001101110M3 M2M 01101000 1110111001101110000000000000 例4 25 设A 1 2 3 4 R是A上二元关系 关系矩阵为 0110M 100001100000 解 R R2 R3的关系矩阵分别为 求R3 M为R的关系矩阵 设R是A上的关系 R的性质主要有以下5种 1 若 x x A R 则称R在A上是自反的 也就是说 对R A A 若A中每个x 都有xRx 则称R是自反的 即A上关系R是自反的 x x A xRx 该定义表明了 在自反的关系R中 除其他有序对外 必须包括有全部由每个x A所组成的元素相同的有序对例如 设A 1 2 3 R是A上的关系 R 则R是自反的 4 3关系的性质 设R是A上的关系 R的性质主要有以下5种 2 若 x x A R 则称R在A上是反自反的也就是说 对R A A 若A中每个x 有xRx 则称R是反自反的 即A上关系R是反自反的 x x A xRx 该定义表明了 一个反自反的关系R中 不应包括有任何相同元素的有序对 例如 设A 1 2 3 R是A上的关系 R R是反自反的 4 3关系的性质 对关系图 若R是自反的 则每个结点都有自回路出现 若R是反自反 则每个结点没有自回路出现 对关系矩阵 若R是自反的 当且仅当在关系矩阵中 对角线上的所有元素都是1 若R是反自反的 当且仅当在关系矩阵中 对角线上的所有元素都是0 应该指出 任何一个不是自反的关系 未必是反自反的 反之 任何一个不是反自反的关系 未必是自反的 这就是说 存在既不是自反的也不是反自反的二元关系 例如 设A 1 2 3 R是A上的关系 R 缺少 则R是既不是自反的 也不是反自反的 4 3关系的性质 3 若 x y x y A R R 则称R在A上是对称的 也就是说 对R A A 对A中每个x和y 若xRy 则yRx 称R是对称的 即A上关系R是对称的 x y x y A xRy yRx 该定义表明了 在表示对称的关系R的有序对集合中 若有有序对 则必定还会有有序对 例如 设A 1 2 3 R是A上的关系 R4 则R是对称的 4 若 x y x y A R x y R 则称R在A上是反对称的 隐含x y R 也就是说 对R A A 对A中每个x和y 若xRy且yRx 则x y 称R是反对称的 即A上关系R是反对称的 x y x y A xRy yRx x y 该定义表明了 在表示反对称关系R的有序对集合中 若存在有序对和 则必定是x y 或者说 在R中若有有序对 则除非x y 否则必定不会出现 例如 设A 1 2 3 R 是A上的关系 则R是反对称的 判断一个关系是否反对称 通俗地讲就是对于所有的a b A 若a b 则序偶 至多只有一个出现在关系R中 如R 有些关系既是对称的又是反对称的还有的关系既不是对称的又不是反对称的 例如 设A 1 2 3 R6 R7是A上的关系 R6 R7 则R6是对称的 也是反对称的R7既不是对称的又不是反对称的再如 A a c b 中R 既不是对称的又不是反对称的 例4 26设A 1 2 3 则R1 在A上是自反的 对称的 反对称的 R2 在A上既不是对称的 也不是对反称的 R3 在A上是对称的 但不是反对称的 R4 在A上不是对称的 但是反对称的 例4 27设A 1 2 3 4 5 A上的关系R为R a b是偶数 用列举法表示R R是否自反 对称 反对称 解 R 对任意a A a a 0是偶数 R是自反关系又 对任意a b A 若a b是偶数 则b a也是偶数 R是对称关系 当a b时 有和同时出现在R中 例如 R不是反对称关系 若关系R是对称的 当且仅当关系矩阵关于主对角线是对称的 且在关系图上 任何两个结点间若有定向弧线 必是成对反向出现 若关系R是反对称的 当且仅当关系矩阵中以主对角线对称的元素不能同时为1 在关系图上两个不同结点间的定向弧不能成对出现 R1 R2 R3 R4 2 5 x y z x y z A R R R 则称R在A上是传递的关系 也就是说 对R A A 对于A中每个x y z 若xRy且yRz 则xRz 称R是传递的 即A上关系R是传递的 x y z x y z A xRy yRz xRz 该定义表明了 在表示可传递关系R的有序对集合中 若有有序对和 则必有有序对 换句话说 设R为定义在集合A上的二元关系 如果对于任意a b c A 每当有aRb且有bRc时 就有aRc 则称关系R在A上是可传递的 即 R在A上传递 a b c a A b A c A aRb bRc aRc 例4 28设A a b c d R1 R2 R3 R1 R2 R3是可传递的 传递性在关系图上表现为 从一个结点到另一个结点 如果是可达的 则必有长度为1的路 c a b d 例4 29设A a b c d 试讨论下列关系的性质R1 R2 R1是自反的 对称的 可传递的 R2不是自反 是反自反 反对称 可传递的 5 x y z x y z A R R R 则称R在A上是传递的关系 例4 30设A 1 2 3 4 5 A上的关系R为R a b是偶数 用列举法表示R R是否是可传递的 解 R 对于任意的a b c A若a b 2m b c 2n 则a c a b b c 2 m n 也是偶数 因此A是可传递的 R R R 例4 31设A 1 2 3 4 5 6 7 8 9 10 R是A上的关系 R x y A x y 10 说明R具有哪些性质 4 3关系的性质 解 R 易知R既不是自反也不是反自反的R是对称的R不是反对称的R不是传递的 P1 P3 P4 P2 这个关系如右图所示 我们知道 调用关系是传递的 如P1能调用P2 P2能调用P4 则P1亦能调用P4 我们希望在R的基础上建立一个满足传递性的新关系 譬如说 下面的关系R 即是这样一个关系 4 4关系的闭包什么叫一个关系上的闭包呢 设有四个程序所组成的集合P P1 P2 P3 P4 上的 调用 关系R R R 当然满足这个条件的关系不仅仅R 一个 如下面的关系R 亦是R 我们选用满足这个条件的最小者 在这个例子中即为R 这个R 我们就叫做R上的传递闭包 R 是一个新关系 它是在集合P上的一个新的调用关系显然有R R R R 选用满足这个条件的最小者R 这个新关系叫做R上的传递闭包 它是在集合P上的一个新的调用关系 对于关系的自反性 对称性 传递性均可建立闭包 定义4 11设R是非空集合A上的关系 R的自反 对称或传递 闭包是A上的关系R 使得R 满足以下条件 1 R 是自反 对称或传递 的 2 R R 3 对A上的任何包含R的自反 对称或传递 关系R 有R R 一般将R的自反闭包记作r R 对称闭包记作s R 传递闭包记作t R 4 4关系的闭包 例4 33设A a b c d 试讨论下列关系的性质R R R c a b d R R 闭包 包含一些给定对象 具有指定性质的最小集合 最小 任何包含同样对象 具有同样性质的集合 都包含这个闭包集合 c a b d 定理4 4设R是非空集合A上的关系 则有 1 r R R R0 2 s R R R 1 3 t R R R2 R3 此定理提供了一种集合表示形式下关系闭包的求解方法 4 4关系的闭包 例4 34设A a b c d R 则r R R R0 s R R R 1 t R R R2 R3 甚不方便 当关系用关系矩阵表示时 相应闭包求法为 1 Mr M E 2 Ms M M 3 Mt M M2 M3 其中M为R的关系矩阵 E是单位矩阵 M 是M的转置矩阵 4 4关系的闭包 010010001100Mr M E 1010 0100 1110000100100011010000010101 010001000100Ms M M 1010 1001 1011000101000101010000100110 1111Mt M M2 M3 111111111111 例4 35设A a b c d R 则 4 4关系的闭包 E表示同阶单位阵 M 表示M的转置矩阵 abcd abcd 当关系用关系图表示时 相应闭包求法为 设R r R s R t R 的关系图分别为G Gr Gs Gt 则Gr Gs Gt与G的顶点集相等 除了G的边以外依据下列方法添加新的边 1 考察G的每个顶点 如果没有环就加上一个环 最终得到的是Gr 2 考察G的每一条边 如果有一条xi到xj的单向边 i j 则在G中加一条xj到xi的反方向边 最终得到Gs 3 考察G的每个顶点xi 找出从xi出发的所有2步 3步 n步长的路径 n为G中的顶点数 设路径的终点为xj1 xj2 xjk 如果没有从xi到xjl i 1 2 k 的边 就加上这条边 最终得到Gt 例题参见P93例4 10 4 5等价关系和偏序关系 定义4 12设R是非空集合A上的关系 若R是自反的 对称的和传递的 则称R是A上的等价关系如果R是一个等价关系 若 R 称x等价于y 记作x y 等价关系 自反性 对称性 传递性也就是说 若 R 或aRb 称a等价b 记a b由于R是对称的 a等价b即b等价a 反之亦然 a与b彼此等价 例4 36设有一个整数集Z上的关系R R x y可被3整除 求证这个关系是等价关系 证 对每个x Z x x可被3整除 所以是自反的 对于x y Z 如果x y能被3整除 则y x也能被3整除所以是对称的 对于x y Z 如果有x y y c均能被3整除 则x c x y y c 亦能被3整除 所以是传递的 将这个例子推广到一般 比如 例4 30设A 1 2 3 4 5 6 7 8 R为A上的关系R x y A x y mod3 其中 x y mod3 的含义就是x y可以被3整除 这个关系亦是等价关系 例4 37设集合A a b R是P A 上的包含关系 写出R的表达式和关系矩阵 解用描述法表示 用列举法表示 因为所以 关系矩阵 关系图 a b A 例4 38设A 1 2 3 用列举法给出A上的恒等关系IA 全域关系EA A上的小于关系及其逆关系和关系矩阵 关系矩阵 a A LA的逆关系 有 例4 39设集合A 2 3 4 B 4 6 7 C 8 9 12 14 R1是由A到B的二元关系 R2是由B到C的二元关系 定义如下 a A 解 求复合关系R2 R1和R1 R2并用关系矩阵表示 因此R2 R1 R1 R2 布尔运算 例4 40试判断下图中关系的性质 a A 1 2 3 1 2 3 1 2 3 a b c 解图 a 中的关系在集合 1 2 3 上是对称的 因为结点1与2 1与3之间的有向弧是成对出现且方向相反 图 b 中是反自反的 因为每个结点都没有自回路它也是反对称的 因为两条边都是单向边 因此具备传递的潜能 如边2到3或3到2均可构成传递关系 图 c 中的关系自反的 反对称的 但不是传递的因为2到1有边 1到3有边 但2到3没有边 例4 41设集合A a b c d 定义R 求r R s R t R 解求自反闭包 R不具有自反性 由自反性的定义 只需在R上添加IA 其中下画线者为添加元素 于是r R R IA s R R R 1 R t R R R2 R3 R4 R A R R R2 R R 例对以下整数集上的关系R和S确定R S和S R R y 2X 1 S y X 3 R S y 2 X 3 1 S R y 2X 1 3 R y 2X S y x2 S R y 2x 2 R S y 2x 2 定义4 13设R是非空集合A上的等价关系 对任一个x A 可以构造一个A的子集 x R x R y y A xRy 称 x R为x关于R的等价类 简称为x的等价类 简记为 x 例4 42设A 1 2 3 4 5 6 7 8 R为A上的关系R x y A x y mod3 其中 x y mod3 的含义就是x y可以被3整除等价类为 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 4 5等价关系和偏序关系 定理4 5设R是非空集合A上的等价关系 对任意的 x y A 下面的结论成立 1 x 且 x A 2 若xRy 则 x y 3 若xRy 则 x 与 y 不交 即 x y 4 x x A A 4 5等价关系和偏序关系 设A是非空集合 若B A1 A2 An 且 Ai Ai Aj i j A 则称B是A的划分 称B中元素为A的划分块 4 5等价关系和偏序关系 定义4 14集合A上的等价关系R所构成的类产生一个集合A的划分 此划分叫A关于R的商集 记作A R 即A R x R x A 此定义告诉我们 商集A R是以R的所有等价类为元素的集合 例4 43中的商集为 A R 1 4 7 2 5 8 3 6 4 5等价关系和偏序关系 例4 44中的商集为 A R 1 4 7 2 5 8 3 6 例4 45设A a b c d 给定A如下 A1 a b c d A2 a b c d A3 a b c a d A4 a b c d A5 a b c 问 哪些是A的划分 P97 例4 46设A是浙江中医药大学信息技术学院2008级的所有学生组成的集合 用a b c d e分别表示一班 二班 三班 四班和五班 用Ai表示按照班级划分的不同方案 试确定下列哪些是A的一个划分 设A a b c d e 给定A如下 A1 a b c d e A2 a b c d e A3 a b c a d e A4 a b c d e A5 a b c d e A6 a b c d e A7 a b c c d e A8 a b c d e 4 5等价关系和偏序关系 定义4 16设R是非空集合A上的关系 若R是自反的 反对称的和传递的 则称R是A上的偏序关系 记作 若 则记作x y 读作 x小于等于y 这里的小于等于不是指数的大小 而是指它们在偏序中位置的先后 意即 依据这个序 x排在y的前面 等价关系和偏序关系是具有不同性质的两个关系 4 5等价关系和偏序关系 例如 集合A 1 2 3 偏序 是A上的大于等于关系 则 那么有3 2 2 2 3 1 它们分别表示 和属于偏序 因为 是 1 2 3 上的大于等于关系 在 前边的数恰好是比较大的数 4 5等价关系和偏序关系 例4 47集合A 2 3 6 8 上的 整除 关系R x整除y R 那么R有哪些关系 解 R R是自反的又 R而 R R是反对称的由 R有y x n由 R有z y m将y z m代入y x n得z x mn即 R z x mn R是可传递的 事实上 R则 R R是可传递的 综上所述 R是偏序关系 例4 28集合A 18的正整数因子 为整除关系 x整除y 证明 是偏序关系 分析偏序关系只需验证自反性 反对称性和传递性 解 集合A 1 2 3 6 9 18 整除关系为 IA 容易验证IA 故 有自反性 a b a b 则 b a 故 有反对称性 xyz A 若 且 则 整除关系且是正整数因子 x y z A 有y x n由 有z y m y z m并将其代入上式z x mn所以 具有传递性 是偏序关系 定义4 17一个集合A与A上的偏序关系R一起叫做偏序集 记作 如 集合A 2 3 6 8 上的 整除 关系 整数集合上的小于等于关系 R x y Z x y x Z R R是自反的又 R而 R 表示y x与关系R矛盾 R是反对称的又 x y t Z 若 R且 R则 R R是可传递的R是偏序关系 定义4 18设R是非空集合A上的偏序关系 对任意的x y A 如果偏序x y或者y x成立 则称x与y是可比的 如果x是偏序集 那么对 x A都有1 x 所以1和1 2 3 4 5都是可比的 但是2不能整除3 3也不能整除2 所以2和3是不可比的 对于1和2来说 1 2 并且不存在z A使得1整除z并且z整除2 所以2盖住1 同样 4盖住2 但4盖不住1 因为1 2 4成立 显然 如果x与y不可比 则一定不会有x盖住y或y盖住x 定义4 19设为偏序集 若对任意的x y A x和y都可比 即x y或y x 则称R为A上的全序关系 且称为全序集 例如 A 1 2 3 4 5 上的小于等于关系是全序关系 因为由前例知集合A上的小于等于关系是偏序关系 所以为偏序集 又因为对任意的x y A x y均可比较大小 即x y或y x所以是全序关系 而整除关系亦为偏序集 但对任意的x y A x y相互不能整除 所以不是全序关系 对于集合A上的任一全序 集合A中任意两个元素都是可比的 关于盖住概念的补充说明设为偏序集 a b A 若a b且不存在c A 使得a c b 则称b盖住a 例如在A 1 2 4 6 上的整除关系中 有哪些盖住关系呢 2盖住14盖住26盖住24不盖住16不盖住1Why 因为有1 2 41 2 6 偏序关系关系图的简化 哈斯图 Hassediagram 哈斯图的画法 在画偏序集的哈斯图时 首先适当排列A中元素的顺序 对于 x y A 若x y 则将x画在y的下方 其次考虑y是否盖住了x 若y盖住x 则用一条线段连接y和x 也就是说分以下两步 其中 表示偏序关系 若x y 且x y 则将x画在y的下面 若x y x y 并且没有不同于x y的z使得x z y 则在x y之间用直线连结 例4 49A 1 2 3 4 6 上的整除关系为R 画出的哈斯图 1 2 3 4 6 在画偏序集的哈斯图时 首先适当排列顶点的顺序使得 x y A 若x y 则将x画在y的下方 对于A中的两个不同元素x和y 如果y盖住x 就用一条线段连接x和y 例4 50设A a b a b a b c a b c d a b c e 画出的哈斯图 例4 51A 1 2 画出A的幂集P A 上的包含关系的哈斯图 P A 1 2 1 2 例4 52A 2 3 6 12 24 36 画出 整除 R的偏序集的哈斯图 解 A 1 2 3 1 2 2 3 R IA 1 2 2 3 1 2 3 例4 53已知偏序集的哈斯图如下所示 写出集合A和关系R的表达式 定义4 20设为偏序集 B A b B 若 x x B b x 为真 则称b为B的最小元 若 x x B x b 为真 则称b为B的最大元 若 x b x x b 为真 则称b为B的极小元 若 x b x b x 为真 则称b为B的极大元 从本定义可知 最小元与极小元是有区别的 最小元是B中最小的元素 它与B中其他元素都可比 而极小元不一定与B中元素都可比 只要没有比它小的元素 它就是极小元 对于有穷集B 极小元一定存在 且可能有多个 但最小元不一定存在 若存在则必唯一 若B中只有一个极小元 则它一定是B的最小元 类似地可讨论极大元与最大元之间区别 例4 54上述两个偏序集都有最小元 分别是1和 整除关系的偏序集没有最大元 包含关系的偏序集有最大元 a b c 凡是在哈斯图中向上路径的每一个终点都是极大元 上图中整除关系的偏序集有极大元7 8 9 10 11和12 包含关系的偏序集有唯一极大元 a b c 两个偏序集都有极小元 分别是1和 1 2 4 8 7 11 5 10 3 6 12 9 a b c a b a c b c a b c 作为最大元 最小元或极大元 极小元等要求元素本身在考查的集合中 而上界 下界则没有这一方面的要求 极大元是指在该集合中没有比它更大的 这是一种 局部 性质 并不意味着它是最大的 最大元则指比所有的都大 可以发生相等 这是一种 全局 性质 故最大元必定是极大元 例 找出下图中的最大元 最小元 极大元 极小元 a b c d e f g h 1 j k m n o p q r u v x y z w 2 3 图 1 中h为极大元 a b c为极小元 图 2 中o p q r为极大元 j为极小元 图 3 中z为极大元 u为极小元 图 1 图 3 有最大元h和z 图 2 图 3 有最小元j和u 最小 大 元与极小 大 元的区别 最小元是B中最小的元素 它与B中其它元素都可比 而极小元不一定与B中其它元素都可比 只要没有比它小的元素即可 极大元是指在该集合中没有比它更大的 这是一种 局部 性质 并不意味着它是最大的 最大元则指比所有的都大 可以发生相等 这是一种 全局 性质 故最大元必定是极大元 对于有穷集合B 最小 大 元不一定存在 但若存在则一定唯一存在 而极小 大 元一定存在 并且可能存在多个 若B中只有一个极小 大 元 则它一定是B的最小 大 元 定义4 21设为偏序集 B A b A 若 x x B b x 为真 则称b为B的下界 若 x x B x b 为真 则称b为B的上界 若b是一下界且对每一个B的下界b 有b b 则称b为B的最大下界或下确界 若b是一上界且对每一个B的上界b 有b b 则称b为B的最小上界或上确界 由本定义可知 B的最小元一定是B的下界 并且也是B的最大下界 但反之不一定正确 B的下界不一定是B的最小元 因为它可能不是B中的元素 类似地 讨论B的最大元与其上界的关系 B的上界 下界 最小上界 最大下界都可能不存在 若存在 最小上界和最大下界是唯一的 例4 55在上图整除关系的偏序集里 如果B 2 3 6 那么B的上界是6和12 最小上界是6 B的下界是1 最大下界也是1 在右上图中 令B c d e 则B的上界和最小上界都是e B的下界为a b 但B没有最大下界 1 2 4 8 7 11 5 10 3 6 12 9 f b c d a g h e 由此可见 B的最小 大 元一定是B的下 上 界 同时也是B的最大下 小上 界 反之则不一定成立 B的上界 下界 最小上界 最大下界都可能不一定存在 但若存在 最小界 最大下界一定是唯一存在的 例4 56求偏序集中 对于B1 1 2 3 4 5 6 B2 2 3 B3 5 的各极小元 极大元 最小元和最大元 解 B1中极小元 最小元都是1极大元是4 5 6 无最大元 B2中因为2和3不可比 故极小元是2和3 极大元也是2和3但都没有最小元和最大元 B3中极小元 极大元 最小元和最大元都是5 1 2 3 5 4 6 例4 57设有集合A 1 2 3 4 5 6 9 10 15 上的整除关系R B1 1 2 3 B2 3 5 15 B3 A求B1 B2 B3的最大元和最小元B1的最大元素是 B1的最小元素是 1 B2的最大元素是 15 B2的最小元素是 B3的最大元素是 B3的最小元素是 1 1 例4 58设有集合A 1 2 3 4 5 6 9 10 15 上的整除关系R B1 1 2 3 B2 3 5 15 B3 A求B1 B2 B3的极大元和极小元B1的极大元素是 2 3 B1的极小元素是 1 B2的极大元素是 15 B2的极小元素是 3 5 B3的极大元素是 4 6 9 10 15 B3的极小元素是 1 1 例4 59设有集合A 1 2 3 4 5 6 9 10 15 上的整除关系R B1 1 2 3 B2 3 5 15 B3 A 求B1 B2 B3的上界和下界B1的上界是 6 B1的下界是 1 B2的上界是 15 B2的下界是 1 B3的上界是 B3的下界是 1 1 例4 60设有集合A 1 2 3 4 5 6 9 10 15 上的整除关系R B1 1 2 3 B2 3 5 15 B3 A 求B1 B2 B3的上确界 最小上界 下确界 最大下界 B1的最小上界是 6 B1的最大下界是 1 B2的最小上界是 15 B2的最大下界是 1 B3的最小上界是 B3的最大下界是 1 1 总结 确定任一子集的最大 小 元 极大 小 元 极大 小 元 最大 小 元 界 从上述的例子我们可以看到 一个子集的极大 小 元可以有多个 而最大 小 元若有 只能惟一 且极大 小 元 最大 小 元只在该子集内 而上界与下界可在子集之外确定 最小上界是所有上界中最小者 最小上界再小也不会小于子集中的任一元素 可以与某一元素相等 最大下界也是同样 函数的定义和性质 一种特殊的二元关系设A和B是任意两个集合 且F是从A到B的关系 若对每一个x A 都存在唯一的y B 使 F 则称F为从A到B的函数 并记作F A B A称为函数F的定义域 即D F A B称为函数F的陪域 R F 称为函数F的值域 且R F B 有时也用F A 表示函数F的值域 即F A R F y y B x x A y F x 并称F A 值域 为函数F的像 4 6函数的定义和性质 函数的定义和性质 一种特殊的二元关系对于F A B来说 若 F 则称x为函数的自变元 称y为函数因变元 因为y值依赖于x所取的值 或称y是F在x处的值 或称y为F下x的像 通常把 F记作F x y 例 设F A BA x1 x2 x3 B y1 y2 y3 F1 F2 判断它们是否为函数 4 6函数的定义和性质 从函数的定义可以看出 从A到B的函数F和一般从A到