離散數(shù)學?？碱}型梳理

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

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

3、合是由有序?qū)υ亟M成的，才能當做二元關(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)系的集合運算、復合運算和逆運算：關(guān)系的集合運算與普通集合運算基本相同，主要為并運算、交運算、補運算、差運算和對稱差運算。關(guān)系復合運算，描述為復合關(guān)系滿足結(jié)合律：關(guā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ì)：自反性、反自反性、對稱性、反對稱性、傳遞性（1）自反性：對任意，則關(guān)系R 是自反的。自反關(guān)系的矩陣主對角線元素全為1；自反關(guān)系圖的每個結(jié)點都有自回路。（2）反自反性：對，則關(guān)系R 是反自反的。反自反關(guān)系矩陣主對角線元素全為0；關(guān)系圖的每個結(jié)點都沒有自回路。（3）對稱性：對，則關(guān)系R 是對稱的。對稱關(guān)系的矩陣是對稱矩陣，即；關(guān)系圖中有向弧成對出現(xiàn)，方向相反（4）反對稱性：對，必有，則關(guān)系R 是反對稱的；或者，則關(guān)系R 是反對稱的反對稱關(guān)系的矩陣不出現(xiàn)對稱元素，關(guān)系圖中任意兩個頂點之間或者沒有有向弧，或者僅有一條有向?。?）傳遞性：對，則關(guān)系

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

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

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

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

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

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

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

12、的基礎(chǔ)上，添加最少的有序?qū)?，使得到的新關(guān)系具備某些特定性質(zhì)。如，R自反閉包就是包含R的、并且具備自反性的最小關(guān)系。提示：同學們可以在理解相關(guān)概念的基礎(chǔ)上，牢記并熟練應用閉包的計算公式。?？贾R點2： HYPERLINK /mod/resource/view.php?inpopup=true&id=425 t _blank 函數(shù)的概念與性質(zhì)（歷年考核次數(shù)：4次，本課程共考過6次；重要程度：）（2009年7月試卷第7題）設A=a，b，c，B=1，2，作f：AB，則不同的函數(shù)個數(shù)為 。解題過程：本題目考核的是學生對函數(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ù)個數(shù)為8。另外，此類題目也可以作以下分析。A到B映射個數(shù)可以描述為：=8 正確答案：8易錯點：同學們對函數(shù)的單值性理解不夠清楚，可能會認為A中必須有元素與B中元素唯一對應。提示：函數(shù)概念中，有兩點尤其要注意。第一，是函數(shù)的單值性，即對于A中任何元素，必須有B中元素映射f唯一對應；第二，是函數(shù)的定義域，即A是函數(shù)f定義域。（2009年1月試卷第14題）判斷說明：設N、R分別為

14、自然數(shù)集與實數(shù)集，f：NR，f (x)=x+6，則f是單射。解題過程：正確。 設x1，x2為自然數(shù)且x1x2，則有f(x1)= x1+6 x2+6= f(x2)，故f為單射。 易錯點：同學們對函數(shù)單射概念理解不夠清楚，可能會認為對于R中的小數(shù)，自然數(shù)集中無法用函數(shù)f對應，因此給出“錯誤”判定結(jié)論。提示：“單射”概念中，強調(diào)的是對于不同定義域中的值，通過函數(shù)映射得到的對應值不同，這種“一對一”是從前到后的一對一，并不要求從后到前一對一。（2009年1月試卷第14題）設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解題過程：選擇A錯誤正確答案：B函數(shù)的概念中，強調(diào)兩點：第一，函數(shù)的單值性，即對于每一個定義域中的值，只能有一個對應函數(shù)值；第二，函數(shù)的定義域必須為集合A。本題中的R2不符合函數(shù)概念強調(diào)的第一點。易錯點：有的同學可能認為R1也不是函數(shù)，理由是a和b的對應的是相同值。這是對函數(shù)概念理解常見的錯誤。函數(shù)概念并不要求值域中的值必須與定義域唯一對應。提示：判斷一個二元關(guān)系是否為函數(shù)，要按照函數(shù)概念所規(guī)定的兩個條件逐一比較，只要完全符合便可得到正確判斷。常考知識點3： HYPERLINK /mod/resource/view.php?inpopup=tru

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

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

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

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