离散数学关系课件.ppt

1 第二章 关系 2 在现实生活中 集合与集合之间还存在着某种联系 如同学关系 朋友关系等 这些关系正是各门学科所要研究的主要内容 离散数学从集合出发 主要研究集合之间的关系 本章内容主要研究二元关系 3 本章主要内容 关系的基本概念关系的表示方法关系的运算关系的性质关系的闭包等价关系与划分偏序关系 4 2 1关系的基本概念 为了讨论关系 首先引入有序对和笛卡儿积两个概念 由两个元素a b组成的集合 a b 中 a和b是没有次序的 有时需要考虑有次序的两个元素 所以需要由两个元素组成新的东西 并且两个元素是有次序的 定义2 1两个元素a b有次序地放在一起 称为一个有序对或序偶 记为 a b 在有序对 a b 中 a称为第一元素 b称为第二元素 且 a1 b1 a2 b2 当且仅当a1 a2且b1 b2 5 定义2 2设A B是两个集合 集合 x y x A且y B 称为A和B的笛卡儿积 也称卡氏积 记为A B 用属于关系来表示就是 x y A B当且仅当x A且y B和 x y A B当且仅当x A或y B 其中A称为第一集合 B称为第二集合 6 例2 1设A 1 2 3 B a b 求A B 由笛卡儿积的定义可知有A A 又由有序对的性质可知 一般没有A B B A A B也是一个集合 所以可以和另一集合C作笛卡儿积 A B C 类似地有A B C 但是 一般没有 A B C A B C 且A B中的元素既不是A中的元素 也不是B中的元素 7 定理2 1如果B1 A1 B2 A2 则B1 B2 A1 A2 8 证明对 x y B1 B2 有x B1且y B2 又因为B1 A1 B2 A2 则x A1且y A2 所以 x y A1 A2 即B1 B2 A1 A2 9 定理2 2A B C是任意集合 则 1 A B C A B A C B C A B A C A 2 A B C A B A C B C A B A C A 3 A B C A B A C B C A B A C A 10 证明 1 对 x y A B C 有x A且y B C 因此x A且 y B或y C 当y B时 由x A和y B得 x y A B 当y C时 由x A和y C得 x y A C 所以 x y A B A C 即A B C A B A C 因为A A B B C和C B C得A B A B C 和A C A B C 因此 A B A C A B C 因此A B C A B A C 成立 同理可证 B C A B A C A 11 2 对 x y A B A C 有 x y A B且 x y A C 所以 x A且y B 且 x A且y C 由y B且y C得y B C 由x A且y B C得 x y A B C 因此 A B A C A B C 因为A A B C B和B C C 所以有A B C A B和A B C A C成立 因此A B C A B A C 因此A B C A B A C 同理可证 B C A B A C A 12 3 对 x y A B C 有x A且y B C 所以x A且y B且y C 由x A且y B得 x y A B 由y C得 x y A C 所以 x y A B A C 因此A B C A B A C 对 x y A B A C 有 x y A B且 x y A C 由 x y A B得x A且y B 由x A和 x y A C得y C 所以x A且y B且y C 由y B且y C得y B C 所以 x y A B C 因此 A B A C A B C 因此A B C A B A C 同理可证 B C A B A C A 13 定义2 3任给n 2 n个元素a1 an有次序地放在一起 称为一个n元有序组 记为 a1 an 为了体现n元有序组的次序 规定 a1 an b1 bn 当且仅当任给1 i n 都有ai bi n元有序组可以组成集合 特别地有n个集合的卡氏积 14 定义2 4任给n 2 A1 An是n个集合 集合 x1 xn 任给1 i n 都有xi Ai 称为A1 An的卡氏积 记为A1 An 任给1 i n Ai称为这个卡氏积的第i个集合 15 定义2 5如果一个集合满足以下条件之一 1 集合非空 且它的元素都是有序对 2 集合是空集 则称该集合为一个二元关系 记作R 二元关系也可简称为关系 对于二元关系R 如果 x y R 可记作xRy 如果 x y R 则记作xR y 设A B为集合 A B的任何子集所定义的二元关系叫做从A到B的二元关系 特别当A B时则叫做A上的二元关系 16 例2 2设集合A 0 1 B 1 2 3 那么R1 0 2 R2 A B R3 R4 0 1 等都是从A到B的二元关系 而R3和R4同时也是A上的二元关系 17 定义2 6笛卡尔积A1 A2 An的任意一个子集R称为A1 A2 An上的一个n元关系 当A1 A2 An A时 称R为A上的n元关系 定义2 7空集 上定义一个二元关系 简称空关系 若一个n元关系R本身是笛卡儿积A1 A2 An 则称R为全关系 用符号UA表示 即UA ai aj ai aj A 为A上的全关系 符号IA x x x A 为A上的恒等关系 18 例2 3设A 1 2 3 4 下面各式定义的R都是A上的关系 试用列元素法表示R 1 R x y x是y的倍数 2 R x y x y 2 A 3 R x y x y是素数 4 R x y x y 19 解 1 R 4 4 4 2 4 1 3 3 3 1 2 2 2 1 1 1 2 R 2 1 3 2 4 3 3 1 4 2 2 4 1 3 3 4 2 3 1 2 3 R 2 1 3 1 4 2 4 R UA IA 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 20 定义2 8R A B中所有的有序对的第一元素构成的集合称为R的定义域 记为domR 形式化表示为 domR x x A y B 使得 x y R R A B中所有有序对的第二元素构成的集合称为R的值域 记作ranR 形式化表示为ranR y y B x A 使得 x y R 21 定义2 9设R为二元关系 R的逆关系 简称R的逆 记作R 1 其中R 1 y x x y R 例2 4整除关系设A 2 3 4 8 B 3 4 5 6 7 定义从A到B的二元关系R a b R a整除b 则R 2 4 2 6 3 3 3 6 4 4 DomR 2 3 4 RanR 3 4 6 R 1 4 2 6 2 3 3 6 3 4 4 22 关系从本质上讲 仍是集合 只是这个集合中的元素都是以有序对的形式出现 既然关系是一个集合 那么集合的表示方法就可以用来表示关系 又因为关系是一个特殊的集合 其中的元素均以序偶的形式出现 除了可以用集合的表示方法外 还可以用其他的表示方法 这里主要介绍如下几种表示方法 2 2关系的表示方法 23 1 用列举法表示二元关系如果二元关系中的序偶个数是有限的 可以用列举法将其所包含的全部元素一一列举出来 例2 5设集合A 1 2 3 在集合A上定义的小于等于关系 LA a b a b A a b 则LA 1 1 1 2 1 3 2 2 2 3 3 3 24 2 用描述法表示二元关系用确定的条件表示某些序偶是否属于这个关系 并把这个条件写在大括号内表示关系的方法 格式是 LR x y x R且y R且x y 例2 6设A 1 2 3 4 下面两式定义的R1和R2都是A上的关系 分别列出R1与R2的元素如下 1 R1 x y x是y的倍数 2 R2 x y x y 2 A 25 解 1 R1 4 4 4 2 4 1 3 3 3 1 2 2 2 1 1 1 2 R2 2 1 1 2 3 1 1 3 2 3 3 2 4 2 2 4 3 4 4 3 26 3 用关系矩阵表示关系 定义2 10设A和B是两个有限集A a1 am B b1 bn R是从A到B的二元关系 称m n阶矩阵MR rij 为R的关系矩阵 其中rij 1 当且仅当 ai bj Rrij 0 当且仅当 ai bj R 27 例2 7例2 5中的关系R的关系矩阵为 例2 8例2 6中的关系R1与R2的关系矩阵分别为 28 4 用关系图表示二元关系 设A a1 an R是A上的二元关系 A中每个元素ai用一个点表示 称该点为顶点ai R的关系图是一个有向图 A中每个元素分别用一个顶点表示 当且仅当 ai aj R时 用弧或线段联结ai和aj 若 ai aj R 则在ai处画一条自封闭的弧线 其中1 i j n 这样表示R中关系的图形 称为R的关系图 用GR表示 29 例2 9设集合A 1 2 3 4 在集合A上定义关系R 1 1 1 2 2 3 2 4 4 2 则R的关系图如图2 1所示 30 关系R的集合表达式 关系矩阵MR 关系图GR三者均可唯一相互确定 31 定义2 11设关系R和S是从A到B的两个二元关系 对于a A b B 定义 1 R S a b R S a b R或 a b S 2 R S a b R S a b R且 a b S 3 R S a b R S a b R且 a b S 4 R a b R a b A B R 2 3关系的运算 32 例2 10设集合A a b c 集合B 1 2 且R和S是从A到B的两个二元关系 R a 1 b 2 c 1 S a 1 b 1 c 2 则R S a 1 b 2 c 1 b 1 c 2 R S a 1 R S b 2 c 1 R A B R a 2 b 1 c 2 33 因为关系可以用矩阵的形式表示 当我们用矩阵的形式求关系的并 交 补及对称差的运算时 可以用如下形式表示 MR S MR MS 矩阵的对应分量做逻辑析取运算 MR S MR MS 矩阵的对应分量做逻辑合取运算 MR S MR S MR MS MR M R 矩阵的对应分量做逻辑非运算 34 例2 11对例2 10中的关系的运算采用矩阵的形式表示如下 根据题意 关系R与S的关系矩阵分别表示为 则 35 定理2 3设关系R S是集合A到集合B的二元关系 则有下列性质成立 1 R 1 1 R R R 双重否定律 2 R 1 R 1 1 可换性 3 R S 1 R 1 S 1 分配律 R S 1 R 1 S 1 R S 1 R 1 S 1 4 S R S 1 R 1 单调性 S R S R 5 domR 1 ranR ranR 1 domR 6 A B 1 B A 36 证明 这里只证明 1 和 5 1 任取 x y 由逆的定义有 x y R 1 1 y x R 1 x y R 所以有 R 1 1 R 5 任取x x domR 1 y x y R 1 y y x R x ranR所以有domR 1 ranR 同理可证ranR 1 domR 37 合成关系 定义2 12设R是从集合A到集合B的二元关系 S是从集合B到集合C的二元关系 则R与S的复合关系 合成关系 R S是从A到C的关系 并且 R S x z x A且z C且存在y B使得 x y R y z S 运算 称为复合运算或合成运算 38 例2 12设A上的二元关系R x y x y A x是y的父亲 S x y x y A x是y的母亲 1 说明R R R 1 S 1 R 1 S的含义 2 表示以下关系 x y x y A y是x的外祖母 x y x y A x是y的祖母 39 解 1 R R表示关系 x y x y A x是y的祖父 R 1 S 1表示关系 x y x y A y是x的祖母 t A x t R 1 t y S 1 R 1 S表示空关系 2 x y x y A y是x的外祖母 表示为S 1 S 1 x y x y A x是y的祖母 表示为S R 40 例2 13设Z是整数集合 R S是Z到Z的两个关系 R x 3x x Z S x 5x x Z 计算R S S R R R S S R R R R S R 41 解R S x 15x x Z S R x 15x x Z R R x 9x x Z S S x 25x x Z R R R x 27x x Z R S R x 45x x Z 42 定理2 4R为定义在集合A上的关系 则R IA IA R R 43 证明任取 x y 有 x y R IA t x t R且 t y IA t x t R且t y x y R又有 x y R x y R且x y A x y R且 y y IA x y R IA所以 R IA R 同理可证IA R R 44 定理2 5设R1 A1 A2 R2 A2 A3 R3 A3 A4 则 1 R1 R2 R3 R1 R2 R3 2 R1 R2 1 R2 1 R1 1不满足交换律 即R1 R2 R2 R1 45 证明 1 任取 x y x y R1 R2 R3 t A3 使得 x t R1 R2且 t y R3 t A3 s A2 使得 x s R1且 s t R2 且 t y R3 t A3 s A2 使得 x s R1且 s t R2且 t y R3 s A2 使得 x s R1且 t A3 使得 s t R2且 t y R3 s A2 使得 x s R1且 s y R2 R3 x y R1 R2 R3 所以 R1 R2 R3 R1 R2 R3 46 由归纳法 任意n个关系的合成也是可结合的特别 当A1 A2 An 1 A且R1 R2 Rn R 合成关系R R R Rn是集合A上的一个关系 47 2 任取 z x R1 R2 1 则 x z R1 R2 由 的定义知 至少存一个y B 使得 x y R1 y z R2 即 y x R 11 z y R 12 由 z y R 12和 y x R 11 有 z x R 12 R 11 所以 R1 R2 1 R 12 R 11 反之 任取 z x R 12 R 11 由 的定义知 则至少存在一个y B 使得 z y R 12和 y x R 11 所以 x y R1 y z R2 由 知 x z R1 R2 即有 z x R1 R2 1 所以 R 12 R 11 R1 R2 1 由集合的性质知 R1 R2 1 R 12 R 11 48 例2 14设A a b c d e f R a a a b b c c d d e e f 求Rn n 1 2 3 4 49 解 R1 R R2 R R a a a b a c b d c e d f R3 R R R R2 R a a a b a c a d b e c f R4 R3 R a a a b a c a d a e b f R5 R4 R a a a b a c a d a e a f R6 R5 R a a a b a c a d a e a f R5 R7 R6 R R5 Rn R5 n 5 50 幂集Rn的基数 Rn 并非随着n的增加而增加 而是呈递减趋势 而且 当时 有 51 2 4关系的性质 有了关系的定义 可以来定义关系的某些特殊性质 这些性质在以后的讨论中 将起到极其重要的作用 本节主要讨论关系的五种性质 即自反性 反自反性 对称性 反对称性和传递性 52 自反 反自反 定义2 14设R为集合A上的二元关系 1 若对任意的x A 都有 x x R 则称关系R在集合A上是自反的或称关系R具有自反性 否则 称R是非自反的 2 若对任意的x A 都有 x x R 则称关系R在集合A上是反自反的或称关系R具有反自反性 自反关系 全关系 恒等关系 小于等于关系 整除关系 包含关系反自反关系 小于关系 真包含关系 53 例2 15设A 1 2 3 R1 1 1 2 2 R2 1 1 2 2 3 3 1 2 R3 1 3 说明R1 R2 R3是否为A上自反的关系 54 解 只有R2是A上自反的关系 因为IA R2 而R1和R3都不是A上的自反关系 因为 3 3 R1 所以R1不是自反的 而 1 1 2 2 3 3 都不属于R3 因此R3不是自反的 关系R是否为自反关系是相对集合A来说的 同一个关系在不同的集合上具有不同的性质 55 例2 16设A a b c d 在集合A上定义如下三个二元关系R S T分别如下 R a a a d b b b d c c d d S a b a d b c b d c a d c T a a a b a c b d c a c c d c 说明R S T在A上的自反性与反自反性 56 解 因为A中每个元素x 都有 x x R 所以R在A具备自反性 因为A中每个元素x 都有 x x S 所以S在A具备反自反性 因为A中有元素b 使 b b T 所以T在A上不具备自反性 因为A中有元素a 使 a a T 所以T在A上也不具备反自反性 任何不是自反的关系未必一定是反自反的关系 反之亦然 即存在既不是自反的也不是反自反的关系 57 定理2 6设R是定义在集合A上的二元关系 R是自反的当且仅当IA R 58 证明 1 必要性设R在A上是自反的 则IA R 根据恒等关系的定义 对任意的x A有 x x IA 又因为R在A上是自反的 即对于任意的x A有 x x R 因此IA R 2 充分性设IA R 则R在A上是自反的 对任意的x A有 x x IA 而IA R 因此对任意的x A有 x x R 即R在A上是自反的 59 定理2 7设R是定义在集合A上的二元关系 R是反自反的当且仅当R IA 60 证明 1 必要性设R在A上是反自反的 则R IA 假设R IA 比如存在 x y R IA 即 x y R且 x y IA 也即 x y R且x y 即 x x R 与R在A上是反自反的相矛盾 因此R IA 充分性设R IA 则R在A上是反自反的 对任意的x A 有 x x IA 由于R IA 因此 x x R 即R在A上是反自反的 61 对称 反对称 定义2 15设R为A上的关系 1 若对任意的x与y 都有x y A且 x y R 则有 y x R 则称R为A上对称关系 否则 称R是非对称的 2 若对任意的x与y 都有x y A且当 x y R y x R时 有x y 则称R为A上的反对称关系 对称 全关系 恒等关系 空关系反对称 恒等关系 空关系 62 例2 17设A a b c 定义A上的二元关系如下 R a a b b S a a a b b a T a c a b b a 试说明R S T是否是A上的对称关系和反对称关系 63 解 根据定义R上A上的对称关系与反对称关系 S是A上的对称关系 S不是A上的反对称关系 因为 a b 与 b a 都是S中的元素 但是a b 所以S不是A上的反对称关系 T既不是A上的对称关系 也不是A上的反对称关系 因为 a c 是T中的元素 但是 c a 不是T中的元素 因此不满足对称性 又因为 a b 与 b a 都是T中的元素 但是a b 因此也不满足反对称性 64 定理2 8设R是A上的二元关系 R是对称的当且仅当R R 1 65 证明 1 必要性设R是对称的 则R R 1 x y R y x R x y R 1 R R 1 2 充分性设R R 1 则R是对称的 x y R y x R 1 y x R 因此R是对称的 66 定理2 9设R是A上的二元关系 R是反对称的当且仅当R R 1 IA 67 证明 1 必要性设R是反对称的 则R R 1 IA x y R R 1 x y R且 x y R 1 x y R且 y x R 因为R是反对称的 根据反对称的定义 则x y 因此 x y y x x x IA 所以R R 1 IA 2 充分性设R R 1 IA 则R是反对称的 x y R且 y x R x y R且 x y R 1 x y R R 1因为R R 1 IA 所以 x y IA 顾x y 因此R是反对称的 68 传递 定义2 16设R为A上的关系 若对任意的x y z有x y z A且当 x y R y z R时 有 x z R 则称R是A上的传递关系 否则称R是非传递关系 传递关系 全关系 空关系 小于 包含 69 例2 18设A 1 2 3 R1 1 1 R2 1 3 2 3 R3 1 1 1 2 2 3 说明R1 R2 R3是否为集合A上传递的关系 70 解 根据定义2 16 R1 R2是A上传递的关系 但R3不是传递的 因为 1 2 R3 2 3 R3 而 1 3 R3 由传递关系的定义知R3不是传递的关系 71 定理2 10设R是集合A上的二元关系 则R是传递的当且仅当R R R 72 证明 1 必要性设R是传递的 则R R R 设 x y R R z A 使得 x z R且 z y R 因为R是传递的 所以 x y R 即有R R R 2 充分性设R R R 则R是传递的 x y R且 y z R 由复合关系的定义可得 x z R R 因为R R R 所以 x z R 即R是传递的 73 2 4 2关系性质的证明 在二元关系中 除了对一个具体的关系判断它具有哪些性质外 更多的是针对一个抽象的关系 利用它的特点来证明它具有某个性质 由于关系性质的定义全部都是按 如果 那么 来描述的 在证明这类问题时 一般采用按照定义证明的方法 这种证明问题的方法在于 证明时不能仅仅利用题目所给的已知条件 还要同时结合定义中的 已知 并且推出的并非整个定义 而是定义中的结论 另外 由于关系是特殊的集合 当用集合的手段来描述关系的性质时 其证明的方法也是按集合中的按定义证明方法来证 74 例2 19设R1 R2是定义在集合A上的两个关系 并且R1 R2具有传递性 则R1 R2也具有传递性 75 证明 对任意x y A 则若 x y R1 R2且 y z R1 R2 x y R1且 x y R2且 y z R1且 y z R2 x y R1且 y z R1 且 x y R2且 y z R2 又因为R1 R2具有传递性 因此 x y R1且 y z R1 且 x y R2且 y z R2 x z R1且 x z R2 x z R1 R2根据定义2 16 R1 R2具有传递性 76 关系性质与集合运算 77 2 5关系的闭包 对于在非空集合上定义的关系R不一定具备某种性质或某几种性质 而这些性质对研究某些具体的问题时又非常重要 这时就需要构造一个基于此关系的新关系 使其具备所需要的性质 即往该关系中添加一些适量的元素以改变原有关系的性质 得到新的关系 使得新关系具有所需要的性质 但又不希望新关系与R相差太多 也就是说 要尽可能少地来添加有序对 满足这些要求的新关系就称为R的闭包 本节介绍关系的自反 对称和传递闭包 78 定义2 17设R是非空集合A上的关系 R的自反 对称或传递 闭包是A上的关系Rc 使得Rc满足以下条件 1 Rc是自反的 对称的或传递的 2 R Rc 3 对A上任何包含R的自反 对称或传递 关系Rp有Rc Rp 一般将R的自反闭包记作r R 对称闭包记作s R 传递闭包记作t R 79 定理2 11设R为定义在非空集合A上的二元关系 则有 1 r R R IA 2 s R R R 1 3 t R R R2 R3 80 证明 1 令R R IA 则有 IA R IA 而R IA R 因此R 是自反的 R R IA 而R IA R 因此R R 假设R 是A上的任意自反关系并且R R 因为R 是自反的 所以IA R 因此有R R IA R 由自反闭包的定义 R R IA是R的自反闭包 即r R R R IA 81 2 令R R R 1 R 1 R R 1 1 R 1 R 1 1 R 1 R R R 1 R 因此R 是对称的 R R R 1 而R R 1 R 因此R R 设R 是A上的任意对称关系并且R R 又 x y R 1 y x R y x R 从而有R R R 1 R 因此R 是R的对称闭包 即s R R R 1 3 分两部分来证所要的结论 先证R R2 R3 t R 用数学归纳法来证 对任意自然数i 有Ri t R 当i 1时 由传递闭包的定义 R1 R t R 假设当i n时 Rn t R 下证Rn 1 t R 对任意的 x y Rn 1 存在c A 使得 x c Rn且 c y R 即存在c A 使得 x c t R 且 c y t R 则 x y t R 即Rn 1 t R 因此 R R2 R3 t R 再证明t R R R2 R3 显然 有R R R2 R3 成立 下证R R2 R3 是传递的 x y R R2 R3 t R 且 y z R R2 R3 t A 使得 x y Rt且 s A 使得 y z Rs x z Rt Rs Rt s R R2 R3 x z R R2 R3 由传递关系的定义 R R2 R3 是传递的 综上所述 R R2 R3 是包含R的传递关系 而R的传递闭包是包含R的最小传递关系 因此t R R R2 R3 即t R R R2 R3 成立 83 推论设R是有限集合A上的关系 A n 此时t R R R2 R3 Rn有 84 例2 20设集合A a b c R是A上的二元关系 且R a b b c c a 求出关系R的自反 对称和传递闭包 85 解 r R R IA a a b b c c a b b c c a s R R R 1 a b b c c a b a c b a c R2 a c b a c b R3 a a b b c c R4 a b b c c a 因此 有R R4R2 R5R3 R6 t R R R2 R3 R R2 R3 a a b b c c a b b c c a a c b a c b 86 例2 21设集合A a b c R是A上的二元关系 且R a b b c c a 用关系矩阵求关系R的自反 对称和传递闭包 87 解关系的关系矩阵为 88 定理2 12设R是非空集合A上的关系 1 若R是自反的 则s R 与t R 也是自反的 2 若R是对称的 则r R 与t R 也是对称的 3 若R是传递的 则r R 是传递的 而s R 不一定传递 证明 1 若R是自反的 则有IA R 又因为R s R 且R t R 所以IA s R 且IA t R 因此s R 与t R 是自反的 2 因为R对称 有R R 1 由于r R R IA 而 r R 1 R IA 1 R 1 IA 1 R IA r R 因此r R 对称 因为R对称 因此 Ri 1 R 1 i Ri 由于t R R R2 R3 于是 t R 1 R R2 R3 1 R 1 R2 1 R3 1 R R2 R3 t R 所以t R 也对称 90 3 因为R传递 所以R R R 而r R R IA 则有r R r R R IA R IA R R IA IA R IA R R RIA IA R IA R R R R IA R R R IA R IA r R 即r R 具有传递性 91 下面举一个反例来说明s R 不具备传递性 假设集合A 1 2 3 R 1 2 是定义在集合A上的且具有传递性 而s R 1 2 2 1 却不具备传递性 92 定理2 13设R1 R2 A A 且R1 R2 则r R1 r R2 s R1 s R2 t R1 t R2 93 证明 1 因为R1 R2 因此R1 IA R2 IA 所以r R1 r R2 反证法 假设 x y r R1 但 x y r R2 则r R1 x y 也是自反的 即x y 如果 x y R1 则 x y R2 那么 x y r R2 导致矛盾 因此 x y R1 所以R1 r R1 x y 那么r R1 不是R1的自反闭包 矛盾 因此 x y r R2 所以r R1 r R2 94 2 因为R1 R2 R2 s R2 因此R1 s R2 由s R1 是包含R1的最小对称关系 所以s R1 s R2 3 因为R1 R2 R2 t R2 因此R1 t R2 由t R1 是包含R1的最小传递关系 所以t R1 t R2 95 定理2 14设R1和R2是集合A上的关系 则以下各式成立 1 r R1 R2 r R1 r R2 2 s R1 R2 s R1 s R2 3 t R1 t R2 t R1 R2 96 证明 1 r R1 R2 IA R1 R2 IA R1 IA R2 r R1 r R2 2 s R1 R2 R1 R2 R1 R2 1 R1 R2 R 11 R 12 R1 R 11 R2 R 12 s R1 s R2 3 因为R1 R1 R2 R2 R1 R2 所以t R1 t R1 R2 t R2 t R1 R2 得出t R1 t R2 t R1 R2 一般地 t R1 t R2 t R1 R2 97 例2 22设集合A 1 2 3 R1 1 2 2 3 R2 3 2 有t R1 1 2 1 3 2 3 t R2 3 2 而t R1 R2 1 2 1 3 2 2 2 3 3 2 3 3 t R1 t R2 1 2 1 3 2 3 3 2 由此可见t R1 t R2 t R1 R2 98 定理2 15设R是集合A上的关系 则 1 rs R sr R 2 rt R tr R 3 st R ts R 99 证明 1 100 2 101 3 若R S 则显然有s R s S t R t S 根据对称闭包的定义 R s R 于是t R ts R st R sts R 若s R 对称 则ts R 也对称 所以 由 1 可得sts R ts R 即st R ts R 102 例2 23设A 1 2 R 1 2 求st R 与ts R 103 例2 23设A 1 2 R 1 2 求st R 与ts R 解 st R s t R s 1 2 1 2 2 1 ts R t s R t 1 2 2 1 1 2 2 1 1 1 2 2 104 2 6等价关系与划分 在日常生活中或者在数学等学科中 常常需要对某个集合上的元素按照某种方式进行分类 即集合的划分 这是一个非常重要的而且应用十分广泛的概念 集合的划分与一种重要的关系 等价关系密切相关 利用等价关系 可以将集合中的元素分类 将一个大的集合分成若干个等价类 其主要意义在于它证实了应用抽象的一般原理的正确性 即在某方面等价的个体产生等价类 对全体的等价类进行分析常常比对全体本身进行分析更简单 105 2 6 1等价关系 定义2 18设R为非空集合A上的关系 如果R是自反的 对称的和传递的 则称R为A上的等价关系 设R是一个等价关系 若 x y R 称x等价于y 记做x y 106 例2 24以下关系是等价关系 1 集合A上的恒等关系 全域关系是等价关系 2 三角形的全等关系 三角形的相似关系是等价关系 3 在一个班级里 年龄相等 的关系是等价关系 107 例2 25设关系R是定义在有理数集Q上的关系 并且 x y R 当且仅当x y是整数 试证R是等价关系 108 例2 25设关系R是定义在有理数集Q上的关系 并且 x y R 当且仅当x y是整数 试证R是等价关系 证明 1 自反性 对任意一个有理数x Q 有x x 0是整数 即对所有的有理数有 x x R 因此R满足自反性 2 对称性 假设x y Q 并且 x y R 即x y是整数 则y x x y 也是整数 即 y x R 因此R满足对称性 3 传递性 假设x y z Q 并且 x y R y z R 即x y与y z都是整数 则x z x y y z x y y z 也是整数 即 x z R 因此R满足传递性 所以 R是等价关系 109 例2 26设集合A a b c d R a a a d b b b c c b c c d a d d 试证R是A上的等价关系 110 证明 写出关系R关系矩阵如下 由关系矩阵可以看出 该矩阵的主对角线的元素都是1 即关系R满足自反性 该关系矩阵是对称的 即R满足对称性 求出R2的关系矩阵为 即R2的关系矩阵与R的关系矩阵相同 并且有R3 Rn都与R的关系矩阵相同 因此 t R R R2 R3 Rn的关系矩阵也与R的关系矩阵相同 所以R是传递的 综上所述 R是A上的等价关系 111 例2 27设A 1 2 8 定义A上的关系R x y x y A且x y mod3 其中x y mod3 叫做x与y模3相等 即x除以3的余数与y除以3的余数相等 试证R为A上的等价关系 112 证明 R 1 4 4 1 1 7 7 1 2 5 5 2 2 8 8 2 3 6 6 3 IA因为IA R 因此R满足自反性 对x y A 若 x y R 即x ymod3 则有y xmod3 即 y x R 因此R满足对称性 对x y z A 若 x y R y z R 即x ymod3 y zmod3 则有x zmod3 即 x z R 因此R满足传递性 综上所述 R是等价关系 113 定理2 16设R是定义在集合A上的关系 则R为等价关系 R R 1 R 114 定理2 16设R是定义在集合A上的关系 则R为等价关系 R R 1 R 证明 1 必要性 R为等价关系 R R 1 R令x y是集合A中的任意元素 且 x y R 则 x y R x y R且 y x R x y R且 y x R 1 z 使得 x y R且 z y R 1 x y R R 1于是 R R R 1 另一方面 x y R R 1 z使得 x z R且 z y R 1 x z R且 y z R x z R且 z y R x y R因此 R R 1 R 综上可知 必要性得证 2 充分性 由假设R R 1 R可知 x y R x y R R 1 z使得 x z R且 z y R 1 z使得 x z R且 z y R由此可推知R为对称和传递时方使上式成立 从而R也必为自反 充分性得证 115 定义2 19设R为集合A上的等价关系 对集合A中的任意元素a 称A中与a等价的全体元素所组成的集合为由a生成的等价类 记作 a R 即 a R b b A且 a b R a称为这一等价类的代表元或生成元 116 例2 28设A 1 2 8 如下定义A上的二元关系R x y x y A且x y mod3 其中x y mod3 叫做x与y模3相等 求R的等价类 117 解 1 R 1 4 7 2 R 2 5 8 3 R 3 6 4 R 1 4 7 5 R 2 5 8 6 R 3 6 7 R 1 4 7 8 R 2 5 8 即 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 所以不同的等价类只有3个 1 R 2 R 3 R 118 定义2 20设R为非空集合A上的等价关系 以R的所有等价类作为元素的集合称为A关于R的商集 记做A R 即 A R a R a A A R的基数 即不同类的个数 称为R的秩 119 例2 29在例2 28中的商集为A R 1 4 7 2 5 8 3 6 关系R的秩为3 120 例2 30整数集Z上模m的等价关系R x y x y Z且x y mod m 其等价类是 0 R km k Z 1 R km 1 k Z m 1 R km m 1 k Z 因此商集为Z R 0 R 1 R m 1 R 121 定理2 17设R为非空集合A上的等价关系 则 1 a A a R是A的非空子集 2 a b A 如果 a b R 则 a R b R 3 a b A 如果 a b R 则 a R b R 4 a R a A A 122 证明 1 a A 由R的自反性 有 a a R 所以a a R 因此 a R非空 再由等价类定义 a R A 2 对于 x a R 则 a x R 又因为 a b R 由R的对称性与传递性 可得 b x R 于是x b R 因此 a R b R 同样可证 b R a R所以 a R b R 3 反证法 如果有元素x a R b R 则 a x R且 b x R 由R的对称性和传递性 可得 a b R 与 a b R矛盾 所以 a R与 b R不交 123 4 先证 a R a A A任取b b a R a A a使得a A且b a R b A 因为 a R A a R a A A再证A a R a A 任取b b A b b R b a R a A A a R a A 成立 综上所述得 a R a A A 124 2 6 2集合的划分 定义2 21 设A是任意非空集合 A1 A2 Am是集合A的子集 满足 1 Ai i 1 2 m 2 Ai Aj i j 3 A1 A2 Am A 则集合族 A1 A2 Am 为A的一个划分 而A1 A2 Am为这个划分的划分块 125 例2 31设集合A 1 2 3 4 则 1 1 2 3 4 2 1 2 3 4 3 1 2 3 4 4 1 2 3 4 均为对集合A的划分 例2 32设集合A a b c d 判断下列子集是否是A的划分 1 a b c d b d 2 a b c d 3 a b c 4 a b c d 5 a b c d 解 根据划分的定义有 1 3 不是A的划分 2 4 5 是A的划分 126 细分 真细分 定义2 22设 1 A1 A2 An 和 2 B1 B2 Bm 是集合S的两种划分 如果 1中的每个Ai都是 2中某个Bj的子集 则称划分 1是划分 2的一个细分 如果 1是 2的细分 且 1中至少有一个Ai是某个Bj的真子集 则称 1是 2的真细分 127 例2 33设集合A 1 2 3 4 则在例2 31中 1 划分 1 1 2 3 4 是 2 1 2 3 4 的细分 也是真细分 2 划分 3 1 2 3 4 是 4 1 2 3 4 的细分 也是真细分 对集合A 1 2 3 4 有 1 1 2 3 4 是对集合A的任意一个划分的细分 而对集合A的任意一个划分都是划分 4 1 2 3 4 的细分 128 最大划分 最小划分 交叉划分 定义2 23设A是非空集合 G a a A 称为A的最大划分 S A 称为A的最小划分 例2 34在例2 31中的划分 1 1 2 3 4 是对集合A的最大划分 划分 4 1 2 3 4 是对集合A的最小划分 129 最大划分 最小划分 交叉划分 定义2 24设 1 A1 A2 An 和 2 B1 B2 Bm 是集合S的两种划分 称 Ai Bj Ai Bj 1 i n 1 j m 为 1和 2的交叉划分 例2 35设集合A 1 2 3 4 则在例2 31中的划分 2 1 2 3 4 与划分 3 1 2 3 4 的交叉划分为 2 3 1 2 3 4 130 定理2 18 设 1 A1 A2 An 和 2 B1 B2 Bm 是集合S的两种划分 则其交叉划分 1 2也是S的一个划分 131 证明交叉划分 Ai Bj Ai Bj 1 i n 1 j m 在 中任取两个元素Ai Bh Aj Bk 考察 Ai Bh Aj Bk 是否满足集合划分定义中的三个条件 1 若i j且h k 由于Ai Aj 则Ai Bh Aj Bk 2 若i j且h k 由于Ai Aj Bh Bk 则Ai Bh Aj Bk 3 若i j且h k 由于Bh Bk 则Ai Bh Aj Bk 由此可见 在交叉划分中 任意两个元素的交集均为 且有交叉划分中所有元素的并集为 132 A1 B1 A1 B2 A1 Bm A2 B1 A2 B2 A2 Bm An B1 An B2 An Bm A1 B1 B2 Bm A2 B1 B2 Bm An B1 B2 Bm A1 A2 An B1 B2 Bm S S S因此交叉划分 1 2也是S的一个划分 133 定理2 19 任何两种划分的交叉划分 都是原来各自划分的一个细分 134 证明设 Ai Bj Ai Bj 1 i n 1 j m 为 1 A1 A2 An 和 2 B1 B2 Bm 的交叉划分 对 中的任意元素Ai Bj 都有Ai Bj Ai与Ai Bj Bj成立 因此 是原来各自划分的一个细分 135 2 6 3划分与等价关系 比较某集合A的划分与A的等价关系的商集的定义 可以发现 一个划分就是一个等价关系 136 例2 36设集合A 1 2 3 求出A上所有的等价关系 137 例2 36设集合A 1 2 3 求出A上所有的等价关系 解 写出A上所有的划分如图2 2所示 即可找出它们所对应的等价关系 图2 2集合A的五种划分 138 A的不同划分只有图2 2所示的五种 设对应于划分 i i 1 2 5 的等价关系为Ri 则有R1 1 1 2 2 3 3 1 2 2 1 1 3 3 1 2 3 3 2 R2 1 1 2 2 3 3 2 3 3 2 R3 1 1 2 2 3 3 1 3 3 1 R4 1 1 2 2 3 3 1 2 2 1 R5 1 1 2 2 3 3 139 例2 37设A 1 2 3 4 5 A上的二元关系R中 有多少个是等价关系 140 解 对于A的划分可分为如下几种情况 1 划分成5个都只含1个元素的块 共有1种 2 划分成1个都只含2个元素 3个都只含1个元素的块 共有10种 3 划分成2个都只含2个元素 1个都只含1个元素的块 共有15种 4 划分成1个都只含3个元素 2个都只含1个元素的块 共有10种 5 划分成1个都只含3个元素 1个都只含2个元素的块 共有10种 6 划分成1个都只含4个元素 1个都只含1个元素的块 共有5种 7 划分成1个都只含5个元素的块 共有1种 综上所述 A上的等价关系共有1 10 15 10 10 5 1 52 141 定理2 20 设 是集合A的划分 R是A上等价关系 那么 对应 的等价关系为R 当且仅当R对应的划分为 142 证明 证A 时 只有 划分和等价关系 结论显然成立 下设A 1 必要性设对应 的等价关系为R R对应的划分为 欲证 为此对任一元素a A 设B B 分别是 中含a的单元 那么 对A中任一元素b 有b B a b R R是对应的等价关系 b a R b B 是R对应的划分 这就是说B B 由于a是A中任意元素 故可断定 143 充分性设R对应的划分为 对应的等价关系为R 欲证R R 为此考虑A中任意元素a b a b R b a R B 使得B 且 a R B且b B 为R对应的划分 B 使得B 且a B且b B a b R R 为 对应的等价关系 故R R 144 2 7偏序关系 偏序关系是另一种特殊的关系 它是一个集合上的传递关系 提供了一种对集合的元素进行比较的方法 虽然有的次序关系不一定能对任意二元素进行比较 因此 在关系理论中 最早研究的对象就是属于次序关系 145 2 7 1偏序的定义及表示 定义2 25设R为非空集合A上的关系 如果R是自反的 反对称的和传递的 则称R为A上的偏序关系 记作 集合A与集合A上的偏序关系一