离散数学第四章(第2讲)课件.ppt

1、3 关系的性质关系的性质自反性自反性根据根据R的关系矩阵和关系图，也可以判断的关系矩阵和关系图，也可以判断R是自反的。是自反的。定义定义 设是集合设是集合A A中的二元关系，对于任中的二元关系，对于任xAxA,R,R,即即 x(x(x x A A RR），），则称是自反关系。则称是自反关系。思考：集合思考：集合A 上的恒等关上的恒等关系系IA与与R的自反性有什么联的自反性有什么联系？系？001010110RM例：设A=a,b,c,R=是自反的。例：设X=1,2,3,1,22,11S2,12S1,23S000100000,000000010,000100010321SSSMMM2反自反性反自反性

2、定义定义 设是集合设是集合A A中的二元关系，对于任中的二元关系，对于任xAxA,R,R,即即 x(x(x x A A R R），），则称是反自反关系。则称是反自反关系。2,31,31,21,14S110100100RMS4既不是自反的，又不是反自反的既不是自反的，又不是反自反的思考：集合思考：集合A 上的恒等关系上的恒等关系IA与与R的反自反性有什么联系？的反自反性有什么联系？3对称性对称性定义定义：设：设R是是A中的二元关系，对于每一个中的二元关系，对于每一个x x，yAyA,如果如果每当有每当有xRy，则必有，则必有yRx，则称，则称R是是A中的对称关系中的对称关系.例：设例：设A=1,

3、2,3,R=,则则R是对称的关系是对称的关系.010101110RM思考：思考：RC与与R的对称性有什么联系？的对称性有什么联系？x x y(y(x x A A y y A A xRyxRy yRxyRx）定义定义1：设：设R是是A集合中的二元关系，对于每一个集合中的二元关系，对于每一个x x，yAyA,如果每当如果每当xRy和和yRx就必有就必有x=y，则称，则称R是反对称的关系。是反对称的关系。4反对称性反对称性即当且仅当即当且仅当 x x y(y(x x A A y y A A xRyxRy yRxyRx x=yx=y）,R,R才是反才是反对称的。对称的。例：设例：设A=a,b,c，R=

4、是反对称的。是反对称的。定义定义2：设：设R是是A集合中的二元关系，对于每一个集合中的二元关系，对于每一个x x，yAyA，如果如果xy且且xRy,则则 R R,称称R是反对称的关系。是反对称的关系。)(yRxxRyyxAyAxyx思考：思考：RC与与R的反对称性有什么联系？的反对称性有什么联系？例：设例：设A=a,b,c,R1,R2,R3都是反对称的都是反对称的,1accbbaR,2ccbbaacaR,3accbaaR100001100,001010101,100001010321RRRMMM例：例：X=a,b,c,判断下列关系是否对称的，是否反对称的。判断下列关系是否对称的，是否反对称的。

5、,1cbabbaR,2cabccbaaR010001101,00010101021RRMM这两个二元关系既不是对称的，也不是反对称的。这两个二元关系既不是对称的，也不是反对称的。5传递性传递性 思考：复合运算与思考：复合运算与R的传递性有什么联系？的传递性有什么联系？定义定义：设：设R R是是A A中的二元关系，对于每一个中的二元关系，对于每一个x x，y y，zAzA,如如果每当果每当xRyxRy yRzyRz,就必有就必有xRzxRz,则称则称R R是可传递的，并表示成：是可传递的，并表示成：x x y y z(z(x x A A y y A A z z A A xRyxRy yRzyRz

6、 xRzxRz）例：设例：设X=a,b,c，判断下列关系是否满足传递性质。，判断下列关系是否满足传递性质。,1cbcabaaaR,2baR,3cabaR4R()x y z xAyAzAxRyyRzxRz 以上关系都满足传递性质。以上关系都满足传递性质。而二元关系而二元关系R5不具有传递性不具有传递性.,5accbbaR()x y z xAyAzAxRyyRzxRz 例例:判断下列二元关系的性质。判断下列二元关系的性质。（1）设）设X=1,2,33,13,22,11R性质有：反自反，反对称，传递性质有：反自反，反对称，传递3,22,11,12R性质有：反对称性质有：反对称 3,32,21,13R性质有：自反，对称，反对称，传递性质有：自反，对称，反对称，传递 xER4性质有：自反，对称，传递性质有：自反，对称，传递 5R性质有：反自反，对称，反对称，传递性质有：反自反，对称，反对称，传递 性质有：自反，反自反，对称，反对称，传递性质有：自反，反自反，对称，反对称，传递 若X=,则X上的空关系具有什么性质？