離散數(shù)學(xué)課本定義和定理

1、.第1章集合1.1集合的基本概念1. 集合、元（元素） 、有限集、無限集、空集2. 表示集合的方法：列舉法、描述法3.定義 （子集 ）：給定集合A 和 B，如果集合A 的任何一個(gè)元都是集合B 中的元，則稱集合 A 包含于 B 或 B 包含 A，記為或，并稱 A 為 B 的一個(gè)子集。如果集合 A 和 B 滿足，但 B 中有元不屬于A，則稱集合A 真包含于 B，記為，并且稱 A 為 B 的一個(gè)真子集。4. 定義（冪集）：給定集合 A，以 A 的所有子集為元構(gòu)成的一個(gè)集合，這個(gè)集合稱為A 的冪集，記為或1.2 集合的運(yùn)算定義 1.2.1（并集）：設(shè) A 和 B 是兩個(gè)集合，則包含 A 和 B 的所有

2、元，但不包含其他元的集合，稱為 A和 B 的并集，記為.定義 1.2.2 （交集 ）：A 和 B 是兩個(gè)集合， 包含 A 和 B 的所有公共元， 但不包含其他元的集合，稱為 A 和 B的交集，記為.定義 1.2.3（不相交 ）： A 和 B 是兩個(gè)集合，如果它們滿足，則稱集合 A 和 B 是不相交 的。定義 1.2.4（差集 ）：A 和 B 是兩個(gè)集合，屬于 A 而不屬于 B 的所有元構(gòu)成集合，稱為A 和 B的差集 ，記為.定義 1.2.5（補(bǔ)集）：若 A 是空間 E 的集合，則 E 中所有不屬于A 的元構(gòu)成的集合稱為A 的補(bǔ)集 ，記為.定義（對(duì)稱差 ）： A 和 B 是兩個(gè)集合，則定義A 和

3、 B 的對(duì)稱差為1.3包含排斥原理定理設(shè)為有限集，其元素個(gè)數(shù)分別為，則定理設(shè)為有限集，其元素個(gè)數(shù)分別為，則定理設(shè)為有限集，則重要例題P11 例.第 2 章二元關(guān)系2.1關(guān)系定義 2.1.1（序偶）：若 和 是兩個(gè)元，將它們按前后順序排列，記為，則成為一個(gè) 序偶 。 對(duì)于序偶和，當(dāng)且僅當(dāng)并且時(shí)，才稱和相等，記為定義 2.1.2（有序 元組）：若是個(gè)元，將它們按前后順序排列，記為，則成為一個(gè) 有序 元組（簡稱 元組）。定義 2.1.3（直接積 ）：和是兩個(gè)集合， 則所有序偶的集合，稱為和的 直接積（或笛卡爾積） ，記為.定義 2.1.4（直接積 ）：設(shè)是 個(gè)集合，則所有元組的集合，稱為的笛卡爾積

4、（或直接積），記為.定義 2.1.5（二元關(guān)系 ）若 和 是兩個(gè)集合，則的任何子集都定義了一個(gè)二元關(guān)系，稱為上的二元關(guān)系。如果，則稱為上的 二元關(guān)系 。定義 2.1.5（恒等關(guān)系 ）：設(shè) 是 上的二元關(guān)系，則稱是 上的恒等關(guān)系。定義 2.1.7（定義域、值域 ）：若 是一個(gè)二元關(guān)系，則稱為 的定義域。為 的值域。定義 2.1.8（自反）：設(shè)是集合上的關(guān)系，若對(duì)于 任何，都有即則稱關(guān)系是自反的。定義 2.1.9（反自反 ）：設(shè)是集合上的關(guān)系， 若對(duì)于任何，都滿足, 即對(duì)任何都不成立，則稱關(guān)系是反自反的。定義 2.1.10 （對(duì)稱 ）：設(shè)是集合上的關(guān)系，若對(duì)于任何，只要, 就有, 那么稱關(guān)系是對(duì)稱

5、的。定義 2.1.11 （反對(duì)稱 ）：設(shè)是集合上的關(guān)系，若對(duì)于任何，只要并且時(shí) ,就有，那么稱關(guān)系是對(duì)稱的。定義2.1.11 （傳遞 ） 設(shè)是集合上的關(guān)系，若對(duì)于任何，只要并且時(shí)，就有，則稱關(guān)系是傳遞的。定理 2.1.1設(shè) 是集合上的關(guān)系，若 是反自反的和傳遞的，則是反對(duì)稱的。2.2關(guān)系矩陣和關(guān)系圖定義無定理無2.3關(guān)系的運(yùn)算定義 2.3.1（連接 ）：設(shè)為上的關(guān)系，為上的關(guān)系，則定義關(guān)系.稱為關(guān)系和 的連接 或復(fù)合，有時(shí)也記為.定義（逆關(guān)系 ）：設(shè)為上的關(guān)系，則定義的逆關(guān)系為為上的關(guān)系：.定理 2.3.1設(shè)和都是上的二元關(guān)系，則下列各式成立（1）（ 2）（3）（4）（ 5）定理設(shè)為上的關(guān)系，

