離散數(shù)學(xué)3-1

1、第三章 二元關(guān)系,關(guān)系是一個(gè)基本概念，在日常生活中我們都熟悉關(guān)系這詞的含義，例如兄弟關(guān)系；上下級(jí)關(guān)系；位置關(guān)系等等。在數(shù)學(xué)上關(guān)系可表達(dá)集合中元素間的聯(lián)系。而我們知道，序偶可表達(dá)兩個(gè)、三個(gè)或n個(gè)客體之間的聯(lián)系，因此用序偶表達(dá)關(guān)系這個(gè)概念是非常自然的。,第三章 —— 二元關(guān)系,3-1 關(guān)系及其表示 3-2 關(guān)系的性質(zhì) 3-3 復(fù)合關(guān)系和逆關(guān)系 3-4 關(guān)系的閉包運(yùn)算3-5 集合的劃分和覆

2、蓋 3-6 等價(jià)關(guān)系與等價(jià)類3-7 相容關(guān)系 3-8 序關(guān)系,3-1 關(guān)系及其表示,任一序偶的集合確定了一個(gè)二元關(guān)系R，R中任一序偶可記作∈R或xRy。不在R中的任一序偶可記作 或 。,例如，在實(shí)數(shù)中關(guān)系>可記作 >={|x，y是實(shí)數(shù)且x>y}。,定義3-1.1,定義3-1.2前域：令R為二元關(guān)

3、系，由∈R的所有x組成的集合domR稱為R的前域，即 值域：使∈R的所有y組成的集合ranR稱作R的值域，即 域：R的前域和值域一起稱作R的域，記作FLD R，即 FLD R=domR∪ranR,例題1,設(shè) A={1，2，3，5}，B={1，2，4}， H=

4、{，，，} 求 domH，ranH，F(xiàn)LDH。 解：domH={1，2，3}， ranH={2，4}，F(xiàn)LDH={1，2，3，4},定義3-1.2 例題,,定義3-1.3,令X和Y是任意兩個(gè)集合，直積X×Y的子集R稱作X到Y(jié)的關(guān)系。 X到Y(jié)的關(guān)系R，可以由下圖表示：,,,例題2,設(shè)X={1，2，3，4}，求X上的關(guān)系>及dom>，Ran>。解：>={,

5、,,,,} dom>={2，3，4} ran>={1，2，3},定義3-1.3 例題,定義3-1.4,恒等關(guān)系：設(shè)Ix是X上的二元關(guān)系且滿足Ix={|x∈X}， 則稱Ix是X上的恒等關(guān)系。例如：A={1，2，3}，則IA={,,}。,定理3-1.1,若Z和S是從集合X到集合Y的兩個(gè)關(guān)系，則Z，S的并、交、補(bǔ)、差仍是X到Y(jié)的關(guān)系。 簡證：因?yàn)?故,關(guān)系的三種表示方法：,一、

6、序偶集合二、關(guān)系圖:用小圓圈表示元素，帶單向箭頭的線條連接元素，表示序偶。如：序偶可畫為 a b三、關(guān)系矩陣 0 ?R mij= 1 ?R,,關(guān)系的三種表示法 例題,設(shè)X={x1,x2,x3,x4}，Y={y1,y2,y3}，R={,,,,,,},寫出關(guān)系矩陣MR并畫出關(guān)系圖。,例題3,關(guān)系圖：,3-2 關(guān)系的性

7、質(zhì),1.自反：設(shè)R為定義在集合X上的二元關(guān)系,如果對(duì)于每個(gè)x∈X,有xRx,則稱二元關(guān)系R是自反的. R在X上自反,例如,在實(shí)數(shù)集合中,“ ”是自反的,因?yàn)閷?duì)于任意實(shí)數(shù)x x 成立.又如平面上三角形的全等關(guān)系是自反的.,定義3-2.2,對(duì)稱：設(shè)R為定義在集合X上的二元關(guān)系，如果對(duì)于每個(gè)x,y∈X,每當(dāng)xRy，就有yRx，則稱集合X上關(guān)系R是對(duì)稱的。 R在X上對(duì)稱,定義3-2.3,傳遞：設(shè)R為定義在集合X

