離散數(shù)學(xué)--期末復(fù)習(xí)

1、離散數(shù)學(xué)知識(shí)要點(diǎn)總結(jié)第1章 命題邏輯1、會(huì)判斷一個(gè)語(yǔ)句是否為命題（如P31-習(xí)題1.1題）練習(xí)：判斷下列語(yǔ)句是否為命題。 7 / 7(1).3+8=13；(2).離散數(shù)學(xué)是計(jì)算機(jī)系的一門必修課；(3).太陽(yáng)系以外的星球上有生物；(4).你打算考碩士研究生嗎？ (5).9+512 ； (6). 天上有三個(gè)月亮。(7).x+5 6；(8).一定要努力學(xué)習(xí)！ (9).2是素?cái)?shù)； (10).x+5 6； (11).我正在說(shuō)謊；(12).x=13.(13).這朵花多好看呀！ (14).7能被2整除. (15).我用的計(jì)算機(jī)CPU主頻是1G嗎？(16).藍(lán)色和黃色可以調(diào)成綠色；(17). 雪是黑色的. (

2、18). 明天會(huì)下雨嗎？；(19).我能進(jìn)來(lái)嗎？ (20).這個(gè)男孩真勇敢呀！(21).藍(lán)色和黃色可以調(diào)成綠色；(22).x3；(23)地球饒著太陽(yáng)轉(zhuǎn). (24)青年人多么朝氣蓬發(fā)呀！(25).5能被2整除. (26).嫦娥一號(hào)太棒了！ (27).臺(tái)灣是中國(guó)的一部分； (29) 你下午有會(huì)嗎？若無(wú)會(huì)，請(qǐng)到我這兒來(lái)！ (30).請(qǐng)不要講話！ (31) 5是奇數(shù)；(32).2、注意五個(gè)命題聯(lián)結(jié)詞的使用，會(huì)將命題進(jìn)行符號(hào)化（如P32-1.3，1.4，1.5題的題型）或在判斷體現(xiàn)邏輯聯(lián)結(jié)詞的邏輯有關(guān)系等。練習(xí)：將以下命題符號(hào)化(1)如果你不去逛街，那么我也不去逛街。(2)小李邊吃飯邊看電視。(3)林芳

