離散數(shù)學(3.6關系性質(zhì))

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 關系的性質(zhì)關系的性質(zhì)(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 關系的性質(zhì)關系的性質(zhì)(The properties of (The properties of Relations)Relations)3.4.13.4.1 集合集合A

4、 A上上關系的關系的性質(zhì)性質(zhì)( (The properties ofThe properties of Relations on set A Relations on set A) )3.4.2 3.4.2 由由關系圖、關系矩陣判別關系的性質(zhì)關系圖、關系矩陣判別關系的性質(zhì)第三章第三章 集合與關系集合與關系(Sets & Relations)第三章第三章 集合與關系集合與關系(Sets & Relations) 3.4.1 3.4.1 集合集合A A上關系的性質(zhì)上關系的性質(zhì) 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|,是偶數(shù)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對于任意的對于任意的 , , ， 則則 也是偶數(shù)。也是偶數(shù)。 因

9、此因此 是可傳遞的。是可傳遞的。 Acba,ncbmba2,2)(2)()(nmcbbaca),(),(),(531333),(),(),(553515則則 是是自反的、反對稱的、自反的、反對稱的、可傳遞的?？蓚鬟f的。 例例3 3 設設則則 自反的、對稱的、反對稱的、自反的、對稱的、反對稱的、可傳遞的?？蓚鬟f的。則則 自反的、反對稱的、自反的、反對稱的、可傳遞的。可傳遞的。,|,1baRbaba且123,|,2baRbaba且,|,3baNbaba且),(),(),(531333),(),(),(553515則則 是是自反的、對稱的、自反的、對稱的、可傳遞的?？蓚鬟f的。 例例3 3（續(xù)）（續(xù)）

10、則則 反自反的、反對稱的、反自反的、反對稱的、可傳遞的?？蓚鬟f的。則則 反自反的、反對稱的反自反的、反對稱的。546,|,4的朋友是且是人bababa,|,5的祖先是且是人bababa,|,6的父親是且是人bababa例例4 4 是不是不自反、反自反的、對稱的、反對稱、自反、反自反的、對稱的、反對稱、可傳遞的。可傳遞的。例例5 5 全關系是全關系是自反的、對稱的、自反的、對稱的、可傳遞的。可傳遞的。3.4.2 3.4.2 由由關系圖、關系矩陣判別關系的性質(zhì)關系圖、關系矩陣判別關系的性質(zhì)1. 1. 關系矩陣關系矩陣 1 2 3 410000100101011114321M若若 是自反的，則關系矩

11、陣的主對角線上的所有元素是自反的，則關系矩陣的主對角線上的所有元素均為均為1 1。若若 是反自反的，則關系矩陣的主對角線上所有元素是反自反的，則關系矩陣的主對角線上所有元素均為均為0 0。 若若 是對稱的，則關系矩陣關于主對角線對稱。是對稱的，則關系矩陣關于主對角線對稱。若若 是反對稱的，則關系矩陣中，關于主對角線對稱是反對稱的，則關系矩陣中，關于主對角線對稱的元素不同時為的元素不同時為1 1。 例如，例如，2. 2. 關系圖關系圖 若若 是對稱的，則在關系圖中，若兩結(jié)點之間有邊，則必是對稱的，則在關系圖中，若兩結(jié)點之間有邊，則必存在兩條方向相反的邊。存在兩條方向相反的邊。 若若 是反對稱的，

12、則在關系圖中，任意兩個不同的結(jié)點間是反對稱的，則在關系圖中，任意兩個不同的結(jié)點間至多只有一條邊。至多只有一條邊。 kaiaja 若若 是自反的，則關系圖中每一結(jié)點引出一個指向自身是自反的，則關系圖中每一結(jié)點引出一個指向自身的單邊環(huán)的單邊環(huán)( (自環(huán)）。自環(huán)）。 若若 是反自反的，則關系圖中每一結(jié)點均沒有自環(huán)。是反自反的，則關系圖中每一結(jié)點均沒有自環(huán)。 若若 是可傳遞的，則在關系圖中，若每當有邊由是可傳遞的，則在關系圖中，若每當有邊由 指指向向 ，且又有邊由，且又有邊由 指向指向 ，則必有一條邊由，則必有一條邊由 指向指向 。 iakajaiajaka123例例6 6 設設 ，下面分別給出集合，下面分別給出集合A A上三個關系的上三個關系的關系圖，試判斷它們的性質(zhì)。關系圖，試判斷它們的性質(zhì)。 3 , 2 , 1A（2 2） 非自反，也不是反自反，非對稱，反對稱，非自反，也不是反自反，非對稱，反對稱， 可傳遞。可傳遞。 （3 3） 是自反的，對稱的，可傳遞的，不是反自反，是自反的，對稱的，可傳