基本等值式

1.雙重否定律 A ? ┐┐A

2.冪等律 A ? A∨A, A ? A∧A

3.交換律 A∨B ? B∨A， A∧B ? B∧A

4.結(jié)合律 (A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C)

5.分配律 A∨(B∧C) ? (A∨B)∧(A∨C) （∨對(duì)∧的分配律）
A∧(B∨C) ? (A∧B)∨(A∧C) （∧對(duì)∨的分配律）

6.德·摩根律 ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B

7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A

8.零律 A∨1 ? 1,A∧0 ? 0

9.同一律 A∨0 ? A，A∧1 ? A

10.排中律 A∨┐A ? 1

11.矛盾律 A∧┐A ? 0

12.蘊(yùn)涵等值式 A→B ? ┐A∨B

13.等價(jià)等值式 A?B ? (A→B)∧(B→A)

14.假言易位 A→B ? ┐B→┐A

15.等價(jià)否定等值式 A?B ? ┐A?┐B

16.歸謬論 (A→B)∧(A→┐B) ? ┐A

求給定公式范式的步驟

(1)消去聯(lián)結(jié)詞→、?(若存在)。

(2)否定號(hào)的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。

(3)利用分配律：利用∧對(duì)∨的分配律求析取范式，∨對(duì)∧的分配律求合取范式。

推理定律--重言蘊(yùn)含式

(1) A T (A∨B) 附加律

(2) (A∧B) T A 化簡律

(3) (A→B)∧A T B 假言推理

(4) (A→B)∧┐B T ┐A 拒取式

(5) (A∨B)∧┐B T A 析取三段論

(6) (A→B) ∧ (B→C) T (A→C) 假言三段論

(7) (A?B) ∧ (B?C) T (A ? C) 等價(jià)三段論

(8) (A→B)∧(C→D)∧(A∨C) T(B∨D) 構(gòu)造性二難
(A→B)∧(┐A→B)∧(A∨┐A) T B 構(gòu)造性二難(特殊形式)

(9)(A→B)∧(C→D)∧(┐B∨┐D) T(┐A∨┐C)破壞性二難

設(shè)個(gè)體域?yàn)橛邢藜疍={a1,a2,…,an},則有

（1）"xA(x) ? A(a1)∧A(a2)∧…∧A(an)

（2）$xA(x) ? A(a1)∨A(a2)∨…∨A(an)

設(shè)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，則

（1）┐"xA(x) ? $x┐A(x)

（2）┐$xA(x) ? "x┐A(x)