6、為上的關(guān)系，則2.4 閉包運(yùn)算定義 2.4.1（自反閉包 ）： 設(shè) 是集合上的二元關(guān)系，如果是包含的最小自反關(guān)系，則稱 是關(guān)系的自反閉包，記為.定義 2.4.2 （對(duì)稱閉包 ）： 設(shè)是集合上的二元關(guān)系，如果是包含的最小對(duì)稱關(guān)系，則稱 是關(guān)系的對(duì)稱閉包，記為.定義 2.4.3 （傳遞閉包 ）： 設(shè)是集合上的二元關(guān)系，如果是包含的最小傳遞關(guān)系，則稱 是關(guān)系的傳遞閉包，記為或.定理 2.4.1設(shè) 是集合 上的二元關(guān)系，則（1）是自反的，當(dāng)且僅當(dāng).（2）是對(duì)稱的，當(dāng)且僅當(dāng).（3）是傳遞的，當(dāng)且僅當(dāng).定理 2.4.2設(shè) 是集合上的二元關(guān)系，則.“恒等關(guān)系 ”定理 2.4.3設(shè) 是集合上的二元關(guān)系，則.“

7、逆關(guān)系 ”定理 2.4.4設(shè) 是集合上的二元關(guān)系，則.“冪集”定理 2.4.5設(shè) 是一個(gè)元集， 是 上的二元關(guān)系，則存在一個(gè)正整數(shù)，使得.2.5等價(jià)關(guān)系和相容關(guān)系定義（ 覆蓋、劃分）：是一個(gè)集合，, 如果，則稱.是 的一個(gè)覆蓋。如果，并且，則稱 是的一個(gè)劃分，中的元稱為的劃分塊。定義 2.5.2（等價(jià)關(guān)系 ）：設(shè) 是 上的一個(gè)關(guān)系，如果具有自反性、對(duì)稱性和傳遞性三個(gè)性質(zhì)，則稱是一個(gè)等價(jià)關(guān)系。設(shè)是等價(jià)關(guān)系，若成立，則稱等價(jià)于 .定義 2.5.3 （等價(jià)類 ）：設(shè) 是 上的一個(gè)等價(jià)關(guān)系， 則對(duì)任何，令，稱為 關(guān)于的等價(jià)類，簡稱為的等價(jià)類，也可以簡記為.定義 2.5.4（同余 ）：對(duì)于整數(shù)和正整數(shù),

8、 有關(guān)系式：如果，則稱對(duì)于模同余的，記作定義 2.5.5（商集）：設(shè) 是 上的一個(gè)等價(jià)關(guān)系，由引出的等價(jià)類組成的集合稱為集合 上由關(guān)系 產(chǎn)生的商集，記為.“等價(jià)類的集合 ”定理 2.5.1若是上的一個(gè)等價(jià)關(guān)系，則由可以產(chǎn)生唯一的一個(gè)對(duì)的劃分。 “商集 ”定義 2.5.6（相容關(guān)系 ）：設(shè) 是 上的一個(gè)關(guān)系，如果是自反的和對(duì)稱的，則稱是一個(gè)相容關(guān)系。相容關(guān)系可以記為.所有的等價(jià)關(guān)系都是相容關(guān)系，但相容關(guān)系卻不一定是等價(jià)關(guān)系。定義 2.5.7（最大相容塊 ）：設(shè)是一個(gè)集合，是定義在上的相容關(guān)系。如果,中的任何兩個(gè)元都有關(guān)系，而的每一個(gè)元都不能和中所有元具有關(guān)系，則稱是的一個(gè)最大相容塊。2.6偏序關(guān)

9、系定義 2.6.1（偏序關(guān)系 ）： 是定義在集合上的一個(gè)關(guān)系，如果它具有自反性、反對(duì)稱性和傳遞性，則稱是 上的一個(gè)偏序關(guān)系，簡稱為一個(gè)偏序，記為. 更一般地講，若是一個(gè)集合，在 上定義了一個(gè)偏序，則我們用符號(hào)來表示它， 并稱是一個(gè)偏序集。定義 2.6.2（全序 / 鏈）：是一個(gè)偏序集，對(duì)任何，如果或這兩者中至少有一個(gè)必須成立，則稱是一個(gè)全序集或鏈，而稱是 上的一個(gè)全序或線性序。定義 2.6.3（蓋住 ）：是一個(gè)偏序集，若，并且不存在, 使并且，則稱蓋住 . “緊挨著 ”定義 2.6.4（最小元、最大元 ）：是一個(gè)偏序集，如果中存在有元，對(duì)任何都滿足，則稱 是的最小元。如果中存在有元，對(duì)任何都滿

