离散数学课件：3-5 二元关系的性质

1、 以下设以下设R是集合是集合A上的一个二元关系，讨上的一个二元关系，讨论论R的几个性质：的几个性质：&自反性；自反性；&对称性；对称性；&传递性；传递性；&反自反性；反自反性；&反对称性反对称性.若对若对A中的任意中的任意x, 有有xRx，则称，则称R是是自反自反的的.(一一) 自反自反(reflexive)性性R是自反的是自反的 ( x)(x AxRx) MR主对角元全为主对角元全为1 GR每一结点有每一结点有自回路自回路.例如，设例如，设A=1, 2, 3, 4，R为为“ ”，则，则RM 11110111001100011234五、二元关系的性质五、

2、二元关系的性质 若对任意若对任意x, y A，每当，每当xRy，就有，就有yRx，则，则称称R是是对称对称的的.(二二) 对称对称(symmetric)性性R是对称的是对称的 ( x)( y)(x A y A xRy yRx) MR是对称矩阵是对称矩阵 GR有向边成对出现有向边成对出现(若有若有a到到b的弧，的弧，则必有则必有b到到a的弧的弧)例如，例如，RM 010101011123五、二元关系的性质五、二元关系的性质 若对任意若对任意x, y, z A，每当，每当xRy, yRz，就有，就有xRz，则则称称R是是传递传递的的.(三三) 传递传递(transitive)性性R是传递的是传递的

3、 ( x)( y) ( z)(x A y A z A xRy yRz xRz) GR中若从中若从a到到b有一条路径，则从有一条路径，则从a到到b有一条弧有一条弧.例如，例如，RM 01110010000000011234五、二元关系的性质五、二元关系的性质(四四) 反自反反自反(irreflexive)性性R是反自反的是反自反的 MR主对角元全为主对角元全为0 GR每一结点每一结点无自回路无自回路.例如，例如，RM 0110001000000010若对若对A中的任意中的任意x, 有有xRx，则称，则称R是是反自反反自反的的. ( x)(x AxRx)1234五、二元关系的性质五、二元关系的性质

4、反自反反自反(irreflexive)性性&关系矩阵的主对角元不全为关系矩阵的主对角元不全为1，所以不是，所以不是“自反自反”的；的；&关系矩阵的主对角元不全为关系矩阵的主对角元不全为0，所以不是，所以不是“反自反反自反”的的.F“自反自反”的否定不是的否定不是“反自反自反反”.一个不是自反的关系，一定就是反自反吗？一个不是自反的关系，一定就是反自反吗？不一定不一定.例如，例如，RM 10101010000100011234五、二元关系的性质五、二元关系的性质反自反反自反(irreflexive)性性 设集合设集合A=R|R为自反的关系为自反的关系， B=R|R为为反自反的关系

5、反自反的关系，则，则A和和B的关系如下图所示：的关系如下图所示：EAB五、二元关系的性质五、二元关系的性质 若对任意若对任意x, y A，每当，每当xRy和和yRx，必有，必有x=y，则，则称称R是是反反对称对称的的.(五五) 反对称反对称(antisymmetric)性性R是反对称的是反对称的 ( x)( y)(x A y A xRy yRx x=y) ( i)( j)(i, j 1, 2, ,n (i j) (aji=1) aij=0) GR中若有中若有a到到b的弧，则的弧，则必没有必没有b到到a的弧的弧例如，例如，RM 00111010000100011234五、二元关系的性质五、二元关

6、系的性质反对称反对称(antisymmetric)性性关系关系R既不是对称的，也不是反对称的；既不是对称的，也不是反对称的；F“对称对称”的否定不是的否定不是“反对称反对称”.F不具备对称性的关系称为不具备对称性的关系称为非对称非对称 (asymmetric) 关系关系.一个不是对称的关系，一定就是反对称吗？一个不是对称的关系，一定就是反对称吗？不一定不一定.例如，例如，RM 011000100123五、二元关系的性质五、二元关系的性质反对称反对称(antisymmetric)性性 设集合设集合A=R|R为对为对称的关系称的关系， B=R|R为为反对称的关系反对称的关系，则，则A和和B的关系如

7、右图所示：的关系如右图所示：存在某种关系，既是对称的，又是反对称的吗？存在某种关系，既是对称的，又是反对称的吗？存在存在.例如，例如，RM 100010001123EAB五、二元关系的性质五、二元关系的性质给定给定A=1, 2, 3, 4，考虑，考虑A上的关系上的关系R，若，若R=, , , , ，(a)在在A A的坐标图中标出的坐标图中标出R，并绘出它的关系图；，并绘出它的关系图；(b) R是是i) 自反的，自反的，ii)反自反的，反自反的，iii) 对称的，对称的， iv)反反对称的，对称的，v) 可传递的吗？可传递的吗？解：解： (1)见下图见下图.五、二元关系的性质五、二元关系的性质1234坐标图坐标图关系图关系图(2)R是反自反、反对称和可传递的；不是自反或是反自反、反对称和可传递的；不是自反或对称的对称的. 判断以下判断以下整数集整数集(Z)上的关系是否自反、反自上的关系是否自反、反自反、对称、反对称、传递反、对称、反对称、传递.关系关系自反自反反自反反自反对称对称反对称反对称传递传递空关系空关