8、上的二元關(guān)系，如果對(duì)于任意x，y，z∈X，每當(dāng)xRy，yRz時(shí)就有xRz，稱關(guān)系R在X上是傳遞的。 R在X上傳遞,定義3-2.4,反自反：設(shè)R為定義在集合X上的二元關(guān)系，如果對(duì)于每一個(gè)x∈X,都有? R,則R稱作反自反的。R在X上反自反,例如，數(shù)的大于關(guān)系，日常生活中的父子關(guān)系等都是反自反的。應(yīng)該注意：一個(gè)不是自反的關(guān)系，不一定就是反自反的。,定義3-2.5,反對(duì)稱：設(shè)R為定義在集合X上的二元關(guān)系，對(duì)于每一個(gè)x,y∈X,每當(dāng)xRy和y

9、Rx必有x=y，則稱R在X上是反對(duì)稱的,即是,例如實(shí)數(shù)集合中≤ 是反對(duì)稱的, 集合的關(guān)系是反對(duì)稱的。,3-3 復(fù)合關(guān)系和逆關(guān)系,二元關(guān)系是序偶為元素的集合，因此對(duì)它可以進(jìn)行集合的運(yùn)算，如并、交、補(bǔ)等而產(chǎn)生新的集合。對(duì)于關(guān)系還可以進(jìn)行一種新的運(yùn)算，那就是關(guān)系的復(fù)合。,定義3-3.1,設(shè)R為X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，則R?S稱為R和S的復(fù)合關(guān)系，表示為 從R和S，求R?S稱為關(guān)系的合成運(yùn)算。,例如，如果R1是關(guān)

10、系“是···的兄弟”，R2是關(guān)系“是···的父親”，那么R?S是關(guān)系“是···的叔伯”。,令R={,,}和S={,,,}，試求R?S，S?R，R?（R? S）， R? R，S? S，R? R? R 。,解： R?S={,,} S?R={,,}≠R?S (R?S) ? R={} R?(S?R)={}

11、 S? S={,,} R? R={,} R? R? R={,},定義3-3.1 例題,例題1,關(guān)系復(fù)合的矩陣運(yùn)算方法：,設(shè)MR和MS分別是關(guān)系R和關(guān)系S的關(guān)系矩陣，則MR ? S=MR ? MS，若MR和MS的元素記為uij和vij， MR ? S的元素記為wij則wij的計(jì)算公式定義為：,,∨ 為邏輯加，∧為邏輯乘 即按布爾矩陣乘法運(yùn)算,關(guān)系復(fù)合運(yùn)算的性質(zhì)：,具有結(jié)合性：即(A ? B) ?

12、 C=A ? (B ? C),記Rm為：,,有,Rs ? Rt=Rs+t,定義3-3.2,設(shè)R為X到Y(jié)的二元關(guān)系，如將R中每一序偶的元素順序互換，所得到的集合稱為R的逆關(guān)系。記作 ，即 ={|∈R}。,如在集合I上，關(guān)系“”。而在集合X={1，2，3，4}到Y(jié)={a，b，c}上的關(guān)系R={,,},其逆關(guān)系為 ={,,},定理3-3.1,設(shè)R，R1和R2都是從A

13、到B的二元關(guān)系，則下列各式成立。,a) b) c) 這里 d) e) (A×B）C= B×A,證明：,∈（R1∩R2）C?∈（R1∩R2）? ∈R1∧∈R2）? ∈R1C∧∈R2C? ∈R1C∩R2C,定理3-3.2,設(shè)T為從X到Y(jié)的關(guān)系，S為從Y到Z的關(guān)系，則有關(guān)系 ：,定理3-3.3,a) R是對(duì)