命題：稱能判斷真假的陳述句為命題。
命題公式：若在復合命題中，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為兩命題公式，若等價式ab是重言式，則稱a與b是等值的，記作a<=>b。
約束變元和自由變元：在合式公式x a和 x a中，稱x為指導變項，稱a為相應量詞的轄域，x稱為約束變元，x的出現稱為約束出現，a中其他出現稱為自由出現（自由變元）。
一階邏輯等值式：設a，b是一階邏輯中任意的兩公式，若ab為邏輯有效式，則稱a與b是等值的，記作a<=>b，稱a<=>b為等值式。
前束正規化：設a為一謂詞公式，若a具有如下形式q1x1q2x2qk…xkb，稱a為前束正規化。
集合的基本運算：並、 交、差、相對補和對稱差運算。
笛卡爾積：設a和b為集合，用a中元素為第一元素，用b中元素為第二元素構成有序對組成的集合稱為a和b的笛卡爾積，記為a×b。
二元關係：如果乙個集合r為空集或者它的元素都是有序對，則稱集合r是乙個二元關係。
特殊關係：（1）、空關係：φ （2）全域關係：ea== a×a
（3）恒等關係：ia=
（4）小於等於關係：la=,a r
（5）整除關係： r = ,ψ是集合族
二元關係的運算：設r是二元關係，
（1）r中所有有序對的第一元素構成的集合稱為r的定義域domr =
（2）r中所有有序對的第二元素構成的集合稱為r的值域ranr =
（3）r的定義域和值域的並集稱為r的域fldr= domr ∪ranr
二元關係的性質：自反性，反自反性，對稱性，反對稱性，傳遞性。
等價關係：如果集合a上的二元關係r是自反的，對稱的和傳遞的，那麼稱r是等價關係。設r是a上的等價關係，x , y是a的任意元素，記作x～y。
等價類：設r是a上的等價關係，對任意的x∈a，令[x]r=，稱[x]r為x關於r的等價類。
偏序關係：設r是集合a上的二元關係，如果r是自反的，反對稱的和傳遞的，那麼稱r為a上的偏序，記作≤；稱序偶< a ,r >為偏序集合。
函式的性質：設f: ab，
（1）若ranf = b，則稱f 是滿射（到上）的。
（2）若 y ranf 都存在唯一的x a 使得f(x)=y,則稱f 是單射（— —）的。
（3）若f 既是滿射又是單射的，則稱f 是雙射（— —到上）的。
無向圖：是乙個有序的二元組，記作g，其中：
(1) vф稱為頂點集，其元素稱為頂點或結點。
(2) e為邊集，它是無序積v&v的多重子集，其元素稱為無向邊，簡稱邊。
有向圖：是乙個有序的二元組,記作d,其中
(1) v同無向圖。 (2) e為邊集，它是笛卡爾積vv的多重子集，其元素稱為有向邊。
設g=是乙個無向圖或有向圖。
有限圖：若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 = ），使g中的任何一條邊的兩個端點分別屬於v1和v2，則稱g為二部圖（偶圖）。二部圖可記為g = < v1, v 2 , e >, v1和v 2稱為互補頂點子集。
樹的定義：連通無迴路的無向圖稱為無向樹，簡稱樹，常用t表示樹。平凡圖稱為平凡樹。
若無向圖g至少有兩個連通分支，每個連通都是樹，則稱g為森林。在無向圖中，懸掛頂點稱為樹葉，度數大於或等於2的頂點稱為分支點。
樹的性質：性質1、設g=是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)
學習離散數學總結
學習離散數學的心得體會 姓名 學號 1 班級 計算機 離散數學，對絕大多數學生來說應該都會是一門十分困難的課程，當然也包括我在內。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。在還沒有接觸的時候，看見課本就想退縮，心想 這是什麼課程啊，這叫數學嗎，這些符號都是之前沒有...
離散數學考題總結
第1章主要介紹集合論的基本概念和結論，集合的運算及其性質，以及利用運算性質進行集合表示式的化簡和集合恒等式的證明等內容 考試經常涉及到的題型有以下4個 集合與集合之間的包含 元素與集合之間的屬於關係 冪集的計算 集合之間的運算 利用集合運算性質證明集合恒等式 大家對於集合與集合 元素和集合之間的關係...
離散數學圖論課後總結
第8章圖論 例1 下面哪些數的序列,可能是乙個圖的度數序列?如果可能,請試畫出它的圖.哪些可能不是簡單圖?a 1,2,3,4,5 b 2,2,2,2,2 c 1,2,3,2,4 d 1,1,1,1,4 e 1,2,2,4,5 解 a 不是,因為有三個數字是奇數.b c d 是.e 不是簡單圖,因為它...