左孝凌离散数学课件3.6关系的性质

《左孝凌离散数学课件3.6关系的性质》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/10/181离散数学(DiscreteMathematics)2021/10/1813.6关系的性质一、自反性与反自反性二、对称性与反对称性三、传递性1.自反性设R为定义在A上的二元关系，即RAA,如果对于每一个xA，有xRx(R)，则称二元关系R是自反的。R在A上是自反的(x)(xAxRx)R在A上是非自反的(x)(xAR)例如，在实数集合中，“”是自反的，因为对于任意实数xx成立。平面上三角形的全等关系是自反的一、自反性与反自反性1.自反性例：设集合

2、A={a,b,c}上有下列关系：R1={,,,,}R2={,,}R3={,}R4=A上的空关系=Φ分析它们的自反性，并画出关系图和关系矩阵一、自反性与反自反性110010101010001100100001000000000000自反1.自反性一、自反性与反自反性特点：具有自反性的关系矩阵主对角线元素全是1；关系图上每个节点都有自回路思考：具有自反性的关系与恒等关系有何区别和联系2.反自反性：设RAA,如果对于

3、每一个xA，有R，则称二元关系R是反自反的。R在A上是反自反的(x)(xAR)R在A上是非反自反的(x)(xAxRx)一、自反性与反自反性2.反自反性例：设集合A={a,b,c}上有下列关系：R1={,,,,}R2={,,}R3={,}R4=A上的空关系=Φ分析它们的反自反性，并画出关系图和关系矩阵一、自反性与反自反性1100101010100011001000010000

4、00000000反自反既非自反也非反自反反自反2.反自反性一、自反性与反自反性特点：对于关系矩阵，其主对角线元素全是0；对于关系图，其每个节点都没有自回路2.反自反性一、自反性与反自反性注意：如果R不是自反关系，则R未必一定是反自反关系，有可能既非自反关系，也非反自反关系，如R3；一个非空集合上的关系不能既是自反关系，又是反自反关系。结论：R是A上的关系，则：1）R是自反关系的充要条件是IAR;2）R是反自反关系的充要条件是R∩IA=Φ;1.对称性：设RAA,如果对于每个x,yA,每当xRy，则必有yRx

5、，则称集合A上的关系R是对称的。R在A上对称(x)(y)(xAyAxRyyRx)R非对称(x)(y)(xAyAxRyyRx)例如，实数集R上的“=”，三角形的相似关系，朋友关系都是对称的。二、对称性与反对称性1.对称性：设RAA,如果对于任意x,yA,每当xRy，则必有yRx，则称集合A上的关系R是对称的。R在A上对称(x)(y)(xAyAxRyyRx)R非对称(x)(y)(xAyAxRyyRx)例：设集合A={a,b,c}上有下列关系：R1=

6、{,}R2={,,}R3={,}R4={,,}R5={,}R6=Φ二、对称性与反对称性√√√√××1.对称性例：设集合A={a,b,c}上有下列关系：R1={,}R2={,,}R3={,}R4={,,}R5={,}R6=Φ二、对称性与反对称性010100000010001010

7、100010000100010001010000010对称对称对称对称1.对称性特点：具有对称性的关系矩阵关于主对角线对称关系图的特点是任何两个不同的节点之间，或者是一来一回两条弧，或者是没有弧。是否有自回路，对对称没有影响。即：R是对称的MR是对称的GR的任何两个顶点之间若有边,则必有两条方向相反的有向边二、对称性与反对称性2.反对称性：设RAA,如果对于每个x,yA,每当xRy和yRx，必有x=y，则称集合A上的关系R是反对称的。R是反对称的(x)(y)(xAyAxRyyRxx=y

8、)(x)(y)(xAyAx≠yxRyyRx)R非反对称(x)(y)(xAyAxRyyRxxy)例如，实数集合R上的“≤”、“≥”集合上的“”关系，都是反对称的。二、对称性与反对称性2.反对称性：例：设集合A={a,b,c}上有下列关系，考察其反对称性R1={,}R2={,,}R3={