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

《離散數(shù)學(xué)知識(shí)點(diǎn).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)知識(shí)點(diǎn).doc（23頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

說(shuō)明： 定義：紅色表示。 定理性質(zhì)：橙色表示。 公式：藍(lán)色表示。 算法: 綠色表示 頁(yè)碼：灰色表示 數(shù)理邏輯： 1. 命題公式：命題， 聯(lián)結(jié)詞(?，ù，ú，?，?)，合式公式，子公式 2. 公式的真值：賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式 3. 范式：析取范式，極小項(xiàng)，主析取范式，合取范式，極大項(xiàng)，主合取范式 4. 聯(lián)結(jié)詞的完備集：真值函數(shù)，異或，條件否定，與非，或非，聯(lián)結(jié)詞完備集 5. 推理理論：重言蘊(yùn)含式，有效結(jié)論，P規(guī)則，T規(guī)則， CP規(guī)則，推理 6. 謂詞與量詞:謂詞，個(gè)體詞，論域，全稱(chēng)量詞，存在量詞 7. 項(xiàng)與公式:項(xiàng)，原子公式，合式公式，自由變?cè)?，約束變?cè)?，轄域，換名，代入 8. 公式語(yǔ)義:解釋?zhuān)x值，有效的，可滿(mǎn)足的，不可滿(mǎn)足的 9. 前束范式:前束范式 10. 推理理論:邏輯蘊(yùn)含式，有效結(jié)論，"-規(guī)則（US），"+規(guī)則（UG）， $-規(guī)則(ES)，$+規(guī)則(EG), 推理 集合論： 1. 集合: 集合, 外延性原理, ?, í , ì, 空集, 全集, 冪集, 文氏圖, 交, 并, 差, 補(bǔ), 對(duì)稱(chēng)差 2. 關(guān)系: 序偶, 笛卡爾積, 關(guān)系, domR, ranR, 關(guān)系圖, 空關(guān)系, 全域關(guān)系, 恒等關(guān)系 3. 關(guān)系性質(zhì)與閉包:自反的, 反自反的, 對(duì)稱(chēng)的, 反對(duì)稱(chēng)的, 傳遞的,自反閉包 r(R),對(duì)稱(chēng)閉包 s(R), 傳遞閉包 t(R) 4. 等價(jià)關(guān)系: 等價(jià)關(guān)系, 等價(jià)類(lèi), 商集, 劃分 5. 偏序關(guān)系:偏序, 哈斯圖, 全序(線序), 極大元/極小元, 最大元/最小元, 上界/下界 6. 函數(shù): 函數(shù), 常函數(shù), 恒等函數(shù), 滿(mǎn)射,入射,雙射，反函數(shù), 復(fù)合函數(shù) 7. 集合基數(shù):基數(shù), 等勢(shì), 有限集/無(wú)限集, 可數(shù)集, 不可數(shù)集 代數(shù)結(jié)構(gòu)： 1. 運(yùn)算及其性質(zhì)：運(yùn)算，封閉的,可交換的,可結(jié)合的,可分配的,吸收律, 冪等的，幺元,零元,逆元 2. 代數(shù)系統(tǒng)：代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)，同態(tài)，同構(gòu)。 3. 群與子群：半群,子半群,元素的冪，獨(dú)異點(diǎn)，群，群的階數(shù)，子群,平凡子群，陪集，拉格朗日（Lagrange）定理 4. 阿貝爾群和循環(huán)群：阿貝爾群(交換群)，循環(huán)群,生成元 5. 環(huán)與域：環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域 6. 格與布爾代數(shù)：格，對(duì)偶原理，子格，分配格，有界格，有補(bǔ)格，布爾代數(shù)，有限布爾代數(shù)的表示定理 圖論： 1. 圖的基本概念：無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖，握手定理，圖的同構(gòu) 2. 圖的連通性:通路，回路，簡(jiǎn)單通路，簡(jiǎn)單回路（跡）初級(jí)通路（路徑），初級(jí)回路（圈），點(diǎn)連通，連通圖，點(diǎn)割集，割點(diǎn)，邊割集，割邊，點(diǎn)連通度，邊連通度，弱連通圖，單向連通圖，強(qiáng)連通圖，二部圖（二分圖） 3. 圖的矩陣表示：關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣 4. 歐拉圖與哈密頓圖：歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖 5. 無(wú)向樹(shù)與根樹(shù)：無(wú)向樹(shù)，生成樹(shù)，最小生成樹(shù)，Kruskal，根樹(shù)，m叉樹(shù)，最優(yōu)二叉樹(shù)，Huffman算法 6. 平面圖:平面圖，面，歐拉公式，Kuratoski定理 數(shù)理邏輯： 命題：具有確定真值的陳述句。 否定詞符號(hào)?：設(shè)p是一個(gè)命題，?p稱(chēng)為p的否定式。?p是真的當(dāng)且僅當(dāng)p是假的。p是真的當(dāng)且僅當(dāng)?p是假的?！径x1.1】 合取詞符號(hào)ù：設(shè)p，q是兩個(gè)命題，命題 “p并且q”稱(chēng)為p，q的合取，記以pùq，讀作p且q。pùq是真的當(dāng)且僅當(dāng)p和q都是真的?！径x1.2】 析取詞符號(hào)ú：設(shè)p，q是兩個(gè)命題，命題 “p或者q”稱(chēng)為p，q的析取，記以púq，讀作p或q。púq是真的當(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，記以p?q。p?q是假的當(dāng)且僅當(dāng)p是真的而q是假的。【定義1.4】 等價(jià)詞符號(hào) ?：設(shè)p，q是兩個(gè)命題，命題 “p當(dāng)且僅當(dāng)q”稱(chēng)為p等價(jià)q，記以p?q。p?q是真的當(dāng)且僅當(dāng)p，q或者都是真的，或者都是假的?！径x1.5】 合式公式: (1) 命題常元和變?cè)?hào)是合式公式； (2) 若A是合式公式，則(?A)是合式公式，稱(chēng)為A的否定式； (3) 若A，B是合式公式，則 (AúB)， (AùB)， (A?B)，(A?B)是合式公式； (4) 所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符號(hào)串。 子公式: 如果Ｘ是合式公式A的一部分，且Ｘ本身也是一個(gè)合式公式，則稱(chēng)Ｘ為公式A的子公式?！径x1.6】 賦值（指派，解釋?zhuān)? 設(shè)?是命題變?cè)?，則稱(chēng)函數(shù)v：? ? {1，0}是一個(gè)真值賦值?！径x1.8】 真值表：公式A在其所有可能的賦值下所取真值的表，稱(chēng)為A的真值表?！径x1.9】 重言式（永真式）:任意賦值v， v A 矛盾式（永假式）:任意賦值v， 有v A【定義1.10】 等值式：若等價(jià)式A?B是重言式，則稱(chēng)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? ^ 蘊(yùn)涵等值式 A?B??AúB 等價(jià)等值式 A?B?(A?B)ù(B?A) 假言易位 A?B??B??A 等價(jià)否定等值式A?B??A??B 歸謬論 (A?B)ù(A??B) ??A 置換規(guī)則： 設(shè)Ｘ是公式A的子公式, Ｘ? Y。將A中的Ｘ（可以是全部或部分X）用Y來(lái)置換，所得到的公式B，則 A?B。 文字: 設(shè)A??（命題變?cè)? 則A和 ? A都稱(chēng)為命題符號(hào)A的文字，其中前者稱(chēng)為正文字，后者稱(chēng)為負(fù)文字。【定義2.2】 析取范式：形如A1 ú A2 ú …ú An (n31) 的公式稱(chēng)為析取范式，其中Ai(i=1,…,n)是由文字組成的合取范式。 合取范式：形為A1ù A2 ù …ùAn (n3 1) 的公式稱(chēng)為合取范式，其中A1,…,An都是由文字組成的析取式?！径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é)詞的完備集?！径ɡ?.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】 重言蘊(yùn)含式：當(dāng)且僅當(dāng)P?Q是一個(gè)重言式時(shí)，稱(chēng)P重言蘊(yùn)含Q，記為PTQ。 有效結(jié)論：設(shè)A、C是兩個(gè)命題公式，若A T C，稱(chēng)C是A的有效結(jié)論。【定義3.1】 推理定律——重言蘊(yùn)涵式 1. A T (AúB) 附加律 2. (AùB) T A 化簡(jiǎn)律 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) T B 構(gòu)造性二難(特殊形式) 9. (A?B)ù(C?D)ù( ?Bú?D) T (?Aú?C) 破壞性二難 形式系統(tǒng): 一個(gè)形式系統(tǒng) I 由下面四個(gè)部分組成： (1) 非空的字母表，記作 A(I). (2) A(I) 中符號(hào)構(gòu)造的合式公式集，記作 E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作 R(I). 記 I=, 其中是 I 的形式語(yǔ)言系統(tǒng), 是 I 的形式演算系統(tǒng). 自然推理系統(tǒng): 無(wú)公理, 即AX(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,?, Ak到結(jié)論B的推理是一個(gè)公式序列C1, C2,?, Cl. 其中Ci(1￡i￡l)是某個(gè)Aj, 或者可由序列中前面的公式應(yīng)用推理規(guī)則得到, 并且Cl =B?！径x3.3】 CP規(guī)則(演繹定理)：若G è{R}|- S，則 G |- R?S, 其中G為命題公式的集合。 個(gè)體詞：用于表示命題中主語(yǔ)部分的符號(hào)或符號(hào)串。 個(gè)體常元 表示確指?jìng)€(gè)體。 個(gè)體變?cè)? 表示不確指?jìng)€(gè)體。 個(gè)體域: 個(gè)體變?cè)娜≈捣秶Ｓ肈表示。 量詞：限定個(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, …, tn是項(xiàng)，則f(t1, …, tn)是項(xiàng)； (3) 僅僅有限次使用(1)，(2)產(chǎn)生的符號(hào)串是項(xiàng)。 【定義4.2】 原子公式: 若P是一個(gè)元謂詞符號(hào)，t1,…,tn是項(xiàng), 則P(t1,…,tn)是原子公式?！径x4.3】 合式公式： (1) 原子公式是公式； (2) 若A是合式公式，則(? A)是合式公式； (3) 若A，B是公式，則(AúB)，(AùB)，A?B)，(A?B)是公式； (4) 若A是公式，x是變?cè)?，則"xA，$xA是公式； (5) 僅僅有限次使用１～４得到的符號(hào)串才是合式公式。 【定義4.4】 設(shè)公式 a的一個(gè)子公式為" x A或$ x A。則稱(chēng)： 指導(dǎo)變?cè)簒是"或$的指導(dǎo)變?cè)? 轄域：A是相應(yīng)量詞的轄域。 約束出現(xiàn)：轄域中x的一切出現(xiàn)，以及(" x)中的x稱(chēng)為x在a中的約束出現(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è)溆嗖糠植蛔儭? （2） 換名時(shí)最好選用轄域中未出現(xiàn)的變?cè)? 變?cè)耄捍雽?duì)自由變?cè)M(jìn)行。不能改變約束關(guān)系。 解釋?zhuān)?謂詞語(yǔ)言的一個(gè)解釋 I= (D, j )包括： (1) 非空集合D，稱(chēng)之為論域； (2) 對(duì)應(yīng)于每一個(gè)個(gè)體常元a， j(a)?D； (3) 對(duì)應(yīng)于每一個(gè)n元函數(shù)符號(hào)f都有一個(gè)函數(shù) j(f):Dn ? D； (4) 對(duì)應(yīng)于每一個(gè)n元謂詞符號(hào)A都有一個(gè)n元關(guān)系j(A) í Dn?！径x4.7】 賦值：解釋I中的賦值v為每一個(gè)個(gè)體變?cè)獂指定一個(gè)值v(x ）? D，即設(shè) V為所個(gè)體變?cè)募希瑒t賦值v是函數(shù) v:V ? D. 可滿(mǎn)足的：給定公式A，若在某一解釋中至少有一種賦值使A取值為1，則稱(chēng)A為可滿(mǎn)足的。否則稱(chēng)A是不可滿(mǎn)足的。 等值式A ? B：若A?B是有效的【定義5.1】 幾類(lèi)等值式 （1）命題公式的推廣 e.g. P(x) ? Q(x) ? ? P(x) ú Q(x) （2）否定深入 ? " x P(x) ? $ x(? P(x)) ? $ xP(x) ? " x (? P(x)) （3）量詞作用域的擴(kuò)張與收縮 設(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）多個(gè)量詞的使用 " 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中某量詞轄域中個(gè)體變項(xiàng)的所有約束出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)獡Q成該量詞轄域中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，其余部分不變，設(shè)所得公式為A￠，則A￠?A. 前束范式：如果謂詞公式A有如下形狀：Q1x1…QnxnM，其中 Qixi或者是"xi，或者是$xi，i=1，…，n，M是不含量詞的公式， Q1x1…Qnxn稱(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è)? 步2. 將所有的否定號(hào)?深入到量詞后面。 步3. 將量詞符號(hào)移至公式最外層。 邏輯蘊(yùn)含式A T C：當(dāng)且僅當(dāng)A?C是有效的。 幾類(lèi)邏輯蘊(yùn)涵式 第一組 命題邏輯推理定理的代換實(shí)例 如, "xF(x)ù$yG(y) T "xF(x) 第二組 基本等值式生成的推理定理 如, "xF(x) T??"xF(x), ??"xF(x) T"xF(x) ?"xF(x)T$x?F(x), $x?F(x) T ?"xF(x) 第三組 其它常用推理定律 (1) "xA(x)ú"xB(x) T "x(A(x)úB(x)) (2) $x(A(x)ùB(x))T$xA(x)ù$xB(x) (3) "x(A(x)?B(x)) T "xA(x)?"xB(x) (4) " x(A(x)?B(x)) T $xA(x)?$xB(x) 推理規(guī)則 "- 規(guī)則(US)：?xAx∴Ay或?xAx∴Ac x,y個(gè)體變項(xiàng)，c個(gè)體常項(xiàng) "+規(guī)則(UG)：Ax∴?xAx x個(gè)體變項(xiàng) $- 規(guī)則(ES)：∴?xAx∴Ac x個(gè)體變項(xiàng), c個(gè)體常項(xiàng) $+ 規(guī)則(EG)：Ay∴?xAx或B→Ay∴B→?xAx x,y個(gè)體變項(xiàng)，c個(gè)體常項(xiàng) Ac∴?xAx或B→Ac∴B→?xAx 先用ES，再用US 自然推理系統(tǒng)N L ： 1. 字母表. 同一階語(yǔ)言L 的字母表 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】 集合論： A í B ? "x ( x?A ? x?B )【定義6.1】 A = B ? A í B ù B í A 【定義6.2】 A ì B ? A í B ù A 1 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} 差（相對(duì)補(bǔ)）A-B = {x | x?A ù x?B}【定義6.7】 對(duì)稱(chēng)差A(yù)?B = (A-B)è(B-A) 【定義6.8】 補(bǔ)（絕對(duì)補(bǔ)）~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.只涉及一個(gè)運(yùn)算的算律： è ? ? 交換 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．涉及兩個(gè)不同運(yùn)算的算律： è與? ?與? 分配 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．涉及補(bǔ)運(yùn)算的算律： - ~ 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 補(bǔ)元律 A?~A=? Aè~A=E 零律 A??=? AèE=E 同一律 Aè?=A A?E=A 否定 ~?=E ~E=? 序偶（有序?qū)?）： 由兩個(gè)元素 x 和 y，按照一定的順序組成的二元組，記作.【定義7.1】 笛卡兒積:設(shè)A,B為集合，A與B的笛卡兒積記作A′B定義為A′B = {| x?Aùy?B}.【定義7.2】 笛卡爾積性質(zhì)：A=?或B=?時(shí), A′B=? “ ′”不滿(mǎn)足結(jié)合律 A′(BèC) = (A′B)è(A′C) 關(guān)系：（兩個(gè)定義） (1) 序偶的一個(gè)集合, 確定了一個(gè)二元關(guān)系R。R 中任一序偶 ,可記作 ?R 或 xRy【定義7.3】 (2) 笛卡爾積的子集： R í A′B 【定義7.4】 空關(guān)系:? 全域關(guān)系：A×B 恒等關(guān)系 IA = {| 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為結(jié)點(diǎn)集，R為邊集. 如果屬于關(guān)系R，在圖中就有一條從 xi 到 xj 的有向邊. 前域(定義域) dom(R) = {x|$y.?R} 值域 ran(R) ={y|$x.?R} 域fld(R) = domR è ranR 【定義7.6】 逆關(guān)系R-1 = { | ?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 = { | $ y (?R ù ?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 = { | xRy∧x∈A } A在R下的像R[A]=ran(R?A) 【定義7.9】 自反的：若 "x∈A，都有?R, 則稱(chēng) R 是自反的 反自反的：若 "x∈A，都有 ? R, 則稱(chēng) R 是反自反的.【定義7.11】 對(duì)稱(chēng)的：對(duì)任意x,y?A,滿(mǎn)足, 若 ?R,則?R 反對(duì)稱(chēng)的：對(duì)任意x,y?A,滿(mǎn)足，若 ?R且?R,則x=y【定義7.12】 傳遞的：對(duì)任意的x,y,z?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)=R∪IA (2) s(R)=R∪R-1 (3) t(R)=R∪R2∪R3∪…（若|A|=n， 則 t(R)=R∪R2∪… ∪Rn ） 等價(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ì)"a?A, 定義:[a]R = {x|x?A 且 ?R}稱(chēng)之為元素a關(guān)于R的等價(jià)類(lèi)?！径x7.16】 給定A上的等價(jià)關(guān)系R,對(duì)于a,b?A有當(dāng)且僅當(dāng)[a]R=[b]R【定理17.4】 商集：設(shè)R是A上的等價(jià)關(guān)系，定義 A/R={[a]R|a?A}稱(chēng)之為A關(guān)于R的商集.【定義7.17】 劃分：設(shè)A為非空集合, 若A的子集族π(π í P(A))滿(mǎn)足: (1) ? ?π (2) "x"y(x,y?π∧x≠y?x∩y=?) (3) ∪π = A 則稱(chēng)π是A的一個(gè)劃分, 稱(chēng)π中的元素為A的劃分塊.【定義7.18】 給定集合 A 上的等價(jià)關(guān)系 R, 則商集 A/R 是 A 的一個(gè)劃分. 集合A的一個(gè)劃分π誘導(dǎo)出A上的一個(gè)等價(jià)關(guān)系R. R定義為R= {| x,y ?A 且x,y在π的同一分塊中} 設(shè)R1和R2為非空集合A上的一個(gè)等價(jià)關(guān)系,則 R1 = R2當(dāng)且僅當(dāng)A/R1 = A/R2. 偏序 ：設(shè)A是一個(gè)集合. 如果 A 上的二元關(guān)系 R 是自反的,反對(duì)稱(chēng)的和傳遞的, 則稱(chēng)R是A上的一個(gè)偏序關(guān)系. 記R為“￡”, 且稱(chēng)序偶 為偏序集?！径x7.19】【定義7.22】 全序（線序）：設(shè) 為偏序集, 若對(duì)任 意的x,y?A滿(mǎn)足: x￡y或 y￡x則稱(chēng) ￡ 為全序關(guān)系. 為全序集.【定義7.21】 覆蓋：設(shè)為偏序集,若x,y?A, x￡y,x1y且沒(méi)有其它元素z滿(mǎn)足x￡z,z￡y,則稱(chēng)y覆蓋x. 記covA={ |x,y?A且y覆蓋x}【定義7.23】 哈斯圖：作圖規(guī)則 ① 用小元圈o代表元素; ② 若x￡y且x1y,則將代表y的小元圈畫(huà)在代表x的小元圈之上; ③ 若?covA, 則在x,y之間用直線連接。 你 極小元/極大元：設(shè)為偏序集, Bí A (1) 對(duì)b?B，若B中不存在x滿(mǎn)足: b1x且 x￡b則稱(chēng)b為B的極小元. (2) 對(duì)b?B，若B中不存在x滿(mǎn)足: b1x且 b￡x則稱(chēng)b為B的極大元. 最小元/最大元：設(shè)為偏序集,BíA,若有某個(gè)b?B (1) 對(duì)于B中每一個(gè)元素x都有b￡x，則稱(chēng)b為B的最小元. (2) 對(duì)于B中每一個(gè)元素x都有x￡b，則稱(chēng)b為B的最大元.【定義7.24】 下界/上界：設(shè)為偏序集, Bí A (1) 若有a?A,且對(duì)"x?B 滿(mǎn)足 a￡x，則稱(chēng)a為B的下界。 進(jìn)一步: 設(shè)a為B的下界,若B的所有下界y均有y￡a,則稱(chēng)a為B的下確界 ，記為glb B。 (2) 若有a?A,且對(duì)"x?B 滿(mǎn)足 x￡a，則稱(chēng)a為B的上界。 進(jìn)一步: 設(shè)a為B的上界,若B的所有上界y均有a￡y,則稱(chēng)a為B的上確界 ，記為lub B?！径x7.25】 函數(shù)：設(shè)X,Y為兩個(gè)集合,fíX′Y, 若對(duì)"x?X,$!(唯一的)y?Y,滿(mǎn)足: ?f,則稱(chēng)f為函數(shù).記為:f:X?Y 定義域: domf=X 值域: ranf (有時(shí)記為f(X))={f(x)|x?X}【定義8.1】 函數(shù)相等：設(shè)f和g都是從A到B的函數(shù), 若對(duì)任意x?A,有f(x)=g(x),則稱(chēng)f和g相等.記為f=g【定義8.2】 函數(shù)的個(gè)數(shù)：設(shè)f:A?B,|A|=m, |B|=n.記 BA={f|f: A?B}, 則| BA |= nm 滿(mǎn)射(到上映射)：設(shè) f: X ?Y, 若 ranf = Y, 則稱(chēng) f 為滿(mǎn)射的. 入射（單射）(一對(duì)一映射)：設(shè)f: X?Y, 對(duì) " x1, x2 ?X, 滿(mǎn)足:若 x1 1 x2, 則 f(x1) 1 f(x2),稱(chēng) f 為入射的. 雙射 (一一對(duì)應(yīng)映射)：設(shè)f:X?Y, 若f既是滿(mǎn)射的, 又是入射的. 則稱(chēng)f是雙射的.【定義8.6】 常函數(shù):設(shè) f:A→B, 如果存在c∈B使得對(duì)所有的 x∈A都有 f(x)=c, 則稱(chēng) f:A→B是常函數(shù). 恒等函數(shù):稱(chēng) A上的恒等關(guān)系IA為A上的恒等函數(shù), 對(duì)所有的x∈A都有IA(x)=x. 單調(diào)遞增:設(shè), 為偏序集，f:A→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ù)cA ' :A→{0,1}定義為cA'(a)=1, a∈A';cA'(a)=0, a∈A-A' 自然映射：設(shè)R是A上的等價(jià)關(guān)系, 令g:A→A/R；g(a)=[a], "a∈A稱(chēng) g 是從 A 到商集 A/R 的自然映射 【定義8.7】 復(fù)合函數(shù)：設(shè) f:X?Y,g:Y?Z, 定義: fo g = {|x?X且z?Z且可找到y(tǒng)?Y使y=f(x),z=g(y)} 稱(chēng)fo g為f與 g 的復(fù)合函數(shù). 設(shè)f:A→B, g:B→C? (1) 如果 f:A→B, g:B→C是滿(mǎn)射的, 則 f°g:A→C也是滿(mǎn)射的 (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是一個(gè)雙射函數(shù)，那么f -1是Y?X的雙射函數(shù). 稱(chēng)f -1為f的反函數(shù). 互逆 (f -1 )-1=f 設(shè) f:A→B是雙射的, 則 f -1°f = IB, f °f -1 = IA 【定理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ù)記為 |A|.【定義8.8】 N ≈ Z ≈ Q ≈ N×N 任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合R等勢(shì) {0,1}N≈R 康托定理 (1) N ? R； (2) 對(duì)任意集合A都有A?P(A).【定義8.7】 有限集(有窮集)/無(wú)限集 (無(wú)窮集) ： 設(shè)A為一個(gè)集合. 若存在某個(gè)自然數(shù)n, 使得A與集合{0,1,…,n-1}等勢(shì), 則稱(chēng)A是有限的. 若集合A不是有限的, 則稱(chēng)A是無(wú)限的.【定義8.11】 à：實(shí)數(shù)集R的基數(shù)記作à, 即cardR =à 【定義8.12】 可數(shù)集(可列集)：設(shè)A為集合，若cardA≤à0，則稱(chēng)A為可數(shù)集或可列集。【定義8.14】 與自然數(shù)集N等勢(shì)的任意集合稱(chēng)為可數(shù)的. 其基數(shù)為à0 結(jié)論： (1) A為可數(shù)的當(dāng)且僅當(dāng)可排列成A={a1,a2,… ,an,…}的形式. (2) 任一無(wú)限集必含有可數(shù)子集. (3) 可數(shù)集的任何無(wú)限子集是可數(shù)的. (4) 可數(shù)個(gè)兩兩不相交的可數(shù)集合的并集,仍是一個(gè)可數(shù)集. (5) N′N(xiāo)是可數(shù)集. (6) 有理數(shù)的全體組成的集合是可數(shù)集. (7) 全體實(shí)數(shù)構(gòu)成的集合R是不可數(shù)的. 基數(shù)的常識(shí)： ① 對(duì)于有窮集合A, 基數(shù)是其元素個(gè)數(shù)n，|A| = n; ② 沒(méi)有最大的基數(shù)。將已知的基數(shù)按從小到大的順序排列就得到： 0, 1, 2, …, n, …, à0, à, … 代數(shù)結(jié)構(gòu) 運(yùn)算：對(duì)于集合 A，f 是從An到 A 的函數(shù)，稱(chēng) f 為集合A上的一個(gè)n元運(yùn)算。 【定義9.1】 交換律：已知，若"x，y∈A，有x*y=y*x，稱(chēng)*在A上是可交換的?！径x9.3】 結(jié)合律：已知，若"x，y，z∈A，有x*（y*z）=（x*y）*z，稱(chēng)*在A上是可結(jié)合的?！径x9.4】 冪等律：已知〈A，*〉，若"x∈A，x*x=x 則稱(chēng)滿(mǎn)足冪等律 ?！径x9.5】 分配律：設(shè)，若"x，y，z∈A有: x*(y△z)=（x*y）△（x*z） ; (y△z)*x=(y*x)△(z*x)稱(chēng)運(yùn)算*對(duì)△是可分配的?！径x9.6】 吸收律：設(shè)*,D是定義在集合A上的兩個(gè)可交換二元運(yùn)算，若對(duì)"x,y? A,都有:x*(xD y) = x ； xD(x* y) = x則稱(chēng)運(yùn)算*和D滿(mǎn)足吸收律.【定義9.7】 單位元（幺元）: 設(shè)*是A上二元運(yùn)算， el, er,e?A 左幺元：若"x?A，有el*x=x，稱(chēng)el為運(yùn)算*的左幺元； 右幺元：若"x?A，有x*er=x，稱(chēng)er為運(yùn)算*的右幺元； 若e既是左幺元又是右幺元，稱(chēng)e為運(yùn)算*的幺元【定義9.8】 設(shè)*是A上的二元運(yùn)算，具有左幺元el，右幺元er，則el=er=e 【定理9.1】 零元: 設(shè)*是A上二元運(yùn)算， ql, qr, q?A 左零元：若"x?A，有ql*x=ql ，稱(chēng)ql為運(yùn)算*的左零元； 右零元： 若"x?A，有x*qr=qr，稱(chēng)qr為運(yùn)算*的右零元； 若q既是左零元又是右零元，稱(chēng)q為運(yùn)算*的零元。 【定義9.9】 設(shè)*是A上的二元運(yùn)算，具有左零元q l ，右零元qr， 則q l= q r= q【定理9.2】 逆元：設(shè)*是A上的二元運(yùn)算，e是運(yùn)算*的幺元，若x*y=e那對(duì)于運(yùn)算*，x是y的左逆元，y是x的右逆元 存在逆元(左逆無(wú)，右逆元）的元素稱(chēng)為可逆的（左可逆的，右可逆的）【定義9.10】 對(duì)于可結(jié)合運(yùn)算ο ，如果元素x有 左逆元ｌ，右逆元r，則l=r=x－１【定理9.4】 消去律：已知，若"x，y，z∈A，有 (1) 若 x*y = x*z且 x 1q,則y=z；(左消去律) (2) 若 y*x = z*x且 x 1q,則y=z；（右消去律） 那么稱(chēng)*滿(mǎn)足消去律?！径x9.11】 代數(shù)系統(tǒng)：設(shè)A為非空集合，W為A上運(yùn)算的集合,稱(chēng)為一個(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è)V=是代數(shù)系統(tǒng)，B是S的非空子集，如果B對(duì)f1, f2, …, fk 都是封閉的，且B和S含有相同的代數(shù)常數(shù)，則稱(chēng)是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=和V2=是同類(lèi)型的代數(shù)系統(tǒng)，?和*為二元運(yùn)算，在集合A′B上如下定義二元運(yùn)算?， ",?A′B，有?= 稱(chēng)V=為V1與V2的積代數(shù)，記作V1′V2. 這時(shí)也稱(chēng)V1和V2為V的因子代數(shù). 【定義9.15】 設(shè)V1=和V2=是同類(lèi)型的代數(shù)系統(tǒng)，V1′V2=是它們的積代數(shù). (1) 如果? 和 *運(yùn)算是可交換（可結(jié)合、冪等）的，那幺?運(yùn)算也是可交換（可結(jié)合、冪等）的 (2) 如果 e1 和 e2（q1和q2）分別為? 和 *運(yùn)算的單位元（零元），那幺（）也是?運(yùn)算的單位元（零元） (3) 如果 x 和 y 分別為?和 *運(yùn)算的可逆元素，那幺也是?運(yùn)算的可逆元素，其逆元就是 【定理9.5】 同態(tài):設(shè)V1=和V2=是同類(lèi)型的代數(shù)系統(tǒng)，f:A?B，對(duì)"x, y?A 有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)像， 記作V1~V2。 (3) 如果是雙射，則稱(chēng)為同構(gòu)，也稱(chēng)代數(shù)系統(tǒng)V1同構(gòu)于V2， 記作V1@V2 。 (4) 如果V1=V2，則稱(chēng)作自同態(tài)?！径x9.16】 半群：設(shè)V=是代數(shù)系統(tǒng)，°為二元運(yùn)算，如果°運(yùn)算是可結(jié)合的，則稱(chēng)V為半群。 獨(dú)異點(diǎn)：設(shè)V=是半群，若e∈S是關(guān)于°運(yùn)算的單位元，則稱(chēng)V是含幺半群，也叫做獨(dú)異點(diǎn)。 有時(shí)也將獨(dú)異點(diǎn)V 記作 V=. 群：設(shè)V=是獨(dú)異點(diǎn)，e? G關(guān)于°運(yùn)算的單位元，若 "a?G，a-1?G，則稱(chēng)V是群(Group). 通常將群記作G. 【定義10.1】 群的階數(shù)：設(shè)是一個(gè)群 有限群：如果G是有限集，那么稱(chēng)為有限群 階數(shù)：|G| 為該有限群的階數(shù)； 無(wú)限群：如果G是無(wú)限集，則稱(chēng)為無(wú)限群。 平凡群：階數(shù)為1（即只含單位元）的群稱(chēng)為平凡群【定義10.2】 群的性質(zhì)：設(shè)是一個(gè)群。 （1）非平凡群中不可能有零元. （2）對(duì)于"a,b? G, 必存在唯一的x? G,使得a* x =b. （3）對(duì)于"{a,b,c}? G若: a*b = a*c或b*a = c*a則必有b=c (消去律)。 （4）運(yùn)算表中的每一行或每一列都是一個(gè)置換。 （5）除幺元e外,不可能有任何別的冪等元。 元素的冪：設(shè)G是群，a∈G，n∈Z，則a 的 n次冪【定義10.3】 元素的階：設(shè)G是群，a∈G，使得等式 ak=e 成立的最小正整數(shù)k 稱(chēng)為元素a 的階，記作|a|=k，稱(chēng) a 為 k 階元。若不存在這樣的正整數(shù) k，則稱(chēng) a 為無(wú)限階元?！径x10.4】 冪運(yùn)算性質(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當(dāng)且僅當(dāng)r | k (r整除k) (2 )|a-1| = |a| 【定理10.3】 子群：設(shè)G 是群，H 是G 的非空子集， 如果H關(guān)于G中的運(yùn)算構(gòu)成群，則稱(chēng)H是G 的子群, 記作H≤G。 真子群：若H是G 的子群，且HìG，則稱(chēng)H是G的真子群，記作H. 陪集：設(shè)是群的一個(gè)子群,a? G則: 左陪集：aH ::= {a}H，由a所確定的H在G中的左陪集. 右陪集：Ha::=H{a} 陪集是左陪集與右陪集的統(tǒng)稱(chē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, ∈R ? ab-1∈H則 R是G上的等價(jià)關(guān)系，且[a]R = Ha. ⑤ |Ha|=|H| 【定理10.7】【定理10.8】 拉格朗日定理：設(shè)G是有限群，H是G的子群，則|G| = |H|·[G:H] 其中[G:H] 是H在G中的不同右陪集(或左陪集) 數(shù)，稱(chēng)為H在G 中的指數(shù).【定理10.10】 推論： （1） 設(shè)G是n階群，則"a∈G，|a|是n的因子，且an = e. （2） 對(duì)階為素?cái)?shù)的群G，必存在a∈G使得G = . 阿貝爾群（交換群）：若群G中的運(yùn)算是可交換的，則稱(chēng)G為交換群或阿貝爾群。 循環(huán)群：設(shè)G是群，若存在a∈G使得G={ak| k∈Z} 則稱(chēng)G是循環(huán)群，記作G=，稱(chēng) a 為G 的生成元.? n 階循環(huán)群: 設(shè)G=是循環(huán)群，若a是n 階元，則 G = { a0=e, a1, a2, … , an-1 } 無(wú)限循環(huán)群: 若a 是無(wú)限階元，則 G = { a0=e, a±1, a±2, … }【定義10.7】 循環(huán)群的生成元:設(shè)G=是循環(huán)群 (1) 若G是無(wú)限循環(huán)群，則G只有兩個(gè)生成元，即a和a-1.? (2)若G是n階循環(huán)群，則G含有f(n)個(gè)生成元. 對(duì)于任何小于n且與 n 互質(zhì)的數(shù)r∈{0,1,…,n-1}, ar是G的生成元.【定理10.11】 循環(huán)群的子群： (1)設(shè)G=是循環(huán)群，則G的子群仍是循環(huán)群； (2) 若G=是無(wú)限循環(huán)群，則G的子群除{e}以外都是無(wú)限循環(huán)群； (3) 若G=是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) 構(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) "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è)是環(huán) 交換環(huán)：若環(huán)中乘法 · 適合交換律，則稱(chēng)R是交換環(huán)； 含幺環(huán)：若環(huán)中乘法 · 存在單位元，則稱(chēng)R是含幺環(huán)； 無(wú)零因子環(huán)：若"a,b∈R，ab=0 T a=0∨b=0，則稱(chēng)R是無(wú)零因子環(huán)。 整環(huán)：設(shè)是一個(gè)代數(shù)系統(tǒng),若滿(mǎn)足: (1) 是阿貝爾群； (2) 是可交換獨(dú)異點(diǎn)，且無(wú)零因子，即對(duì)"a,b?R, a10,b10 則a· b10； (3) 運(yùn)算·對(duì)+是可分配的， 則稱(chēng)是整環(huán) 域 ：設(shè)是一個(gè)代數(shù)系統(tǒng),若滿(mǎn)足: (1) 是阿貝爾群； (2) 是阿貝爾群； (3) 運(yùn)算·對(duì)+是可分配的， 則稱(chēng)是域。【定義10.12】 格：設(shè)是偏序集，如果"x,y?S，{x,y}都有最小上界和最大下界，則稱(chēng)S關(guān)于偏序?作成一個(gè)格【定義11.1】 格的代數(shù)系統(tǒng)定義：設(shè)是代數(shù)系統(tǒng), ?和?是二元運(yùn)算, 如果?和?滿(mǎn)足交換律、結(jié)合律和吸收律, 則構(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è)是格, 則運(yùn)算∨和∧適合交換律、結(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】 格的序與運(yùn)算性質(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è)是格, S是L的非空子集, 若S關(guān)于L中的運(yùn)算∧和∨仍構(gòu)成格, 則稱(chēng)S是L的子格【定義11.4】 分配格：設(shè)是格, 若"a,b,c∈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)的全上界?。【定義11.6】 有界格： 設(shè)L是格，若L存在全下界和全上界, 則稱(chēng)L 為有界格，一般將有界格L記為. 【定義11.7】 有界格的性質(zhì)：設(shè)是有界格,則"a∈L有a∧0 = 0,a∨0 = a,a∧1 = a, a∨1=1 補(bǔ)元：設(shè)是有界格, a∈L, 若存在b∈L 使得a∧b = 0 和 a∨b = 1成立, 則稱(chēng)b是a的補(bǔ)元 【定義11.8】 有界分配格的補(bǔ)元惟一性定理：設(shè)是有界分配格. 若L中元素 a 存在 補(bǔ)元, 則存在惟一的補(bǔ)元. 【定理11.6】 有補(bǔ)格 :設(shè)是有界格,若L中所有元素都有補(bǔ)元存在, 則稱(chēng)L為有補(bǔ)格.【定義11.9】 布爾格（布爾代數(shù)）：如果一個(gè)格是有補(bǔ)分配格, 則稱(chēng)它為布爾格或布爾代數(shù). 布爾代數(shù)標(biāo)記為, ￠為求補(bǔ)運(yùn)算. 【定義11.10】 布爾代數(shù)的代數(shù)系統(tǒng)定義：設(shè)是代數(shù)系統(tǒng), ?和?是二元運(yùn)算. 若?和?運(yùn)算滿(mǎn)足： (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) 補(bǔ)元律, 即"a∈B, 存在 a￠∈B 使得 a ?a￠ = 0, a?a￠ = 1 則稱(chēng) 是一個(gè)布爾代數(shù). 【定義11.11】 布爾代數(shù)的性質(zhì)：設(shè)是布爾代數(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, 則稱(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&B={(x,y) | x?A