离散数学-3-6关系的性质.ppt

1、1、第三章集合和关系，3-6关系的性质课程师：李朔email :2，2，1，自反性，P110定义3-6.1作为a上的二元关系，如果每个xX有xRx，则二元关系r是自反这个r是x上的自反(x)(xX xRx )，例如： 这是因为对于任意的实数xx都成立。 设r为x上的自反关系，则可以看出r的关系矩阵MR的主对角线都是1的图的各个节点都有自环。 例如，a=1、2、3、r=1、1、2、2、3、3、1、2是自然相反的。 其关系图和关系矩阵如下图所示。 MR=、3、二、对称性，定义3-6.2把r作为a上的二元关系，如果每x、yX有xRy，则把二元关系r称为对称。 r在x上对称r在x上对称(x)(y)(x

2、XyXxRy yRx )例如，在平面上的三角形集合中的相似关系是对称的。 可知r是x上的对称关系，r的关系矩阵MR是对称排列。 在r的关系图中，如果在两个节点之间具有边缘，则必须具有相反方向的两个边缘。 例如，a=1，2，3，r4=1，2，2，1，3，3是对称的，其关系图和关系矩阵的特征是图、MR=、4，3、传递性，作为pp的r在x上是对称的(x)(y)(z)(xXyXzXxRyyRz xRz )例：在实数集上、5、练习，例如A=a、b、c、R=、是a上的二项关系，关系r具有什么性质？ 为什么？ a:r是对称传递的，而r不是自反的。 因为cA没有r。 6、练习、集合a上的关系r，如果是对称传达

3、的话，据说也是相反的。 其理由是，从aRb得到了bRa，从对称性得到了传递性得到了aRa。 你是对的吗？ 为什么？ a :不是。因为不是各自的a，所以aRa成立。 7、自我反性是指每个xX都有一个r。 所谓对称性，就是每个r都有r，不需要每个xX求出。 所谓传达性，是指r、r各有r，而不是xX各有所求。 因此，不能从一个关系对称地传达。 那个是自我相反的。8、4、逆自反性，P111定义3-6.4将r设为a以上的二元关系，如果每xX有r，则二元关系r称为逆自反。 r在x中逆自反(x)(xX R )数比关系大，日常生活中的父子关系是逆自反的。 设r为x上的逆自反关系，则可知r的关系矩阵MR的主对角

4、线都为0，在r的关系图中任何节点上都没有自我电路。 例如，如果将x=1，2，3，x上的二元关系r=1，2，2，3，3，1，r设为逆自反，则其关系图如、MR=、9，4所示，其关系图和关系矩阵如下图所示。 注意：一个不是自反的关系可能不一定自反也可能相反，10，5，反对称性，定义3-6.5把r作为a上的二项关系，每次x，yX有xRy和yRx就需要x。 可知r在x上将反对称(x)(y)(xxyxryyrxrxy)r设为x上的反对称关系，在r的关系矩阵MR中不能在以主对角线为轴的对称位置上同时设为1 (主对角线除外)。 在r关系图中，两个不同节点之间不能有反向的两条边。 在自回路的主对角线上可以存在的

5、是1。 所以有对称和反对对称的关系。 P112例如将x=1、2、3、x上的二维关系r=1、2、2、3、3、3、r设为反对称。其关系图中，关系矩阵为，MR=，11，思考练习，例.集合a=1，2，3上的以下关系： R=，S=，T=， 12、思考练习、例.集合a=1、2、3上的如下关系： R=、S=、T=、空关系AA=给出全域关系，分别判断具有怎样的性质，具有既不对称也不反对称的3传递性关系也是对称的，是反对称的。 14、思考练习、非空集上的空关系具有怎样的性质a :反自反、对称、反对称、传达，但不是自反。 非空集合的全球关系有哪些性质？ a :自反、对称、传达，但不是自反、反对称。 15、考虑练习

6、，如果r、s是a上的传达关系，则证明RS也是a上的传达关系。 证明：假设为RS、RS，则为r、r且为s、s。 由于r，s是a上的传递关系，所以r，s，因此RS，即RS是a上的传递关系。16、考虑练习，注意： r、s都被传输，而RS不一定被传输。 示例： R=、S=、r、s全部传播，而RS=、不传播。 17、思考练习，例如.给定的s=1、2、3、4和s上的关系R=、说明r是不可传递的.找到包括r在内的关系，R1是可传递的，可以找到另一个，R2也是同样的解：r，但是r不传递. R1=。 当添加了另外一个元素时，另外一个传达的关系R2=，可以是，、的、的、的、的、元素、元素、元素、元素、元素、元素、

7、元素、元素、元素、元素。 只有和在r中的情况下，一定在r中。证明：十分性。1r显然r (自我反向性)=R (条件)=R具有对称性。2是R=，r (对称性)=R=传递性成立的2 s=1，1，1，2，2，1 t=1，2，1，3 u=1，3 s是a上的对称关系。 1、2和2、1都是s元素，因此s不是a上的反对称关系。 因为1、2t、2、1t，所以t不是a上的对称关系。 t是a上的反对称关系。 u不是a上的对称关系，也不是a上的反对称关系。 20、思考练习，例子r为实数集合，S=x，y|xRyRx=y为实数集合上的等价关系。 证明实数集合上的相等关系被传达了。 证明： xR、yR、zR、x、yS以及y、zS根据