離散數(shù)學(xué)知識(shí)點(diǎn)

離散數(shù)學(xué)知識(shí)點(diǎn)離散數(shù)學(xué)知識(shí)點(diǎn)/離散數(shù)學(xué)知識(shí)點(diǎn)說(shuō)明： 定義：紅色表示。 定理性質(zhì)：橙色表示。 公式：藍(lán)色表示。 算法:綠色表示 頁(yè)碼：灰色表示數(shù)理邏輯：命題公式：命題，聯(lián)結(jié)詞(，，，，)，合式公式，子公式公式的真值：賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式范式：析取范式，極小項(xiàng)，主析取范式，合取范式，極大項(xiàng)，主合取范式聯(lián)結(jié)詞的完備集：真值函數(shù)，異或，條件否定，與非，或非，聯(lián)結(jié)詞完備集推理理論：重言蘊(yùn)含式，有效結(jié)論，P規(guī)則，T規(guī)則，規(guī)則，推理謂詞與量詞:謂詞，個(gè)體詞，論域，全稱(chēng)量詞，存在量詞項(xiàng)與公式:項(xiàng)，原子公式，合式公式，自由變?cè)s束變?cè)?，轄域，換名，代入公式語(yǔ)義:解釋?zhuān)x值，有效的，可滿(mǎn)足的，不可滿(mǎn)足的前束范式:前束范式推理理論:邏輯蘊(yùn)含式，有效結(jié)論，-規(guī)則（），+規(guī)則（），-規(guī)則()，+規(guī)則(),推理集合論：集合:集合,外延性原理,,,,空集,全集,冪集,文氏圖,交,并,差,補(bǔ),對(duì)稱(chēng)差關(guān)系:序偶,笛卡爾積,關(guān)系,,,關(guān)系圖,空關(guān)系,全域關(guān)系,恒等關(guān)系關(guān)系性質(zhì)與閉包:自反的,反自反的,對(duì)稱(chēng)的,反對(duì)稱(chēng)的,傳遞的,自反閉包r(R),對(duì)稱(chēng)閉包s(R),傳遞閉包t(R)等價(jià)關(guān)系:等價(jià)關(guān)系,等價(jià)類(lèi),商集,劃分偏序關(guān)系:偏序,哈斯圖,全序(線(xiàn)序),極大元/極小元,最大元/最小元,上界/下界函數(shù):函數(shù),常函數(shù),恒等函數(shù),滿(mǎn)射,入射,雙射，反函數(shù),復(fù)合函數(shù)集合基數(shù):基數(shù),等勢(shì),有限集/無(wú)限集,可數(shù)集,不可數(shù)集代數(shù)結(jié)構(gòu)：運(yùn)算與其性質(zhì)：運(yùn)算，封閉的,可交換的,可結(jié)合的,可分配的,吸收律,冪等的，幺元,零元,逆元代數(shù)系統(tǒng)：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)，同態(tài)，同構(gòu)。群與子群：半群,子半群,元素的冪，獨(dú)異點(diǎn)，群，群的階數(shù)，子群,平凡子群，陪集，拉格朗日（）定理阿貝爾群和循環(huán)群：阿貝爾群(交換群)，循環(huán)群,生成元環(huán)與域：環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域格與布爾代數(shù)：格，對(duì)偶原理，子格，分配格，有界格，有補(bǔ)格，布爾代數(shù)，有限布爾代數(shù)的表示定理圖論：圖的基本概念：無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖，握手定理，圖的同構(gòu)圖的連通性:通路，回路，簡(jiǎn)單通路，簡(jiǎn)單回路（跡）初級(jí)通路（路徑），初級(jí)回路（圈），點(diǎn)連通，連通圖，點(diǎn)割集，割點(diǎn)，邊割集，割邊，點(diǎn)連通度，邊連通度，弱連通圖，單向連通圖，強(qiáng)連通圖，二部圖（二分圖）圖的矩陣表示：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣歐拉圖與哈密頓圖：歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖無(wú)向樹(shù)與根樹(shù)：無(wú)向樹(shù)，生成樹(shù)，最小生成樹(shù)，，根樹(shù)，m叉樹(shù)，最優(yōu)二叉樹(shù)，算法平面圖:平面圖，面，歐拉公式，定理數(shù)理邏輯：命題：具有確定真值的陳述句。否定詞符號(hào)：設(shè)p是一個(gè)命題，p稱(chēng)為p的否定式。p是真的當(dāng)且僅當(dāng)p是假的。p是真的當(dāng)且僅當(dāng)p是假的。【定義1.1】合取詞符號(hào)：設(shè)p，q是兩個(gè)命題，命題“p并且q”稱(chēng)為p，q的合取，記以pq，讀作p且q。pq是真的當(dāng)且僅當(dāng)p和q都是真的?！径x1.2】析取詞符號(hào)：設(shè)p，q是兩個(gè)命題，命題“p或者q”稱(chēng)為p，q的析取，記以pq，讀作p或q。pq是真的當(dāng)且僅當(dāng)p，q中至少有一個(gè)是真的?！径x1.3】蘊(yùn)含詞符號(hào)：設(shè)p，q是兩個(gè)命題，命題“如果p，則q”稱(chēng)為p蘊(yùn)含q，記以pq。pq是假的當(dāng)且僅當(dāng)p是真的而q是假的?！径x1.4】等價(jià)詞符號(hào)：設(shè)p，q是兩個(gè)命題，命題“p當(dāng)且僅當(dāng)q”稱(chēng)為p等價(jià)q，記以pq。pq是真的當(dāng)且僅當(dāng)p，q或者都是真的，或者都是假的?！径x1.5】合式公式:命題常元和變?cè)?hào)是合式公式；若A是合式公式，則(A)是合式公式，稱(chēng)為A的否定式；若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)是合式公式；所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符號(hào)串。子公式:如果Ｘ是合式公式A的一部分，且Ｘ本身也是一個(gè)合式公式，則稱(chēng)Ｘ為公式A的子公式?！径x1.6】賦值（指派，解釋?zhuān)涸O(shè)是命題變?cè)?，則稱(chēng)函數(shù)v：{1，0}是一個(gè)真值賦值。【定義1.8】真值表：公式A在其所有可能的賦值下所取真值的表，稱(chēng)為A的真值表?！径x1.9】重言式（永真式）:任意賦值v，vA矛盾式（永假式）:任意賦值v，有vA【定義1.10】等值式：若等價(jià)式AB是重言式，則稱(chēng)A與B等值，記作AB?！径x2.1】基本等值式 雙重否定律 AA冪等律AAA,AAA交換律ABBA,ABBA結(jié)合律(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蘊(yùn)涵等值式ABAB等價(jià)等值式AB(AB)(BA)假言易位ABBA等價(jià)否定等值式ABAB歸謬論(AB)(AB)A置換規(guī)則：設(shè)Ｘ是公式A的子公式,ＸY。將A中的Ｘ（可以是全部或部分X）用Y來(lái)置換，所得到的公式B，則AB。文字:設(shè)A（命題變?cè)?則A和A都稱(chēng)為命題符號(hào)A的文字，其中前者稱(chēng)為正文字，后者稱(chēng)為負(fù)文字?！径x2.2】析取范式：形如A1A2…(n1)的公式稱(chēng)為析取范式，其中(1,…)是由文字組成的合取范式。合取范式：形為A1A2…(n1)的公式稱(chēng)為合取范式，其中A1,…都是由文字組成的析取式?！径x2.3】極小項(xiàng)：文字的合取式稱(chēng)為極小項(xiàng)，其中公式中每個(gè)命題符號(hào)的文字都在該合取式中出現(xiàn)一次。極大項(xiàng)：文字的析取式稱(chēng)為極大項(xiàng)，其中公式中每個(gè)命題符號(hào)的文字都在該合取式中出現(xiàn)一次?！径x2.4】主析取范式：給定的命題公式的主析取范式是一個(gè)與之等價(jià)的公式，后者由極小項(xiàng)的析取組成。主合取范式：給定的命題公式的主合取范式是一個(gè)與之等價(jià)的公式，后者由極大項(xiàng)的合取組成。【定義2.5】公式的真值表中真值為F的指派所對(duì)應(yīng)的極大項(xiàng)的合取，即為此公式的主合取范式。真值函數(shù)：稱(chēng)F:{0,1}n{0,1}為n元真值函數(shù).【定義2.6】聯(lián)結(jié)詞的完備集：設(shè)C是聯(lián)結(jié)詞的集合，若對(duì)于任意一個(gè)合式公式均存在一個(gè)與之等價(jià)的公式，而后者只含有C中的聯(lián)結(jié)詞，則稱(chēng)C是聯(lián)結(jié)詞的完備集?！径x2.7】{，，，，}，{，，},{，}，{，}，{，}是聯(lián)結(jié)詞的完備集。【定理2.6】c異或PQ： (PQ)c條件否定PQ：(PQ)與非PQ： (PQ)或非PQ： (PQ)【定義2.8】{},{↓}都是聯(lián)結(jié)詞的完備集【定理2.7】重言蘊(yùn)含式：當(dāng)且僅當(dāng)PQ是一個(gè)重言式時(shí)，稱(chēng)P重言蘊(yùn)含Q，記為PQ。有效結(jié)論：設(shè)A、C是兩個(gè)命題公式，若AC，稱(chēng)C是A的有效結(jié)論?！径x3.1】推理定律——重言蘊(yùn)涵式 1.A(AB) 附加律2.(AB)A 化簡(jiǎn)律3.(AB)AB 假言推理4.(AB)BA 拒取式5.(AB)BA 析取三段論6.(AB)(BC)(AC) 假言三段論7.(AB)(BC)(AC) 等價(jià)三段論8.(AB)(CD)(AC)(BD) 構(gòu)造性二難 (AB)(AB)B 構(gòu)造性二難(特殊形式)9.(AB)(CD)(BD)(AC) 破壞性二難形式系統(tǒng):一個(gè)形式系統(tǒng)I由下面四個(gè)部分組成： (1)非空的字母表，記作A(I). (2)A(I)中符號(hào)構(gòu)造的合式公式集，記作E(I). (3)E(I)中一些特殊的公式組成的公理集，記作(I). (4)推理規(guī)則集，記作R(I).記<A(I)(I)(I)(I)>,其中<A(I)(I)>是I的形式語(yǔ)言系統(tǒng),<(I)(I)>是I的形式演算系統(tǒng).自然推理系統(tǒng):無(wú)公理,即(I)=公理推理系統(tǒng):推出的結(jié)論是系統(tǒng)中的重言式,稱(chēng)作定理【定義3.2】P規(guī)則：在推導(dǎo)過(guò)程中,可以隨時(shí)添加前提。T規(guī)則：在推導(dǎo)過(guò)程中,可以引入公式S，它是由其前題的一個(gè)或多個(gè)公式借助重言、蘊(yùn)含而得到的。推理（證明）：從前提A1,A2,,到結(jié)論B的推理是一個(gè)公式序列C1,C2,,.其中(1il)是某個(gè),或者可由序列中前面的公式應(yīng)用推理規(guī)則得到,并且?！径x3.3】規(guī)則(演繹定理)：若{R}S，則RS,其中為命題公式的集合。個(gè)體詞：用于表示命題中主語(yǔ)部分的符號(hào)或符號(hào)串。個(gè)體常元表示確指?jìng)€(gè)體。個(gè)體變?cè)硎静淮_指?jìng)€(gè)體。個(gè)體域:個(gè)體變?cè)娜≈捣秶?，常用D表示。量詞：限定個(gè)體數(shù)量特性的詞。全稱(chēng)量詞：對(duì)所有的存在量詞：有些謂詞語(yǔ)言：用符號(hào)串表示個(gè)體、謂詞、量詞和命題 個(gè)體變?cè)?hào)：x，y，z，… 個(gè)體常元符號(hào)：a，b，c，… 函數(shù)符號(hào)：f，g，… 謂詞符號(hào)：P，Q，R，… 命題常元符號(hào)：， 量詞符號(hào)：， 連接詞符號(hào)：,,,, 輔助符號(hào)：）,（ 【定義4.1】項(xiàng):(1)個(gè)體常元和變?cè)琼?xiàng)；(2)若f是n元函數(shù)符號(hào)，t1,…,是項(xiàng)，則f(t1,…,)是項(xiàng)；(3)僅僅有限次使用(1)，(2)產(chǎn)生的符號(hào)串是項(xiàng)?！径x4.2】原子公式:若P是一個(gè)元謂詞符號(hào)，t1,…是項(xiàng),則P(t1,…)是原子公式。【定義4.3】合式公式：(1)原子公式是公式；(2)若A是合式公式，則(A)是合式公式；(3)若A，B是公式，則(AB)，(AB)，AB)，(AB)是公式；(4)若A是公式，x是變?cè)瑒t，是公式；(5)僅僅有限次使用１～４得到的符號(hào)串才是合式公式?！径x4.4】設(shè)公式的一個(gè)子公式為xA或xA。則稱(chēng)：指導(dǎo)變?cè)簒是或的指導(dǎo)變?cè)?。轄域：A是相應(yīng)量詞的轄域。約束出現(xiàn)：轄域中x的一切出現(xiàn)，以與(x)中的x稱(chēng)為x在中的約束出現(xiàn)。自由出現(xiàn)：變?cè)姆羌s束出現(xiàn)。約束變?cè)杭s束出現(xiàn)的變?cè)?。自由變?cè)鹤杂沙霈F(xiàn)的變?cè)?。【定義4.5】封閉的：一個(gè)公式A是封閉的，若其中不含自由變?cè)！径x4.6】變?cè)獡Q名：（1）換名的范圍是量詞的指導(dǎo)變?cè)?與其相應(yīng)轄域中的變?cè)?，其余部分不變。?）換名時(shí)最好選用轄域中未出現(xiàn)的變?cè)?。變?cè)耄捍雽?duì)自由變?cè)M(jìn)行。不能改變約束關(guān)系。解釋?zhuān)褐^詞語(yǔ)言的一個(gè)解釋(D,)包括：(1)非空集合D，稱(chēng)之為論域；(2)對(duì)應(yīng)于每一個(gè)個(gè)體常元a，(a)D；(3)對(duì)應(yīng)于每一個(gè)n元函數(shù)符號(hào)f都有一個(gè)函數(shù)(f)D；(4)對(duì)應(yīng)于每一個(gè)n元謂詞符號(hào)A都有一個(gè)n元關(guān)系(A)?！径x4.7】賦值：解釋I中的賦值v為每一個(gè)個(gè)體變?cè)獂指定一個(gè)值v(x）D，即設(shè)V為所個(gè)體變?cè)募?，則賦值v是函數(shù)D.可滿(mǎn)足的：給定公式A，若在某一解釋中至少有一種賦值使A取值為1，則稱(chēng)A為可滿(mǎn)足的。否則稱(chēng)A是不可滿(mǎn)足的。等值式AB：若AB是有效的【定義5.1】幾類(lèi)等值式（1）命題公式的推廣.P(x)Q(x)P(x)Q(x)（2）否定深入xP(x)x(P(x))(x)x(P(x))（3）量詞作用域的擴(kuò)張與收縮 設(shè)B中不含x的自由出現(xiàn)，則x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)（4）量詞分配等值式x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x)（5）多個(gè)量詞的使用 xyA()yxA() xyA()yxA()置換規(guī)則：設(shè)(A)是含A的公式,那么,若AB,則(A)(B).換名規(guī)則：設(shè)A為一公式，將A中某量詞轄域中個(gè)體變項(xiàng)的所有約束出現(xiàn)與相應(yīng)的指導(dǎo)變?cè)獡Q成該量詞轄域中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，其余部分不變，設(shè)所得公式為A，則AA.前束范式：如果謂詞公式A有如下形狀：Q1x1…，其中或者是，或者是，1，…，n，M是不含量詞的公式，Q1x1…稱(chēng)為首標(biāo)，M稱(chēng)為母式。【定義5.2】前束范式存在定理：對(duì)于任意謂詞公式，都存在與它邏輯等價(jià)的前束范式?！径ɡ?.1】前束范式的算法：步1.對(duì)約束出現(xiàn)的變?cè)M(jìn)行必要的換名，使得約束出現(xiàn)的變?cè)ゲ幌嗤也慌c任何自由變?cè)２?.將所有的否定號(hào)深入到量詞后面。 步3.將量詞符號(hào)移至公式最外層。邏輯蘊(yùn)含式AC：當(dāng)且僅當(dāng)AC是有效的。幾類(lèi)邏輯蘊(yùn)涵式 第一組命題邏輯推理定理的代換實(shí)例 如,(x)(y)(x)第二組基本等值式生成的推理定理 如,(x)(x),(x)(x)(x)xF(x),xF(x)(x)第三組其它常用推理定律 (1)(x)(x)x(A(x)B(x)) (2)x(A(x)B(x))(x)(x) (3)x(A(x)B(x))(x)(x) (4)x(A(x)B(x))(x)(x)推理規(guī)則 -規(guī)則()：?xAx∴Ay或? +規(guī)則()：Ax∴?xAx -規(guī)則()：∴?xAx∴Ac x +規(guī)則()：Ay∴?xAx或B Ac∴? 先用，再用自然推理系統(tǒng)NL：1.字母表.同一階語(yǔ)言L(fǎng)的字母表2.合式公式.同L的合式公式3.推理規(guī)則:(1)前提引入規(guī)則 (2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則(6)化簡(jiǎn)規(guī)則(7)拒取式(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則(12)-規(guī)則(13)+規(guī)則(14)-規(guī)則(15)+規(guī)則 【定義5.3】集合論：ABx(xAxB)【定義6.1】A=BABBA 【定義6.2】ABABAB 【定義6.3】A?Bx(xAxB)空集：不含有任何元素的集合【定義6.4】空集是任何集合的子集?！径ɡ?.1】?jī)缂疨(A)={x|xA}【定義6.5】如果，則(A)2n全集E：包含了所有元素的集合【定義6.6】并AB={x|xAxB}交AB={x|xAxB}差（相對(duì)補(bǔ)）AB={x|xAxB}【定義6.7】對(duì)稱(chēng)差A(yù)B=(AB)(BA)【定義6.8】補(bǔ)（絕對(duì)補(bǔ)）A=EA={A}【定義6.9】廣義并A={x|z(zAxz)}【定義6.10】廣義交A={x|z(zAxz)}【定義6.11】集合恒等式1.只涉與一個(gè)運(yùn)算的算律：交換AAAAAA結(jié)合(AB)(BC)(AB)(BC)(AB)(BC)冪等AA2．涉與兩個(gè)不同運(yùn)算的算律：與與分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)A(AB)3．涉與補(bǔ)運(yùn)算的算律：律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC雙重否定4．涉與全集和空集的算律：E補(bǔ)元律AA零律A=A同一律AA否定序偶（有序?qū)Γ河蓛蓚€(gè)元素x和y，按照一定的順序組成的二元組，記作<>.【定義7.1】笛卡兒積:設(shè)為集合，A與B的笛卡兒積記作AB定義為AB={<>|xAyB}.【定義7.2】笛卡爾積性質(zhì)：或時(shí),A“”不滿(mǎn)足結(jié)合律A(BC)=(AB)(AC)關(guān)系：（兩個(gè)定義）(1)序偶的一個(gè)集合,確定了一個(gè)二元關(guān)系R。R中任一序偶<>,可記作<x,y>R或【定義7.3】(2)笛卡爾積的子集：RAB【定義7.4】空關(guān)系:全域關(guān)系：A×B恒等關(guān)系={<>|x∈A} 【定義7.5】關(guān)系矩陣：若{x1,x2,…,}，{y1,y2,…,}，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣=[]mn,其中=1<,>R.關(guān)系圖：若{x1,x2,…,}，R是從A上的關(guān)系，R的關(guān)系圖是<A,R>,其中A為結(jié)點(diǎn)集，R為邊集.如果<>屬于關(guān)系R，在圖中就有一條從到的有向邊.前域(定義域)(R)={y.<>R} 值域(R)={x.<>R}域(R)= 【定義7.6】逆關(guān)系R1={<y,x>|<x,y>R} 【定義7.7】互逆(R1)1=R(RS)1=R1S1(RS)1=R1S1(AB)1=BA(R-S)1=R1-S1復(fù)合關(guān)系RS={<x,z>|y(<x,y>R<y,z>S)}【定義7.8】(RS)(SP)=RR…R設(shè)RXYZ,則(RS)1=S1R1【定理7.2】R在A上的限制R?A={<>|∧x∈A} A在R下的像R[A](R?A) 【定義7.9】自反的：若x∈A，都有<>R,則稱(chēng)R是自反的反自反的：若x∈A，都有<>R,則稱(chēng)R是反自反的.【定義7.11】對(duì)稱(chēng)的：對(duì)任意A,滿(mǎn)足,若<>R,則<>R反對(duì)稱(chēng)的：對(duì)任意A,滿(mǎn)足，若<>R且<>R,則【定義7.12】傳遞的：對(duì)任意的A,滿(mǎn)足:若<>R且<>R,則<>R,則稱(chēng)R是傳遞的【定義7.13】自反閉包（對(duì)稱(chēng)、傳遞）：設(shè)R是A上的二元關(guān)系,如果有另一個(gè)關(guān)系R'滿(mǎn)足:R'是自反（對(duì)稱(chēng)、傳遞）的;R'R;對(duì)于任何自反的關(guān)系R”,若R"R,則有R"R'.則稱(chēng)關(guān)系R'為R的自反閉包.記為r(R)（

