1、學習資料收集于網絡，僅供參考離散數學期末復習大綱一、數理邏輯復習知識點 1、命題與聯結詞（否定、析取、合取、蘊涵、等價? ），復合命題2、命題公式與賦值（成真、成假） ，真值表，公式類型（重言、矛盾、可滿足） ，公式的基本等值式3、范式：析取范式、合取范式，極大（小）項，主析取范式、主合取范式4、公式類型的判別方法（真值表法、等值演算法、主析取/合取范式法）5、命題邏輯的推理理論6、謂詞、量詞、個體詞（一階邏輯3 要素）、個體域、變元（約束出現與自由出現）7、命題符號化、謂詞公式賦值與解釋，謂詞公式的類型（永真、永假、可滿足）8、謂詞公式的等值式（代換實例、消去量詞、量詞否定和量詞轄域收與擴、

2、量詞分配）和置換規則（置換規則、換名規則）9、一階邏輯前束范式（定義、求法）本章重點內容： 命題與聯結詞、公式與解釋、 （主）析取范式與（主）合取范式、公式類型的判定、命題邏輯的推理、謂詞與量詞、命題符號化、謂詞公式賦值與解釋、求前束范式。復習要求 1、理解命題的概念；了解命題聯結詞的概念；理解用聯結詞產生復合命題的方法。2、理解公式與賦值的概念；掌握求給定公式真值表的方法，用基本等值式化簡其它公式，公式在解釋下的真值。3、了解析取（合取）范式的概念；理解極大（小）項的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表將公式化為主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主

3、析取/合取范式的唯一性判別公式類型和公式等價方法。5、掌握命題邏輯的推理理論。6、理解謂詞、量詞、個體詞、個體域、變元的概念；理解用謂詞、量詞、邏輯學習資料學習資料收集于網絡，僅供參考聯結詞描述一個簡單命題；掌握命題的符號化。7、理解公式與解釋的概念；掌握在有限個體域下消去公式量詞，求公式在給定解釋下真值的方法；了解謂詞公式的類型。8、掌握求一階邏輯前束范式的方法。二、集合復習知識點 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集2、集合的交、并、差、補以及對稱差等運算及有窮集的計數（文氏（Venn）圖、包含排斥原理）3、集合恒等式（冪等律、交換律、結合律、分配律、吸

4、收律、矛盾律、德摩根律等）及應用本章重點內容： 集合的概念、集合的運算性質、集合恒等式的證明。復習要求 1、理解集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補、對稱差等基本運算。3、掌握集合運算基本規律，證明集合等式的方法。三、二元關系復習知識點 1、序偶、迪卡兒積，迪卡兒積的性質及運算。2、二元關系（定義、空關系、全域關系、恒等關系）、關系表達式、關系矩陣與關系圖3、關系的定義域、值域、限制、像、復合關系（右復合）與逆關系4、關系的性質（自反性、反自反性、對稱性、反對稱性、傳遞性）5、關系的閉包（自反閉包、對稱閉包、傳遞閉包）6、等

5、價關系與等價類、商集、劃分7、偏序關系與哈斯圖、極大/小元、最大 /小元學習資料學習資料收集于網絡，僅供參考本章重點內容： 二元關系的概念、關系的性質、關系的閉包、等價關系及劃分、偏序關系和哈斯圖復習要求 1、了解序偶與迪卡兒積的概念，掌握迪卡兒積的運算。2、理解關系的概念：二元關系、空關系、全域關系、恒等關系；掌握關系的集合表示、關系矩陣和關系圖、關系的運算。3、掌握求復合關系與逆關系的方法。4、理解關系的性質（自反性、反自反性、對稱性、反對稱性、傳遞性），掌握其判別方法（定義、圖）。5、掌握求關系的閉包（自反閉包、對稱閉包、傳遞閉包）的方法。6、理解等價關系和劃分、掌握等價類和劃分的求法7

