離散數(shù)學知識點

1、-. z. . . . . 資料. . .說明：定義：紅色表示。定理性質：橙色表示。公式：藍色表示。算法:綠色表示頁碼：灰色表示數(shù)理邏輯：命題公式：命題，聯(lián)結詞(，)，合式公式，子公式公式的真值：賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式*式：析取*式，極小項，主析取*式，合取*式，極大項，主合取*式聯(lián)結詞的完備集：真值函數(shù)，異或，條件否認，與非，或非，聯(lián)結詞完備集推理理論：重言蘊含式，有效結論，P規(guī)則，T規(guī)則， CP規(guī)則，推理謂詞與量詞:謂詞，個體詞，論域，全稱量詞，存在量詞項與公式:項，原子公式，合式公式，自由變元，約束變元，轄域，換名，代入公式語義:解釋，賦值，有效的，可滿足的，不可

2、滿足的前束*式:前束*式推理理論:邏輯蘊含式，有效結論，-規(guī)則US，+規(guī)則UG，-規(guī)則(ES)，+規(guī)則(EG), 推理集合論：集合: 集合, 外延性原理, , , , 空集, 全集, 冪集, 文氏圖, 交, 并, 差, 補, 對稱差關系: 序偶, 笛卡爾積, 關系, domR, ranR, 關系圖, 空關系, 全域關系, 恒等關系關系性質與閉包:自反的, 反自反的,對稱的, 反對稱的, 傳遞的,自反閉包 r(R),對稱閉包 s(R), 傳遞閉包 t(R)等價關系: 等價關系, 等價類, 商集, 劃分偏序關系:偏序, 哈斯圖, 全序(線序), 極大元/極小元, 最大元/最小元, 上界/下界函數(shù):

3、 函數(shù), 常函數(shù), 恒等函數(shù), 滿射,入射,雙射，反函數(shù), 復合函數(shù)集合基數(shù):基數(shù), 等勢, 有限集/無限集, 可數(shù)集, 不可數(shù)集代數(shù)構造：運算及其性質：運算，封閉的,可交換的,可結合的,可分配的,吸收律, 冪等的，幺元,零元,逆元代數(shù)系統(tǒng)：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)，同態(tài)，同構。群與子群：半群,子半群,元素的冪，獨異點，群，群的階數(shù)，子群,平凡子群，陪集，拉格朗日Lagrange定理阿貝爾群和循環(huán)群：阿貝爾群(交換群)，循環(huán)群,生成元環(huán)與域：環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域格與布爾代數(shù)：格，對偶原理，子格，分配格，有界格，有補格，布爾代數(shù)，有限布爾代數(shù)的表示定理圖論：圖的根本概念：無向圖、有向圖、

4、關聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖，握手定理，圖的同構圖的連通性:通路，回路，簡單通路，簡單回路跡初級通路路徑，初級回路圈，點連通，連通圖，點割集，割點，邊割集，割邊，點連通度，邊連通度，弱連通圖，單向連通圖，強連通圖，二部圖二分圖圖的矩陣表示：關聯(lián)矩陣，鄰接矩陣，可達矩陣歐拉圖與哈密頓圖：歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖無向樹與根樹：無向樹，生成樹，最小生成樹，Kruskal，根樹，m叉樹，最優(yōu)二叉樹，Huffman算法平面圖:平面圖，面，歐拉公式，Kuratoski定理數(shù)理邏輯：命題：具有確定真值的陳述句。否認詞符號：設p是一個

5、命題，p稱為p的否認式。p是真的當且僅當p是假的。p是真的當且僅當p是假的?！径x1.1】合取詞符號：設p，q是兩個命題，命題p并且q稱為p，q的合取，記以pq，讀作p且q。pq是真的當且僅當p和q都是真的?！径x1.2】析取詞符號：設p，q是兩個命題，命題p或者q稱為p，q的析取，記以pq，讀作p或q。pq是真的當且僅當p，q中至少有一個是真的?！径x1.3】蘊含詞符號：設p，q是兩個命題，命題如果p，則q稱為p蘊含q，記以pq。pq是假的當且僅當p是真的而q是假的?！径x1.4】等價詞符號：設p，q是兩個命題，命題p當且僅當q稱為p等價q，記以pq。pq是真的當且僅當p，q或者都是真的，或

6、者都是假的?！径x1.5】合式公式:命題常元和變元符號是合式公式；假設A是合式公式，則(A)是合式公式，稱為A的否認式；假設A，B是合式公式，則 (AB)， (AB)， (AB)，(AB)是合式公式；所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符號串。子公式: 如果是合式公式A的一局部，且本身也是一個合式公式，則稱為公式A的子公式?！径x1.6】賦值指派，解釋：設是命題變元集合，則稱函數(shù)v： 1，0是一個真值賦值。【定義1.8】真值表：公式A在其所有可能的賦值下所取真值的表，稱為A的真值表?！径x1.9】重言式永真式:任意賦值v， v A矛盾式永假式:任意賦值v，有v A【定