3、學(xué)過(guò)英語(yǔ)或日語(yǔ)。(4)張輝與王麗都是三好生.(5)小王住在101室或102室。(6).2+24當(dāng)且僅當(dāng)王紅沒(méi)努力學(xué)習(xí)離散數(shù)學(xué)。(7)4或6是素?cái)?shù).(8).王曉聰明，但是他不用功.(9)如果今天是1號(hào)，則明天是5號(hào)。(10).小潘不能既跳舞又唱歌。(11)如果你來(lái)了，他就唱歌而且陪你跳舞。(12).或者雪是黑色的，或者太陽(yáng)從東方升起。(13).王曉既用功又聰明。 (14)2 + 2 4 當(dāng)且僅當(dāng)美國(guó)位于非洲。(15)小李學(xué)過(guò)英語(yǔ)或法語(yǔ)。 (16）如果石頭會(huì)說(shuō)話，那么月亮上就會(huì)出現(xiàn)海洋。(17）.如果天氣寒冷，小梅就不去游泳 。（18）小紅喜歡看書和畫畫。p qp qpqpq0 000110 10

4、1101 001001 111113、會(huì)求命題公式的真值表，當(dāng)一個(gè)命題公式中的命題變項(xiàng)被指定具體某組真值時(shí)，能求整個(gè)公式的真值。 練習(xí)：請(qǐng)回答下列問(wèn)題。（1）設(shè)p，q 的真值為0，r，s的真值為1，則公式的真值是？ （2）設(shè)p，q的真值為1，r，s的真值為0，則公式的真值是？ （3）設(shè)p，q 的真值為0，r，s的真值為1,則公式的真值是？ （4）設(shè)p，q 的真值為0，r，s的真值為1,則公式的真值是？ （5）設(shè)p，q 的真值為0，r，s的真值為1,則公式的真值是？在畫真值表時(shí)注意的知識(shí)點(diǎn)：一個(gè)命題公式中含有n個(gè)原子命題，則對(duì)其所有可能賦值有 2n 種。4、會(huì)判斷一個(gè)命題公式的類型（包括：重言式

5、（永真式），矛盾式（永假式），可滿足式）,(如P33-1.7，1.9題，方法可以用真值表，也可以用等值演算，但是如果指定方法，必須按指定方法做。)練習(xí)：判斷下列公式的類型（1）；（2）；（3）； (4)（5）； （6）；（7）(8)（9）；（10）；（11）；(12)（13）（14）；（15）；（16 5、掌握基本等值式，并會(huì)運(yùn)用基本等值式，會(huì)證明等值式，會(huì)判斷公式的類型：方法一，真值表法，方法二，等值演算法。（如P34-1.8，1.9題題型）練習(xí)：證明下列等值式。（1） （2）（3） （4）6、關(guān)于主析取范式與主合取范式的求法及應(yīng)用。（例1.14,習(xí)題1.12題型。）要求：會(huì)判斷什么是極小項(xiàng)

6、與極大項(xiàng)，并會(huì)求主析取范式與主合取范式，可以通知所求式子判斷成真賦值與成假賦值，及判斷命題公式類型。（1）、（2）、(p(qr)(pqr)（3）、（4）、（5）、（6）、(pq) (pr) （7）、(qp)r （8）、 7、命題邏輯推理掌握基本理論，基本推理定律規(guī)則。見課本與課堂的練習(xí)題（1）如果教練教得好而且我努力練習(xí)，那么我就一定能學(xué)好輪滑。我努力練習(xí)了，但我還是沒(méi)有學(xué)好輪滑。所以是教練教得不好。（2）如果今天我沒(méi)有課，則我去機(jī)房上機(jī)或去圖書館查資料。若機(jī)房沒(méi)有空機(jī)器，則我沒(méi)法去上機(jī)。今天我沒(méi)課，機(jī)房也沒(méi)有空機(jī)器。所以我去圖書館查資料。（3）或者C+程序設(shè)計(jì)難學(xué)，或者學(xué)生喜歡C+程序設(shè)計(jì)。

7、如果編程語(yǔ)言容易學(xué)，那么C+程序設(shè)計(jì)并不難學(xué)。因此，如果學(xué)生不喜歡C+程序設(shè)計(jì)，那么編程語(yǔ)言并不容易學(xué)。（4）今天或者天晴或者下雨。如果天晴，我去看電影。若我去看電影，我就不看書。我今天在看書。所以今天下雨。 （5）若星期天不下雪且能買到票，我就去體育館看球。我買到票了，但是我沒(méi)有去體育館看球。所以星期天下雪了。（6）若小張喜歡數(shù)學(xué)，則小李或小趙也喜歡數(shù)學(xué)。若小李喜歡數(shù)學(xué)，則他也喜歡物理。小張確實(shí)喜歡數(shù)學(xué)，可小李不喜歡物理。所以小趙喜歡數(shù)學(xué)。 (7)如果今天是星期五，那么我會(huì)有離散數(shù)學(xué)或數(shù)字邏輯考試。如果離散數(shù)學(xué)老師有事，那么沒(méi)有離散數(shù)學(xué)考試。今天是星期五且離散數(shù)學(xué)老師有事。所以我有一次數(shù)字邏

8、輯考試。（8）若明天是星期一或星期三，我就有課. 若有課，今天必備課. 我今天下午沒(méi)備課. 所以，明天不是星期一和星期三. 8、一些綜合知識(shí)的認(rèn)知。練習(xí)：判斷下列語(yǔ)句是否正確。（1）、矛盾式一定不是可滿足式，可滿足式也一定不是矛盾式。 （2）、的邏輯關(guān)系是：是的充分必要條件。（3）、若A至少存在一種賦值是成假賦值，則稱A為矛盾式。（4）、若A至少存在一種賦值是成真賦值，則稱A為重言式。 （5）、一般地說(shuō)，排斥或不能用的方式表示.（6）、的邏輯關(guān)系是：是的必要條件。（7）在命題邏輯中，任何命題公式的主合取范式都是存在的，并且是唯一的.（8）、矛盾式一定不是可滿足式，但可滿足式可能是矛盾式。 （9

9、）、含有聯(lián)結(jié)詞“和”的命題一定是復(fù)合命題。（10）五個(gè)基本聯(lián)結(jié)詞的運(yùn)算順序是：，。第2章 一階邏輯1、一階邏輯中的命題符號(hào)化問(wèn)題（要求：注意區(qū)分全稱量詞與存在量詞的提取，注意命題的個(gè)體域（若題目沒(méi)有特別指明時(shí)，均指全總個(gè)體域），如何引入特性謂詞。例2.22.5，P52習(xí)題2.1，2.3）在引入特性量詞后，使用全稱量詞與存在量詞符號(hào)化的形式是不同的，則有全稱量詞時(shí)，“所有的是”應(yīng)表示為：x(A(x)B(x)，存在量詞時(shí)，“存在是”應(yīng)表示為：$x(A(x)B(x)。練習(xí)：（1）沒(méi)有不愛看電影的人。（2）并非所有的人都喜歡吃辣椒。（3）素?cái)?shù)不全是奇數(shù)。（4）沒(méi)有一個(gè)人不愛美。（5）沒(méi)有不吃飯的人。（

10、6）沒(méi)有不呼吸的人。（7）在北京工作的人未必都是北京人。(8)每個(gè)兔子都比某些烏龜跑得快。(9)任何人都喜歡某些花。2、解釋：要求在給定解釋下求公式的真值。（如P44-例2.7，2.8）練習(xí)：論域D=1，2，3，特定元素a=1，指定謂詞P為如下表，則公式的的真值為？P (1,1)P (1,2)P (1,3)P (2,1)P (2,2)P (2,3)P (3,1)P (3,2)P (3,3)1010101013、求公式的前束范式。（注意：代替規(guī)則與換名規(guī)則的使用，等值式、基本等值式、量詞否定等值式、量詞轄域收縮與擴(kuò)張等值式（只有遇到B時(shí)量詞才互換）、量詞分配等值式，P48-例題2.11，P54-

11、習(xí)題2.14，2.15）練習(xí)：（1）x(F(x,y) $y(G(x,y)H(x,z) （2）（3） （4）3、一些基本概念：變量的約束出現(xiàn)、變量的自由出現(xiàn)、閉式、解釋，邏輯有效式，矛盾式，可滿足式，代換實(shí)例。第3章 集合的基本概念和運(yùn)算1、集合的相關(guān)概念：空集、子集、冪集、基數(shù)設(shè)A為一有限集合，|A|=n，那么A的子集個(gè)數(shù)為 。練習(xí)：（1）設(shè)A=1,2,3，B=P(A)，則|P(B)|=（ ）（2）設(shè)，則 P(P(S) 有（ ）個(gè)元素（3）設(shè)A= ，B=(A)，則P(B)有( )個(gè)元素。2、注意集合中元素與集合的關(guān)系及集合與集合的關(guān)系的表示。例如：（1）下列關(guān)系式正確的是（ ）。（2）下列關(guān)系

12、式正確的有（ ）A）且， B)且， C)且 D）且3、有關(guān)集合的計(jì)數(shù)問(wèn)題，特別是對(duì)兩個(gè)基本事件與三個(gè)基本事件的情形（P73-3.5，3.6，課堂練習(xí)）練習(xí)：（1）設(shè)集合A的基數(shù)A=4，集合B的基數(shù)|B|=5，且集合A與集合B有3個(gè)相同的元素，則（ ）（2）某幼兒園大班一共有28個(gè)小朋友，其中有15人學(xué)鋼琴，12人學(xué)圍棋，有5人兼學(xué)鋼琴和圍棋，那么有多少人沒(méi)有學(xué)鋼琴也沒(méi)有學(xué)圍棋？（3）如練習(xí)3.6中從1到300的整數(shù)中，有多少個(gè)不能被3也不能被5整除的數(shù)。4、本章節(jié)中特別一些基本概念的準(zhǔn)確性認(rèn)知。練習(xí)：判斷下列語(yǔ)句是否正確。（1）如果集合A有6個(gè)元素，則A的子集最多有5個(gè)元素。 （2）任何集合都

13、至少含有一個(gè)元素。 （3）任何一個(gè)集合都不可以是另一個(gè)集合的元素。第4章 二元關(guān)系與函數(shù)1、笛卡爾積的定義與計(jì)算及相關(guān)性質(zhì)：（1）語(yǔ)句“A，B，C為任意集合，若，則。”是否正確？（2）設(shè)A、B、C為任意的三個(gè)集合，則笛卡爾積：A(BC)=A(BC)。是否正確？2、二元關(guān)系的定義與表示：練習(xí)：（1），則A至B的笛卡爾積？從A到B有多少個(gè)不同的二元關(guān)系，A上的有多少個(gè)不同的二元關(guān)系?3、表示二元關(guān)系的方法：描述、關(guān)系矩陣、關(guān)系圖。（注意幾種方法表示關(guān)系是一一對(duì)應(yīng)，給出其中一個(gè)都要能表示出其他，例如給出關(guān)系矩陣，要能寫出表達(dá)式中的具體元素，能畫出關(guān)系圖。）練習(xí)：設(shè)A=2，3，4，5，6上的二元關(guān)系，

14、則R的表達(dá)式為？關(guān)系矩陣為?關(guān)系圖為？ 4、關(guān)系的運(yùn)算：關(guān)系的定義域、值域、域，逆、合成、F在A上的限制、A在F下的像，會(huì)求關(guān)系的冪。（課本練習(xí)題與留過(guò)的作業(yè)，P107例4.28重點(diǎn)）練習(xí)：P107例4.28一共有十六種不同的情形：設(shè)R和S是P上的關(guān)系，P是所有人的集合，則（1）表示（2）表示 （3）表示 。 （4）表示關(guān)系。 （5）表示. （6）表示。 （7）表示.（8）表示.（9）表示. (10) 表示.（11）表示. (12) 表示. (13)表示(14) 表示。(15) 表示(16) 均表示 。5、關(guān)系的性質(zhì)的討論（自反性、對(duì)稱性、反對(duì)稱性、傳遞性）（注意從關(guān)系圖觀察更方便）（P114

15、頁(yè)4.4）（1）自反關(guān)系的關(guān)系圖中每一個(gè)結(jié)點(diǎn)都有環(huán)。（2）對(duì)稱關(guān)系的關(guān)系圖中，如果兩個(gè)結(jié)點(diǎn)間有有向邊，則必成對(duì)出現(xiàn)。（3）反對(duì)稱關(guān)系的關(guān)系圖中，如果兩個(gè)結(jié)點(diǎn)間有有向邊，則必不是成對(duì)出現(xiàn)的。（4）傳遞關(guān)系的關(guān)系圖中，如果有從結(jié)點(diǎn)a到結(jié)點(diǎn)b的有向邊，同時(shí)又有從結(jié)點(diǎn)b到結(jié)點(diǎn)c的有向邊，則必定有從結(jié)點(diǎn)a到結(jié)點(diǎn)c的有向邊。 練習(xí)：（1）判斷下列關(guān)系的所具有的性質(zhì)。（2）設(shè)集合A=a，b，c，A上的關(guān)系R=，則R具備什么性質(zhì)？不具備什么性質(zhì)？特別注意:(1) 一個(gè)關(guān)系可以既不是對(duì)稱的，也不是反對(duì)稱的。(2) 一個(gè)關(guān)系可以既是對(duì)稱的，也是反對(duì)稱的。一些特殊關(guān)系的性質(zhì)如下：（1）空關(guān)系是對(duì)稱的、反對(duì)稱的和傳遞

16、的。（2）全關(guān)系是自反的、對(duì)稱的和傳遞的。（3）恒等關(guān)系是自反的、對(duì)稱的、反對(duì)稱的和傳遞的。6、會(huì)求關(guān)系的閉包（自反閉包，對(duì)稱閉包，傳遞閉包）。練習(xí)：（1）設(shè)，A上的關(guān)系 ，a)求出的關(guān)系矩陣。b)畫出的關(guān)系圖。c)求出自反閉包對(duì)稱閉包傳遞閉包.(2) 設(shè)集合上的二元關(guān)系R的關(guān)系矩陣,a)求出關(guān)系R的表示式，b)畫出R的關(guān)系圖，c) R具有哪些性質(zhì)？ d) 求出的表達(dá)式。7、關(guān)于等價(jià)關(guān)系：（要求會(huì)從定義上判斷一個(gè)關(guān)系是否為等價(jià)關(guān)系，會(huì)求等價(jià)類，商集，理解等價(jià)關(guān)系的商集與集合的劃分是一一對(duì)應(yīng)的。）定義：設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時(shí)具有自反性、對(duì)稱性和傳遞性，則稱R是等價(jià)關(guān)系。練習(xí)：（