6、、理解偏序關系的概念，掌握畫哈斯圖的方法，極大/小元、最大 /小元的求法。四、函數復習知識點 1、理解函數概念：函數、函數相等、A 到 B 的函數。2、理解單射、滿射、雙射等概念，掌握其判別方法。3、函數的復合與反函數本章重點內容：函數的定義及判別方法、 函數的三大性質、函數的復合與反函數。復習要求 1、掌握函數及從 A 到 B 的函數的判別方法。2、理解函數的像與原像。3、掌握函數的單射、滿射、雙射的判別方法。4、掌握求函數的復合與反函數的方法。五、圖論復習知識點 1、 圖的基本概念：無向圖與有向圖、頂點與邊的關聯關系、頂點（邊）與頂點學習資料學習資料收集于網絡，僅供參考（邊）之間鄰接關系、

7、 簡單圖與多重圖、 頂點度數（度）與握手定理、 圖的同構、完全圖、子（補）圖。2、 通路與回路、簡單通（回）路與初級通（回）路；連通圖與非連通圖、連通分支、點割集、邊割集、點（邊）連通度；強連通圖、單向連通圖與弱連通圖；二部圖。3、 圖的矩陣表示：關聯矩陣、鄰接矩陣、可達矩陣。4、 歐拉通（回）路、（半）歐拉圖；哈密爾頓通（回）路、 （半）哈密爾頓圖；5、 無向樹、生成樹、帶權樹、最小生成樹。6、 有向樹、樹根、有序樹、二叉樹、最優二叉樹、前綴碼、最佳前綴碼、霍夫曼（ Huffman）算法、二叉樹的周游及應用。本章重點內容：握手定理、點（邊）割集、通路與回路、特殊圖（歐拉圖與哈密頓圖、無（有）

8、向樹） 、最優二叉樹、最佳前綴碼、霍夫曼（ Huffman）算法。復習要求 1、理解圖的有關概念：圖、完全圖、簡單圖、子圖、母圖、生成子圖等。2、深刻理解握手定理及其推論的內容，并能熟練地應用它們。3、能判斷兩個圖是否同構。4、理解連通度、點割集、邊割集、割邊和割點。5、能判斷圖是否為強連通圖、單向連通圖與弱連通圖。6、理解圖的矩陣表示（關聯矩陣、相鄰矩陣）和性質以及熟練掌握用有向圖的鄰接矩陣及各次冪求圖中通路與回路數的方法。4、理解歐拉圖、哈密頓圖的定義及判別定理。在無向圖中找出一條歐拉通路或歐拉回路、哈密頓通路或哈密頓回路。5、理解無向樹的定義，熟練掌握無向樹的主要性質，并能靈活應用它們。

9、6、理解生成樹的有關概念與性質。7、理解有向樹、根樹、二叉樹和前綴碼的有關概念；掌握用霍夫曼（ Huffman）算法求帶權圖的最優二分樹， 掌握求最佳前綴碼方法， 二叉樹的中序和前序行遍法。學習資料學習資料收集于網絡，僅供參考考試說明一、考核方式1）期末筆試為 100 分鐘的閉卷考試，占總評成績的70。2）平時成績來自作業、考勤和課堂考核，占總評成績30。二、各部分比例（大概為講授學時*2.5 ）1）數理邏輯： 35 分2）集合論： 40 分3）圖論：25 分三、考題類型1）單選題： 20 題，每題 1 分，共 20 分2）判斷題： 20 題，每題 1 分，共 20 分3）填空題： 10 題，

10、每題 2 分，共 20 分4）綜合題： 5 題，每題 8 分，共 40 分四、常見綜合題1. 用等值演算法證明等值式。2. 在自然推理系統 P 中構造證明推理（多種方法）3. 用等值演算法求解主析取范式或主合取范式，計算分析4. 集合恒等式的證明或化簡 (1-2 例題或練習 )5. 集合的運算，有窮集的計數（文氏圖、包含排斥原理）6. 求二元關系導出的劃分 (1-2 例題或作業 )7. 給定一個偏序集，畫出哈斯圖并求極大、極小元素、求最大、最小元素、上界、最小上界、下界、最大下界、上確界和下確界。8. 圖的集合表示、圖形表示、矩陣表示，以及相互之間的轉換。9. 利用握手定理，無向樹中的頂點數、

