離散數(shù)學(xué)常考題型梳理

1、PAGE PAGE 10離散數(shù)學(xué)常考題型梳理第2章 關(guān)系與函數(shù)一、題型分析本章主要介紹關(guān)系的概念及運(yùn)算、關(guān)系的性質(zhì)與閉包運(yùn)算、等價(jià)關(guān)系、相容關(guān)系和偏序關(guān)系三個(gè)重要關(guān)系、函數(shù)以及函數(shù)相關(guān)知識(shí)等內(nèi)容。常涉及到的題型主要包括：2-1關(guān)系的概念理解以及關(guān)系的并、交、補(bǔ)、差以及復(fù)合和逆關(guān)系等運(yùn)算2-2關(guān)系自反和反自反、對(duì)稱和反對(duì)稱等性質(zhì)的概念理解與判定；自反、對(duì)稱和傳遞閉包運(yùn)算。2-3 HYPERLINK /mod/resource/view.php?inpopup=true&id=428 t _blank 等價(jià)關(guān)系 2-4偏序關(guān)系和哈斯圖2-5 函數(shù)的概念和性質(zhì)因此，在本章學(xué)習(xí)過(guò)程中希望大家要清楚地知

2、道：1有序?qū)偷芽柗e（1）有序?qū)Γ核^有序?qū)褪侵敢粋€(gè)有順序的數(shù)組，如 ，x , y 的位置是確定的，且。（2）笛卡爾積：把集合A，B合成集合AB，規(guī)定：由于有序?qū)χ?x，y 的位置是確定的，因此 AB 的記法也是確定的，不能寫(xiě)成 BA 。笛卡兒積的運(yùn)算一般不滿足交換律。2二元關(guān)系的概念和表示、幾種特殊的關(guān)系和關(guān)系的運(yùn)算（1）二元關(guān)系的概念：二元關(guān)系是一個(gè)有序?qū)?，設(shè)集合 A，B ，從集合 A 到 B 的二元關(guān)系記作xRy。二元關(guān)系的定義域：；二元關(guān)系的值域：。二元關(guān)系 R 是一個(gè)有序?qū)M成的集合因此，一個(gè)二元關(guān)系是一個(gè)集合，可以用集合形式表示；反過(guò)來(lái)說(shuō)，一個(gè)集合未必是一個(gè)二元關(guān)系，僅當(dāng)集

3、合是由有序?qū)υ亟M成的，才能當(dāng)做二元關(guān)系。常用關(guān)系的表示法包括了集合表示法、列舉法、描述法、關(guān)系矩陣法和關(guān)系圖法。關(guān)系矩陣和關(guān)系圖是有限集合上的二元關(guān)系的表示方法。（2）特殊的關(guān)系：空關(guān)系、全關(guān)系和恒等關(guān)系空關(guān)系（記作）：是任何關(guān)系的子集全關(guān)系（記作EA）： 恒等全系（記作IA）：（3）關(guān)系的集合運(yùn)算、復(fù)合運(yùn)算和逆運(yùn)算：關(guān)系的集合運(yùn)算與普通集合運(yùn)算基本相同，主要為并運(yùn)算、交運(yùn)算、補(bǔ)運(yùn)算、差運(yùn)算和對(duì)稱差運(yùn)算。關(guān)系復(fù)合運(yùn)算，描述為復(fù)合關(guān)系滿足結(jié)合律：關(guān)系的逆運(yùn)算，描述為逆關(guān)系滿足： 二元關(guān)系 R 的逆關(guān)系可以用關(guān)系矩陣和關(guān)系圖表示并且逆關(guān)系的關(guān)系矩陣就是關(guān)系R的關(guān)系矩陣的轉(zhuǎn)置，而逆關(guān)系的關(guān)系圖就是