17、1）前面6中的練習(xí)（2）加一問(wèn)e) 它是一個(gè)等價(jià)關(guān)系嗎？為什么？(2):設(shè)，A上的關(guān)，要求：（a）請(qǐng)畫出關(guān)系R的關(guān)系矩陣與關(guān)系圖；（b）R是否為等價(jià)關(guān)系，請(qǐng)說(shuō)明理由； （c）若R是等價(jià)關(guān)系，請(qǐng)求出關(guān)系R的所有等價(jià)類與求商集A/R。(3) 設(shè)集合A=1，2，3，4，5，6，A上的關(guān)系R滿足：R=|x,yAxy(mod)2，(或R=|x,yAxy(mod)3，)（a）請(qǐng)寫出關(guān)系R的元素，畫出關(guān)系R的關(guān)系矩陣與關(guān)系圖； （b）R是否為等價(jià)關(guān)系，請(qǐng)說(shuō)明理由； （c）若R是等價(jià)關(guān)系，請(qǐng)求出關(guān)系R的所有等價(jià)類與求商集A/R。（4）試判斷下列關(guān)系到是否為等價(jià)關(guān)系.1）在一群人所組成的集合上定義的“同姓”關(guān)系

18、；2）在一群人所組成的集合上定義的“朋友”關(guān)系；3）整數(shù)集上的“小于”關(guān)系；4）整數(shù)集上的“等于”關(guān)系；5）直線間的“平行”關(guān)系；6）冪集上的“”關(guān)系。8、關(guān)于偏序關(guān)系：（會(huì)定義，會(huì)畫偏序關(guān)系的哈斯圖，會(huì)根據(jù)哈斯圖寫出關(guān)系的表達(dá)式）。定義：設(shè)R是集合A上的二元關(guān)系，如果關(guān)系R同時(shí)具有自反性、反對(duì)稱性和傳遞性，則稱R是偏序關(guān)系。練習(xí)：設(shè)A=1，2，3，4，其上偏序關(guān)系R的12341234哈斯圖如右圖所示，則關(guān)系R的表達(dá)式為？第5章 圖的基本概念1、掌握?qǐng)D的基本概念：圖，環(huán)，平行邊，平凡圖(只有一個(gè)頂點(diǎn)的零圖，實(shí)際上是只有一個(gè)孤立點(diǎn)的圖)，簡(jiǎn)單圖，頂點(diǎn)的度練習(xí)：求下列各圖中指定點(diǎn)的度（1）設(shè)圖G

