計算機(jī)數(shù)學(xué)課件第十六章

1、第16章 集合與函數(shù),知識點(diǎn)關(guān)系概念與運(yùn)算 關(guān)系表示法與性質(zhì) 關(guān)系矩陣與閉包 相容關(guān)系與覆蓋等價關(guān)系與劃分 序關(guān)系 函數(shù)的定義與性質(zhì) 復(fù)合函數(shù)與逆函數(shù),難點(diǎn) 相容關(guān)系、等價關(guān)系和序關(guān)系等有關(guān)性質(zhì) 關(guān)系閉包概念及求法 要求熟練掌握 集合運(yùn)算的證明序偶與笛卡爾乘積關(guān)系的性質(zhì)及復(fù)合關(guān)系、逆關(guān)系相容關(guān)系與覆蓋等價關(guān)系與劃分,偏序關(guān)系 與特殊元函數(shù)的定義與圖示復(fù)合函數(shù)與逆函數(shù) 定義與運(yùn)算16.1 集

2、合的基本概念 集合的表示方法一般有列舉法和特法。列舉法就是將集合中的元素一一列舉出來，用逗號分開，然后用花括號括起來。 例如，特征法就是用一個小寫字母統(tǒng)一表示該集合的元素并指出這類元素的公共特征。,,例如， 當(dāng)兩個集合A和B有相同元素時，稱這兩個集合相等。記作A=B。 有些數(shù)集經(jīng)常用特定字母表示： N：自然數(shù)集； I：整數(shù)集

3、； Q：有理數(shù)集； R：實(shí)數(shù)集； C：復(fù)數(shù)集；,,如果集合A中的每一個元素又都是集合B的元素，則稱A是B的子集。記作定理1 集合A和集合B相等的充分必要條件是 ,即 。 如果集合A是集合B的子集，A和B

4、不等，B中至少有一元素不屬于A，則稱A為B的真子集，記作 ,例如 。 不含任何元素的集合稱為空集。記作 或 。 空集是任何集合的子集。,,,,,,,,在一個具體問題中，如果所涉及到的集合都是某個集合的子集則稱這個集合為全集。用 表示。 A是一個集合由屬于全集U但不屬于A的所有元

5、素組成的集合稱為A的補(bǔ)集。記作 。定理2 A是有限集， 則A的冪集P（A）的基為 。即 例 計算以下冪集 1） 2） 3）,4） 解 1） 2） 3） 4）,,,,,16.2 集合的運(yùn)算,1.集合的交定義1 兩個集合A和B，由A和B的所有共

6、同元素組成的集合稱A和B的交，記作 即 交運(yùn)算有如下性質(zhì)：,,,2.集合的并定義2 兩個集合A和B，所有屬于A或?qū)儆贐的元素組成的集合成為A和B的并。記作 即 并運(yùn)算有如下性質(zhì)：定理3 設(shè)A，B，C為三個集合則下列成立：,,,,,,上式稱分配律定理4 設(shè)A，B為集合，則下列關(guān)系式成立：上式稱吸收律定理4 設(shè)A，B為集合

7、，則下列關(guān)系式成立：上式稱摩根律3.集合的減運(yùn)算定義3 由屬于集合A但不屬于集合B的那些元素組成的集合稱為A減B的差。記作A-B。,,即 減運(yùn)算有如下性質(zhì)：4.集合的對稱差 定義4 設(shè)A，B為兩個集合，A和B的對稱差記作， 其元素或?qū)儆贏，或?qū)儆贐，但不能既屬于A又屬于B。即 對稱差的關(guān)系見書中圖16.2所示。,,,,,對稱差有如下性質(zhì)： 16.3

8、 包含排斥原理 當(dāng)有限集A，B不相交時，顯然有當(dāng)A，B相交時，根據(jù)文氏圖有此結(jié)論稱包含排斥原理。定理6 設(shè) 為有限集合，則,,,,,,,,,,例對100個大學(xué)生進(jìn)行調(diào)查的結(jié)果是：34人愛好音樂，24人愛好美術(shù)，48人愛好舞蹈；13人既愛好音樂又愛好舞蹈，14人既愛好音樂又愛好美術(shù)，15人既愛好美術(shù)又愛好舞蹈；有25人這三種愛好都沒有，問這三種愛好都有的大學(xué)生人

