復(fù)習(xí)要點(diǎn)及練習(xí)題市公開課特等獎(jiǎng)市賽課微課一等獎(jiǎng)?wù)n件

離散數(shù)學(xué)復(fù)習(xí)及練習(xí)題第1頁第1章集合1、集合表示及其運(yùn)算掌握集合表示法；掌握集合相關(guān)概念、相關(guān)運(yùn)算和相關(guān)性質(zhì)。重點(diǎn)掌握利用集合運(yùn)算相關(guān)性質(zhì)化簡(jiǎn)集合表示式。2、自然數(shù)和歸納法掌握兩種（第一、第二）數(shù)學(xué)歸納法特點(diǎn)；能夠熟練利用兩種歸納法進(jìn)行問題求解。3、笛卡爾乘積掌握笛卡爾乘積相關(guān)概念。第2頁第2章二元關(guān)系1、二元關(guān)系定義及相關(guān)概念2、二元關(guān)系3種表示方式：序偶集合；關(guān)系矩陣；關(guān)系圖3、3種特殊二元關(guān)系：相容關(guān)系；等價(jià)關(guān)系；序關(guān)系重點(diǎn)掌握等價(jià)關(guān)系4、關(guān)系4類運(yùn)算：求補(bǔ)運(yùn)算；求逆運(yùn)算；合成運(yùn)算；閉包運(yùn)算重點(diǎn)掌握關(guān)系閉包運(yùn)算。5、關(guān)系5個(gè)性質(zhì)：自反性；反自反性；對(duì)稱性；反對(duì)稱性；傳遞性第3頁第3章函數(shù)1、部分函數(shù)掌握函數(shù)及其相關(guān)定義：部分函數(shù)，全函數(shù)，定義域，值域。掌握滿射、內(nèi)射和雙射概念。2、基數(shù)

集合基數(shù)定義，無窮集合之間等勢(shì)定義，無窮基數(shù)分級(jí)，以及集合基數(shù)必定小于其冪集基數(shù)。重點(diǎn)掌握“抽屜原理”應(yīng)用。第4頁《集合論》填空題1、設(shè)A={1,2}，B={1,2,3,4,5},則B–A=(),A

B=()。2、設(shè)A={1,2,3,4}，A上二元關(guān)系R={<1,2>,<3,4>}，S={<2,4>,<3,1>}，則R-1oS-1=(),

S-1oR-1=(),domR=(),ranS=().

3.設(shè)A={a,b}，則P(A)×A=().4.設(shè)集合A={

,a}，則A冪集P(A)=().5.設(shè)A={x｜x∈N且2≤x≤12}，R為A上整除關(guān)系。若取S={2,4,9}，則對(duì)半序結(jié)構(gòu)〈A,R〉來說，S上界為(),下界為(),上確界為(),下確界為().S極大元為(),極小元為();最大元為(),最小元為().6.設(shè)A是由4個(gè)元素組成集合，則A上能夠定義()個(gè)不一樣二元關(guān)系；()個(gè)不一樣自反關(guān)系；()個(gè)不一樣反自反關(guān)系；()個(gè)不一樣對(duì)稱關(guān)系；()個(gè)不一樣反對(duì)稱關(guān)系。7.

設(shè)A={a,b,c},則A上能夠定義（）個(gè)不一樣等價(jià)關(guān)系。8.等價(jià)關(guān)系性質(zhì)為()。9.等價(jià)關(guān)系關(guān)系矩陣有哪些特點(diǎn)？（）

第5頁《集合論》選擇題1.空集冪集()基數(shù)為（）A.0B.1C.2.D.32.設(shè)R是非空集合A上二元關(guān)系，則R對(duì)稱閉包s(R)=().A.R∪IAB.R∪R-1C.R∪IAD.R∩

R-13.關(guān)系R傳遞閉包t(R)能夠由()來定義。

A.t(R)是包含R二元關(guān)系B.t(R)是包含R最小傳遞關(guān)系

C.t(R)是包含R一個(gè)傳遞關(guān)系D.任何包含R傳遞關(guān)系4.設(shè)集合A={{1},{2,3,4},{5}}，則下式為真是()A.1

