離散數(shù)學(xué)復(fù)習(xí)要點(diǎn)

離散數(shù)學(xué)復(fù)習(xí) 2018.1.3第1章 數(shù)學(xué)語(yǔ)言與證明方法知識(shí)點(diǎn)1：冪集的定義冪集的元素個(gè)數(shù)計(jì)算，如果A有n個(gè)元素，那么P（A）有2的n次方個(gè)元素例1的冪集 P（）的元素個(gè)數(shù) 為1，因?yàn)?的0次方為1.即 。的冪集P（）元素個(gè)數(shù)為2，其冪集為，知識(shí)點(diǎn)2： 集合的運(yùn)算P8的公式，特別要注意下面的公式：A-B=ABA=A(AB)= AB(AB) = ABAB=（A - B）(B - A)知識(shí)點(diǎn)3 文氏圖P7 用文氏圖表達(dá)集合運(yùn)算第2章 命題邏輯1 成真賦值，成假賦值例1：求 (pq)r的成假賦值若上式子成假，必須(pq)為1，r為0故成假賦值為 110 ，100，0102可滿足式，矛盾式，永真式的定義3 合取范式，析取范式的定義4 極大項(xiàng)，極小項(xiàng)的定義。例2 求(pq)r的合取范式的極大項(xiàng)，析取范式的極小項(xiàng)解 成假賦值為110，100，010，故此有三項(xiàng)極大項(xiàng)，(pq)r M2M4M6 成真賦值為000，001，011，101，111，故此析取范式有五項(xiàng)極小項(xiàng) (pq)rm0m1m3m5m75 聯(lián)接詞完備集 ，是完備的，因?yàn)?和 都可以用前三個(gè)符號(hào)來(lái)表達(dá)例如 pq（pq）（q p） （pq） pq ，也是完備的因?yàn)閜q (pq) (pq)但， 就不是完備的6 命題符號(hào)化和定理證明 例如 小王學(xué)過(guò)英語(yǔ)或者日語(yǔ)。如果小王學(xué)過(guò)英語(yǔ)，則他去過(guò)英國(guó)，如果他去過(guò)英國(guó)，他也去過(guò)日本。所以小王學(xué)過(guò)日語(yǔ)或者去過(guò)日本。證明： 1）p：小王去過(guò)英語(yǔ)； q：小王學(xué)過(guò)英語(yǔ)r : 小王去過(guò)英國(guó) s：小王去過(guò)日本2）前提： pq，pr，rs結(jié)論 ：qs3）構(gòu)造證明過(guò)程： 1 pr 前提引入 2 rs 前提引入 3 ps 1，2假言三段倫4 pq 前提引入 5 pq 4置換 6 qp 5置換 7 qs 6，3假言三段 8 qs 7置換7 歸結(jié)法證明：例子：用歸結(jié)法證明上述命題1）p：小王去過(guò)英語(yǔ)； q：小王學(xué)過(guò)英語(yǔ)r : 小王去過(guò)英國(guó) s：小王去過(guò)日本2）前提： pq，pr，rs結(jié)論 ：qs用歸結(jié)法改寫(xiě)為下述形式：前提：pq，pr，rs，q，s結(jié)論 0證明：1 rs 前提引入 2 s 前提引入3 r 1，2歸結(jié)4 pr 前提引入5 p 3，4歸結(jié)6 pq 前提引入7 q 6，7歸結(jié)8 q 前提引入9 0 7，8歸結(jié) 第3章 一階邏輯知識(shí)點(diǎn)1 公式符號(hào)化例如 所有的汽車(chē)比飛機(jī)慢例如 有的汽車(chē)比有的飛機(jī)慢例如 有的汽車(chē)比所有的飛機(jī)慢知識(shí)點(diǎn)2 前束范式的定義，及轉(zhuǎn)換 例：將上述轉(zhuǎn)換為前束范式P85 3.32第四章 關(guān)系1 笛卡爾積的定義例子：求1，2，34，52二元關(guān)系的矩陣表示與圖表示3 關(guān)系的傳遞性，對(duì)稱(chēng)性，反對(duì)稱(chēng)性，自反性。（判斷法則）4 關(guān)系的交，并，關(guān)系的合成，關(guān)系的冪運(yùn)算。5 傳遞閉包，對(duì)稱(chēng)閉包，自反閉包，tsr閉包4 等價(jià)關(guān)系，偏序關(guān)系與哈斯圖，集合的劃分例11，2，3有多少種劃分1,2,3,4有多少種劃分例2 A=1，2，3，4，5，6，7，8，9，10如果整除關(guān)系為偏序關(guān)系，畫(huà)出哈斯圖。并求2，3在該偏序關(guān)系的上界和下界第5章 函數(shù)知識(shí)點(diǎn)1：函數(shù)，恒等函數(shù)，單射，滿射，雙射函數(shù)例子 判斷下列映射是否是函數(shù)，是否是雙射函數(shù)例子 |A|=m |B|=n,求A到B上函數(shù)的個(gè)數(shù)，A到B上雙射函數(shù)的個(gè)數(shù)A到B上函數(shù)有 nm個(gè)，因?yàn)槊總€(gè)自變量都有n種選擇。A到B的雙射函數(shù)，如果當(dāng)n不等于m時(shí)，為0.因?yàn)殡p射函數(shù)必須一一對(duì)應(yīng)。如果m=n，則有n!知識(shí)點(diǎn)2 函數(shù)的像，完全原像。知識(shí)點(diǎn)3 函數(shù)的合成，的定義第6章圖1 握手定理2 完全圖Kn 圈圖Cn，輪圖Wn，各有多少頂點(diǎn)，多少邊3 生成子圖的定義和性質(zhì)。4 初級(jí)通路和簡(jiǎn)單通路的定義，初級(jí)回路和簡(jiǎn)單回路的定義。例子：給定一個(gè)無(wú)向圖，計(jì)算初級(jí)通路和簡(jiǎn)單通路的條數(shù)5 平面圖的定義，歐