離散數(shù)學知識點整理2163

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

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

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