離散數(shù)學3-1

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

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

3、系，由∈R的所有x組成的集合domR稱為R的前域，即 值域：使∈R的所有y組成的集合ranR稱作R的值域，即 域：R的前域和值域一起稱作R的域，記作FLD R，即 FLD R=domR∪ranR,例題1,設 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是任意兩個集合，直積X×Y的子集R稱作X到Y的關系。 X到Y的關系R，可以由下圖表示：,,,例題2,設X={1，2，3，4}，求X上的關系>及dom>，Ran>。解：>={,

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

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

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

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

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

10、系“是···的兄弟”，R2是關系“是···的父親”，那么R?S是關系“是···的叔伯”。,令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,關系復合的矩陣運算方法：,設MR和MS分別是關系R和關系S的關系矩陣，則MR ? S=MR ? MS，若MR和MS的元素記為uij和vij， MR ? S的元素記為wij則wij的計算公式定義為：,,∨ 為邏輯加，∧為邏輯乘 即按布爾矩陣乘法運算,關系復合運算的性質：,具有結合性：即(A ? B) ?

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

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