1、一、邏輯和證明命題邏輯命題：是一個(gè)可以判斷真假的陳述句。聯(lián)接詞：A、V、-、 ？、?0記住“ p僅當(dāng)q”意思是“如果p,則q，即p-記住“ q除非p”意思是“ ？p“q”。會(huì)考察條件語句翻譯成漢語構(gòu)造真值表pqpqpAqpVqTTTTTFFTFTFTFFFFp” qp?qpOq?pTTFFFFTFTFTTTTFTpq無論取何pq無論取何系統(tǒng)規(guī)范說明的一致性是指系統(tǒng)沒有可能會(huì)導(dǎo)致矛盾的需求，即若值都無法讓復(fù)合語句為真，則該系統(tǒng)規(guī)范說明是不一致的命題等價(jià)式邏輯等價(jià)：在所有可能情況下都有相同的真值的兩個(gè)復(fù)合命題，可以用真值表或者構(gòu)造新的邏輯等價(jià)式。證邏輯等彳是通過p推導(dǎo)出q,證永真式是通過p推導(dǎo)出T

2、o邏輯等價(jià)式p A T ? ppVF ? p恒等律pAF ? FpVT ? T支配律p A p ? p募等律?(?P) ? p雙否律p A q ? q A p交換律(p A q) A r ? p A (q A r)結(jié)合律p V (q Ar)? (p V q) A (p V r)p A (q V r)? (p A q) V (p A r)分配律?(p A q) ? ?p V ?q?(p Vq) ? ?p A ?q德摩根律pV(p Aq) ? pPA(pVq) ? p吸收律pA?p ? FpV?p ? T否定律條件命題等價(jià)式pfq ? ?pVqpf q ? ?qf ?ppVq ? ?p f q p

3、Aq ? ?(pf?q)?(pf q) ? pA ?q(p f q) A (p f r) ? p f (q A r)(pr) A(qfr) ? ( pVq)f(pfq)V(pfr) ? pfqVr)(pr) V(qfr) ? ( pAq)fr雙條件命題等價(jià)式p?q ? (p fq) A(qf p) p?q ? ?p?q p?q ? (p A q) V (?p A ?q)?(p?q) ? p?q量詞謂詞+量詞變成一個(gè)更詳細(xì)的命題，量詞要說明論域，否則沒有意義，如果有約束條件就直接放在量詞后面，如 ?x0P(x) 0當(dāng)論域中的元素可以一一列舉，那么?xP(x)就等價(jià)于P(x1) A P(x2).