10、足，則稱是的最大元。定義 2.6.5 （極小元、極大元 ）：是一個(gè)偏序集， 如果, 而 中不存在元，使,則稱 是的極小元。如果, 而 中不存在元, 使,則稱是的極大元。定義 2.6.6（上界、下界、上確界、下確界）：是一個(gè)偏序集，, 如果對(duì)于所有的, 都有,則稱 是 的一個(gè) 上界。如果對(duì)于所有的, 都有,則稱 是的一個(gè) 下界 。如果是 的一個(gè)上界，對(duì)于的任一上界, 都有,則稱 是 的最小上界（上確界） .如果 是 的一個(gè)上界，對(duì)于的任一上界,都有,則稱 是 的最大下界（下確界） .定義 2.6.5（良序集 ）：設(shè)是一個(gè)偏序集，對(duì)于偏序，如果的每個(gè)非空子集都具有最小元，則稱是一個(gè)良序集，而稱是

11、上的一個(gè)良序。.每個(gè)良序集都是全序集。第 3 章 函數(shù)和運(yùn)算3.1函數(shù)定義（映射、象）：關(guān)系定義在上，如果對(duì)于 每一個(gè)，都有唯一的一個(gè)，使，則稱是從到 的一個(gè)函數(shù)（或映射） ，記為.稱為函數(shù)的變?cè)?，稱為變?cè)谙碌闹担ɑ蛳螅?，記為.注意：（1）定義域，而不是.（2）每一個(gè)，有唯一的，使.多值函數(shù)不符合定義（3）值域.定義 3.1.2（受限、擴(kuò)展）： 若 是從到 的一個(gè)函數(shù)，則也是一個(gè)函數(shù)，它定義于到 ，我們稱它是在 上的受限。如果 是函數(shù)的一個(gè)受限，則稱是 的一個(gè)擴(kuò)展。定義 3.1.3 （映上、映、一對(duì)一、一一對(duì)應(yīng)）： 若，則 的值域時(shí)，稱函數(shù) 是映上的（或滿射）。如果 的值域時(shí)，則稱函數(shù)是映

12、的。如果，則有, 則稱 是一對(duì)一的 （單射）（即時(shí)，有） .如果 映上的，又是一對(duì)一的，則稱是一一對(duì)應(yīng)的 （或雙射）。定義 3.1.4（復(fù)合運(yùn)算 ）：若，則定義 和 的復(fù)合運(yùn)算為：即.注：逆函數(shù)若要存在需要滿足以下條件：（1）函數(shù)是映上的（ 2）函數(shù) 必須是一對(duì)一的定義 3.1.5（恒等函數(shù) ） 函數(shù)稱為恒等函數(shù)。定理 3.1.1，則的充分必要條件是，并且3.2 運(yùn)算定義 3.2.1（二目運(yùn)算 ）： 若 是一個(gè)集合，是從到 的一個(gè)映射（函數(shù)） ，則稱 為一個(gè)二目運(yùn)算。一般地，若是從到 的一個(gè)映射（是正整數(shù)），則稱 是一個(gè) 目運(yùn)算。運(yùn)算的封閉：運(yùn)算的結(jié)果總是集合中的一個(gè)元，因此這個(gè)定義保證了運(yùn)算

13、的施行，這種情況又稱為集合對(duì)于該種運(yùn)算是封閉的。定義 3.2.2（可交換 ）：若是一個(gè)運(yùn)算，對(duì)于任何，都有，則稱運(yùn)算是可交換的（或者說，服從交換律） .定義 3.2.3 （可結(jié)合）：若是一個(gè)運(yùn)算，對(duì)于任何, 都 有，則稱運(yùn)算是可結(jié)合的（或者說，服從結(jié)合律） .定義 3.2.4（可分配 ）：若是一個(gè)運(yùn)算，是一個(gè)運(yùn)算，對(duì)于任何，都有，則稱運(yùn)算對(duì)于運(yùn)算是可分配的 （或者說，對(duì)于 服從分配律）.定義 3.2.5（左單位元、右單位元）：設(shè)是 上的一個(gè)運(yùn)算，如果中存在有一個(gè)元，對(duì)于任何，有，則稱是運(yùn)算的左單位元；如果中存在有一個(gè)元，對(duì)于任何，有，則稱是運(yùn)算的右單位元。定理 3.2.1若 是上的一個(gè)運(yùn)算，和

14、分別是它的左、 右單位元， 則，并且 是唯一的（因此，稱為運(yùn)算的單位元） .定義 3.2.6 （左零元、右零元）：設(shè)是 上的一個(gè)運(yùn)算，如果中存在有一個(gè)元，對(duì)于任何，有，則稱是運(yùn)算的左零元；如果 中存在有一個(gè)元，對(duì)于任何，有，則稱是運(yùn)算的右零元 .定義 3.2.7（等冪 ）：若 是 上的一個(gè)運(yùn)算，對(duì)于運(yùn)算，有，則稱元對(duì)于運(yùn)算是等冪的。定義 3.2.8 （左逆元、右逆元 ）：若是 上的一個(gè)運(yùn)算， 它具有單位元，對(duì)于任何一個(gè),如果存在有元，使，則稱是 的左逆元；如果存在有元，使，則稱是 的右逆元；定理 3.2.3若 是 上的一個(gè)運(yùn)算，它具有單位元，并且是 可結(jié)合 的，則當(dāng)元可逆時(shí)，它的左、右逆元相等