7、義1.10】等值式：假設等價式AB是重言式，則稱A與B等值，記作AB?！径x2.1】根本等值式雙重否認律AA冪等律AAA, AAA交換律ABBA, ABBA結合律(AB)CA(BC), (AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB,(AB)AB吸收律A(AB)A, A(AB)A零律 A, A同一律 AA, AA排中律 AA 矛盾律 AA蘊涵等值式 ABAB等價等值式 AB(AB)(BA)假言易位 ABBA等價否認等值式ABAB歸謬論 (AB)(AB) A置換規(guī)則：設是公式A的子公式, Y。將A中的可以是全部或局部*用Y來置換，所得到的公式

8、B，則 AB。文字: 設A命題變元集, 則A和 A都稱為命題符號A的文字，其中前者稱為正文字，后者稱為負文字。【定義2.2】析取*式：形如A1 A2 An(n1) 的公式稱為析取*式，其中Ai(i=1,n)是由文字組成的合取*式。合取*式：形為A1 A2 An(n 1) 的公式稱為合取*式，其中A1,An都是由文字組成的析取式?！径x2.3】極小項：文字的合取式稱為極小項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次。極大項：文字的析取式稱為極大項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次?！径x2.4】主析取*式：給定的命題公式的主析取*式是一個與之等價的公式，后者由極小項的

9、析取組成。主合取*式：給定的命題公式的主合取*式是一個與之等價的公式，后者由極大項的合取組成?！径x2.5】公式的真值表中真值為F的指派所對應的極大項的合取，即為此公式的主合取*式。真值函數(shù)：稱F:0,1n 0,1 為n元真值函數(shù).【定義2.6】聯(lián)結詞的完備集：設C是聯(lián)結詞的集合，假設對于任意一個合式公式均存在一個與之等價的公式，而后者只含有C中的聯(lián)結詞，則稱C是聯(lián)結詞的完備集?！径x2.7】， , ， ，是聯(lián)結詞的完備集。【定理2.6】c異或PQ： (P Q)c條件否認PQ： (P Q)與非PQ： (P Q)或非PQ： (P Q)【定義2.8】,都是聯(lián)結詞的完備集【定理2.7】重言蘊含式：當

10、且僅當PQ是一個重言式時，稱P重言蘊含Q，記為PQ。有效結論：設A、C是兩個命題公式，假設A C，稱C是A的有效結論?！径x3.1】推理定律重言蘊涵式1. A (AB)附加律2. (AB) A化簡律3. (AB)A B假言推理4. (AB)B A拒取式5. (AB)B A析取三段論6. (AB)(BC) (AC)假言三段論7. (AB)(BC) (AC)等價三段論8. (AB)(CD)(AC) (BD)構造性二難(AB)(AB) B構造性二難(特殊形式)9. (AB)(CD)( BD) (AC)破壞性二難形式系統(tǒng): 一個形式系統(tǒng)I 由下面四個局部組成： (1) 非空的字母表，記作A(I). (

11、2) A(I) 中符號構造的合式公式集，記作E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作A*(I). (4) 推理規(guī)則集，記作R(I).記I=, 其中是I 的形式語言系統(tǒng), 是I 的形式演算系統(tǒng).自然推理系統(tǒng): 無公理, 即A*(I)=公理推理系統(tǒng): 推出的結論是系統(tǒng)中的重言式, 稱作定理【定義3.2】P規(guī)則：在推導過程中,可以隨時添加前提。T規(guī)則：在推導過程中,可以引入公式S，它是由其前題的一個或多個公式借助重言、蘊含而得到的。推理證明：從前提A1, A2, Ak到結論B的推理是一個公式序列C1, C2, Cl. 其中Ci(1il)是*個Aj, 或者可由序列中前面的公式應

12、用推理規(guī)則得到, 并且Cl =B。【定義3.3】CP規(guī)則(演繹定理)：假設R|- S，則 |- RS, 其中為命題公式的集合。個體詞：用于表示命題中主語局部的符號或符號串。個體常元表示確指個體。個體變元表示不確指個體。個體域: 個體變元的取值*圍，常用D表示。量詞：限定個體數(shù)量特性的詞。全稱量詞：對所有的存在量詞：有些謂詞語言：用符號串表示個體、謂詞、量詞和命題個體變元符號： *，y，z，個體常元符號： a，b，c，函數(shù)符號：f，g，謂詞符號：P，Q，R，命題常元符號：，量詞符號：，連接詞符號： , , , , 輔助符號： , 【定義4.1】項: (1)個體常元和變元是項；(2) 假設f是n元

13、函數(shù)符號，t1, , tn是項，則f(t1, , tn)是項；(3) 僅僅有限次使用(1)，(2)產生的符號串是項?！径x4.2】原子公式:假設P是一個元謂詞符號，t1,tn是項, 則P(t1,tn)是原子公式?！径x4.3】合式公式： (1) 原子公式是公式；(2) 假設A是合式公式，則( A)是合式公式；(3) 假設A，B是公式，則(AB)，(AB)，AB)，(AB)是公式；(4) 假設A是公式，*是變元，則*A，*A是公式；(5) 僅僅有限次使用得到的符號串才是合式公式?！径x4.4】設公式的一個子公式為 * A或 * A。則稱：指導變元：*是或的指導變元。轄域：A是相應量詞的轄域。約束

14、出現(xiàn)：轄域中*的一切出現(xiàn)，以及( *)中的*稱為*在中的約束出現(xiàn)。自由出現(xiàn)：變元的非約束出現(xiàn)。約束變元：約束出現(xiàn)的變元。自由變元：自由出現(xiàn)的變元。【定義4.5】封閉的：一個公式A是封閉的，假設其中不含自由變元?！径x4.6】變元換名：1換名的*圍是量詞的指導變元,及其相應轄域中的變元，其余局部不變。2換名時最好選用轄域中未出現(xiàn)的變元名。變元代入：代入對自由變元進展。不能改變約束關系。解釋：謂詞語言的一個解釋 I= (D, )包括： (1) 非空集合D，稱之為論域； (2) 對應于每一個個體常元a，(a)D； (3) 對應于每一個n元函數(shù)符號f都有一個函數(shù)(f):Dn D； (4) 對應于每一個

