離散數(shù)學(xué)知識(shí)點(diǎn)整理2163

離散數(shù)學(xué)一、邏輯和證明命題邏輯命題：是一個(gè)可以判斷真假的陳述句。聯(lián)接詞：∧、∨、→、?、?。記住“p僅當(dāng)q”意思是“如果p，則q”，即p→。記住“q除非p”意思是“?p→q”。會(huì)考察條件語句翻譯成漢語。構(gòu)造真值表pTTFFqTFTFp∧qp∨qp→qp?qp⊙q?pTFFFTTTFTFTTTFFTFTTFFFTT語句翻譯系統(tǒng)規(guī)范說明的一致性是指系統(tǒng)沒有可能會(huì)導(dǎo)致矛盾的需求，即若pq無論取何值都無法讓復(fù)合語句為真，則該系統(tǒng)規(guī)范說明是不一致的。命題等價(jià)式邏輯等價(jià)：在所有可能情況下都有相同的真值的兩個(gè)復(fù)合命題，可以用真值表或者構(gòu)造新的邏輯等價(jià)式。證邏輯等價(jià)是通過p推導(dǎo)出q，證永真式是通過p推導(dǎo)出T。邏輯等價(jià)式p∧T?p恒等律支配律p∨F?pp∧F?Fp∨T?Tp∧p?p冪等律雙否律?(?P)?pp∧q?q∧p(p∧q)∧r?p∧(q∧r)交換律結(jié)合律分配律p∨(q∧r)?(p∨q)∧(p∨r)p∧(q∨r)?(p∧q)∨(p∧r)?(p∧q)??p∨?q德摩根律吸收律否定律?(p∨q)??p∧?qp∨(p∧q)?pP∧(p∨q)?pp∧?p?Fp∨?p?T條件命題等價(jià)式p→q??p∨qp→q??q→?pp∨q??p→qp∧q??(p→?q)?(p→q)?p∧?q(p→q)∧(p→r)?p→(q∧r)(p→r)∧(q→r)?(p∨q)→r(p→q)∨(p→r)?p→(q∨r)(p→r)∨(q→r)?(p∧q)→r雙條件命題等價(jià)式p?q?(p→q)∧(q→p)p?q??p??qp?q?(p∧q)∨(?p∧?q)?(p?q)?p??q量詞謂詞+量詞變成一個(gè)更詳細(xì)的命題，量詞要說明論域，否則沒有意義，如果有約束條件就直接放在量詞后面，如?x>0P(x)。當(dāng)論域中的元素可以一一列舉，那么?xP(x)就等價(jià)于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等價(jià)于P(x1)∨P(x2)...∨P(xn)。兩個(gè)語句是邏輯等價(jià)的，如果不論他們謂詞是什么，也不論他們的論域是什么，他們總有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。量詞表達(dá)式的否定：??xP(x)??x?P(x)，??xP(x)??x?P(x)。量詞嵌套我們采用循環(huán)的思考方法。量詞順序的不同會(huì)影響結(jié)果。語句到嵌套量詞語句的翻譯，注意論域。嵌套量詞的否定就是連續(xù)使用德摩根定律，將否定詞移入所有量詞里。推理規(guī)則一個(gè)論證是有效的，如果它的所有前提為真且蘊(yùn)含著結(jié)論為真。但有效論證不代表結(jié)論正確，因?yàn)橐灿性S的前提是假的。推理規(guī)則，都是基于永真式的，用來證明一個(gè)前提蘊(yùn)含一個(gè)結(jié)論。而基于可滿足式的推理規(guī)則叫謬誤。p(p∧(p→q))→q假言推理假言三段論取拒式p→qqp→qq→rp→r?qp→q?pp∨q((p→q)∧(q→r))→(p→r)(?q∧(p→q))→?p((p∨q)∧?p)→q析取三段論?pqpp→(p∨q)附加律化簡(jiǎn)律合取律p∨qp∧q(p∧q)→ppp（p∧q）→（p∧q）qp∧qp∨q(p∨q)∧(?p∨r)→(q∨r)消解律?p∨rq∨r量化推理規(guī)則?xP(x)全稱實(shí)例P(c)P(c)，任意c?P(x)全稱引入存在實(shí)例?xP(x)P(c)，對(duì)某個(gè)cP(c)，對(duì)某個(gè)c存在引入?xP(x)命題和量化命題的組合使用。二、集合、函數(shù)、序列、與矩陣集合∈說的是元素與集合的關(guān)系，?說的是集合與集合的關(guān)系。常見數(shù)集有N={0,1,2,3...}，Z整數(shù)集，Z+正整數(shù)集，Q有理數(shù)集，R實(shí)數(shù)集，R+正實(shí)數(shù)集，C復(fù)數(shù)集。A和B相等當(dāng)僅當(dāng)?x(x∈A?x∈B)；A是B的子集當(dāng)僅當(dāng)?x(x∈A→x∈B)；A是B的真子集當(dāng)僅當(dāng)?x(x∈A→x∈B)∧?x(x?A∧x∈B)。冪集：集合元素的所有可能組合，肯定有?何它自身。如?的冪集就是{?}，而{?}的冪集是{?，{?}}。笛卡爾積：A×B，結(jié)果是序偶，其中的一個(gè)子集叫一個(gè)關(guān)系。帶量詞和集合符號(hào)如?x∈R（x2>0）是真的，則所有真值構(gòu)成真值集。集合恒等式名稱(A∪B)'=A'∩B'(A∩B)'=A'∪B'A∪(A∩B)=AA∩(A∪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οg(a)=f(g(a))，一般來說交換律不成立。序列無限集分為：一組是和自然數(shù)集合有相同基數(shù)，另一組是沒有相同基數(shù)。前者是可數(shù)的，后者不可數(shù)。想要證明一個(gè)無限集是可數(shù)的只要證明它與自然數(shù)之間有一一對(duì)應(yīng)的關(guān)系。如果A和B是可數(shù)的，則A∪B也是可數(shù)的。如果存在一對(duì)一函數(shù)f從A到B和一對(duì)一函數(shù)g從B到A，那么A和B之間是一一對(duì)應(yīng)的。求和公式：a+ar+ar2+ar3+...+arn=(arn+1-a)/(r-1)1+2+3+...+n=n(n+1)/21+22+32+...+n2=n(n+1)(2n+1)/61+23+33+...+n3=n2(n+1)2/4矩陣普通矩陣和、減、乘積，0-1矩陣還可以∧、∨、⊙（和相乘類似，用∨代替+，用∧代替×）九、關(guān)系關(guān)系及其性質(zhì)設(shè)A和B是集合，從A到B的二元關(guān)系是A×B的子集。一個(gè)從A到B的二元關(guān)系是集合R，第一個(gè)元素取自A，第二個(gè)元素取自B，當(dāng)(a,b)屬于R時(shí)寫作aRb。集合A上的關(guān)系是A到A的關(guān)系，有n個(gè)元素就有n2個(gè)有序?qū)?，n2個(gè)有序?qū)陀?n2個(gè)關(guān)系?？紤]集合A到A的關(guān)系R：任意a∈A都有（a，a）∈R，則R是集合A上的自反關(guān)系。任意a，b∈A，若（a，b）∈R都有（b，a）∈R，則R是對(duì)稱關(guān)系。任意a，b∈A，若（a，b）∈R且（b，a）∈R一定有a=b，則R是反對(duì)稱關(guān)系。任意a，b，c∈A，若（a，b）∈R且（b，c）∈R一定有（a，c）∈R，則R是傳遞關(guān)系。若R是A到B的關(guān)系，S是B到C的關(guān)系，R與S的合成RοS是有序數(shù)對(duì)（a，c）。其中a∈A，c∈C，且存在一個(gè)b∈B使得（a，b）∈R，（b，c）∈S。二元關(guān)系的5種復(fù)合要會(huì)翻譯成漢語。

