三峽大學(xué)期末計(jì)算機(jī)專業(yè)離散數(shù)學(xué)考試期末離散復(fù)習(xí)(共13頁)

1、PAGE 1PAGE 14離散數(shù)學(xué)期末復(fù)習(xí)(fx)提要 課程(kchng)的主要內(nèi)容集合論部分(b fen)（集合的基本概念和運(yùn)算、二元關(guān)系和函數(shù)）；數(shù)理邏輯部分（命題邏輯、謂詞邏輯）；圖論部分（圖的基本概念、特殊的圖，樹及其性質(zhì)）。各章復(fù)習(xí)要求與重點(diǎn)第一章命題邏輯復(fù)習(xí)知識(shí)點(diǎn)、命題與聯(lián)結(jié)詞（否定、析取、合取、蘊(yùn)涵、等價(jià)），復(fù)合命題、命題公式與解釋，真值表，公式分類（永真、矛盾、可滿足），公式的等價(jià)、析取范式、合取范式，極?。ù螅╉?xiàng)，主析取范式、主合取范式 、公式類別的判別方法（真值表法、等值演算法、主析取/合取范式法）、全功能集、推理理論本章重點(diǎn)內(nèi)容：命題與聯(lián)結(jié)詞、公式與解釋、析取范式與合取范

2、式、公式恒真性的判定、推理理論復(fù)習(xí)要求、理解命題的概念；了解命題聯(lián)結(jié)詞的概念；理解用聯(lián)結(jié)詞產(chǎn)生復(fù)合命題的方法。、理解公式與解釋的概念；掌握求給定公式真值表的方法，用基本等價(jià)式化簡其他公式，公式在解釋下的真值。、了解析?。ê先。┓妒降母拍?；理解極大（?。╉?xiàng)的概念和主析?。ê先。┓妒降母拍?；掌握用基本等價(jià)式或真值表將公式化為主析取（合?。┓妒降姆椒ā?、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判別公式類型和公式等價(jià)的方法。掌握24個(gè)重要等值式。、掌握推理理論，會(huì)寫出推理的證明，掌握附加前提證明法和歸謬發(fā)。本章重點(diǎn)習(xí)題習(xí)題P31-36: 1.1,1.7-1.9,1.12,1.18,1.19

3、，1.15疑難解析1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具體方法有兩種，一是真值表法，對(duì)于任給一個(gè)公式，主要列出該公式的真值表，觀察(gunch)真值表的最后一列是否全為1（或全為0），就可以判定該公式是否恒真（或恒假），若不全為0，則為可滿足的。二是推導(dǎo)法，即利用基本等價(jià)式推導(dǎo)出結(jié)果為1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）當(dāng)且僅當(dāng)?shù)葍r(jià)于它的合取范式（析取范式）中，每個(gè)子句（短語）均至少包含一個(gè)原子及其否定。這里要求的析取范式中所含有的每個(gè)短語不是(b shi)極小項(xiàng)，一定要與求主析取范式相區(qū)別，對(duì)于合取范式也同樣。2、范式(fn sh)求范

4、式，包括求析取范式、合取范式、主析取范式和主合取范式。關(guān)鍵有兩點(diǎn)：一是準(zhǔn)確理解掌握定義；另一是巧妙使用基本等價(jià)式中的分配律、同一律和互補(bǔ)律，結(jié)果的前一步適當(dāng)使用等冪律，使相同的短語（或子句）只保留一個(gè)。3、推理理論掌握構(gòu)造證明法，一是要理解并掌握8個(gè)推理定理，二是會(huì)使用常用的推理規(guī)則，附加前提證明法和歸謬法，需要進(jìn)行一定的練習(xí)。例題分析例1 求的主析取范式與主合取范式。解 （1）求主析取范式， 方法1：利用真值表求解G0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000000111010101101011111因此 方法2：推導(dǎo)法 （2）求主合取范式方法(fn

5、gf)1：利用上面的真值表為0的有兩行，它們對(duì)應(yīng)的極大(j d)項(xiàng)分別為因此(ync)，方法2：利用已求出的主析取范式求主合取范式已用去6個(gè)極小項(xiàng)，尚有2個(gè)極小項(xiàng)，即 與 于是 例2 試證明公式為恒真公式。證法一 ：G=（PQ）（QR）（PR） =（PQ）（QR）PR =（PQ）（PR）（QQ）（QR）P）R =（PQP）（PRP）（QRP）R =（1（QRP）R =QRPR =1故G為恒真公式。例3 構(gòu)造下面的推理證明前提：p(qr) , sr , ps 結(jié)論：q 證明(zhngmng)：ps 前提引入p 化簡p(qr) 前提(qint)引入qr 假言(ji yn)推理s 化簡sr 前提引入

