《左孝凌离散数学课件3.6关系的性质》由会员分享，可在线阅读，更多相关《左孝凌离散数学课件3.6关系的性质（29页珍藏版）》请在金锄头文库上搜索。
1、2019/1/31,1,离散数学(Discrete Mathematics),2019/1/31,1,3.6 关系的性质,一、自反性与反自反性 二、对称性与反对称性 三、传递性,1.自反性 设R为定义在A上的二元关系，即RAA, 如果对于每一个xA，有xRx (R)，则称二元关系R是自反的。 R在A上是自反的 (x)( xA xRx) R在A上是非自反的 (x)( xA R) 例如，在实数集合中，“”是自反的，因为对于任意实数xx成立。 平面上三角形的全等关系是自反的,一、自反性与反自反性,1.自反性 例：设集合A=a,b,c上有下列关系： R1=, R2=, R3=, R4=A上的空关系=
2、分析它们的自反性，并画出关系图和关系矩阵,一、自反性与反自反性,1 1 0 0 1 0 1 0 1,0 1 0 0 0 1 1 0 0,1 0 0 0 0 1 0 0 0,0 0 0 0 0 0 0 0 0,自反,1.自反性,一、自反性与反自反性,特点： 具有自反性的关系矩阵主对角线元素全是1； 关系图上每个节点都有自回路 思考： 具有自反性的关系与恒等关系有何区别和联系,2.反自反性：设RAA, 如果对于每一个xA，有R，则称二元关系R是反自反的。 R在A上是反自反的 (x)(xA R ) R在A上是非反自反的 (x)( xA xRx),一、自反性与反自反性,2.反自反性 例：设集合A=a,
3、b,c上有下列关系： R1=, R2=, R3=, R4=A上的空关系= 分析它们的反自反性，并画出关系图和关系矩阵,一、自反性与反自反性,1 1 0 0 1 0 1 0 1,0 1 0 0 0 1 1 0 0,1 0 0 0 0 1 0 0 0,0 0 0 0 0 0 0 0 0,反自反,既非自反也非反自反,反自反,2.反自反性,一、自反性与反自反性,特点： 对于关系矩阵，其主对角线元素全是0； 对于关系图，其每个节点都没有自回路,2.反自反性,一、自反性与反自反性,注意： 如果R不是自反关系，则R未必一定是反自反关系，有可能既非自反关系，也非反自反关系，如R3； 一个非空集合上的关系不能既
4、是自反关系，又是反自反关系。 结论： R是A上的关系，则： 1）R是自反关系的充要条件是IA R; 2）R是反自反关系的充要条件是RIA =;,1.对称性： 设RAA, 如果对于每个x,yA,每当 xRy，则必有 yRx，则称集合A上的关系R是对称的。 R在A上对称(x)(y)(xAyA xRyyRx) R非对称 (x)(y)(xAyA xRyyRx) 例如，实数集R上的“=”，三角形的相似关系，朋友关系都是对称的。,二、对称性与反对称性,1.对称性： 设RAA, 如果对于任意x,yA,每当 xRy，则必有 yRx，则称集合A上的关系R是对称的。 R在A上对称(x)(y)(xAyA xRyyR
5、x) R非对称 (x)(y)(xAyA xRyyRx) 例：设集合A=a,b,c上有下列关系： R1=, R2=, R3=, R4=, R5=, R6=,二、对称性与反对称性,1.对称性 例：设集合A=a,b,c上有下列关系： R1=, R2=, R3=, R4=, R5=, R6=,二、对称性与反对称性,0 1 0 1 0 0 0 0 0,0 1 0 0 0 1 0 1 0,1 0 0 0 1 0 0 0 0,1 0 0 0 1 0 0 0 1,0 1 0 0 0 0 0 1 0,对称,对称,对称,对称,1.对称性 特点： 具有对称性的关系矩阵关于主对角线对称 关系图的特点是任何两个不同的节
6、点之间，或者是一来一回两条弧，或者是没有弧。是否有自回路，对对称没有影响。 即：R是对称的 MR是对称的 GR的任何两个顶点之间若有边, 则必有两条方向相反的有向边,二、对称性与反对称性,2.反对称性： 设RAA,如果对于每个x,yA,每当 xRy和yRx，必有x=y，则称集合A上的关系R是反对称的。 R是反对称的 (x)(y)(xAyA xRy yRx x=y ) (x)(y)(xAyA xy xRy yRx ) R非反对称 (x)(y)(xA yA xRy yRx xy) 例如，实数集合R上的“”、“”集合上的“”关系，都是反对称的。,二、对称性与反对称性,2.反对称性： 例：设集合A=a
7、,b,c上有下列关系，考察其反对称性 R1=, R2=, R3=, R4=, R5=, R6=,二、对称性与反对称性,2.反对称性 例：设集合A=a,b,c上有下列关系： R1=, R2=, R3=, R4=, R5=, R6=,二、对称性与反对称性,0 1 0 1 0 0 0 0 0,0 1 0 0 0 1 0 1 0,1 0 0 0 1 0 0 0 0,1 0 0 0 1 0 0 0 1,0 1 0 0 0 0 0 1 0,既非对称也非反对称,反对称,反对称,反对称,反对称,R1=， R2=， R3=， R4=，,对称的,是对称的也是反对称的,不是对称的也不是反对称的，,反对称的,2.反对
8、称性 特点： 具有反对称性的关系矩阵如果在非对角元上rij=1，则在其对称位置上，rji=0 ，即rji和rij（ ij ）这两个数至多有一个是1，但允许两个均为0 关系图上任何两个不同的节点之间，至多有一条弧，但允许没有弧 即：R是反对称的 在MR中, xi xj( ij rij=1rji=0) 在GR中, xi xj (ij), 若有有向边, 则必没有。,二、对称性与反对称性,说明：反对称性的等价说法 x,y A,如x y且 R,则必有 R 即两个不同点结点间不允许有两条弧； 总结： 有些关系既不是对称的，也不是反对称的； 有些关系既是对称的，也是反对称的； 空关系、恒等关系既是对称的，也
9、是反对称的； 全关系EA不是反对称的。,二、对称性与反对称性,三、传递性,定义：设RAA, 如果对于任意的x,y,zA, 每当xRy， yRz 时就有xRz ，称关系R在A上是传递的。 R在A上是传递的 (x)(y)(z)(xAyAzAxRy yRz xRz) R非传递 (x)(y)(z)(xAyAzAxRy yRzxRz)。 例如，实数集R上的“”“”“”“”以及集合上的“”,三、传递性,定义：设RAA, 如果对于任意的x,y,zA, 每当xRy， yRz 时就有xRz ，称关系R在A上是传递的。 R在A上是传递的 (x)(y)(z)(xAyAzAxRy yRz xRz) R非传递 (x)(
10、y)(z)(xAyAzAxRy yRzxRz)。,例：设A=a,b,c考擦下列关系的传递性 R1=, R2= R3=,三、传递性,特点： 如果R是传递关系，如果结点x能通过有向弧组成的有向路通向结点z，（该有向路包含两条或两条以上的弧）则x必须有有向弧直接指向z，否则R就不是传递的； 传递关系的关系矩阵的特点不是很容易看出，后面会讲到,三、传递性,定理1： 如果R是传递关系，如果结点x能通过有向弧组成的有向路通向结点z，（该有向路包含两条或两条以上的弧）则x必须有有向弧直接指向z，否则R就不是传递的； 传递关系的关系矩阵的特点不是很容易看出，后面会讲到,有人说：集合A上的关系R，如果是对称且传
11、递的，则它也是自反的。其理由是，从aRb，由对称性得bRa，再由传递性得aRa，你说对吗？为什么？,不对！再看自反性、对称性、传递性的定义。,自反性： 设R是集合X上的二元关系，如果对于每一个xX，有R，则称R是自反的。,对称性： 设R是集合X上的二元关系，如果对于每一个x，yX，每当R，就有R，则称R是对称的。,传递性： 设R是集合X上的二元关系，如果对于任意x,y,zX，每当R，R时就有R，则称R是传递的。,自反性是说对于每一个xX，有R。对称性是说每当R，就有R，没有要求对于每一个xX，传递性是说每当R，R时就有R ，也没有要求对于每一个xX。因此不能从一个关系是对称且传递的推出它是是自反的。,例如A=a，b，c， R=，是A上的一个二元关系，R是对称且传递的，但R不是自反的，因为对于cA，没有 R。,非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，反对称的和传递的。 非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。,112页 例题4 设某人有三个儿子，组成集合A=T,G,H，在A上的兄弟关系具有哪些性质。 例题5 集合I=1,2,3,4，I上的关系 R=,讨论R的性质。,练习 113页(1),(2) ,(3) ,(5),作业 113页(4) 114页(6),