對(duì)稱(chēng)閉包s(R)和傳遞閉包t(R)）?！径x7.14】設(shè)R為A上的關(guān)系,則有(1)r(R)∪(2)s(R)∪R1(3)t(R)∪R2∪R3∪…（若，則t(R)∪R2∪…∪）等價(jià)關(guān)系：設(shè)R為集合A上的一個(gè)二元關(guān)系。若R是自反的,對(duì)稱(chēng)的,傳遞的,則稱(chēng)R為A上的等價(jià)關(guān)系【定義7.15】等價(jià)類(lèi)：設(shè)R為集合A上的等價(jià)關(guān)系,對(duì)aA,定義:[a]R={A且<>R}稱(chēng)之為元素a關(guān)于R的等價(jià)類(lèi)?！径x7.16】給定A上的等價(jià)關(guān)系R,對(duì)于A有<>當(dāng)且僅當(dāng)[a][b]R【定理17.4】商集：設(shè)R是A上的等價(jià)關(guān)系，定義{[a]A}稱(chēng)之為A關(guān)于R的商集.【定義7.17】劃分：設(shè)A為非空集合,若A的子集族π(πP(A))滿(mǎn)足: (1)π (2)xy(π∧x≠yx∩) (3)∪π=A則稱(chēng)π是A的一個(gè)劃分,稱(chēng)π中的元素為A的劃分塊.【定義7.18】給定集合A上的等價(jià)關(guān)系R,則商集是A的一個(gè)劃分.集合A的一個(gè)劃分π誘導(dǎo)出A上的一個(gè)等價(jià)關(guān)系R.R定義為{<>|A且在π的同一分塊中}設(shè)R1和R2為非空集合A上的一個(gè)等價(jià)關(guān)系,則R1=R2當(dāng)且僅當(dāng)1=2.偏序：設(shè)A是一個(gè)集合.如果A上的二元關(guān)系R是自反的,反對(duì)稱(chēng)的和傳遞的,則稱(chēng)R是A上的一個(gè)偏序關(guān)系.記R為“”,且稱(chēng)序偶<A,>為偏序集?！径x7.19】【定義7.22】全序（線(xiàn)序）：設(shè)<A,>為偏序集,若對(duì)任意的A滿(mǎn)足:xy或yx則稱(chēng)為全序關(guān)系.<A,>為全序集.【定義7.21】覆蓋：設(shè)<A,>為偏序集,若A,xy且沒(méi)有其它元素z滿(mǎn)足xy,則稱(chēng)y覆蓋x.記{<>A且y覆蓋x}【定義7.23】哈斯圖：作圖規(guī)則用小元圈代表元素;若xy且xy,則將代表y的小元圈畫(huà)在代表x的小元圈之上;若<>,則在之間用直線(xiàn)連接。你極小元/極大元：設(shè)<A,>為偏序集,BA(1)對(duì)bB，若B中不存在x滿(mǎn)足:bx且xb則稱(chēng)b為B的極小元.(2)對(duì)bB，若B中不存在x滿(mǎn)足:bx且bx則稱(chēng)b為B的極大元.最小元/最大元：設(shè)<A,>為偏序集A,若有某個(gè)bB(1)對(duì)于B中每一個(gè)元素x都有bx，則稱(chēng)b為B的最小元.(2)對(duì)于B中每一個(gè)元素x都有xb，則稱(chēng)b為B的最大元.【定義7.24】下界/上界：設(shè)<A,>為偏序集,BA (1)若有aA,且對(duì)xB滿(mǎn)足ax，則稱(chēng)a為B的下界。進(jìn)一步:設(shè)a為B的下界,若B的所有下界y均有ya,則稱(chēng)a為B的下確界，記為B。 (2)若有aA,且對(duì)xB滿(mǎn)足xa，則稱(chēng)a為B的上界。進(jìn)一步:設(shè)a為B的上界,若B的所有上界y均有ay,則稱(chēng)a為B的上確界，記為B?！径x7.25】函數(shù)：設(shè)為兩個(gè)集合XY,若對(duì)xX,!(唯一的)yY,滿(mǎn)足:<>f,則稱(chēng)f為函數(shù).記為Y定義域:值域:(有時(shí)記為f(X))={f(x)X}【定義8.1】函數(shù)相等：設(shè)f和g都是從A到B的函數(shù),若對(duì)任意xA,有f(x)(x),則稱(chēng)f和g相等.記為【定義8.2】函數(shù)的個(gè)數(shù)：設(shè),.記{:AB},則|滿(mǎn)射(到上映射)：設(shè)f:XY,若=Y,則稱(chēng)f為滿(mǎn)射的.入射（單射）(一對(duì)一映射)：設(shè)f:XY,對(duì)x1,x2X,滿(mǎn)足:若x1x2,則f(x1)f(x2),稱(chēng)f為入射的.雙射(一一對(duì)應(yīng)映射)：設(shè)Y,若f既是滿(mǎn)射的,又是入射的.則稱(chēng)f是雙射的.【定義8.6】常函數(shù):設(shè)→B,如果存在c∈B使得對(duì)所有的x∈A都有f(x),則稱(chēng)→B是常函數(shù).恒等函數(shù):稱(chēng)A上的恒等關(guān)系為A上的恒等函數(shù),對(duì)所有的x∈A都有(x).單調(diào)遞增:設(shè)<A,?>,<B,?>為偏序集，→B，如果對(duì)任意的x1,x2∈A,x1?x2,就有f(x1)?f(x2),則稱(chēng)f為單調(diào)遞增的；嚴(yán)格單調(diào)遞增:如果對(duì)任意的x1,x2∈A,x1?x2,就有f(x1)?f(x2),則稱(chēng)f為嚴(yán)格單調(diào)遞增的.類(lèi)似的也可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù) 特征函數(shù)：設(shè)A為集合,對(duì)于任意的A'A,A'的特征函數(shù)A'→{0,1}定義為A'(a)=1,a∈A';A'(a)=0,a∈AA'自然映射：設(shè)R是A上的等價(jià)關(guān)系,令→；g(a)=[a],a∈A稱(chēng)g是從A到商集的自然映射 【定義8.7】復(fù)合函數(shù)：設(shè)Z,定義:fg={<>X且zZ且可找到y(tǒng)Y使(x)(y)}稱(chēng)fg為f與g的復(fù)合函數(shù).設(shè)→B,→C

