自反性和反自反性课件

3-6关系的性质

本节讨论集合X上的二元关系R的一些特殊性质。3-6关系的性质本节讨论集合X上的二元关系1一、自反性和反自反性1、自反性：设R是集合X上的二元关系，如果对于每一个xX，有<x，x>R，则称R是自反的。R在X上自反(x)(xX<x，x>R)2、反自反性：设R是集合X上的二元关系，如果对于每一个xX，有<x，x>R，则称R是反自反的。R在X上反自反(x)(xX<x，x>R)一、自反性和反自反性2例如，在实数集合中，””是自反的，因为对于任意实数xx成立。

平面上三角形的全等关系是自反的。例：X={a，b，c}，R1={<a，a>，<b，b>，<c，c>，<a，b>，<c，a>}是自反的，R2={<a，b>，<b，c>，<c，a>}是反自反的，R3={<a，a>，<b，c>}不是自反的也不是反自反的。注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。例如，在实数集合中，””是自反的，因为对于任意实数xx成33、关系矩阵的特点自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素均为0。4、关系图的特点自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。3、关系矩阵的特点45、结论：R是X上的二元关系，则：(1)R是自反关系的充要条件是IXR。(2)R是反自反关系的充要条件是RIX=。如果|X|=n，其中n个序偶为<x，x>，则X上的自反关系共有2n*n-n个。例|X|=3，X上关系共有29个，而自反关系共有26个。5、结论：5二、对称性和反对称性1、对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当<x，y>R，就有<y，x>R，则称R是对称的。R在X上对称(x)(y)(xXyX<x,y>R<y,x>R)2、反对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当<x，y>R和<y，x>R必有x=y，则称R是反对称的。R在X上反对称(x)(y)(xXyX<x,y>R<y,x>Rx=y)二、对称性和反对称性6例如，平面上三角形的相似关系是对称的。例：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>}是反对称的。注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。例如，平面上三角形的相似关系是对称的。73、关系矩阵和关系图的特点对称关系的关系矩阵是对称矩阵，即对所有i，j，rij＝rji，对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上rij＝1，则在其对称位置上rji＝0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。3、关系矩阵和关系图的特点8三、传递性1、定义：设R是集合X上的二元关系，如果对于任意x，y，zX，每当<x，y>R，<y，z>R时就有<x，z>R，则称R是传递的。R在X上传递(x)(y)(z)(xXyXzX<x,y>R<y,z>R<x,z>R)例：R1={<x,y>,<z,x>,<z,y>}是传递的，R2={<x,b>,<c,d>}也是传递的，它没有违背定义。R3={<x,b>,<b,x>}不是传递的。三、传递性92、定理：设R、S是A上的传递关系，则RS也是A上的传递关系。注意：R、S均是传递的，但RS未必是传递的。例：R={<a，b>}，S={<b，c>}，则R、S均是传递的，但RS={<a，b>，<b，c>}不是传递的。证明：设<x,y>RS，<y,z>RS，则<x,y>R，<y,z>R且<x,y>S，<y,z>S。因为R、S是A上的传递关系，所以<x,z>R，<x,z>S，从而<x,z>RS，即RS是A上的传递关系。2、定理：设R、S是A上的传递关系，则RS也是A上的传递关10有人说：集合A上的关系R，如果是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa，你说对吗？为什么？不对！再看自反性、对称性、传递性的定义。有人说：集合A上的关系R，如果是对称且传递的，则11自反性：设R是集合X上的二元关系，如果对于每一个xX，有<x，x>R，则称R是自反的。对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当<x，y>R，就有<y，x>R，则称R是对称的。传递性：设R是集合X上的二元关系，如果对于任意x,y,zX，每当<x，y>R，<y，z>R时就有<x，z>R，则称R是传递的。自反性：对称性：传递性：12自反性是说对于每一个xX，有<x，x>R。对称性是说每当<x，y>R，就有<y，x>R，没有要求对于每一个xX，传递性是说每当<x，y>R，<y，z>R时就有<x，z>R，也没有要求对于每一个xX。因此不能从一个关系是对称且传递的推出它是是自反的。例如A={a，b，c}，R={<a,a>，<b,b>，<a,b>，<b,a>}是A上的一个二元关系，R是对称且传递的，但R不是自反的，因为对于cA，没有<c,c>R。自反性是说对于每一个xX，有<x，x>R。对13非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。非空集合上的空关系是反自反的，对称的，反对称的和14112页例题4设某人有三个儿子，组成集合A={T,G,H}，在A上的兄弟关系具有哪些性质。例题5集合I={1,2,3,4}，I上的关系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>}讨论R的性质。练习113页(1),(2),(3),(5)112页练习15作业113页(4)114页(6)作业163-6关系的性质

