離散數(shù)學(xué)知識點.doc

說明： 定義：紅色表示。 定理性質(zhì)：橙色表示。 公式：藍色表示。 算法: 綠色表示 頁碼：灰色表示 數(shù)理邏輯： 1. 命題公式：命題， 聯(lián)結(jié)詞(Ø，Ù，Ú，®，«)，合式公式，子公式 2. 公式的真值：賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式 3. 范式：析取范式，極小項，主析取范式，合取范式，極大項，主合取范式 4. 聯(lián)結(jié)詞的完備集：真值函數(shù)，異或，條件否定，與非，或非，聯(lián)結(jié)詞完備集 5. 推理理論：重言蘊含式，有效結(jié)論，P規(guī)則，T規(guī)則， CP規(guī)則，推理 6. 謂詞與量詞:謂詞，個體詞，論域，全稱量詞，存在量詞 7. 項與公式:項，原子公式，合式公式，自由變元，約束變元，轄域，換名，代入 8. 公式語義:解釋，賦值，有效的，可滿足的，不可滿足的 9. 前束范式:前束范式 10. 推理理論:邏輯蘊含式，有效結(jié)論，"-規(guī)則（US），"+規(guī)則（UG）， $-規(guī)則(ES)，$+規(guī)則(EG), 推理 集合論： 1. 集合: 集合, 外延性原理, Î, Í , Ì, 空集, 全集, 冪集, 文氏圖, 交, 并, 差, 補, 對稱差 2. 關(guān)系: 序偶, 笛卡爾積, 關(guān)系, domR, ranR, 關(guān)系圖, 空關(guān)系, 全域關(guān)系, 恒等關(guān)系 3. 關(guān)系性質(zhì)與閉包:自反的, 反自反的, 對稱的, 反對稱的, 傳遞的,自反閉包 r(R),對稱閉包 s(R), 傳遞閉包 t(R) 4. 等價關(guān)系: 等價關(guān)系, 等價類, 商集, 劃分 5. 偏序關(guān)系:偏序, 哈斯圖, 全序(線序), 極大元/極小元, 最大元/最小元, 上界/下界 6. 函數(shù): 函數(shù), 常函數(shù), 恒等函數(shù), 滿射,入射,雙射，反函數(shù), 復(fù)合函數(shù) 7. 集合基數(shù):基數(shù), 等勢, 有限集/無限集, 可數(shù)集, 不可數(shù)集 代數(shù)結(jié)構(gòu)： 1. 運算及其性質(zhì)：運算，封閉的,可交換的,可結(jié)合的,可分配的,吸收律, 冪等的，幺元,零元,逆元 2. 代數(shù)系統(tǒng)：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)，同態(tài)，同構(gòu)。 3. 群與子群：半群,子半群,元素的冪，獨異點，群，群的階數(shù)，子群,平凡子群，陪集，拉格朗日（Lagrange）定理 4. 阿貝爾群和循環(huán)群：阿貝爾群(交換群)，循環(huán)群,生成元 5. 環(huán)與域：環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域 6. 格與布爾代數(shù)：格，對偶原理，子格，分配格，有界格，有補格，布爾代數(shù)，有限布爾代數(shù)的表示定理 圖論： 1. 圖的基本概念：無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖，握手定理，圖的同構(gòu) 2. 圖的連通性:通路，回路，簡單通路，簡單回路（跡）初級通路（路徑），初級回路（圈），點連通，連通圖，點割集，割點，邊割集，割邊，點連通度，邊連通度，弱連通圖，單向連通圖，強連通圖，二部圖（二分圖） 3. 圖的矩陣表示：關(guān)聯(lián)矩陣，鄰接矩陣，可達矩陣 4. 歐拉圖與哈密頓圖：歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖 5. 無向樹與根樹：無向樹，生成樹，最小生成樹，Kruskal，根樹，m叉樹，最優(yōu)二叉樹，Huffman算法 6. 平面圖:平面圖，面，歐拉公式，Kuratoski定理 數(shù)理邏輯： 命題：具有確定真值的陳述句。 否定詞符號Ø：設(shè)p是一個命題，Øp稱為p的否定式。Øp是真的當且僅當p是假的。p是真的當且僅當Øp是假的。【定義1.1】 合取詞符號Ù：設(shè)p，q是兩個命題，命題 “p并且q”稱為p，q的合取，記以pÙq，讀作p且q。pÙq是真的當且僅當p和q都是真的?！径x1.2】 析取詞符號Ú：設(shè)p，q是兩個命題，命題 “p或者q”稱為p，q的析取，記以pÚq，讀作p或q。pÚq是真的當且僅當p，q中至少有一個是真的。【定義1.3】 蘊含詞符號 ®：設(shè)p，q是兩個命題，命題 “如果p，則q”稱為p蘊含q，記以p®q。p®q是假的當且僅當p是真的而q是假的?！径x1.4】 等價詞符號 «：設(shè)p，q是兩個命題，命題 “p當且僅當q”稱為p等價q，記以p«q。p®q是真的當且僅當p，q或者都是真的，或者都是假的?！径x1.5】 合式公式: (1) 命題常元和變元符號是合式公式； (2) 若A是合式公式，則(ØA)是合式公式，稱為A的否定式； (3) 若A，B是合式公式，則 (AÚB)， (AÙB)， (A®B)，(A«B)是合式公式； (4) 所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符號串。 子公式: 如果Ｘ是合式公式A的一部分，且Ｘ本身也是一個合式公式，則稱Ｘ為公式A的子公式?！径x1.6】 賦值（指派，解釋）： 設(shè)å是命題變元集合，則稱函數(shù)v：å ® {1，0}是一個真值賦值。【定義1.8】 真值表：公式A在其所有可能的賦值下所取真值的表，稱為A的真值表。【定義1.9】 重言式（永真式）:任意賦值v， v A 矛盾式（永假式）:任意賦值v， 有v A【定義1.10】 等值式：若等價式A«B是重言式，則稱A與B等值，記作AÛB?！径x2.1】 基本等值式 雙重否定律 ØØAÛA 冪等律 AÚAÛA, AÙAÛA 交換律 AÚBÛBÚA, AÙBÛBÙA 結(jié)合律 (AÚB)ÚCÛAÚ(BÚC), (AÙB)ÙCÛAÙ(BÙC) 分配律 AÚ(BÙC)Û(AÚB)Ù(AÚC), AÙ(BÚC)Û(AÙB)Ú(AÙC) 德摩根律 Ø(AÚB)ÛØAÙØB ,Ø(AÙB)ÛØAÚØB ^ ^ 吸收律 AÚ(AÙB)ÛA, AÙ(AÚB)ÛA ^ 零律 AÚ Û , AÙ^Û^ ^ 同一律 AÚ^ÛA, AÙ ÛA 排中律 AÚØA Û 矛盾律 AÙØAÛ ^ 蘊涵等值式 A®BÛØAÚB 等價等值式 A«BÛ(A®B)Ù(B®A) 假言易位 A®BÛØB®ØA 等價否定等值式A«BÛØA«ØB 歸謬論 (A®B)Ù(A®ØB) ÛØA 置換規(guī)則： 設(shè)Ｘ是公式A的子公式, ＸÛ Y。將A中的Ｘ（可以是全部或部分X）用Y來置換，所得到的公式B，則 AÛB。 文字: 設(shè)AÎå（命題變元集）, 則A和 Ø A都稱為命題符號A的文字，其中前者稱為正文字，后者稱為負文字?！径x2.2】 析取范式：形如A1 Ú A2 Ú …Ú An (n³1) 的公式稱為析取范式，其中Ai(i=1,…,n)是由文字組成的合取范式。 合取范式：形為A1Ù A2 Ù …ÙAn (n³ 1) 的公式稱為合取范式，其中A1,…,An都是由文字組成的析取式。【定義2.3】 極小項：文字的合取式稱為極小項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次。 極大項：文字的析取式稱為極大項，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次。【定義2.4】 主析取范式：給定的命題公式的主析取范式是一個與之等價的公式，后者由極小項的析取組成。 主合取范式：給定的命題公式的主合取范式是一個與之等價的公式，后者由極大項的合取組成。 【定義2.5】 公式的真值表中真值為F的指派所對應(yīng)的極大項的合取，即為此公式的主合取范式。 真值函數(shù)： 稱F:{0,1}n® {0,1} 為n元真值函數(shù).【定義2.6】 聯(lián)結(jié)詞的完備集：設(shè)C是聯(lián)結(jié)詞的集合，若對于任意一個合式公式均存在一個與之等價的公式，而后者只含有C中的聯(lián)結(jié)詞，則稱C是聯(lián)結(jié)詞的完備集?！径x2.7】 {Ø，Ù，Ú，®，«}，{ Ø，Ù，Ú } , {Ø， Ù}， {Ø， Ú}，{^ ，®}是聯(lián)結(jié)詞的完備集?！径ɡ?.6】 c 異或PÅQ ： Û Ø (P « Q) 條件否定P®Q： Û Ø (P ® Q) 與非P­Q： Û Ø (P Ù Q) 或非P¯Q： Û Ø (P Ú Q)【定義2.8】 {­},{↓}都是聯(lián)結(jié)詞的完備集【定理2.7】 重言蘊含式：當且僅當P®Q是一個重言式時，稱P重言蘊含Q，記為PÞQ。 有效結(jié)論：設(shè)A、C是兩個命題公式，若A Þ C，稱C是A的有效結(jié)論?！径x3.1】 推理定律——重言蘊涵式 1. A Þ (AÚB) 附加律 2. (AÙB) Þ A 化簡律 3. (A®B)ÙA Þ B 假言推理 4. (A®B)ÙØB Þ ØA 拒取式 5. (AÚB)ÙØB Þ A 析取三段論 6. (A®B)Ù(B®C) Þ (A®C) 假言三段論 7. (A«B)Ù(B«C) Þ (A«C) 等價三段論 8. (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 構(gòu)造性二難 (A®B)Ù(ØA®B) Þ B 構(gòu)造性二難(特殊形式) 9. (A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破壞性二難 形式系統(tǒng): 一個形式系統(tǒng) I 由下面四個部分組成： (1) 非空的字母表，記作 A(I). (2) A(I) 中符號構(gòu)造的合式公式集，記作 E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作 R(I). 記 I=<A(I),E(I),AX(I),R(I)>, 其中<A(I),E(I)>是 I 的形式語言系統(tǒng), <AX(I),R(I)> 是 I 的形式演算系統(tǒng). 自然推理系統(tǒng): 無公理, 即AX(I)=Æ 公理推理系統(tǒng): 推出的結(jié)論是系統(tǒng)中的重言式, 稱作定理【定義3.2】 P規(guī)則：在推導(dǎo)過程中,可以隨時添加前提。 T規(guī)則：在推導(dǎo)過程中,可以引入公式S，它是由其前題的一個或多個公式借助重言、蘊含而得到的。 推理（證明）：從前提A1, A2,¼, Ak到結(jié)論B的推理是一個公式序列C1, C2,¼, Cl. 其中Ci(1£i£l)是某個Aj, 或者可由序列中前面的公式應(yīng)用推理規(guī)則得到, 并且Cl =B?！径x3.3】 CP規(guī)則(演繹定理)：若G È{R}|- S，則 G |- R®S, 其中G為命題公式的集合。 個體詞：用于表示命題中主語部分的符號或符號串。 個體常元 表示確指個體。 個體變元 表示不確指個體。 個體域: 個體變元的取值范圍，常用D表示。 量詞：限定個體數(shù)量特性的詞。 全稱量詞"：對所有的 存在量詞$：有些 謂詞語言：用符號串表示個體、謂詞、量詞和命題 個體變元符號： x，y，z，… 個體常元符號： a，b，c，… 函數(shù)符號：f，g，… ^ 謂詞符號：P，Q，R，… 命題常元符號： ^ ， 量詞符號：" ，$ 連接詞符號： Ø , Ù, Ú, ®, « 輔助符號： ） , （ 【定義4.1】 項: (1)個體常元和變元是項； (2) 若f是n元函數(shù)符號，t1, …, tn是項，則f(t1, …, tn)是項； (3) 僅僅有限次使用(1)，(2)產(chǎn)生的符號串是項。 【定義4.2】 原子公式: 若P是一個元謂詞符號，t1,…,tn是項, 則P(t1,…,tn)是原子公式。【定義4.3】 合式公式： (1) 原子公式是公式； (2) 若A是合式公式，則(Ø A)是合式公式； (3) 若A，B是公式，則(AÚB)，(AÙB)，A®B)，(A«B)是公式； (4) 若A是公式，x是變元，則"xA，$xA是公式； (5) 僅僅有限次使用１～４得到的符號串才是合式公式。 【定義4.4】 設(shè)公式 a的一個子公式為" x A或$ x A。則稱： 指導(dǎo)變元：x是"或$的指導(dǎo)變元。 轄域：A是相應(yīng)量詞的轄域。 約束出現(xiàn)：轄域中x的一切出現(xiàn)，以及(" x)中的x稱為x在a中的約束出現(xiàn)。 自由出現(xiàn)：變元的非約束出現(xiàn)。 約束變元：約束出現(xiàn)的變元。 自由變元：自由出現(xiàn)的變元。 【定義4.5】 封閉的：一個公式A是封閉的，若其中不含自由變元?！径x4.6】 變元換名：（1） 換名的范圍是量詞的指導(dǎo)變元,及其相應(yīng)轄域中的變元，其余部分不變。 （2） 換名時最好選用轄域中未出現(xiàn)的變元名。 變元代入：代入對自由變元進行。不能改變約束關(guān)系。 解釋： 謂詞語言的一個解釋 I= (D, j )包括： (1) 非空集合D，稱之為論域； (2) 對應(yīng)于每一個個體常元a， j(a)ÎD； (3) 對應(yīng)于每一個n元函數(shù)符號f都有一個函數(shù) j(f):Dn ® D； (4) 對應(yīng)于每一個n元謂詞符號A都有一個n元關(guān)系j(A) Í Dn?！径x4.7】 賦值：解釋I中的賦值v為每一個個體變元x指定一個值v(x ）Î D，即設(shè) V為所個體變元的集合，則賦值v是函數(shù) v:V ® D. 可滿足的：給定公式A，若在某一解釋中至少有一種賦值使A取值為1，則稱A為可滿足的。否則稱A是不可滿足的。 等值式A Û B：若A«B是有效的【定義5.1】 幾類等值式 （1）命題公式的推廣 e.g. P(x) ® Q(x) Û Ø P(x) Ú Q(x) （2）否定深入 Ø " x P(x) Û $ x(Ø P(x)) Ø $ xP(x) Û " x (Ø P(x)) （3）量詞作用域的擴張與收縮 設(shè)B中不含x的自由出現(xiàn)，則 " x(A(x)Ú B) Û " x A(x) Ú B " x(A(x)Ù B) Û " x A(x) Ù B " x(A(x)®B) Û $ x A(x) ® B " x(B® A(x)) Û B ®" x A(x) $ x(A(x)Ú B) Û $ x A(x) Ú B $ x(A(x)Ù B) Û $ x A(x) Ù B $ x(A(x)®B) Û " x A(x) ® B $ x(B® A(x)) Û B®$ x A(x) （4）量詞分配等值式 " x(A(x) Ù B(x)) Û " x A(x) Ù " x B(x) $ x(A(x) Ú B(x)) Û $ x A(x) Ú $ x B(x) （5）多個量詞的使用 " x " y A(x,y) Û " y " x A(x,y) $ x $ y A(x,y) Û $ y $ x A(x,y) 置換規(guī)則：設(shè)F(A)是含A的公式, 那么, 若AÛB, 則F(A)ÛF(B). 換名規(guī)則：設(shè)A為一公式，將A中某量詞轄域中個體變項的所有約束出現(xiàn)及相應(yīng)的指導(dǎo)變元換成該量詞轄域中未曾出現(xiàn)過的個體變項符號，其余部分不變，設(shè)所得公式為A¢，則A¢ÛA. 前束范式：如果謂詞公式A有如下形狀：Q1x1…QnxnM，其中 Qixi或者是"xi，或者是$xi，i=1，…，n，M是不含量詞的公式， Q1x1…Qnxn稱為首標，M稱為母式?！径x5.2】 前束范式存在定理：對于任意謂詞公式，都存在與它邏輯等價的前束范式?！径ɡ?.1】 前束范式的算法： 步1. 對約束出現(xiàn)的變元進行必要的換名，使得約束出現(xiàn)的變元互不相同且不與任何自由變元同名。 步2. 將所有的否定號Ø深入到量詞后面。 步3. 將量詞符號移至公式最外層。 邏輯蘊含式A Þ C：當且僅當A®C是有效的。 幾類邏輯蘊涵式 第一組 命題邏輯推理定理的代換實例 如, "xF(x)Ù$yG(y) Þ "xF(x) 第二組 基本等值式生成的推理定理 如, "xF(x) ÞØØ"xF(x), ØØ"xF(x) Þ"xF(x) Ø"xF(x)Þ$xØF(x), $xØF(x) Þ Ø"xF(x) 第三組 其它常用推理定律 (1) "xA(x)Ú"xB(x) Þ "x(A(x)ÚB(x)) (2) $x(A(x)ÙB(x))Þ$xA(x)Ù$xB(x) (3) "x(A(x)®B(x)) Þ "xA(x)®"xB(x) (4) " x(A(x)®B(x)) Þ $xA(x)®$xB(x) 推理規(guī)則 "- 規(guī)則(US)：?xAx∴Ay或?xAx∴Ac x,y個體變項，c個體常項 "+規(guī)則(UG)：Ax∴?xAx x個體變項 $- 規(guī)則(ES)：∴?xAx∴Ac x個體變項, c個體常項 $+ 規(guī)則(EG)：Ay∴?xAx或B→Ay∴B→?xAx x,y個體變項，c個體常項 Ac∴?xAx或B→Ac∴B→?xAx 先用ES，再用US 自然推理系統(tǒng)N L ： 1. 字母表. 同一階語言L 的字母表 2. 合式公式. 同L的合式公式 3. 推理規(guī)則: (1) 前提引入規(guī)則 (2) 結(jié)論引入規(guī)則 (3) 置換規(guī)則 (4) 假言推理規(guī)則 (5) 附加規(guī)則 (6) 化簡規(guī)則 (7) 拒取式 (8) 假言三段論規(guī)則 (9) 析取三段論規(guī)則 (10) 構(gòu)造性二難推理規(guī)則 (11) 合取引入規(guī)則 (12) " -規(guī)則 (13) " +規(guī)則 (14) $ -規(guī)則 (15) $ +規(guī)則 【定義5.3】 集合論： A Í B Û "x ( xÎA ® xÎB )【定義6.1】 A = B Û A Í B Ù B Í A 【定義6.2】 A Ì B Û A Í B Ù A ¹ B 【定義6.3】 A ? B Û $x ( xÎA Ù xÏB ) 空集 Æ：不含有任何元素的集合【定義6.4】 空集是任何集合的子集?！径ɡ?.1】 冪集P(A) = { x | x Í A }【定義6.5】 如果 |A|=n，則 |P(A)|=2n 全集 E：包含了所有元素的集合【定義6.6】 并AÈB = {x | xÎA Ú xÎB} 交AÇB = {x | xÎA Ù xÎB} 差（相對補）A-B = {x | xÎA Ù xÏB}【定義6.7】 對稱差A(yù)ÅB = (A-B)È(B-A) 【定義6.8】 補（絕對補）~A = E-A = {x|xÏA}【定義6.9】 廣義并ÈA = { x | $z ( zÎA Ù xÎz )}【定義6.10】 廣義交ÇA = { x | "z ( zÎA ® xÎz )}【定義6.11】 集合恒等式 1.只涉及一個運算的算律： È Ç Å 交換 AÈB=BÈA AÇB=BÇA AÅB=BÅA 結(jié)合 (AÈB)ÈC=AÈ(BÈC) (AÇB)ÇC=AÇ(BÇC) (AÅB)ÅC=AÅ(BÅC) 冪等 AÈA=A AÇA=A 2．涉及兩個不同運算的算律： È與Ç Ç與Å 分配 AÈ(BÇC)=(AÈB)Ç(AÈC) AÇ(BÈC)=(AÇB)È(AÇC) AÇ(BÅC)=(AÇB)Å(AÇC) 吸收 AÈ(AÇB)=A AÇ(AÈB)=A 3．涉及補運算的算律： - ~ D.M律 A-(BÈC)=(A-B)Ç(A-C) A-(BÇC)=(A-B)È(A-C) ~(BÈC)=~BÇ~C ~(BÇC)=~BÈ~C 雙重否定 ~~A=A 4．涉及全集和空集的算律： Æ E 補元律 AÇ~A=Æ AÈ~A=E 零律 AÇÆ=Æ AÈE=E 同一律 AÈÆ=A AÇE=A 否定 ~Æ=E ~E=Æ 序偶（有序?qū)?）： 由兩個元素 x 和 y，按照一定的順序組成的二元組，記作<x,y>.【定義7.1】 笛卡兒積:設(shè)A,B為集合，A與B的笛卡兒積記作A´B定義為A´B = {<x,y>| xÎAÙyÎB}.【定義7.2】 笛卡爾積性質(zhì)：A=Æ或B=Æ時, A´B=Æ “ ´”不滿足結(jié)合律 A´(BÈC) = (A´B)È(A´C) 關(guān)系：（兩個定義） (1) 序偶的一個集合, 確定了一個二元關(guān)系R。R 中任一序偶 <x,y>,可記作 <x, y>ÎR 或 xRy【定義7.3】 (2) 笛卡爾積的子集： R Í A´B 【定義7.4】 空關(guān)系:Æ 全域關(guān)系：A×B 恒等關(guān)系 IA = {<x,x>| x∈A} 【定義7.5】 關(guān)系矩陣：若A={x1, x2, …, xm}，B={y1, y2, …, yn}，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR = [ rij ] m´n, 其中rij = 1Û < xi, yj> ÎR. 關(guān)系圖：若A= {x1, x2, …, xm}，R是從A上的關(guān)系，R的關(guān)系圖是GR=<A, R>, 其中A為結(jié)點集，R為邊集. 如果<xi,xj>屬于關(guān)系R，在圖中就有一條從 xi 到 xj 的有向邊. 前域(定義域) dom(R) = {x|$y.<x,y>ÎR} 值域 ran(R) ={y|$x.<x,y>ÎR} 域fld(R) = domR È ranR 【定義7.6】 逆關(guān)系R-1 = { <y, x> | <x, y>ÎR } 【定義7.7】 互逆 (R-1)-1 = R (R Ç S) -1 = R -1 Ç S -1 (RÈ S) -1 = R -1 È S -1 (A´ B) -1 = B´A (R - S) -1 = R -1 - S -1 復(fù)合關(guān)系 R°S = { <x, z> | $ y (<x, y>ÎR Ù <y, z>ÎS) }【定義7.8】 (Ro S)o P=Ro (So P) Rm = RoRo … oR 設(shè)RÍ X´ Y,SÍ Y´Z,則 (Ro S) -1 = S -1 o R -1 【定理7.2】 R在A上的限制R?A = { <x,y> | xRy∧x∈A } A在R下的像R[A]=ran(R?A) 【定義7.9】 自反的：若 "x∈A，都有<x,x>ÎR, 則稱 R 是自反的 反自反的：若 "x∈A，都有<x,x> Ï R, 則稱 R 是反自反的.【定義7.11】 對稱的：對任意x,yÎA,滿足, 若 <x,y>ÎR,則<y,x>ÎR 反對稱的：對任意x,yÎA,滿足，若 <x,y>ÎR且<y,x>ÎR,則x=y【定義7.12】 傳遞的：對任意的x,y,zÎA, 滿足:若<x,y>ÎR且<y,z>ÎR, 則<x,z>ÎR,則稱R是傳遞的【定義7.13】 自反閉包（對稱、傳遞） ： 設(shè)R是A上的二元關(guān)系,如果有另一個關(guān)系R'滿足: ① R'是自反（對稱、傳遞）的; ② R'ÊR; ③ 對于任何自反的關(guān)系R”,若R"ÊR, 則有R"ÊR'. 則稱關(guān)系R'為R的自反閉包. 記為 r(R)（ 對稱閉包 s(R) 和傳遞閉包 t(R)）。【定義7.14】 設(shè)R為A上的關(guān)系, 則有 (1) r(R)=R∪IA (2) s(R)=R∪R-1 (3) t(R)=R∪R2∪R3∪…（若|A|=n， 則 t(R)=R∪R2∪… ∪Rn ） 等價關(guān)系：設(shè) R 為集合 A 上的一個二元關(guān)系。若 R 是自反的, 對稱的, 傳遞的, 則稱 R 為 A 上的等價關(guān)系【定義7.15】 等價類 ：設(shè)R為集合A上的等價關(guān)系, 對"aÎA, 定義:[a]R = {x|xÎA 且 <a,x>ÎR}稱之為元素a關(guān)于R的等價類?！径x7.16】 給定A上的等價關(guān)系R,對于a,bÎA有<a,b>當且僅當[a]R=[b]R【定理17.4】 商集：設(shè)R是A上的等價關(guān)系，定義 A/R={[a]R|aÎA}稱之為A關(guān)于R的商集.【定義7.17】 劃分：設(shè)A為非空集合, 若A的子集族π(π Í P(A))滿足: (1) Æ Ïπ (2) "x"y(x,yÎπ∧x≠y®x∩y=Æ) (3) ∪π = A 則稱π是A的一個劃分, 稱π中的元素為A的劃分塊.【定義7.18】 給定集合 A 上的等價關(guān)系 R, 則商集 A/R 是 A 的一個劃分. 集合A的一個劃分π誘導(dǎo)出A上的一個等價關(guān)系R. R定義為R= {<x,y>| x,y ÎA 且x,y在π的同一分塊中} 設(shè)R1和R2為非空集合A上的一個等價關(guān)系,則 R1 = R2當且僅當A/R1 = A/R2. 偏序 ：設(shè)A是一個集合. 如果 A 上的二元關(guān)系 R 是自反的,反對稱的和傳遞的, 則稱R是A上的一個偏序關(guān)系. 記R為“£”, 且稱序偶<A,£> 為偏序集。【定義7.19】【定義7.22】 全序（線序）：設(shè) <A,£>為偏序集, 若對任 意的x,yÎA滿足: x£y或 y£x則稱 £ 為全序關(guān)系. <A,£>為全序集.【定義7.21】 覆蓋：設(shè)<A,£>為偏序集,若x,yÎA, x£y,x¹y且沒有其它元素z滿足x£z,z£y,則稱y覆蓋x. 記covA={ <x,y> |x,yÎA且y覆蓋x}【定義7.23】 哈斯圖：作圖規(guī)則 ① 用小元圈o代表元素; ② 若x£y且x¹y,則將代表y的小元圈畫在代表x的小元圈之上; ③ 若<x,y>ÎcovA, 則在x,y之間用直線連接。 你 極小元/極大元：設(shè)<A,£>為偏序集, BÍ A (1) 對bÎB，若B中不存在x滿足: b¹x且 x£b則稱b為B的極小元. (2) 對bÎB，若B中不存在x滿足: b¹x且 b£x則稱b為B的極大元. 最小元/最大元：設(shè)<A,£>為偏序集,BÍA,若有某個bÎB (1) 對于B中每一個元素x都有b£x，則稱b為B的最小元. (2) 對于B中每一個元素x都有x£b，則稱b為B的最大元.【定義7.24】 下界/上界：設(shè)<A,£>為偏序集, BÍ A (1) 若有aÎA,且對"xÎB 滿足 a£x，則稱a為B的下界。 進一步: 設(shè)a為B的下界,若B的所有下界y均有y£a,則稱a為B的下確界 ，記為glb B。 (2) 若有aÎA,且對"xÎB 滿足 x£a，則稱a為B的上界。 進一步: 設(shè)a為B的上界,若B的所有上界y均有a£y,則稱a為B的上確界 ，記為lub B。【定義7.25】 函數(shù)：設(shè)X,Y為兩個集合,fÍX´Y, 若對"xÎX,$!(唯一的)yÎY,滿足: <x,y>Îf,則稱f為函數(shù).記為:f:X®Y 定義域: domf=X 值域: ranf (有時記為f(X))={f(x)|xÎX}【定義8.1】 函數(shù)相等：設(shè)f和g都是從A到B的函數(shù), 若對任意xÎA,有f(x)=g(x),則稱f和g相等.記為f=g【定義8.2】 函數(shù)的個數(shù)：設(shè)f:A®B,|A|=m, |B|=n.記 BA={f|f: A®B}, 則| BA |= nm 滿射(到上映射)：設(shè) f: X ®Y, 若 ranf = Y, 則稱 f 為滿射的. 入射（單射）(一對一映射)：設(shè)f: X®Y, 對 " x1, x2 ÎX, 滿足:若 x1 ¹ x2, 則 f(x1) ¹ f(x2),稱 f 為入射的. 雙射 (一一對應(yīng)映射)：設(shè)f:X®Y, 若f既是滿射的, 又是入射的. 則稱f是雙射的.【定義8.6】 常函數(shù):設(shè) f:A→B, 如果存在c∈B使得對所有的 x∈A都有 f(x)=c, 則稱 f:A→B是常函數(shù). 恒等函數(shù):稱 A上的恒等關(guān)系IA為A上的恒等函數(shù), 對所有的x∈A都有IA(x)=x. 單調(diào)遞增:設(shè)<A, ?>, <B, ?>為偏序集，f:A→B，如果對任意的x1, x2∈A, x1?x2, 就有 f(x1)? f(x2), 則稱 f 為單調(diào)遞增的； 嚴格單調(diào)遞增:如果對任意的x1, x2∈A, x1?x2, 就有f(x1) ?f(x2), 則稱 f 為嚴格單調(diào)遞增的. 類似的也可以定義單調(diào)遞減和嚴格單調(diào)遞減的函數(shù) 特征函數(shù)：設(shè)A為集合, 對于任意的A'ÍA, A'的特征函數(shù)cA ' :A→{0,1}定義為cA'(a)=1, a∈A';cA'(a)=0, a∈A-A' 自然映射：設(shè)R是A上的等價關(guān)系, 令g:A→A/R；g(a)=[a], "a∈A稱 g 是從 A 到商集 A/R 的自然映射 【定義8.7】 復(fù)合函數(shù)：設(shè) f:X®Y,g:Y®Z, 定義: fo g = {<x,z>|xÎX且zÎZ且可找到y(tǒng)ÎY使y=f(x),z=g(y)} 稱fo g為f與 g 的復(fù)合函數(shù). 設(shè)f:A→B, g:B→C  (1) 如果 f:A→B, g:B→C是滿射的, 則 f°g:A→C也是滿射的 (2) 如果 f:A→B, g:B→C是單射的, 則 f°g:A→C也是單射的  (3) 如果 f:A→B, g:B→C是雙射的, 則 f°g:A→C也是雙射的  【定理8.2】 反函數(shù)（逆函數(shù)）：設(shè)f:X®Y是一個雙射函數(shù)，那么f -1是Y®X的雙射函數(shù). 稱f -1為f的反函數(shù). 互逆 (f -1 )-1=f 設(shè) f:A→B是雙射的, 則 f -1°f = IB, f °f -1 = IA 【定理8.5】 基數(shù)：用來衡量集合大小的一個概念. 對于有限集合集來說, 集合的基數(shù)就是其中所含元素的個數(shù). 等勢的：設(shè)A, B是集合, 如果存在著從A到B的雙射函數(shù), 就稱A和B是等勢的, 記作A≈B. 如果A不與B等勢, 則記作A?B. 注：通常將A的基數(shù)記為 |A|.【定義8.8】 N ≈ Z ≈ Q ≈ N×N 任何實數(shù)區(qū)間都與實數(shù)集合R等勢 {0,1}N≈R 康托定理 (1) N ? R； (2) 對任意集合A都有A?P(A).【定義8.7】 有限集(有窮集)/無限集 (無窮集) ： 設(shè)A為一個集合. 若存在某個自然數(shù)n, 使得A與集合{0,1,…,n-1}等勢, 則稱A是有限的. 若集合A不是有限的, 則稱A是無限的.【定義8.11】 À：實數(shù)集R的基數(shù)記作À, 即cardR =À 【定義8.12】 可數(shù)集(可列集)：設(shè)A為集合，若cardA≤À0，則稱A為可數(shù)集或可列集?！径x8.14】 與自然數(shù)集N等勢的任意集合稱為可數(shù)的. 其基數(shù)為À0 結(jié)論： (1) A為可數(shù)的當且僅當可排列成A={a1,a2,… ,an,…}的形式. (2) 任一無限集必含有可數(shù)子集. (3) 可數(shù)集的任何無限子集是可數(shù)的. (4) 可數(shù)個兩兩不相交的可數(shù)集合的并集,仍是一個可數(shù)集. (5) N´N是可數(shù)集. (6) 有理數(shù)的全體組成的集合是可數(shù)集. (7) 全體實數(shù)構(gòu)成的集合R是不可數(shù)的. 基數(shù)的常識： ① 對于有窮集合A, 基數(shù)是其元素個數(shù)n，|A| = n; ② 沒有最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到： 0, 1, 2, …, n, …, À0, À, … 代數(shù)結(jié)構(gòu) 運算：對于集合 A，f 是從An到 A 的函數(shù)，稱 f 為集合A上的一個n元運算。 【定義9.1】 交換律：已知<A，*>，若"x，y∈A，有x*y=y*x，稱*在A上是可交換的?！径x9.3】 結(jié)合律：已知<A，*>，若"x，y，z∈A，有x*（y*z）=（x*y）*z，稱*在A上是可結(jié)合的?！径x9.4】 冪等律：已知〈A，*〉，若"x∈A，x*x=x 則稱滿足冪等律 ?！径x9.5】 分配律：設(shè)<A，*，△>，若"x，y，z∈A有: x*(y△z)=（x*y）△（x*z） ; (y△z)*x=(y*x)△(z*x)稱運算*對△是可分配的?！径x9.6】 吸收律：設(shè)*,D是定義在集合A上的兩個可交換二元運算，若對"x,yÎ A,都有:x*(xD y) = x ； xD(x* y) = x則稱運算*和D滿足吸收律.【定義9.7】 單位元（幺元）: 設(shè)*是A上二元運算， el, er,eÎA 左幺元：若"xÎA，有el*x=x，稱el為運算*的左幺元； 右幺元：若"xÎA，有x*er=x，稱er為運算*的右幺元； 若e既是左幺元又是右幺元，稱e為運算*的幺元【定義9.8】 設(shè)*是A上的二元運算，具有左幺元el，右幺元er，則el=er=e 【定理9.1】 零元: 設(shè)*是A上二元運算， ql, qr, qÎA 左零元：若"xÎA，有ql*x=ql ，稱ql為運算*的左零元； 右零元： 若"xÎA，有x*qr=qr，稱qr為運算*的右零元； 若q既是左零元又是右零元，稱q為運算*的零元。 【定義9.9】 設(shè)*是A上的二元運算，具有左零元q l ，右零元qr， 則q l= q r= q【定理9.2】 逆元：設(shè)*是A上的二元運算，e是運算*的幺元，若x*y=e那對于運算*，x是y的左逆元，y是x的右逆元 存在逆元(左逆無，右逆元）的元素稱為可逆的（左可逆的，右可逆的）【定義9.10】 對于可結(jié)合運算ο ，如果元素x有 左逆元ｌ，右逆元r，則l=r=x－１【定理9.4】 消去律：已知<A，*>，若"x，y，z∈A，有 (1) 若 x*y = x*z且 x ¹q,則y=z；(左消去律) (2) 若 y*x = z*x且 x ¹q,則y=z；（右消去律） 那么稱*滿足消去律?！径x9.11】 代數(shù)系統(tǒng)：設(shè)A為非空集合，W為A上運算的集合,稱<A,W >為一個代數(shù)系統(tǒng).【定義9.12】 同類型的代數(shù)系統(tǒng)：如果兩個代數(shù)系統(tǒng)中運算的個數(shù)相同，對應(yīng)運算的元數(shù)相同，且代數(shù)常數(shù)的個數(shù)也相同，則稱它們是同類型的代數(shù)系統(tǒng).【定義9.13】 子代數(shù)：設(shè)V=<S, f1, f2, …, fk>是代數(shù)系統(tǒng)，B是S的非空子集，如果B對f1, f2, …, fk 都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱<B, f1, f2, …, fk>是V的子代數(shù)系統(tǒng)，簡稱子代數(shù)【定義9.14】 最大的子代數(shù)：就是V本身 最小的子代數(shù)：如果令V中所有代數(shù)常數(shù)構(gòu)成的集合是B，且B對V中所有的運算都是封閉的，則B就構(gòu)成了V的最小的子代數(shù) 平凡的子代數(shù):最大和最小的子代數(shù)稱為V 的平凡的子代數(shù) 真子代數(shù)：若B是S的真子集，則B構(gòu)成的子代數(shù)稱為V的真子代數(shù). 因子代數(shù)：設(shè)V1=<A,?>和V2=<B,*>是同類型的代數(shù)系統(tǒng)，?和*為二元運算，在集合A´B上如下定義二元運算?， "<a1,b1>,<a2,b2>ÎA´B，有<a1,b1>?<a2,b2>=<a1?a2, b1*b2> 稱V=<A´B,? >為V1與V2的積代數(shù)，記作V1´V2. 這時也稱V1和V2為V的因子代數(shù). 【定義9.15】 設(shè)V1=<A,?>和V2=<B,*>是同類型的代數(shù)系統(tǒng)，V1´V2=<A´B,?>是它們的積代數(shù). (1) 如果? 和 *運算是可交換（可結(jié)合、冪等）的，那幺?運算也是可交換（可結(jié)合、冪等）的 (2) 如果 e1 和 e2（q1和q2）分別為? 和 *運算的單位元（零元），那幺<e1,e2>（<q1,q2>）也是?運算的單位元（零元） (3) 如果 x 和 y 分別為?和 *運算的可逆元素，那幺<x,y>也是?運算的可逆元素，其逆元就是<x-1,y-1> 【定理9.5】 同態(tài):設(shè)V1=<A,°>和V2=<B,*>是同類型的代數(shù)系統(tǒng)，f:A®B，對"x, yÎA 有f(x°y) = f(x)*f(y), 則稱 f 是V1到V2的同態(tài)映射，簡稱同態(tài) (1) f 如果是單射，則稱為單同態(tài)。 (2) 如果是滿射，則稱為滿同態(tài)，這時稱V2是V1的同態(tài)像， 記作V1~V2。 (3) 如果是雙射，則稱為同構(gòu)，也稱代數(shù)系統(tǒng)V1同構(gòu)于V2， 記作V1@V2 。 (4) 如果V1=V2，則稱作自同態(tài)?！径x9.16】 半群：設(shè)V=<S, ° >是代數(shù)系統(tǒng)，°為二元運算，如果°運算是可結(jié)合的，則稱V為半群。 獨異點：設(shè)V=<S,°>是半群，若e∈S是關(guān)于°運算的單位元，則稱V是含幺半群，也叫做獨異點。 有時也將獨異點V 記作 V=<S,°,e>. 群：設(shè)V=<G,°>是獨異點，eÎ G關(guān)于°運算的單位元，若 "aÎG，a-1ÎG，則稱V是群(Group). 通常將群記作G. 【定義10.1】 群的階數(shù)：設(shè)<G,*>是一個群 有限群：如果G是有限集，那么稱<G,*>為有限群 階數(shù)：|G| 為該有限群的階數(shù)； 無限群：如果G是無限集，則稱<G,*>為無限群。 平凡群：階數(shù)為1（即只含單位元）的群稱為平凡群【定義10.2】 群的性質(zhì)：設(shè)<G,*>是一個群。 （1）非平凡群中不可能有零元. （2）對于"a,bÎ G, 必存在唯一的xÎ G,使得a* x =b. （3）對于"{a,b,c}Î G若: a*b = a*c或b*a = c*a則必有b=c (消去律)。 （4）運算表中的每一行或每一列都是一個置換。 （5）除幺元e外,不可能有任何別的冪等元。 元素的冪：設(shè)G是群，a∈G，n∈Z，則a 的 n次冪【定義10.3】 元素的階：設(shè)G是群，a∈G，使得等式 ak=e 成立的最小正整數(shù)k 稱為元素a 的階，記作|a|=k，稱 a 為 k 階元。若不存在這樣的正整數(shù) k，則稱 a 為無限階元?！径x10.4】 冪運算性質(zhì)： (1) "a∈G，(a-1)-1=a (2) "a,b∈G，(ab)-1=b-1a-1 (3) "a∈G，anam = an+m，n, m∈Z (4) "a∈G，(an)m = anm，n, m∈Z (5) 若G為交換群，則 (ab)n = anbn.【定理10.1】 元素的階的性質(zhì)：G為群，a∈G且 |a| = r. 設(shè)k是整數(shù)，則 (1) ak = e當且僅當r | k (r整除k) (2 )|a-1| = |a| 【定理10.3】 子群：設(shè)G 是群，H 是G 的非空子集， 如果H關(guān)于G中的運算構(gòu)成群，則稱H是G 的子群, 記作H≤G。 真子群：若H是G 的子群，且HÌG，則稱H是G的真子群，記作H<G. 平凡子群：對任何群G都存在子群. G和{e}都是G 的子群，稱為G 的平凡子群. 【定義10.5】 子群判定定理一：設(shè)G為群，H是G的非空子集，則H是G的子群當且僅當 (1) "a,b∈H有ab∈H； (2) "a∈H有a-1∈H?！径ɡ?0.4】 子群判定定理二：設(shè)G為群，H是G的非空子集. H是G的子群當且僅當"a,b∈H有ab-1∈H. 【定理10.5】 子群判定定理三：設(shè)G為群，H是G的非空有窮子集，則H是G的子群當且僅當"a,b∈H有ab∈H. 【定理10.6】 生成子群：設(shè)G為群，a∈G，令H={ak| k∈Z}，則H是G的子群，稱為由 a 生成的子群，記作<a>. 陪集：設(shè)<H,*>是群<G,*>的一個子群,aÎ G則: 左陪集：aH ::= {a}H，由a所確定的H在G中的左陪集. 右陪集：Ha::=H{a} 陪集是左陪集與右陪集的統(tǒng)稱. 【定義10.6】 陪集性質(zhì)：設(shè)H是群G的子群，則 ① He = H ② "a∈G 有a∈Ha ③ "a,b∈G有：a∈Hb Û ab-1∈H Û Ha=Hb ④ 在G上定義二元關(guān)系R： "a,b∈G, <a,b>∈R Û ab-1∈H則 R是G上的等價關(guān)系，且[a]R = Ha. ⑤ |Ha|=|H| 【定理10.7】【定理10.8】 拉格朗日定理：設(shè)G是有限群，H是G的子群，則|G| = |H|·[G:H] 其中[G:H] 是H在G中的不同右陪集(或左陪集) 數(shù)，稱為H在G 中的指數(shù).【定理10.10】 推論： （1） 設(shè)G是n階群，則"a∈G，|a|是n的因子，且an = e. （2） 對階為素數(shù)的群G，必存在a∈G使得G = <a>. 阿貝爾群（交換群）：若群G中的運算是可交換的，則稱G為交換群或阿貝爾群。 循環(huán)群：設(shè)G是群，若存在a∈G使得G={ak| k∈Z} 則稱G是循環(huán)群，記作G=<a>，稱 a 為G 的生成元.  n 階循環(huán)群: 設(shè)G=<a>是循環(huán)群，若a是n 階元，則 G = { a0=e, a1, a2, … , an-1 } 無限循環(huán)群: 若a 是無限階元，則 G = { a0=e, a±1, a±2, … }【定義10.7】 循環(huán)群的生成元:設(shè)G=<a>是循環(huán)群 (1) 若G是無限循環(huán)群，則G只有兩個生成元，即a和a-1.  (2)若G是n階循環(huán)群，則G含有f(n)個生成元. 對于任何小于n且與 n 互質(zhì)的數(shù)r∈{0,1,…,n-1}, ar是G的生成元.【定理10.11】 循環(huán)群的子群： (1)設(shè)G=<a>是循環(huán)群，則G的子群仍是循環(huán)群； (2) 若G=<a>是無限循環(huán)群，則G的子群除{e}以外都是無限循環(huán)群； (3) 若G=<a>是n階循環(huán)群，則對n的每個正因子d，G恰好含有一個d 階子群?！径ɡ?0.12】 環(huán)：設(shè)<R,+,·>是代數(shù)系統(tǒng)，+和·是二元運算. 如果滿足以下條件: (1) <R,+>構(gòu)成交換群； (2) <R,·>構(gòu)成半群； (3) · 運算關(guān)于+運算適合分配律， 則稱<R,+,·>是一個環(huán). 【定義10.11】 環(huán)的運算性質(zhì)：設(shè)<R,+,·>是環(huán)，則 (1) "a∈R，a0 = 0a = 0 (2) "a,b∈R，(-a)b = a(-b) = -ab (3) "a,b,c∈R，a(b-c) = ab-ac， (b-c)a = ba-ca (4) "a1,a2,...,an,b1,b2,...,bm∈R (n,m≥2)i=1naij=1mbj=i=1nj=1maibj【定理10.14】 設(shè)<R,+,·>是環(huán) 交換環(huán)：若環(huán)中乘法 · 適合交換律，則稱R是交換環(huán)； 含幺環(huán)：若環(huán)中乘法 · 存在單位元，則稱R是含幺環(huán)； 無零因子環(huán)：若"a,b∈R，ab=0 Þ a=0∨b=0，則稱R是無零因子環(huán)。 整環(huán)：設(shè)<R,+,·>是一個代數(shù)系統(tǒng),若滿足: (1) <R,+>是阿貝爾群； (2) <R,·>是可交換獨異點，且無零因子，即對"a,bÎR, a¹0,b¹0 則a· b¹0； (3) 運算·對+是可分配的， 則稱<R,+,·>是整環(huán) 域 ：設(shè)<R,+,·>是一個代數(shù)系統(tǒng),若滿足: (1) <R,+>是阿貝爾群； (2) <R-{0},·>是阿貝爾群； (3) 運算·對+是可分配的， 則稱<R,+,·>是域?！径x10.12】 格：設(shè)<S, ?>是偏序集，如果"x,yÎS，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序?作成一個格【定義11.1】 格的代數(shù)系統(tǒng)定義：設(shè)<S, ?, ? >是代數(shù)系統(tǒng), ?和?是二元運算, 如果?和?滿足交換律、結(jié)合律和吸收律, 則<S, ?,?>構(gòu)成格【定義11.3】 對偶命題：設(shè) f 是含有格中元素以及符號 =,? ,? ,∨和∧的命題. 令 f*是將 f 中的?替換成?,?替換成?,∨替換成∧,∧替換成∨所得到的命題. 稱 f* 為 f 的對偶命題【定義11.2】 格的對偶原理：設(shè) f 是含有格中元素以及符號=,?,?,∨和∧等的命題. 若 f 對一切格為真, 則 f 的對偶命題 f*也對一切格為真. 格的性質(zhì)：設(shè)<L, ?>是格, 則運算∨和∧適合交換律、結(jié)合律、冪等律和吸收律, 即 (1) "a,b∈L 有a∨b = b∨a, a∧b = b∧a (2) "a,b,c∈L 有 (a∨b)∨c = a∨(b∨c), (a∧b)∧c = a∧(b∧c) (3) "a∈L 有a∨a = a, a∧a = a (4) "a,b∈L 有a∨(a∧b) = a, a∧(a∨b) = a 【定理11.1】 格的序與運算性質(zhì)： 設(shè)L是格, 則"a,b∈L有a ? b Û a∧b = a Û a∨b = b 【定理11.3】 格的保序性質(zhì)： 設(shè)L是格, "a,b,c,d∈L，若a ? b 且 c ? d, 則a∧c ? b∧d, a∨c? b∨d 【定理11.4】 子格：設(shè)<L,∧,∨>是格, S是L的非空子集, 若S關(guān)于L中的運算∧和∨仍構(gòu)成格, 則稱S是L的子格【定義11.4】 分配格：設(shè)<L,∧,∨>是格, 若"a,b,c∈L,有 a∧(b∨c) = (a∧b)∨(a∧c) a∨(b∧c) = (a∨b)∧(a∨c) 則稱L為分配格.【定義11.5】 分配格的判別：設(shè)L是格, 則L是分配格當且僅當L不含有與鉆石格或五角格同構(gòu)的子格【定理11.5】 全下界：設(shè)L是格,若存在a∈L使得"x∈L有 a ? x, 則稱a為L的全下界； 全上界：設(shè)L是格,若存在b∈L使得"x∈L有 x ? b, 則稱b為L的全上界 ?！径x11.6】 有界格： 設(shè)L是格，若L存在全下界和全上界, 則稱L 為有界格，一般將有界格L記為<L,∧,∨,0,1>. 【定義11.7】 有界格的性質(zhì)：設(shè)<L,∧,∨,0,1>是有界格,則"a∈L有a∧0 = 0,a∨0 = a,a∧1 = a, a∨1=1 補元：設(shè)<L,∧,∨,0,1>是有界格, a∈L, 若存在b∈L 使得a∧b = 0 和 a∨b = 1成立, 則稱b是a的補元 【定義11.8】 有界分配格的補元惟一性定理：設(shè)<L,∧,∨,0,1>是有界分配格. 若L中元素 a 存在 補元, 則存在惟一的補元. 【定理11.6】 有補格 :設(shè)<L,∧,∨,0,1>是有界格,若L中所有元素都有補元存在, 則稱L為有補格.【定義11.9】 布爾格（布爾代數(shù)）：如果一個格是有補分配格, 則稱它為布爾格或布爾代數(shù). 布爾代數(shù)標記為<B,∧,∨,¢, 0, 1>, ¢為求補運算. 【定義11.10】 布爾代數(shù)的代數(shù)系統(tǒng)定義：設(shè)<B, ?,?>是代數(shù)系統(tǒng), ?和?是二元運算. 若?和?運算滿足： (1) 交換律, 即"a,b∈B有 a?b = b?a, a?b = b?a (2) 分配律, 即"a,b,c∈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) 補元律, 即"a∈B, 存在 a¢∈B 使得 a ?a¢ = 0, a?a¢ = 1 則稱 <B,?,?>是一個布爾代數(shù). 【定義11.11】 布爾代數(shù)的性質(zhì)：設(shè)<B,∧,∨, ¢, 0, 1>是布爾代數(shù), 則 (1) "a∈B, (a¢)¢ = a . (2) "a,b∈B, (a∧b)¢ = a¢∨b¢, (a∨b) ¢= a¢∧b¢ （德摩根律）【定理11.7】 原子：設(shè) L 是格, 0∈L, a∈L若"b∈L有 0 ? b ? a Û b = a, 則稱 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ù)都是同構(gòu)的 圖論 無序積：A&B={(x,y) | xÎA