4、把關(guān)系 R 的關(guān)系圖中的有向弧的方向改變。3關(guān)系的性質(zhì)：自反性、反自反性、對(duì)稱性、反對(duì)稱性、傳遞性（1）自反性：對(duì)任意，則關(guān)系R 是自反的。自反關(guān)系的矩陣主對(duì)角線元素全為1；自反關(guān)系圖的每個(gè)結(jié)點(diǎn)都有自回路。（2）反自反性：對(duì)，則關(guān)系R 是反自反的。反自反關(guān)系矩陣主對(duì)角線元素全為0；關(guān)系圖的每個(gè)結(jié)點(diǎn)都沒(méi)有自回路。（3）對(duì)稱性：對(duì)，則關(guān)系R 是對(duì)稱的。對(duì)稱關(guān)系的矩陣是對(duì)稱矩陣，即；關(guān)系圖中有向弧成對(duì)出現(xiàn)，方向相反（4）反對(duì)稱性：對(duì)，必有，則關(guān)系R 是反對(duì)稱的；或者，則關(guān)系R 是反對(duì)稱的反對(duì)稱關(guān)系的矩陣不出現(xiàn)對(duì)稱元素，關(guān)系圖中任意兩個(gè)頂點(diǎn)之間或者沒(méi)有有向弧，或者僅有一條有向?。?）傳遞性：對(duì)，則關(guān)系

5、R 是傳遞的 在傳遞關(guān)系的關(guān)系圖中，若有從a 到b 的弧，且有從b 到c 的弧，則必有從a 到c 的弧。4關(guān)系的自反閉包、傳遞閉包和對(duì)稱閉包求解方法（1）求解關(guān)系的自反閉包集合法：把所有的構(gòu)成的有序?qū)?添加到A 上的關(guān)系R 中，就能夠獲得R 的自反閉包r (R)。即：，其中，IA是A上的恒等關(guān)系。矩陣法：若R 的關(guān)系矩陣MR ，通過(guò)公式，就能夠求出R 的自反閉包r (R) 的關(guān)系矩陣Mr ，其中E 是單位矩陣。圖像法：在R 的關(guān)系圖上沒(méi)有自回路的結(jié)點(diǎn)處都添上自回路，就得到了R 的自反閉包r (R) 的關(guān)系圖。（2）求解關(guān)系的對(duì)稱閉包集合法：若R上的任意關(guān)系a , b，若，則把b , a添加到關(guān)

6、系R 中，就能夠獲得R 的對(duì)稱閉包s (R)。即：。矩陣法：若R 的關(guān)系矩陣為MR ，利用公式，就能夠得出R 的對(duì)稱閉包s (R)的關(guān)系矩陣Ms ，其中的轉(zhuǎn)置矩陣. 圖像法：把R 的關(guān)系圖圖上所有單向弧都畫(huà)為雙向弧，就能得到R 的對(duì)稱閉包s (R)的關(guān)系圖（3）求解關(guān)系的傳遞閉包集合法：先求出R2，Rn ，再求它們的并，就能夠獲得R 的傳遞閉包t (R)。即：。矩陣法：若已知R 的關(guān)系矩陣MR ，通過(guò)公式，便能求出R 的傳遞閉包t (R)的關(guān)系矩陣Mt 。圖像法：若已知R 的關(guān)系圖，從關(guān)系圖的每個(gè)結(jié)點(diǎn)ai（i =1，2，n）出發(fā)，找出所有2步，3步，n步長(zhǎng)的路徑，設(shè)路徑的終點(diǎn)為，從aI依次用有

7、向弧連接到，當(dāng)檢查完所有結(jié)點(diǎn)后，就畫(huà)出了R 的傳遞閉包t (R)的關(guān)系圖。5.等價(jià)關(guān)系等價(jià)關(guān)系概念：設(shè)R是非空集合A上的二元關(guān)系，如果R是自反的、對(duì)稱的和傳遞的，則稱R是A上的等價(jià)關(guān)系。設(shè)R是一個(gè)等價(jià)關(guān)系，若R，則稱a等價(jià)于b，記作ab。6.偏序關(guān)系和哈斯圖（1）偏序關(guān)系設(shè)R是非空集合A上的二元關(guān)系，如果R是自反的、反對(duì)稱的和傳遞的，則稱R是A上的偏序關(guān)系或者簡(jiǎn)稱序關(guān)系。偏序關(guān)系記作。，則稱a小于等于b，記作a b。（2）哈斯圖作圖規(guī)則： = 1 * roman i去掉每個(gè)結(jié)點(diǎn)的自回路，用空心點(diǎn)表示集合的元素； = 2 * roman ii對(duì)于集合任意元素a和b，若ab，則將a畫(huà)在b的下方；