設(shè)A(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B中不含x的出現(xiàn)，則

（1） "x(A(x)∨B) ? "xA(x)∨B

"x(A(x)∧B) ? "xA(x)∧B

"x(A(x)→B) ? $xA(x)→B

"x(B→A(x)) ? B→"xA(x)

（2） $x(A(x)∨B) ? $xA(x)∨B

$x(A(x)∧B) ? $xA(x)∧B

$x(A(x)→B) ? "xA(x)→B

$x(B→A(x)) ? B→$xA(x)

設(shè)A(x)，B(x)是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，則

（1）"x(A(x)∧B(x)) ? "xA(x)∧"xB(x)

（2）$x(A(x)∨B(x)) ? $xA(x)∨ $xB(x)

全稱量詞“"”對(duì)“∨”無分配律。

存在量詞“$”對(duì)“∧”無分配律。

UI規(guī)則。

UG規(guī)則。

EG規(guī)則。

EI規(guī)則。

A∪B＝{x|x∈A∨x∈B }  、

A∩B＝{x|x∈A∧x∈B }

A－B＝{x|x∈A∧x?B }

冪集 P(A)＝{x | xíA}

對(duì)稱差集 A?B＝(A－B)∪(B－A)

A?B＝(A∪B)－(A∩B)

絕對(duì)補(bǔ)集 ～A＝{x|x ? A }

廣義并 ∪A＝{x | $z(z∈A∧x∈z)} 廣義交 ∩A＝{x | "z(z∈A→x∈z)}

設(shè) A＝{{a,b,c},{a,c,d},{a,e,f}} B＝{{a}} C＝{a,{c,d}}

則 ∪A＝{a,b,c,d,e,f}

 ∪B＝{a}

 ∪C＝a∪{c,d}

∪?＝?

∩A＝{a}

∩B＝{a}

∩C＝a∩{c,d}

集合恒等式

冪等律 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∪?＝A A∩E＝A

零律  A∪E＝E A∩?＝?

排中律  A∪～A＝E

矛盾律  A∩～A＝?

吸收律 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

 ～?＝E ～E＝? 

雙重否定律 ～(～A)＝A

集合運(yùn)算性質(zhì)的一些重要結(jié)果

A∩BíA，A∩BíB  

AíA∪B，BíA∪B  

A－BíA 

A－B＝A∩～B 

A∪B＝B ? AíB ? A∩B＝A ? A－B＝?

A?B＝B?A 

(A?B)?C＝A?(B?C) 

A??＝A  

A?A＝?     

A?B＝A?C T B＝C

對(duì)偶(dual)式：一個(gè)集合表達(dá)式，如果只含有∩、∪、～、?、E、＝、í、ê，那么同時(shí)把∩與∪互換，把?與E互換，把í與ê互換，得到式子稱為原式的對(duì)偶式。

有序?qū)?lt;x,y>具有以下性質(zhì)： （1）當(dāng)x≠y時(shí)，<x,y>≠<y,x>。

（2）<x,y>＝<u,v>的充分必要條件是x＝u且y＝v。

笛卡兒積的符號(hào)化表示為 A×B＝{<x,y>|x∈A∧y∈B}

如果|A|=m,|B|=n,則|A×B|=mn。

笛卡兒積的運(yùn)算性質(zhì)

(1)對(duì)任意集合A，根據(jù)定義有

A×?＝?, ?×A＝?

(2)一般的說，笛卡兒積運(yùn)算不滿足交換律，即

A×B≠B×A (當(dāng) A≠? ∧ B≠? ∧ A≠B 時(shí))

(3)笛卡兒積運(yùn)算不滿足結(jié)合律，即

(A×B)×C≠A×(B×C) (當(dāng) A≠? ∧ B≠? ∧ C≠? 時(shí))

(4)笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即

A×(B∪C)=(A×B)∪(A×C) (B∪C)×A=(B×A)∪(C×A)
A×(B∩C)=(A×B)∩(A×C) (B∩C)×A=(B×A)∩(C×A)

(5)AíC ∧ BíD T A×B í C×D

常用的關(guān)系

對(duì)任意集合A，定義

全域關(guān)系 EA={<x,y>|x∈A∧y∈A}=A×A

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

空關(guān)系 ?

小于或等于關(guān)系：LA={<x,y>|x,y∈A∧x≤y}，其中 AíR。

整除關(guān)系：DB={<x,y>|x,y∈B∧x整除y}，其中 AíZ* ，Z*是非零整數(shù)集

包含關(guān)系：Rí＝{<x,y>|x,y∈A∧xíy}，其中 A是集合族。

關(guān)系矩陣和關(guān)系圖

設(shè) A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，
則R的關(guān)系矩陣和關(guān)系圖分別是

定義域 dom R ＝ {x | $y(<x,y>∈R )}

值域 ran R＝{y | $ x(<x,y>∈R)}

域 fld R＝dom R ∪ ran R

例 求R={<1,2>,<1,3>,<2,4>,<4,3>}的定義域、值域和域。

解答 dom R＝{1,2,4} ran R＝{2,3,4} fld R＝{1,2,3,4}

逆 R-1＝{<x,y>|<y,x>∈R}

右復(fù)合 F°G＝{<x,y> | $t(<x,t>∈F∧<t,y>∈G)}

限制 R↑A={<x,y>|xRy∧x∈A}

像 R[A]=ran(R↑A)

例 設(shè)R＝{<1,2>，<1,3>，<2,2>，<2,4>，<3,2>}

R↑{1}＝{<1,2>，<1,3>} R↑? ＝? R↑{2,3}＝{<2,2>，<2,4>}，<3,2>}

