1、第第4章章 二元關系與函數(shù)二元關系與函數(shù)教學要求：教學要求：1.1.掌握有序對與笛卡兒積的概念和應用；掌握有序對與笛卡兒積的概念和應用； 2. 2.掌握關系的概念；關系的性質；自反閉包、對稱掌握關系的概念；關系的性質；自反閉包、對稱閉包、傳遞閉包的概念；閉包、傳遞閉包的概念； 3. 3.理解等價關系與等價類的概念，偏序關系、偏序理解等價關系與等價類的概念，偏序關系、偏序集的概念及用哈斯圖表示；。集的概念及用哈斯圖表示；。 4. 4.理解關系矩陣與關系圖；理解關系矩陣與關系圖； 5. 5.理解函數(shù)的概念，單射、滿射、雙射的概念；復理解函數(shù)的概念，單射、滿射、雙射的概念；復合函數(shù)與反函數(shù)的概念。合

2、函數(shù)與反函數(shù)的概念。4.1 集合的笛卡兒集與二元關系集合的笛卡兒集與二元關系一、關系及其定義一、關系及其定義例：設一家庭旅館有例：設一家庭旅館有3個房間，每個房間住兩個旅客。個房間，每個房間住兩個旅客。我們討論關系：我們討論關系：“某旅客住在某房間某旅客住在某房間”設：用設：用R表示這種關系，三間房間分別記以表示這種關系，三間房間分別記以1、2、3，六，六個旅客分別記以個旅客分別記以a、b、c、d、e、fa 1bc 2de 3f由圖可以很清楚地看出，由圖可以很清楚地看出，a與與1間存在關系間存在關系R，記為：記為：aR1，將滿足的所有關系列出如下：將滿足的所有關系列出如下：aR1，bR1，cR

3、2，dR2，eR3，fR3說明：說明：1) 滿足滿足pRq的關系可看成是一個有序對（的關系可看成是一個有序對（p，q），），如上面如上面aR1可寫成有序對（可寫成有序對（a，1）2) 滿足滿足R的所有關系可看成是一個有序對的集合，這個集的所有關系可看成是一個有序對的集合，這個集合即可叫合即可叫R ，上例中，上例中R既為：既為： R=(a,1), (b,1), (c,2), (d,2) ,(e,3) ,(f,3)3) 上面這種關系叫二元關系，因為它僅牽涉到兩個客體間上面這種關系叫二元關系，因為它僅牽涉到兩個客體間的關系的關系關系的定義：關系是一些有序對的集合關系的定義：關系是一些有序對的集合v有

4、序對：有序對：P76定義定義4.1注意注意 有序對強調第一元素與第二元素的順序有序對強調第一元素與第二元素的順序v有序有序n元組：元組： P76定義定義4.2二、集合的笛卡兒積與二元關系二、集合的笛卡兒積與二元關系1.笛卡兒積笛卡兒積 ： P76定義定義4.32.笛卡兒積的性質：笛卡兒積的性質：P77 例：例：P77 【例例】4.1 4.23.二元關系：二元關系： P79定義定義4.5.說明：可見用笛卡兒積的一個子集可以表示某個二元關系說明：可見用笛卡兒積的一個子集可以表示某個二元關系 P79定義定義4.64.三種特殊關系（對任何集合三種特殊關系（對任何集合A）：）： P79定義定義4.7 例

5、：例：P79 【例如例如】問題：一個笛卡兒積有多少個子集？問題：一個笛卡兒積有多少個子集？ 如果如果|A|=n，那么那么|AA|=n2，則則AA的子集有的子集有2n25.關系的表示：關系的表示： 集合表達式集合表達式: 例例 P79【例例】4.4 關系矩陣：關系矩陣：P80 圖圖4-1（a） 關系圖關系圖: P80 圖圖4-1（b）4.2 關系的運算關系的運算1.求關系的定義域求關系的定義域 值域值域 域域 P80定義定義4.8 例：例：P80 【例例4.5】2.求關系的逆、合成、限制、像求關系的逆、合成、限制、像 P82定義定義4.9 例：例：P82【例例4.6、例、例4.7、例、例4.8】

