离散数学3.ppt

关系与函数 关系的定义与表示 二元关系的定义 定义3 1 3设A B是两个集合 称下述集合乘积 AXB二 a Ab B 为集合A B构成的笛卡儿积 直接积 二元关系的定义 定义3 1 1 设A B是两个集合 称笛卡儿积AXB的子集为从A到B的二元关系或简称关系 设R是从A到B的关系 则R是一些序偶组成的集合 在这些序偶中 第一个元素来自A的第二个元素来自B 即对每一对a A和b B R 称a与b之间具有关系R 记作aRb 二元关系的定义 例3 1 2 设A 鸡蛋 奶 玉米 B 奶牛 山羊 母鸡 我们可以定义由A到B的关系 R如果a由b产生 即R 例3 1 3 假定我们说两个国家相邻是指两个国家具有公共的国境线 那么 相邻 就是世界上国家之间的关系R 且 中国R俄罗斯 中国R印度 例3 1 4 实数集合R上的小于等于 是关系 关系的表示 1 集合法 关系可以表示成序偶对的集合 如例3 1 5 1 R为定义在集合AXBA 1 2 3 B a b c 的关系可表示为 R 对于有限集上的二元关系 除了用上面集合表示法外 还可以用关系矩阵和关系图进行表示 关系的表示 图示法 用图表示关系更加形象具体 定义3 1 4 设A al a2 an R是AxA上的关系 令有向图G V E 其中 顶点集合V A 边集合E按如下规定 有向边 ai aj E R则称有向图G为R的关系图 记为G 关系的表示 图示法 例4 1 6 设A 是R上的二元关系 则R的关系图如图3 1 关系的表示 矩阵表示法 定义3 1 5设A al a2 am B bl b2 bn R是A到B上的关系 则关系矩阵R rij 1当aiRbjrij 0elseR 矩阵是比较适合计算机处理的表示方法 关系的表示 关系的表示 例3 1 7 学生集合A 学生A 学生B 学生C 电视剧集合B 言情片 武打片 R是定义在A到B上的 喜爱观看 关系 学生AR言情片表明学生A喜爱观看言情片 R 表示成矩阵 关系的表示 例3 1 7 复合运算 定义3 2 1 R为定义在集合AXB的关系 S是定义在BXC的关系 则在AXC上的关系为 RoS 存在b B使得 Rand b c S 记为R与S的复合关系 复合运算 例3 2 1学生集合A 学生A 学生B 学生C 课程集合B 离散数学 数据结构 教室集合C 教室A 教室B 学生选课关系R定义在A到B上 R 课程教室关系S定义在B到C上 S 复合关系 T RoS 复合关系T表明了学生和上课教室的关系 复合运算 定理3 2 1 设Rl是从X到Y的关系 R2是从Y到Z的关系 选定X Y和Z的顺序 所有的关系矩阵都对应于已选的顺序 设A1是R1的矩阵 A2是R2的矩阵 则将矩阵乘积A1XA2中的每个非零项用1替换后就得到了关系R2oR1的矩阵 复合运算 例3 2 2 R1是X 1 2 3 Y a b 上的关系 R1 R2是Y到Z x y z 的关系 R2 R1 R2对应的矩阵分别为A1A2R R1oR2对应的矩阵为 A 复合运算 复合运算 算法3 2 1 求复合关系的算法 复合关系的算法GetCompositiveRelation RelationR RelationS T Multi R S 实现矩阵RS的相乘For i 0 i0Tij 1 关系与函数 关系性质 关系性质 定义3 3 1对定义在集合X到X上的关系R 如果对每个x R都有 x x R 则称R为自反的定义3 3 2对定义在集合X到X上的关系R 如果对每个x R x x 不属于R 称R反自反的 关系性质 定义4 3 3对定义在集合X上的关系R 如果对所有的x y X 若 x y R则 y x R 称R为对称的 定义4 3 4对定义在集合XxX上的关系R称 如果对所有的x y X 若 x y R 且x y 则 y x 不属于R 称R为反对称的 关系性质 定义3 3 5集合XxX上的关系R称为传递的 如果对所有的x y z X 若 x y R y z R 则 x z 属于R 在实数集里 大于关系 小于等于关系等都是传递关系 关系性质的判定算法 关系R是自反的当且仅当A在主对角线上全是1关系是对称的当且仅当对所有的i和j A的第ij项等于A的第ji项 通俗地说 R是对称的当且仅当A关于主对角线是对称的 关系性质的判定算法 关系R是传递的当且仅当只要A2的第ij项非零 A的第ij项就非零 关系性质的判定算法 算法3 2 判定关系自反的算法 判定关系R是否自反IsSelf RelationR for i 0 i iRlength i ifrii 1returnfalse returntrue 关系性质的判定算法 算法3 4 判定反对称的算法 判定反对称的算法 IsAntiSym RelationR for i 0 i iRlength i for j 0 j iRlength j if rij rji and rij 1 or rji 1 returnfalse returntrue 关系性质的判定算法 算法3 5 判定算法的传递 判定传递的算法 IsTran RelationR 计算R和R的乘积RelationT GetCompositiveRelation RelationR Rel tionR for i 0 i0 ifrij 0returnfalse returntrue 关系与函数 等价关系 等价关系 定义3 4 1 设R是集合A上的关系 如果R是自反的 对称的 传递的 则称R是等价关系 等价关系 判定一个关系是否是等价关系的算法如下isEqu RelationR if i elf R andi ym R andisTran R retuentrue elsereturnfalse 等价关系 定义3 4 2 设R是一个等价关系 若 R 称a等价于b 例5 9 1 在全体中国人组成的集合上定义 同姓 关系 它具备自反 对称 传递的性质 因此是一个等价关系 2 平面上直线集合上上的 平行或恒等 关系是等价关系 而L上的 垂直 关系不是等价关系 因为它既不是自反的 也不是传递的 3 平面上三角形的 全等 关系 相似 关系等都是等价关系 4 朋友 关系不是等价关系 因为它不是传递的 5 集合的 包含于 关系不是等价关系 因为它不是对称的 等价关系 定义3 4 3设R是非空集合A上的等价关系 a A 称 a b b A且 R 为元素a关于等价关系R的等价类 简称口的等价类 简记为 a 由定义3 4 3可知 a的等价类是A中所有与a等价的元素组成的集合 上例中的等价类是 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 等价关系 定义3 4 4设A是一个非空集合 A1 A2 Am是它的非空子集 如果它们满足下列条件 1 对所有的i j i j 1 2 m 如果i j则Ai Aj 2 Ai A则称集合 A1 A2 Am 为A的一个划分 等价关系 根据集合X上的等价关系R 对X进行划分GetEquivalenceCla Setx RelationR ForX中的元素xi i代表xi的序号 创建xi的等价类 并置为空集 xi ForX中的元素xj j代表xj的序号 Ifrij 1 rij是R中第i行就列的元素 把xj加入到xi的等价类集合中 xi xi xj 把xj从集合X中去除 X X xj 所得到的等价类就是X的一个划分 关系与函数 次序关系 次序关系 偏序关系 满足自反性的次序关系 即满足自反性 反对称性及传递性 线性次序关系 所有元素均能顺序排列的偏序关系 拟序关系 满足反自反性的次序关系 即满足反自反性 反对称性及传递性 次序关系 偏序关系 满足自反性的次序关系 即满足自反性 反对称性及传递性 线性次序关系 所有元素均能顺序排列的偏序关系 拟序关系 满足反自反性的次序关系 即满足反自反性 反对称性及传递性 偏序关系 定义3 5 1 偏序关系 集合S上的关系R如果是自反的 反对称的及传递的 则称R在S上是偏序的或称R是S上的偏序关系并可记以 S R 一般可用符号 表示偏序 注意 它并不表示数字中的小于或等于符号 例3 5 1整数集Z上的 关系是偏序关系 它可记为 Z 例3 5 2集合S 2 3 6 8 上的 整除 关系 I R 2 2 3 3 6 6 8 8 2 6 2 8 3 6 是偏序的 并可记为 S I 哈斯图 为方便表示偏序关系可用一种图示方法 这种方法可称为哈斯 Hasse 图 哈斯图 例3 5 3 Z 的哈斯图可见图2 1la 哈斯图 S 2 3 6 12 24 36 上的整除关系R的哈斯图可见图3 3b 最大元素 最小元素 极大元素 极小元素 定义3 5 2最大元素 最小元素 极大元素 极小元素 设有 X 且集合YX 有y Y 1 对每个y Y都有y y 则称y是Y的最大元素 2 对每个y Y都有y y 则称y是Y的最小元素 3 Y中不存在y 使得y y 且y y 则称y是Y的极大元素 4 Y中不存在y 使得y y 且y y 则称y是Y的极小元素 上界上确界下界下确界 定义3 5 3上界上确界下界下确界 设有 X 且集合YX 有x X 1 对每个y Y都有y x 则称x是Y的上界 2 对每个y Y都有x y 则称x是Y的下界 3 x是Y的上界 且对每个Y的上界x 有x x 则称x是Y的上确界 4 x是Y的下界 且对每个Y的下界x 有x x 则称x是Y的下确界 例子 设S 1 2 10 在S上的定义关系 小于等于 可以看出这是一个偏序关系 哈斯图如图3 4 对S的子集s1 1 2 3 S2 8 9 10 和S其重要元素见表3 1 例子 偏序关系 定理3 5 1对集合X上的偏序关系 有YX 则我们有 1 x是Y的最大 小 元素 则它必为Y的极大 小 元素 2 x是Y的最大 小 元素 则它必为Y的上 下 界 3 x是Y的上 下 确界 且x Y 则x必为Y的最大 小 元素 线性关系 定义3 5 4 线性次序 设集合S上有偏序关系R 如x y S 必有x y或y x 则称R是线性次序的 也称全序的 或称只上集合S上的线性次序关系 例3 5 6集合S a b c 上的关系R a b b c a c a a b b c c 是线性次序的 它的哈斯图可见图3 5 线性关系 拟序关系 定义3 5 5 拟序关系 集合S上的关系及如是反自反的 反对称的及传递的 则称只是S上的拟序的 或称只是S上的拟序关系 一般可用符号 表示拟序 注意 它并不表示数字中的小于符号 关系与函数 函数 函数 定义3 7 1一个从X到Y的函数f是一个具有如下性质的从X到Y的关