8、= 3 * roman iii對(duì)于集合任意元素a和b，若ab，且不存在c使acb，則在a和b之間劃一條弧。（3）最小元、極小元、最大元和極大元，上界和下界一個(gè)子集的極大(小)元可以有多個(gè)，而最大(小)元若有，只能惟一；且極元、最元只在該子集內(nèi)；而上界與下界可在子集之外確定，最小上界是所有上界中最小者，最小上界再小也不會(huì)小于子集中的任一元素；可以與某一元素相等，最大下界也是同樣。7函數(shù)的概念與性質(zhì)（1）函數(shù)的概念設(shè) f 是集合 A 到 B 的二元關(guān)系，若任意 aA，存在 bB，且 f ，Dom ( f ) = A，則 f 是一個(gè)函數(shù)（映射）函數(shù)是一種特殊的關(guān)系。注意：集合 AB 的任何子集都是關(guān)

9、系，但不一定是函數(shù)。函數(shù)要求對(duì)于定義域 A 中每一個(gè)元素 a ，B 中有且僅有一個(gè)元素與 a 對(duì)應(yīng)，而一般的關(guān)系沒(méi)有這個(gè)限制。（2）單射、滿射和雙射的判斷單射：若； 滿射：f (A) = B ，即對(duì)任意 y B，存在 x A，使得 y = f (x) ； 雙射：?jiǎn)紊淝覞M射。（3）函數(shù)的復(fù)合若，則，即。復(fù)合成立的條件是：二、常考知識(shí)點(diǎn)分析?？贾R(shí)點(diǎn)1：關(guān)系的概念與性質(zhì)（歷年考核次數(shù)：4次，本課程共考過(guò)6次；重要程度：）（2010年1月試卷第7題）如果R是非空集合A上的等價(jià)關(guān)系，a A，bA，則可推知R中至少包含 等元素解題過(guò)程： 由等價(jià)關(guān)系的概念，知道R具備了自反性、對(duì)稱性和傳遞性。根據(jù)已知A上

10、的元素a和b，根據(jù)自反的概念，知道R中必須包含和，由對(duì)稱和傳遞概念，得知，也具備對(duì)稱性和傳遞性，因此對(duì)應(yīng)A上的關(guān)系R至少應(yīng)該包含元素，正確答案：，易錯(cuò)點(diǎn)：同學(xué)們對(duì)本題目中要求的最小等價(jià)關(guān)系沒(méi)有理解清楚，容易將答案寫(xiě)為，仔細(xì)觀察可以看出，該關(guān)系去掉和之后，仍然為等價(jià)關(guān)系。提示：先加入自反關(guān)系，然后再根據(jù)等價(jià)關(guān)系加入必要的對(duì)稱和傳遞所需的元素。（2009年7月試卷第2題）集合A=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系R=|x+y=10且x, yA，則R的性質(zhì)為（ ） A自反的 B對(duì)稱的 C傳遞且對(duì)稱的 D反自反且傳遞的解題過(guò)程：首先，可以寫(xiě)出關(guān)系R的有限集合表示，即,容易看出， R，

11、因此R不是自反的。R因此，R不是反自反的。又因?yàn)镽，且R，而 R，因此，R不具備傳遞性。因此，答案選擇B。易錯(cuò)點(diǎn)：同學(xué)們對(duì)關(guān)系的自反性、對(duì)稱性、傳遞性和反自反性沒(méi)有理解清楚，往往是能夠?qū)懗鯮的有限集合表示卻不能用相關(guān)概念進(jìn)行判別。提示：熟練理解關(guān)系以及關(guān)系性質(zhì)概念。（2009年7月試卷第6題）若A=1,2，R=|xA, yA, x+y=10，則R的自反閉包為 。解題過(guò)程：正確答案：，。本題考核的是關(guān)系閉包的計(jì)算。計(jì)算關(guān)系閉包有集合法、矩陣法和關(guān)系圖法。本題目可以直接使用集合法計(jì)算公式。首先容易計(jì)算出R=，IA=，。= IA=，。易錯(cuò)點(diǎn)：有的同學(xué)對(duì)閉包的概念理解不夠清楚。簡(jiǎn)單說(shuō)，閉包是在原有關(guān)系