15、，并且唯一的（此時(shí)稱之為的逆元，并且記為） .定義 3.2.9（可消去 ）：若 是 上的一個(gè)運(yùn)算，對(duì)于任何，如果元 滿足：則；或則，則稱元 對(duì)于運(yùn)算是可消去的。第 4章無限集合4.1 基數(shù)定義 4.1.1 （等勢(shì) ）： 若 和是兩個(gè)集合，如果在和 之間可以建立 一個(gè)一一 對(duì)應(yīng)關(guān)系，則稱集合和 等勢(shì)，并記為。定理 4.1.1令是由若干個(gè)集合為元所組成的集合，則上定義的等勢(shì)關(guān)系是一個(gè)等價(jià)關(guān)系。定義 4.1.2（有限集、無限集 ）：若 是一個(gè)集合，它和某個(gè)自然數(shù)集等勢(shì)，則稱 是一有限集，不是有限集的集合稱為無限集。定理 4.1.2有限集的任何子集都是有限集定理 4.1.3有限集不與其任何真子集等勢(shì)定

16、理 4.1.4自然數(shù)集是無限集4.2可列集定義（可列集 ）：若是一個(gè)集合，它和所有自然數(shù)的集合等勢(shì)，則稱是一個(gè)可列.集?？闪屑幕鶖?shù)用符號(hào)表示。定理 4.2.1若 是一個(gè)集合，可列的充分必要條件是可以將它的元排列為的序列形式。定理 4.2.2任何無限集必包含有可列子集。定理 4.2.3可列集的子集是有限集或可列集（記為：）定理 4.2.4若 是可列集， 是有限集，并且，則是可列集（記為：）.定理 4.2.5若 和 都是可列集，并且，則是可列集（記為：）推論 4.2.1設(shè)都是可列集，則是可列集（記為：）定理 4.2.6設(shè)都是可列集，并且，則是可列集（記為：）推論 4.2.1設(shè)都是可列集，則是可列

17、集 .定理 4.2.7所有有理數(shù)的集合是可列集。4.3 不可列集定理 4.3.1區(qū)間中所有實(shí)數(shù)構(gòu)成的集合是不可列的。定義 4.3.1（連續(xù)基數(shù) ）： 開區(qū)間中所有數(shù)組成集合的基數(shù)記為，具有基數(shù)的集合稱為連續(xù)統(tǒng)，稱為連續(xù)基數(shù)。推論：集合的基數(shù)也是 .定理 4.3.2所有實(shí)數(shù)的集合是不可列的，它的基數(shù)是.定理 4.3.3對(duì)于任何數(shù)，若，則區(qū)間,以及都具有連續(xù)基數(shù)定理 4.3.4一個(gè)無限集和一個(gè)可列集作并集時(shí)，并集的基數(shù)等于集的基數(shù)。推論 4.3.2一個(gè)無限集和一個(gè)有限集的并集，其基數(shù)等于集的基數(shù)。4.4 基數(shù)的比較定義 4.4.1（） 設(shè)集合的基數(shù)是. 如果 與 的真子集等勢(shì)，而和 不等勢(shì)，則稱

18、的基數(shù)小于的基數(shù)，記為.定理 4.4.1：是兩個(gè)集合，若與 的某一子集等勢(shì)，與 的某一子集等勢(shì)，則.定理 4.4.2 ：是任意兩個(gè)集合，的基數(shù)為,的基數(shù)為，則下列三個(gè)關(guān)系：中必有一個(gè)且只有個(gè)成立。定理 4.4.3：若 是有限集的基數(shù)，則.定理 4.4.4：若是無限集合，則定理：若是可列個(gè)互不相交的集合，它們的基數(shù)都是，則的基.數(shù)是（記為：）定理 4.4.6：可列集的冪集，其基數(shù)是（記為：）定理 4.4.7：若 是一個(gè)集合，是 的冪集，則.此定理說明：不存在最大的基數(shù)。補(bǔ)充：第 5章形式語言5.1 文法和語言定義 5.1.1 （產(chǎn)生式 ）： 一個(gè)產(chǎn)生式或重寫規(guī)則是一個(gè)有序?qū)?，通常寫? 其中，是

19、一個(gè)符號(hào)，而是一個(gè)符號(hào)的非空有限串，是這個(gè)產(chǎn)生式的左部，而是產(chǎn)生式的右部 .產(chǎn)生式將簡稱為規(guī)則。定義 5.1.2（非終極符號(hào)、 字母表、終極符號(hào)、開始符號(hào) ）：一個(gè)文法是一個(gè)四元組.其中，是元語言的語法類或變?cè)募?，它生成語言的串，這些語法類或變?cè)蔀榉墙K極符號(hào) ，是符號(hào)的非空有窮集合，稱為字母表，的符號(hào)稱為 終極符號(hào) .是之一，是詞匯表的一個(gè)識(shí)別元素，稱為開始符號(hào) .是產(chǎn)生式的集合。定義 5.1.3（直接產(chǎn)生、直接推導(dǎo)，直接規(guī)約）：設(shè) 是一個(gè)文法，如果，而 中有規(guī)則，就稱串直接產(chǎn)生串，或稱 是 直接推導(dǎo)出來的，或直接規(guī)約到 ,記為.定義 5.1.4 （產(chǎn)生、規(guī)約到、推導(dǎo)）：設(shè) 是一個(gè)文法，