R[{1}]＝{2,3} R[?] ＝? R[{3}]＝{2}

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

(1)(F-1)-1＝F

(2)dom F-1＝ran F，ran F-1＝dom F

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

(1)(F°G)°H＝F°(G°H)

(2)(F°G)-1＝G-1 ° F-1

設(shè)R為A上的關(guān)系，則R ° IA＝IA° R＝R

設(shè)F，G，H是任意的關(guān)系，則
(1) F°(G∪H)＝F°G∪F°H
(2) (G∪H)°F＝G°F∪H°F
(3) F°(G∩H)íF°G∩F°H
(4) (G∩H)°FíG°F∩H°F

設(shè)F為關(guān)系，A,B為集合，則

(1) F↑(A∪B)＝F↑A∪F↑B

(2) F[A∪B]＝F[A]∪F[B]

(3) F↑(A∩B)＝F↑A∩F↑B

(4) F[A∩B]íF[A]∩F[B]

關(guān)系的冪運(yùn)算

設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：

（1） R0＝{<x,x>|x∈A}＝IA

（2） Rn+1＝Rn ° R

冪運(yùn)算的性質(zhì)

設(shè)A為n元集，R是A上的關(guān)系，則存在自然數(shù)s和t,使得Rs=Rt。

設(shè)R是A上的關(guān)系，m,n∈N，則

(1)Rm ° Rn＝Rm+n (2)(Rm)n＝Rmn

設(shè)R是A上的關(guān)系，若存在自然數(shù)s,t(s<t)使得Rs=Rt，則

(1) 對(duì)任何k∈N有 Rs+k=Rt+k

(2) 對(duì)任何k,i∈N有 Rs+kp+i=Rs+i，其中p=t-s

(3) 令S={R0，R1，…，Rt-1}，則對(duì)于任意的q∈N有 Rq∈S

自反 "x(x∈A→<x,x>∈R)，

反自反 "x(x∈A→<x,x>?R)，

對(duì)稱 "x"y(x,y∈A∧<x,y>∈R→<y,x>∈R)

反對(duì)稱 "x"y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，

傳遞 "x"y"z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)

關(guān)系性質(zhì)的等價(jià)描述

設(shè)R為A上的關(guān)系，則

（1）R在A上自反當(dāng)且僅當(dāng) IA í R

（2）R在A上反自反當(dāng)且僅當(dāng) R∩IA＝?

（3）R在A上對(duì)稱當(dāng)且僅當(dāng) R＝R-1

（4）R在A上反對(duì)稱當(dāng)且僅當(dāng) R∩R-1 í IA

（5）R在A上傳遞當(dāng)且僅當(dāng) R°RíR

(1)若R1，R2是自反的和對(duì)稱的，則R1∪R2也是自反的和對(duì)稱的。

(2)若R1和R2是傳遞的，則R1∩R2也是傳遞的。

關(guān)系性質(zhì)的特點(diǎn)

自反性

反自反性

對(duì)稱性

反對(duì)稱性

傳遞性

集合表達(dá)式

IA í R

R∩IA＝?

R＝R-1

R∩R-1 í IA

R°RíR

關(guān)系矩陣

主對(duì)角線元素全是1

主對(duì)角線元素全是0

矩陣是對(duì)稱矩陣

若rij＝1，且i≠j，則rji＝0

對(duì)M2中1所在位置，M中相應(yīng)的位置都是1

關(guān)系圖

每個(gè)頂點(diǎn)都有環(huán)

每個(gè)頂點(diǎn)都沒有環(huán)

如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊(無單邊)

如果兩點(diǎn)之間有邊，一定是一條有向邊(無雙向邊)

如果頂點(diǎn)xi到xj有邊，xj到xk有邊，則從xi到xk也有邊

關(guān)系的性質(zhì)和運(yùn)算之間的關(guān)系

自反性

反自反性

對(duì)稱性

反對(duì)稱性

傳遞性

R1-1

√

√

√

√

√

R1∩R2

√

√

√

√

√

R1∪R2

√

√

√

×

×