12、的基礎(chǔ)上，添加最少的有序?qū)?，使得到的新關(guān)系具備某些特定性質(zhì)。如，R自反閉包就是包含R的、并且具備自反性的最小關(guān)系。提示：同學(xué)們可以在理解相關(guān)概念的基礎(chǔ)上，牢記并熟練應(yīng)用閉包的計(jì)算公式。?？贾R(shí)點(diǎn)2： HYPERLINK /mod/resource/view.php?inpopup=true&id=425 t _blank 函數(shù)的概念與性質(zhì)（歷年考核次數(shù)：4次，本課程共考過(guò)6次；重要程度：）（2009年7月試卷第7題）設(shè)A=a，b，c，B=1，2，作f：AB，則不同的函數(shù)個(gè)數(shù)為 。解題過(guò)程：本題目考核的是學(xué)生對(duì)函數(shù)概念的理解。函數(shù)可以有下面映射規(guī)則：（1）a,b,c全映射到2；（2）a映射到1，

13、b和c映射到2；（3）b映射到1，a和c映射到2；（4）c映射到1，a和b映射到2；（5）a映射到2，b和c映射到1；（6）b映射到2，a和c映射到1；（7）c映射到2，a和b映射到1；（8）a,b,c全映射到1；因此，函數(shù)個(gè)數(shù)為8。另外，此類題目也可以作以下分析。A到B映射個(gè)數(shù)可以描述為：=8 正確答案：8易錯(cuò)點(diǎn)：同學(xué)們對(duì)函數(shù)的單值性理解不夠清楚，可能會(huì)認(rèn)為A中必須有元素與B中元素唯一對(duì)應(yīng)。提示：函數(shù)概念中，有兩點(diǎn)尤其要注意。第一，是函數(shù)的單值性，即對(duì)于A中任何元素，必須有B中元素映射f唯一對(duì)應(yīng)；第二，是函數(shù)的定義域，即A是函數(shù)f定義域。（2009年1月試卷第14題）判斷說(shuō)明：設(shè)N、R分別為

14、自然數(shù)集與實(shí)數(shù)集，f：NR，f (x)=x+6，則f是單射。解題過(guò)程：正確。 設(shè)x1，x2為自然數(shù)且x1x2，則有f(x1)= x1+6 x2+6= f(x2)，故f為單射。 易錯(cuò)點(diǎn)：同學(xué)們對(duì)函數(shù)單射概念理解不夠清楚，可能會(huì)認(rèn)為對(duì)于R中的小數(shù)，自然數(shù)集中無(wú)法用函數(shù)f對(duì)應(yīng)，因此給出“錯(cuò)誤”判定結(jié)論。提示：“單射”概念中，強(qiáng)調(diào)的是對(duì)于不同定義域中的值，通過(guò)函數(shù)映射得到的對(duì)應(yīng)值不同，這種“一對(duì)一”是從前到后的一對(duì)一，并不要求從后到前一對(duì)一。（2009年1月試卷第14題）設(shè)A=a, b，B=1, 2，R1，R2，R3是A到B的二元關(guān)系，且R1=, ，R2=, , ，R3=, ，則（ ）不是從A到B的函

15、數(shù)。 AR1和R2 BR2 CR3 DR1和R3解題過(guò)程：選擇A錯(cuò)誤正確答案：B函數(shù)的概念中，強(qiáng)調(diào)兩點(diǎn)：第一，函數(shù)的單值性，即對(duì)于每一個(gè)定義域中的值，只能有一個(gè)對(duì)應(yīng)函數(shù)值；第二，函數(shù)的定義域必須為集合A。本題中的R2不符合函數(shù)概念強(qiáng)調(diào)的第一點(diǎn)。易錯(cuò)點(diǎn)：有的同學(xué)可能認(rèn)為R1也不是函數(shù)，理由是a和b的對(duì)應(yīng)的是相同值。這是對(duì)函數(shù)概念理解常見(jiàn)的錯(cuò)誤。函數(shù)概念并不要求值域中的值必須與定義域唯一對(duì)應(yīng)。提示：判斷一個(gè)二元關(guān)系是否為函數(shù)，要按照函數(shù)概念所規(guī)定的兩個(gè)條件逐一比較，只要完全符合便可得到正確判斷。?？贾R(shí)點(diǎn)3： HYPERLINK /mod/resource/view.php?inpopup=tru