AB.{2,3,4}

AC.{{5}}

AD.

A5.設(shè)

是一個(gè)空集，則以下之一哪一個(gè)不成立（）A.

B.

C.

+ D.

+第6頁《集合論》計(jì)算或證實(shí)題1.求{1,

,{1}}冪集：2.設(shè)A={a,b,c,d}RA×A,且R={<a,a>,<b,b>,<a,b>,<c,d>}求：（1）r(R)(2)s(R)(3)t(R)并畫出它們關(guān)系圖。3.設(shè)｜A｜=3,｜

(B)｜=16,｜

(A∪B)｜=64,試求｜B｜,｜A∩B｜,｜A-B｜,｜A

B｜.4.設(shè)A={x｜x為54因子}，RA×A,且對(duì)任意x,yA,xRyiffx整除y.

（1）畫出半序集<A,R>哈斯圖；（2）取A子集B={2,3,9},求出B最小元、極大元和上確界。5.任給52個(gè)整數(shù)，證實(shí)其中必定有兩數(shù)之差或者兩數(shù)之和能夠被100整除。第7頁第4章命題邏輯1、命題和邏輯詞掌握命題邏輯相關(guān)概念，熟悉邏輯聯(lián)接詞真值表。重點(diǎn)掌握命題符號(hào)化。

2、合式公式掌握合式公式定義方法，掌握永真式、永假式以及公式可滿足定義。重點(diǎn)掌握合式公式真值表結(jié)構(gòu)方法。

3、等價(jià)與蘊(yùn)含掌握等價(jià)、對(duì)偶式和蘊(yùn)含概念。重點(diǎn)掌握等價(jià)式、蘊(yùn)含式證實(shí)。掌握一些實(shí)際應(yīng)用問題推理。

4、范式和判定問題掌握命題公式極大項(xiàng)、極小項(xiàng)、主合?。ㄎ鋈。┓妒蕉x。重點(diǎn)掌握主范式求法。第8頁第5章謂詞邏輯

1.變?cè)⒅^詞和量詞掌握一階謂詞邏輯中新引入語法語義概念。重點(diǎn)是掌握將自然語言表示符號(hào)化。

2.合式公式掌握一階謂詞邏輯中合式公式歸納定義方法；掌握一階邏輯公式語義解釋方法；能夠區(qū)分變?cè)s束出現(xiàn)和自由出現(xiàn)。

3.永真式及其判定掌握一階謂詞邏輯代入定理、置換定理；掌握一些主要等價(jià)式和蘊(yùn)含式；重點(diǎn)掌握求公式前束范式方法。第9頁《數(shù)理邏輯》填空題1、給定以下命題：

P:天在下雪Q:我進(jìn)城R:我有時(shí)間使用邏輯聯(lián)接詞將以下復(fù)合命題符號(hào)化（1）假如天不下雪且我有時(shí)間，我就進(jìn)城；（2）我進(jìn)城必要條件是我有時(shí)間；（3）天不在下雪；（4）我進(jìn)城當(dāng)且僅當(dāng)我有時(shí)間且天不下雪；（5）天下雪，那么我不進(jìn)城。

2、合式公式┐Q∧(P→Q)與┐P關(guān)系是______。(等價(jià)、蘊(yùn)含)

3、合式公式(Q∨┐Q)→((P∧┐R)∧┐P)是永_______式。4、n個(gè)命題變?cè)缮桑ǎ﹤€(gè)不等價(jià)合式公式。

第10頁《數(shù)理邏輯》填空題（續(xù)）5.設(shè)論域?yàn)閧1,2}，命題(

x)(

y)(x+y=4)真值為（）。

6.若論域?yàn)榉秦?fù)整數(shù)集，A(x,y)表示x+y=y則(

x)(

y)A(x,y)真值為（）。

7.設(shè)論域D＝{4,5},那么謂詞公式(

x)P(x)∧(y)Q(y)消去量詞后等值式為（）。8.

(

x)F(x)→(y)G(x,y)前束范式為（）。

9.A,B為集合，命題A–B=