20、 如果存在產(chǎn)生式序列,使得，而, 就說產(chǎn)生 （ 規(guī)約到, 或 是 的推導(dǎo)），記為.定義 5.1.5（句型 ）：令 是一個(gè)文法，如果串可從開始符號(hào) 推導(dǎo)出來，即如果，則稱為一個(gè)句型。補(bǔ) 充 ：若， 則,其 中是空串，（不含空串）5.2 文法的類型定義 5.2.1（ 0- 型文法 ）：在 上的 0- 型文法由以下組成：（1）不在 中的不同符號(hào)的非空集合, 稱為變量表，它包含一個(gè)綱符號(hào),稱為開始變量。（2）產(chǎn)生式的有限集合。由 產(chǎn)生的所有字集稱為由產(chǎn)生的語言。定義 5.2.2（ 0- 型語言 ）：在上可由某一0- 型文法產(chǎn)生的字集稱為0- 型語言。.定義 5.2.3（ 1- 型文法 ）：如果在0-

21、型文法中，對(duì)于中的每個(gè)產(chǎn)生式，要求,則這文法稱為 1- 型文法或上下文敏感文法 .定義 5.2.4（ 2- 型文法 ）：設(shè)文法, 對(duì)于 中的每一個(gè)產(chǎn)生式有且（有的人要求），則此文法叫2- 型文法或前后文無關(guān)文法。定義（ 3- 型文法 ）：設(shè)為一文法， 又設(shè)中的每一個(gè)產(chǎn)生式都是或，其中和都是變量，而為終極符號(hào)，而此文法為3- 型文法或正規(guī)文法。第 1章代數(shù)系統(tǒng)1.1代數(shù)系統(tǒng)的實(shí)例和一般性質(zhì)定義（代數(shù)系統(tǒng) ）： 若是序偶，是一個(gè)非空集合，是定義在上的某些運(yùn)算的非空集合，則稱是一個(gè)代數(shù)系統(tǒng)，或稱代數(shù)。代數(shù)系統(tǒng)的類型：（1）代數(shù)系統(tǒng)的類型是，其中代表目運(yùn)算符。（2），分別為目運(yùn)算符，則的類型為.1.2

22、 同態(tài)和同構(gòu)定義 1.2.1（同態(tài)象、同態(tài)映射 ）:和是兩個(gè)同類型的代數(shù)系統(tǒng)，映射和 也構(gòu)成一一對(duì)應(yīng). 如果對(duì)于任意 目運(yùn)算，及其對(duì)應(yīng)的運(yùn)算， 當(dāng)時(shí)，都有, 則稱代數(shù)是的同態(tài)象，稱是從到的一個(gè)同態(tài)映射。定義 1.2.2（同態(tài)象、同態(tài)映射 ）：若和是兩個(gè)同類型的代數(shù)系統(tǒng)，和都是二目運(yùn)算，映射. 如果對(duì)于任何, 都有，則稱是的一個(gè)同態(tài)象，稱是從到的一個(gè)同態(tài)映射。注：如果就是，則映射是從 到它自身。當(dāng)上述條件仍然滿足時(shí)，我們就稱是的一個(gè)自同態(tài)映射。定義 1.2.3（同構(gòu)、同構(gòu)映射、自同構(gòu)映射）：如果和是同態(tài)的，映射不僅是同態(tài)映射，而且是一一對(duì)應(yīng) 的，則稱和同構(gòu)，稱是從到的一個(gè)同構(gòu)映射。如果就是，則稱

23、 是上的一個(gè)自同構(gòu)映射定義 1.2.4（同余關(guān)系 ）：設(shè)是一個(gè)代數(shù)系統(tǒng)，是 上的一個(gè)等價(jià)關(guān)系，如果存在,當(dāng)時(shí)，成立 ，則稱是上的一個(gè)同余關(guān)系。.定理：設(shè)是上的一個(gè)等價(jià)關(guān)系，如果存在同態(tài)映射, 使得當(dāng)時(shí)，當(dāng)且僅當(dāng)，則是上的同余關(guān)系。1.3商代數(shù)與積代數(shù)定義（子代數(shù) ）：設(shè)是一個(gè)代數(shù)系統(tǒng)，在運(yùn)算下封閉的，則稱是的一個(gè)子代數(shù)。定義（直接積 ）：設(shè)到是兩個(gè)同類型的代數(shù)系統(tǒng)，如果對(duì)任意的和，定義運(yùn)算于，稱是和的直接積，稱和為的因子。第 2章半群和群2.1半群和有幺半群定義（半群、有幺半群）： 是一個(gè)非空集合，如果中定義了一個(gè)二目運(yùn)算，對(duì)于任何, 都有，則稱是一個(gè)半群 . 如果半群中具有單位元 ，使得對(duì)任