R1－R2

×

√

√

√

×

R1 ° R2

√

×

×

×

×

閉包的構(gòu)造方法

設(shè)R為A上的關(guān)系，則有

（1）自反閉包 r(R)＝R∪R0

（2）對(duì)稱閉包 s(R)＝R∪R-1

（3）t(R)＝R∪R2∪R3∪…

關(guān)系性質(zhì)與閉包運(yùn)算之間的聯(lián)系

設(shè)R是非空集合A上的關(guān)系，

（1）若R是自反的，則s(R)與t(R)也是自反的。

（2）若R是對(duì)稱的，則r(R)與t(R)也是對(duì)稱的。

（3）若R是傳遞的，則r(R)是傳遞的。

等價(jià)類的性質(zhì)

設(shè)R是非空集合A上的等價(jià)關(guān)系，則

（1）"x∈A，[x]是A的非空子集。

（2）"x,y∈A，如果xRy，則[x]＝[y]。

（3）"x,y∈A，如果<x,y>?R，則[x]與[y]不交。

（4）∪{[x]|x∈A}＝A。

偏序集中的特殊元素

設(shè)<A，≤>為偏序集，BíA，y∈B。

（1）若"x(x∈B→y≤x)成立，則稱y為B的最小元。

（2）若"x(x∈B→x≤y)成立，則稱y為B的最大元。

（3）若"x(x∈B∧x≤y→x＝y(tǒng))成立，則稱y為B的極小元。

（4）若"x(x∈B∧y≤x→x＝y(tǒng))成立，則稱y為B的極大元

B

最大元

最小元

極大元

極小元

{2,3,6,12,24,36}

無

無

24，36

2,3

{6,12}

12

6

12

6

{2,3,6}

6

無

6

2,3

{6}

6

6

6

6

B

上界

下界

上確界

下確界

{2,3,6,12,24,36}

無

無

無

無

{6,12}

12,24,36

2,3,6

12

6

{2,3,6}

6,12,24,36

無

6

無

{6}

6,12,24,36,

2,3,6,

6

6

函數(shù)相等

由定義可知，兩個(gè)函數(shù)F和G相等, 一定滿足下面兩個(gè)條件：

（1）dom F＝dom G

（2）"x∈dom F＝dom G，都有 F(x)＝G(x)

所有從A到B的函數(shù)的集合記作BA，讀作“B上A”，符號(hào)化表示為 BA＝{f | f：A→B} 。

例：設(shè)A＝{1,2,3}，B＝{a,b}，求BA。

BA＝{ f0, f1, f2, f3, f4, f5, f6, f7} 。其中

f 0＝{<1,a>,<2,a>,<3,a>} f 1＝{<1,a>,<2,a>,<3,b>}

f 2＝{<1,a>,<2,b>,<3,a>} f 3＝{<1,a>,<2,b>,<3,b>}

f 4＝{<1,b>,<2,a>,<3,a>} f 5＝{<1,b>,<2,a>,<3,b>}

f 6＝{<1,b>,<2,b>,<3,a>} f 7＝{<1,b>,<2,b>,<3,b>}

設(shè)f:A→B，（1）若ran f＝B，則稱f:A→B是滿射(surjection)的。

（2）若"y∈ran f 都存在唯一的x∈A使得f(x)＝y(tǒng)，則稱 f:A→B是單射(injection)的。

（3）若f 既是滿射又是單射的，則稱f:A→B是雙射(bijection)

單射 雙射 函數(shù) 滿射

例：判斷下面函數(shù)是否為單射、滿射、雙射的，為什么?

(1) f：R→R，f(x)= -x2+2x-1 (2) f：Z+→R，f(x)=ln x，Z+為正整數(shù)集
(3) f：R→Z，f(x)=?x? (4) f：R→R，f(x)=2x+1。

解（1）f 在x=1取得極大值0。既不是單射也不是滿射的。

（2）f 是單調(diào)上升的，是單射的，但不滿射。ran f={ln1, ln2, …}。

（3）f 是滿射的， 但不是單射的，例如f(1.5)=f(1.2)=1。