19、= ，如右圖所示，則b的入度= ， a的度= ，b的出度= ，d的度= 。（2）設(shè)圖G = ，如右圖所示，則v1的入度= ，v1的出度= .（3）設(shè)圖G = ，如右圖所示，v2的= 。（4）v3的度= 。2、理解“握手定理”及其推理的定理內(nèi)容，并能熟練應(yīng)用定理。握手定理：任意無(wú)向圖和有向圖的所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的2倍, 并且有向圖的所有頂點(diǎn)入度之和等于出度之和等于邊數(shù).握手定理推論 在任何無(wú)向圖和有向圖中，奇度頂點(diǎn)的個(gè)數(shù)必為偶數(shù).所以不存在有5個(gè)度數(shù)為奇數(shù)的頂點(diǎn)。練習(xí)：請(qǐng)回答下列各題。（1）、設(shè)一個(gè)圖有20個(gè)頂點(diǎn)，且所有頂點(diǎn)的度數(shù)都為3，則這個(gè)圖中有多少條邊？（2）、已知圖G有10條邊,

20、 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均為2度,則這個(gè)圖中有多少個(gè)頂點(diǎn)？（3）、已知圖G有16條邊, 每個(gè)頂點(diǎn)的度數(shù)均為2度,，則這個(gè)圖中有多少個(gè)頂點(diǎn)？（4）、已知圖G有12條邊, 其中有3個(gè)4度點(diǎn)，其余的頂點(diǎn)的度數(shù)均為3度,，則這個(gè)圖中有多少個(gè)頂點(diǎn)？（5）、已知圖G有28條邊, 其中有4個(gè)3度點(diǎn)，其余的頂點(diǎn)的度數(shù)均為4度,，則這個(gè)圖中有多少個(gè)頂點(diǎn)？（6）存在有5個(gè)度數(shù)為奇數(shù)的頂點(diǎn)嗎？3、會(huì)判斷一組數(shù)組是否為圖的度數(shù)列。練習(xí)：給定下列序列，可以構(gòu)成無(wú)向圖的結(jié)點(diǎn)度數(shù)的序列有：（ ），能構(gòu)成無(wú)向簡(jiǎn)單圖的結(jié)點(diǎn)度數(shù)序列的有：（ ）。（1）、（1，1，2，2，3）；（2）、（1，1，2，2，2）；（3）、（5

21、, 5, 4, 4, 2, 1）；（4）、（1，3，4，4，5）；（5）、（1，3，2，2，3）；（6）、（1，3，2，2，2）；（7）、（3, 5, 4, 2, 2, 1）；（8）、（2，2，2，2，2）；（9）、（1，1，2，5，2）；（10）、（1，1，3，3，3）；（11）（3，2，2，4，2）；（12）（1，4，2，2，3）；（13）、（1，3，2，5，2）；（14）、（2，3，2，2，2）；（15）、（3，3，3，3，3）。4、會(huì)求一個(gè)圖的補(bǔ)圖：設(shè)G=為n階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集,所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖. 練習(xí)：求下列圖的補(bǔ)圖。5、會(huì)判斷圖的連通性（有向圖與無(wú)向圖）特別是對(duì)于有向圖有：一個(gè)有向圖，如果它是強(qiáng)連通圖，