?A=B真值為（）。第11頁《數(shù)理邏輯》選擇題1、以下命題中，不是真命題是（）A.假如2*2=5,則雪是白。B.不存在最大質(zhì)數(shù)。C.若太陽從西邊落下，則9+5小于10。D.離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)系一門必修課。

2、以下式子中，（）是永真。

A.Q→(P∧Q)B.P→(P∧Q)C.(P∧Q)→PD.(P∧Q)→Q3.下面”P→Q”等價(jià)說法中，不正確為

()

A.P是Q充分條件B.Q是P必要條件C.Q僅當(dāng)PD.只有Q才P4.以下各式中，（）是析取范式。A.┐P∧QB.┐P∧(Q∨R)C.P∧(┐Q∨R)D.┐P∧(Q∨┐R)第12頁《數(shù)理邏輯》計(jì)算題和推理題1.一個(gè)命題公式A(P,Q,R)成真指派為FFF,FFT,FTF,TFF,TTF,求其主范式。

2.教材上習(xí)題4.4第1題b),d),3.教材上習(xí)題4.3第2題a)4.在謂詞邏輯中將以下命題符號(hào)化：

(1)有些大學(xué)生不是運(yùn)動(dòng)員；（2）會(huì)叫狗未必會(huì)咬人（3）對(duì)于每個(gè)實(shí)數(shù)都存在比它大有理數(shù)。5.求公式前束范式:教材上習(xí)題5.4第1題a)6.三人預(yù)計(jì)比賽結(jié)果，甲說“A第一，B第二”。乙說“C第二，D第四”.丙說“A第二，D第四”。結(jié)果三人預(yù)計(jì)得都不全對(duì)，但都對(duì)了一個(gè)，問A,B,C.D名次。第13頁首先要依據(jù)題設(shè)條件，把原題表示為一個(gè)合取范式，然后將合取范式化為主析取范式，每一個(gè)極小項(xiàng)就是一個(gè)可能結(jié)果。在主析取范式中，刪除不符題意極小項(xiàng)，其剩下即為所求可能結(jié)果。解：設(shè)P:A第一Q:B第二R:C第二S:D第四W:A第二由題意應(yīng)有:(P

Q)∧(R

S)∧(W

S)

T（

表示異或）

將左邊合式公式化為析取范式：

(P∧

Q∧R∧S∧W)∨(P∧

Q∧

R∧S∧

W)∨(P∧Q∧R∧

S∧W)∨(P∧Q∧

R∧S∧

W)因?yàn)镼、R、W矛盾故

P∧

Q∧R∧S∧W

F,P∧Q∧R∧

S∧W

F.

又因?yàn)镻∧

Q∧

R∧S∧

W表示A第一,B不是第二,C不是第二,D第四,A不是第二.由此可知A,B,C,D都不是第二，矛盾.所以原式

P∧Q∧

R∧S∧

W

T即A不是第一,B是第二,C不是第二,D第四,A不是第二由此可得：C第一B第二A第三D第四。第14頁第7章圖論1．基本概念：

(1)掌握有向圖、無向圖及其相關(guān)要素（節(jié)點(diǎn)、邊、出度、入度、度）數(shù)學(xué)定義及記號(hào);

(2)掌握完全圖、連通圖、補(bǔ)圖、子圖、同構(gòu)圖等基本概念；

(3)掌握和應(yīng)用握手定理；2．圖矩陣表示方法：

熟悉了解圖鄰接矩陣表示法3．樹與有向樹：

(1)掌握樹幾個(gè)等價(jià)定義；(2)熟悉了解完全二叉樹結(jié)構(gòu)和性質(zhì)；(3)掌握哈夫曼樹算法；(4)掌握用“避圈法”結(jié)構(gòu)加權(quán)圖最小生成樹。4．歐拉圖、哈米爾頓圖、二部圖與平面圖：

掌握上述各特殊圖定義、性質(zhì)和判斷方法第15頁《圖論》填空題1、設(shè)G是n個(gè)結(jié)點(diǎn)簡(jiǎn)單無向連通圖，那么其邊最少條數(shù)為（）;邊最多條數(shù)為（）。2、無向圖G是由k(k≥2)棵樹組成森林，最少要添加（）條邊才能使G成為一棵樹。3、設(shè)用G是由4棵樹組成一個(gè)樹林，G有15個(gè)結(jié)點(diǎn)，則G有()條邊。