15、n元謂詞符號A都有一個n元關系(A) Dn?！径x4.7】賦值：解釋I中的賦值v為每一個個體變元*指定一個值v(* D，即設 V為所個體變元的集合，則賦值v是函數(shù) v:V D.可滿足的：給定公式A，假設在*一解釋中至少有一種賦值使A取值為1，則稱A為可滿足的。否則稱A是不可滿足的。等值式A B：假設AB是有效的【定義5.1】幾類等值式1命題公式的推廣 e.g. P(*) Q(*) P(*) Q(*)2否認深入 * P(*) *( P(*) *P(*) * ( P(*)3量詞作用域的擴*與收縮設B中不含*的自由出現(xiàn)，則 *(A(*) B) * A(*) B *(A(*) B) * A(*) B

16、*(A(*)B) * A(*) B *(B A(*) B * A(*) *(A(*) B) * A(*) B *(A(*) B) * A(*) B *(A(*)B) * A(*) B *(B A(*) B * A(*)4量詞分配等值式 *(A(*) B(*) * A(*) * B(*) *(A(*) B(*) * A(*) * B(*)5多個量詞的使用 * y A(*,y) y * A(*,y) * y A(*,y) y * A(*,y)置換規(guī)則：設(A)是含A的公式, 則, 假設AB, 則(A)(B).換名規(guī)則：設A為一公式，將A中*量詞轄域中個體變項的所有約束出現(xiàn)及相應的指導變元換成該量詞

17、轄域中未曾出現(xiàn)過的個體變項符號，其余局部不變，設所得公式為A，則AA.前束*式：如果謂詞公式A有如下形狀：Q1*1Qn*nM，其中 Qi*i或者是*i，或者是*i，i=1，n，M是不含量詞的公式， Q1*1Qn*n稱為首標，M稱為母式?！径x5.2】前束*式存在定理：對于任意謂詞公式，都存在與它邏輯等價的前束*式?！径ɡ?.1】前束*式的算法：步1. 對約束出現(xiàn)的變元進展必要的換名，使得約束出現(xiàn)的變元互不一樣且不與任何自由變元同名。步2. 將所有的否認號深入到量詞后面。步3. 將量詞符號移至公式最外層。邏輯蘊含式A C：當且僅當AC是有效的。幾類邏輯蘊涵式第一組命題邏輯推理定理的代換實例如,

18、*F(*)yG(y) *F(*) 第二組根本等值式生成的推理定理如, *F(*) *F(*), *F(*) *F(*)*F(*)*F(*), *F(*) *F(*)第三組其它常用推理定律 (1) *A(*)*B(*) *(A(*)B(*) (2) *(A(*)B(*)*A(*)*B(*) (3) *(A(*)B(*) *A(*)*B(*) (4) *(A(*)B(*) *A(*)*B(*)推理規(guī)則- 規(guī)則(US)： QUOTE 或 QUOTE *,y個體變項，c個體常項+規(guī)則(UG)： QUOTE *個體變項- 規(guī)則(ES)： QUOTE *個體變項, c個體常項+ 規(guī)則(EG)： QUOTE

19、 或 QUOTE *,y個體變項，c個體常項 QUOTE 或 QUOTE 先用ES，再用US自然推理系統(tǒng)NL：1. 字母表. 同一階語言L 的字母表2. 合式公式. 同L的合式公式3. 推理規(guī)則:(1) 前提引入規(guī)則(2) 結論引入規(guī)則(3) 置換規(guī)則(4) 假言推理規(guī)則(5) 附加規(guī)則(6) 化簡規(guī)則(7) 拒取式(8) 假言三段論規(guī)則(9) 析取三段論規(guī)則(10) 構造性二難推理規(guī)則(11) 合取引入規(guī)則(12) -規(guī)則(13) +規(guī)則(14) -規(guī)則(15) +規(guī)則【定義5.3】集合論：A B * ( *A *B )【定義6.1】A = B A B B A【定義6.2】A B A B A

20、 B 【定義6.3】AB * ( *A *B ) 空集：不含有任何元素的集合【定義6.4】空集是任何集合的子集?！径ɡ?.1】冪集P(A) = * | * A 【定義6.5】如果 |A|=n，則 |P(A)|=2n全集 E：包含了所有元素的集合【定義6.6】并AB= * | *A *B交AB = * | *A *B 差相對補AB = * | *A *B【定義6.7】對稱差AB = (AB)(BA) 【定義6.8】補絕對補A = EA = *|*A【定義6.9】廣義并A= * | z ( zA*z )【定義6.10】廣義交A = * | z ( zA *z )【定義6.11】集合恒等式1.只涉及

21、一個運算的算律：交換AB=BAAB=BAAB=BA結合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)冪等AA=AAA=A2涉及兩個不同運算的算律：與與分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A3涉及補運算的算律：D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC雙重否認A=A4涉及全集和空集的算律：E補元律AA=AA=E零律A=AE=E同一律A=AAE=A否認=EE=序偶有序對：由兩個元素 * 和 y，按照一定的順序組成的二元組，記作.【定義7.1】笛卡兒

22、積:設A,B為集合，A與B的笛卡兒積記作AB定義為AB = | *AyB.【定義7.2】笛卡爾積性質：A=或B=時, AB=不滿足結合律A(BC) = (AB)(AC)關系：兩個定義(1) 序偶的一個集合, 確定了一個二元關系R。R 中任一序偶 ,可記作 R 或 *Ry【定義7.3】(2) 笛卡爾積的子集： R AB【定義7.4】空關系:全域關系：AB 恒等關系IA= | *A【定義7.5】關系矩陣：假設A=*1, *2, , *m，B=y1, y2, , yn，R是從A到B的關系，R的關系矩陣是布爾矩陣MR = rij mn, 其中rij= 1 R. 關系圖：假設A= *1, *2, , *

23、m，R是從A上的關系，R的關系圖是GR=, 其中A為結點集，R為邊集. 如果屬于關系R，在圖中就有一條從*i 到*j 的有向邊. 前域(定義域) dom(R) = *|y.R值域 ran(R)=y|*.R域fld(R) = domR ranR【定義7.6】逆關系R1= | R 【定義7.7】互逆(R1)1 = R(R S)1 = R1 S1(R S)1 = R1 S1(A B)1 = BA(R - S)1 = R1 - S1復合關系RS= | y (R S) 【定義7.8】(R S) P=R (S P) Rm = RRR 設R * Y,S YZ,則 (R S)1 = S1 R1 【定理7.2】

24、R在A上的限制RA = | *Ry*A A在R下的像RA=ran(RA) 【定義7.9】自反的：假設*A，都有R, 則稱 R 是自反的反自反的：假設*A，都有 R, 則稱 R 是反自反的.【定義7.11】對稱的：對任意*,yA,滿足, 假設 R,則R反對稱的：對任意*,yA,滿足，假設 R且R,則*=y【定義7.12】傳遞的：對任意的*,y,zA, 滿足:假設R且R, 則R,則稱R是傳遞的【定義7.13】自反閉包對稱、傳遞：設R是A上的二元關系,如果有另一個關系R滿足:R是自反對稱、傳遞的;RR;對于任何自反的關系R,假設RR, 則有RR.則稱關系R為R的自反閉包. 記為 r(R)對稱閉包 s

25、(R) 和傳遞閉包 t(R)?！径x7.14】設R為A上的關系, 則有(1) r(R)=RIA(2) s(R)=RR1(3) t(R)=RR2R3假設|A|=n，則 t(R)=RR2Rn 等價關系：設 R 為集合 A 上的一個二元關系。假設 R 是自反的, 對稱的, 傳遞的, 則稱 R 為 A 上的等價關系【定義7.15】等價類：設R為集合A上的等價關系, 對aA, 定義:aR = *|*A 且 R稱之為元素a關于R的等價類。【定義7.16】給定A上的等價關系R,對于a,bA有當且僅當aR=bR【定理17.4】商集：設R是A上的等價關系，定義 A/R=aR|aA稱之為A關于R的商集.【定義7.

26、17】劃分：設A為非空集合, 假設A的子集族( P(A)滿足:(1) (2) *y(*,y*y*y=)(3) = A則稱是A的一個劃分, 稱中的元素為A的劃分塊.【定義7.18】給定集合 A 上的等價關系 R, 則商集 A/R 是 A 的一個劃分.集合A的一個劃分誘導出A上的一個等價關系R. R定義為R= | *,y A 且*,y在的同一分塊中設R1和R2為非空集合A上的一個等價關系,則 R1 = R2當且僅當A/R1 = A/R2.偏序：設A是一個集合. 如果 A 上的二元關系 R 是自反的,反對稱的和傳遞的, 則稱R是A上的一個偏序關系. 記R為, 且稱序偶 為偏序集?！径x7.19】【定

27、義7.22】全序線序：設 為偏序集, 假設對任意的*,yA滿足: *y或 y*則稱為全序關系. 為全序集.【定義7.21】覆蓋：設為偏序集,假設*,yA, *y,*y且沒有其它元素z滿足*z,zy,則稱y覆蓋*. 記covA= |*,yA且y覆蓋*【定義7.23】哈斯圖：作圖規(guī)則用小元圈代表元素;假設*y且*y,則將代表y的小元圈畫在代表*的小元圈之上;假設covA, 則在*,y之間用直線連接。你極小元/極大元：設為偏序集, B A (1) 對bB，假設B中不存在*滿足: b*且 *b則稱b為B的極小元. (2) 對bB，假設B中不存在*滿足: b*且 b*則稱b為B的極大元.最小元/最大元：

28、設為偏序集,BA,假設有*個bB (1) 對于B中每一個元素*都有b*，則稱b為B的最小元.(2) 對于B中每一個元素*都有*b，則稱b為B的最大元.【定義7.24】下界/上界：設為偏序集, B A(1) 假設有aA,且對*B 滿足 a*，則稱a為B的下界。進一步: 設a為B的下界,假設B的所有下界y均有ya,則稱a為B的下確界，記為glb B。(2) 假設有aA,且對*B 滿足 *a，則稱a為B的上界。進一步: 設a為B的上界,假設B的所有上界y均有ay,則稱a為B的上確界，記為lub B?！径x7.25】函數(shù)：設*,Y為兩個集合,f*Y, 假設對*,!(唯一的)yY,滿足: f,則稱f為函

29、數(shù).記為:f:*Y定義域: domf=*值域: ranf (有時記為f(*)=f(*)|*【定義8.1】函數(shù)相等：設f和g都是從A到B的函數(shù), 假設對任意*A,有f(*)=g(*),則稱f和g相等.記為f=g【定義8.2】函數(shù)的個數(shù)：設f:AB,|A|=m, |B|=n.記 BA=f|f: AB, 則| BA |= nm滿射(到上映射)：設 f: * Y, 假設 ranf = Y, 則稱 f 為滿射的.入射單射(一對一映射)：設f: *Y, 對 *1, *2*, 滿足:假設 *1 *2, 則 f(*1) f(*2),稱 f 為入射的.雙射(一一對應映射)：設f:*Y, 假設f既是滿射的, 又是

30、入射的. 則稱f是雙射的.【定義8.6】常函數(shù):設f:AB, 如果存在cB使得對所有的*A都有 f(*)=c, 則稱f:AB是常函數(shù).恒等函數(shù):稱 A上的恒等關系IA為A上的恒等函數(shù), 對所有的*A都有IA(*)=*.單調遞增:設, 為偏序集，f:AB，如果對任意的*1, *2A, *1*2, 就有f(*1)f(*2), 則稱 f 為單調遞增的；嚴格單調遞增:如果對任意的*1, *2A, *1*2, 就有f(*1) f(*2), 則稱 f 為嚴格單調遞增的. 類似的也可以定義單調遞減和嚴格單調遞減的函數(shù)特征函數(shù)：設A為集合, 對于任意的AA, A的特征函數(shù)A :A0,1定義為A(a)=1, a

31、A;A(a)=0, aAA自然映射：設R是A上的等價關系, 令g:AA/R；g(a)=a, aA稱 g 是從 A 到商集 A/R 的自然映射【定義8.7】復合函數(shù)：設 f:*Y,g:YZ, 定義: f g = |*且zZ且可找到y(tǒng)Y使y=f(*),z=g(y)稱f g為f與 g 的復合函數(shù).設f:AB, g:BC(1) 如果 f:AB, g:BC是滿射的, 則 fg:AC也是滿射的(2) 如果 f:AB, g:BC是單射的, 則 fg:AC也是單射的(3) 如果 f:AB, g:BC是雙射的, 則 fg:AC也是雙射的【定理8.2】反函數(shù)逆函數(shù)：設f:*Y是一個雙射函數(shù)，則f -1是Y*的雙射

32、函數(shù). 稱f -1為f的反函數(shù).互逆 (f -1 )-1=f設f:AB是雙射的, 則f1f = IB, f f 1 = IA 【定理8.5】基數(shù)：用來衡量集合大小的一個概念. 對于有限集合集來說, 集合的基數(shù)就是其中所含元素的個數(shù).等勢的：設A, B是集合, 如果存在著從A到B的雙射函數(shù), 就稱A和B是等勢的, 記作AB. 如果A不與B等勢, 則記作AB.注：通常將A的基數(shù)記為 |A|.【定義8.8】N Z Q NN任何實數(shù)區(qū)間都與實數(shù)集合R等勢0,1NR康托定理N R；對任意集合A都有AP(A).【定義8.7】有限集(有窮集)/無限集 (無窮集)：設A為一個集合. 假設存在*個自然數(shù)n, 使

33、得A與集合0,1,n-1等勢, 則稱A是有限的. 假設集合A不是有限的, 則稱A是無限的.【定義8.11】：實數(shù)集R的基數(shù)記作, 即cardR=【定義8.12】可數(shù)集(可列集)：設A為集合，假設cardA0，則稱A為可數(shù)集或可列集。【定義8.14】與自然數(shù)集N等勢的任意集合稱為可數(shù)的.其基數(shù)為0結論： (1) A為可數(shù)的當且僅當可排列成A=a1,a2, ,an,的形式.(2) 任一無限集必含有可數(shù)子集.(3) 可數(shù)集的任何無限子集是可數(shù)的.(4) 可數(shù)個兩兩不相交的可數(shù)集合的并集,仍是一個可數(shù)集.(5) NN是可數(shù)集.(6) 有理數(shù)的全體組成的集合是可數(shù)集.(7) 全體實數(shù)構成的集合R是不可數(shù)

34、的.基數(shù)的常識：對于有窮集合A, 基數(shù)是其元素個數(shù)n，|A| = n; 沒有最大的基數(shù)。將的基數(shù)按從小到大的順序排列就得到： 0, 1, 2, , n, , 0, , 代數(shù)構造運算：對于集合 A，f 是從An到 A 的函數(shù)，稱 f 為集合A上的一個n元運算。【定義9.1】交換律：，假設*，yA，有*y=y*，稱*在A上是可交換的?！径x9.3】結合律：，假設*，y，zA，有*y*z=*y*z，稱*在A上是可結合的?！径x9.4】冪等律：A，*，假設*A，*=* 則稱滿足冪等律?！径x9.5】分配律：設，假設*，y，zA有: *(yz)=*y*z ; (yz)*=(y*)(z*)稱運算*對是可分

35、配的?！径x9.6】吸收律：設,是定義在集合A上的兩個可交換二元運算，假設對*,y A,都有:*(*y) = * ； *(* y) = *則稱運算和滿足吸收律.【定義9.7】單位元幺元:設*是A上二元運算， el, er,eA左幺元：假設*A，有el*=*，稱el為運算*的左幺元；右幺元：假設*A，有*er=*，稱er為運算*的右幺元；假設e既是左幺元又是右幺元，稱e為運算*的幺元【定義9.8】設*是A上的二元運算，具有左幺元el，右幺元er，則el=er=e 【定理9.1】零元:設*是A上二元運算，l, r, A左零元：假設*A，有l(wèi)*=l，稱l為運算*的左零元；右零元：假設*A，有*r=r

36、，稱r為運算*的右零元；假設既是左零元又是右零元，稱為運算*的零元?！径x9.9】設*是A上的二元運算，具有左零元l，右零元r，則l= r= 【定理9.2】逆元：設*是A上的二元運算，e是運算*的幺元，假設*y=e那對于運算*，*是y的左逆元，y是*的右逆元存在逆元(【定義9.10】對于可結合運算，如果元素*有左逆元，右逆元r，則l=r=*【定理9.4】消去律：，假設*，y，zA，有 (1) 假設 *y = *z且 * ,則y=z；(左消去律) (2) 假設 y* = z*且 * ,則y=z；右消去律則稱*滿足消去律?！径x9.11】代數(shù)系統(tǒng)：設A為非空集合，為A上運算的集合,稱為一個代數(shù)系統(tǒng)

37、.【定義9.12】同類型的代數(shù)系統(tǒng)：如果兩個代數(shù)系統(tǒng)中運算的個數(shù)一樣，對應運算的元數(shù)一樣，且代數(shù)常數(shù)的個數(shù)也一樣，則稱它們是同類型的代數(shù)系統(tǒng).【定義9.13】子代數(shù)：設V=是代數(shù)系統(tǒng)，B是S的非空子集，如果B對f1, f2, , fk 都是封閉的，且B和S含有一樣的代數(shù)常數(shù)，則稱是V的子代數(shù)系統(tǒng)，簡稱子代數(shù)【定義9.14】最大的子代數(shù)：就是V本身最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構成的集合是B，且B對V中所有的運算都是封閉的，則B就構成了V的最小的子代數(shù)平凡的子代數(shù):最大和最小的子代數(shù)稱為V 的平凡的子代數(shù)真子代數(shù)：假設B是S的真子集，則B構成的子代數(shù)稱為V的真子代數(shù).因子代數(shù)：設V1=和V

38、2=是同類型的代數(shù)系統(tǒng)，和為二元運算，在集合AB上如下定義二元運算，,AB，有= 稱V=為V1與V2的積代數(shù)，記作V1V2. 這時也稱V1和V2為V的因子代數(shù). 【定義9.15】設V1=和V2=是同類型的代數(shù)系統(tǒng)，V1V2=是它們的積代數(shù). (1) 如果和運算是可交換可結合、冪等的，那幺運算也是可交換可結合、冪等的(2) 如果e1 和e21和2分別為和運算的單位元零元，那幺也是運算的單位元零元(3) 如果* 和y 分別為和運算的可逆元素，那幺也是運算的可逆元素，其逆元就是 【定理9.5】同態(tài):設V1=和V2=是同類型的代數(shù)系統(tǒng)，f:AB，對*, yA 有f(*y) = f(*)f(y), 則稱

39、f 是V1到V2的同態(tài)映射，簡稱同態(tài)(1) f 如果是單射，則稱為單同態(tài)。(2) 如果是滿射，則稱為滿同態(tài)，這時稱V2是V1的同態(tài)像，記作V1V2。(3) 如果是雙射，則稱為同構，也稱代數(shù)系統(tǒng)V1同構于V2，記作V1V2 。(4) 如果V1=V2，則稱作自同態(tài)。【定義9.16】半群：設V=是代數(shù)系統(tǒng)，為二元運算，如果運算是可結合的，則稱V為半群。獨異點：設V=是半群，假設eS是關于運算的單位元，則稱V是含幺半群，也叫做獨異點。有時也將獨異點V 記作 V=. 群設V=是獨異點，e G關于運算的單位元，假設aG，a1G，則稱V是群(Group). 通常將群記作G. 【定義10.1】群的階數(shù)：設是一

40、個群有限群：如果G是有限集，則稱為有限群階數(shù)：|G| 為該有限群的階數(shù)；無限群：如果G是無限集，則稱為無限群。平凡群：階數(shù)為1即只含單位元的群稱為平凡群【定義10.2】群的性質：設是一個群。1非平凡群中不可能有零元.2對于a,b G, 必存在唯一的* G,使得a * =b.3對于a,b,c G假設: ab = ac或ba = ca則必有b=c (消去律)。4運算表中的每一行或每一列都是一個置換。5除幺元e外,不可能有任何別的冪等元。元素的冪設G是群，aG，nZ，則a 的 n次冪【定義10.3】元素的階：設G是群，aG，使得等式ak=e 成立的最小正整數(shù)k 稱為元素a 的階，記作|a|=k，稱a

41、 為k 階元。假設不存在這樣的正整數(shù)k，則稱a 為無限階元。【定義10.4】冪運算性質：(1) aG，(a1)1=a(2) a,bG，(ab)1=b1a1(3) aG，anam = an+m，n, mZ(4) aG，(an)m = anm，n, mZ (5) 假設G為交換群，則 (ab)n = anbn.【定理10.1】元素的階的性質：G為群，aG且 |a| = r. 設k是整數(shù)，則(1) ak = e當且僅當r | k(r整除k)(2 )|a1| = |a|【定理10.3】子群：設G 是群，H 是G 的非空子集，如果H關于G中的運算構成群，則稱H是G 的子群, 記作HG。真子群：假設H是G

42、的子群，且HG，則稱H是G的真子群，記作HG.平凡子群：對任何群G都存在子群. G和e都是G 的子群，稱為G 的平凡子群.【定義10.5】子群判定定理設G為群，H是G的非空子集，則H是G的子群當且僅當(1) a,bH有abH；(2) aH有a1H。【定理10.4】子群判定定理二：設G為群，H是G的非空子集. H是G的子群當且僅當a,bH有ab1H.【定理10.5】子群判定定理三：設G為群，H是G的非空有窮子集，則H是G的子群當且僅當a,bH有abH. 【定理10.6】生成子群：設G為群，aG，令H=ak| kZ，則H是G的子群，稱為由a 生成的子群，記作.陪集設是群的一個子群,a G則:左陪集

43、aH := aH，由a所確定的H在G中的左陪集.右陪集Ha:=Ha陪集是左陪集與右陪集的統(tǒng)稱.【定義10.6】陪集性質：設H是群G的子群，則He = HaG 有aHaa,bG有：aHb ab1H Ha=Hb在G上定義二元關系R：a,bG, R ab1H則R是G上的等價關系，且aR = Ha.|Ha|=|H|【定理10.7】【定理10.8】拉格朗日定理：設G是有限群，H是G的子群，則|G| = |H|G:H 其中G:H 是H在G中的不同右陪集(或左陪集) 數(shù)，稱為H在G 中的指數(shù).【定理10.10】推論：1設G是n階群，則aG，|a|是n的因子，且an= e. 2對階為素數(shù)的群G，必存在aG使得

44、G = .阿貝爾群交換群：假設群G中的運算是可交換的，則稱G為交換群或阿貝爾群。循環(huán)群：設G是群，假設存在aG使得G=ak| kZ 則稱G是循環(huán)群，記作G=，稱a 為G 的生成元.n 階循環(huán)群:設G=是循環(huán)群，假設a是n 階元，則 G= a0=e, a1, a2, , an1 無限循環(huán)群:假設a 是無限階元，則 G= a0=e, a1, a2, 【定義10.7】循環(huán)群的生成元:設G=是循環(huán)群(1) 假設G是無限循環(huán)群，則G只有兩個生成元，即a和a1.(2)假設G是n階循環(huán)群，則G含有(n)個生成元. 對于任何小于n且與n 互質的數(shù)r0,1,n-1, ar是G的生成元.【定理10.11】循環(huán)群的

45、子群：(1)設G=是循環(huán)群，則G的子群仍是循環(huán)群；(2) 假設G=是無限循環(huán)群，則G的子群除e以外都是無限循環(huán)群；(3) 假設G=是n階循環(huán)群，則對n的每個正因子d，G恰好含有一個d 階子群?！径ɡ?0.12】環(huán)：設是代數(shù)系統(tǒng)，+和是二元運算. 如果滿足以下條件:(1) 構成交換群；(2) 構成半群；(3) 運算關于+運算適合分配律，則稱是一個環(huán). 【定義10.11】環(huán)的運算性質：設是環(huán)，則(1) aR，a0 = 0a = 0(2) a,bR，(a)b = a(b) = ab(3) a,b,cR，a(bc) = abac， (bc)a = baca(4) a1,a2,.,an,b1,b2,.,

46、bmR (n,m2) QUOTE 【定理10.14】設是環(huán)交換環(huán)：假設環(huán)中乘法 適合交換律，則稱R是交換環(huán)；含幺環(huán)：假設環(huán)中乘法 存在單位元，則稱R是含幺環(huán)；無零因子環(huán)：假設a,bR，ab=0 a=0b=0，則稱R是無零因子環(huán)。整環(huán)：設是一個代數(shù)系統(tǒng),假設滿足:(1) 是阿貝爾群；(2) 是可交換獨異點，且無零因子，即對a,bR, a0,b0 則a b0；(3) 運算對+是可分配的，則稱是整環(huán)域：設是一個代數(shù)系統(tǒng),假設滿足:(1) 是阿貝爾群；(2) 是阿貝爾群；(3) 運算對+是可分配的，則稱是域?！径x10.12】格：設是偏序集，如果*,yS，*,y都有最小上界和最大下界，則稱S關于偏序作

47、成一個格【定義11.1】格的代數(shù)系統(tǒng)定義：設是代數(shù)系統(tǒng), 和是二元運算, 如果和滿足交換律、結合律和吸收律, 則構成格【定義11.3】對偶命題：設f 是含有格中元素以及符號 =, , ,和的命題. 令f*是將f 中的替換成,替換成,替換成,替換成所得到的命題. 稱f* 為f 的對偶命題【定義11.2】格的對偶原理：設 f 是含有格中元素以及符號=,和等的命題. 假設 f 對一切格為真, 則 f 的對偶命題 f*也對一切格為真.格的性質：設是格, 則運算和適合交換律、結合律、冪等律和吸收律, 即(1) a,bL 有ab = ba, ab = ba(2) a,b,cL 有 (ab)c = a(bc

48、), (ab)c = a(bc)(3) aL 有aa = a, aa = a(4) a,bL 有a(ab) = a, a(ab) = a 【定理11.1】格的序與運算性質：設L是格, 則a,bL有a bab = aab = b 【定理11.3】格的保序性質：設L是格, a,b,c,dL，假設a b 且c d, 則ac bd, acbd【定理11.4】子格：設是格, S是L的非空子集, 假設S關于L中的運算和仍構成格, 則稱S是L的子格【定義11.4】分配格：設是格, 假設a,b,cL,有a(bc) = (ab)(ac) a(bc) = (ab)(ac) 則稱L為分配格.【定義11.5】分配格的

49、判別：設L是格, 則L是分配格當且僅當L不含有與鉆石格或五角格同構的子格【定理11.5】全下界：設L是格,假設存在aL使得*L有 a *, 則稱a為L的全下界；全上界：設L是格,假設存在bL使得*L有 * b, 則稱b為L的全上界?！径x11.6】有界格：設L是格，假設L存在全下界和全上界, 則稱L 為有界格，一般將有界格L記為.【定義11.7】有界格的性質：設是有界格,則aL有a0 = 0,a0 = a,a1 = a, a1=1補元：設是有界格, aL, 假設存在bL 使得ab = 0 和ab = 1成立, 則稱b是a的補元【定義11.8】有界分配格的補元惟一性定理：設是有界分配格. 假設L

50、中元素 a 存在補元, 則存在惟一的補元.【定理11.6】有補格 :設是有界格,假設L中所有元素都有補元存在, 則稱L為有補格.【定義11.9】布爾格布爾代數(shù)：如果一個格是有補分配格, 則稱它為布爾格或布爾代數(shù). 布爾代數(shù)標記為, 為求補運算. 【定義11.10】布爾代數(shù)的代數(shù)系統(tǒng)定義：設是代數(shù)系統(tǒng), 和是二元運算. 假設和運算滿足：(1) 交換律, 即a,bB有 ab = ba, ab = ba (2) 分配律, 即a,b,cB有a(bc) = (ab)(ac), a(bc) = (ab) (ac)(3) 同一律, 即存在0,1B, 使得aB有a 1 = a, a0 = a(4) 補元律,

51、即aB, 存在 aB 使得 a a = 0, aa = 1 則稱 是一個布爾代數(shù).【定義11.11】布爾代數(shù)的性質：設是布爾代數(shù), 則(1) aB, (a) = a .(2) a,bB, (ab) = ab, (ab) = ab德摩根律【定理11.7】原子：設 L 是格, 0L, aL假設bL有 0 b a b = a, 則稱 a 是 L 中的原子【定義11.12】有限布爾代數(shù)的表示定理：設B是有限布爾代數(shù), A是B的全體原子構成的集合, 則B同構于A的冪集代數(shù)P(A).【定理11.8】推論1：任何有限布爾代數(shù)的基數(shù)為2n, nN.推論2：任何等勢的有限布爾代數(shù)都是同構的圖論無序積：AB=(*

52、,y) | *AyB無向圖G = , 其中(1) V 為頂點集，元素稱為頂點；(2) E為VV 的多重集，其元素稱為無向邊，簡稱邊。【定義14.1】有向圖D=, 只需注意E是VV 的多重子集【定義14.2】n階圖：頂點個數(shù)為n.零圖：邊的個數(shù)為0. n 階零圖記為Nn平凡圖：1階零圖N1空圖：標定圖與非標定圖：依據頂點和邊是否命名標識。有向圖的基圖：有向邊改為無向邊后的圖。頂點與邊的關聯(lián)關系ek=(vi , vj) 關聯(lián)：ek與vi , vj關聯(lián)關聯(lián)次數(shù)：0(不關聯(lián))，1(vi vj )， 2(vi =vj ) 環(huán)：與同一頂點關聯(lián)次數(shù)為2的邊；孤立點：不與任何邊關聯(lián)的頂點。頂點相鄰：兩個頂點之

53、間有邊。邊相鄰：兩條邊有公共端點。平行邊：關聯(lián)的端點一樣的兩條邊有向圖中方向一樣。vV(G) (G為無向圖) v的鄰域：v的閉鄰域：v 的關聯(lián)集：vV(D) (D為有向圖)v的后繼元集：v的先驅元集：v的鄰域：v多重圖：含平行邊的圖；簡單圖：即不含平行邊又不含環(huán)的圖?！径x14.3】度度數(shù)：設G=為無向圖, vV, d(v)v的度數(shù), 簡稱度設D=為有向圖, vV,出度d+(v)v入度d(v)v作為邊的終點的次數(shù)度度數(shù)d(v)d+(v)+ d(v)最大度(G)=ma*d(v)|vV(G)最小度(G)= mind(v)|vV(G)+(D)=ma*d+(v)|vV(D)+(D)=mind+(v)|

54、vV(D)(D)=ma*d-(v)|vV(D)(D)=mind-(v)|vV(D)(D)=ma*d(v)|vV(D)(D)=mind(v)|vV(G)奇頂點度：度為奇數(shù)的頂點偶度頂點：度為偶數(shù)的頂點【定義14.4】握手定理：設G=為任意無向圖，V=v1,v2,vn, |E|=m, 則設D=為任意有向圖，V=v1,v2,vn, |E|=m, 則【定理14.1】【定理14.2】推論：任何圖 (無向或有向) 中，奇度頂點的個數(shù)是偶數(shù).度數(shù)列：V=v1, v2, , vn為無向圖G的頂點集，稱d(v1), d(v2), , d(vn)為G的度數(shù)列V=v1, v2, , vn為有向圖D的頂點集度數(shù)列：d

55、(v1), d(v2), , d(vn)出度列：d+(v1), d+(v2), , d+(vn)入度列：d(v1), d(v2), , d(vn) 非負整數(shù)列d=(d1, d2, , dn)V=v1,v2,vnnG,使得d(vi)=di，則稱d是可圖化的。特別的，假設得到的圖是簡單圖，則稱d是可簡單圖化的。非負整數(shù)列d=(d1, d2, , dn)是可圖化的當且僅當為偶數(shù).【定理14.3】設G為任意n階無向簡單圖，則(G) n -1.【定理14.4】圖的同構：設G1=, G2=為兩個無向圖(兩個有向圖)，假設存在雙射函數(shù)f :V1V2，對于vi, vjV1, (vi,vj)E1 當且僅當 (f

56、(vi), f(vj)E2 E1 當且僅當 E2 )并且, (vi,vj)與 (f(vi), f(vj)的重數(shù)一樣，則稱G1與G2是同構的，記作G1G2.【定義14.5】n (n1) 階無向完全圖每個頂點與其余頂點均相鄰的無向簡單圖，記作Kn.邊數(shù)n (n1)階有向完全圖每對頂點之間均有兩條方向相反的有向邊的有向簡單圖.邊數(shù)n (n1) 階競賽圖基圖為Kn的有向簡單圖.【定義14.6】邊數(shù)n 階k正則圖：=k的無向簡單圖。【定義14.7】邊數(shù)G=, G=子圖：VV 且EE ,則稱G為G的子圖，記為GG ，稱G為G的母圖;生成子圖：假設GG且V=V，則稱G為G的生成子圖；真子圖：假設VV或EE，

57、稱G為G的真子圖；導出子圖：VVV且V的導出子圖，記作GV；EEE且E的導出子圖，記作GE.【定義14.8】補圖：設G=為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作.假設G , 則稱G是自補圖【定義14.9】Gv從G中將v及關聯(lián)的邊去掉GV從G中刪除V中所有的頂點Ge將e從G中去掉GE刪除E中所有邊【定義14.10】通路與回路：給定圖G=無向或有向的，G中頂點與邊的交替序列 = v0e1v1e2elvl稱為從v0到vl的通路，其中vi1, vi 是 ei 的端點.；假設 v0=vl，為回路。中的邊數(shù)稱為通路的長度. 簡單通路與簡單回路

58、：所有邊各異。初級通路(路徑)與初級回路(圈)：中所有頂點各異v0=vl 除外，所有邊也各異復雜通路與復雜回路：有邊重復出現(xiàn)【定義14.11】在n 階圖G中，假設從頂點vi 到vjvivj存在通路，則從vi 到vj 存在長度小于或等于n1 的通路.【定理14.5】推論：在n 階圖G中，假設從頂點vi到vjvivj存在通路，則從vi到vj 存在長度小于或等于n1的初級通路路徑在一個n 階圖G中，假設存在vi 到自身的回路，則一定存在vi 到自身長度小于或等于n 的回路.【定理14.6】推論：在一個n 階圖G中，假設存在vi 到自身的簡單回路，則一定存在長度小于或等于n 的初級回路.頂點的連通性：

59、G=為無向圖，假設vi 與vj 之間有通路，則稱vi 與vj是連通的，記為vivj 假設u,vV，uv，則稱G是連通的；【定義14.12】連通分支：V/R=V1,V2,Vk，稱GV1, GV2, ,GVk為連通分支，其個數(shù)稱為連通分支數(shù)，記為p(G)【定義14.13】短程線uv：，u與v之間長度最短的通路距離d(u,v)：短程線的長度【定義14.14】d(u,v)0, uv時d(u,v)=d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)G=, VV點割集p(GV)p(G)，且對任意VV均有p(GV)=p(G)V為點割集割點v為點割集，則v為割點【定義14.15】G=, EE邊割

60、集p(GE)p(G)且有極小性則E是邊割集割邊橋e為邊割集e是割邊橋【定義14.16】G為連通非完全圖點連通度(G) = min |V |V 為點割集 規(guī)定(Kn) = n1;假設G非連通，(G) = 0k-連通圖：假設(G)k，則稱G為k-連通圖【定義14.17】設G為連通圖邊連通度(G) = min|E|E為邊割集規(guī)定：假設G非連通，則(G) = 0r 邊-連通圖：假設(G)r，則稱G是r 邊-連通圖【定義14.18】, , 之間的關系：(G)(G)(G)【定理14.7】D=為有向圖可達vi vj：存在從vi 到vj 有通路相互可達vi vj： vi vjvj vi【定義14.19】D=為