6、r 假言推理q 析取三段論推理正確。第二章 一階邏輯復(fù)習(xí)知識(shí)點(diǎn) 1、謂詞、量詞、個(gè)體詞、個(gè)體域、變元（約束變元與自由變元）2、一階邏輯公式與解釋，謂詞公式的類型（永真、矛盾、可滿足）3、一階邏輯公式等值式4、前束范式本章重點(diǎn)內(nèi)容：謂詞與量詞、公式與解釋、前束范式復(fù)習(xí)要求1、理解謂詞、量詞、個(gè)體詞、個(gè)體域、變元的概念；理解用謂詞、量詞、邏輯聯(lián)結(jié)詞描述一個(gè)簡單命題；了解命題符號(hào)化。2、理解公式與解釋的概念；掌握在有限個(gè)體域下消去公式量詞，求公式在給定解釋下真值的方法；了解謂詞公式的類型。3、證明等值式。4、掌握求公式前束范式的方法。本章重點(diǎn)習(xí)題習(xí)題P52-55：2.3，2.12 , 2.13,2.

7、14, 2.15疑難解析1、謂詞與量詞反復(fù)理解謂詞與量詞引入的意義，概念的含義及在謂詞與量詞作用下變量的自由性、約束性與換名規(guī)則。2、公式(gngsh)與解釋能將一階邏輯公式表達(dá)式中的量詞消除(xioch)，寫成與之等價(jià)的公式，然后將解釋I中的數(shù)值(shz)代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基礎(chǔ)上，利用改名規(guī)則、基本等價(jià)式與蘊(yùn)涵式（一階邏輯中），將給定公式中量詞提到母式之前稱為首標(biāo)。典型例題例1 設(shè)I是如下一個(gè)解釋： F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1求的真值。解 例2 試將一

8、階邏輯公式化成前束范式。解 第三章 集合的基本概念和運(yùn)算復(fù)習(xí)知識(shí)點(diǎn)1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、冪集2、集合的交、并、差、補(bǔ)等運(yùn)算及其運(yùn)算律（交換律、結(jié)合律、分配律、吸收律、 對(duì)偶律等），文氏圖3、集合的計(jì)數(shù)本章重點(diǎn)內(nèi)容：集合的概念、集合的運(yùn)算性質(zhì)、集合恒等式的證明，集合的計(jì)數(shù) 復(fù)習(xí)要求1、理解(lji)集合、元素、子集、空集、全集、集合的包含、相等、冪集等基本概念。2、掌握集合的表示法和集合的交、并、差、補(bǔ)等基本(jbn)運(yùn)算。3、掌握集合運(yùn)算基本規(guī)律，證明(zhngmng)集合等式的方法。4、 掌握集合的計(jì)數(shù)。 疑難解析1、集合的概念重點(diǎn)對(duì)冪集加以掌握

9、，一是掌握冪集的構(gòu)成，一是掌握冪集元數(shù)為2n。2、集合恒等式的證明重視吸收律和重要等價(jià)式在證明中的特殊作用。習(xí)題P71-75: 3.8， 3.9，3.16， 3.17， 3.18例題分析例1 設(shè)A，B是兩個(gè)集合，A=1，2，3，B=1，2，則 。解 于是例2 設(shè)，試求： (1)； (2)； (3)； (4)； (5)； (6)。解 (1) (2) (3) (4) (5) (6)例3 試證明 證明 第四章 二元關(guān)系和函數(shù)(hnsh)復(fù)習(xí)(fx)知識(shí)點(diǎn)1、笛卡爾積，關(guān)系(gun x)、關(guān)系矩陣 2、復(fù)合關(guān)系與逆關(guān)系 3、關(guān)系的性質(zhì)（自反性、對(duì)稱性、反對(duì)稱性、傳遞性） 4、關(guān)系的閉包（自反閉包、對(duì)稱