24、何, 都有, 則稱是一個(gè)有幺半群。（1） 是一個(gè)由有限個(gè)符號(hào)組成的集合，其中的元稱為字母。表示所有的字構(gòu)成的集合，表示非空串組成的集合。（2）自由半群：半群的各元相互間沒有任何關(guān)系。說明：半群是一個(gè)定義了二目運(yùn)算，并且服從結(jié)合律的代數(shù)系統(tǒng)。有幺半群則是具有單位元的半群。2.2群和循環(huán)群定義 2.2.1 （群）：在代數(shù)系統(tǒng)中，如果二目運(yùn)算滿足（1）對(duì)于任何, 有；（2） 中存在單位元，對(duì)任何, 有；（3）對(duì)于任何，存在有逆元, 使則稱是一個(gè)群。注：對(duì)于群來說，單位元是唯一的，每個(gè)元的逆元也是唯一的。“存在逆元的有幺半群叫做群”定義（階數(shù) ）：若是一個(gè)群，當(dāng)是有限集時(shí)，則稱中元的個(gè)數(shù)為群的階數(shù)，記

25、為.定理若是一個(gè)群，則，其中即.定義（冪）：是一個(gè)群，則記個(gè) 的積為,稱為冪，.記為表示單位元。定理 2.2.2（指數(shù)律）：若和 是整數(shù)，則.定理 2.2.3若則定義 2.2.4（次數(shù) ）：若是一個(gè)群，, 使的最小正整數(shù) ，稱為元的次數(shù)。定理 2.2.4若是一個(gè)群， 的次數(shù)為，則都是 中不同的元。定義 2.2.5（循環(huán)群、生成元 ）：由一個(gè)單獨(dú)元素的一切冪所組成的群稱為循環(huán)群，稱為這個(gè)群的生成元。定理 2.2.5在階數(shù)為的循環(huán)群，由生成元所產(chǎn)生的元次數(shù)為 ，即 是生成元的充分必要條件是 和 互質(zhì)。定理 2.2.6若 和 不是互質(zhì)的，則的次數(shù)是，其中的 是 和 的最小公倍數(shù)。定義 2.2.6（阿

26、貝爾群 ）： 如果群中的元對(duì)于運(yùn)算滿足交換律，則稱這個(gè)群是一個(gè)阿貝爾群?！皾M足交換律的群叫做阿貝爾群”循環(huán)群是一個(gè)阿貝爾群。定理 2.2.7若和都是有限的阿貝爾群，定義則是一個(gè)阿貝爾群。最簡單的一個(gè)阿貝爾群是群,為按位加2.3二面體群、置換群二面體群是從圖形的變換中到處，這些圖形都是比較正規(guī)的圖形。定理 2.3.1更一般地講，定義 2.3.1（置換 ）：若 是一個(gè)非空的有限集合，則上任何一個(gè)到它自身的一一對(duì)應(yīng)的映射，都稱為上的置換。定理 2.3.2兩個(gè)置換的乘積仍是一個(gè)置換，并且置換的乘積服從結(jié)合律。的恒等映射也是一個(gè)置換稱為單位置換。上所有置換的集合，對(duì)于置換乘法構(gòu)成一個(gè)群，這個(gè)群稱為對(duì)稱群

27、，記為, 是 中元的個(gè)數(shù)。定義 2.3.2（ 階置換群 ）若 是非空有限集合，是 上的 個(gè)置換所構(gòu)成的群，則稱是一個(gè) 階置換群。定理 2.3.3任何一個(gè)（階）群都同構(gòu)于一個(gè)（階）置換群。2.4子群、群的同態(tài).定義 2.4.1（子群）：是一個(gè)群，, 如果（1）單位元（2）若，則 的逆元（3）若, 則則稱是的一個(gè)子群。定理 2.4.1是一個(gè)群，是一個(gè)子群的充分必要條件是：若, 則定義 2.4.2（ 同態(tài)象、群同態(tài)映射）：和是群，. 若對(duì)任何, 有群的同態(tài)映射具有下列性質(zhì) ：（ 1）將單位元映射為單位元（ 2）將逆元映射為逆元（3）對(duì)運(yùn)算封閉，即對(duì)任何，有定理 2.4.2若和是群，是一個(gè)群同態(tài)映射，