(1)如果→B,→C是滿(mǎn)射的,則f→C也是滿(mǎn)射的(2)如果→B,→C是單射的,則f→C也是單射的

(3)如果→B,→C是雙射的,則f→C也是雙射的

【定理8.2】反函數(shù)（逆函數(shù)）：設(shè)Y是一個(gè)雙射函數(shù)，那么f-1是YX的雙射函數(shù).稱(chēng)f-1為f的反函數(shù).互逆(f-1)-1設(shè)→B是雙射的,則f1f=,ff1=【定理8.5】基數(shù)：用來(lái)衡量集合大小的一個(gè)概念.對(duì)于有限集合集來(lái)說(shuō),集合的基數(shù)就是其中所含元素的個(gè)數(shù).等勢(shì)的：設(shè)A,B是集合,如果存在著從A到B的雙射函數(shù),就稱(chēng)A和B是等勢(shì)的,記作A≈B.如果A不與B等勢(shì),則記作A?B. 注：通常將A的基數(shù)記為.【定義8.8】N≈Z≈Q≈N×N任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合R等勢(shì){0,1}N≈R康托定理N?R；對(duì)任意集合A都有A?P(A).【定義8.7】有限集(有窮集)/無(wú)限集(無(wú)窮集)：設(shè)A為一個(gè)集合.若存在某個(gè)自然數(shù)n,使得A與集合{0,1,…1}等勢(shì),則稱(chēng)A是有限的.若集合A不是有限的,則稱(chēng)A是無(wú)限的.【定義8.11】：實(shí)數(shù)集R的基數(shù)記作,即=【定義8.12】可數(shù)集(可列集)：設(shè)A為集合，若≤0，則稱(chēng)A為可數(shù)集或可列集?！径x8.14】與自然數(shù)集N等勢(shì)的任意集合稱(chēng)為可數(shù)的.其基數(shù)為0結(jié)論： (1)A為可數(shù)的當(dāng)且僅當(dāng)可排列成{a12,…,…}的形式.(2)任一無(wú)限集必含有可數(shù)子集.(3)可數(shù)集的任何無(wú)限子集是可數(shù)的.(4)可數(shù)個(gè)兩兩不相交的可數(shù)集合的并集,仍是一個(gè)可數(shù)集.(5)NN是可數(shù)集.(6)有理數(shù)的全體組成的集合是可數(shù)集.(7)全體實(shí)數(shù)構(gòu)成的集合R是不可數(shù)的.基數(shù)的常識(shí)：對(duì)于有窮集合A,基數(shù)是其元素個(gè)數(shù)n，=n;沒(méi)有最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到：0,1,2,…,n,…,0,,…代數(shù)結(jié)構(gòu)運(yùn)算：對(duì)于集合A，f是從到A的函數(shù)，稱(chēng)f為集合A上的一個(gè)n元運(yùn)算。【定義9.1】交換律：已知<A，*>，若x，y∈A，有x**x，稱(chēng)*在A上是可交換的?！径x9.3】結(jié)合律：已知<A，*>，若x，y，z∈A，有x*（y*z）=（x*y）*z，稱(chēng)*在A上是可結(jié)合的。【定義9.4】?jī)绲嚷桑阂阎碅，*〉，若x∈A，x*則稱(chēng)滿(mǎn)足冪等律?！径x9.5】分配律：設(shè)<A，*，△>，若x，y，z∈A有:x*(y△z)=（x*y）△（x*z）;(y△z)*(y*x)△(z*x)稱(chēng)運(yùn)算*對(duì)△是可分配的?！径x9.6】吸收律：設(shè),是定義在集合A上的兩個(gè)可交換二元運(yùn)算，若對(duì)A,都有(xy)=x；x(xy)=x則稱(chēng)運(yùn)算和滿(mǎn)足吸收律.【定義9.7】單位元（幺元）:設(shè)*是A上二元運(yùn)算，,A 左幺元：若xA，有*，稱(chēng)為運(yùn)算*的左幺元； 右幺元：若xA，有x*，稱(chēng)為運(yùn)算*的右幺元；若e既是左幺元又是右幺元，稱(chēng)e為運(yùn)算*的幺元【定義9.8】設(shè)*是A上的二元運(yùn)算，具有左幺元，右幺元，則【定理9.1】零元:設(shè)*是A上二元運(yùn)算，l,r,A 左零元：若xA，有l(wèi)*l，稱(chēng)l為運(yùn)算*的左零元； 右零元： 若xA，有x*r，稱(chēng)r為運(yùn)算*的右零元；若既是左零元又是右零元，稱(chēng)為運(yùn)算*的零元?！径x9.9】設(shè)*是A上的二元運(yùn)算，具有左零元l，右零元r，則【定理9.2】逆元：設(shè)*是A上的二元運(yùn)算，e是運(yùn)算*的幺元，若x*那對(duì)于運(yùn)算*，x是y的左逆元，y是x的右逆元存在逆元(左逆無(wú)，右逆元）的元素稱(chēng)為可逆的（左可逆的，右可逆的）【定義9.10】對(duì)于可結(jié)合運(yùn)算ο，如果元素x有左逆元ｌ，右逆元r，則－１【定理9.4】消去律：已知<A，*>，若x，y，z∈A，有(1)若x*y=x*z且x,則；(左消去律)(2)若y*x=z*x且x,則；（右消去律）那么稱(chēng)*滿(mǎn)足消去律?！径x9.11】代數(shù)系統(tǒng)：設(shè)A為非空集合，為A上運(yùn)算的集合,稱(chēng)<A,>為一個(gè)代數(shù)系統(tǒng).【定義9.12】同類(lèi)型的代數(shù)系統(tǒng)：如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對(duì)應(yīng)運(yùn)算的元數(shù)相同，且代數(shù)常數(shù)的個(gè)數(shù)也相同，則稱(chēng)它們是同類(lèi)型的代數(shù)系統(tǒng).【定義9.13】子代數(shù)：設(shè)<S,f1,f2,…,>是代數(shù)系統(tǒng)，B是S的非空子集，如果B對(duì)f1,f2,…,都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱(chēng)<B,f1,f2,…,>是V的子代數(shù)系統(tǒng)，簡(jiǎn)稱(chēng)子代數(shù)【定義9.14】最大的子代數(shù)：就是V本身最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構(gòu)成的集合是B，且B對(duì)V中所有的運(yùn)算都是封閉的，則B就構(gòu)成了V的最小的子代數(shù)平凡的子代數(shù):最大和最小的子代數(shù)稱(chēng)為V的平凡的子代數(shù)真子代數(shù)：若B是S的真子集，則B構(gòu)成的子代數(shù)稱(chēng)為V的真子代數(shù).因子代數(shù)：設(shè)V1=<A,?>和V2=<B,>是同類(lèi)型的代數(shù)系統(tǒng)，?和為二元運(yùn)算，在集合AB上如下定義二元運(yùn)算?，<a11>,<a22>AB，有<a11>?<a22>=<a1?a2,b1b2>稱(chēng)<AB,?>為V1與V2的積代數(shù)，記作V1V2.這時(shí)也稱(chēng)V1和V2為V的因子代數(shù).【定義9.15】設(shè)V1=<A,?>和V2=<B,>是同類(lèi)型的代數(shù)系統(tǒng)，V1V2=<AB,?>是它們的積代數(shù).(1)如果?和運(yùn)算是可交換（可結(jié)合、冪等）的，那幺?運(yùn)算也是可交換（可結(jié)合、冪等）的(2)如果e1和e2（1和2）分別為?和運(yùn)算的單位元（零元），那幺<e12>（<1,2>）也是?運(yùn)算的單位元（零元）(3)如果x和y分別為?和運(yùn)算的可逆元素，那幺<>也是?運(yùn)算的可逆元素，其逆元就是<x11>【定理9.5】同態(tài):設(shè)V1=<A,°>和V2=<B,>是同類(lèi)型的代數(shù)系統(tǒng)，B，對(duì)x,yA有f(x°y)=f(x)f(y),則稱(chēng)f是V1到V2的同態(tài)映射，簡(jiǎn)稱(chēng)同態(tài)(1)f如果是單射，則稱(chēng)為單同態(tài)。(2)如果是滿(mǎn)射，則稱(chēng)為滿(mǎn)同態(tài)，這時(shí)稱(chēng)V2是V1的同態(tài)像，記作V1V2。(3)如果是雙射，則稱(chēng)為同構(gòu)，也稱(chēng)代數(shù)系統(tǒng)V1同構(gòu)于V2，記作V1V2。(4)如果V12，則稱(chēng)作自同態(tài)?！径x9.16】半群：設(shè)<S,°>是代數(shù)系統(tǒng)，°為二元運(yùn)算，如果°運(yùn)算是可結(jié)合的，則稱(chēng)V為半群。獨(dú)異點(diǎn)：設(shè)<S,°>是半群，若e∈S是關(guān)于°運(yùn)算的單位元，則稱(chēng)V是含幺半群，也叫做獨(dú)異點(diǎn)。有時(shí)也將獨(dú)異點(diǎn)V記作<S,°>.群：設(shè)<G,°>是獨(dú)異點(diǎn)，eG關(guān)于°運(yùn)算的單位元，若aG，a1G，則稱(chēng)V是群().通常將群記作G.【定義10.1】群的階數(shù)：設(shè)<G,>是一個(gè)群 有限群：如果G是有限集，那么稱(chēng)<G,>為有限群 階數(shù)：為該有限群的階數(shù)； 無(wú)限群：如果G是無(wú)限集，則稱(chēng)<G,>為無(wú)限群。平凡群：階數(shù)為1（即只含單位元）的群稱(chēng)為平凡群【定義10.2】群的性質(zhì)：設(shè)<G,>是一個(gè)群。（1）非平凡群中不可能有零元.（2）對(duì)于G,必存在唯一的xG,使得ax.（3）對(duì)于{}G若:ab=ac或ba=ca則必有(消去律)。（4）運(yùn)算表中的每一行或每一列都是一個(gè)置換。（5）除幺元e外,不可能有任何別的冪等元。元素的冪：設(shè)G是群，a∈G，n∈Z，則a的n次冪【定義10.3】元素的階：設(shè)G是群，a∈G，使得等式成立的最小正整數(shù)k稱(chēng)為元素a的階，記作，稱(chēng)a為k階元。若不存在這樣的正整數(shù)k，則稱(chēng)a為無(wú)限階元?！径x10.4】?jī)邕\(yùn)算性質(zhì)： (1)a∈G，(a1)1 (2)∈G，()11a1 (3)a∈G，=，n,m∈Z (4)a∈G，()m=，n,m∈Z (5)若G為交換群，則()n=.【定理10.1】元素的階的性質(zhì)：G為群，a∈G且=r.設(shè)k是整數(shù)，則(1)=e當(dāng)且僅當(dāng)r|k(r整除k)(2)1|=【定理10.3】子群：設(shè)G是群，H是G的非空子集，如果H關(guān)于G中的運(yùn)算構(gòu)成群，則稱(chēng)H是G的子群,記作H≤G。真子群：若H是G的子群，且HG，則稱(chēng)H是G的真子群，記作H<G.平凡子群：對(duì)任何群G都存在子群.G和{e}都是G的子群，稱(chēng)為G的平凡子群.【定義10.5】子群判定定理一：設(shè)G為群，H是G的非空子集，則H是G的子群當(dāng)且僅當(dāng)(1)∈H有∈H；(2)a∈H有a1∈H?！径ɡ?0.4】子群判定定理二：設(shè)G為群，H是G的非空子集.H是G的子群當(dāng)且僅當(dāng)∈H有1∈H.