10、閉包、傳遞閉包）5、等價(jià)關(guān)系與等價(jià)類6、偏序關(guān)系與哈斯圖（Hasse）、極大/小元、最大/小元、上/下界、最小上界、最大下界7、函數(shù)及其性質(zhì)（單射、滿射、雙射）8、復(fù)合函數(shù)與反函數(shù)本章重點(diǎn)內(nèi)容：二元關(guān)系的概念、關(guān)系的性質(zhì)、關(guān)系的閉包、等價(jià)關(guān)系、映射的概念復(fù)習(xí)要求1、理解關(guān)系的概念：二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系；掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖、關(guān)系的運(yùn)算。2、掌握求復(fù)合關(guān)系與逆關(guān)系的方法。3、理解關(guān)系的性質(zhì)（自反性、反自反性，對(duì)稱性、反對(duì)稱性、傳遞性），掌握其判別方法（定義、矩陣、圖）。4、掌握求關(guān)系的閉包 （自反閉包、對(duì)稱閉包、傳遞閉包）的方法。5、理解等價(jià)關(guān)系和偏序關(guān)系的概念，掌

11、握等價(jià)類的求法和偏序關(guān)系做哈斯圖的方法，極大/小元、最大/小元、上/下界、最小上界、最大下界的求法。6、理解函數(shù)概念：函數(shù)、函數(shù)相等、復(fù)合函數(shù)和反函數(shù)。7、理解單射、滿射、雙射等概念，掌握其判別方法。 疑難解析 1、關(guān)系的概念理解并熟練掌握二元關(guān)系的概念及關(guān)系矩陣、關(guān)系圖表示。 2、關(guān)系的性質(zhì)及其判定關(guān)系的性質(zhì)既是對(duì)關(guān)系概念的加深理解與掌握，又是關(guān)系的閉包、等價(jià)關(guān)系、偏序關(guān)系的基礎(chǔ)。 要會(huì)判斷關(guān)系的性質(zhì)。、關(guān)系的閉包在理解掌握關(guān)系閉包概念(ginin)的基礎(chǔ)上，主要掌握閉包的求法。關(guān)鍵是熟記三個(gè)定理的結(jié)論： ；定理(dngl)3， ；定理(dngl)4，推論 。、半序關(guān)系及半序集中特殊元素的確

12、定理解與掌握半序關(guān)系與半序集概念的關(guān)鍵是哈斯圖。哈斯圖畫法掌握了，對(duì)于確定任一子集的最大（?。┰?，極大（?。┰簿腿菀琢?。這里要注意，最大（小）元與極大（?。┰荒茉谧蛹瘍?nèi)確定，而上界與下界可在子集之外的全集中確定，最小上界為所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以與某一元素相等，最大下界也同樣。、映射的概念與映射種類的判定映射的種類主要指單射、滿射、雙射與非單非滿射。判定的方法除定義外，可借助于關(guān)系圖，而實(shí)數(shù)集的子集上的映射也可以利用直角坐標(biāo)系表示進(jìn)行，尤其是對(duì)各種初等函數(shù)。習(xí)題P112-116: 4.4， 4.25例題分析例1 設(shè)集合，判定下列關(guān)系，哪些是自反的，對(duì)稱的

13、，反對(duì)稱的和傳遞的：解：均不是自反的；R4是對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是反對(duì)稱的；R1 ,R2 ,R3 , R4 ,R5是傳遞的。例2、設(shè)集合上的關(guān)系 ，求出它的自反閉包，對(duì)稱閉包和傳遞閉包。解：第五-七章 圖論復(fù)習(xí)知識(shí)點(diǎn)1、無向圖、有向圖，通路，回路，連通分支 2、關(guān)聯(lián)矩陣、鄰接矩陣，可達(dá)矩陣3、二部圖，歐拉圖，哈密頓圖，平面圖4、樹 本章重點(diǎn)內(nèi)容(nirng)： 圖的基本概念，特殊圖的判定復(fù)習(xí)(fx)要求1、理解圖的有關(guān)概念(ginin)：圖、完全圖、子圖、圖的同構(gòu)。2、掌握圖的矩陣表示（關(guān)聯(lián)矩陣、鄰接矩陣）。3、學(xué)會(huì)判斷特殊的圖。4、理解無向樹與有向樹的概念。 疑難解

14、析 本章的概念較多，學(xué)習(xí)時(shí)需要認(rèn)真比較各概念的含義，如：圖、子圖、有向圖；路、簡單路、回路；連通分支；二部圖，歐拉圖，哈密頓圖，平面圖；樹等。 典型例題在具有n個(gè)頂點(diǎn)的完全圖Kn中刪去多少條邊才能得到樹？解：n個(gè)頂點(diǎn)的完全圖Kn中共有n（n-1）/2條邊，n個(gè)頂點(diǎn)的樹應(yīng)有n-1條邊，于是，刪去的邊有：n（n-1）/2-（n-1）=（n-1）（n-2）/2二、考核說明本課程的考核按平時(shí)成績30%期末考試70%的分配進(jìn)行考核。 期末考試實(shí)行統(tǒng)一閉卷考核，試卷滿分為100。 （考試時(shí)間為110分鐘）。1、試題類型試題類型有選擇題（分?jǐn)?shù)占5%）、填空題（分?jǐn)?shù)占15%）、計(jì)算題（分?jǐn)?shù)占21%），證明題（

