离散数学3-6关系的性质和3-7复合关系

《离散数学3-6关系的性质和3-7复合关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics陈明Email:mingchen_gang@163.com信息科学与工程学院二零一一年十月1、序偶：记作2、笛卡尔积：记作AB3、关系：序偶的集合；前域、值域4、X到Y的关系，X上的关系5、关系的表示：关系矩阵、关系图回顾ρ1＝｛<-2,-2>,<-1,-1>,<0,0>,<1,1>，<-1,0>,<0,-1>,<1,-2>,<-2,1>｝设A＝｛-2,-1,0,1｝3-6关系的性质一、自反性和反自反性1、自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是自反的。R在X上自反(x)(xX<

2、x，x>R)2、反自反性：设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是反自反的。R在X上反自反(x)(xXR)例如，在实数集合中，””是自反的，因为对于任意实数xx成立。平面上三角形的全等关系是自反的。例：X={a，b，c}，R1={，，，，}R2={，，}R3={，}注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。3、关系矩阵的特点自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素

3、均为0。4、关系图的特点自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。5、结论(两个充要条件)R是X上的二元关系，则：(1)R是自反关系的充要条件是IXR；(2)R是反自反关系的充要条件是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

4、)(y)(xXyXRRx=y)二、对称性和反对称性例如，平面上三角形的相似关系是对称的。例：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＝

5、1，则在其对称位置上rji＝0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。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上的传递关系。注意：R、S均是传递

6、的，但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，如果是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa，你说对吗？为什么？不对！再看自反性、对称性、传递性的定义。自反性：设R是集合X上的二元关系，如果对于每一个x

7、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，传递性是说每当R，