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

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

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

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

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

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

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

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

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

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

約束變元和自由變元：在合式公式"x A和 $x A中，稱x為指導(dǎo)變項，稱A為相應(yīng)量詞的轄域，x稱為約束變元，x的出現(xiàn)稱為約束出現(xiàn)，A中其他出現(xiàn)稱為自由出現(xiàn)（自由變元）。

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

前束范式：設(shè)A為一謂詞公式，若A具有如下形式Q1x1Q2x2Qk…xkB，稱A為前束范式。

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

笛卡爾積：設(shè)A和B為集合，用A中元素為第一元素，用B中元素為第二元素構(gòu)成有序?qū)M成的集合稱為A和B的笛卡爾積，記為A×B。

二元關(guān)系：如果一個集合R為空集或者它的元素都是有序?qū)?，則稱集合R是一個二元關(guān)系。

特殊關(guān)系：（1）、空關(guān)系：Φ （2）全域關(guān)系：EA={<x, y> | x∈A ∧ y∈A }= A×A

（3）恒等關(guān)系：IA={<x, x> | x∈A}

（4）小于等于關(guān)系：LA={<x, y>| x, y∈A∧x≤y∈A },A í R

（5）整除關(guān)系： Rí ={<x, y>| x，y∈ψ ∧ x í y} ,ψ是集合族

二元關(guān)系的運算：設(shè)R是二元關(guān)系，

（1）R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域domR = { x | $y（<x , y>∈R）}

（2）R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域ranR = {y | $x（<x , y>∈R）}

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

二元關(guān)系的性質(zhì)：自反性，反自反性，對稱性，反對稱性，傳遞性。

等價關(guān)系：如果集合A上的二元關(guān)系R是自反的，對稱的和傳遞的，那么稱R是等價關(guān)系。設(shè)R是A上的等價關(guān)系，x , y是A的任意元素，記作x～y。

等價類：設(shè)R是A上的等價關(guān)系，對任意的"x∈A，令[x]R={ y | y∈A ∧ x R y }，稱[x]R為x關(guān)于R的等價類。

偏序關(guān)系：設(shè)R是集合A上的二元關(guān)系，如果R是自反的，反對稱的和傳遞的，那么稱R為A上的偏序，記作≤；稱序偶< A ,R >為偏序集合。

函數(shù)的性質(zhì)：設(shè)f: A?B，

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

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

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

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

(1) V1Ф稱為頂點集，其元素稱為頂點或結(jié)點。

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

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

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

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

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

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

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

基圖：將有向圖變?yōu)闊o向圖得到的新圖，稱為有向圖的基圖。

圖的同構(gòu)：在用圖形表示圖時，由于頂點的位置不同，邊的形狀不同，同一個事物之間的關(guān)系可以用不同的圖表示，這樣的圖稱為圖同構(gòu)。

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

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

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

哈密頓圖：經(jīng)過圖中每個頂點一次且僅一次的通路（回路），稱為哈密頓通路（回路），存在哈密頓回路的圖稱為哈密頓圖。

平面圖：一個圖G如果能以這樣的方式畫在平面上：出定點處外沒有變交叉出現(xiàn)，則稱G為平面圖。畫出的沒有邊交叉出現(xiàn)的圖稱為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為森林。在無向圖中，懸掛頂點稱為樹葉，度數(shù)大于或等于2的頂點稱為分支點。

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

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

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

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

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

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

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

最佳前綴碼：利用Huffman算法求最優(yōu)2叉樹，由最優(yōu)2叉樹產(chǎn)生的前綴碼稱為最佳前綴碼，用最佳前綴碼傳輸對應(yīng)的各符號能使傳輸?shù)亩M制數(shù)位最省。

蘊含式推理

E1

┐┐p<=>P

E12

R∨(P∧┐P)<=>R

E2

P∧Q<=>Q∧P

E13

R ∧(P∨┐P)<=>R

E3

P∨Q<=>Q∨P

E14

