離散數(shù)學考試真題解析寫在前面離散數(shù)學作為計算機科學與技術(shù)、軟件工程等專業(yè)的核心基礎(chǔ)課程，其概念抽象、邏輯性強，對學習者的抽象思維能力和邏輯推理能力提出了較高要求。期末考試不僅是對知識掌握程度的檢驗，更是對運用這些知識解決實際問題能力的考察。本文將結(jié)合幾道典型的離散數(shù)學考試真題，進行深入解析，希望能為同學們理解離散數(shù)學的核心概念、掌握解題方法提供一些幫助。我們將側(cè)重于思路的引導和方法的提煉，而不僅僅是答案的呈現(xiàn)。一、命題邏輯例題1：符號化下列命題，并判斷其真值?！叭绻裉焓切瞧谝唬敲疵魈焓切瞧诙?；反之亦然?！苯馕觯菏紫龋覀冃枰鞔_命題符號化的基本步驟。對于這種復合命題，關(guān)鍵在于識別聯(lián)結(jié)詞，并將原子命題用命題變元表示。設(shè)P：今天是星期一。設(shè)Q：明天是星期二。原命題中包含兩個部分：“如果今天是星期一，那么明天是星期二”以及“反之亦然”?！叭绻?..那么...”是典型的蘊含聯(lián)結(jié)詞，即“P→Q”?！胺粗嗳弧痹谶@里的意思是“如果明天是星期二，那么今天是星期一”，即“Q→P”。所以整個命題是這兩個蘊含式的合取。因此，符號化為：(P→Q)∧(Q→P)。我們知道，(P→Q)∧(Q→P)等價于P?Q（等價聯(lián)結(jié)詞），即“P當且僅當Q”。接下來判斷其真值。在現(xiàn)實的時間序列中，“今天是星期一”與“明天是星期二”這兩個命題的真值總是相同的：當P為真時Q必為真，當P為假時（即今天不是星期一），Q也為假（明天不是星期二）。因此，P與Q要么同真，要么同假，根據(jù)等價聯(lián)結(jié)詞的定義，P?Q的真值為真。考點總結(jié)：本題主要考察命題的符號化，特別是蘊含聯(lián)結(jié)詞與等價聯(lián)結(jié)詞的理解和應(yīng)用。需要準確把握自然語言中聯(lián)結(jié)詞的邏輯含義，并能正確運用邏輯符號表示。同時，對等價式的直觀理解和真值判斷也是考察的一個方面。二、集合與關(guān)系例題2：設(shè)集合A={a,b,c}，R是A上的二元關(guān)系，R={(a,a),(a,b),(b,c),(c,a)}。(1)畫出R的關(guān)系圖。(2)求出R的自反閉包r(R)和對稱閉包s(R)。(3)判斷R是否為等價關(guān)系，并說明理由。解析：這是一道關(guān)于集合上二元關(guān)系基本性質(zhì)及閉包運算的典型題目。(1)關(guān)系圖的繪制：集合A中的元素作為關(guān)系圖的頂點，通常用小圓圈表示，并在圈內(nèi)標注元素。對于關(guān)系R中的每一個有序?qū)?x,y)，我們從頂點x向頂點y畫一條有向邊。因此，R的關(guān)系圖頂點為a,b,c。邊有：從a到a（自環(huán)），從a到b，從b到c，從c到a。(2)求自反閉包r(R)和對稱閉包s(R)：*自反閉包r(R)：自反閉包是包含R且具有自反性的最小關(guān)系。集合A上的關(guān)系具有自反性，當且僅當對A中的每一個元素x，(x,x)都屬于該關(guān)系。原關(guān)系R中已有(a,a)，但缺少(b,b)和(c,c)。因此，r(R)=R∪{(b,b),(c,c)}={(a,a),(a,b),(b,c),(c,a),(b,b),(c,c)}。*對稱閉包s(R)：對稱閉包是包含R且具有對稱性的最小關(guān)系。關(guān)系具有對稱性，當且僅當如果(x,y)屬于該關(guān)系，則(y,x)也屬于該關(guān)系。原關(guān)系R中有(a,b)，則需添加(b,a)；有(b,c)，則需添加(c,b)；有(c,a)，則需添加(a,c)；(a,a)本身是對稱的，無需添加。因此，s(R)=R∪{(b,a),(c,b),(a,c)}={(a,a),(a,b),(b,c),(c,a),(b,a),(c,b),(a,c)}。(3)判斷R是否為等價關(guān)系：等價關(guān)系需要同時滿足自反性、對稱性和傳遞性。*自反性：如(2)中所述，R中缺少(b,b)和(c,c)，因此不滿足自反性。*對稱性：R中有(a,b)，但沒有(b,a)；有(b,c)，但沒有(c,b)；有(c,a)，但沒有(a,c)，因此不滿足對稱性。*傳遞性：我們檢查是否對所有x,y,z，若(x,y)∈R且(y,z)∈R，則(x,z)∈R。例如，(a,b)∈R且(b,c)∈R，但(a,c)?R，因此不滿足傳遞性。由于R不滿足自反性、對稱性和傳遞性中的任何一條（實際上只要有一條不滿足即可），因此R不是等價關(guān)系?？键c總結(jié)：本題綜合考察了關(guān)系圖的表示、關(guān)系的基本性質(zhì)（自反、對稱、傳遞）的判斷以及閉包運算（自反閉包、對稱閉包）的計算。這些都是集合與關(guān)系部分的核心內(nèi)容，需要熟練掌握關(guān)系圖的畫法，深刻理解各性質(zhì)的定義，并能準確計算閉包。等價關(guān)系的判斷需要對三個性質(zhì)逐一進行驗證。三、圖論例題3：設(shè)無向圖G有8個頂點，各頂點的度數(shù)分別為1,1,2,2,3,3,4,4。(1)G有多少條邊？(2)證明G不是簡單圖。解析：(1)求邊數(shù)：對于任何無向圖，握手定理告訴我們：所有頂點的度數(shù)之和等于邊數(shù)的兩倍。設(shè)邊數(shù)為m。則頂點度數(shù)之和為：1+1+2+2+3+3+4+4=(1+1)+(2+2)+(3+3)+(4+4)=2+4+6+8=20。根據(jù)握手定理：2m=20→m=10。因此，G有10條邊。(2)證明G不是簡單圖：簡單圖是指不含平行邊（多重邊）和自環(huán)的圖。要證明G不是簡單圖，我們可以嘗試從簡單圖的必要條件入手，或者尋找矛盾。一種常用的方法是利用“在n個頂點的簡單圖中，每個頂點的度數(shù)至多為n-1”這一性質(zhì)。但在此題中，最大度數(shù)為4，n=8，4≤8-1=7，因此這條性質(zhì)無法直接得出結(jié)論。另一種思路是考慮度數(shù)序列是否可圖化（對于簡單圖而言，是可簡單圖化）。我們可以使用Havel-Hakimi定理來判斷一個非負整數(shù)序列是否是可簡單圖化的。Havel-Hakimi定理：給定一個非負整數(shù)序列d?≥d?≥...≥d?，且其和為偶數(shù)。按降序排列：4,4,3,3,2,2,1,1。取第一個數(shù)4，去掉它，然后將接下來的4個數(shù)都減1：序列變?yōu)椋?4-1),(3-1),(3-1),(2-1),2,1,1→3,2,2,1,2,1,1。重新按降序排列：3,2,2,2,1,1,1。取第一個數(shù)3，去掉它，將接下來的3個數(shù)都減1：序列變?yōu)椋?2-1),(2-1),(2-1),1,1,1→1,1,1,1,1,1。此時得到的序列是1,1,1,1,1,1，這顯然是可簡單圖化的（例如一個6頂點的簡單圖，每兩個頂點之間有一條邊？不，6個1的話，是3條邊的匹配）。咦，按照Havel-Hakimi定理，這個序列似乎是可簡單圖化的？這與題目要求證明“不是簡單圖”矛盾。難道我哪里出錯了？哦，不對，Havel-Hakimi定理是判斷是否存在簡單圖的充分必要條件。那是不是題目有問題，還是我的理解有誤？或者，我是否忽略了什么？讓我再仔細看看題目：“證明G不是簡單圖”。如果根據(jù)Havel-Hakimi定理，這個度數(shù)序列是可簡單圖化的，那么就存在這樣的簡單圖。這說明我的推理過程可能有誤?；蛘?，是不是我在應(yīng)用Havel-Hakimi定理時犯了錯誤？原始度數(shù)序列：4,4,3,3,2,2,1,1。和為20，是偶數(shù)。第一步：取4，去掉，后面4個數(shù)減1：原序列去掉第一個4后，剩下的序列是4,3,3,2,2,1,1。然后對前4個數(shù)減1：4-1=3，3-1=2，3-1=2，2-1=1。得到新序列：3,2,2,1,2,1,1。然后排序：3,2,2,2,1,1,1。這一步是對的。第二步：取3，去掉，后面3個數(shù)減1：剩下的序列是2,2,2,1,1,1。對前3個數(shù)減1：2-1=1，2-1=1，2-1=1。得到新序列：1,1,1,1,1,1。這也是對的。1,1,1,1,1,1是可簡單圖化的，比如一個3K?（三個不相連的邊）。所以，根據(jù)Havel-Hakimi定理，原序列是可簡單圖化的。這說明存在以該序列為度序列的簡單圖。那么，題目說“證明G不是簡單圖”，這就意味著，題目中的“G”可能指的是“任意一個具有該度數(shù)序列的無向圖”嗎？或者題目本身是否有瑕疵？不，更可能的是，我最初的理解可能過于依賴Havel-Hakimi定理的正面應(yīng)用。Havel-Hakimi定理告訴我們“如果按照步驟能得到全零序列，則可簡單圖化”，但它并沒有說“如果一個序列滿足某些條件就一定不是簡單圖”?；蛘?，是不是題目中的“無向圖G”是特指某個圖？但題目描述中只給出了度數(shù)序列。啊，我明白了！可能我之前的思路被Havel-Hakimi定理帶偏了。題目說“證明G不是簡單圖”，但根據(jù)度數(shù)序列，我們只能說“存在一個簡單圖具有該度數(shù)序列”，但不能說“所有具有該度數(shù)序列的圖都是簡單圖”。但題目并沒有給出G的更多信息，只給了度數(shù)序列。這似乎有點矛盾。或者，是否存在其他限制？比如，對于8個頂點的簡單圖，其最大邊數(shù)為C(8,2)=28。我們算出的邊數(shù)是10，遠小于28，這不是問題。再仔細想想，是否有其他角度？比如，考慮度數(shù)為4的兩個頂點。每個頂點要與其他4個不同的頂點相連。在簡單圖中，它們不能與自身相連，也不能有多重邊。假設(shè)兩個4度頂點為u和v。u需要連接4個不同的頂點，v也需要連接4個不同的頂點。如果u和v之間沒有邊相連，那么u要從剩下的6個頂點（8-1（自身）-1（v）=6）中選4個，v也要從剩下的6個頂點中選4個。這是可能的。如果u和v之間有邊相連，那么u還需要連接3個其他頂點，v也還需要連接3個其他頂點。這也是可能的。那么，題目要求“證明G不是簡單圖”，這似乎與Havel-Hakimi定理的結(jié)論相悖。這說明什么？哦！我可能犯了一個根本性的錯誤。Havel-Hakimi定理的前提是“非負整數(shù)序列”，并且“序列的和為偶數(shù)”。我們的序列滿足這些。那么，根據(jù)定理，就一定存在一個簡單圖。所以，題目說“證明G不是簡單圖”，這可能意味著題目本身的表述或者我對題目的理解有誤？或者，是否題目中的“無向圖G”有其他隱含條件？或者，會不會是我在計算邊數(shù)的時候算錯了？1+1+2+2+3+3+4+4=20，20/2=10。邊數(shù)是10，沒錯。8個頂點的簡單圖，邊數(shù)10，完全可以存在。例如，一個8頂點的簡單圖，包含一個5頂點的完全圖K5（邊數(shù)10），但K5每個頂點的度數(shù)是4，有5個頂點，這與我們的度數(shù)序列不符。但可以構(gòu)造其他的。看來，可能是題目本身存在問題，或者我對題目的理解有偏差。但根據(jù)現(xiàn)有信息，按照Havel-Hakimi定理，給定的度數(shù)序列是可簡單圖化的，即存在這樣的簡單圖。因此，“證明G不是簡單圖”這個要求，如果G是指“具有該度數(shù)序列的任意一個無向圖”，那么這個命題本身就是不成立的。如果G是指“某個特定的具有該度數(shù)序列的無向圖”，但題目沒有給出更多關(guān)于G的結(jié)構(gòu)信息，我們也無法證明它不是簡單圖。（*此處思考：如果題目改為“證明G可能不是簡單圖”或者“舉例說明存在具有該度數(shù)序列的非簡單圖”，則更為合理?；蛘撸}的度數(shù)序列可能我抄錄有誤？例如，如果最大度數(shù)是5，那么對于8個頂點，5≤7，Havel-Hakimi走下來也可能成立?；蛘撸绻葦?shù)之和是奇數(shù)，則直接不是圖。但目前來看，題目給出的度數(shù)序列和為20，是偶數(shù)。*）（修正思路）或許，我應(yīng)該換一個角度。如果題目堅持要證明“G不是簡單圖”，那么可能是在假設(shè)“G是簡單圖”的前提下，會推出與已知條件或圖論基本定理相矛盾的結(jié)論。假設(shè)G是簡單圖。那么，根據(jù)圖論中關(guān)于簡單圖的一個推論：在任何簡單圖中，度數(shù)為k的頂點個數(shù)不能超過n-k-1（當k<n時）。不過這個結(jié)論并不絕對，它是在特定情況下，比如在證明Ramsey數(shù)或某些極端圖時可能用到，但并非普適定理?；蛘?，考慮所有頂點的度數(shù)之和為20，邊數(shù)為10。對于8個頂點的簡單圖，其邊數(shù)可以是0到28之間的任何整數(shù)。10是合理的。因此，我傾向于認為，在原題給定的條件下，無法證明G一定不是簡單圖，反而存在是簡單圖的可能。這可能是題目設(shè)置上的一個小瑕疵，或者是我個人理解的局限。在考試中，如果遇到此類問題，應(yīng)首先檢查自己的計算和推理步驟是否正確。如果確信度數(shù)序列可簡單圖化，那么可以指出這一點?？键c總結(jié)：本題主要考察握手定理的應(yīng)用以及對簡單圖概念的理解。握手定理是圖論中最基本的定理之一，必須熟練掌握和應(yīng)用。對于簡單圖的判斷，Havel-Hakimi定理是一個非常有力的工具，需要理解其原理和應(yīng)用步驟。在解決問題時，嚴謹?shù)倪壿嬐评砗蛯Χɡ項l件的準確把握至關(guān)重要?？偨Y(jié)與備考建議通過對以上幾道典型真題的解析，我們可以看出離散數(shù)學的考試重點在于對基本概念的理解、基本定理的應(yīng)用以及邏輯推理能力的展現(xiàn)。為了更好地備考，建議同學們：1.回歸課本，夯實基礎(chǔ)：離散數(shù)學的概念繁多且抽象，務(wù)必吃透每一個定義、定理和推論，理解其來龍去脈和適用場景。2.多做練習，注重思路：做題不是為了題海戰(zhàn)術(shù)，而是為了熟悉不同