【定理10.5】子群判定定理三：設(shè)G為群，H是G的非空有窮子集，則H是G的子群當(dāng)且僅當(dāng)∈H有∈H.【定理10.6】生成子群：設(shè)G為群，a∈G，令{k∈Z}，則H是G的子群，稱(chēng)為由a生成的子群，記作<a>.陪集：設(shè)<H,>是群<G,>的一個(gè)子群G則: 左陪集：{a}H，由a所確定的H在G中的左陪集. 右陪集：{a}陪集是左陪集與右陪集的統(tǒng)稱(chēng).

【定義10.6】陪集性質(zhì)：設(shè)H是群G的子群，則=Ha∈G有a∈∈G有：a∈1∈H在G上定義二元關(guān)系R：∈G,<>∈R1∈H則R是G上的等價(jià)關(guān)系，且[a]R=. 【定理10.7】【定理10.8】拉格朗日定理：設(shè)G是有限群，H是G的子群，則=·[]其中[]是H在G中的不同右陪集(或左陪集)數(shù)，稱(chēng)為H在G中的指數(shù).【定理10.10】推論：（1）設(shè)G是n階群，則a∈G，是n的因子，且=e.（2）對(duì)階為素?cái)?shù)的群G，必存在a∈G使得G=<a>.阿貝爾群（交換群）：若群G中的運(yùn)算是可交換的，則稱(chēng)G為交換群或阿貝爾群。循環(huán)群：設(shè)G是群，若存在a∈G使得{k∈Z}則稱(chēng)G是循環(huán)群，記作<a>，稱(chēng)a為G的生成元.

