离散数学讲义 第五章二元关系.ppt

例12 设A={a,b,c}，求出A上所有的等价关系。 解 先求出A上有多少个不同的分划。 分成一个分划块的分划 分成两个分划块的分划 分成三个分划块的分划 因此，A上有5个不同的分划，如下图所示 a b c a b c b a c c a b a c b 记与分划 相对应的等价关系为 （3）若ρ1和ρ2是对称的，则ρ1·ρ2也是对称的； （4）若ρ1和ρ2是反对称的，则ρ1·ρ2也是反对称的； （5）若ρ1和ρ2是可传递的，则ρ1·ρ2也是可传递的； 　　　　　　　例如 ，设集合A=｛1,2,3｝， ρ1=｛（1,2），（2, 1）｝ ,ρ2=｛（1,3），(3,1)｝， 显然 ρ1和ρ2都是对称的， 　　　　　例如设 A =｛1,2,3｝,ρ1={(1,2),(3，3）｝, ρ2 ={(2,3）,(3，1）｝显然ρ1和ρ2都是反对称的， 　　　　　例如设 A =｛1,2,3},ρ1={(1,2),(2,3）,(1,3）}, ρ2 =｛（2，3），（3，1），（2，1）｝， 　　　显然ρ1和ρ2都可传递的. 但ρ1·ρ2=｛（2,3）｝不是对称的。 但ρ1·ρ2={(1,3）,(2,1）,(1,1)} 不是可传递的。 但ρ1·ρ2 =｛（1, 3），(3,1)｝不是反对称的。 证明（3）否 . (4) 否 . （5）否 . 4 .有人说，集合A上的关系　 ，如果是对称的且可 　　传递，则它也是自反的。其理由是，从 对称性 传递性 例 设 A＝｛1,2，3｝ ρ＝｛(1,2),(2,1),(1,1),(2,2)} 5． 设ρ1是集合A上的一个关系，ρ2=｛（a,b）| 存在 c， 　　　使（a,c）∈ρ1且（c,b）∈ρ1｝，试证明： 若 ρ1是一个等价关系，则ρ2也是一个等价关系。 证明 因为ρ1是自反的，所以对于任意的 a ∈A　, 有（a, a）∈ρ1 　　　　　 ，　由（a,a）∈ρ1 ,(a,a) ∈ρ1 由ρ1的对称性,又有（b, c）∈ρ1 ,且（c, a）∈ρ1 , 因而有（b, a）∈ρ2 ,故ρ2 是对称的。 对于任意的a, b∈A,若（a, b）∈ρ2 , 则必有元素c∈A，使得（a, c）∈ρ1, 且（c, b）∈ρ1 , 因此有 （a,a)∈ρ2 ,ρ2 是自反的。 对于任意的a, b, c∈A , 若（a, b）∈ρ2 , (b, c) ∈ρ2, 则必有元素 d , e ∈ A , 使得 （a, d）∈ρ1 (d, b) ∈ρ1 　(b, e) ∈ρ1 (e, c) ∈ρ1 由ρ1的可传递性，又有（a, b）∈ρ1, (b, c) ∈ρ1, 于是有（a, c）∈ρ2,故ρ2 是可传递的。 由上证得ρ2 是一个等价关系。 证法二 设（a, b）∈ρ1, 由ρ1的自反性，又有（a, a）∈ρ1, 由（a, a）∈ρ1,(a, b) ∈ρ1, 于是有（a, b）∈ρ2 , 因此ρ1 ρ2 。 反之，设（a, b）∈ρ2 ， 则必存在c∈A,使得（a, c）∈ρ1,(c, b) ∈ρ1, 而由ρ1的可传递性，又有（a, b）∈ρ1,因此ρ2 ρ1 . 由上可知ρ2=ρ1，因此ρ2是等价关系。 5.7 相容关系与等价关系 一、相容关系 定义5.7.1 设R是集合A上的关系，如果它是自反的，对称的，则称R是A上的相容关系。若aRb,则称a和b是相容的，否则称a和b是不相容的。 例1 设A为学生的集合，考察集合A上的“同班同学”关系是否是相容关系？ 是 1. 相容关系的定义 例2 有学生6人组成集合A={张小平，王平，丁小燕，王芳，王春，李承} 定义A上的关系R={(x,y)|x,y∈A，且x与y中出现有相同的字}，考察R是否是A上的相容关系？ 是 例3 设A={T1,T2,T3,T4,T5,T6}是某台微机上6项任务的集合，有五个子程序S1,S2,S3,S4,S5供它们选择调用，下表列出了它们调用子程序的情况。 调用的子程序 任务名称 定义A上的关系R={(x,y)|x,y∈A且x与y调用了相同的子程序},问R是否是相容关系？ 是 2. 相容关系的简化表示 1 2 5 4 3 2. 极大相容类 定义5.7.2 设R是非空集合A上的相容