4、A P(xn)同理，？xP(x)就等價(jià)于 P(x1) VP(x2). VP(xn)。兩個(gè)語句是邏輯等價(jià)的，如果不論他們謂詞是什么，也不論他們的論域是什么， 他們總有相同的真值，如 ?x (P(x) A Q(x) ffi( ?xP(x) A ( ?xQ(x)。量詞表達(dá)式的否定： ？?xP(x) ? ?x?P(x) , ?xP(x) ? ?x?P(x) o量詞嵌套我們采用循環(huán)的思考方法。量詞順序的不同會(huì)影響結(jié)果。語句到嵌套量詞語句的翻譯，注意論域。嵌套量詞的否定就是連續(xù)使用德摩根定律，將否定詞移入所有量 詞里。推理規(guī)則一個(gè)論證是有效的，如果它的所有前提為真且蘊(yùn)含著結(jié)論為真。但有效論證不代表結(jié)論正確

5、，因?yàn)橐苍S有的前提是假的。推理規(guī)則，都是基于永真式的，用來證明一個(gè)前提蘊(yùn)含一個(gè)結(jié)論。而基于可滿足式的推理規(guī)則叫謬誤。pp” q(p A(p” q) “q假言推理qp” qqf r(p f q) A(q7 r) f(pfr)假言二段論pf r?qp” q(?q A(p“q) f?p取拒式?ppVq?p(p V q) A ?p) f q析取三段論qpp” (p V q)附加律pVqpAq(p Aq)f p化簡律PPq(pAq) ( pAq)合取律pAqPVq?pVr(p V q) A (?p V r) f (q V r)消解律q V r量化推理規(guī)則?xP(x)全稱實(shí)例P(c)P(c),任意c全稱引

6、入?P(x)?xP(x)存在實(shí)例P(c),對(duì)某個(gè)cP(c),對(duì)某個(gè)c存在引入?xP(x)命題和量化命題的組合使用。二、集合、函數(shù)、序列、與矩陣2.1集合G說的是元素與集合的關(guān)系，？說的是集合與集合的關(guān)系。常見數(shù)集有N=0,1,2,3.),2整數(shù)集，Z+正整數(shù)集，Q有理數(shù)集，R實(shí)數(shù)集，R+正實(shí)數(shù)集，C復(fù)數(shù)集。A和B相等當(dāng)僅當(dāng)？x(x G A?xG B); A是B的子集當(dāng)僅當(dāng)？x(x G Qx G B);A是 B 的真子集當(dāng)僅當(dāng)？x(x GA- x G B) A ?x(x?A A x G B)。募集：集合元素的所有可能組合，肯定有？何它自身。如？的募集就是?,而?的募集是? , ?。笛卡爾積：AX

7、 B,結(jié)果是序偶，其中的一個(gè)子集叫一個(gè)關(guān)系。帶量詞和集合符號(hào)如？xGR (x20)是真的，則所有真值構(gòu)成真值集。集合恒等式名稱(A U B)=A n B?(A n B)=A U B德摩根律AU (A n B)=AAn (A U B)=A吸收律函數(shù)考慮A-B的函數(shù)關(guān)系，定義域、陪域(實(shí)值函數(shù)、整數(shù)值函數(shù))、值域、像集(定義域的一個(gè)子集在值域的元素集合)一對(duì)一或者單射：B可能有多余的元素，但不重復(fù)指向映上或者滿射：B中沒有多余的元素，但可能重復(fù)指向。一一對(duì)應(yīng)或者雙射：符合上述兩種情況的函數(shù)關(guān)系。反函數(shù)：如果是一一對(duì)應(yīng)的就有反函數(shù)，否則沒有。合成函數(shù)：f o g(a)=f(g(a), 一般來說交換律

8、不成立。序列無限集分為：一組是和自然數(shù)集合有相同基數(shù)，另一組是沒有相同基數(shù)。前者是可數(shù)的，后者不可數(shù)。想要證明一個(gè)無限集是可數(shù)的只要證明它與自然數(shù)之間有一 一對(duì)應(yīng)的關(guān)系。如果A和B是可數(shù)的，則 AU B也是可數(shù)的。如果存在一對(duì)一函數(shù)f從A到B和一對(duì)一函數(shù)g從B到A,那么A和B之間是一 一對(duì)應(yīng)的。求和公式：a+ar+ar 2+ar3+.+ar n = (ar n+1-a)/(r-1)1+2+3+.+n = n(n+1)/21+22+32+.+n 2 = n(n+1)(2n+1)/61+23+33+.+n 3 = n 2(n+1) 2/42.6矩陣普通矩陣和、減、乘積，0-1矩陣還可以A、V、O

9、（和相乘類似，用V代替 +, 用A代替X）九、關(guān)系9.1關(guān)系及其性質(zhì)設(shè)A和B是集合，從A到B的二元關(guān)系是 AX B的子集。一個(gè)從 A到B的二元關(guān)系是集合R,第一個(gè)元素取自 A第二個(gè)元素取自B,當(dāng)（a,b）屬于R時(shí)寫作aRbo集合A上的關(guān)系是A到A的關(guān)系，有n個(gè)元素就有n2個(gè)有序?qū)Γ琻2個(gè)有序?qū)陀?2n2個(gè)關(guān)系。考慮集合A到A的關(guān)系R:任意aG A都有（a, a） G R,則R是集合A上的自反關(guān)系。任意a, bGA,若（a, b） G R都有（b, a） G R,則R是對(duì)稱關(guān)系。任意a, bGA,若（a, b） G R且（b, a） G R一定有a=b,則R是反對(duì)稱關(guān)系。任意 a, b, c

10、G A,若（a, b） G R 且（b, c） G R一定有（a, c） G R,則 R是 傳遞關(guān)系。若R是A到B的關(guān)系，S是B到C的關(guān)系，R與S的合成Ro S是有序數(shù)對(duì)（a, c）。 其中a GA, cGC,且存在一個(gè)bGB使得（a, b） G R, （b, c） G S。二元關(guān)系的5 種復(fù)合要會(huì)翻譯成漢語。關(guān)系的表示0-1矩陣法：A有n個(gè)元素，B有m個(gè)元素，用一個(gè) nXm的矩陣M表示，m=1 表示有關(guān)系。自反關(guān)系的0-1矩陣主對(duì)角線全為1;對(duì)稱關(guān)系的0-1矩陣是對(duì)稱陣；反對(duì)稱關(guān)系的0-1矩陣關(guān)于主對(duì)角線反對(duì)稱。M1UR2=M1 V M2, MmRkM1A M2, M1 0 RkMQM2。有

11、向圖法：A有n個(gè)元素，每一個(gè)關(guān)系是一條有向邊。自反關(guān)系的圖每一個(gè)頂點(diǎn) 都有一個(gè)環(huán)；對(duì)稱關(guān)系的圖在不同頂點(diǎn)之間每一條邊都存在與之對(duì)應(yīng)的反方向邊(也可用無向圖)；反對(duì)稱關(guān)系的圖在不同頂點(diǎn)之間每一條邊都不存在與之對(duì)應(yīng)的反方 向邊；傳遞關(guān)系的圖在 3個(gè)不同頂點(diǎn)之間構(gòu)成正確方向的三角形。關(guān)系的閉包自反閉包：RUA,其中 = (a, a) |a G A對(duì)稱閉包：R并 R1,其中 R1= (b,a) | (a, b) G R傳遞閉包：r矩陣傳遞閉包=mvm2 v m3 . v mT , 了解沃舍爾算法等價(jià)關(guān)系：自反、對(duì)稱且傳遞的關(guān)系集合 A 的元素 a在 R上的 等價(jià)類a=s|(a,s) G R A s G

12、 A。如 A=1,2,3,4,5,6,7,8, R=(a,b)|a = b(mod 3)的等價(jià)類劃分如下1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,6偏序關(guān)系：自反、反對(duì)稱且傳遞的的關(guān)系偏序集（S, ）中如果既沒有 a&b,也沒有b a,則a和b是不可比的。全序集：如果偏序集中每個(gè)元素都可比，則為全序集，如（Z, 0）是全序集，但（Z+, |）不是，因?yàn)橛?和7是不可比的。良序集：如果是全序集，而且S的每個(gè)非空機(jī)子都有一個(gè)最小元素，則為良序集。哈塞圖：對(duì)有窮偏序集，去掉環(huán)，去掉所有由傳遞性可以得到的邊，排列所有的 邊使得方向向上。極大元極小元：圖中的頂元素和底元素，可能有多個(gè)最