9、數(shù)是多少？解設(shè)A是愛好音樂的大學(xué)生集合，B是愛好美術(shù)的大學(xué)生集合，C是愛好舞蹈的大學(xué)生的集合，則,,,因?yàn)樗?6.4 笛卡爾積與關(guān)系定義5 由兩客體 和b，按一定順序組成一個二元組，稱此二元組為有序?qū)蛐蚺肌Ｓ涀鳎?，b）其中 為序偶的第一元素，b為序偶為第二元素。序偶元素順序一經(jīng)確定就不能變更。,,,,定義6 設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成序偶，所

10、有這樣的序偶組成的集合，稱 的笛卡爾乘積。記作 例如， 則定義7 設(shè)A，B為集合，R是笛卡爾積 的子集，則R為A到B的一個二元關(guān)系。當(dāng)A=B時，稱R為A上的二元關(guān)系。例如， ，如果

11、 ， 那么R就是一個A到B,,,,,,的二元關(guān)系， 即稱 與 有關(guān)系R，記作 ； 則稱 沒有關(guān)系R， 記作 。例如 ，

12、那么R是A上的一個二元關(guān)系。定義8 設(shè)R為二元關(guān)系，由 的所有x組成集合domR，稱為R的前域; 由 的所有y組成集合ranR，稱為R的值域；R的前域和值域一起稱作R的域，記作FLDR即 。,,,,,,,,,,,,,,,,例 如， 在 上關(guān)

13、系R定義為： 則 若 稱為空關(guān)系；若 稱為R全關(guān)系，當(dāng)A=B時，全關(guān)系 ； A上恒等關(guān)系 。例

14、如 則 。例 ， 下面各式定義的R為A上關(guān)系，分別列出下列R的元素。,,,,,,,,,,,,1）2）3）4）解1）2）3）4） ，其中 （R的元素請讀者自己寫出）,,,,,,,,,16.5 關(guān)系的表達(dá)式與基

15、本類型,設(shè)集合 到 上的二元關(guān)系為R。在平面上作出m個點(diǎn)，分別記作， 然后畫出n個點(diǎn)分別記作如果 ，則可自點(diǎn) 到 點(diǎn) 作一有向弧，其箭頭指向 ，如果 ，則不連接，這樣聯(lián)結(jié)起來的圖，稱為R的關(guān)系圖。

16、 例如，則關(guān)系圖如書中圖16.3所示。,,,,,,,,,,,,除用關(guān)系圖描述關(guān)系外，還有經(jīng)常用的一種方法-----布爾矩陣,即設(shè) R為X到Y(jié)的一個二元關(guān)系，則 對于R有一個關(guān)系矩陣 其中 上例可表示為,,,,,,

17、,,,,定義9 設(shè)R為集合X上的二元關(guān)系，則1）如果 對任意，必有xRx則稱關(guān)系R在X上是自反的。2）如果 對任意，必有xRx則稱關(guān)系R在X上是反自反的。3）如果 對任意，若xRy，必有yRx，則稱關(guān)系R在X上是對稱的。4）如果 對任意，若xRy且yRx，必有x=y，則稱R是反對稱的。此定義也可敘述為：若

18、xRy，且 必有yRx 。,,,,,5）如果對任意 ，xRy且yRz必有xRz，則稱關(guān)系R在X上是傳遞的。 關(guān)系類型可以從關(guān)系矩陣的關(guān)系圖上予以驗(yàn)證：1）若關(guān)系R是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上所有元素都為1，在關(guān)系圖中，每個點(diǎn)都有自回路。2）若關(guān)系R是對稱的，當(dāng)且僅當(dāng)在關(guān)系矩陣中是對稱的且在關(guān)系圖上，任兩點(diǎn)間若有定向弧