R∨(P∨┐P)<=>T

E4

(P∧Q)∧R<=>P∧(Q∧R)

E15

R∧(P∧┐P)<=>F

E5

(P∨Q)∨R<=>P∨(Q∨R)

E16

P→Q<=>┐P∨Q

E6

P∧(Q∨R)<=>(P∧Q)∨(P∧R)

E17

┐(P→Q)<=> P∧┐Q

E7

P∨(Q∧R)<=>(P∨Q)∧(P∨R)

E18

P→Q<=>┐Q→┐P

E8

┐(P∧Q)<=> ┐P∨┐Q

E19

P→(Q→R)<=>(P∧Q)→R

E9

┐(P∨Q)<=> ┐P∧┐Q

E20

PDQ<=>(P→Q)∧(Q→P)

E10

P∨P<=>P

E21

PDQ<=>(P∧Q)∨(┐P∧┐Q)

E11

P∧P<=>P

E22

┐(PDQ) <=> PD┐Q

等值公式表

P∧Q=>P

化簡式

P∧Q=>Q

化簡式

P=>P∨Q

附加式

┐P=>P→Q

變形附加式

Q=>P→Q

變形附加式

┐(P→Q)=>P

變形簡化式

┐(P→Q)=>┐Q

變形簡化式

p∧(P→Q)=>Q

假言推論

┐Q∧(P→Q)=>┐P

拒取式

┐p∧(P∨Q)=>Q

析取三段式

(P→Q) ∧(Q→R)=>P→R

條件三段式

(PDQ) ∧(QDR)=>PDR

雙條件三段式

(P→Q)∧(R→S)∧(P∧R)=>Q→S

合取構(gòu)造二難

(P→Q)∧(R→S)∧(P∨R)=>Q∨S

析取構(gòu)造二難

P→Q=>(P∨R) →(Q∨R)

前后附加式

P→Q=>(P∧R) →(Q∧R)

前后附加式

E23

(

x)((Ax)∨(Bx))<=>(

x)(Ax)∨(

x)(Bx)

E30

(

x)(Ax) →B<=>(

x) ((Ax)→B)

E24

(

x)((Ax)∧(Bx))<=>(

x)(Ax)∧(

x)(Bx)

E31

(

x)(Ax) →B<=>(

x) ((Ax)→B)

E25

┐(

x)(Ax)<=>(

x)┐(Ax)

E32

A→(

x)(Bx) <=>(

x) (A→(Bx))

E26

┐(

x)(Ax)<=>(

x)┐(Ax)

E33

A→(

x)(Bx) <=>(

x) (A→(Bx))

E27

(

x)(A∨(Bx))<=>A∨(

x)(Bx)

I17

(

x)(Ax)∨(

x)(Bx) =>(

x)((Ax)∨(Bx))

E28

(

x)(A∧(Bx))<=>A∧(

x)(Bx)

I18

(

x)((Ax)∧(Bx)) =>(

x)(Ax)∧(

x)(Bx)

E29

(

x)((Ax)→(Bx))<=>(

x)(Ax)→(

x)(Bx)

I19

(

x)(Ax)→(

x)(Bx) =>(

x)((Ax)→(Bx))

集合恒等式：P61

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

結(jié)合律：(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

二元關(guān)系的運算：

設(shè)F,G,H是任意的關(guān)系，

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

（3）（ F ? G ) ? H =　F ?(G ? H ) （4）（ F ? G ) - 1 =G -1 ? F -1

設(shè)R是A上的關(guān)系（冪運算）

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

圖的矩陣表示：

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

（2）有向圖的關(guān)聯(lián)矩陣：設(shè)無向圖D=<V,E>, V={v1,v2,…,vn}, E={e1,e2,…,em}，

1, vi是ej的始點

mij = 0, vi與ej不關(guān)聯(lián)

-1，vi是ej的終點

則稱（ mij ）n′ m為D的關(guān)聯(lián)矩陣。記為M(D) 。