关系的性质.pptVIP

adfadffd 等价关系的判定 例3 设?1是集合A上的一个二元关系，?2={(a,b)∣存在c，使(a,c)∈?1且(c,b)∈?1}，证明若?1是一个等价关系，则?2也是一个等价关系。 证明 设?1是A上的等价关系 （1）证?2自反 对任意一个x?A，因为?1在A上自反，所以(x,x)??1。由?2的定义，(x,x)??2，所以?2是自反的。 （2）证?2对称 对任意x,y?A，若(x,y)??2，则存在某个c?A，使得(x,c)??1且(c,y)??1，因为?1是对称，故有(y,c)??1且(c,x)??1，由?2的定义，可知(y,x)??2，所以?2是对称的。 （3）证?2传递 对任意x,y,z?A，若(x,y)??2，(y,z)??2，则必存在某个c1?A，使(x,c1)??1，(c1,y)??1。由?1的传递性，可知(x,y)??1，同理存在c2?A，使(y,c2)??1且(c2,z)??1，由?1传递，可知(y,z)??1。再由?2的定义，得(x,z)??2。所以?2是传递的。 由以上（1）（2）（3）可知?2是一个等价关系。 重点掌握：已知一个集合的一个划分，求该划分所确定的等价关系 例7 设A={a,b,c,d,e}有一个分划?={{a,b},{c},{d,e}}，求?所确定的等价关系?。 解 设?1={a,b}?{a,b}={(a,a),(a,b),(b,a),(b,b)}， ?2={c}?{c}={(c,c)}, ?3={d,e}?{d,e}={(d,d),(d,e),(e,d),(e,e)}。 所以?=?1∪?2∪?3 ={(a,a),(a,b),(b,a),(b,b),(c,c),(d,d),(d,e),(e,d),(e,e)}。 例8 设A是由4个元素组成的集合，试问在A上可以定义多少个不同的等价关系？ 分析 如果直接考虑A上可以定义多少个等价关系，则计算过程比较繁琐，也容易出错。根据定理1可知集合A上的等价关系与分划存在一一对应的关系，因此此题可转化为考虑A上有多少个不同的分划。 解 将集合A分划为一块：有1种分法； 将集合A分划为两块：有(24-2)/2种分法； 将集合A分划为三块：有C(4,2)种分法； 将集合A分划为四块：有1种分法； 因此，集合A上不同等价关系的个数为 1+(24-2)/2+C(4,2)+1=15。 * 5.3关系的性质 一、集合A上关系的性质 设?为集合A上的二元关系，则 自反关系 若对所有的a?A，有(a,a)??，则称?为自反关系； 反自反关系 若对所有的a?A，有(a,a)??，则称?为反自反关系； 对称关系 对任意a,b?A，若有(a,b)??，就必有(b,a)??，则称?为对称关系； 反对称关系 对任意a,b?A，若有(a,b)??，(b,a)??，就必有a=b，则称?为反对称关系； 传递关系 对任意a,b,c? A，若有(a,b)??，(b,c)??，就必有(a,c)??，则称?为传递关系。 例1 设 ，  （1）自反与反自反 自反 自反 非自反、非反自反 反自反 （2）对称与反对称 对称，非反对称 非对称，反对称 非对称，非反对称 对称，反对称 可能有某种关系，既是对称的，又是反对称的。 或者既不是对称的，又不是反对称的 （3）可传递与不可传递 可传递 不可传递 可传递 二、如何利用关系矩阵和关系图来判断关系的性质 1. 关系矩阵 1 2 3 4 若 是对称的，则关系矩阵关于主对角线对称。 若 是反对称的，则关系矩阵中，关于主对角线对称的每一对元素不同时为1。 若 是自反的，则关系矩阵的主对角线上的所有元素均为1。 若 是反自反的，则关系矩阵的主对角线上所有元素均为0。 2. 关系图 若 是自反的，则关系图中每一结点引出一个指向自身的单边环。 若 是反自反的，则关系图中每一结点均没有单边环。 自反 反自反 若 是对称的，则在关系图中，若两结点之间存在有边，则必存在两条方向相反的边。 若 是反对称的，则在关系图中，任意两个不同的结点间至多只有一条边。 对称 反对称 若 是可传递的，则在关系图中，若每当有边由 指向 ，且又有边由