二元关系等价关系

二元关系等价关系第一页，共二十二页，2022年，8月28日第4章二元关系第二页，共二十二页，2022年，8月28日二元关系4.1二元关系基本概念(重点)4.2关系的运算4.3关系的性质(重点)4.4关系的闭包4.5等价关系和偏序关系(重点及难点)4.6函数的基本概念第三页，共二十二页，2022年，8月28日等价关系本节内容主要说明等价关系和集合的划分(分类)之间的关系：1.等价关系→等价类→商集→集合的划分2.集合的划分→等价关系第四页，共二十二页，2022年，8月28日等价关系定义

等价关系：设A上的二元关系R,如果R是自反的,

对称的，传递的，则称R为等价关系。若<x，y>∈R，称x与y等价，记作x～y。第五页，共二十二页，2022年，8月28日等价关系例1数学中一些常见的等价关系：1.数理逻辑中的公式等值关系。2.无向图中“点的连通”关系。3.方程组的“同解”关系。4.代数系统中的“同构”关系。第六页，共二十二页，2022年，8月28日等价关系例2

设集合A={1,2,3,4,5,6,7,8}，R是A上的模3同余关系，请画出关系图。

1～4～7

2～5～8

3～6第七页，共二十二页，2022年，8月28日等价类定义

等价类——把具有相同性质的元素归为一类设R是A上的等价关系，则称[x]R={y|y∈A∧x～y}为x关于R的等价类。第八页，共二十二页，2022年，8月28日等价类例3

设学生集合A={a,b,c,d,e,f},R1

和R2分别是A上的“同性别”关系和“同宿舍”关系，求所有元素关于R1和R2

的等价类，其中元素属性如下表：解：关于R1

的等价类：关于R2

的等价类：abcdef性别女男男女男女宿舍1-2032-3022-3021-2032-3021-202第九页，共二十二页，2022年，8月28日等价类练习试写出A={1,2,3,4,5,6,7,8}上关于模3同余关系的等价类。解：[1]=[4]=[7]={1,4,7},[2]

=[5]

=[8]={2,5,8},[3]=[6]={3,6}.第十页，共二十二页，2022年，8月28日等价类上述两例可以看出，1.等价关系实际上“同类关系”，是对集合按照某种性质进行的“分类”

。2.这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。第十一页，共二十二页，2022年，8月28日等价类定理

设R是非空集合A上的等价关系,则(1)xA,[x]≠(2)x,yA,如果xRy,则[x]=[y](3)x,yA,如果x

y,则[x]∩[y]=(4)等价类或者完全相同，或者完全不同，其并集恰好是A第十二页，共二十二页，2022年，8月28日商集定义

商集——等价类的集合

A/R={[x]|x∈A}性质商集是集合的一个划分。第十三页，共二十二页，2022年，8月28日集合的划分定义集合的划分把集合A分为若干非空子集A1,A2,…,An,满足：

(1)当i≠j时，Ai∩Aj＝

(2)则子集族={A1，A2，…，An}称为A的一个划分，Ai(i=1,2,...,n)称为划分块。A1A6A5A4A3A2A第十四页，共二十二页，2022年，8月28日集合的划分例4

分别给出学生集合A={a,b,c,d,e,f}根据“性别”和“宿舍”进行的划分1和2。解：1

={{a,d,f},{b,c,d}}={A1，A2},

其中A1={a,d,f}，A2={b,d,c}2

={{a,d},{f},{b,c,d}}={A1，A2，A3},

其中A1={a,d}，A2={f}，A3={b,d,c}abcdef性别女男男女男女宿舍1-2032-3022-3021-2032-3021-202第十五页，共二十二页，2022年，8月28日集合的划分例5

试给出集合A={1,2,3}的所有划分。1231

1235123212341233第十六页，共二十二页，2022年，8月28日集合的划分与等价关系性质1.等价关系对应集合的一个划分。等价关系→等价类→商集→集合的划分2.集合的一个划分对应着一个等价关系，这个等价关系的商集恰好是这个划分。第十七页，共二十二页，2022年，8月28日集合的划分与等价关系例6

试给出学生集合A={a,b,c,d,e,f}关于“性别”的划分所对应的等价关系R。解：={{a,d,f},{b,c,d}}={A1，A2},

R={<x,y>|x,y同性别}={<x,y>|x,yA1

∨

x,yA2}={<x,y>|x,yA1}

∨{<x,y>|x,yA2}=A1A1

A2A2

abcdef性别女男男女男女

=?第十八页，共二十二页，2022年，8月28日集合的划分与等价关系性质设={A1，A2，…，An}为A的一个划分，则所对应的等价关系R可由如下方法得到：R={<x,y>|x,y属于的同一划分块（具有相同的性质）}=A1×A1A2×A2......An×An=第十九页，共二十二页，2022年，8月28日小结等价关系是“分类关系”。集合的划分与等价关系本质上相同，可以相互导出。(1)等价关系导出划分：等价关系→商集(2)集合的划分导出等价关系：R={<x,y>|x,y属于的同一划分块（具有相同的性质）}

=第二十页，共二十二页，2022年，8月28日集合的划分与等价关系例7

试写出集合A={1,2,3}上的所有等价关系。解：

1.写出所有划分：2.写出每个划分对应的每个等价关系：(略)1231

1235123212341233第二十一页，共二十二页，2022年，8月28日作业1.给定集合A={1,2,3,4}，且A中的关系R：R={<1,1>,<1,3>,<2,2>,<3,4>,<4,1>,<4,4>}求包含R的最小的等价关系R*（前已求）,并写出商集A/R*。2.给定集合S={1,2,3,4,5},找出S上的等