n階循環(huán)群:設(shè)<a>是循環(huán)群，若a是n階元，則G={a0,a1,a2,…,1}無(wú)限循環(huán)群:若a是無(wú)限階元，則G={a0,a±1,a±2,…}【定義10.7】循環(huán)群的生成元:設(shè)<a>是循環(huán)群(1)若G是無(wú)限循環(huán)群，則G只有兩個(gè)生成元，即a和a1.

(2)若G是n階循環(huán)群，則G含有(n)個(gè)生成元.對(duì)于任何小于n且與n互質(zhì)的數(shù)r∈{0,1,…1},是G的生成元.【定理10.11】循環(huán)群的子群：(1)設(shè)<a>是循環(huán)群，則G的子群仍是循環(huán)群；(2)若<a>是無(wú)限循環(huán)群，則G的子群除{e}以外都是無(wú)限循環(huán)群；(3)若<a>是n階循環(huán)群，則對(duì)n的每個(gè)正因子d，G恰好含有一個(gè)d階子群。【定理10.12】環(huán)：設(shè)<,·>是代數(shù)系統(tǒng)，+和·是二元運(yùn)算.如果滿(mǎn)足以下條件:(1)<>構(gòu)成交換群；(2)<R,·>構(gòu)成半群；(3)·運(yùn)算關(guān)于+運(yùn)算適合分配律，則稱(chēng)<,·>是一個(gè)環(huán).【定義10.11】環(huán)的運(yùn)算性質(zhì)：設(shè)<,·>是環(huán)，則(1)a∈R，a0=0a=0(2)∈R，(a)b=a(b)=(3)∈R，a(bc)=，(bc)a=(4)a1212∈R(≥2)i=1nai設(shè)<,·>是環(huán) 交換環(huán)：若環(huán)中乘法·適合交換律，則稱(chēng)R是交換環(huán)；含幺環(huán)：若環(huán)中乘法·存在單位元，則稱(chēng)R是含幺環(huán)；無(wú)零因子環(huán)：若∈R，00∨0，則稱(chēng)R是無(wú)零因子環(huán)。整環(huán)：設(shè)<,>是一個(gè)代數(shù)系統(tǒng),若滿(mǎn)足:(1)<>是阿貝爾群；(2)<R,>是可交換獨(dú)異點(diǎn)，且無(wú)零因子，即對(duì)R,a00則ab0；(3)運(yùn)算對(duì)+是可分配的，則稱(chēng)<,>是整環(huán)域：設(shè)<,>是一個(gè)代數(shù)系統(tǒng),若滿(mǎn)足:(1)<>是阿貝爾群；(2)<{0},>是阿貝爾群；(3)運(yùn)算對(duì)+是可分配的，則稱(chēng)<,>是域?！径x10.12】格：設(shè)<S,?>是偏序集，如果S，{}都有最小上界和最大下界，則稱(chēng)S關(guān)于偏序?作成一個(gè)格【定義11.1】格的代數(shù)系統(tǒng)定義：設(shè)<S,?,?>是代數(shù)系統(tǒng),?和?是二元運(yùn)算,如果?和?滿(mǎn)足交換律、結(jié)合律和吸收律,則<S,?,?>構(gòu)成格【定義11.3】對(duì)偶命題：設(shè)f是含有格中元素以與符號(hào)=,?,?,∨和∧的命題.令f*是將f中的?替換成?,?替換成?,∨替換成∧,∧替換成∨所得到的命題.稱(chēng)f*為f的對(duì)偶命題【定義11.2】格的對(duì)偶原理：設(shè)f是含有格中元素以與符號(hào)=,?,?,∨和∧等的命題.若f對(duì)一切格為真,則f的對(duì)偶命題f*也對(duì)一切格為真.格的性質(zhì)：設(shè)<L,?>是格,則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即(1)∈L有a∨b=b∨a,a∧b=b∧a(2)∈L有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L有a∨a=a,a∧a=a(4)∈L有a∨(a∧b)=a,a∧(a∨b)=a【定理11.1】格的序與運(yùn)算性質(zhì)：設(shè)L是格,則∈L有a?ba∧b=aa∨b=b【定理11.3】格的保序性質(zhì)：設(shè)L是格,∈L，若a?b且c?d,則a∧c?b∧d,a∨c?b∨d【定理11.4】子格：設(shè)<L,∧,∨>是格,S是L的非空子集,若S關(guān)于L中的運(yùn)算∧和∨仍構(gòu)成格,則稱(chēng)S是L的子格【定義11.4】分配格：設(shè)<L,∧,∨>是格,若∈L,有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)則稱(chēng)L為分配格.【定義11.5】分配格的判別：設(shè)L是格,則L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格【定理11.5】全下界：設(shè)L是格,若存在a∈L使得x∈L有a?x,則稱(chēng)a為L(zhǎng)的全下界；全上界：設(shè)L是格,若存在b∈L使得x∈L有x?b,則稱(chēng)b為L(zhǎng)的全上界

