離散數學部分概念和公式總結(考試專用)

命題：稱能判斷真假的陳述句為命題。

命題公式：若在複合命題中，p、q、r等不僅可以代表命題常項，還可以代表命題變項，這樣的複合命題形式稱為命題公式。

命題的賦值：設A為一命題公式，p ,p ,…,p 為出現在A中的所有命題變項。給p ,p ,…,p 指定一組真值，稱為對A的一個賦值或解釋。若指定的一組值使A的值為真，則稱成真賦值。

真值表：含n（n≥1）個命題變項的命題公式，共有2^n組賦值。將命題公式A在所有賦值下的取值情況列成表，稱為A的真值表。

命題公式的類型：（1）若A在它的各種賦值下均取值為真，則稱A為重言式或永真式。

（2）若A在它的賦值下取值均為假，則稱A為矛盾式或永假式。

（3）若A至少存在一組賦值是成真賦值，則A是可滿足式。

主析取範式：設命題公式A中含n個命題變項，如果A得析取範式中的簡單合取式全是極小項，則稱該析取範式為A的主析取範式。

主合取範式：設命題公式A中含n個命題變項，如果A得析取範式中的簡單合析式全是極大項，則稱該析取範式為A的主析取範式。

命題的等值式：設A、B為兩命題公式，若等價式A↔B是重言式，則稱A與B是等值的，記作A<=>B。

約束變元和自由變元：在合式公式"x A和 $x A中，稱x為指導變項，稱A為相應量詞的轄域，x稱為約束變元，x的出現稱為約束出現，A中其他出現稱為自由出現（自由變元）。

一階邏輯等值式：設A，B是一階邏輯中任意的兩公式，若A↔B為邏輯有效式，則稱A與B是等值的，記作A<=>B，稱A<=>B為等值式。

前束範式：設A為一謂詞公式，若A具有如下形式Q1x1Q2x2Qk…xkB，稱A為前束範式。

集合的基本運算：並、 交、差、相對補和對稱差運算。

笛卡爾積：設A和B為集合，用A中元素為第一元素，用B中元素為第二元素構成有序對組成的集合稱為A和B的笛卡爾積，記為A×B。

二元關係：如果一個集合R為空集或者它的元素都是有序對，則稱集合R是一個二元關係。

特殊關係：（1）、空關係：Φ （2）全域關係：EA={<x, y> | x∈A ∧ y∈A }= A×A

（3）恆等關係：IA={<x, x> | x∈A}

（4）小於等於關係：LA={<x, y>| x, y∈A∧x≤y∈A },A Í R

（5）整除關係： RÍ ={<x, y>| x，y∈ψ ∧ x Í y} ,ψ是集合族

二元關係的運算：設R是二元關係，

（1）R中所有有序對的第一元素構成的集合稱為R的定義域domR = { x | $y（<x , y>∈R）}

（2）R中所有有序對的第二元素構成的集合稱為R的值域ranR = {y | $x（<x , y>∈R）}

（3）R的定義域和值域的並集稱為R的域fldR= domR ∪ranR

二元關係的性質：自反性，反自反性，對稱性，反對稱性，傳遞性。

等價關係：如果集合A上的二元關係R是自反的，對稱的和傳遞的，那麼稱R是等價關系。設R是A上的等價關係，x , y是A的任意元素，記作x～y。

等價類：設R是A上的等價關係，對任意的"x∈A，令[x]R={ y | y∈A ∧ x R y }，稱[x]R為x關於R的等價類。

偏序關係：設R是集合A上的二元關係，如果R是自反的，反對稱的和傳遞的，那麼稱R為A上的偏序，記作≤；稱序偶< A ,R >為偏序集合。

函數的性質：設f: A®B，

（1）若ranf = B，則稱f 是滿射（到上）的。

（2）若 "yÎ ranf 都存在唯一的x ÎA 使得f(x)=y,則稱f 是單射（— —）的。

（3）若f 既是滿射又是單射的，則稱f 是雙射（— —到上）的。

無向圖：是一個有序的二元組<V, E>，記作G，其中：

(1) V¹Ф稱為頂點集，其元素稱為頂點或結點。

(2) E為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。

有向圖：是一個有序的二元組<V,E>,記作D,其中

(1) V同無向圖。 (2) E為邊集，它是笛卡爾積V´V的多重子集，其元素稱為有向邊。

設G=<V,E>是一個無向圖或有向圖。

有限圖：若V, E是有限集，則稱G為有限圖。

n階圖：若| V |=n，稱G為n階圖。

零圖：若| E |=0，稱G為零圖,當| V |=1時，稱G為平凡圖。

基圖：將有向圖變為無向圖得到的新圖，稱為有向圖的基圖。

圖的同構：在用圖形表示圖時，由於頂點的位置不同，邊的形狀不同，同一個事物之間的關係可以用不同的圖表示，這樣的圖稱為圖同構。

帶權圖：在處理有關圖的實際問題時，往往有值的存在，一般這個值成為權值，帶權值的圖稱為帶權圖或賦權圖。