11、邊數、度數、葉子數，知道其中部分數據，求其余部分數據。10. 用 Huffman 算法求 最優二叉樹產生的最佳前綴碼（根樹的應用） 。學習資料學習資料收集于網絡，僅供參考離散數學試卷結構及樣題一、單選題（20小題，每題 1分，共 20分）1.設 M ( x)：x 是人， P( x)：x 犯錯誤，命題“沒有不犯錯誤的人” 符號化為（）A. x(M ( x)P( x)B.(x(M ( x)P(x)C. ( x(M (x)P( x)D.(x( M (x)P( x)2.設 A= x, y , B= y, z 則 A×B 為（）A. ( x, y),(x, z) ,( y, y),(y, z)

12、B.( y, x),(x, z) ,(y,y),(y,z)C. ( x, y),(z, x) ,( y, y),(y, z)D. ( x, y),(x, z) ,(y,y),(z,y)3.設集合 A=1,2,3 ,A 上的關系 R(1,1),(2,2),(2,3),(3,3),(3,1),則R具有()A. 反自反性B.傳遞性C.對稱性D.以上答案都不對4.關于整數集 Z 上的“”關系 R，以下描述不正確的是（）A.R 的自反閉包是“”關系B.R 的對稱閉包是“”關系C.R 的傳遞閉包是它本身D.R 的反自反閉包是“”5.下列圖中（）是歐拉圖二、判斷題（20 小題，每題 1 分，共 20 分）1

13、.公式 (xF(x)yG(y)yG(y)是可滿足式。 （）2.(AB)(BC) (AC)這個定律叫做假言三段論。（）3. 設 A=a，b，c，d，R 是 A 上的一個二元關系， R = < a,a >,< a,c >,< b,b >,<c,c >是自反的，是反對稱的，是傳遞的。（）4.在每個圖中，所有頂點的度數之和等于邊數的兩倍。（）5.樹是不包含回路的連通圖，在（ n，m）樹中必有 m=n+1（）。學習資料學習資料收集于網絡，僅供參考三、填空題（10 小題，每題 2 分，共 20 分）1.已知命題公式 G ( P Q)R ，則 G的析取范式為。

14、2.設 A=2,3,4,5，若 A上的關系為 R=<x,y>|(x-y)/2是整數 ，則R=。3. R是集合 X上的一個關系，如果 R是自反的，對稱的，傳遞的，則 R稱為。4.無向完全圖 K 的邊數為。n5.在一個圖中，不與任何一個頂點相鄰接的點叫做。四、綜合題（5 小題，每題 8 分，共 40 分）1 用等值演算法證明等值式(p q) (p r)(p (q r) 。2 對偏序集（ 3 ， 5，6， 15，24， 30 ，| ）上的整除關系，畫出哈斯圖并回答下列問題：1）求極大、極小元素；2）求最大、最小元素；3）找出 3 ， 5 的所有上界，如果存在的話求出最小上界；4）找出 1

15、5 ，30 的所有下界，如果存在的話求出最大下界。學習資料學習資料收集于網絡，僅供參考離散數學復習題一、選擇題1.下述句子中哪一個不是命題（）A. 5 是有理數B. 2020 年元旦下大雪C. 我正在說假話D. ln1是整數2.在自然推理系統 P 中，推理規則通常不包括（）A.直接證明法B.前提引入規則C.置換規則D.結論引入規則3.命題 x y( x2y21) 的意義是（）A.對任何 x 均存在 y 使得 x2+y2=1B.對任何 y 均存在 x 使得 x2+y2 =1C.存在 y 對任何 x 均使得 x2+y2=1D. 存在 x 對任何 y 均使得 x2+y2=14.下述句子中哪一個是命題

16、（）A.海南島的天氣好熱啊！B.我知道我什么都不知道C.開會時請關閉手機D.明天天氣晴朗5.判斷推理是否正確的方法通常不包括（）A.真值表法B.歸納法C.等值演算法D.主析取范式法6.在自然推理系統 P 中,聯結詞符號不包括（）A.B.C.D.7.在自然推理系統 P 中，構造證明的方法通常不包括（）A.直接證明法B.附加前提證明法C.歸納法D.歸謬法8.對于集合的表示法，下列表示錯誤的是（）A. x | x 是實數 ? x2 1=0 B. x | x21=0，其中 x 是自然數 C.-1, 1D. x 是實數并且 x21=0 9.下列命題中錯誤的是（）A. 11, 1 B. 11, 1 C.

17、11, 1 D. 1110.下列集合的基數互不相等的是（）A. , 和1, 2B.和C. , 和1,1, 2D. 1，1,1,2,3和1, 1, 211.設 M(x) :x 是人，P(x):x 犯錯誤，命題“沒有不犯錯誤的人” 符號化為（）學習資料學習資料收集于網絡，僅供參考A. x(M ( x) P( x)B.x(M (x)P( x)C.x( M ( x)P(x)D.x(M ( x)P( x)12.設、 是謂詞公式，P是謂詞， xP(x), H xP( x),則謂詞公式 GHG HG是 ()A.永真的B.永假的C.可滿足的D.矛盾的13.對于集合的表示法，下列表示正確的是（）A.(-1 ,

18、0 , 1)B. x | x21=0 ? x 是自然數 C.-1 , 0 , 1D. x 是實數并且 x21=0 14.設 a、b、c 各不相同，對于下列選項中的兩個集合，相等的是（）A. a, b, c和c, a, bB. a, b, c和 a, b,cC. a, b, c和a, b, cD. a, b 和a, b15.設 A、 B、 C 為集合，下列命題中錯誤的是（）A.(A B) B BB.A-B=A B=C. A-B =A BD.A B=B A B=A16.設 A=1,2,3,B =1,2,那么下列不是從 A到 B的二元關系的是（）A. <1, 2>,<1, 3>

19、;B. A×BC.D. <1, 1>,<2, 1>,<3, 1>17.設 R = <1, 2>, <1, 3>, <2, 4>, <4, 1>,則 domR 和 ranR 分別 是（）A. 1, 2, 4和2, 3, 4B. 1, 2, 4和 1, 2, 3, 4C. 1, 2, 3, 4和1, 2, 3D. 1, 2, 3和 1, 2, 3, 418.設 R = <1, 2>, <1, 4>, <2, 2>,<2, 3>, S = <1, 1&g

20、t;, <1, 3>, <2, 3>,<3,2>,<3, 3>，則 R S 是（）A. <1, 3>B. <1, 3>,<2, 3>C. <1, 3>,<2, 3>,<2, 2>D. <1, 3>,<2, 1>, <2, 3>19.設 R = <1, 2>, <1, 3>, <2, 2>, <2, 4>, <3, 1>, <3, 2>，則 R2 是（）A. <1,

21、 2>, <2, 2>, <3, 2>B. <2, 2>, <2, 4>C. 1, 2, 3D. 2, 420.列集合的基數互為相等的是（）A. , 和1, ，1, 2B.和學習資料學習資料收集于網絡，僅供參考C. ,和1, 1, 2, 3D. 1, 1,1,2,3和1, 1, 2, 321.設 X=，Y= P( , )， 下列命題為假的是（）A.X YB.X=YC. XYD. XY22.設 A=1,2,3,B =1,2,那么下列不是從A 到 B 的二元關系的是（）A. <1, 2>,<1, 3>B. A×

22、BC.D. <1, 1>,<2, 1>,<3, 1>23.設 R = <a, b>, <b, c>, <d, b>, <d, c>,則 domR 和 ranR 分別 是（）A. a, b, c和b, c, dB. a, b, d和 b, c, dC. a, b, c和b, cD. a, b, d和 b, c24.下列關系中哪個能構成函數？（）A. <x,y>|x,y N,x+y<10B. <x,y>|x,y N,x+y=20C. <x,y>|x,y R,|x|=yD.

23、<x,y>|x,y Z,x=|y|25. 設無向圖如圖所示，則（）是一條哈密頓回路AgabcdefgBabcdefgC cfabcdegD efgabcd26.設 G 為 n 階 m 條邊的無向連通圖，則下列()是不可能的。A m<n-1B m=n-1C m=nD m=n+127.設 A=1, 2, 3, 4，定義在 A 上的關系 R=<1,1>, <1,2>, <2,1>, <3,4> ,則關系R 具有性質（）A. 自反的B. 對稱的C. 傳遞的D. 以上均不對28.設 A=1, 2, 3，定義在 A 上的關系 R=<1

24、,1>,<2,1>,<1,3>，則 R 的對稱閉包是（）A. <1,1>,<2,1>,<2,2>,<1,3>,<3,1>,<3,3>B. <1,1>,<2,1>,<1,3>,<3,1>,<1,2>C. <1,1>,<1,2>,<2,1>,<1,3>,<3,1>,<2,2>,<3,3>D. 以上均不對學習資料學習資料收集于網絡，僅供參考29. 下列（）是

25、滿 2 元樹30. 下列給出的符號串集合（）不是前綴碼。A. 1,11,101,001,0011B.1,01,001,000C.0,10,110,1111D.b,c,dd,dc,aba,abb,abc二、判斷題1.設 R 是集合 A 上的關系，若 R1 , R2 是對稱的，則 R1R2 也是對稱的。（）2. 設 A=a，b，c，d，R 是 A 上的一個二元關系， R = < a,a >,< a,c >,< b,b >,<c,c >是自反的，是反對稱的，是傳遞的。（）3. 自然數集 N 上的關系“”（小于等于）是偏序關系，也是全序關系，同時也是良序

26、關系。（）4.設 R 是整數集 Z 上的一個關系，如果 R 是擬序，則 R 是反對稱的。（）5.在每個圖中，所有頂點的度數等于邊數的兩倍。（）6.樹是不包含回路的連通圖，在（ n，m）樹中必有 m=n+1（）。7. 公式 p? q 為重言式。（ ）8.如果推理正確，則結論一定正確。（）9.若明天有超強臺風，則明天放假。明天不放假，所以明天沒有超強臺風。(）10.在公式x(F(x, y)G(x, z) 中，x 為指導變元， F(x, y)G(x, z) 為 x 的轄域。（）11.公式 (xF(x)yG(y) yG(y)是可滿足式。 （）12.設 a、b 各不相同， a,b=a,b 。（）13.空

27、集是所有集合的子集。（）14. 設 R 為二元關系，則 R 既可能不是對稱的，也可能不是反對稱的。（ ）15.函數 f:N N,f(x)=(x)mod 3,x 除以 3 的余數 ,是滿射，不是單射（）16.設 T 是 n 階非平凡的無向樹，則 T 中至少有兩片樹葉。（）17. 如果函數 f:X Y 是滿射函數，而且是一對一函數， 那么 f:X Y 一定存在逆函數。（ ）學習資料學習資料收集于網絡，僅供參考18. 如果函數 f:X Y 是一一對應函數，那么f:X Y 一定存在逆函數。（）19. 設 R 是整數集 Z 上的一個關系， R = < x,y > |x - y 是偶數 ，則

28、R 是等價關系。（ ）20. 自然數集 N 上的關系“”（小于等于）是偏序關系，也是全序關系，同時也是良序關系。（ ）21. 自然數集 N 上的關系“ <”（小于）是偏序關系，也是全序關系，同時也是良序關系。（ ）22. 自然數集 N 上的關系“整除”是偏序關系，也是全序關系，同時也是良序關系。（ ）23.設 R 是整數集 Z 上的一個關系，如果 R 是擬序，則 R 是反對稱的。（）24.在每個圖中，所有頂點的度數等于邊數的兩倍。（）25.在任何有向圖中，所以頂點的入度之和等于所有頂點出度之和。（）三、填空題1.公式（ qp） p的主合取范式為。2.根據假言推理定律，（AB)A。3. 設

29、 M(x):x 是男生 , F(y):y 女生 , H(x,y):x 比 y力氣大，則命題“不是所有的男生都比所有的女生力氣大”符合號形式為。4.在一階邏輯中將命題符號化時，若沒有指明個體域，則使用。5.公式x(M(x) F(x) 的前束范式是。6.量詞轄域收縮與擴張等值式 x(A(x) B)。7.設 A=，1, a, b ， B=2, a, b ，則A B=。8. 無向圖 G有生成樹當且僅當 _。9. 對于 2叉有序正則樹， 訪問次序為： _的行遍法為中序行遍法。10.一個無向樹的頂點是 27，則它的邊數有個。11.公式q p的成真賦值是。12.（ AB) (BC）為假言三段論。13. 設 F(x): x是人， G(x): x喜歡共享單車，則“有人不喜歡共享單車”符號化形式為。14.在一階邏輯中將命題符號化時，若沒有指明個體域，則使用。15