第4章二元關(guān)系與函數(shù)

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

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

3、2，dR2，eR3，fR3說明：說明：滿足滿足pRq的關(guān)系可看成是一個(gè)有序?qū)Γǖ年P(guān)系可看成是一個(gè)有序?qū)Γ╬，q），），如上面如上面aR1可寫成有序?qū)Γ蓪懗捎行驅(qū)Γ╝，1）滿足滿足R的所有關(guān)系可看成是一個(gè)有序?qū)Φ募希@個(gè)集的所有關(guān)系可看成是一個(gè)有序?qū)Φ募?，這個(gè)集合即可叫合即可叫R ，上例中，上例中R既為：既為： R=(a,1), (b,1), (c,2), (d,2) ,(e,3) ,(f,3)上面這種關(guān)系叫二元關(guān)系，因?yàn)樗鼉H牽涉到兩個(gè)客體間上面這種關(guān)系叫二元關(guān)系，因?yàn)樗鼉H牽涉到兩個(gè)客體間的關(guān)系的關(guān)系關(guān)系的定義：關(guān)系是一些有序?qū)Φ募详P(guān)系的定義：關(guān)系是一些有序?qū)Φ募蟰有序?qū)Γ河行驅(qū)Γ篜7

4、6定義定義4.1注意注意 有序?qū)?qiáng)調(diào)第一元素與第二元素的順序有序?qū)?qiáng)調(diào)第一元素與第二元素的順序v有序有序n元組：元組： P76定義定義4.2二、集合的笛卡兒積與二元關(guān)系二、集合的笛卡兒積與二元關(guān)系1.笛卡兒積笛卡兒積 ： P76定義定義4.32.笛卡兒積的性質(zhì)：笛卡兒積的性質(zhì)：P77 例：例：P77 【例例】4.1 4.23.二元關(guān)系：二元關(guān)系： P79定義定義4.5.說明：可見用笛卡兒積的一個(gè)子集可以表示某個(gè)二元關(guān)系說明：可見用笛卡兒積的一個(gè)子集可以表示某個(gè)二元關(guān)系 P79定義定義4.64.三種特殊關(guān)系（對任何集合三種特殊關(guān)系（對任何集合A）：）： P79定義定義4.7 例：例：P79 【例

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

6、系的冪 P84定義定義4.10 例：例：P84【例例4.8】題例分析：題例分析：P106-107 【例例4.27、例、例4.28】作 業(yè)：P113-114 【題4.2、題4.3】例題 關(guān)系的復(fù)合運(yùn)算設(shè)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 關(guān)系的性質(zhì)關(guān)系的性質(zhì)通過前面的學(xué)習(xí)，我們知道在一個(gè)集合上可以定義通過前面的學(xué)習(xí)，我們知道在一個(gè)集合上可以定義2n2個(gè)不同的關(guān)系，其中有實(shí)際意義的關(guān)系具有某種個(gè)不同的關(guān)系，其中有實(shí)際意義的關(guān)系具有某種性質(zhì)，這些性質(zhì)是：自反性、反自反性、對稱性、反

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

8、自反的也是自反的 這樣我們可以推出在這樣我們可以推出在29個(gè)關(guān)系中有若干關(guān)系是自反的個(gè)關(guān)系中有若干關(guān)系是自反的,很顯很顯 然然R中添加的有序?qū)κ亲钌俚闹刑砑拥挠行驅(qū)κ亲钌俚?那么稱那么稱R是是R的自反閉包的自反閉包, 記為記為:r(R),同理有對稱閉包同理有對稱閉包s (R),傳遞閉包傳遞閉包t (R). 2.閉包的定義閉包的定義 P88定義定義4.113.閉包的構(gòu)造方法閉包的構(gòu)造方法 (1) 定理法定理法 P88定理定理4.4 (2) 矩陣法矩陣法P89 (3) 關(guān)系圖法關(guān)系圖法 （最直觀）（最直觀）例：例：P88【例例4.10】可以說關(guān)系的閉包其實(shí)是對該關(guān)系針對某個(gè)性質(zhì)的擴(kuò)充可以說關(guān)系的閉

9、包其實(shí)是對該關(guān)系針對某個(gè)性質(zhì)的擴(kuò)充例：例：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 等價(jià)關(guān)系與偏序關(guān)系等價(jià)關(guān)系與偏序關(guān)系一一 等價(jià)關(guān)系等價(jià)關(guān)系1. 定義定義: P89 定義定義4.12例例:A=1,2,3,8 R= |x,y Axy(mod3) ,我們可以得到下面我們可以得到下面 一個(gè)等價(jià)關(guān)系一個(gè)等價(jià)關(guān)系R,其中包含的有序?qū)τ衅渲邪挠行驅(qū)τ?自反自反:, 對稱對稱:,傳遞傳遞:,2. 等價(jià)類等價(jià)類xR:設(shè)設(shè)R是非空集

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

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

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

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

14、是一偏序關(guān)系， 其哈斯圖為：其哈斯圖為： (b)設(shè)設(shè)X=a,b,c),(XP的哈斯圖為：的哈斯圖為： 三 關(guān)于偏序集的幾個(gè)概念1.最小元和最大元 見書P93定義4.20（1）、（2）2.極小元和極大元 見書P93定義4.20（3）、（4）作業(yè)：P116【題4.16(2)】4.6 函數(shù)的定義和性質(zhì)函數(shù)的定義和性質(zhì)一、函數(shù)一、函數(shù)(映射映射)定義定義 首先考察下圖所表示的映射首先考察下圖所表示的映射XYx1x4我們發(fā)現(xiàn)，映射建立了從我們發(fā)現(xiàn)，映射建立了從X到到Y(jié)的一種關(guān)系：的一種關(guān)系：F=,x2x3x5y1y6y4y2y3y5若關(guān)系若關(guān)系F滿足下列兩個(gè)條件：滿足下列兩個(gè)條件： (1)對每個(gè)對每個(gè)xX必存在必存在y Y ，使得使得F (2)對每個(gè)對每個(gè)xX也只存在一個(gè)也只存在一個(gè)y Y ，使得使得F（單值性）（單值性）那么則稱那么則稱F是從是從X到到Y(jié)的函數(shù)的函數(shù),記為記為:F:XY二二 函數(shù)的性質(zhì)函數(shù)的性質(zhì) 比較下列三個(gè)圖比較下列三個(gè)圖x2x3x5y1y2y3y4x1x4滿射滿射x2x4y1y4y2y3x1x3x2x4y1y4y2y3x1x3y5單射單射雙射雙射4.7 函數(shù)的復(fù)合和反函數(shù)一 函數(shù)的復(fù)合 1.復(fù)合函數(shù)的定義：P98 定理4.6 2.復(fù)合函數(shù)的性質(zhì)： P98 定理4.7二 反函數(shù) 定義： P99 定理4.81.閱讀閱讀P100-106的的【例例4.23】、 【例例4