28、則將的子群映射為的子群。定義 2.4.3（同態(tài)核 ）：若是一個(gè)群同態(tài)映射，是的單位元，則中所有滿足的元 的集合，稱為同態(tài)核，記為.定理 2.4.3同態(tài)核是一個(gè)子群。定理 2.4.3若是群的子群，則定義了 上的一個(gè)劃分（因而也定義了上一個(gè)等價(jià)關(guān)系） .群子集 ：假定都是群中的元構(gòu)成的集合（稱之為群子集），定義特別地，當(dāng)是一元集時(shí)，我們簡記為, 則定理 2.4.5若是群的子群都是群的子群，則是一個(gè)群的充分必要條件是.2.5陪集、正規(guī)子群、商群定義 2.5.1（左陪集 ）：若是群的子群，對(duì)于, 稱稱為 的一個(gè)左陪集 .定理 2.5.1若是群的子群，則的所有左陪集構(gòu)成的一個(gè)劃分。定理 2.5.2（拉格

29、朗日定理）每個(gè)左陪集的元和中的元都是一樣多。推論 2.5.1子群中元的個(gè)數(shù)一定是群中元的個(gè)數(shù)的因子。定義 2.5.2（正規(guī)子群 ）：若是群的子群，對(duì)于任何, 都滿足, 則稱是群的一個(gè)正規(guī)子群 .一個(gè)阿貝爾群的任何子群都是正規(guī)子群。當(dāng)是群的正規(guī)子群時(shí)，對(duì)于關(guān)于 的陪集 . 定義運(yùn)算為考慮所有關(guān)于的陪集組成的集合和運(yùn)算構(gòu)成的系統(tǒng)為一個(gè)群。這個(gè)群稱為關(guān)于的商群，記為.定理 2.5.3若是從群到群的映上的同態(tài)映射，則核是正規(guī)子群，商群同構(gòu)于 .群同態(tài)基本定理： 商群是由陪集構(gòu)成的群， 也是同余類的集構(gòu)成的群，所以它.同構(gòu)于象代數(shù)，即同構(gòu)于.如果群沒有真正的正規(guī)子群，則該群為單群。正規(guī)群的任何子群都是正

30、規(guī)子群。第 3 章 格和布爾代數(shù)3.1 格定義 3.1.1 （格）：表示一個(gè)偏序集，如果對(duì)于中的任何兩個(gè)元和 , 在 中都存在一個(gè)元是它們的上確界，存在一個(gè)元是它們的下確界，則稱是一個(gè)格。對(duì)于 中的元，它們的上確界常常記為，它們的下確界常常記為, 前者又稱為 和析取或和（或），后者又稱為和 的合取或積（或或 ）。定理 3.1.1若是一個(gè)格，則對(duì)于任何，有（1）的充分必要條件是.（2）的充分必要條件是.定 理 3.1.2（保序性）若是一個(gè)格，則對(duì)于任何， 當(dāng)時(shí) ， 有引理 3.1.1若是一個(gè)格，則定理 3.1.3（分配不等式） ：若是一個(gè)格，則對(duì)于任何，定理 3.1.4（模數(shù)不等式）若是一個(gè)格，

31、則對(duì)于任何，的充分必要條件是定理 3.1.5若是一個(gè)代數(shù)系統(tǒng)，和 是 上的二目運(yùn)算， 它服從交換律、 結(jié)合律和吸收律 .則是一個(gè)格 .定義 3.1.2（子格 ）是一個(gè)格，當(dāng)且僅當(dāng)對(duì)于運(yùn)算和是封閉的，運(yùn)算結(jié)果和在中相同時(shí)，則稱代數(shù)系統(tǒng)是 的一個(gè)子格。定義 3.1.3（直接積） 若和是兩個(gè)格，則稱為這兩個(gè)格的直接積，其中的運(yùn)算和 定義為：對(duì)于任何的,定義（同態(tài)映射 ）設(shè)和是兩個(gè)格，. 如果對(duì)任何，有則稱是到的一個(gè)同態(tài)映射. 特別地，當(dāng)是一個(gè)一一對(duì)應(yīng)時(shí)，稱是一個(gè)同構(gòu)映射，并且稱格和同構(gòu)的。如果是格上一個(gè)同態(tài)映射，則稱是一個(gè)自同態(tài)映射. 如果是一個(gè)同構(gòu)映射，則稱是一個(gè)自同構(gòu)映射.定義（完備 ）： 對(duì)于

32、一個(gè)格，如果它的每一個(gè)非空子集在格中都具有一個(gè)上確界和下確界，則這個(gè)格稱為完備的。顯然每個(gè)有限的格都是完備的。對(duì)于一個(gè)格， 它的上確界和下確界如果存在，我們稱它們?yōu)檫@個(gè)格的邊界，并分別記為1 和 0，因此有時(shí)這種格稱為有界格 。定義（補(bǔ)元 ）：是一個(gè)有界格，如果存在元, 使且，則稱為 的補(bǔ)元。定義（補(bǔ)格）：中的每個(gè)元都至少具有一個(gè)補(bǔ)元，則稱這個(gè)格是一個(gè)補(bǔ)格。.定義（分配格 ）：是一個(gè)格，如果對(duì)任何，有則稱是一個(gè)分配格。定理 3.1.6任何兩個(gè)分配格的直接積是分配格。定 理 3.1.7若是一個(gè)分配格，則對(duì)于任何, 如 果， 并 且, 則推論如果一個(gè)格是分配格，同時(shí)又是補(bǔ)格，則它的每一個(gè)元都具有唯

