等价关系与等价类报告.ppt

3-10 等价关系与等价类 离散数学 复习 自反性（ reflexive ） 定义：设R为定义在集合A上的二元关系，如果 对于每个x∈A，都有x,x∈R,即xRx，则称二元关系R是自反的。 对称性（ symmetric ） 定义：设R为定义在集合A上的二元关系，如果对于每个x，y∈A，每当x,y∈R，就有y,x∈R，则称集合A上关系R是对称的。 传递性（ transitive ） 定义:设R为定义在集合A上的二元关系， 如果对于任意x，y，z∈A， 每当x,y ∈ R且y,z ∈R，就有x,z ∈ R，称关系R在A上是传递的。 R1 是对称的。 R2 是自反的、对称的、传递的。 等价关系与等价类的基本概念 1 等价关系的基本性质 2 主要内容 商集与集合的划分 3 3 一、定义 定义1:设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为集合A上的等价关系。 例如 平面上三角形集合中，三角形的相似关系； 同学集合A={a,b,c,d,e,f,g},A中的关系R：住在同一宿舍； 同性关系。 例1 设T＝｛1，2，3，4｝， R＝｛＜1，1＞，＜1，4＞，＜4，1＞， ＜4，4＞，＜2，2＞，＜2，3＞， ＜3，2＞，＜3，3＞｝。 验证R是集合T上的等价关系。 例2 设A = { 1, 2, …, 8 }, 如下定义A上的关系R:  R = { x, y | x, y?A且x≡y（mod3) } 证明R为A上的等价关系。 证明: ?x?A , 因为x-x=0=0×3,所以x,x∈R; ?x,y?A, 若x-y=3t(t为整数）, 则有: y-x=-3t,即 y,x∈R; ?x,y,z?A, 若x-y=3t, y-z=3s, 则有: x-z=3(t+s),即x,z ∈R. 关系图如下图所示. 等价类 定义2：设R为集合A上的等价关系，对任意a∈A，集合 [a]R={x|x ∈ A,a,x∈R} 称为元素a关于R的等价类。 例2可求出三个不同的等价类 [1]R=[4]R=[7]R={1,4,7} [2]R=[5]R=[8]R={2,5,8} [3]R=[6]R={3,6} 定义3:集合A上的等价关系R，其等价类集合{[a]R|a ∈ A}称作A关于R的商集(quotient set) 。记作A/R (1) a ∈[a]R (2)定理1:设给定集合A上的等价关系R，对于a,b∈A，若a,b∈R,iff [a]R=[b]R。 二、性质 (3)设R为集合A上的等价关系，则任意a,b ∈ A,若a,b R,则 证明　设集合A上的一个等价关系R，则[a]R是A的一个子集，则所有这样的子集可做成商集A/R 　1、A/R={[a]R|a ∈A}中,　∪[a]R=A 　2、 对任意a ∈A，都有aRa，即a∈[a]R，即A中的每一个元素都属于一个分块。 　3、A的每个元素只能属于一个分块 　　反证设a∈[b]R ，a∈[c]R,且[b]R ≠ [c]R，则bRa,cRa成立，所以有aRc,所以bRc，即[b]R ＝ [c]R 所以A/R是A上对应于R的一个划分。 定理2：集合A上的等价关系R，决定了A的一个划分，该划分就是商集A/R。 三 商集与集合的划分