?！径x11.6】有界格：設(shè)L是格，若L存在全下界和全上界,則稱(chēng)L為有界格，一般將有界格L記為<L,∧,∨,0,1>.【定義11.7】有界格的性質(zhì)：設(shè)<L,∧,∨,0,1>是有界格,則a∈L有a∧0=0∨0=∧1=a,a∨1=1補(bǔ)元：設(shè)<L,∧,∨,0,1>是有界格,a∈L,若存在b∈L使得a∧b=0和a∨b=1成立,則稱(chēng)b是a的補(bǔ)元 【定義11.8】有界分配格的補(bǔ)元惟一性定理：設(shè)<L,∧,∨,0,1>是有界分配格.若L中元素a存在補(bǔ)元,則存在惟一的補(bǔ)元. 【定理11.6】有補(bǔ)格:設(shè)<L,∧,∨,0,1>是有界格,若L中所有元素都有補(bǔ)元存在,則稱(chēng)L為有補(bǔ)格.【定義11.9】布爾格（布爾代數(shù)）：如果一個(gè)格是有補(bǔ)分配格,則稱(chēng)它為布爾格或布爾代數(shù).布爾代數(shù)標(biāo)記為<B,∧,∨,,0,1>,為求補(bǔ)運(yùn)算.【定義11.10】布爾代數(shù)的代數(shù)系統(tǒng)定義：設(shè)<B,?,?>是代數(shù)系統(tǒng),?和?是二元運(yùn)算.若?和?運(yùn)算滿(mǎn)足：(1)交換律,即∈B有a?b=b?a,a?b=b?a(2)分配律,即∈B有a?(b?c)=(a?b)?(a?c),