33、一的一個(gè)補(bǔ)元。3.2 布爾代數(shù)定義 3.2.1（布爾代數(shù) ） 一個(gè)既是補(bǔ)格，又是分配格的格，稱為布爾代數(shù)。定義 3.2.2（對(duì)偶命題 ） 如果是一個(gè)布爾代數(shù)，是關(guān)于 中變?cè)囊粋€(gè)命題，它可以由中變?cè)ㄟ^運(yùn)算來表示 . 如果對(duì)的表示式進(jìn)行下列代換：代換為； 代換為； 代換 0；0代換為 1，則這樣代換后也將得到一個(gè)命題, 它成為命題 的對(duì)偶命題，簡稱為對(duì)偶。定理 3.2.1（對(duì)偶原理）如果是一個(gè)命題，它在任何一個(gè)布爾代數(shù)中都成立，并且可以由運(yùn)算來表示，則對(duì)它的對(duì)偶命題也在任何一個(gè)布爾代數(shù)中成立。定理 3.2.1*（對(duì)偶原理）如果是一個(gè)命題，它在任何一個(gè)布爾代數(shù)中都成立，并且可以由運(yùn)算和關(guān)系來表

34、示，則將中的運(yùn)算代換為；代換為；0 代換為 1，代換 0；換為，換為，所得到的對(duì)偶命題也在任何一個(gè)布爾代數(shù)中成立。定理 3.2.2若 和是兩個(gè)布爾代數(shù)，是一個(gè)同態(tài)映射，則在 中的同態(tài)象是的一個(gè)子布爾代數(shù)。定義（基元 ）：是一個(gè)布爾代數(shù)，, 如果中不存在元, 使, 則稱是的一個(gè)基元。如果對(duì)于任何都存在有基元, 則稱這個(gè)布爾代數(shù)是基元的。定理若是一個(gè)布爾代數(shù)，, 則下列命題是等價(jià)的。（1）是一個(gè)基元（2）對(duì)于所有的, 若, 則或（3）對(duì)于所有的，推論若和 是不同的基元，定理是一個(gè)基元的布爾代數(shù)，是其基元的集合，對(duì)任一令, 則, 并且作為基元的析取式，這個(gè)表達(dá)式是唯一的。.定理 3.2.5若是一個(gè)非

35、空有限的布爾代數(shù)，是它的所有基元構(gòu)成的集合，則同構(gòu).推論 3.2.2一個(gè)有限的布爾代數(shù)具有個(gè)元，其中的是它的基元的個(gè)數(shù)。推論 3.2.3對(duì)于任意正整數(shù), 具有個(gè)元的布爾代數(shù)是同構(gòu)的。3.3其他代數(shù)系統(tǒng)定義（ 環(huán)）若代數(shù)系統(tǒng)滿足下列條件：（ 1） 對(duì)于二目運(yùn)算是一個(gè)可交換的加法群。（ 2） 對(duì)于二目運(yùn)算（即乘法）是封閉的。（3）乘法結(jié)合律成立，即對(duì)中任何三個(gè)元和 , 有（4）分配律成立，即對(duì)中任何元和 ，有則稱是一個(gè)環(huán)。定義（交換環(huán) ） 一個(gè)環(huán)中的任何兩個(gè)元, 如果都滿足, 則稱是一個(gè)交換環(huán)。定義（逆元、零元）一個(gè)環(huán)中如果存在有元, 使得對(duì)中任何一個(gè)元都有, 則稱是的一個(gè)單位元。定義（逆元、零元

36、 ）在一個(gè)有單位元的環(huán)里，如果和是環(huán)中的元，滿足,則稱是的逆元。對(duì)任意, 若, 則稱0 是的零元。環(huán)的零元通常用表示。定義（域）：一個(gè)可交換的除環(huán)稱為一個(gè)域。定義（子環(huán) ）：一個(gè)環(huán)的一個(gè)子集本身對(duì)的代數(shù)運(yùn)算也構(gòu)成一個(gè)環(huán)，則稱為的子環(huán)。定義（理想子環(huán)，理想）：若 是環(huán)的一個(gè)非空子集，滿足（1）（2）則稱 是的一個(gè)理想子環(huán)，簡稱理想。第4章群碼4.1通信模型和錯(cuò)誤校正的基本概念4.2二進(jìn)制編碼定義 4.2.1（海明距離 ） 設(shè)與 之間的海明距離是的權(quán)，用表示。定理 4.2.1設(shè), 則（1）（2）.（3）當(dāng)且僅當(dāng)（ 4）定義 4.2.2 （碼字）：碼字是元組的碼的最小距離，是該碼中所有碼字之間的海明距離的最小值。定理 4.2.2當(dāng)且僅當(dāng)一個(gè)編碼的任意兩個(gè)碼字之間的最小距離至少時(shí)，能夠檢查出個(gè)或至少 個(gè)錯(cuò)誤的所有