6、3.求關系的冪求關系的冪 P84定義定義4.10 例：例：P84【例例4.8】題例分析：題例分析：P106-107 【例例4.27、例、例4.28】作 業(yè)：P113-114 【題4.2、題4.3】例題 關系的復合運算設R=， S= =，求：R S S R R R S S R (S R)解： R S =， S R =， R R =， S S =， R (S R) =4.3 關系的性質關系的性質通過前面的學習，我們知道在一個集合上可以定義通過前面的學習，我們知道在一個集合上可以定義2n2個不同的關系，其中有實際意義的關系具有某種個不同的關系，其中有實際意義的關系具有某種性質，這些性質是：自反性、反

7、自反性、對稱性、反性質，這些性質是：自反性、反自反性、對稱性、反對稱性對稱性 和傳遞性和傳遞性 P86表表4-1舉例：舉例：1.P86 A=1，2，3，判斷，判斷R1-R7的性質的性質 2.判斷圖判斷圖4-5表示的表示的X=1，2，3上的關系的性質上的關系的性質4.4 關系的閉包關系的閉包1.閉包的概念（某個關系對某個關系的某種性質的閉包）閉包的概念（某個關系對某個關系的某種性質的閉包） 首先看一個例子：設非空集合首先看一個例子：設非空集合A=1，2，3有：有：A上的一個關系上的一個關系R=,，則：則：A上的另一個關系上的另一個關系R= ,，,是自反的是自反的 A上的另一個關系上的另一個關系R

8、”= ,，, 也是自反的也是自反的 這樣我們可以推出在這樣我們可以推出在29個關系中有若干關系是自反的個關系中有若干關系是自反的,很顯很顯 然然R中添加的有序對是最少的中添加的有序對是最少的,那么稱那么稱R是是R的自反閉包的自反閉包, 記為記為:r(R),同理有對稱閉包同理有對稱閉包s (R),傳遞閉包傳遞閉包t (R). 2.閉包的定義閉包的定義 P88定義定義4.113.閉包的構造方法閉包的構造方法 (1) 定理法定理法 P88定理定理4.4 (2) 矩陣法矩陣法P89 (3) 關系圖法關系圖法 （最直觀）（最直觀）例：例：P88【例例4.10】可以說關系的閉包其實是對該關系針對某個性質的

9、擴充可以說關系的閉包其實是對該關系針對某個性質的擴充例：例：P88 【例例】4.10例：例：X=a,b,c,R=,，|X|=3, 求求:t(R) RRccbbaaRbccbcaRRR432,t(R)=RR2R3 =,作業(yè) P113 【題4.4】 P116 【題4.14】4.5 等價關系與偏序關系等價關系與偏序關系一一 等價關系等價關系1. 定義定義: P89 定義定義4.12例例:A=1,2,3,8 R= |x,y Axy(mod3) ,我們可以得到下面我們可以得到下面 一個等價關系一個等價關系R,其中包含的有序對有其中包含的有序對有:自反自反:, 對稱對稱:,傳遞傳遞:,2. 等價類等價類x

10、R:設設R是非空集合上的等價關系是非空集合上的等價關系,則則A上互上互相等價的元素構成了相等價的元素構成了A的若干個子集的若干個子集,叫做叫做x關于關于R的等的等價類價類 定義定義: P90 定義定義4.13 性質性質: P91 定理定理4.53. 商集商集A/R: P91 定義定義4.144. 劃分與劃分塊劃分與劃分塊 : P91 定義定義4.15說明說明:由商集和劃分的定義不難看出由商集和劃分的定義不難看出:即商集就是即商集就是A的的一個劃分一個劃分,商集是由商集是由R所誘導的劃分所誘導的劃分. 反過來反過來,也可以由也可以由劃分誘導等價關系劃分誘導等價關系所以說所以說:集合集合A上的等價