13、大元最小元：只有唯一的一個(gè)，比其他都或上界下界：只有唯一的一個(gè)，比其他都）或格：每對(duì)元素都有最小上界和最大下界十、圖圖的概念簡單圖：每對(duì)頂點(diǎn)最多只有一條邊多重圖：每對(duì)頂點(diǎn)可以有多條邊無向圖：邊沒有方向有向圖：邊有方向圖的術(shù)語無向圖中，點(diǎn)v的度為deg(v),如果v是一個(gè)環(huán)，則度為2。度為0的點(diǎn)是孤立 的，度為1的點(diǎn)是懸掛的。有 m條邊的無向圖則2m=2 deg(v)。無向圖有偶數(shù)個(gè)度 為奇數(shù)的點(diǎn)，因?yàn)?2m=S deg(Vi)+ Ndeg(Vj)。有向圖中，點(diǎn)v的入度為deg(v),出度為deg+(v),且deg-(v尸deg+(v尸邊數(shù)。 有向圖忽略邊的方向后得到的圖叫做基本無向圖，它們有相

14、同的邊數(shù)。會(huì)畫完全圖Kn、圈圖G、輪圖W。二分圖，將點(diǎn)分成2部分，每條邊都連著一部分和另一部分。用著色法判讀是否是二分圖。完全二分圖 (,m是邊最多的二分圖。圖的表示鄰接表：無向簡單圖包括頂點(diǎn)和相鄰頂點(diǎn)，不太好表示無向多重圖因?yàn)檫叺臄?shù)量不好表示。有向圖包括起點(diǎn)和終點(diǎn)。鄰接矩陣：無向簡單圖按頂點(diǎn)排列，如果 w和vj之間相鄰則a。是1,否則是 00無向多重圖這時(shí)aij是vi和vj之間的邊數(shù)。可知無向圖的鄰接矩陣都是對(duì)稱陣。 有向簡單圖也按照頂點(diǎn)排列，如果 vi, vj是邊則aij是1,否則是0。有向多重 圖也按頂點(diǎn)排列，只不過 aij是vi, vj之間的邊數(shù)。關(guān)聯(lián)矩陣：將圖G按v行e歹U排列，如果

15、v和e關(guān)聯(lián)，則a0是1,否則是0圖的同構(gòu)：簡單圖 G1和G2,如果存在對(duì)應(yīng)的從 V1到V2的函數(shù)f ,且對(duì)V1 的a和b來說，a與b相鄰當(dāng)僅當(dāng)f（a）與f（b）在G2中相鄰，則G1和G2是同構(gòu)的， f稱為同構(gòu)。圖形不變量如頂點(diǎn)數(shù)、邊數(shù)、度數(shù)，如果不同則不同構(gòu)，如果相同則 可能同構(gòu)。當(dāng)我們找到f后，還要比較兩個(gè)圖的鄰接矩陣，看 f是否是保持邊的。圖的連通性簡單圖中，用X0 = u, x1.x n=v來表示一條通路，若 u=v且路長度大于0,則是 回路，如果不包含重復(fù)的邊，則這條通路是簡單的。無向圖中每對(duì)不同頂點(diǎn)之間都有通路則這個(gè)圖是連通的，割點(diǎn)（關(guān)節(jié)點(diǎn)）、割邊 （橋）去掉后就會(huì)使圖變得不連通，不

16、含割點(diǎn)的圖叫做不可割圖。有向圖中，任意一對(duì)頂點(diǎn) a和b,都有從a至ij b以及從b到a的通路，則這個(gè)有 向圖是強(qiáng)連通的，如果只是基本無向圖能保持聯(lián)通則叫做弱聯(lián)通的，會(huì)求強(qiáng)連通分 支。通路與同構(gòu)：可以用長度為 k2的簡單回路的存在性來證不同構(gòu)或者是潛在的 同構(gòu)映射f ,同樣找到f后還要驗(yàn)證f保持邊。圖G （允許是有向和無向、 多重邊和環(huán)）的Vi到必的長度為n的不同通路的條數(shù) 等于Ani,j, A是G的鄰接矩陣。歐拉回路與哈密頓回路歐拉回路：包含G的每一條邊的簡單回路歐拉通路：包含 G的每一條邊的簡單通路。含有至少2個(gè)頂點(diǎn)的連通多重圖有歐拉回路當(dāng)僅當(dāng)它的每個(gè)頂點(diǎn)度都為偶數(shù)，有歐拉通路但無歐拉回路當(dāng)

17、僅當(dāng)它恰有2個(gè)度為奇數(shù)的頂點(diǎn)。哈密頓回路：包含G的每一個(gè)頂點(diǎn)恰好一次的簡單回路。哈密頓通路：包含 G的每一個(gè)頂點(diǎn)恰好一次的簡單通路。含有至少3個(gè)頂點(diǎn)的簡單圖，若每個(gè)頂點(diǎn)的度都(n/2),或者每一對(duì)不相鄰的頂點(diǎn)u和v都有deg(u)+deg(v) n,則有哈密頓回路。最短通路算法：迪克斯特拉算法和旅行商問題(枚舉)10.7平面圖歐拉公式：G是有e條邊和v個(gè)頂點(diǎn)的平面連通簡單圖，r是G的平面圖表示中的面數(shù)，則有r=e-v+2 o根據(jù)上述條件，有 3個(gè)推論，可以用來判斷不是平面圖：推論 1:若 v3,則 e 3v-6。推論2: G中有度不超過5的頂點(diǎn)。推論3: v)3且沒有長度為3的回路，則e 2V-4