第一篇：《李剛版離散數(shù)學(xué)》大一期末考試復(fù)習(xí)方向
《離散數(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í)指導(dǎo)
《離散數(shù)學(xué)》期末考試復(fù)習(xí)指導(dǎo)
期末考試僅限于期中考試以后的內(nèi)容：Chapter 7 Trees;Chapter 8 Topics in
graph theory.考試題型：計(jì)算題；簡(jiǎn)答題；證明題；構(gòu)造圖形（構(gòu)造滿足一定條件的圖，如：
6個(gè)頂點(diǎn)，11條邊且無(wú)Hamiltonian circuit）。題目共計(jì)6題，無(wú)選擇題和填空題。
考試難度：基本與期中考試相同，有一定數(shù)量的題直接來(lái)自于習(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í)中如遇困難請(qǐng)聯(lián)系：錢建國(guó)***，jgqian@jingxian.xmu.edu.cn徐偉***
陳美潤(rùn)***
祝大家取得好成績(jī)！
第三篇：離散數(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>，
A、{<1，b>，<1，c>，}
D、{
3、設(shè)集合H={1，2，3，4}，則H上的關(guān)系R={
。x +y是偶數(shù)}具有（）A、自反性、反對(duì)稱性和傳遞性
B、反自反性、反對(duì)稱性和傳遞性
C、反自反性、對(duì)稱性和傳遞性
D、自反性、對(duì)稱性和傳遞性
4、設(shè)T是一棵完全二叉樹(shù)，則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ù)減法，則下列說(shuō)法正確的是（）。A、 B、 C、 D、 9、設(shè)L是無(wú)向圖G中的一條通路，L中的頂點(diǎn)各不相同，則L是一條（）。A、簡(jiǎn)單通路 B、初級(jí)通路 C、簡(jiǎn)單回路 D、初級(jí)回路 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，1>，<2，b>}，則R逆關(guān)系R?1=_______________________________。 2、在代數(shù)系統(tǒng) 3、設(shè)集合M={1，2，3，5}，則M的冪集P（M）包含___________個(gè)元素。 4、設(shè)T是一棵有n(n?2)個(gè)頂點(diǎn)的樹(shù)，則T有_____________條邊。 5、設(shè) 6、設(shè) 7、設(shè)D是有向圖，若D的基圖是連通圖，則稱D是_________________圖 8、既不含________________也不含____________________的無(wú)向圖稱為簡(jiǎn)單圖。 三、計(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、用命題公式將下列命題符號(hào)化： 2和5是偶數(shù)，當(dāng)且僅當(dāng)5>2。 2、用謂詞公式將下列命題符號(hào)化： 每個(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.通過(guò)求主析取范式判斷下列命題公式是否等價(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>， 環(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í) 內(nèi)容：第一章~第七章 題型： 一、選擇題（20%，每題2分）二．填空題（20%，每題2分） 三、計(jì)算題（20%，每題5分） 四、證明題（20%，每題5分） 五、判斷題（20%，每題2分） 第1章 數(shù)學(xué)語(yǔ)言與證明方法 1.1 常用的數(shù)學(xué)符號(hào) 1.計(jì)算常用的數(shù)學(xué)符號(hào)式子 1.2 集合及其表示法 1.用列舉法和描述法表示集合 2.判斷元素與集合的關(guān)系(屬于和不屬于)3.判斷集合之間的包含與相等關(guān)系，空集(E)，全集(?)4.計(jì)算集合的冪集 5.求集合的運(yùn)算：并、交、相對(duì)補(bǔ)、對(duì)稱差、絕對(duì)補(bǔ) 6.用文氏圖表示集合的運(yùn)算 7.證明集合包含或相等 方法一： 根據(jù)定義, 通過(guò)邏輯等值演算證明 方法二： 利用已知集合等式或包含式, 通過(guò)集合演算證明 1.3 證明方法概述 1、用如下各式方法對(duì)命題進(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、判斷句子是否為命題、將命題符號(hào)化、求命題的真值（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í)際問(wèn)題 2.4 命題邏輯推理理論 1、用直接法、附加前提、歸謬法、歸結(jié)證明法等推理規(guī)則證明推理有效 第3章 一階邏輯 3.1 一階邏輯基本概念 1、用謂詞公式符號(hào)命題（正確使用量詞） 2、求謂詞公式的真值、判斷謂詞公式的類型 3.2 一階邏輯等值演算 1、證明謂詞公式的等值式 2、求謂詞公式的前束范式 第4章 關(guān)系 4.1 關(guān)系的定義及其表示 1、計(jì)算有序?qū)Α⒌芽▋悍e 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)系是否為自反、反自反、對(duì)稱、反對(duì)稱、傳遞的2、判斷關(guān)系運(yùn)算與性質(zhì)的關(guān)系 3、計(jì)算關(guān)系自反閉包、對(duì)稱閉包和傳遞閉包 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.指出無(wú)向圖的階數(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)成無(wú)向圖 6.判斷圖是否為簡(jiǎn)單圖、完全圖、正則圖、圈圖、輪圖、方體圖 7.求給定圖的補(bǔ)圖、生成子圖、導(dǎo)出子圖 8.判斷兩個(gè)圖是否同構(gòu) 6.2 圖的連通性 1.求圖中給定頂點(diǎn)通路、回路的距離 2.計(jì)算無(wú)向圖的連通度、點(diǎn)割集、割點(diǎn)、邊割集、割邊 3.判斷有向圖的類型：強(qiáng)連通圖、單向連通圖、弱連通圖 6.3 圖的矩陣表示 1.計(jì)算無(wú)向圖的關(guān)聯(lián)矩陣 2.計(jì)算有向無(wú)環(huán)圖的關(guān)聯(lián)矩陣 3.計(jì)算有向圖的鄰接矩陣 4.計(jì)算有向圖的可達(dá)矩陣 5.計(jì)算圖的給定長(zhǎng)度的通路數(shù)、回路數(shù) 6.4 幾種特殊的圖 1、判斷無(wú)向圖是否為二部圖、歐拉圖、哈密頓圖 第7章 樹(shù)及其應(yīng)用 7.1 無(wú)向樹(shù) 1.判斷一個(gè)無(wú)向圖是否為樹(shù) 2.計(jì)算無(wú)向樹(shù)的樹(shù)葉、樹(shù)枝、頂點(diǎn)數(shù)、頂點(diǎn)度數(shù)之間的關(guān)系 3.給定無(wú)向樹(shù)的度數(shù)列，畫出非同構(gòu)的無(wú)向樹(shù) 4.求生成樹(shù)對(duì)應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng) 5.求最小生成樹(shù) 7.2 根樹(shù)及其應(yīng)用 1.判斷一個(gè)有向圖是否為根樹(shù) 2.求根樹(shù)的樹(shù)根、樹(shù)葉、內(nèi)點(diǎn)、樹(shù)高 3.求最優(yōu)樹(shù) 4.判斷一個(gè)符號(hào)串集合是否為前綴碼 5.求最佳前綴碼 6.用三種方法遍歷根樹(shù) 離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)： 1、集合的運(yùn)算以及運(yùn)算律； 2、關(guān)系的三種表示方法，以及他們之間的轉(zhuǎn)化； 3、常見(jiàn)關(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、各種圖和樹(shù)的概念及相關(guān)的結(jié)論，比如：歐拉圖的充要條件，哈密頓圖的充分條件、必 要條件、充要條件等； 9、圖的矩陣計(jì)算； 10、會(huì)畫一些簡(jiǎn)單的樹(shù)； 11、五種聯(lián)結(jié)詞的真值表； 12、一些要求記住的命題公式； 13、命題公式的證明； 14、命題公式的析取范式，合取范式，主析取范式和主合取范式的求法。 題型：填空題、證明題和解答題。 友情提醒： 1、周三下午一點(diǎn)半到三點(diǎn)半在逸夫樓519答疑。 2、概念、定理和公式請(qǐng)務(wù)必記住，可能會(huì)出填空題； 3、考試內(nèi)容不會(huì)超出我們的重點(diǎn)； 請(qǐng)大家好好復(fù)習(xí)，爭(zhēng)取一次性通過(guò)。（Q是有理數(shù)集，“+”是有理數(shù)加法）中，單位元是______，2的逆元是___________。
的_______________。中有單位元，則稱第四篇：《離散數(shù)學(xué)》期末復(fù)習(xí)
第五篇：離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)
點(diǎn)擊咨詢 