西安电子科技大学离散数学软件学院办第二篇集合论第3章集合与关系第13课时V3.1集合及其运算第14课时3.2二元关系X第15课时3.3集合上的二元关系及其特性Y第16课时3.4关系的闭包运算第18课时3.5等价关系（2)第19-20课时3.6序关系1
西安电子科技大学 离散数学 软件学院 第二篇 集合论 第13课时 3.1 集合及其运算 第3章 集合与关系 3.4 关系的闭包运算 3.2 二元关系 3.5 等价关系 (2) 第14课时 第16课时 第18课时 第15课时 3.3 集合上的二元关系及其特性 第19－20课时 3.6 序关系
西安电子科技大学集合的覆盖与划分$3.5.4软件学院家家家给定非空集合A和集合簇元={A1，A2，"，A.}，如果覆盖满足(1A,二A且A± 0(1<i≤m)(2) A= YA,那么称元是A的一个覆盖如果一组非空集合的并集等于A，那么以这组集合为元素的集合称为A的覆盖
西安电子科技大学 §3.5.4 集合的覆盖与划分 软件学院 覆盖 给定非空集合A和集合簇π={A 1, A 2, ., A m}，如果 满足 （1）Ai ⊆A且Ai ≠ ∅ （1≤ i ≤m） （2）A= 那么称π是A的一个覆盖。 Υ m i Ai =1 如果一组非空集合的并集等于A，那么以 这组集合为元素的集合称为A的覆盖
西安电子科技大学$3.5.4集合的覆盖与划分软件学院给定非空集合A和集合簇元={A1，A2，，Am}，如果划分满足(1)A,A且A,±(1<i<m)YA(2) A=i=l(3）AnA,=の（1≤i,j≤m且i±j)那么称元是A的一个划分。如果一组两两互不相交的非空集合的并集等于A，那么以这组集合为元素的集合称为A的划分
西安电子科技大学 §3.5.4 集合的覆盖与划分 软件学院 划分 给定非空集合A和集合簇π ={A 1, A 2, ., A m}，如果 满足 （1）Ai ⊆A且Ai ≠ ∅（1≤ i ≤m） （2）A= （3）Ai ⋂ Aj= ∅（1≤i, j≤m且i≠j） 那么称π是A的一个划分。 Υ m i Ai =1 如果一组两两互不相交的非空集合的并集 等于A，那么以这组集合为元素的集合称 为A的划分
西安电子科技大学$3.5.4集合的覆盖与划分软件学院【例题】设A={1，2，3}，判断以下集合簇是A的覆盖还是A的划分。解答：元1=(1), (1, 2)既非覆盖又非划分元2={(1, 2),{2, 3)覆盖而非划分元3 ={(1), (1, 2), (1, 3),覆盖而非划分覆盖且是划分元4 =(1, 3), (2)元s = p (A)既非覆盖又非划分
西安电子科技大学 软件学院 【例题】设A={1, 2, 3}，判断以下集合簇是A的覆盖还是A 的划分。 π1={{1}, {1, 2}} π2={{1, 2}, {2, 3}} π3 ={{1}, {1, 2}, {1, 3}}， π4 ={{1, 3}, {2}} §3.5.4 集合的覆盖与划分 π5 =ρ(A) ρ 解答： 覆盖且是划分 覆盖而非划分 覆盖而非划分 既非覆盖又非划分 既非覆盖又非划分
西安电子科技大学集合的覆盖与划分$3.5.4软件学院块一个集合A的划分元中的元素A称为该划分的块。秩非空集合A的划分元，若元为有限集合，则称划分元的块数|元1为划分的秩。若元为无限集合，称其秩是无限的
西安电子科技大学 §3.5.4 集合的覆盖与划分 软件学院 块 秩 一个集合A的划分π中的元素A称为该划分的块。 非空集合A的划分π，若π为有限集合，则称划 分π的块数|π|为划分的秩。若π为无限集合， 称其秩是无限的
西安电子科技大学S3.5.5等价关系与集合的划分软件学院家米『定理』设R是非空集合A上的等价关系，则A上关于R的商集A/R是A的一个划分，称为由R诱导的A的划分，即(a）任取xEA，[β];(b）任取x,yEA，或者[β]=[y]，或者[]r[y]=の;(c)Y[x]R =A。xEA证明：（a）任取xEA，因为R是等价关系，所以R是自反的，因此有ER，即xE[β]R，故[]r≠の
西安电子科技大学 §3.5.5 等价关系与集合的划分 软件学院 『定理』设R是非空集合A上的等价关系，则A上关于R 的商集A/R是A的一个划分，称为由R诱导的A的划分，即 （a）任取x∈A，[x] R ≠ ∅ ； （b）任取x,y∈A，或者[x] R=[y] R，或者[x] R ⋂ [y] R = ∅ ； （c） Υ Ax R x ∈ ][ =A。 证明： （a）任取x∈A，因为R是等价关系，所以R是自反 的，因此有∈R，即x∈[x] R，故[x] R ≠ ∅ 。
西安电子科技大学$3.5.5等价关系与集合的划分软件学院(b）任取x,yEA，考虑以下几种情况(i)若yE[x]R，则ER。任取zE[β]R，ER，因为R是对称的，所以ER。又因为R是传递的，所以有ER，即zE[ylR故有[x]R[y]R。同理可得，[y]R二[x]R由此可知[]R=[y]R°(ii）若y[]R，设[]R[y]Rの，则存在zE[网]Rn[y]R，即zE[]r且zE[ylR，因此有ER且ER。由R是对称的和传递的可知ER，即yE[β]R，矛盾。所以[x]RN[ylR= 。由（i）（ii）可知，或者[×]r=[ylr或者[β]rn[y]r=の
西安电子科技大学 §3.5.5 等价关系与集合的划分 软件学院 （b）任取x,y∈A，考虑以下几种情况： （i）若y∈[x] R，则∈R。 任取z∈[x] R，∈R，因为R是对称的，所以∈R。又因为R是传递的，所以有∈R，即z∈[y] R， 故有[x] R ⊆[y] R 。 同理可得，[y] R ⊆[x] R 。 由此可知[x] R=[y] R 。 （ii）若y ∉ [x] R，设[x] R ⋂[y] R ≠ ∅ ，则存在z∈[x] R ⋂[y] R，即 z∈[x] R且z∈[y] R，因此有∈R且∈R。 由R是对称的和传递的可知∈R，即y∈[x] R，矛盾。 所以[x] R ⋂[y] R = ∅ 。 由（i）（ii）可知，或者[x] R=[y] R或者[x] R ⋂[y] R = ∅
西安电子科技大学S3.5.5等价关系与集合的划分软件学院(c）因为对任意xEA，[β]β二A，所以有Y[x], 二AXEA任取xEA，因为R是自反的，所以ER，即Y[x]rxE[xlR，所以x ExEAA Y[x]rXEA由此可知 Y[x] =A。XEA
西安电子科技大学 §3.5.5 等价关系与集合的划分 软件学院 Υ Ax R x ∈ ][ （c）因为对任意x∈A，[x] R ⊆A，所以有 ⊆ A 任取x∈A，因为R是自反的，所以∈R，即 x∈[x] R，所以x ∈ Υ Ax R x ∈ ][ A ⊆ Υ Ax R x ∈ ][ 由此可知 Υ Ax R x ∈ ][ =A
西安电子科技大学$3.5.5等价关系与集合的划分软件学院【例题】A=(a,b,c,d)，A上的等价关系R=(,,,,,,}，求由关系R诱导的集合A的划分解答：由关系R诱导的集合A的划分元为：元=A/R=( (a,b), (c,d) }
西安电子科技大学 软件学院 【例题】A={a, b, c, d}，A上的等价关系R={, , , , , , , }，求由关系 R诱导的集合A的划分 解答：由关系R诱导的集合A的划分π为： π=A/R={ {a,b}, {c,d} } §3.5.5 等价关系与集合的划分
西安电子科技大学S3.5.5等价关系与集合的划分软件学院率『定理』集合A的一个划分元所确定的A上一个二元关系R=YB×B是A上的等价关系，称为由划分元诱导的A上的等侨关系。证明：设A的一个划分元=B,B2,B,现定义A上的二元关系R，aRb当且仅当a,b在同一块中。现可以证明R满足自反、对称和传递性。故R是等价关系。R=YB×B由R的定义可知BET
西安电子科技大学 §3.5.5 等价关系与集合的划分 软件学院 『定理』集合A的一个划分π所确定的A上一个二元关系 R= B×B 是A上的等价关系，称为由划分 π诱导的A上的 等价关系。 ΥB ∈ π 证明：设A的一个划分π={B 1,B 2,.,B n},现定义A上的 二元关系R，aRb当且仅当a,b在同一块中。现可以证 明R满足自反、对称和传递性。 故R是等价关系。 由R的定义可知 BBR B ×= ∈ Υ π