19、線，必是成對出現(xiàn)。3）若關(guān)系R是反自反的，當(dāng)且僅當(dāng)關(guān)系矩陣對角線的元素皆為零，關(guān)系圖上每個點(diǎn)都沒有自回路。4）若關(guān)系R是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣以主對角線為對稱的元素不能同時為1，在關(guān)系圖上兩點(diǎn)間的定向弧線不可能成對出現(xiàn)。,,,16.6 等價關(guān)系與劃分,定義10 R是A上的二元關(guān)系，如果R是自反的，稱的，可傳遞的，則稱R為A上的等價關(guān)系。例 設(shè)集合 ，如果

20、A中的元素 ,b被4除后余數(shù)相同（即模4同余關(guān)系）則認(rèn)為 ,b是相 關(guān)的。并用關(guān)系矩陣描述該等價關(guān)系。解設(shè)A上的模4同余關(guān)系為R，由于相同數(shù)被4除后余數(shù)相等所以R是自反的。R是對稱的是顯然的。對于 可表示為 -b=4k（k是整數(shù)），所以當(dāng) 和 時，即,,,,,,,那么可是 ，R滿足傳

21、遞性，綜上R是等價關(guān)系。將集合A中元素寫成 ，關(guān)系矩陣為,,,,,,,,定義11 R是A上的等價關(guān)系， 由A中所有與相關(guān)的元素組成的集合稱為 關(guān)于R的等類價，記作 。例如， R是A上的模3同余關(guān)系。顯然R是A上的等價關(guān)系，A中各元素關(guān)于R的等價類分別是可以看到相同元

22、素其等價類是相同的，不同等價類僅有3個， 即 、 、 。,,,,,,,,,,,,,,,,定義12 R是A上的等價關(guān)系，以R的不交的等價類為元素的集合，稱為A在R下的商集。記作 即 上例的商集定義13 設(shè)A是集合 是A的子集，如果 且

23、 由以作為元素構(gòu)成的集合 稱為A的一個劃分，每一個子集 稱為塊。,,,,,,例如， 而 則 都是A的劃分，在 中集合 都是塊。容易看到，如果R是A上的等價關(guān)系則商集 就是A上的一個劃分，等價類就是塊。 定理7

24、 集合A的一個劃分能確定一個A上的等價關(guān)系；反之，確定了A上的一個等價關(guān)系也確定A上的一個劃分。,,,,,,,,,,,16.7 相容關(guān)系與覆蓋,定義13 R是A上二元關(guān)系，如果R是自反的，對稱的，則稱R是A上的相容關(guān)系。例 ，求R。解 設(shè)則,,,,,,,,,

25、,,定義15 設(shè)R是A上的相容關(guān)系，B是A的子集，而且在B中任意兩個元素都是相關(guān)的，則稱B為由相容關(guān)系R產(chǎn)生的相容類。假如，設(shè) R是A上的二元關(guān)系，其定義為： 且 和b至少有一個數(shù)相同，則 。顯然R是相容關(guān)系。A的子集：

26、 等都是相容類。 下面討論相容和覆蓋之間的關(guān)系。,定義16 設(shè)A是集合， 是它的非空子集，令 如果 則S為A的覆蓋。例如

27、 S是A的覆蓋。定義17 如 是集合A的覆蓋，且對于S中任意元素 ，不存在S中其他元素 使得 是 的子集，則稱S為A的完全覆蓋。例如,,,,,,,,,,,其中 是A的覆蓋又是完全覆蓋，而 是A的覆蓋但不是完全覆蓋，因?yàn)?

28、 是 的子集。 16.8 序關(guān)系定義18 R是A上的二元關(guān)系，如果R是自反的，反對稱的，可傳遞的則稱R為A上的偏序關(guān)系，簡稱偏序，記作“ ” 。 任何集合A上的恒等關(guān)系，集合的冪集P（A）上的包含關(guān)系，實(shí)數(shù)集上的小于等于關(guān)系，正整數(shù)集上的整除關(guān)系都是偏序關(guān)系。,,例如 集合 ，R是A上大于等于關(guān)系，則定義19

