離散數(shù)學--期末復習

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

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

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

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

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

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

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

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

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

10、6）沒有不呼吸的人。（7）在北京工作的人未必都是北京人。(8)每個兔子都比某些烏龜跑得快。(9)任何人都喜歡某些花。2、解釋：要求在給定解釋下求公式的真值。（如P44-例2.7，2.8）練習：論域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ī)則的使用，等值式、基本等值式、量詞否定等值式、量詞轄域收縮與擴張等值式（只有遇到B時量詞才互換）、量詞分配等值式，P48-例題2.11，P54-

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

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

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

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

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

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

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

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

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

20、 4個3度頂點, 其余頂點的度數(shù)均為2度,則這個圖中有多少個頂點？（3）、已知圖G有16條邊, 每個頂點的度數(shù)均為2度,，則這個圖中有多少個頂點？（4）、已知圖G有12條邊, 其中有3個4度點，其余的頂點的度數(shù)均為3度,，則這個圖中有多少個頂點？（5）、已知圖G有28條邊, 其中有4個3度點，其余的頂點的度數(shù)均為4度,，則這個圖中有多少個頂點？（6）存在有5個度數(shù)為奇數(shù)的頂點嗎？3、會判斷一組數(shù)組是否為圖的度數(shù)列。練習：給定下列序列，可以構成無向圖的結點度數(shù)的序列有：（ ），能構成無向簡單圖的結點度數(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、會求一個圖的補圖：設G=為n階無向簡單圖，以V為頂點集,所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖. 練習：求下列圖的補圖。5、會判斷圖的連通性（有向圖與無向圖）特別是對于有向圖有：一個有向圖，如果它是強連通圖，