16、e&id=425 t _blank 序關(guān)系（歷年考核次數(shù)：4次，本課程共考過(guò)6次；重要程度：）（2009年7月試卷第14題）若偏序集的哈斯圖如圖二所示，則集合A的最大元為a，最小元不存在。 圖二解題過(guò)程：判斷結(jié)論：錯(cuò)誤。集合A的最大元不存在，a是極大元。若a為最大元，則對(duì)于任意xA，必有R，但從圖中可以得知，R，因此a不是最大元。同時(shí)，不存在xA，滿足R，因此，a為極大元。易錯(cuò)點(diǎn)：同學(xué)們對(duì)序關(guān)系的相關(guān)概念理解不夠透徹。哈斯圖不是簡(jiǎn)單的層次關(guān)系圖，不要用層次關(guān)系判斷最大元、最小元、極大元、極小元等。提示：最小元應(yīng)小于等于其它各元素；最大元應(yīng)該大于等于其它個(gè)元素；極小元應(yīng)該小于等于一些元素，而與剩

17、下的元素沒(méi)有關(guān)系；極大元應(yīng)該大于等于一些元素，而與剩下的元素沒(méi)有關(guān)系。最大元和最小元不一定存在，如果存在則必定唯一。（2009年10月試卷第3題）設(shè)集合A=1，2，3，4，5，偏序關(guān)系是A上的整除關(guān)系，則偏序集上的元素5是集合A的（ ）A最大元 B極大元 C最小元 D極小元解題過(guò)程：選擇A錯(cuò)了。正確答案：B。由于元素4和5沒(méi)有整除關(guān)系，顯然5不是最大元。同理，5和2沒(méi)有整除關(guān)系，5也不是最小元。易錯(cuò)點(diǎn)：同學(xué)們對(duì)序關(guān)系的相關(guān)概念理解不夠透徹。哈斯圖不是簡(jiǎn)單的層次關(guān)系圖，不要用層次關(guān)系判斷最大元、最小元、極大元、極小元等。提示：整除關(guān)系是?？嫉囊活惼蜿P(guān)系。兩個(gè)元素是否具備整除關(guān)系可以不直接表達(dá)，

18、所以題型描述簡(jiǎn)單，但是同學(xué)們需要將序關(guān)系的概念應(yīng)用到此類題目中才能正確辨別。三、模擬練習(xí)練習(xí)1 ：（2010年1月試卷第6題）設(shè)集合A=2, 3, 4，B=1, 2, 3, 4，R是A到B的二元關(guān)系， 則R的有序?qū)蠟?解析：答案為，對(duì)于A中元素2，滿足條件在集合B中的元素為2、3和4，因此，有序?qū)?yīng)該包括，和。對(duì)于A中元素3，滿足條件在集合B中的元素為3和4，因此，有序?qū)?yīng)該包括，。對(duì)于A中元素4，滿足條件在集合B中的元素為4，因此，有序?qū)?yīng)該包括。匯總上面結(jié)論，R的有序?qū)蠟椋?，練?xí)2 ：（2009年7月試卷第2題）集合A=1, 2, 3, 4上的關(guān)系R=|x=y且x, yA，則R的性

19、質(zhì)為（ ） A不是自反的 B不是對(duì)稱的 C傳遞的 D反自反解析：答案為C 本題目考的知識(shí)點(diǎn)是關(guān)系的集合表示以及關(guān)系的性質(zhì)。根據(jù)關(guān)系R的描述，可以將有限集合A上關(guān)系R表示為，由關(guān)系自反、反自反以及對(duì)稱和傳遞的概念，可知關(guān)系R滿足自反性、對(duì)稱性和傳遞性。 因此答案選擇為C。練習(xí)3 ：（2009年10月試卷第7題）設(shè)集合A=1，2，3上的函數(shù)分別為：f=, , ,，g=, , ,，則復(fù)合函數(shù)gf = 解析：, , 本題考核的是復(fù)合函數(shù)的概念。對(duì)于f中元素，g中存在元素， 使f(1)=2，g (2)=2，因此 gf。同理，對(duì)于f中的元素，g中存在元素以及f中的元素，g中存在元素使和滿足復(fù)合函數(shù)的概念。因此，答案為, , 。練習(xí)4 ：（2008年7月試卷第3題）如果R1和R2是A上的自反關(guān)系，則R1R2，R1R2，R1-R2中自反關(guān)系有（ ）個(gè) A0 B2 C1 D3解析：答案B本題目考核的是集合的運(yùn)算以及關(guān)系自反性的概念。因?yàn)镽1和R2是A上的自反關(guān)系，對(duì)于A中任意元素a，均同時(shí)滿足 R1