29、 R是A上偏序關(guān)系，若 且A中沒有其它元素C滿足 ， 則稱元素b蓋住元素 。定義20 設(shè) 是偏序集，B是A的子集，如果B中任意兩個元素都是有關(guān)系的，則稱子集B為鏈。 定義21 在偏序集 中，如果A是鏈，則稱 是全序集，二元關(guān)系

30、 稱全序關(guān)系。例如 在正整數(shù)數(shù)集合 上的小于等于關(guān)系就是全序關(guān)系。,,,,,,,,,,定義22 是偏序集， 是A中的一個元素，如果A中沒有其他元素x，使得 ，則 稱為A中的極大元。同理，b是A中的一個元素，如果A中沒有其他元素x，使得 則稱b為A中的極小元。例如

31、 ， 是A上整除關(guān)系，那么元素2和3是A中極小元；元素6和8是A中極大元。定義23 是偏序集，如果A中存在著元素 ，使得A中任意元素x都有 則稱 是A中的最 大元。同理，如果A中存在著元素b，使得A中任 意元素x都有 則稱b是A中最小元。,,,,,,,,例如，

32、 是A上的整除關(guān)系，則元素1是A的最小元，元素12是A的最大元。 定義24 是偏序集， 和b是A中的兩個元素，如果A中存在元素c，使得 且 則稱c為和b的上界。同理，如果A中存在元素d使得且 則稱d為 和b的下界。 例如， ， 是A上的整

33、除關(guān)系，對元素2和3，元素6和12都是上界，元素1是下界；對于元素3和6，元素6和12是上界，元素1和3是下界；對于元素6和8元素1和2是下界，但沒有上界。,,,,,,,,定義25 是偏序集， 和b是A上兩個元素，c是他們的上界，且對 和b的其它上界x，都有 則稱c為 和b最小上界。同理，d是 和b的下界，且對于 和b的其它下界x都有

34、 ，則稱d為 和b的最大下界。例如， ， 是整除關(guān)系，對元素2和3，其最小上界為b，最大下界是1；對元素4和8，其最小上界是8，最大下界是4；對于元素6和8，其最大下界是2，但沒有最小上界。,,,,16.9 關(guān)系運(yùn)算與閉包,定義26 R是A到B的二元關(guān)系，若將R中每一個有序?qū)?nèi)的元素順序互換，所得到的集合稱為R的逆關(guān)系，記作

35、 ，即 。 由逆關(guān)系定義還可得下列定理：定理8 設(shè) 都是從A到B的二元關(guān)系，則下列各式成立： 1） 2） 3）,,,,,,4） ，這里 5） 6） 7）若 ，則定義27 R是A到B的二元關(guān)

36、系，S是B到C的二元關(guān)系；R和S的復(fù)合記作 ，它是一個A到C的二元關(guān)系當(dāng) 且 時， 定理9 R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，復(fù)合關(guān)系RoS是A到C的二元關(guān)系，它們的關(guān)系矩陣分別為 則,,,,,,,,,,,,,定義

37、28 R是A上二元關(guān)系，R的自反（或?qū)ΨQ，或傳遞）閉包 也是A上的二元關(guān)系，且滿足， 1） 是自反的（或?qū)ΨQ的或傳遞的）。 2） 。 3）對任何自反的（或?qū)ΨQ的，或傳遞的）二元關(guān)系 ，如果 則必有 。R的自反閉包，對稱閉包，傳遞閉包分別用 r（R），S（R），t（R）表示。,,,,,,下面介紹一種求傳遞

38、閉包的有效算法。第一步 置新矩陣第二步 置j=1第三步 對所有的i如果，則對K=1，2，……，n置第四步 j=j+1第五步 如果 則轉(zhuǎn)到第三步，否則停止。,,,,,16.10 函數(shù)的概念,定義29 A和B是集合，f是A到B的二元關(guān)系，如果f滿足：對于A中的每一個元素 存在著B中的一個元素且僅一個元素b使，則 稱f為A到B的函