本节讨论集合X上的二元关系R的一些特殊性质。3-6关系的性质本节讨论集合X上的二元关系17一、自反性和反自反性1、自反性：设R是集合X上的二元关系，如果对于每一个xX，有<x，x>R，则称R是自反的。R在X上自反(x)(xX<x，x>R)2、反自反性：设R是集合X上的二元关系，如果对于每一个xX，有<x，x>R，则称R是反自反的。R在X上反自反(x)(xX<x，x>R)一、自反性和反自反性18例如，在实数集合中，””是自反的，因为对于任意实数xx成立。

平面上三角形的全等关系是自反的。例：X={a，b，c}，R1={<a，a>，<b，b>，<c，c>，<a，b>，<c，a>}是自反的，R2={<a，b>，<b，c>，<c，a>}是反自反的，R3={<a，a>，<b，c>}不是自反的也不是反自反的。注意：R不是自反的，未必一定是反自反的。一个关系可能既不是自反的，也不是反自反的。例如，在实数集合中，””是自反的，因为对于任意实数xx成193、关系矩阵的特点自反关系的关系矩阵的对角元素均为1，反自反关系的关系矩阵的对角元素均为0。4、关系图的特点自反关系的关系图，每个结点均有自回路，而反自反关系的关系图，每个结点均没有自回路。3、关系矩阵的特点205、结论：R是X上的二元关系，则：(1)R是自反关系的充要条件是IXR。(2)R是反自反关系的充要条件是RIX=。如果|X|=n，其中n个序偶为<x，x>，则X上的自反关系共有2n*n-n个。例|X|=3，X上关系共有29个，而自反关系共有26个。5、结论：21二、对称性和反对称性1、对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当<x，y>R，就有<y，x>R，则称R是对称的。R在X上对称(x)(y)(xXyX<x,y>R<y,x>R)2、反对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当<x，y>R和<y，x>R必有x=y，则称R是反对称的。R在X上反对称(x)(y)(xXyX<x,y>R<y,x>Rx=y)二、对称性和反对称性22例如，平面上三角形的相似关系是对称的。例：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>}是反对称的。注意：存在关系既不是对称的，也不是反对称的。也存在关系既是对称的，也是反对称的。例如，平面上三角形的相似关系是对称的。233、关系矩阵和关系图的特点对称关系的关系矩阵是对称矩阵，即对所有i，j，rij＝rji，对称关系的关系图，任何两个不同的结点之间，或者有双向两条弧，或者没有弧。反对称关系的关系矩阵，如果在非对角元上rij＝1，则在其对称位置上rji＝0，反对称关系的关系图，任何两个不同的结点之间至多有一条弧。3、关系矩阵和关系图的特点24三、传递性1、定义：设R是集合X上的二元关系，如果对于任意x，y，zX，每当<x，y>R，<y，z>R时就有<x，z>R，则称R是传递的。R在X上传递(x)(y)(z)(xXyXzX<x,y>R<y,z>R<x,z>R)例：R1={<x,y>,<z,x>,<z,y>}是传递的，R2={<x,b>,<c,d>}也是传递的，它没有违背定义。R3={<x,b>,<b,x>}不是传递的。三、传递性252、定理：设R、S是A上的传递关系，则RS也是A上的传递关系。注意：R、S均是传递的，但RS未必是传递的。例：R={<a，b>}，S={<b，c>}，则R、S均是传递的，但RS={<a，b>，<b，c>}不是传递的。证明：设<x,y>RS，<y,z>RS，则<x,y>R，<y,z>R且<x,y>S，<y,z>S。因为R、S是A上的传递关系，所以<x,z>R，<x,z>S，从而<x,z>RS，即RS是A上的传递关系。2、定理：设R、S是A上的传递关系，则RS也是A上的传递关26有人说：集合A上的关系R，如果是对称且传递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa，你说对吗？为什么？不对！再看自反性、对称性、传递性的定义。有人说：集合A上的关系R，如果是对称且传递的，则27自反性：设R是集合X上的二元关系，如果对于每一个xX，有<x，x>R，则称R是自反的。对称性：设R是集合X上的二元关系，如果对于每一个x，yX，每当<x，y>R，就有<y，x>R，则称R是对称的。传递性：设R是集合X上的二元关系，如果对于任意x,y,zX，每当<x，y>R，<y，z>R时就有<x，z>R，则称R是传递的。自反性：对称性：传递性：28自反性是说对于每一个xX，有<x，x