關(guān)系的表示0-1矩陣法：A有n個(gè)元素，B有m個(gè)元素，用一個(gè)n×m的矩陣M表示，m=1Rij表示有關(guān)系。自反關(guān)系的0-1矩陣主對(duì)角線全為1；對(duì)稱關(guān)系的0-1矩陣是對(duì)稱陣；反對(duì)稱關(guān)系的0-1矩陣關(guān)于主對(duì)角線反對(duì)稱。M=M∨M，M=M∧M，Mο=M⊙M。R1R1∪R2R1R2R1∩R2R1R2R2R1R2有向圖法：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)系的閉包自反閉包：R∪Δ，其中Δ={（a，a）|a∈A}對(duì)稱閉包：R并R-1，其中R-1={（b,a）|（a，b）∈R}傳遞閉包：R矩陣傳遞閉包=M∨M[2]∨M[3]...∨M[n]，了解沃舍爾算法RRRR等價(jià)關(guān)系：自反、對(duì)稱且傳遞的關(guān)系集合A的元素a在R上的等價(jià)類[a]={s|(a,s)∈R∧s∈A}。如A={1,2,3,4,5,6,7,8}，R={(a,b)|a=b(mod3)}的等價(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，≤）是全序集，但（Z+，|）不是，因?yàn)橛?和7是不可比的。良序集：如果是全序集，而且S的每個(gè)非空機(jī)子都有一個(gè)最小元素，則為良序集。哈塞圖：對(duì)有窮偏序集，去掉環(huán)，去掉所有由傳遞性可以得到的邊，排列所有的邊使得方向向上。極大元極小元：圖中的頂元素和底元素，可能有多個(gè)最大元最小元：只有唯一的一個(gè)，比其他都＞或＜上界下界：只有唯一的一個(gè)，比其他都≥或≤格：每對(duì)元素都有最小上界和最大下界十、圖圖的概念簡(jiǎn)單圖：每對(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=Σdeg(v)。無向圖有偶數(shù)個(gè)度為奇數(shù)的點(diǎn)，因?yàn)?m=Σdeg(V)+Σdeg(V)。ji有向圖中，點(diǎn)v的入度為deg-(v)，出度為deg+(v)，且deg-(v)=deg+(v)=邊數(shù)。有向圖忽略邊的方向后得到的圖叫做基本無向圖，它們有相同的邊數(shù)。會(huì)畫完全圖K、圈圖C、輪圖W。nnn二分圖，將點(diǎn)分成2部分，每條邊都連著一部分和另一部分。用著色法判讀是否是二分圖。完全二分圖K是邊最多的二分圖。n,m圖的表示鄰接表：無向簡(jiǎn)單圖包括頂點(diǎn)和相鄰頂點(diǎn)，不太好表示無向多重圖因?yàn)檫叺臄?shù)量不好表示。有向圖包括起點(diǎn)和終點(diǎn)。鄰接矩陣：①無向簡(jiǎn)單圖按頂點(diǎn)排列，如果v和v之間相鄰則a是1，否ijij則是0。②無向多重圖這時(shí)a是v和v之間的邊數(shù)?？芍獰o向圖的鄰接矩陣都jiji是對(duì)稱陣。③有向簡(jiǎn)單圖也按照頂點(diǎn)排列，如果{v，v}是邊則a是1，否則是ijij0。④有向多重圖也按頂點(diǎn)排列，只不過a是{v，v}之間的邊數(shù)。jiji關(guān)聯(lián)矩陣：將圖G按v行e列排列，如果v和e關(guān)聯(lián)，則a是1，否則是0。ijij圖的同構(gòu)：簡(jiǎn)單圖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是否是保持邊的。圖的連通性簡(jiǎn)單圖中，用x=u，x1...x=v來表示一條通路，若u=v且路長(zhǎng)n度大于0，則0是回路，如果不包含重復(fù)的邊，則這條通路是簡(jiǎn)單的。無向圖中每對(duì)不同頂點(diǎn)之間都有通路則這個(gè)圖是連通的，割點(diǎn)（關(guān)節(jié)點(diǎn)）、割邊（橋）去掉后就會(huì)使圖變得不連通，不含割點(diǎn)的圖叫做不可割圖。有向圖中，任意一對(duì)頂點(diǎn)a和b，都有從a到b以及從b到a的通路，則這個(gè)有向圖是強(qiáng)連通的，如果只是基本無向圖能保持聯(lián)通則叫做弱聯(lián)通的，連通分支。會(huì)求強(qiáng)通路與同構(gòu)：可以用長(zhǎng)度為k≥2的簡(jiǎn)單回路的存在來性證不同構(gòu)或者是潛在的同構(gòu)映射f，同樣找到f后還要驗(yàn)證f保持邊。