39、數(shù)。常把 記作 ，稱 為自變元或原象，b為對應(yīng) 的函數(shù)值或映象。集合A稱函數(shù)f的定義域，由所有映象組成的集合稱函數(shù)f的值域。,,,,,理解函數(shù)時要注意以下兩點(diǎn)：1）函數(shù)定義域是集合A，而不是A的某一個真子集。2）對于 ，在B中只有一個元素b與之相關(guān)，不能即有 ，又有

40、 即只能多對一，而不能一對多。例 集合 f是A到B的二元關(guān)系，f的關(guān)系圖見書中圖16.13所示，試指出哪個二元關(guān)系可構(gòu)成函數(shù)。,解圖（a）不能構(gòu)成函數(shù)，因?yàn)锳中元素 即 有 還有 ， 有兩個映象，所以不能

41、構(gòu)成函數(shù)。圖（b）能構(gòu)成函數(shù)。圖（c）不能構(gòu)成函數(shù)，因?yàn)樵豤在集合B中無映象。定義30 設(shè)集合A和B，把所有從A到B的函數(shù)構(gòu)成的集合記作 ，即 。,,,,,,,例 設(shè)從A到B可定義多少種不同函數(shù)？解 從A到B的函數(shù)可構(gòu)成8個，即,,,,,,,,,,,

42、定義31 設(shè)A，B是集合，f是A到B的函數(shù)，則 1）對于A中任兩元素 當(dāng) 時，都有 ，則稱f為單射函數(shù)。2）如果函數(shù)的值域恰好是B則稱f為滿射函數(shù)。3）如果f既是單射函數(shù)，又是滿射函數(shù)，則稱f是雙射函數(shù)。例 設(shè) 函數(shù) 都是A到

43、B的映射，且 問： 是滿射？單射？雙射函數(shù)？,,,,,,,,,解 不是滿射，也不是單射 是滿射，又是單射，所以 是雙射。16.11 復(fù)合函數(shù)和逆函數(shù)定義32 設(shè)f是A到B的函數(shù)，g是B到C的函數(shù)，f和g合成后的函數(shù)稱為復(fù)合函數(shù)。記作gof。它是A

44、到C的函數(shù)。當(dāng) 且 時，則 ，即為 。定理10 設(shè)A，B，C是集合，f是A到B的函數(shù)，g是B到C的函數(shù)：1）如果f和g都是單射函數(shù)，則gof也是單射函數(shù)。,,,,,,,2）如果f和g都是滿射函數(shù)，則gof也是滿射函數(shù)。3）如果f和g

45、都是雙射函數(shù)，則gof也是雙射函數(shù)。定義33 設(shè)f是A到B的雙射函數(shù)，其逆關(guān)系稱為f 的逆函數(shù)。記作 。 例如 f是A到B的雙射函數(shù)，且 即其逆函數(shù)

46、 即 只有雙射函數(shù)有逆函數(shù)，單射和滿射函數(shù)沒有逆函數(shù)。,,,,,,,,,,,,,最后一個部分介紹著名的“鴿洞原理” 某人修了n個鴿洞，養(yǎng)了多于n只的鴿子這樣必然有一個鴿洞住2只或2只以上的鴿子。用數(shù)學(xué)語言來描述即：A，B是有限集合，于是A到B的函數(shù)，如果 則在A中至少有m+1個元素，其函

47、數(shù)值相等。例 任意n+1個正整數(shù)，其中必有兩個數(shù)之差被n整除。解 由于任意正整數(shù)被n除后，其余數(shù)只能是0，1，2，…，n-1共n種，所以在n+1個正整數(shù)中，必有兩個數(shù)被n除后 余數(shù)相同，那么這兩個數(shù)之差必能被n整除。,,小 結(jié),本章論述了集合，關(guān)系和函數(shù)，學(xué)習(xí)本章要能熟練集合的運(yùn)算，特別是對稱差，要能掌握有關(guān)冪集的求法。會運(yùn)用鴿洞原理處理一些實(shí)際問題。 對于關(guān)系要會用圖和矩陣方式表示，給定A上