第一篇:《李剛版離散數(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>,},G={,,<1,2>}則 F?G=()。
A、{<1,b>,<1,c>,}
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>,} 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í) 內(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ò)。是一個(gè)代數(shù)系統(tǒng),若多任意的x,y?S,都有x?y=y?x,則稱運(yùn)算?在S上滿足()。(Q是有理數(shù)集,“+”是有理數(shù)加法)中,單位元是______,2的逆元是___________。
是一個(gè)代數(shù)系統(tǒng),?是S上的二元運(yùn)算,若存在??S,對(duì)任意x?S,有??x=x??=?,則稱?是的_______________。是一個(gè)代數(shù)系統(tǒng),若?滿足結(jié)合律且中有單位元,則稱為一個(gè)___________________。第四篇:《離散數(shù)學(xué)》期末復(fù)習(xí)
第五篇:離散數(shù)學(xué)復(fù)習(xí)重點(diǎn)