离散数学(3.6关系性质)

1、1张捷第三章第三章 集合与关系集合与关系（Sets and Relations)Sets and Relations) 3.6 3.6 关系的闭包运算关系的闭包运算(Closure Operations)(Closure Operations)3.7 3.7 集合的划分与覆盖集合的划分与覆盖(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等价关系等价关系(Equivalent Relations) (Equivalent Relations) 3.9 3.9 相容关系相容关系(Compatibili

2、ty(CompatibilityRelations) Relations) 3.10 3.10 序关系序关系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其运算集合及其运算(Sets & Operations with sets)(Sets & Operations with sets) 3.2 3.2 序偶与笛卡尔积序偶与笛卡尔积(Ordered Pairs & Cartesian Product)(Ordered Pairs & Cartesian Product)3.3 3.3 关系关系 (Relatio

3、ns) (Relations) 3.4 3.4 关系的性质关系的性质(The Propeties(The Propeties of Relations) of Relations) 3.5 3.5 复合关系与逆关系复合关系与逆关系(Compound Relations & Inverse(Compound Relations & Inverse Relations) Relations)BABA 3.4 3.4 关系的性质关系的性质(The properties of (The properties of Relations)Relations)3.4.13.4.1 集合集合A

4、 A上上关系的关系的性质性质( (The properties ofThe properties of Relations on set A Relations on set A) )3.4.2 3.4.2 由由关系图、关系矩阵判别关系的性质关系图、关系矩阵判别关系的性质第三章第三章 集合与关系集合与关系(Sets & Relations)第三章第三章 集合与关系集合与关系(Sets & Relations) 3.4.1 3.4.1 集合集合A A上关系的性质上关系的性质 aa 定义定义3.4.1 设设 是集合是集合A A上的关系上的关系 （1 1）若对于所有的）若对于所有的

5、，均有，均有 ，则称，则称 在在A A上是自反的上是自反的(reflexive)(reflexive)。 Aaaa （2 2）若对于所有的）若对于所有的 ，均有，均有 ，则称，则称 在在A A上是反自反的上是反自反的(antireflexive(antireflexive) ) 。 AaaaAba, （3 3）对于所有的）对于所有的 ，若每当有，若每当有 就必有就必有 ，则称则称 在在 A A 上是对称的上是对称的(symmetric)(symmetric)。 baab （4 4）对于所有的）对于所有的 ，若每当有，若每当有 和和 就就必有必有 ，则称，则称 在在 A A 上是反对称的上是反对

6、称的(antisymmetric(antisymmetric). ). Aba,baabba （5 5）对于所有的）对于所有的 ，若每当有，若每当有 和和 就必有就必有 ，则称，则称 在在 A A 上是可传递的上是可传递的(transitive)(transitive)。 Acba,bacbca例例1 1 设设 ， （1 1）自反与反自反）自反与反自反 自反自反自反自反非自反非自反反自反反自反3 , 2 , 1 , 0A3 , 3,2 , 2,1 , 1,0 , 013 , 3,3 , 2,2 , 2,1 , 1,2 , 1,0 , 023 , 3,0 , 0,1 , 232 , 1,3 ,

7、2,1 , 04),(),(),(),(233222217 （2 2）对称与反对称）对称与反对称对称，非反对称对称，非反对称非对称，反对称非对称，反对称非对称，非反对称非对称，非反对称对称，反对称对称，反对称2 , 3,3 , 2,1 , 2,2 , 1,1 , 152 , 0,1 , 3,2 , 1,1 , 162 , 2,2 , 3,2 , 1,3 , 270 , 0,2 , 2,1 , 18),(),(),(),(3212211110（3 3）可传递与不可传递）可传递与不可传递可传递可传递不可传递不可传递可传递可传递3 , 0,3 , 2,2 , 0,0 , 091 , 2,3 , 2,

8、2 , 1,1 , 1102 , 3,2 , 1,0 , 311U 自反自反反自反反自反U对称不对称不反对称反对称反对称反对称不对称不对称既对称又反对称既对称又反对称则则),(),(),(531333),(),(4424),(),(),(553515例例2 2 设设 ，A A上的关系上的关系自反自反对称对称不是反对称不是反对称5 , 4 , 3 , 2 , 1A|,是偶数baba,5 , 3,1 , 3,3 , 3,4 , 2,2 , 2,5 , 1,3 , 1,1 , 15 , 5,3 , 5,1 , 5,4 , 4,2 , 4对于任意的对于任意的 , , ， 则则 也是偶数。也是偶数。 因

9、此因此 是可传递的。是可传递的。 Acba,ncbmba2,2)(2)()(nmcbbaca),(),(),(531333),(),(),(553515则则 是是自反的、反对称的、自反的、反对称的、可传递的。可传递的。 例例3 3 设设则则 自反的、对称的、反对称的、自反的、对称的、反对称的、可传递的。可传递的。则则 自反的、反对称的、自反的、反对称的、可传递的。可传递的。,|,1baRbaba且123,|,2baRbaba且,|,3baNbaba且),(),(),(531333),(),(),(553515则则 是是自反的、对称的、自反的、对称的、可传递的。可传递的。 例例3 3（续）（续）

10、则则 反自反的、反对称的、反自反的、反对称的、可传递的。可传递的。则则 反自反的、反对称的反自反的、反对称的。546,|,4的朋友是且是人bababa,|,5的祖先是且是人bababa,|,6的父亲是且是人bababa例例4 4 是不是不自反、反自反的、对称的、反对称、自反、反自反的、对称的、反对称、可传递的。可传递的。例例5 5 全关系是全关系是自反的、对称的、自反的、对称的、可传递的。可传递的。3.4.2 3.4.2 由由关系图、关系矩阵判别关系的性质关系图、关系矩阵判别关系的性质1. 1. 关系矩阵关系矩阵 1 2 3 410000100101011114321M若若 是自反的，则关系矩

11、阵的主对角线上的所有元素是自反的，则关系矩阵的主对角线上的所有元素均为均为1 1。若若 是反自反的，则关系矩阵的主对角线上所有元素是反自反的，则关系矩阵的主对角线上所有元素均为均为0 0。 若若 是对称的，则关系矩阵关于主对角线对称。是对称的，则关系矩阵关于主对角线对称。若若 是反对称的，则关系矩阵中，关于主对角线对称是反对称的，则关系矩阵中，关于主对角线对称的元素不同时为的元素不同时为1 1。 例如，例如，2. 2. 关系图关系图 若若 是对称的，则在关系图中，若两结点之间有边，则必是对称的，则在关系图中，若两结点之间有边，则必存在两条方向相反的边。存在两条方向相反的边。 若若 是反对称的，

12、则在关系图中，任意两个不同的结点间是反对称的，则在关系图中，任意两个不同的结点间至多只有一条边。至多只有一条边。 kaiaja 若若 是自反的，则关系图中每一结点引出一个指向自身是自反的，则关系图中每一结点引出一个指向自身的单边环的单边环( (自环）。自环）。 若若 是反自反的，则关系图中每一结点均没有自环。是反自反的，则关系图中每一结点均没有自环。 若若 是可传递的，则在关系图中，若每当有边由是可传递的，则在关系图中，若每当有边由 指指向向 ，且又有边由，且又有边由 指向指向 ，则必有一条边由，则必有一条边由 指向指向 。 iakajaiajaka123例例6 6 设设 ，下面分别给出集合，下面分别给出集合A A上三个关系的上三个关系的关系图，试判断它们的性质。关系图，试判断它们的性质。 3 , 2 , 1A（2 2） 非自反，也不是反自反，非对称，反对称，非自反，也不是反自反，非对称，反对称， 可传递。可传递。 （3 3） 是自反的，对称的，可传递的，不是反自反，是自反的，对称的，可传