圖G（允許是有向和無向、多重邊和環(huán)）的v到v的長(zhǎng)度為n的不同通路的ji條數(shù)等于An[i,j]，A是G的鄰接矩陣。歐拉回路與哈密頓回路歐拉回路：包含G的每一條邊的簡(jiǎn)單回路。歐拉通路：包含G的每一條邊的簡(jiǎn)單通路。含有至少2個(gè)頂點(diǎn)的連通多重圖有歐拉回路當(dāng)僅當(dāng)它的每個(gè)頂點(diǎn)度都為偶數(shù)，有歐拉通路但無歐拉回路當(dāng)僅當(dāng)它恰有2個(gè)度為奇數(shù)的頂點(diǎn)。哈密頓回路：包含G的每一個(gè)頂點(diǎn)恰好一次的簡(jiǎn)單回路。哈密頓通路：包含G的每一個(gè)頂點(diǎn)恰好一次的簡(jiǎn)單通路。含有至少3個(gè)頂點(diǎn)的簡(jiǎn)單圖，若每個(gè)頂點(diǎn)的度都≥(n/2)，或者每一對(duì)不相鄰的頂點(diǎn)u和v都有deg(u)+deg(v)≥n，則有哈密頓回路。最短通路算法：迪克斯特拉算法和旅行商問題（枚舉）平面圖歐拉公式：G是有e條邊和v個(gè)頂點(diǎn)的平面連通簡(jiǎn)單圖，r是G的平面圖表示中的面數(shù)，則有r=e-v+2。根據(jù)上述條件，有3個(gè)推論，可以用來判斷不是平面圖：推論1：若v≥3，則e≤3v-6。推論2：G中有