離散數(shù)學(xué)(3.6關(guān)系性質(zhì))

1、1張捷第三章第三章 集合與關(guān)系集合與關(guān)系（Sets and Relations)Sets and Relations) 3.6 3.6 關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算(Closure Operations)(Closure Operations)3.7 3.7 集合的劃分與覆蓋集合的劃分與覆蓋(Partition & Cover of Sets) (Partition & Cover of Sets) 3.8 3.8 等價關(guān)系等價關(guān)系(Equivalent Relations) (Equivalent Relations) 3.9 3.9 相容關(guān)系相容關(guān)系(Compatibili

2、ty(CompatibilityRelations) Relations) 3.10 3.10 序關(guān)系序關(guān)系(Ordered Relations)(Ordered Relations)3.1 3.1 集合及其運(yùn)算集合及其運(yùn)算(Sets & Operations with sets)(Sets & Operations with sets) 3.2 3.2 序偶與笛卡爾積序偶與笛卡爾積(Ordered Pairs & Cartesian Product)(Ordered Pairs & Cartesian Product)3.3 3.3 關(guān)系關(guān)系 (Relatio

3、ns) (Relations) 3.4 3.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)(The Propeties(The Propeties of Relations) of Relations) 3.5 3.5 復(fù)合關(guān)系與逆關(guān)系復(fù)合關(guān)系與逆關(guān)系(Compound Relations & Inverse(Compound Relations & Inverse Relations) Relations)BABA 3.4 3.4 關(guān)系的性質(zhì)關(guān)系的性質(zhì)(The properties of (The properties of Relations)Relations)3.4.13.4.1 集合集合A

4、 A上上關(guān)系的關(guān)系的性質(zhì)性質(zhì)( (The properties ofThe properties of Relations on set A Relations on set A) )3.4.2 3.4.2 由由關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)第三章第三章 集合與關(guān)系集合與關(guān)系(Sets & Relations)第三章第三章 集合與關(guān)系集合與關(guān)系(Sets & Relations) 3.4.1 3.4.1 集合集合A A上關(guān)系的性質(zhì)上關(guān)系的性質(zhì) aa 定義定義3.4.1 設(shè)設(shè) 是集合是集合A A上的關(guān)系上的關(guān)系 （1 1）若對于所有的）若對于所有的

5、，均有，均有 ，則稱，則稱 在在A A上是自反的上是自反的(reflexive)(reflexive)。 Aaaa （2 2）若對于所有的）若對于所有的 ，均有，均有 ，則稱，則稱 在在A A上是反自反的上是反自反的(antireflexive(antireflexive) ) 。 AaaaAba, （3 3）對于所有的）對于所有的 ，若每當(dāng)有，若每當(dāng)有 就必有就必有 ，則稱則稱 在在 A A 上是對稱的上是對稱的(symmetric)(symmetric)。 baab （4 4）對于所有的）對于所有的 ，若每當(dāng)有，若每當(dāng)有 和和 就就必有必有 ，則稱，則稱 在在 A A 上是反對稱的上是反對

6、稱的(antisymmetric(antisymmetric). ). Aba,baabba （5 5）對于所有的）對于所有的 ，若每當(dāng)有，若每當(dāng)有 和和 就必有就必有 ，則稱，則稱 在在 A A 上是可傳遞的上是可傳遞的(transitive)(transitive)。 Acba,bacbca例例1 1 設(shè)設(shè) ， （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 設(shè)設(shè) ，A A上的關(guān)系上的關(guān)系自反自反對稱對稱不是反對稱不是反對稱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 設(shè)設(shè)則則 自反的、對稱的、反對稱的、自反的、對稱的、反對稱的、可傳遞的?？蓚鬟f的。則則 自反的、反對稱的、自反的、反對稱的、可傳遞的?？蓚鬟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 全關(guān)系是全關(guān)系是自反的、對稱的、自反的、對稱的、可傳遞的。可傳遞的。3.4.2 3.4.2 由由關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)關(guān)系圖、關(guān)系矩陣判別關(guān)系的性質(zhì)1. 1. 關(guān)系矩陣關(guān)系矩陣 1 2 3 410000100101011114321M若若 是自反的，則關(guān)系矩

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

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