11、關系與集合上的等價關系與集合A的劃分是一一對的劃分是一一對應的應的例例:設設A=1,2,3,求出求出A上所有的等價關系上所有的等價關系 P92 圖圖4-8 二二 偏序關系偏序關系1.偏序關系（偏序關系（）的）的 定義定義:P92 定義定義4.162.偏序集（偏序集（或或 ）的定義：）的定義：P93定義定義4.173.可比與蓋住的定義：可比與蓋住的定義：(描述偏序集合中元素間的層次關系描述偏序集合中元素間的層次關系) P93定義定義4.18 可比可比:若若x y或或yx,則稱則稱x,y可比可比 蓋住蓋住:對于任意對于任意x,yA ，當，當 Rxy且沒有其他且沒有其他 元素元素z滿足滿足和和,則稱

12、元素則稱元素y蓋住元素蓋住元素x4. 全序集全序集: P93 定義定義4.195. 哈斯圖哈斯圖:用來描述有窮偏序集的關系圖用來描述有窮偏序集的關系圖在一個集合上，我們常常要考慮元素的次序關系，其中很重要在一個集合上，我們常常要考慮元素的次序關系，其中很重要的一類關系稱作偏序關系。的一類關系稱作偏序關系。 （2）若）若 Ayx,，且且xy和和 yx，則把則把x畫在畫在y的下面；的下面； （3）若若y蓋住蓋住x，則在則在x和和y之間畫一條聯(lián)線，并箭頭向上，之間畫一條聯(lián)線，并箭頭向上，若若y不蓋住不蓋住x，但又存在但又存在“”關系，則必定通過關系，則必定通過x和和y之間之間的其它中間結點把的其它中

13、間結點把x和和y聯(lián)結起來；聯(lián)結起來；（4）所有邊的方向均是向上的，所以實際畫時，箭頭均可所有邊的方向均是向上的，所以實際畫時，箭頭均可 省去。省去。 畫一個偏序集（畫一個偏序集（A，）的哈斯圖的方法）的哈斯圖的方法 （1）用）用“”表示圖中的結點，每個節(jié)點代表集合表示圖中的結點，每個節(jié)點代表集合A中的一中的一個個 元素（具有自反性）；元素（具有自反性）；例：設例：設X=2,3,6,12,24,36“”定義為：若定義為：若 XyXxx整除整除y，X，是一偏序集合是一偏序集合,則則xy，其哈斯圖為其哈斯圖為:考查有序對考查有序對:, ,例：例：(a)設設X=a,b,P(X)= , ,baba),(

14、XP是一偏序關系，是一偏序關系， 其哈斯圖為：其哈斯圖為： (b)設設X=a,b,c),(XP的哈斯圖為：的哈斯圖為： 三 關于偏序集的幾個概念1.最小元和最大元 見書P93定義4.20（1）、（2）2.極小元和極大元 見書P93定義4.20（3）、（4）作業(yè)：P116【題4.16(2)】4.6 函數(shù)的定義和性質函數(shù)的定義和性質一、函數(shù)一、函數(shù)(映射映射)定義定義 首先考察下圖所表示的映射首先考察下圖所表示的映射XYx1x4我們發(fā)現(xiàn)，映射建立了從我們發(fā)現(xiàn)，映射建立了從X到到Y的一種關系：的一種關系：F=,x2x3x5y1y6y4y2y3y5若關系若關系F滿足下列兩個條件：滿足下列兩個條件： (

15、1)對每個對每個xX必存在必存在y Y ，使得使得F (2)對每個對每個xX也只存在一個也只存在一個y Y ，使得使得F（單值性）（單值性）那么則稱那么則稱F是從是從X到到Y的函數(shù)的函數(shù),記為記為:F:XY二二 函數(shù)的性質函數(shù)的性質 比較下列三個圖比較下列三個圖x2x3x5y1y2y3y4x1x4滿射滿射x2x4y1y4y2y3x1x3x2x4y1y4y2y3x1x3y5單射單射雙射雙射4.7 函數(shù)的復合和反函數(shù)一 函數(shù)的復合 1.復合函數(shù)的定義：P98 定理4.6 2.復合函數(shù)的性質： P98 定理4.7二 反函數(shù) 定義： P99 定理4.81.閱讀閱讀P100-106的的【例例4.23】、 【例例