（4）f 是滿射、單射、雙射的，因?yàn)樗菃握{(diào)函數(shù)并且ran f=R。

例：(1) 給定無向圖G＝<V,E>，其中 V＝{v1,v2,v3,v4,v5}，
E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.

　(2) 給定有向圖D=<V,E>，其中 V＝{a,b,c,d}，
E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。

　畫出G與D的圖形。

鄰域：NG(v1) ＝{v2，v5} 后繼元集：Г+D(d ) ＝{c}

閉鄰域：NG(v1) ＝{v1，v2，v5} 先驅(qū)元集：Г-D(d ) ＝{a，c}

關(guān)聯(lián)集：IG(v1) ＝{e1，e2，e3} 鄰域： ND(d ) ＝{a，c}

閉鄰域：ND(d ) ＝{a，c，d}

d(v1)＝4(注意，環(huán)提供2度)， 出度：d+(a)＝4，入度：d-(a)＝1
△＝4，δ＝1， (環(huán)e1提供出度1，提供入度1)，

v4是懸掛頂點(diǎn)，e7是懸掛邊。 d(a)＝4+1＝5。△＝5，δ＝3，

△+＝4 (在a點(diǎn)達(dá)到)

度數(shù)列為4,4,2,1,3。 δ+＝0(在b點(diǎn)達(dá)到)

△-＝3(在b點(diǎn)達(dá)到)

δ-＝1(在a和c點(diǎn)達(dá)到)

按字母順序，度數(shù)列：5,3,3,3

出度列：4,0,2,1 入度列：1,3,1,2

設(shè)G＝<V,E>是n階m條邊的無向圖，則下面各命題是等價(jià)的：

（1）G是樹。 （2）G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。

（3）G中無回路且m＝n-1。 （4）G是連通的且m＝n-1。

（5）G是連通的且G中任何邊均為橋。

（6）G中沒有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個(gè)含新邊的圈。

例題 已知無向樹T中，有1個(gè)3度頂點(diǎn)，2個(gè)2度頂點(diǎn)，其余頂點(diǎn)全是樹葉，試求樹葉數(shù)，并畫出滿足要求的非同構(gòu)的無向樹。

解答 設(shè)有x片樹葉，于是結(jié)點(diǎn)總數(shù)

n＝1+2+x＝3+x

由握手定理和樹的性質(zhì)m＝n-1可知，

2m＝2(n-1)＝2×(2+x)

＝1×3+2×2+x

解出x＝3，故T有3片樹葉。

故T的度數(shù)應(yīng)為1、1、1、2、2、3。

求最小生成樹的算法（避圈法(Kruskal)）

(1)設(shè)n階無向連通帶權(quán)圖G＝<V,E,W>有m條邊。不妨設(shè)G中沒有環(huán)（否則，可以將所有的環(huán)先刪去），將m條邊按權(quán)從小到大排序：e1,e2,…,em。

(2)取e1在T中。

(3)依次檢查e2,…,em ，若ej(j≥2)與已在T中的邊不構(gòu)成回路，取ej也在T中，否則棄去ej。

(4)算法停止時(shí)得到的T為G的最小生成樹為止。

例：求下圖所示兩個(gè)圖中的最小生成樹。

W(T1)＝6 W(T2)＝12

T是n(n≥2)階有向樹，

(1) T為根樹— T中有一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)的入度均為1

(2) 樹根——入度為0的頂點(diǎn)

(3) 樹葉——入度為1，出度為0的頂點(diǎn)

(4) 內(nèi)點(diǎn)——入度為1，出度不為0的頂點(diǎn)

(5) 分支點(diǎn)——樹根與內(nèi)點(diǎn)的總稱

(6) 頂點(diǎn)v的層數(shù)——從樹根到v的通路長度

(7) 樹高——T中層數(shù)最大頂點(diǎn)的層數(shù)

根樹的畫法：樹根放上方，省去所有有向邊上的箭頭。

樹葉——8片 內(nèi)點(diǎn)—— 6個(gè) 分支點(diǎn)—— 7個(gè) 高度—— 5

