第4章+二元关系与函数4.5

人大离散数学课件ppt

离散数学余力82500907 理工配楼303A 理工配楼 buaayuli@http://

人大离散数学课件ppt

第4章 二元关系与函数4.1 集合的笛卡儿积与二元关系

√ 4.3 关系的性质 √ 4.4 关系的闭包 √4.2 关系的运算 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数

√

人大离散数学课件ppt

4.5 等价关系与偏序关系等价关系的定义与实例 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应 偏序关系 偏序集与哈斯图 偏序集中的特定元素3

人大离散数学课件ppt

等价关系的定义与实例为非空集合上的关系. 定义 设 R 为非空集合上的关系 如果 R 是 自反的、对称的和传递的, 自反的、对称的和传递的 则称 R 为 A 上的 等价关系. 是一个等价关系, 等价关系 设 R 是一个等价关系 若 <x,y>∈R, 称 x 等价于 记做 x~y. 等价于y, ∈ ~如下定义A上的关系 ： 实例 设 A={1,2,…,8}, 如下定义 上的关系 R:  R = { <x,y> | x,y∈A∧x≡y(mod 3) } ∈ ∧ 相等, 除以3的 相等 其中 x≡y(mod 3) 叫做 x 与 y 模3相等 即 x 除以 的 除以3的余数相等 的余数相等. 余数与 y 除以 的余数相等4

人大离散数学课件ppt

等价关系的验证上的等价关系, 验证模 3 相等关系 R 为 A上的等价关系 因为 上的等价关系 x∈A, 有x ≡ x(mod 3) ∈ x, y∈A, 若 x ≡ y(mod 3), 则有 y ≡ x(mod 3) y∈ x, y, z∈A, 若x ≡ y(mod 3), y ≡ z(mod 3), ∈ 则有 x≡z(mod 3) 自反性、对称性、 自反性、对称性、传递性得到验证5

人大离散数学课件ppt

A上模3等价关系的关系图 上模3设 A={1,2,…,8}, R={ <x,y>| x,y∈A∧x≡y(mod 3) } ∈ ∧

人大离散数学课件ppt

等价类为非空集合A上的等价关系 定义 设R为非空集合 上的等价关系 x∈A, 为非空集合 上的等价关系, ∈ , 令[x]R = { y | y∈A∧xRy } ∈ ∧ 关于R 等价类, 的等价类, 称 [x]R 为 x 关于 的等价类 简称为 x 的等价类 简记为[x]. 简记为 实例 A={ 1, 2, … , 8 }上模 3 等价关系的等价类 上模 [1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6}7

人大离散数学课件ppt

等价类的性质定理1 是非空集合A上的等价关系 定理 设R是非空集合 上的等价关系 则 是非空集合 上的等价关系, (1) x∈A, [x] 是A的非空子集 的非空子集. ∈ 的非空子集 (2) x, y∈A, 如果 x R y, 则 [x]=[y]. ∈ (3) x, y∈A, 如果 x y, 则 [x]与[y]不交 不交. ∈ 与 不交 (4) ∪{ [x] | x∈A}=A,即所有等价类的并集 ∈ 就是A. 就是8

人大离散数学课件ppt

实例A={ 1, 2, … , 8 }上模 3 等价关系的等价类： 上模 等价关系的等价类： [1]=[4]=[7]={1,4,7}, , [2]=[5]=[8]={2,5,8}, , [3]=[6]={3,6} 以上3 类两两不交， 以上 类两两不交， {1,4,7}∪{2,5,8}∪{3,6} = {1,2, … ,8} ∪ ∪9

人大离散数学课件ppt

商集为非空集合A上的等价关系 定义 设R为非空集合 上的等价关系 以R 为非空集合 上的等价关系, 的所有等价类作为元素的集合称为A关于 关于R 的所有

等价类作为元素的集合称为 关于 商集, 记做A/R, A/R = { [x]R | x∈A } 的商集 记做 ∈ 关于模3等价关系 实例 A={1,2,…,8},A关于模 等价关系 的 ， 关于模 等价关系R的 商集为 A/R = { {1,4,7}, {2,5,8}, {3,6} } A关于恒等关系和全域关系的商集为： 关于恒等关系和全域关系的商集为： 关于恒等关系和全域关系的商集为 A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} }

人大离散数学课件ppt

集合的划分为非空集合, 定义 设A为非空集合 若A的子集族 为非空集合 的子集族 π(π P(A)) 满足下面条件： 满足下面条件： (1) π (2) x y (x,y∈π∧x≠y→x∩y= ) ∈ ∧ (3) ∪π=A 则称π是 的一个划分, 的一个划分 中的元素为A的 则称 是A的一个划分 称π中的元素为 的 中的元素为 划分块. 划分块11

人大离散数学课件ppt

例题例1 设A={a, b, c, d}, = 给定π 给定 1,π2,π3,π4,π5,π6如下： 如下：  π1= { {a, b, c}, {d} }, π2= { {a, b}, {c}, {d} } , π3= { {a}, {a, b, c, d} }, π4= { {a, b}, {c} } π5= { ,{a, b}, {c, d} }, π6= { {a, {a}}, {b, c, d} } 的划分, 的划分. 则π1和π2 是A的划分 其他都不是 A 的划分 的划分 为什么？ 为什么？12

人大离散数学课件ppt

等价关系与划分的一一对应 商集 A/R 就是 A 的一个划分 商集 不同的商集对应于不同的划分 不同的商集对应于不同的划分 任给 A 的一个划分 如下定义 A 上的关系 R: 任给 的一个划分π, : R = {<x,y> | x,y∈A∧x 与 y 在π的同一划分块中 的同一划分块中} ∈ ∧ 的同一划分块中 上的等价关系, 则 R 为 A上的等价关系 且该等价关系确定的商集 上的等价关系 就是π. 就是 给出A= 例2 给出 ={1,2,3}上所有的等价关系 上所有的等价关系 求解思路：先做出A的所有划分 的所有划分, 求解思路：先做出 的所有划分 然后根据划分写 出对应的等价关系. 出对应的等价关系13

人大离散数学课件ppt

等价关系与划分之间的对应

π4 对应于全域关系 EA,π5 对应于恒等关系 IA π1,π2和π3分别对应等价关系 R1, R2 和 R3. R1={<2,3>,<3,2>}∪IA,R2={<1,3>,<3,1>}∪IA ∪ ∪ R3={<1,2>,<2,1>}∪IA ∪

人大离散数学课件ppt

实例例3 设 A={1, 2, 3, 4},在 A×A上定义二 ， × 上定义二 元关系R: 元关系 ： <<x,y>,<u,v> …… 此处隐藏：1150字，全部文档内容请下载后查看。喜欢就下载吧 ……