第一篇：《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)
《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)
期末考試僅限于期中考試以后的內(nèi)容：Chapter 7 Trees;Chapter 8 Topics in
graph theory.考試題型：計(jì)算題；簡答題；證明題；構(gòu)造圖形（構(gòu)造滿足一定條件的圖，如：
6個(gè)頂點(diǎn)，11條邊且無Hamiltonian circuit）。題目共計(jì)6題，無選擇題和填空題。
考試難度：基本與期中考試相同，有一定數(shù)量的題直接來自于習(xí)題，最后一題較
難（構(gòu)造圖形）。
復(fù)習(xí)要點(diǎn)：基本概念及定義：
rooted tree;binary tree;labeled tree;positional tree;tree
searching;undirected tree;weighted graph;minimal spanning tree;(undirected)graph;degree;Euler path and Euler circuit;Hamiltonian path and Hamiltonian circuit;matching function;coloring graph;chromatic number;chromatic polynomial;planar graph;
基本內(nèi)容：
tree searching;the prefix(Polish form)and infix form of the
algebraic expression;minimal spanning tree;the sufficient-necessary condition for a graph G to have Euler circuit(or path);coloring graph;chromatic number;chromatic polynomial;construct a graph(directed or undirected)subject to some given conditions.不要求的內(nèi)容：
Computer representation of binary positional tree;searching general tree;algorithms.復(fù)習(xí)中如遇困難請聯(lián)系：錢建國***，jgqian@jingxian.xmu.edu.cn徐偉***
陳美潤***
祝大家取得好成績！
第二篇：離散數(shù)學(xué)期末考試
一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）
1、設(shè)集合M={a，?}，N ={{a}，?}則M?N=（）。A、? B、{?} C、{a} D、{{a}，?，a}
2、設(shè)關(guān)系F={<1，a >，<2，2>，}，G={
A、{<1，b>，<1，c>，}
3、設(shè)集合H={1，2，3，4}，則H上的關(guān)系R={
。x +y是偶數(shù)}具有（）A、自反性、反對稱性和傳遞性
B、反自反性、反對稱性和傳遞性
C、反自反性、對稱性和傳遞性
D、自反性、對稱性和傳遞性
4、設(shè)T是一棵完全二叉樹，則T的每個(gè)結(jié)點(diǎn)都（）。
A、至少有兩個(gè)子結(jié)點(diǎn)
B、至多有兩個(gè)子結(jié)點(diǎn)
C、恰有兩個(gè)子結(jié)點(diǎn)
D、可以有任意多個(gè)子結(jié)點(diǎn)
5、設(shè)R是實(shí)數(shù)集，“+，—，A、 ?>是群 B、 ? >是半群 D、 6、下面關(guān)系中，函數(shù)關(guān)系是（）。 A、{ B、{ D、{ 7、設(shè) A、結(jié)合律 B、交換律 C、分配律 D、冪等律 8、設(shè)Z是整數(shù)集，“—”是整數(shù)減法，則下列說法正確的是（）。A、 B、 C、 D、 9、設(shè)L是無向圖G中的一條通路，L中的頂點(diǎn)各不相同，則L是一條（）。A、簡單通路 B、初級通路 C、簡單回路 D、初級回路 10、設(shè)G有6個(gè)3度點(diǎn)，2個(gè)4度點(diǎn)，其余頂點(diǎn)的度數(shù)均為0，則G的邊數(shù)是（）。A、10 B、13 C、11 D、6 二、填空題(本大題共8題，共10個(gè)空，每空2分，共20分) 1、設(shè)關(guān)系R={ 2、在代數(shù)系統(tǒng) 3、設(shè)集合M={1，2，3，5}，則M的冪集P（M）包含___________個(gè)元素。 4、設(shè)T是一棵有n(n?2)個(gè)頂點(diǎn)的樹，則T有_____________條邊。 5、設(shè) 6、設(shè) 7、設(shè)D是有向圖，若D的基圖是連通圖，則稱D是_________________圖 8、既不含________________也不含____________________的無向圖稱為簡單圖。 三、計(jì)算題(本大題共3小題，每小題10分，共30分) 1、用等值演算法求公式A=(p??q)?(p?r)的主析取范式。 2、求公式?x(Q(x)?G(x，s))?(?yP(y)??zH(y，z))的前束范式。 3、設(shè)集合A={1，2，3，4，5}，關(guān)系R={ R； （3）求偏序集的極大元、極小元和最小元。 四、應(yīng)用題(本大題共2小題，每小題5分，共10分) 1、用命題公式將下列命題符號化： 2和5是偶數(shù)，當(dāng)且僅當(dāng)5>2。 2、用謂詞公式將下列命題符號化： 每個(gè)計(jì)算機(jī)專業(yè)的學(xué)生都要學(xué)《編譯原理》，但有些計(jì)算機(jī)專業(yè)的學(xué)生不學(xué)《經(jīng)濟(jì)學(xué)》。 五、證明題（本大題共2小題，每小題10分，共20分） 1、在命題邏輯系統(tǒng)中用歸結(jié)法證明下列推理是有效的： 前提：?s?q，p??q，s 結(jié)論：?p 2、在謂詞邏輯系統(tǒng)中寫出下列推理的（形式）證明： 前提：?x(M(x)?P(x))，?x(M(x)?G(x))，?x(?G(x))結(jié)論：?xP(x) 計(jì)算題 6.設(shè)命題公式G = ?(P→Q)∨(Q∧(?P→R)), 求G的主析取范式。 7.(9分)設(shè)一階邏輯公式：G =(?xP(x)∨?yQ(y))→?xR(x)，把G化成前束范式.9.設(shè)R是集合A = {a, b, c, d}.R是A上的二元關(guān)系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)畫出r(R), s(R), t(R)的關(guān)系圖.11.通過求主析取范式判斷下列命題公式是否等價(jià)： (1)G =(P∧Q)∨(?P∧Q∧R) (2)H =(P∨(Q∧R))∧(Q∨(?P∧R))13.設(shè)R和S是集合A＝{a, b, c, d}上的關(guān)系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝ {(a, b),(b, c),(b, d),(d, d)}.(1)試寫出R和S的關(guān)系矩陣；(2)計(jì)算R?S, R∪S, R1, S1?R1.－ － －證明題 1.利用形式演繹法證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S。2.設(shè)A,B為任意集合，證明：(A-B)-C = A-(B∪C).3.(本題10分)利用形式演繹法證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D。4.(本題10分)A, B為兩個(gè)任意集合，求證： A－(A∩B)=(A∪B)－B.答案： 1-5 BADBB 6-10 BBABB 1.{<1，a>，<1，2>，} 2.0，-2 3.16 4.n-1 5.零元 6.半群 7.弱連通 8.平行邊 環(huán) 三． ??(p??q)?(p?r)?(?p?q)?(p?r)1.?(?p?q?r)?(?p?q??r)?(p?q?r)?(p??q?r)?m011?m010?m111?m1012.??x(Q(x)?G(x,s))??y?z(P(y)?H(y,z)) ??y?z?x((Q(x)?G(x,s))?(P(y)?H(y,z))3.(1)R?{?1,1?,?2,2?,?3,3?,?4,4?,?5,5?,?1,2?,?1,3?,?1,4?,?1,5?,?2,4?} ??1??2(2)MR???3?4???512345?11111??01010?? （3）最小元=1 極小元=1 極大元=5 00100?00010??00001??四 1.令p表示2是偶數(shù)；令q表示5是偶數(shù)；r表示5>2； (p?q)?r 2.S（x）：x是計(jì)算機(jī)專業(yè)的學(xué)生；G（x）：x要學(xué)《編譯原理》； F（x）：x學(xué)經(jīng)濟(jì)學(xué)； ?x(S(x)?G(x))??x(S(x)??F(x)) 五 1，（1） s 前提引入（2） ?s?q 前提引入（3） q??s 置換規(guī)則 （4） q 1,3析取三段論（5） p??q 前提引入（6） ?p 4,5拒取 （1） ?x(M(x)?G(x)) 前提引入（2） M（x）v G（x） EI規(guī)則（3） ?x(?G(x)) 前提引入（4） ?G(x)（5） M(x) AI規(guī)則 2,4析取三段論 （6） ?x(M(x)?P(x)) 前提引入（7） M(x)→P（x） AI規(guī)則（8） P（x） 5,7假言推理（9） ?xP(x) EG規(guī)則 6.G = ?(P→Q)∨(Q∧(?P→R)) = ?(?P∨Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧(P∨R))=(P∧?Q)∨(Q∧P)∨(Q∧R)=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)=(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧Q∧?R)∨(?P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = ?(3, 4, 5, 6, 7).7.G =(?xP(x)∨?yQ(y))→?xR(x) = ?(?xP(x)∨?yQ(y))∨?xR(x)=(??xP(x)∧??yQ(y))∨?xR(x)=(?x?P(x)∧?y?Q(y))∨?zR(z)= ?x?y?z((?P(x)∧?Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2) 關(guān)系圖: abr(R)dcabs(R)dabt(R)dc c 11.G＝(P∧Q)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)＝m6∨m7∨m3 ＝?(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(?P∧R))＝(P∧Q)∨(Q∧R))∨(?P∧Q∧R)＝(P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R)∨(P∧Q∧R)∨(?P∧Q∧R)＝(P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝?(3, 6, 7)G,H的主析取范式相同，所以G = H.?1?013.(1)MR???0??0000011000??0?00?? MS??1??0??0??0100001000?1?? 0??1?(2)R?S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1?R1＝{(b, a),(d, c)}.－－四 證明題 1.證明：{P→Q, R→S, P∨R}蘊(yùn)涵Q∨S (1)P∨R (2)?R→P(3)P→Q(4)?R→Q(5)?Q→R(6)R→S P Q(1)P Q(2)(3)Q(4)P (7)?Q→S(8)Q∨S Q(5)(6)Q(7)2.證明：(A-B)-C =(A∩~B)∩~C 3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)證明：{?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D(1)A D(附加)P(2)?A∨B(3)B Q(1)(2)P Q(4)(4)?C→?B(5)B→C(6)C Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D 所以 {?A∨B, ?C→?B, C→D}蘊(yùn)涵A→D.1.證明：A－(A∩B) = A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝?∪(A∩~B)＝(A∩~B)＝A－B 而(A∪B)－B =(A∪B)∩~B =(A∩~B)∪(B∩~B)=(A∩~B)∪? = A－B 所以：A－(A∩B)=(A∪B)－B. 《離散數(shù)學(xué)大一期末考試復(fù)習(xí)方向》 一、命題邏輯 證明等值式 ①等值演算 判斷公式的類型 合?。ㄎ鋈。┓妒?/p> ②范式 主合?。ㄖ魑鋈。┓妒?/p> 重點(diǎn)復(fù)習(xí)題目：課本P55的2.5.3和2.5.2 ③推理證明 P63 的2.6.2 二、謂詞邏輯 ①前述范式。P88的3.35 ②推理論證P91的蘇格拉底、P93的3.4.1（4） 三、關(guān)系 P152的5.4.3。 四、等價(jià)轉(zhuǎn)換。P157的.5.5.4 離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)： 1、集合的運(yùn)算以及運(yùn)算律； 2、關(guān)系的三種表示方法，以及他們之間的轉(zhuǎn)化； 3、常見關(guān)系的定義； 4、哈斯圖的畫法，以及最大最小元、極大極小元、上下界，上下確界的求法； 5、單射、滿射以及雙射的證明（尤其是在代數(shù)系統(tǒng)中）； 6、代數(shù)系統(tǒng)的概念以及代數(shù)系統(tǒng)的常用性質(zhì)，能夠證明具體的代數(shù)系統(tǒng)的運(yùn)算律，找出單 位元，零元、以及逆元等； 7、環(huán)和格只要記住不同的環(huán)和格滿足的運(yùn)算律就好； 8、各種圖和樹的概念及相關(guān)的結(jié)論，比如：歐拉圖的充要條件，哈密頓圖的充分條件、必 要條件、充要條件等； 9、圖的矩陣計(jì)算； 10、會(huì)畫一些簡單的樹； 11、五種聯(lián)結(jié)詞的真值表； 12、一些要求記住的命題公式； 13、命題公式的證明； 14、命題公式的析取范式，合取范式，主析取范式和主合取范式的求法。 題型：填空題、證明題和解答題。 友情提醒： 1、周三下午一點(diǎn)半到三點(diǎn)半在逸夫樓519答疑。 2、概念、定理和公式請務(wù)必記住，可能會(huì)出填空題； 3、考試內(nèi)容不會(huì)超出我們的重點(diǎn)； 請大家好好復(fù)習(xí)，爭取一次性通過。 《離散數(shù)學(xué)》期末復(fù)習(xí) 內(nèi)容：第一章~第七章 題型： 一、選擇題（20%，每題2分）二．填空題（20%，每題2分） 三、計(jì)算題（20%，每題5分） 四、證明題（20%，每題5分） 五、判斷題（20%，每題2分） 第1章 數(shù)學(xué)語言與證明方法 1.1 常用的數(shù)學(xué)符號 1.計(jì)算常用的數(shù)學(xué)符號式子 1.2 集合及其表示法 1.用列舉法和描述法表示集合 2.判斷元素與集合的關(guān)系(屬于和不屬于)3.判斷集合之間的包含與相等關(guān)系，空集(E)，全集(?)4.計(jì)算集合的冪集 5.求集合的運(yùn)算：并、交、相對補(bǔ)、對稱差、絕對補(bǔ) 6.用文氏圖表示集合的運(yùn)算 7.證明集合包含或相等 方法一： 根據(jù)定義, 通過邏輯等值演算證明 方法二： 利用已知集合等式或包含式, 通過集合演算證明 1.3 證明方法概述 1、用如下各式方法對命題進(jìn)行證明。? 直接證明法：A?B為真 ? 間接證明法：“A?B為真” ? “ ?B? ?A為真” ? 歸謬法(反證法)： A??B?0為真 ? 窮舉法： A1?B, A2?B,…, Ak?B 均為真 ? 構(gòu)造證明法：在A為真的條件下, 構(gòu)造出具有這種性質(zhì)的客體B ? 空證明法：“A恒為假” ? “A?B為真” ?平凡證明法：“B恒為真” ? “A?B為真” ? 數(shù)學(xué)歸納法： 第2章 命題邏輯 2.1 命題邏輯基本概念 1、判斷句子是否為命題、將命題符號化、求命題的真值（0或1）。 命題的定義和聯(lián)結(jié)詞(?, ?, ?, ?, ?) 2、判斷命題公式的類型 賦值或解釋.成真賦值,成假賦值；重言式(永真式)、矛盾式(永假式)、可滿足式:。2.2 命題邏輯等值演算 1、用真值表判斷兩個(gè)命題公式是否等值 2、用等值演算證明兩個(gè)命題公式是否等值 3、證明聯(lián)結(jié)詞集合是否為聯(lián)結(jié)詞完備集 2.3 范式 1、求命題公式的析取范式與合取范式 2、求命題公式的主析取范式與主合取范式（兩種主范式的轉(zhuǎn)換） 3、應(yīng)用主析取范式分析和解決實(shí)際問題 2.4 命題邏輯推理理論 1、用直接法、附加前提、歸謬法、歸結(jié)證明法等推理規(guī)則證明推理有效 第3章 一階邏輯 3.1 一階邏輯基本概念 1、用謂詞公式符號命題（正確使用量詞） 2、求謂詞公式的真值、判斷謂詞公式的類型 3.2 一階邏輯等值演算 1、證明謂詞公式的等值式 2、求謂詞公式的前束范式 第4章 關(guān)系 4.1 關(guān)系的定義及其表示 1、計(jì)算有序?qū)?、笛卡兒積 2、計(jì)算給定關(guān)系的集合 3、用關(guān)系圖和關(guān)系矩陣表示關(guān)系 4.2 關(guān)系的運(yùn)算 1、計(jì)算關(guān)系的定義域、關(guān)系的值域 2、計(jì)算關(guān)系的逆關(guān)系、復(fù)合關(guān)系和冪關(guān)系 3、證明關(guān)系運(yùn)算滿足的式子 4.3 關(guān)系的性質(zhì) 1、判斷關(guān)系是否為自反、反自反、對稱、反對稱、傳遞的2、判斷關(guān)系運(yùn)算與性質(zhì)的關(guān)系 3、計(jì)算關(guān)系自反閉包、對稱閉包和傳遞閉包 4.4 等價(jià)關(guān)系與偏序關(guān)系 1、判斷關(guān)系是否為等價(jià)關(guān)系 2、計(jì)算等價(jià)關(guān)系的等價(jià)類和商集 3、計(jì)算集合的劃分 4、判斷關(guān)系是否為偏序關(guān)系 5、畫出偏序集的哈期圖 6、求偏序集的最大元、最小元、極小元、極大元、上界、下界、上確界、下確界 7、求偏序集的拓?fù)渑判?第5章 函數(shù) 1.判斷關(guān)系是否為函數(shù) 2.求函數(shù)的像和完全原像 3.判斷函數(shù)是否為滿射、單射、雙射 4.構(gòu)建集合之間的雙射函數(shù) 5.求復(fù)合函數(shù) 6.判斷函數(shù)的滿射、單射、雙射的性質(zhì)與函數(shù)復(fù)合運(yùn)算之間的關(guān)系 7.判斷函數(shù)的反函數(shù)是否存在，若存在求反函數(shù) 第6章 圖 1.指出無向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的度數(shù)、最大度、最小度 2.指出有向圖的階數(shù)、邊數(shù)、各頂點(diǎn)的出度和入度、最大出度、最大入度、最小出度最小入出度 3.根據(jù)握手定理頂點(diǎn)數(shù)、邊數(shù)等 4.指出圖的平行邊、環(huán)、弧立點(diǎn)、懸掛頂點(diǎn)和懸掛邊 5.判斷給定的度數(shù)列能否構(gòu)成無向圖 6.判斷圖是否為簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補(bǔ)圖、生成子圖、導(dǎo)出子圖 8.判斷兩個(gè)圖是否同構(gòu) 6.2 圖的連通性 1.求圖中給定頂點(diǎn)通路、回路的距離 2.計(jì)算無向圖的連通度、點(diǎn)割集、割點(diǎn)、邊割集、割邊 3.判斷有向圖的類型：強(qiáng)連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示 1.計(jì)算無向圖的關(guān)聯(lián)矩陣 2.計(jì)算有向無環(huán)圖的關(guān)聯(lián)矩陣 3.計(jì)算有向圖的鄰接矩陣 4.計(jì)算有向圖的可達(dá)矩陣 5.計(jì)算圖的給定長度的通路數(shù)、回路數(shù) 6.4 幾種特殊的圖 1、判斷無向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹及其應(yīng)用 7.1 無向樹 1.判斷一個(gè)無向圖是否為樹 2.計(jì)算無向樹的樹葉、樹枝、頂點(diǎn)數(shù)、頂點(diǎn)度數(shù)之間的關(guān)系 3.給定無向樹的度數(shù)列，畫出非同構(gòu)的無向樹 4.求生成樹對應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng) 5.求最小生成樹 7.2 根樹及其應(yīng)用 1.判斷一個(gè)有向圖是否為根樹 2.求根樹的樹根、樹葉、內(nèi)點(diǎn)、樹高 3.求最優(yōu)樹 4.判斷一個(gè)符號串集合是否為前綴碼 5.求最佳前綴碼 6.用三種方法遍歷根樹是一個(gè)代數(shù)系統(tǒng)，若多任意的x，y?S，都有x?y=y?x，則稱運(yùn)算?在S上滿足（）。是一個(gè)代數(shù)系統(tǒng)，若?滿足結(jié)合律且中有單位元，則稱第三篇：《李剛版離散數(shù)學(xué)》大一期末考試復(fù)習(xí)方向
第四篇：離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)
第五篇：《離散數(shù)學(xué)》期末復(fù)習(xí)
點(diǎn)擊咨詢 