离散数学37复合关系和逆关系38关系的闭包ppt课件.ppt

《离散数学37复合关系和逆关系38关系的闭包ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics山东科技大学信息科学与工程学院3-6关系的性质兄弟关系师生关系一、自反性和反自反性1、自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是自反的。R在X上自反(x)(xXR)2、反自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是反自反的。R在X上反自反(x)(xXR)例如，在实数集合中，””是自反的，因为对于任意实数xx成立。平面上三角形的全等关系是自反的。例：

2、X={a，b，c}，R1={，，，，}R2={，，}R3={，}注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。3、关系矩阵的特点自反关系的关系矩阵的对角元素均为1；反自反关系的关系矩阵的对角元素均为0。4、关系图的特点自反关系的关系图，每个结点均有自回路；反自反关系的关系图，每个结点均没有自回路。5、结论：R是X上的二元关系，则：(1)R是自反关系的充要条件是IXR。(2)R是

3、反自反关系的充要条件是RIX=。二、对称性和反对称性1、对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当R，就有R，则称R是对称的。R在X上对称(x)(y)(xXyXRR)2、反对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当R和R必有x=y，则称R是反对称的。R在X上反对称(x)(y)(xXyXRRx=y)例如，平面上三角形的相似关系是对称的。例：

4、R1={<1，1>，<2，3>，<3，2>}R2={<1，1>，<3，3>}R3={<2，2>，<2，3>，<3，2>，<3，1>}R4={<2，2>，<2，3>，<3，1>}注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。3、关系矩阵和关系图的特点对称关系的关系矩阵是对称矩阵，即对所有i，j，rij＝rji；对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上rij＝1，则在其对称位置上rji＝0反对称关系的关系图，任何两

5、个不同的结点之间至多有一条弧。三、传递性1、定义：设R是集合X上的二元关系，如果对于任意x，y，zX，每当R，R时就有R，则称R是传递的。R在X上传递(x)(y)(z)(xXyXzXRRR)例：R1={,,}是传递的，R2={,}也是传递的，它没有违背定义。R3={,}不是传递的。2、定理：设R、S是A上的传递关系，则RS也是A上的传递关系。注意

6、：R、S均是传递的，但RS未必是传递的。例：R={}，S={}，则R、S均是传递的，但RS={，}不是传递的。证明：设RS，RS，则R，R且S，S。因为R、S是A上的传递关系，所以R，S，从而RS，即RS是A上的传递关系。综合练习：集合A上的关系R，如果R是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa。你说对吗？为什么

7、？不对！再看自反性、对称性、传递性的定义。自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是自反的。对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当R，就有R，则称R是对称的。传递性：设R是集合X上的二元关系，如果对于任意x,y,zX，每当R，R时就有R，则称R是传递的。自反性是说对于每一个xX，有R。对称性是说每当R，就有R，没有要求对于每一个xX，传递性是说每当

8、R，R时就有R，也没有要求对于每一个xX。因此不能从一个关系是对称且传递的推出它是是自反的。例如A={a，b，c}，R={，，，}是A上的一个二元关系，R是对称且传递的，但R不是自反的，因为对于cA，没有R。112页例题4设某人有三个儿子，组成集合A={T,G,H}，在A上的兄弟关