a?(b?c)=(a?b)?(a?c)(3)同一律,即存在0,1∈B,使得a∈B有a?1=a,a?0=a(4)補(bǔ)元律,即a∈B,存在a∈B使得a?a=0,a?a=1則稱(chēng)<B,?,?>是一個(gè)布爾代數(shù). 【定義11.11】布爾代數(shù)的性質(zhì)：設(shè)<B,∧,∨,,0,1>是布爾代數(shù),則(1)a∈B,(a)=a.(2)∈B,(a∧b)=a∨b,(a∨b)=a∧b（德摩根律）【定理11.7】原子：設(shè)L是格,0∈L,a∈L若b∈L有0?b?ab=a,則稱(chēng)a是L中的原子【定義11.12】有限布爾代數(shù)的表示定理：設(shè)B是有限布爾代數(shù),A是B的全體原子構(gòu)成的集合,則B同構(gòu)于A的冪集代數(shù)P(A). 【定理11.8】推論1：任何有限布爾代數(shù)的基數(shù)為2n,n∈N.推論2：任何等勢(shì)的有限布爾代數(shù)都是同構(gòu)的圖論無(wú)序積：A{()|xAyB}無(wú)向圖G=<>,其中(1)V為頂點(diǎn)集，元素稱(chēng)為頂點(diǎn)；(2)E為VV的多重集，其元素稱(chēng)為無(wú)向邊，簡(jiǎn)稱(chēng)邊?！径x14.1】有向圖<>,只需注意E是VV的多重子集 【定義14.2】n階圖：頂點(diǎn)個(gè)數(shù)為n.零圖：邊的個(gè)數(shù)為0.n階零圖記為平凡圖：1階零圖N1空?qǐng)D：標(biāo)定圖與非標(biāo)定圖：依據(jù)頂點(diǎn)和邊是否命名標(biāo)識(shí)。有向圖的基圖：有向邊改為無(wú)向邊后的圖。頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系(,) 關(guān)聯(lián)：與,關(guān)聯(lián) 關(guān)聯(lián)次數(shù)：0(不關(guān)聯(lián))，1()，2() 環(huán)：與同一頂點(diǎn)關(guān)聯(lián)次數(shù)為2的邊； 孤立點(diǎn)：不與任何邊關(guān)聯(lián)的頂點(diǎn)。頂點(diǎn)相鄰：兩個(gè)頂點(diǎn)之間有邊。邊相鄰：兩條邊有公共端點(diǎn)。平行邊：關(guān)聯(lián)的端點(diǎn)相同的兩條邊（有向圖中方向相同）。vV(G)(G為無(wú)向圖) v的鄰域： v的閉鄰域： v的關(guān)聯(lián)集：vV(D)(D為有向圖) v的后繼元集： v的先驅(qū)元集： v的鄰域： v的閉鄰域：多重圖：含平行邊的圖；簡(jiǎn)單圖：即不含平行邊又不含環(huán)的圖。【定義14.3】度（度數(shù)）：設(shè)<>為無(wú)向圖,vV,d(v)——v的度數(shù),簡(jiǎn)稱(chēng)度設(shè)<>為有向圖,vV, 出度(v)：v作為邊的始點(diǎn)的次數(shù) 入度d(v)：v作為邊的終點(diǎn)的次數(shù)度（度數(shù)）d(v)：(v)+d(v)最大度(G){d(v)∈V(G)}最小度(G)={d(v)∈V(G)}最大出度+(D){(v)∈V(D)}最小出度+(D){(v)∈V(D)}最大入度(D){(v)∈V(D)}最小入度(D){(v)∈V(D)}最大度(D){d(v)∈V(D)}最小度(D){d(v)∈V(G)}奇頂點(diǎn)度：度為奇數(shù)的頂點(diǎn)偶度頂點(diǎn)：度為偶數(shù)的頂點(diǎn) 【定義14.4】握手定理：設(shè)<>為任意無(wú)向圖，{v12,…},,則 設(shè)<>為任意有向圖，{v12,…},,則 【定理14.1】【定理14.2】推論：任何圖(無(wú)向或有向)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).度數(shù)列：{v1,v2,…,}為無(wú)向圖G的頂點(diǎn)集，稱(chēng)d(v1),d(v2),…,d()為G的度數(shù)列{v1,v2,…,}為有向圖D的頂點(diǎn)集度數(shù)列：d(v1),d(v2),…,d()出度列：(v1),(v2),…,()入度列：d(v1),d(v2),…,d()可圖化的：非負(fù)整數(shù)列(d1,d2,…,)，若存在以{v12,…}為頂點(diǎn)集的n階無(wú)向圖G,使得d()，則稱(chēng)d是可圖化的。特別的，若得到的圖是簡(jiǎn)單圖，則稱(chēng)d是可簡(jiǎn)單圖化的。非負(fù)整數(shù)列(d1,d2,…,)是可圖化的當(dāng)且僅當(dāng)為偶數(shù).【定理14.3】設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則(G)n-1.【定理14.4】圖的同構(gòu)：設(shè)G1=<V11>,G2=<V22>為兩個(gè)無(wú)向圖(兩個(gè)有向圖)，若存在雙射函數(shù)f1V2，對(duì)于,V1,()E1當(dāng)且僅當(dāng)(f(),f())E2（<>E1當(dāng)且僅當(dāng)<f(),f()>E2)并且,()（<>）與(f(),f())（<f()()>）的重?cái)?shù)相同，則稱(chēng)G1與G2是同構(gòu)的，記作G1G2.【定義14.5】n(n1)階無(wú)向完全圖：每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作.邊數(shù)n(n1)階有向完全圖：每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖.邊數(shù)n(n1)階競(jìng)賽圖：基圖為的有向簡(jiǎn)單圖.【定義14.6】邊數(shù)n階k正則圖：=的無(wú)向簡(jiǎn)單圖。【定義14.7】邊數(shù)<>,G=<V> 子圖：V’V且E’E,則稱(chēng)G’為G的子圖，記為GG，稱(chēng)G為G的母圖; 生成子圖：若GG且V，則稱(chēng)G為G的生成子圖； 真子圖：若VV或EE，稱(chēng)G為G的真子圖； 導(dǎo)出子圖：V（VV且V）的導(dǎo)出子圖，記作G[V]； E（EE且E）的導(dǎo)出子圖，記作G[E]. 【定義14.8】補(bǔ)圖：設(shè)<>為n階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以所有使G成為完全圖的添加邊組成的集合為邊集的圖，稱(chēng)為G的補(bǔ)圖，記作.若G,則稱(chēng)G是自補(bǔ)圖 【定義14.9】Gv：從G中將v與關(guān)聯(lián)的邊去掉GV：從G中刪除V中所有的頂點(diǎn)Ge：將e從G中去掉GE：刪除E中所有邊【定義14.10】通路與回路：給定圖<>（無(wú)向或有向的），G中頂點(diǎn)與邊的交替序列=v0e1v1e2…稱(chēng)為從v0到的通路，其中1,是的端點(diǎn).；若v0，為回路。中的邊數(shù)稱(chēng)為通路的長(zhǎng)度.簡(jiǎn)單通路與簡(jiǎn)單回路：所有邊各異。初級(jí)通路(路徑)與初級(jí)回路(圈)：中所有頂點(diǎn)各異（v0除外），所有邊也各異復(fù)雜通路與復(fù)雜回路：有邊重復(fù)出現(xiàn) 【定義14.11】在n階圖G中，若從頂點(diǎn)到（）存在通路，則從到存在長(zhǎng)度小于或等于n1的通路.【定理14.5】推論：在n階圖G中，若從頂點(diǎn)到（）存在通路，則從到存在長(zhǎng)度小于或等于n1的初級(jí)通路（路徑）在一個(gè)n階圖G中，若存在到自身的回路，則一定存在到自身長(zhǎng)度小于或等于n的回路.【定理14.6】推論：在一個(gè)n階圖G中，若存在到自身的簡(jiǎn)單回路，則一定存在長(zhǎng)度小于或等于n的初級(jí)回路.頂點(diǎn)的連通性：<>為無(wú)向圖，若與之間有通路，則稱(chēng)與是連通的，記為連通圖：若V，uv，則稱(chēng)G是連通的；【定義14.12】連通分支：{V12,…}，稱(chēng)G[V1],G[V2],…[]為連通分支，其個(gè)數(shù)稱(chēng)為連通分支數(shù)，記為p(G)【定義14.13】短程線(xiàn)uv：，u與v之間長(zhǎng)度最短的通路距離d()：短程線(xiàn)的長(zhǎng)度 【定義14.14】d()0,u?v時(shí)d()=d()()d()()d()<>,VV 點(diǎn)割集：p(GV)>p(G)，且對(duì)任意VV均有p(GV)(G)，則V為點(diǎn)割集 割點(diǎn)：{v}為點(diǎn)割集，則v為割點(diǎn) 【定義14.15】<>,EE邊割集：p(GE)>p(G)且有極小性則E是邊割集割邊（橋）：{e}為邊割集e是割邊（橋）【定義14.16】G為連通非完全圖 點(diǎn)連通度(G)={|V為點(diǎn)割集}。規(guī)定()=n1;若G非連通，(G)=0 連通圖：若(G)k，則稱(chēng)G為連通圖【定義14.17】設(shè)G為連通圖 邊連通度(G)={|E為邊割集}規(guī)定：若G非連通，則(G)=0r邊-連通圖：若(G)r，則稱(chēng)G是r邊-連通圖 【定義14.18】,,之間的關(guān)系：(G)(G)(G)【定理14.7】<>為有向圖 可達(dá)：存在從到有通路 相互可達(dá)：且 【定義14.19】<>為有向圖 弱連通(連通)：基圖為無(wú)向連通圖 單向連通：V，或 強(qiáng)連通：V， 【定義14.21】有向圖的連通性判別法：(1)D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路；【定理14.8】(2)D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路?！径ɡ?4.9】二部圖(二分圖)(偶圖)：設(shè)<>為一個(gè)無(wú)向圖，若能將V分成V1和V2(V1V2，V1V2=)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱(chēng)G為二部圖(或稱(chēng)二分圖、偶圖等)，稱(chēng)V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為<V12>.完全二部圖：若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱(chēng)G為完全二部圖，記為，其中1|，2|.【定義14.22】二部圖的判別法：無(wú)向圖<>是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈?！径ɡ?4.10】關(guān)聯(lián)矩陣M(G)：無(wú)向圖<>，，，令為與的關(guān)聯(lián)次數(shù)，稱(chēng)()nm為G的，記為M(G).【定義14.23】(4)平行邊的列相同關(guān)聯(lián)矩陣M(D)：有向圖<>，令則稱(chēng)()nm為D的關(guān)聯(lián)矩陣，記為.【定義14.24】(4)平行邊對(duì)應(yīng)的列相同鄰接矩陣：設(shè)D＝()是有向圖，V={v1,…}，構(gòu)造矩陣[]如下：(1n)稱(chēng)A為圖D的鄰接矩陣?！径x14.25】鄰接矩陣的含義：設(shè)A為有向圖D的鄰接矩陣，{v1,v2,…,}為頂點(diǎn)集，則A的l次冪（l1）中元素為D中到長(zhǎng)度為l的通路數(shù)，其中為到自身長(zhǎng)度為l的回路數(shù)，而為D中長(zhǎng)度為l的通路總數(shù)，為D中長(zhǎng)度為l的回路總數(shù).【定理14.11】可達(dá)矩陣P(D)：設(shè)<>為有向圖.{v1,v2,…,},令稱(chēng)()nn為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P.【定義14.26】歐拉通路：經(jīng)過(guò)圖（無(wú)向圖或有向圖）中每條邊一次且僅一次行遍所有頂點(diǎn)的通路.歐拉回路：經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的回路.歐拉圖：具有歐拉回路的圖.半歐拉圖：具有歐拉通路而無(wú)歐拉回路的圖【定義15.1】平凡圖是歐拉圖.歐拉通路是簡(jiǎn)單通路，歐拉回路是簡(jiǎn)單回路無(wú)向歐拉圖的判別法：(1)無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度數(shù)頂點(diǎn).【定理15.1】(2)無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn).【定理15.2】有向歐拉圖的判別法：(1)有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂點(diǎn)的入度都等于出度.【定理15.3】(2)有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè)的出度比入度大1，而其余頂點(diǎn)的入度都等于出度.【定理15.4】算法(求歐拉回路)：(1)任取v0V(G)，令P00.(2)設(shè)=v0e1v1e2…已經(jīng)行遍，按下面方法從E(G){e12,…}中選取1：(a)1與相關(guān)聯(lián)；(b)除非無(wú)別的邊可供行遍，否則1不應(yīng)該為=G{e12,…}中的橋.(3)當(dāng)(2)不能再進(jìn)行時(shí)，算法停止.哈密頓通路：經(jīng)過(guò)圖（無(wú)向圖或有向圖）中所有頂點(diǎn)一次僅一次的通路.哈密頓回路：經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的回路.哈密頓圖：具有哈密頓回路的圖.半哈密頓圖：具有哈密頓通路且無(wú)哈密頓回路的圖. 【定義15.2】平凡圖是哈密頓圖.哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路.哈密頓圖的必要條件：設(shè)無(wú)向圖<>是哈密頓圖，對(duì)于任意V1V且V1，均有p(GV1)1| 【定理15.6】推論：設(shè)無(wú)向圖<>是半哈密頓圖，對(duì)于任意的V1V且V1均有p(GV1)11哈密頓通路的充分條件：設(shè)G是n階無(wú)向簡(jiǎn)單圖，若對(duì)于任意不相鄰的頂點(diǎn)，均有d()()n1則G中存在哈密頓通路.【定理15.7】推論（哈密頓圖的充分條件）：設(shè)G為n(n3)階無(wú)向簡(jiǎn)單圖，若對(duì)于G中任意兩個(gè)不相鄰的頂點(diǎn)，均有d()()n則G中存在哈密頓回路，從而G為哈密頓圖帶權(quán)圖：設(shè)Ｇ＝()是圖，若G的