4、一顆完全二叉樹高為4，則它最少有（）片樹葉，至多有()片樹葉。

5、設(shè)G是一棵二叉樹，G有10個(gè)點(diǎn)，其中6個(gè)葉點(diǎn)，則G總度數(shù)為（），分枝點(diǎn)數(shù)為().

6、給定一個(gè)圖G鄰結(jié)矩陣X，求vi至vj長(zhǎng)度為3路徑條數(shù)（）。7、無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每一個(gè)頂點(diǎn)度數(shù)為().

第16頁《圖論》選擇題

1、一個(gè)無向圖有4個(gè)結(jié)點(diǎn)，其中3個(gè)度數(shù)為2,3,3,則第4個(gè)結(jié)點(diǎn)度數(shù)不可能為（）。A.

0B.1C).2D.42、設(shè)無向圖中有8條邊，有兩個(gè)3度頂點(diǎn)和一個(gè)4度頂點(diǎn)，其余頂點(diǎn)度為2，則該圖頂點(diǎn)數(shù)是()。A．3 B．4C．5D．63、在有5個(gè)結(jié)點(diǎn)圖中,奇結(jié)點(diǎn)個(gè)數(shù)不可能為（）。(A)0(B)1(C)2(D)44、二部圖K2,3是（）。A.歐拉圖B.哈密頓圖C.非平面圖D.平面圖

5、以下命題正確是（）。

A.歐拉圖子圖一定是歐拉圖B.哈密頓圖子圖一定是哈密頓圖

C.平面圖子圖一定是平面圖D.樹子樹圖一定是樹

第17頁《圖論》計(jì)算或證實(shí)題三、計(jì)算或證實(shí)題1、給定權(quán)1,4,9,16,25,36,49,64,81,100,試結(jié)構(gòu)一棵最優(yōu)二叉樹，并求其葉加權(quán)長(zhǎng)度。2、用“避圈法”對(duì)教材P137圖7.3.8求出其一棵最小生成樹。3、證實(shí)：一棵多于一個(gè)頂點(diǎn)樹最少有兩片樹葉。4、畫出二部圖K3,4問該圖是平面圖嗎？為何？5、平時(shí)布置作業(yè)題（略）。第18頁教材上習(xí)題答案：可參看：

/p-17019984.html第19頁開復(fù)寄語：我學(xué)我成長(zhǎng)

（1）練內(nèi)功。不要只花功夫?qū)W習(xí)各種流行編程語言和工具，以及一些企業(yè)招聘廣告上要求科目。要把數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)據(jù)庫、操作系統(tǒng)原理、計(jì)算機(jī)體系結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)，離散數(shù)學(xué)等基礎(chǔ)課程學(xué)好。

（2）多實(shí)戰(zhàn)。經(jīng)過編程實(shí)戰(zhàn)積累經(jīng)驗(yàn)、鞏固知識(shí)。很多中國大學(xué)畢業(yè)生缺乏編程和調(diào)試經(jīng)驗(yàn)；學(xué)習(xí)C語言，考試過關(guān)就算學(xué)會(huì)了；課題項(xiàng)目中，只要程序能夠編譯，運(yùn)行，而且輸入輸出滿足要求就算了事。這些做法是不行。寫程序時(shí)候，大家必須多想想怎樣把程序?qū)懙糜泳珶挕⒏咝?、高質(zhì)量。提議大家爭(zhēng)取在大學(xué)四年中積累編寫十萬行代碼經(jīng)驗(yàn)。我們必須明白是：好程序員是寫出來，不是學(xué)出來。（3）求實(shí)干。不要輕視任何實(shí)際工作，比如一些看似簡(jiǎn)單編碼或測(cè)試。要不懈追求對(duì)細(xì)節(jié)一絲不茍實(shí)干作風(fēng)與敬業(yè)精神。我發(fā)覺不少程序員