15、分?jǐn)?shù)占28%）和解答題（分?jǐn)?shù)占21%）。2、考核試卷題量分配試卷題量在各部分的分配是：集合論約占40%，數(shù)理邏輯約占50%，圖論約占10%。綜合練習(xí)及解答（一）填空題1、請把“大于3而小于或等于7的整數(shù)集合”用任一種集合的表示方法表示出來A= 。A，B是兩個(gè)集合，A=1，2，3，4，B=2，3，5，則B-A= ，（B）（A）= ，（B）的元素個(gè)數(shù)為 。設(shè)，則從A到B的所有(suyu)映射 。設(shè)命題(mng t)公式，則使公式(gngsh)G為假的解釋是 、 和 。5、全集E=1，2，3，4，5，A=1，5，B=1，2，3，4，C=2，5， 求AB= ，（A）（C）= ，C= 。6、表達(dá)式xyL

16、（x，y）中謂詞的定義域是a，b，c，將其中的量詞消除，寫成與之等價(jià)的命題公式為 。（二）單項(xiàng)選擇題（選擇一個(gè)正確答案的代號(hào)，填入括號(hào)中）設(shè)命題公式，則G是（ ）。A.永真的 B.永假的 C.可滿足的 D.析取范式2、設(shè)集合，A上的關(guān)系，則=（ ）。 3、一個(gè)公式在等價(jià)意義下，下面哪個(gè)寫法是唯一的（ ）。A析取范式 B合取范式 C主析取范式 D以上答案都不對(duì)4、設(shè)命題公式G=（PQ），H=P（QP），則G與H的關(guān)系是（ ）。AGH BHG CG=H D以上都不是5、下列命題正確的是（ ）。A= B= Caa，b，c Da，b，c6、設(shè)集合A=a，b，c，A上的關(guān)系R=（a，b），（a，c），（

17、b，a），（b，c），（c，a），（c，b），（c，c），則R具有關(guān)系的（ ）性質(zhì)。A自反 B對(duì)稱 C傳遞 D反對(duì)稱7、設(shè)R為實(shí)數(shù)集，映射=RR，（x）= -x2+2x-1，則是（ ）。A單射而非滿射 B滿射而非單射 C雙射 D既不是單射，也不是滿射8、下列語句中，（ ）是命題。A下午有會(huì)嗎？ B這朵花多好看呀！ C2是常數(shù)。 D請把門關(guān)上。9、下面給出的一階邏輯等價(jià)式中，（ ）是錯(cuò)的。x（A（x）B（x）=xA（x）xB（x）AxB（x）=x （AB（x）x（A（x）B（x）=xA（x）xB（x）xA（x）=x（A（x）（三）計(jì)算題1、設(shè)R和S是集合(jh)上的關(guān)系(gun x)，其中，試求

18、： （1）寫出R和S 的關(guān)系(gun x)矩陣；計(jì)算。設(shè)A=a，b，c，d，R1，R2是A上的關(guān)系，其中R1=（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d），R2=（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）。畫出R1和R2的關(guān)系圖；判斷它們是否為等價(jià)關(guān)系，是等價(jià)關(guān)系的求A中各元素的等價(jià)類。用真值表判斷下列公式是恒真？恒假？可滿足？（PP）Q（PQ）Q（PQ）（QR）（PR）4. 設(shè)解釋(jish)I為：定義域D=-2，3，6；F（x）：x3；G（x）：x5。 在解釋(jish)I下求公式x（F（x）G（x）的真值。5、化簡下式：（ABC）（AB）（A（BC）A）已知A=1，2，3，4，5，B=1，2，3，R是A到B的二元關(guān)系，并且(bngqi)R=（x，y）|xA且yB且2 x+y 4，畫出R的關(guān)系圖，并寫出關(guān)系矩陣。求命題公式（PQ）（PQ）的析取范式與合取范式。（四）證明題1、證明等價(jià)式。 構(gòu)造推理(tul)證明：蘊(yùn)涵(ynhn)Q。A，B，C為任意的集合(jh)，證明：（AB）C=A（BC）利用一階邏輯的基本等價(jià)式，證明：xy（