求帶權(quán)為1、1、2、3、4、5的最優(yōu)樹。

W(T)=38

中序行遍法：b a (f d g) c e 前序行遍法：a b (c (d f g) e)

后序行遍法：b ((f g d) e c) a

├ 斷定符（公式在L中可證）

╞ 滿足符（公式在E上有效，公式在E上可滿足）

┐ 命題的“非”運(yùn)算

∧ 命題的“合取”（“與”）運(yùn)算

∨ 命題的“析取”（“或”，“可兼或”）運(yùn)算

→ 命題的“條件”運(yùn)算

? 命題的“雙條件”運(yùn)算的

A<=>B 命題A 與B 等價(jià)關(guān)系

A=>B 命題 A與 B的蘊(yùn)涵關(guān)系

A* 公式A 的對(duì)偶公式

wff 合式公式

iff 當(dāng)且僅當(dāng)

↑ 命題的“與非” 運(yùn)算（ “與非門” ）

↓ 命題的“或非”運(yùn)算（ “或非門” ）

□ 模態(tài)詞“必然”

◇ 模態(tài)詞“可能”

φ 空集

∈ 屬于（?不屬于）

P（A） 集合A的冪集

|A| 集合A的點(diǎn)數(shù)

R^2=R○R [R^n=R^(n-1)○R] 關(guān)系R的“復(fù)合”

? 阿列夫

? 包含

?（或下面加 ≠） 真包含

∪ 集合的并運(yùn)算

∩ 集合的交運(yùn)算

- （～） 集合的差運(yùn)算

〡 限制

[X](右下角R) 集合關(guān)于關(guān)系R的等價(jià)類

A/ R 集合A上關(guān)于R的商集

[a] 元素a 產(chǎn)生的循環(huán)群

I (i大寫) 環(huán)，理想

Z/(n) 模n的同余類集合

r(R) 關(guān)系 R的自反閉包

s(R) 關(guān)系 的對(duì)稱閉包

CP 命題演繹的定理（CP 規(guī)則）

EG 存在推廣規(guī)則（存在量詞引入規(guī)則）

ES 存在量詞特指規(guī)則（存在量詞消去規(guī)則）

UG 全稱推廣規(guī)則（全稱量詞引入規(guī)則）

US 全稱特指規(guī)則（全稱量詞消去規(guī)則）

R 關(guān)系r 相容關(guān)系

R○S 關(guān)系 與關(guān)系 的復(fù)合

domf 函數(shù) 的定義域（前域）

ranf 函數(shù) 的值域

f:X→Y f是X到Y(jié)的函數(shù)

GCD(x,y) x,y最大公約數(shù)

LCM(x,y) x,y最小公倍數(shù)

aH(Ha) H 關(guān)于a的左（右）陪集

Ker(f) 同態(tài)映射f的核（或稱 f同態(tài)核）

[1，n] 1到n的整數(shù)集合

d(u,v) 點(diǎn)u與點(diǎn)v間的距離

d(v) 點(diǎn)v的度數(shù)G=(V,E) 點(diǎn)集為V,邊集為E的圖

W(G) 圖G的連通分支數(shù)

k(G) 圖G的點(diǎn)連通度

△（G) 圖G的最大點(diǎn)度

A(G) 圖G的鄰接矩陣

P(G) 圖G的可達(dá)矩陣

M(G) 圖G的關(guān)聯(lián)矩陣

C 復(fù)數(shù)集

N 自然數(shù)集（包含0在內(nèi)）

N* 正自然數(shù)集

P 素?cái)?shù)集

Q 有理數(shù)集

R 實(shí)數(shù)集

Z 整數(shù)集

Set 集范疇

Top 拓?fù)淇臻g范疇

Ab 交換群范疇

Grp 群范疇

Mon 單元半群范疇

Ring 有單位元的（結(jié)合）環(huán)范疇

Rng 環(huán)范疇

CRng 交換環(huán)范疇

R-mod 環(huán)R的左模范疇

mod-R 環(huán)R的右模范疇

Field 域范疇

Poset 偏序集范疇