离散数学ppt课件.ppt

二元关系的性质 设R是A上的关系 R的性质主要有以下5种 自反性反自反性对称性反对称性传递性 1 二元关系的性质 设 是 上的二元关系 rij n n 1 自反性 对 则 称为自反的二元关系 显然 rii 1 n 反自反性 对 则 称为反自反的二元关系 即rii n 2 注 自反和反自反性互斥 但不互补 如 rii中既有0又有1 则R既不是自反的也不是反自反的 对应于关系图 自反性 每个顶点都有自回路反自反性 每个顶点都没有自回路 3 2 对称性 若 必有 称 为对称的二元关系即 的关系矩阵为对称阵 ij ji 关系图对称性 任二个顶点间或没有边 或有二条方向相对的有向边 例2 4 2 4 反对称性 若 则 称 为反对称的二元关系 注意 1 的相关矩阵是反对称的 即 rij rji 2 若rij 则rji 但rij 时 不要求rji 即rij rji 是允许的 3 对称性与反对称性既不互斥 又不互补 关系图 任二个顶点至多只有一条有向边 例2 4 3 5 6 注 rij rjk中有一个不是 则 1 rik就可以任意 即若 b c 中有1个不属于R 则讨论 a c 是否属于R 无意义 即没有传递的条件 就不需讨论传递的结果 如 a b c d 7 传递性 若 到 有边 到 有边 则 到 必有边 8 二元关系的性质对应于关系图 有 1 自反性 每个顶点都有自回路 2 反自反性 每个顶点都没有自回路 3 对称性 任二个顶点间或没有边 或有二条方向相反的有向边 4 反对称性 任二个顶点至多只有一条有向边 也即 或没有边 或只有一条有向边 5 传递性 若 到 有边 到 有边 则 到 必有边 9 10 定理2 4 1设R是集合A上的二元关系 则 1 是自反的当且仅当I 2 是对称的当且仅当 1 3 是反对称的当且仅当 1 I 4 是传递的当且仅当 11 例 分析集合A 1 2 3 上的下述四个关系 判断是否自反 对称 反对称 传递 1 R 1 1 1 2 1 3 3 3 反对称 可传递 2 S 1 1 1 2 2 1 2 2 3 3 自反 对称 可传递 3 T 1 1 1 2 2 2 2 3 反对称 4 A A自反 对称 可传递 12 判断A上关系的性质 全域关系自反的 对称的和传递的恒等关系自反的 对称的和传递的整除关系自反的 反对称的和传递的小于等于关系自反的 反对称的和传递的幂集上的包含关系自反的 反对称的和传递的 13 举出A 1 2 3 上关系R的例子 使其具有下述性质 A 既是对称的 又是反对称的 B R既不是对称的 又不是反对称的 C R是可传递的 解 A R 1 1 2 2 3 3 B R 1 2 2 1 2 3 C R 1 2 2 1 1 1 2 2 3 3 14 设R1 R2是A上的关系 如果经过某种运算后仍保持原来的性质 则划 否则划 15 例 设R1 R2为A上的对称关系 证明R1 R2也是A上的对称关系 证明 对于任意的 R1 R2 R1 R2 R1 R2 R1 R2所以 R1 R2在A上是对称的 16 作业 设X 1 2 3 4 R是X上的二元关系 R 1 1 1 2 1 3 3 1 3 2 3 3 4 1 4 2 4 3 1 画出R的关系图 2 写出R的关系矩阵 3 说明R是否是自反 反自反 对称 传递的 17 关系的闭包 定义 设R是非空集合A上的关系 R的自反闭包 对称闭包或传递闭包 是A上的关系R 且R 满足以下条件 1 R 是自反的 对称的或传递的 2 R R 3 对A上的任何包含R的自反关系 对称或传递关系 S都有R S 即满足 1 2 的最小者 一般将R的自反闭包reflexive记作r R 对称闭包symmetric记作s R 传递闭包transitive记t R 18 教材P43例2 5 1例 设A a b c d R 则R和r R s R t R 的关系图如图所示 例P43 19 A上关系R的闭包 定理2 5 2设R为A上的二元关系 则 1 r R I R 2 s R R R 1 3 t R R R2 R3 4 A是含有n个元素的集合t R R R2 R3 Rn闭包的矩阵表示 20 例 设A a b c d R 则r R s R t R 有解 1 r R I R 2 s R R R 1 21 3 t R R R2 R3 R4 R4 22 闭包的矩阵表示 Mr M EMs M M Mt M M2 M3 其中E表示同阶的单位矩阵 主对角线元素为1 其他元素都是0 M 表示M的转置 而 均表示矩阵中对应元素的逻辑加 即 或运算 Mt中的幂数不超过集合A中的元素数 23 在上例中3个结果矩阵是 24 求传递闭包 Warshall算法 设集合基数为n 构造n 1个矩阵W0 W1 W2 Wn W0为t R 的关系矩阵 Wn即为t R 的关系矩阵 1 令W0 MR 2 设Wi 1已求出 现求Wi考虑Wi 1的第i列 列中为1的元素分别位于P1 P2 行 同时考虑第i行 该行中为1的元素位于q1 q2 列 则 把Wi中第PS行qt列的元素改为1 3 重复 2 过程 直到求出Wn 4 根据Wn写出t R 见书上例2 5 3 25 定理2 5 3设A为集合 R1 R2 A A 若R1 R2则 1 r R1 r R2 2 s R1 s R2 3 t R1 t R2 等价关系 26 作业 1 集合A 1 2 10 上的关系R x y x y 10 x A y A 则R的性质为 A 自反的B 对称的C 传递的 对称的D 反自反的 传递的2 设A a b c 上的关系如下 有传递性的有 A P1 a c c a a b b a B P2 a c c a C P3 a b c c b a b c D P4 a a 27 3 设集合A a b c d 上关系R a b a c d c b c c d 1 用矩阵运算求出R的自反 对称 传递闭包 2 用warshall算法 求出R的传递闭包 28 2 6等价关系 定义1 等价关系 上的二元关系 如果 是 1 自反的 2 对称的 3 传递的称 为等价关系 称 与 等价 记作 29 恒等关系 全关系 三角形的全等关系以及三角形的相似关系均为等价关系 例 设集合A 1 2 3 4 R 1 1 1 4 4 1 4 4 2 2 2 3 3 2 3 3 验证关系R是A上的等价关系 30 例 设R为计算机系所有学生构成的集合上的 同住一个宿舍关系 则R为等价关系 31 例2 6 2A 1 2 8 R x y A x y mod3 其中x y mod3 的含义就是x y可以被3整除 R为A上的等价关系 它的关系图如下所示 32 把模3的等价关系推广 设Z为整数集合 取一个固定的整数m 0 规定Z的元素间的一个关系R a b R当且仅当m a b 这个关系称为模m的同余关系 我们用a b modm 来表示 同余关系为等价关系 33 定义2 6 2若把一个非空集合A分成若干个叫做类的子集 使得A的每个元素属于而且只属于一个类 那么这些类的全体叫做集合A的一个分类 或划分 A1 A2 A3 A4 34 定理2 6 1集合A上的一个等价关系R决定A的一个分类 定理2 6 2集合A上的一个分类决定A上的一个等价关系 例 设集合A中有4个元素 则A上的不同的等价关系的个数为 A 12个B 14个C 15个D 17个 35 等价类 设R为集合A上的等价关系 对任何a A 称集合 a R x x A xRa 为a关于R的等价类 a称为 a R的代表元素 等价类 a R是所有与a具有R关系的元素构成的集合 设A 1 2 3 4 5 R是A上的 模3同余 关系 求其等价类 解 R 1 1 1 4 4 1 4 4 2 2 2 5 5 2 3 3 5 5 A上关于R有三个等价类 1 R 1 4 4 R 2 R 2 5 5 R 3 R 3 36 例 设N是自然数集合 定义N上的二元关系R R x y x N y N x y是偶数 证明R是一个等价关系 37 等价类的性质 定理设R是非空集合A上的等价关系 对任意的x y A 下面的结论成立 1 任取x A x R 2 若x y A 或者 x R y R 或者 x R y R 3 A 38 商集 定义2 6 3设R为集合A上的等价关系 以R的所有的等价类为元素的集合叫做A关于R的商集 记作A R A R x A 在上例中 A在R下的商集是A R 1 2 3 1 4 2 5 3 39 在整数集合z上关于模m同余的等价关系 其等价类是 0 0 m 2m mz z Z mZ 1 1 m 1 2m 1 mz 1 z Z mZ 1 2 2 m 2 2m十2 mz 2 z Z mZ 2 m 1 m 1 m m 1 2m m 1 mz m 1 z Z mZ m 1 商集为 0 1 m 1 40 例2 6 6设A 1 2 3 求出A上所有的等价关系 解 先求A的各种划分 只有1个划分块的划分 1 具有两个划分块的划分 2 3和 4 具有3个划分块的划分 5 请看下图 41 设对应于划分 i的等价关系为Ri i 1 2 5 则有R1 1 2 1 3 2 1 2 3 3 1 3 2 IA EA R2 2 3 3 2 IA R3 1 3 3 1 IA R4 1 2 2 1 IA R5 1 1 2 2 3 3 IA 42 2 7偏序关系 定义2 7 1设R为集合A上的二元关系 如果R是自反的 反对称的和传递的 则称R是A上的偏序关系 简称偏序 记作 具有偏序关系的集合A称为偏序集 记作 A 例 判断下列集合是否是偏序集合 a I 其中 是整数集合上的小于等于关系 b P A 其中 是集合上的包含关系 c I 其中 是整除关系 d I 其中 是小于关系 43 设 A 为偏序集 对于任意的x y A可比 如果x y或者y x成立 则称x与y是可比的 盖住 覆盖关系 如果x y x y 且不存在z A使得x z y 则称y盖住x 并且记COVA x y x y A y盖住x 例1 设A 2 3 6 12 24 36 是A上的整除关系 COVA COVA 2 6 3 6 6 12 12 24 12 36 例2 集合A a b c 偏序集合 P A 中 判断A的以下子集是否盖住 a 1 2 b c 3 a b 4 a b c 44 偏序关系的图形表示 哈斯图 哈斯图画法如下 1 用小圆圈代表元素 2 如果x y且x y 则将代表y的小圆圈画在代表x的小圆圈之上 3 如果 x y COVA 则在x与y之间用直线连接 练习 A a b 画出偏序集合 P R 的哈斯图 45 画偏序集的哈斯图 46 例如 画A a b c P R 的哈斯图 47 例 设偏序集的哈斯图如图所示 求出集合A的偏序 解A a b c d e f g h a c a d a e b c b d b e c e d e f g IA e c d a b g f h 48 最大元 最小元 极大元 极小元 设 A 为偏序集合 B A 最大元 如果a B 若 x B 都有x a 则称a为集合B的最大元 最小元 如果a B 若 x B 都有a x 则称a为集合B的最小元 极大元 若 x B 且由a x可推出a x 则称a为B的极大元 极小元 若 x B 且由x a可推出x a 则称a为B的极小元 区别见P57 49 上界 下界 上确界 下确界 定义2 7 4设为偏序集 B A B a A 1 若 x B 都有x a 则称a为B的上界 2 若 x B 都有a x 则称a为B的下界 3 若a是B的上界 且对B的任意上界b均有a b 则称a为B的最小上界或上确界 4 若a是B的下界 且对B的任意下界b均有b a 则称a为B的最大下界或下确界 例2 7 6 50 1 对于有穷集 极小元和极大元一定存在 还可能存在多个 2 最小元和最大元不一定存在 如果存在一定唯一 3 最小元一定是极小元 最大元一定是极大元 4 孤立结点既是极小元 也是极大元 最小元 最大元 极小元 极大元具有下述性质 51 上界 下界 最大上界与最小上界存在下述性质 1 下界 上界 最大下界 最小上界不一定存在 2 如果下界 上界存在 也不一定是唯一的 3 最大下界 最小上界如果存在 则是唯一的 4 子集B的最小元就是它的最大下界 最大元就是它的最小上界 反之不对 最大下界 最小上界可能不在集合B中 52 例 整数集上的整除关系不是全序关系 但大小关系是全序关系 集合 a a b a b c a b c d 上的包含关系就是全序关系自然数集N大小元关系是良序集 53 作业 设集合P x1 x2 x3 x4 x5 上的偏序关系如图 找出P的最大元 最小元 极大元 极小元 找出 x2 x3 x4 x3 x4 x5 和 x1 x2 x3 的上界 下界 上确界 下确界 x2 x4 x3 x5 x1 54 2 8映射 定义2 8 1设A B是任意两个非空集合 f A B 若对于A中的每个元素a都存在唯一的元素b B 使 a b f 则称f为A到B的映射 函数 x为y在f下的原象 y为x在f下的象 集合A称为定义域 记作Domf 即Domf A 而f A f a a A 称为f的值域 记作Ranf 由定义有Ranf B 55 例 设A x1 x2 x3 B y1 y2 如下关系F1 x1 y1 x2 y1 x3 y2 是不是映射 是映射F2 x1 y1 x1 y2 x2 y1 x3 y2 呢 不是映射 因为对于x1 domF有x1Fy1 x1Fy2同时成立 56 例 判断下列关系中哪些能构成映射 函数 a f x1 x2 x1 x2 N x1 x2 10 b f y1 y2 y1 y2 R y22 y1 c f y1 y2 y1 y2 N y2 y12 1 定义2 8 2设函数f A B g C D 如果A C B D 且对所有x A和x C 都有f x g x 则称函数f等于函数g 记为f g 57 特殊映射 定义2 8 4设映射f A B 1 若ranf B 则称f是满射的 2 若对于任何的x1 x2 A x1 x2 都有f x1 f x2 则称f是单射的 3 若f既是满射的 又是单射的 则称f是双射或一一对应的 例 判断下列函数的类型 a s N N s n n 1 b h R R h x x3 2x2 c a b R且a b g 0 1 a b g x b a x a a 中s是单射非满射 b 中h是满射非单射 c g是双射 58 例如 函数f 1 2 0 f 1 f 2 0 那么f是满射的 但不是单射的 函数f N N f x 2x是单射的 但不是满射的 因为ranf不含有奇数 即ranf N 而函数f Z Z f x x 1是双射的 59 定理设f是从集合X到Y的映射 1 若f是满射的 则必有 X Y 2 若f是单射的 则必有 X Y 3 若f是双射的 则必有 X Y 4 若 X Y 则有f是单射的当且仅当f是满射的 例 设x和y都是有限集合 且有 x m y n 问x到y上有多少个不同的映射 函数 f x1 x2 xm 共有nm种不同的函数 例2 8 9 60 2 9复合映射与逆映射 定理设f A B g B C为两个映射 则f与g的复合映射gf是一个从A到C的映射 即 gf a g f a a A 或用集合表示为gf a c 存在b B使 a b f b c g 61 例 设R为实数集 R到R的映射定义为 f x x 2 g x x 2 h x 3x 则gf x g x 2 x 2 2 xfg x f x 2 x 2 2 xff x f x 2 x 2 2 x 4gg x g x 2 x 2 2 x 4 fgh x fg h x fg 3x f 3x 2 3x 62 定理2 9 1 设f A B g B C h C D均为映射 则h gf hg f 63 逆映射 定理设f A B是双射 则f 1是从B到A的双射 称f 1是f的逆映射 例 设A 1 2 3 B a b c f A B是映射 f 1 a 2 c 3 b 求f 1解 f 1 a 1 c 2 b 3 定理设双射函数f A B 有逆映射f 1 B A 则有 1 f 1 1 f 2 f 1 f IA 3 f f 1 IB 64 定义2 9 2设g x y和h x y是映射 若h g Ix 则称h是g的左逆映射 g是h的右逆映射 见教材P65 定理2 9 2设f A B是映射 则 1 f左可逆f是单射 2 如果f右可逆f是满射 如果f是双射映射 那么f 1 f Ix且f f 1 Iy 因此f 1既是f的左逆 又是f的右逆 例P652 9 3 65 定理2 9 3设f A B g B C为映射 则 1 若f g都是满射 则gf也是满射 2 若f g都是单射 则gf也是单射 3 若f g都是双射 则gf也是双射 定理2 9 4设f A B g B C为映射 则 1 若gf是满射 则g是满射 2 若gf是单射 则f是单射 3 若gf都是双射 则f是单射 g是满射 66 本章重点 集合的笛卡尔积与二元关系关系的运算和关系的性质关系的闭包等价关系和偏序关系映射的定义和性质及映射的复合和逆映射单射 满射 双射 67 1 指出下图中各关系是不是映射 并说明理由 68 2 设X a b c d Y 1 2 3 f a 1 b 2 c 3 则下面命题中唯一正确的是 A f是从X到Y的二元关系 但不是从X到Y的函数B f是从X到Y的函数 但不是满射 也不是单射C f是从X到Y的满射 但不是单射D f是从X到Y的双射3 下列各关系中具有自反性和对称性的关系是 A R1是自然数集合N上的关系 且xR1y当且仅当x y是偶数B R2是自然数集合N上的关系 且xR2y当且仅当x y或y xC R3是自然数集合Q上的关系 且xR3y当且仅当y x 2B R4是自然数集合N上的关系 且xR4y当且仅当x y 4 69 4 A 1 2 3 B 4 5 6 8 R与S是从A到B的关系 且XRY当且仅当gcd x y 1 即x与y的最大公约数等于1 xRy当且仅当x y为偏序集 其中A 1 2 3 4 6 9 24 54 R是A上的整除关系 1 画出的哈斯图 2 求A中的极大元 3 令B 4 6 9 求B的上确界和下确界 6 设A a b c R 1 给出R的关系矩阵 2 说明具有的性质 自反性 反自反性 对称性 反对称性 传递性 70 7 考虑下列实数集上的函数 f x 2x2 1 g x x 7 h x 2x k x sinx求g f f g f f g g f h f k k h的解析式 71 第3章集合的基数 72 集合的基数 希尔伯特饭店 无穷饭店 关于无穷大悖论的故事 无穷饭店 是我们银河系中心的一家巨大的旅馆 它拥有无穷多个房间 这些房间通过黑洞伸展到更高级的时空领域 房间号从1开始 无限制地排下去 旅店每个房间恰能住一位旅客 并已经客满 当日又有一位旅客投宿 店主欣然接纳 希尔伯特 1862 1943 1 2 3 73 无穷集的概念定义3 1 1设A B为两个集合 如果存在A到B的一个双射函数f A B 则称A与B等势 等基数 记作A B例 对集合A和B 构造一个从A到B的双射 以说明A和B具有相同的势 1 A 0 1 B 0 2 f A B 使得f x 2x x A 2 A R B 0 f A B 使得f x ex x R 3 A 0 1 B 1 4 1 2 f A B 使得f x 1 4 x 1 2 x 0 1 74 有限集与无限集 定义3 1 2设n为一个正整数 若集合A是空集或A与集合 1 2 3 n 等势 称集合A为有限集 否则称A为无限集 即 若A为空集或存在集合 1 2 3 n 到A 或A到该集合的双射 称集合A为有限集 否则称A为无限集 自然数集是无限集 证明正整数集合与自然数集合等势定义函数 f N I f x x 1 75 等势 等基数 的相关概念 定义 集合A与集合B等势 等基数 当且仅当 A与B之间存在双射 一一对应 在此意义下 刻画了两个无穷集合比较 多少 的一种办法 但这里的 多少 概念只是一种直观的解释 已经和有限集合比较多少的情况发生了变化 在有限集合中 一个集合不可能与其真子集等势 但在无限集合的比较 则不同 比如 自然数集和偶数集之间 可以通过双射f n 2n建立一一对应的关系 所以自然数集和偶数集是等势的 虽然偶数