連通圖：若無向圖是平凡圖，或圖中任意兩個頂點都是連通的，則稱G是連通圖。否則稱為非連通圖。設D是一個有向圖，如果D的基圖是連通圖，則稱D是弱連通圖，若D中任意兩個頂點至少一個可達另一個，則稱D是單向連通圖。若D中任意兩個頂點是相互可達的，則稱D是強連通圖。

歐拉圖：通過圖中所有邊一次且僅一次並且通過所有定點的通路（迴路），稱為歐拉通路（迴路）。存在歐拉迴路的圖稱為歐拉圖。

哈密頓圖：經過圖中每個頂點一次且僅一次的通路（迴路），稱為哈密頓通路（迴路），存在哈密頓迴路的圖稱為哈密頓圖。

平面圖：一個圖G如果能以這樣的方式畫在平面上：出定點處外沒有變交叉出現，則稱G為平面圖。畫出的沒有邊交叉出現的圖稱為G的一個平面嵌入。

二部圖：若無向圖G=〈V, E〉的頂點集合V可以劃分成兩個子集V1和V 2（V1∩V2 =f ），使G中的任何一條邊的兩個端點分別屬於V1和V2，則稱G為二部圖（偶圖）。二部圖可記為G = < V1, V 2 , E >, V1和V 2稱為互補頂點子集。

樹的定義：連通無迴路的無向圖稱為無向樹，簡稱樹，常用T表示樹。平凡圖稱為平凡樹。若無向圖G至少有兩個連通分支，每個連通都是樹，則稱G為森林。在無向圖中，懸掛頂點稱為樹葉，度數大於或等於2的頂點稱為分支點。

樹的性質：性質1、設G=<V,E>是n階m條邊的無向圖，則下面各命題是等價的：

（1）G是樹 （2）G中任意兩個頂點之間存在唯一的路徑 （3）G中無迴路且m=n-1.

（4）G是連通的且m=n-1. （5）G是連通的且G中任何邊均為橋。 （6）G中沒有迴路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈。

性質2、設T是n階非平凡的無向樹，則T中至少有兩片樹葉。

證：設T有x片樹葉，由握手定理及性質1可知，2(n-1)=∑d(vi)≥x+2(n-x)由上式解出x≥2.

最小生成樹：設T是無向圖G的子圖並且為樹，則稱T為G的樹。若T是G的樹且為生成子圖，則稱T是G的生成樹。設T是G的生成樹。e∈E(G)，若e∈E(T)，則稱e為T的樹枝，否則稱e為T的弦。並稱導出子圖G[E(G)-E(T)]為T的余樹，記作T。

最優二元樹：設2叉樹T有t片樹葉v1,v2,…,vt，權分別為w1,w2,…,wt，稱W(t)=wil(vi)為T的權，其中l(vi)是vi的層數。在所有有t片樹葉，帶權w1,w2,…,wt的2叉樹中，權最小的2叉樹稱為最優2叉樹。

最佳前綴碼：利用Huffman算法求最優2叉樹，由最優2叉樹產生的前綴碼稱為最佳前綴碼，用最佳前綴碼傳輸對應的各符號能使傳輸的二進位數位最省。

蘊含式推理

等值公式表

集合恆等式：P61

冪等律：A∪A=A ；A∩A=A

結合律：(A∪B)∪C=A∪(B∪C) ；(A∩B)∩C=A∩(B∩C)

交換律：A∪B=B∪A ；A∩B=B∩A

分配律：A∪(B∩C)=(A∪B)∩(A∪C) ；A∩(B∪C)=(A∩B)∪(A∩C)

同一律：A∪f =A ；A∩E=A

零 律：A∪E =A ；A∩f = f

排中律：A∪~A=E

矛盾律：A∩~A =ff

吸收律：A∩(A∪B)=A；A∪ (A∩B)=A

德摩根定律：A-(B∪C)=(A-B)∩(A-C)；A-(B∩C)=(A-B)∪(A-C)

~(B∪C)= ~B∩~C；~(B∩C)= ~B∪~C；~f=E；~E=f

雙重否定律：~（~A)=A

二元關係的運算：

設F,G,H是任意的關係，

（1）（F -¹) -¹= F （2）dom(F -¹)=ranF ；ran (F -¹)=domF

（3）（ F ◦ G ) ◦ H =　F ◦(G ◦ H ) （4）（ F ◦ G ) - ¹ =G -¹ ◦ F -¹

設R是A上的關係（冪運算）

（1）Rº = {<x，x>| x∈A} （2）R ^n = R ^(n-1) ◦ R，n≥1 （3）R ◦ Rº = Rº ◦ R = R

圖的矩陣表示：

（1）無向圖的關聯矩陣：設無向圖G=<V,E>, V={v1,v2,…,vn}, E={e1,e2,…,em}，令mij為頂點vi與邊的關聯次數，則稱（ mij ）n´ m為G的關聯矩陣。記為M(G)。

（2）有向圖的關聯矩陣：設無向圖D=<V,E>, V={v1,v2,…,vn}, E={e1,e2,…,em}，

1, vi是ej的始點

mij = 0, vi與ej不關聯

-1，vi是ej的終點

則稱（ mij ）n´ m為D的關聯矩陣。記為M(D) 。