西安电子科技大学离散数学软件学院第二篇集合论第3章集合与关系第13课时V3.1集合及其运算第14课时3.2二元关系X第15课时3.3集合上的二元关系及其特性→第16课时3.4关系的闭包运算第17课时3.5等价关系（1)第19-20课时3.6序关系A
西安电子科技大学 离散数学 软件学院 第二篇 集合论 第13课时 3.1 集合及其运算 第3章 集合与关系 3.4 关系的闭包运算 3.2 二元关系 3.5 等价关系 (1) 第14课时 第16课时 第17课时 第15课时 3.3 集合上的二元关系及其特性 第19－20课时 3.6 序关系
西安电子科技大学等价关系$3.5.1软件学院家家设R是集合A上的一个二元关系，若R是自反等价关系对称和传递的，则称R为等价关系。例如：1,2,3,4,5,8上的模3同余关系
西安电子科技大学 §3.5.1 等价关系 软件学院 等价关系 设R是集合A上的一个二元关系，若R是自反、 对称和传递的，则称R为等价关系。 例如：{1,2,3,4,5,8}上的模3同余关系
西安电子科技大学等价关系$3.5.1软件学院等价关系的关系图的特点：所有结点上自反性有自回路只要结点r到s可达正对称与传递性则r到s有边相连等价关系的关系图的每个连通子图都是有向完全图
西安电子科技大学 软件学院 等价关系的关系图的每个连通子图 都是有向完全图 。 自反性 对称与传递性 所有结点上 有自回路 只要结点r到s可达 则r到s有边相连 等价关系的关系图的特点： §3.5.1 等价关系
西安电子科技大学S3.5.1等价关系软件学院家【例题】A=(a,b,,d)，A上的二元关系R=(，,,,,,),验证关系R是等价关系。解答：(i）因为I二R，所以是自反的：(ii) 因为R-1={,,,,,,，)=R，所以R是对称的;(ii) 因为R.R={,,,,，,,}二R，所以R是传递的。综上所述，R是等价关系，其关系图如图所示
西安电子科技大学 软件学院 【例题】A={a, b, c, d}，A上的二元关系R={, , , , , , , }，验证关 系R是等价关系。 §3.5.1 等价关系 解答： （i）因为IA⊆R，所以是自反的； （ii）因为R-1={, , , , , , , }= R，所以R是对称的； （iii）因为R◦R={, , , , , , , }⊆R，所以R是传递的。 综上所述，R是等价关系，其关系图如图所示
西安电子科技大学等价关系$3.5.1软件学院【例题】设I为整数集，I上的模3相等关系R={]x三y（mod3，证明R是等价关系。证明：(i)对于任一aEI，有a三a(mod 3)，即ER，所以R是自反的；(ii）若ER，则有a=b(mod3)，即存在mEI,使得a-b=3m，于是有b-a=-3m，因此b=a(mod3)，即ER，所以R是对称的。(iii）若,ER，则有a=b(mod3)和b=o(mod3)，即存在m,nEI，使得a-b=3m和b-c=3n，将等式两边相加得a-c=3(m+n）因此a三c(mod 3)，即ER，所以R是传递的。综上所述，R是等价关系
西安电子科技大学 §3.5.1 等价关系 软件学院 【例题】设I为整数集，I上的模3相等关系R={| x≡y(mod 3)}，证明R是等价关系。 证明： （i）对于任一a∈I，有a≡a (mod 3)，即∈R，所 以R是自反的； （ii）若∈R，则有a≡b (mod 3)，即存在m∈I， 使得a-b=3m，于是有b-a=-3m，因此b≡a (mod 3)，即∈R，所以R是对称的。 （iii）若,∈R，则有a≡b (mod 3)和b≡c (mod 3)，即存在m,n∈I，使得a-b=3m和b-c= 3n，将等 式两边相加得a-c=3( m+n) 因此a≡c (mod 3)，即∈R，所以R是传递的。 综上所述，R是等价关系
西安电子科技大学等价关系$3.5.1软件学院【例题】设R为计算机系所有学生构成的集合上的“同住一个宿舍关系”，验证R是等价关系。解答：（i）任意一个学生与自己同住一个宿舍，因此R是自反的;(i）如果aRb，即a学生与b学生同住一个宿舍，则b学生与a学生也同住一个宿舍，因此有bRa，所以R是对称的；(iii）如果有aRb和bRc，即a学生与b学生同住一个宿舍，b学生与c学生同住一个宿舍，自然a学生与c学生也同住一个宿舍，即有aRc成立，所以R是传递的，因此R是等价关系，这个等价关系将计算机系的所有同学划分成若干个宿舍
西安电子科技大学 软件学院 【例题】设R为计算机系所有学生构成的集合上的“同住一 个宿舍关系”，验证R是等价关系。 §3.5.1 等价关系 解答： （i）任意一个学生与自己同住一个宿舍，因此R是自反 的； （ii）如果aRb，即a学生与b学生同住一个宿舍，则b学生 与a学生也同住一个宿舍，因此有bRa，所以R是对称的； （iii）如果有aRb和bRc，即a学生与b学生同住一个宿 舍，b 学生与c学生同住一个宿舍，自然a学生与c学生也同住 一个宿舍，即有aRc成立，所以R是传递的。 因此R是等价关系，这个等价关系将计算机系的所有同 学划分成若干个宿舍
西安电子科技大学等价类$3.5.2软件学院家设R是非空集合A上的等价关系，对于任意等价类aEA，称集合[a]r=区「EA，xRa)为a关于R的等价类，a称为等价类alp的代表元素。等价类[alR是所有与a具有R关系的元素构成的集合
西安电子科技大学 软件学院 等价类 等价类[a]R 是所有与a具有R关系的 元素构成的集合 。 §3.5.2 等价类 设R是非空集合A上的等价关系，对于任意 a∈A，称集合[a]R={x | x∈A，xRa}为a关于R 的等价类，a称为等价类[a]R的代表元素
西安电子科技大学$3.5.2等价类软件学院家家【例题】设A={1，2，3，4，5，8}，R是A上的“模3同余”关系，求关于R的所有等价类。解答：A上关于R有三个等价类：[1]r={1,4)=[4]R;[2]r={2, 5, 8]=[5]R= [8]R[3]R={3]。1
西安电子科技大学 §3.5.2 等价类 软件学院 【例题】设A={1, 2, 3, 4, 5, 8}，R是A上的“模3同余”关 系，求关于R的所有等价类。 A上关于R有三个等价类： [1]R={1,4}=[4]R； [2]R={2, 5, 8}=[5]R= [8]R； [3]R={3}。 解答：
西安电子科技大学商集$3.5.3软件学院设R是集合A上的等价关系，由R确定的所有等价商集类组成的集合，称为集合A上关于R的商集，记为A/R。A/R=[xlR I xEA}
西安电子科技大学 软件学院 商集 §3.5.3 商集 设R是集合A上的等价关系，由R确定的所有等价 类组成的集合，称为集合A上关于R的商集，记 为A/R。 A/R={[x]R | x∈A}
西安电子科技大学$3.5.3商集软件学院【例题】设A={1，2，3，4，5，8}，R是A上的“模3同余”关系，求商集A/R。解答：A/R={[1]r, [2]r, [3]r}={(1,4), (2,5,8), [3))
西安电子科技大学 §3.5.3 商集 软件学院 【例题】设A={1, 2, 3, 4, 5, 8}，R是A上的“模3同余”关 系，求商集A/R。 解答： A/R={[1]R, [2]R, [3]R}={ {1,4}, {2,5,8}, {3} }