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

1、離散數(shù)學課本知識點第1章集合1.1 集合的基本概念1. 集合、元（元素）、有限集、無限集、空集2. 表示集合的方法：列舉法、描述法3. 定義1.1.1（子集）：給定集合A和B，如果集合A的任何一個元都是集合B中的元，則稱集合A包含于B或B包含A，記為AB或BA，并稱A為B的一個子集。如果集合A和B滿足AB，但B中有元不屬于A，則稱集合A真包含于B，記為AB，并且稱A為B的一個真子集。4. 定義1.1.2（冪集）：給定集合A，以A的所有子集為元構成的一個集合，這個集合稱為A的冪集，記為 A 或 2A1.2 集合的運算定義1.2.1（并集）：設A和B是兩個集合，則包含A和B的所有元，但不包含其他元

2、的集合，稱為A和B的并集，記為AB.定義1.2.2（交集）：A和B是兩個集合，包含A和B的所有公共元，但不包含其他元的集合，稱為A和B的交集，記為AB.定義1.2.3（不相交）：A和B是兩個集合，如果它們滿足AB=，則稱集合A和B是不相交的。定義1.2.4（差集）：A和B是兩個集合，屬于A而不屬于B的所有元構成集合，稱為A和B的差集，記為A-B.定義1.2.5（補集）：若A是空間E的集合，則E中所有不屬于A的元構成的集合稱為A的補集，記為A'.定義1.2.6（對稱差）：A和B是兩個集合，則定義A和B的對稱差AB為AB=A-BB-A1.3 包含排斥原理定理1.3.1 設A1,A2為有限集

3、，其元素個數(shù)分別為A1，A2則 A1A1=A1+A2-A1A2定理1.3.2 設A1,A2,A3為有限集，其元素個數(shù)分別為A1,A2,A3，則A1A2A3=A1+A2+A3-A1A2-A1A3-A2A3+A1A2A3定理1.3.3 設A1,A2,An為有限集，則A1A2An=i=1nAi-1i<jnAiAj+1i<j<knAiAjAk+-1n-1A1A2An重要例題 P11 例1.3.1第2章 二元關系2.1 關系定義2.1.1（序偶）：若 x 和 y 是兩個元，將它們按前后順序排列，記為x,y，則y,x成為一個序偶。 對于序偶x,y和a,b，當且僅當x=a并且y=b時，才稱

4、x,y和a,b相等，記為x,y=a,b定義2.1.2（有序n元組）：若x1,x2,xn是個元，將它們按前后順序排列，記為x1,x2,xn，則成為一個有序n元組（簡稱n元組）。定義2.1.3（直接積）：A和B是兩個集合，則所有序偶x,y的集合，稱為和的直接積（或笛卡爾積），記為A×B.定義2.1.4（直接積）：設A1,A2,An是n個集合，xiAi,i=1,2,n ，則所有n元組x1,x2,xn的集合，稱為A1,A2,An的笛卡爾積（或直接積），記為A1×A2××An.定義2.1.5（二元關系） 若A和B是兩個集合，則A×B的任何子集都定義了一個

5、二元關系，稱為A×B上的二元關系。如果A=B，則稱為A上的二元關系。定義2.1.5（恒等關系）：設Ix是X上的二元關系，Ix=x,x|xX，則稱Ix是X上的恒等關系。定義2.1.7（定義域、值域）：若S是一個二元關系，則稱DS=x|存在y,使x,yS為S的定義域。RS=y|存在x,使x,yS為S的值域。定義2.1.8（自反）：設 R 是集合上 X 的關系，若對于任何 xX，都有 xRx 即x,xR則稱R關系是自反的。定義2.1.9（反自反）：設R 是集合上 X 的關系，若對于任何xX，都滿足x,xR,即xRx對任何xX都不成立，則稱關系R是反自反的。定義2.1.10（對稱）：設R 是

6、集合上 X 的關系，若對于任何x,yX，只要xRy,就有yRx,那么稱關系R是對稱的。定義2.1.11（反對稱）：設R 是集合上 X 的關系，若對于任何x,yX，只要xRy并且yRx時,就有x=y，那么稱關系R是對稱的。定義2.1.11（傳遞） 設R 是集合上 X 的關系，若對于任何x,yX，只要xRy并且yRz時，就有xRz，則稱關系R是傳遞的。定理2.1.1 設R 是集合上 X 的關系，若R是反自反的和傳遞的，則R是反對稱的。2.2 關系矩陣和關系圖定義 無 定理 無2.3 關系的運算定義2.3.1（連接）：設 R 為X×Y上的關系，S為Y×Z上的關系，則定義關系RS=

7、x,z|存在y,使x,yR且y,zSRS稱為關系R和S的連接或復合，有時也記為RS.定義2.3.2（逆關系）：設 R 為X×Y上的關系，則定義R的逆關系為R-1為Y×X上的關系：R-1=y,x|y,xR.定理2.3.1 設R和S都是X×Y上的二元關系，則下列各式成立（1）R-1-1=R（2）RS-1=R-1S-1（3）RS-1=R-1S-1（4）R'-1=R-1'（5）R-S-1=R-1-S-1定理2.3.2設R為X×Y上的關系，S為Y×Z上的關系，則RS-1=S-1R-12.4 閉包運算定義2.4.1（自反閉包）： 設R是集合

8、X上的二元關系，如果R1是包含R的最小自反關系，則稱R1是關系R的自反閉包，記為rR.定義2.4.2（對稱閉包）： 設R是集合X上的二元關系，如果R1是包含R的最小對稱關系，則稱R1是關系R的對稱閉包，記為sR.定義2.4.3（傳遞閉包）： 設R是集合X上的二元關系，如果R1是包含R的最小傳遞關系，則稱R1是關系R的傳遞閉包，記為tR或R+.定理2.4.1 設R是集合X上的二元關系，則（1） R是自反的，當且僅當rR=R.（2） R是對稱的，當且僅當rR=R.（3） R是傳遞的，當且僅當tR=R.定理2.4.2 設R是集合X上的二元關系，則rR=RIx. “R恒等關系”定理2.4.3 設R是集

9、合X上的二元關系，則sR=RR-1. “R逆關系”定理2.4.4 設R是集合X上的二元關系，則R+=RR2R3=i=1Ri.“R冪集”定理2.4.5 設X是一個n元集，R是X上的二元關系，則存在一個正整數(shù)kn，使得R+=RR2R3Rk.2.5 等價關系和相容關系定義2.5.1（覆蓋、劃分）： S是一個集合，AiS,i=1,2,n,如果i=1nAi=S，則稱a=A1,A2,An是S的一個覆蓋。如果i=1nAi=S，并且AiAji,j=1,2,n,ij，則稱a是S的一個劃分，a中的元稱為S的劃分塊。定義2.5.2（等價關系）：設R是X上的一個關系，如果R具有自反性、對稱性和傳遞性三個性質，則稱R是

10、一個等價關系。設R是等價關系，若xRy成立，則稱x等價于y.定義2.5.3（等價類）：設R是X上的一個等價關系，則對任何xX，令xR=y|yX且xRy，稱xR為x關于R的等價類，簡稱為x的等價類，xR也可以簡記為x.定義2.5.4（同余）：對于整數(shù)a,b和正整數(shù)m,有關系式：a=mk1+r10r1<mb=mk2+r20r2<m如果r1=r2，則稱a,b對于模m同余的，記作abmod m定義2.5.5（商集）：設R是X上的一個等價關系，由R引出的等價類組成的集合x|xX稱為集合X上由關系R產(chǎn)生的商集，記為X/R.“等價類的集合”定理2.5.1若是 X 上的一個等價關系，則由R可以產(chǎn)生

11、唯一的一個對 X 的劃分?！吧碳倍x2.5.6（相容關系）：設R是X上的一個關系，如果R是自反的和對稱的，則稱R是一個相容關系。相容關系可以記為.所有的等價關系都是相容關系，但相容關系卻不一定是等價關系。定義2.5.7（最大相容塊）：設X是一個集合，是定義在X上的相容關系。如果AX, A中的任何兩個元都有關系，而x-A的每一個元都不能和A中所有元具有關系，則稱A是X的一個最大相容塊。2.6 偏序關系定義2.6.1（偏序關系）：R是定義在集合X上的一個關系，如果它具有自反性、反對稱性和傳遞性，則稱R是X上的一個偏序關系，簡稱為一個偏序，記為.更一般地講，若X是一個集合，在X上定義了一個偏序，則

12、我們用符號 X, 來表示它，并稱X,是一個偏序集。定義2.6.2（全序/鏈）：X,是一個偏序集，對任何x,yX，如果xy或yx這兩者中至少有一個必須成立，則稱X,是一個全序集或鏈，而稱是X上的一個全序或線性序。定義2.6.3（蓋住）：X,是一個偏序集，x,yX，若xy，并且不存在zX,使xz并且zy，則稱y蓋住x.“緊挨著”定義2.6.4（最小元、最大元）：X,是一個偏序集，如果X中存在有元y，對任何xX都滿足yx，則稱y是X,的最小元。如果X中存在有元z，對任何xX都滿足xz，則稱z是X,的最大元。定義2.6.5（極小元、極大元）：X,是一個偏序集，如果yX,而X中不存在元x，使x<y

13、,則稱y是X,的極小元。如果zX,而X中不存在元x,使z<x,則稱z是X,的極大元。定義2.6.6（上界、下界、上確界、下確界）：X,是一個偏序集，AX,x,yX,如果對于所有的aA,都有ax,則稱x是A的一個上界。如果對于所有的aA,都有ya,則稱y是A的一個下界。如果x是A的一個上界，對于A的任一上界z,都有xz,則稱x是A的最小上界（上確界）. 如果y是A的一個上界，對于A的任一上界w,都有wy,則稱y是A的最大下界（下確界）.定義2.6.5（良序集）：設X,是一個偏序集，對于偏序，如果X的每個非空子集都具有最小元，則稱X,是一個良序集，而稱是X上的一個良序。每個良序集都是全序集。

14、第3章 函數(shù)和運算3.1 函數(shù)定義3.1.1（映射、象）： 關系f定義在X×Y上，如果對于每一個xX，都有唯一的一個yY，使x,yf，則稱f是從X到Y的一個函數(shù)（或映射），記為f:XY.x稱為函數(shù) f 的變元，y稱為變元x在f下的值（或象），記為fx.注意：（1） 定義域Df=X，而不是DfX.（2） 每一個x，有唯一的yY，使x,yf.多值函數(shù)不符合定義（3） 值域RfY.定義3.1.2（受限、擴展）： 若f是從X到Y的一個函數(shù)，AX，則fA×Y也是一個函數(shù)，它定義于A到Y，我們稱它是f在A上的受限。如果f是函數(shù)g的一個受限，則稱g是f的一個擴展。定義3.1.3（映上、映

15、內(nèi)、一對一、一一對應）： 若f:XY，則f的值域Rf=Y時，稱函數(shù)f是映上的（或滿射）。如果f的值域RfY時，則稱函數(shù)f是映內(nèi)的。如果x1,x2X,x1x2，則有fx1fx2,則稱f是一對一的（單射）（即fx1=fx2時，有x1=x2）.如果f映上的，又是一對一的，則稱f是一一對應的（或雙射）。定義3.1.4（復合運算）：若f:XY,g:YZ，則定義f和g的復合運算fg為：fg=x,z|存在yY,使y=fx,且z=gy即fgx=gfx.注：逆函數(shù)f-1若要存在需要滿足以下條件：（1）函數(shù)f是映上的（2）函數(shù)f必須是一對一的定義3.1.5（恒等函數(shù)） 函數(shù)Ix=x,x|xX稱為恒等函數(shù)。定理3.

16、1.1 f:XY,g:YZ，則g=f-1的充分必要條件是gf=Iy，并且fg=Ix3.2 運算定義3.2.1（二目運算）： 若X是一個集合，f是從X×X到X的一個映射（函數(shù)），則稱f為一個二目運算。一般地，若f是從Xn到X的一個映射（n是正整數(shù)），則稱f是一個n目運算。運算的封閉：運算的結果總是集合X中的一個元，因此這個定義保證了運算的施行，這種情況又稱為集合X對于該種運算是封閉的。定義3.2.2（可交換）：若f:X×XX是一個運算，對于任何x,yX，都有fx,y=fy,x，則稱運算f是可交換的（或者說，f服從交換律）.定義3.2.3（可結合）：若f:X×XX是一

17、個運算，對于任何x,y,zX,都有ffx,y,z=fx,fy,z，則稱運算f是可結合的（或者說，f服從結合律）.定義3.2.4（可分配）：若f:X×XX是一個運算，g:X×XX是一個運算，對于任何x,y,zX，都有fx,gy,z=gfx,y,fx,z，則稱運算f對于運算g是可分配的（或者說，f對于g服從分配律）定義3.2.5（左單位元、右單位元）：設*是X上的一個運算，如果X中存在有一個元el，對于任何xX，有el*x=x，則稱el是運算*的左單位元；如果X中存在有一個元er，對于任何xX，有x*er=x，則稱er是運算*的右單位元。定理3.2.1 若*是X上的一個運算，e

18、l和er分別是它的左、右單位元，則el=er=e，并且e是唯一的（因此，稱e為運算*的單位元）.定義3.2.6（左零元、右零元）：設*是X上的一個運算，如果X中存在有一個元Ol，對于任何xX，有Ol*x=Ol，則稱Ol是運算*的左零元；如果X中存在有一個元Or，對于任何xX，有x*Or=Or，則稱Or是運算*的右零元.定義3.2.7（等冪）：若*是X上的一個運算，aX，對于運算*，有a*a=a，則稱元a對于運算*是等冪的。定義3.2.8（左逆元、右逆元）：若*是X上的一個運算，它具有單位元e，對于任何一個aX,如果存在有元xlX，使xl*a=e，則稱xl是a的左逆元；如果存在有元xrX，使a*

19、xl=e，則稱xr是a的右逆元；定理3.2.3 若*是X上的一個運算，它具有單位元e，并且是可結合的，則當元a可逆時，它的左、右逆元相等，并且唯一的（此時稱之為a的逆元，并且記為a-1）.定義3.2.9（可消去）：若*是X上的一個運算，對于任何x,yX，如果元a滿足：a*x=a*y則x=y；或x*a=y*a則x=y，則稱元a對于運算*是可消去的。第4章 無限集合4.1 基數(shù)定義4.1.1（等勢）： 若 A 和 B 是兩個集合，如果在 A 和 B 之間可以建立一個一一對應關系，則稱集合A和B等勢，并記為AB。定理4.1.1 令 是由若干個集合為元所組成的集合，則上定義的等勢關系是一個等價關系。定

20、義4.1.2（有限集、無限集）：若 A是一個集合，它和某個自然數(shù)集Mn=0,1,2,n等勢，則稱A是一有限集，不是有限集的集合稱為無限集。定理4.1.2 有限集的任何子集都是有限集定理4.1.3 有限集不與其任何真子集等勢定理4.1.4 自然數(shù)集N=0,1,2,是無限集4.2 可列集定義4.2.1（可列集）：若A是一個集合，它和所有自然數(shù)的集合N等勢，則稱A是一個可列集?？闪屑幕鶖?shù)用符號0表示。定理4.2.1 若A是一個集合，A可列的充分必要條件是可以將它的元排列為a1,a2,an,的序列形式。定理4.2.2 任何無限集必包含有可列子集。定理4.2.3 可列集的子集是有限集或可列集（記為：0

21、-n0）定理4.2.4 若A是可列集，B是有限集，并且AB=，則AB是可列集（記為：0+n=0）.定理4.2.5若A和B都是可列集，并且AB=，則AB是可列集（記為：0+0=0）推論4.2.1 設Aii=1,2,n都是可列集，則i=1nAi是可列集（記為：n0=0）定理4.2.6 設Aii=1,2,n都是可列集，并且AiAj=ij,i,j=1,2,，則 i=1Ai是可列集（記為：00=0）推論4.2.1設Aii=1,2,n都是可列集，則i=1Ai是可列集.定理4.2.7 所有有理數(shù)的集合是可列集。4.3 不可列集定理4.3.1 區(qū)間0,1中所有實數(shù)構成的集合是不可列的。定義4.3.1（連續(xù)基數(shù)

22、）： 開區(qū)間0,1中所有數(shù)組成集合的基數(shù)記為，具有基數(shù)的集合稱為連續(xù)統(tǒng)，稱為連續(xù)基數(shù)。推論：集合0,1的基數(shù)也是.定理4.3.2 所有實數(shù)的集合是不可列的，它的基數(shù)是.定理4.3.3 對于任何數(shù)a,b，若a<b，則區(qū)間a,b,a,b,a,b,a,b)以及0,0,)都具有連續(xù)基數(shù)定理4.3.4 一個無限集A和一個可列集作并集時，并集的基數(shù)等于集A 的基數(shù)。推論4.3.2 一個無限集A和一個有限集的并集，其基數(shù)等于集 A 的基數(shù)。4.4 基數(shù)的比較定義4.4.1（<） 設集合A的基數(shù)是=.如果A與B的真子集等勢，而A和B不等勢，則稱A的基數(shù)小于B的基數(shù)，記為<.定理4.4.1：A

23、,B是兩個集合，若A與B的某一子集等勢，B與A的某一子集等勢，則AB.定理4.4.2：A,B是任意兩個集合，A的基數(shù)為, B的基數(shù)為，則下列三個關系：=,<,>中必有一個且只有個成立。定理4.4.3：若n是有限集A的基數(shù)，則n<0<.定理4.4.4：若A是無限集合，則0CardA定理4.4.5：若A1,A2,An,是可列個互不相交的集合，它們的基數(shù)都是，則n=1An的基數(shù)是（記為：0=）定理4.4.6：可列集的冪集，其基數(shù)是（記為：20=）定理4.4.7：若A是一個集合，B=A是A的冪集，則CardA<CardB.此定理說明：不存在最大的基數(shù)。補充：2>,

24、>第5章 形式語言5.1 文法和語言定義5.1.1（產(chǎn)生式）： 一個產(chǎn)生式或重寫規(guī)則是一個有序對U,x，通常寫成Ux,其中，U是一個符號，而x是一個符號的非空有限串，U是這個產(chǎn)生式的左部，而x是產(chǎn)生式的右部.產(chǎn)生式將簡稱為規(guī)則。定義5.1.2（非終極符號、字母表、終極符號、開始符號）：一個文法G是一個四元組VN,VT,P,S.其中，VN是元語言的語法類或變元的集合，它生成語言的串，這些語法類或變元成為非終極符號，VT是符號的非空有窮集合，稱為字母表，VT的符號稱為終極符號. S是VN之一，是詞匯表的一個識別元素，稱為開始符號. P是產(chǎn)生式的集合。定義5.1.3（直接產(chǎn)生、直接推導，直接規(guī)

25、約）：設G是一個文法，如果V=xUy,w=xuy，而G中有規(guī)則Uu，就稱串V直接產(chǎn)生串w，或稱w是V直接推導出來的，或w直接規(guī)約到V,記為Vw.定義5.1.4（產(chǎn)生、規(guī)約到、推導）：設G是一個文法，如果存在產(chǎn)生式序列P1,P2,Pnn>0,使得VP1P2Pn-1Pn，而Pn=w,就說V產(chǎn)生w（w規(guī)約到V,或w是V的推導），記為V+w.定義5.1.5（句型）：令G是一個文法，如果串x可從開始符號S推導出來，即如果S*x，則x稱為一個句型。補充： 若=a,b，則*=,a,b,aa,ab,ba,bb,aaa,其中是空串，+=a,b,aa,ab,ba,bb,aaa,（不含空串）5.2 文法的類型

26、定義5.2.1（0-型文法）：在上的0-型文法由以下組成：（1） 不在中的不同符號的非空集合V,稱為變量表，它包含一個綱符號S, S稱為開始變量。（2） 產(chǎn)生式的有限集合。由G產(chǎn)生的所有字集稱為由G產(chǎn)生的語言。定義5.2.2（0-型語言）：在上可由某一0-型文法產(chǎn)生的字集稱為0-型語言。定義5.2.3（1-型文法）：如果在0-型文法中，對于P中的每個產(chǎn)生式，要求,則這文法稱為1-型文法或上下文敏感文法.定義5.2.4（2-型文法）：設文法G=VN,VT,P,S,對于P中的每一個產(chǎn)生式有且VN（有的人要求），則此文法叫2-型文法或前后文無關文法。定義5.2.5（3-型文法）：設G=VN,VT,P

27、,S為一文法，又設P中的每一個產(chǎn)生式都是AaB或Aa，其中A和B都是變量，而a為終極符號，而此文法為3-型文法或正規(guī)文法。第1章 代數(shù)系統(tǒng)1.1 代數(shù)系統(tǒng)的實例和一般性質定義1.1.1（代數(shù)系統(tǒng)）： 若X,是序偶，X是一個非空集合，是定義在X上的某些運算的非空集合，則稱X,是一個代數(shù)系統(tǒng)，或稱代數(shù)。代數(shù)系統(tǒng)的類型：（1） 代數(shù)系統(tǒng)X,1,2,m的類型是n1,n2,nm，其中1,2,m代表1,2,m目運算符。（2） X,1,2,3，分別為0,1,2目運算符，則X,1,2,3的類型為0,1,2.1.2 同態(tài)和同構定義1.2.1（同態(tài)象、同態(tài)映射）: X,1和Y,2是兩個同類型的代數(shù)系統(tǒng)，映射g:X

28、Y, 1和2也構成一一對應.如果對于任意n目運算11，及其對應的運算22，當x1,x2,xnX時，都有g1x1,x2,xn=2gx1,gx2,gxn,則稱代數(shù)Y,2是X,1的同態(tài)象，稱g是從X,1到Y,2的一個同態(tài)映射。定義1.2.2（同態(tài)象、同態(tài)映射）：若X,和Y,*是兩個同類型的代數(shù)系統(tǒng)，和*都是二目運算，映射g:XY.如果對于任何x,yX,都有gxy=gx*gy，則稱Y,*是X,的一個同態(tài)象，稱g是從X,到Y,*的一個同態(tài)映射。注：如果Y,*就是X,，則映射g是從X到它自身。當上述條件仍然滿足時，我們就稱g是X,的一個自同態(tài)映射。定義1.2.3（同構、同構映射、自同構映射）：如果X,和Y

29、,*是同態(tài)的，映射g:XY不僅是同態(tài)映射，而且是一一對應的，則稱Y,*和X,同構，稱g是從X,到Y,*的一個同構映射。如果Y,*就是X,，則稱g是X,上的一個自同構映射定義1.2.4（同余關系）：設Z,是一個代數(shù)系統(tǒng)，是Z上的一個等價關系，如果存在x1,x2,x3,x4Z,當x1,x2,x3,x4時，x1x3,x2x4成立，則稱是Z,上的一個同余關系。定理1.2.1：設是Z上的一個等價關系，如果存在同態(tài)映射g:Z,Y,*,使得當x1,x2Z時，x1x2當且僅當gx1=gx2，則是Z,上的同余關系。1.3 商代數(shù)與積代數(shù)定義1.3.1（子代數(shù)）：設Z,是一個代數(shù)系統(tǒng)，Z1Z在運算下封閉的，則稱Z

30、1,是Z,的一個子代數(shù)。定義1.3.2（直接積）：設Z,到Y,*是兩個同類型的代數(shù)系統(tǒng)，如果對任意的x1,x2Z和y1,y2Y，定義運算于Z×Y:x1,y2x2,y2=x1x2,y1*y2，稱Z×Y,是Z,和Y,*的直接積，稱Z,和Y,*為Z×Y,的因子。第2章 半群和群2.1 半群和有幺半群定義2.1.1（半群、有幺半群）：S是一個非空集合，如果S中定義了一個二目運算 ，對于任何a,b,cS,都有abc=abc，則稱S , 是一個半群.如果半群S , 中具有單位元e，使得對任何xS,都有ex=xe=x,則稱S , 是一個有幺半群。（1）是一個由有限個符號組成的集

31、合，其中的元稱為字母。*表示所有的字構成的集合，+表示非空串組成的集合。（2）自由半群：半群的各元相互間沒有任何關系。* , 說明：半群是一個定義了二目運算，并且服從結合律的代數(shù)系統(tǒng)。有幺半群則是具有單位元的半群。2.2 群和循環(huán)群定義2.2.1（群）：在代數(shù)系統(tǒng)G , *中，如果二目運算*滿足（1）對于任何a,b,cG,有a*b*c=a*b*c；（2）G中存在單位元e，對任何aG,有a*e=e*a=a；（3）對于任何aG，存在有逆元a-1G,使a*a-1=a-1*a=e則稱G , *是一個群。注：對于群G , *來說，單位元e是唯一的，每個元a的逆元a-1也是唯一的?！按嬖谀嬖挠戌郯肴航凶?/p>

32、群”定義2.2.2（階數(shù)）：若G , *是一個群，當G是有限集時，則稱G中元的個數(shù)為群的階數(shù)，記為G.定理2.2.1 若G , *是一個群，x,yG，則xy-1=y-1x-1，其中xy即x*y.定義2.2.3（冪）：G , *是一個群，xG，則記r個x的積x*x*x為xr, xr稱為x冪，x-1r記為x-r, x0表示單位元e。定理2.2.2（指數(shù)律）：若m和n是整數(shù)，則xmxn=xm+n,xmn=xmn.定理2.2.3 若xy=yx,則 xmyn=ynxm定義2.2.4（次數(shù)）：若G,*是一個群，xG,使xn=e=x0的最小正整數(shù)n，稱為元x的次數(shù)。定理2.2.4若G,*是一個群，xG，x的

33、次數(shù)為n，則x0=e,x,x2,xn-1都是G中不同的元。定義2.2.5（循環(huán)群、生成元）：由一個單獨元素a的一切冪所組成的群稱為循環(huán)群，a稱為這個群的生成元。定理2.2.5 在階數(shù)為n的循環(huán)群，由生成元x所產(chǎn)生的元xr次數(shù)為n，即xr是生成元的充分必要條件是r和n互質。定理2.2.6 若r和n不是互質的，則xr的次數(shù)是l/r，其中的l是r和n的最小公倍數(shù)。定義2.2.6（阿貝爾群）： 如果群G,*中的元對于運算*滿足交換律，則稱這個群是一個阿貝爾群?！皾M足交換律的群叫做阿貝爾群”循環(huán)群是一個阿貝爾群。定理2.2.7 若A, 和B, *都是有限的阿貝爾群，定義A×B=a,b|aA,b

34、Ba1,b1+a2,b2=a1a2,b1*b1則A×B,+是一個阿貝爾群。最簡單的一個阿貝爾群是B2群0,1, 為按位加2.3 二面體群、置換群二面體群是從圖形的變換中到處，這些圖形都是比較正規(guī)的圖形。定理2.3.1 ab=ban-1.更一般地講，arb=ban-r定義2.3.1（置換）：若S是一個非空的有限集合，則S上任何一個到它自身的一一對應的映射，都稱為S上的置換。定理2.3.2 兩個置換的乘積仍是一個置換，并且置換的乘積服從結合律。S的恒等映射也是一個置換稱為單位置換。S上所有置換的集合，對于置換乘法構成一個群，這個群稱為對稱群，記為Sn, n是S中元的個數(shù)。定義2.3.2（

35、n階置換群）若S是非空有限集合，G是S上的n個置換所構成的群，則稱G是一個n階置換群。定理2.3.3 任何一個（n階）群都同構于一個（n階）置換群。2.4 子群、群的同態(tài)定義2.4.1（子群）： G,*是一個群，SG,如果（1）單位元eS（2）若aS，則a的逆元a-1S（3）若a,bS,則a*bS則稱S,*是G,*的一個子群。定理2.4.1 G,*是一個群，SG，S,*是一個子群的充分必要條件是：若a,bS,則a*b-1S定義2.4.2（同態(tài)象、群同態(tài)映射）：G,*和H,*是群，g:GH.若對任何a,bG,有ga*b=gagb群的同態(tài)映射具有下列性質：（1）將單位元映射為單位元（2）將逆元映射

36、為逆元（3）對運算封閉，即對任何a,bG，有gagb=ga*b定理2.4.2 若G,*和H,*是群，g:GH是一個群同態(tài)映射，則g將G,*的子群映射為H,的子群。定義2.4.3（同態(tài)核）：若g:GH是一個群同態(tài)映射，eH是H的單位元，則G中所有滿足ga=eH的元a的集合，稱為同態(tài)核，記為Kerg.定理2.4.3 同態(tài)核是一個子群。定理2.4.3 若H,*是群G,*的子群，則H定義了G上的一個劃分（因而也定義了G上一個等價關系）.群子集：假定A,B都是群G,*中的元構成的集合（稱之為群子集），定義AB=a*b|aA,bB特別地，當A是一元集a時，我們簡記AB為aB,則aB=a*b|bB定理2.4

37、.5若A,*是群B,*的子群都是群G,*的子群，則AB,*是一個群的充分必要條件是AB=BA.2.5 陪集、正規(guī)子群、商群定義2.5.1（左陪集）：若H,*是群G,*的子群，對于aG,稱aH=a*h|hH稱為H的一個左陪集.定理2.5.1若H,*是群G,*的子群，則H的所有左陪集構成G的一個劃分。定理2.5.2（拉格朗日定理）每個左陪集的元和H中的元都是一樣多。推論2.5.1 子群中元的個數(shù)一定是群中元的個數(shù)的因子。定義2.5.2（正規(guī)子群）：若H,*是群G,*的子群，對于任何aG,都滿足aH=Ha,則稱H,*是群G,*的一個正規(guī)子群.一個阿貝爾群的任何子群都是正規(guī)子群。當H,*是群G,*的正

38、規(guī)子群時，對于H關于G的陪集.定義運算 為aHbH=a*bH考慮所有H關于G的陪集組成的集合aH|aG和運算 構成的系統(tǒng)aH, 為一個群。這個群稱為G關于H的商群，記為G/H.定理2.5.3 若g:GH是從群G,*到群H,的映上的同態(tài)映射，則核N是正規(guī)子群，商群G/N同構于N.群同態(tài)基本定理：商群G/N是由陪集aN構成的群，也是同余類的集aN構成的群，所以它同構于象代數(shù)，即G/N同構于H.如果群沒有真正的正規(guī)子群，則該群為單群。正規(guī)群的任何子群都是正規(guī)子群。第3章 格和布爾代數(shù)3.1 格定義3.1.1（格）：L,表示一個偏序集，如果對于L中的任何兩個元a和b,在L中都存在一個元是它們的上確界，

39、存在一個元是它們的下確界，則稱L,是一個格。對于L中的元a,b，它們的上確界常常記為ab，它們的下確界常常記為a*b,前者又稱為a和b析取或和（ab或a+b），后者又稱為a和b的合取或積（ab或ab或ab）。定理3.1.1 若L,是一個格，則對于任何a,bL，有（1） ab的充分必要條件是a*b=a.（2） ab的充分必要條件是ab=b.定理3.1.2（保序性）若L,是一個格，則對于任何a,b,cL，當bc時，有a*ba*c,ab<ac引理3.1.1若L,是一個格， a,b,cL,ab,ac，則ab*c定理3.1.3（分配不等式）：若L,是一個格，則對于任何a,b,cL，ab*cab*a

40、ca*bca*ba*c定理3.1.4（模數(shù)不等式）若L,是一個格，則對于任何a,b,cL，ac的充分必要條件是ab*cab*c定理3.1.5 若S,*是一個代數(shù)系統(tǒng)，和*是S上的二目運算，它服從交換律、結合律和吸收律.則S,*是一個格.定義3.1.2（子格） L,*是一個格，SL，當且僅當S對于運算和*是封閉的，運算結果和在L中相同時，則稱代數(shù)系統(tǒng)S,*是L的一個子格。定義3.1.3（直接積） 若L,*和S, , 是兩個格，則L×S,+, 稱為這兩個格的直接積，其中的運算+和定義為：對于任何的a1,b1,a2,b2L×S,a1,b1a2,b2=a1*a2,b1b2a1,b1

41、+a2,b2=a1a2,b1b2定義3.1.4（同態(tài)映射）設L,*和S, , 是兩個格，g:LS.如果對任何a,bL，有ga*b=gagb,gab=gagb則稱g是L,*到S, , 的一個同態(tài)映射.特別地，當g是一個一一對應時，稱g是一個同構映射，并且稱格L,*和S, , 同構的。如果g:LL是格L,*上一個同態(tài)映射，則稱g是一個自同態(tài)映射.如果g:LL是一個同構映射，則稱g是一個自同構映射.定義3.1.5（完備）： 對于一個格，如果它的每一個非空子集在格中都具有一個上確界和下確界，則這個格稱為完備的。顯然每個有限的格都是完備的。對于一個格，它的上確界和下確界如果存在，我們稱它們?yōu)檫@個格的邊界

42、，并分別記為1和0，因此有時這種格稱為有界格。定義3.1.6（補元）：L,*,0,1是一個有界格，aL，如果存在元bL,使a*b=0且ab=1，則稱b為a的補元。定義3.1.7（補格）：L,*,0,1中的每個元都至少具有一個補元，則稱這個格是一個補格。定義3.1.8（分配格）：L,*是一個格，如果對任何a,bL，有a*bc=a*ba*c ab*c=ab*ac 則稱L,*是一個分配格。定理3.1.6 任何兩個分配格的直接積是分配格。定理3.1.7 若L,*是一個分配格，則對于任何a,b,cL,如果a*b=a*c，并且ab=ac,則b=c推論3.1.2 如果一個格是分配格，同時又是補格，則它的每一

43、個元都具有唯一的一個補元。3.2 布爾代數(shù)定義3.2.1（布爾代數(shù)） 一個既是補格，又是分配格的格，稱為布爾代數(shù)。定義3.2.2（對偶命題） 如果B,',0,1是一個布爾代數(shù)，P是關于B中變元的一個命題，它可以由B中變元元通過運算,',0,1來表示.如果對P的表示式進行下列代換：代換為；代換為；1代換0；0代換為1，則這樣代換后也將得到一個命題Pd,它成為命題P的對偶命題，簡稱為對偶。定理3.2.1（對偶原理）如果P是一個命題，它在任何一個布爾代數(shù)中都成立，并且可以由運算,',0,1來表示，則對它的對偶命題Pd也在任何一個布爾代數(shù)中成立。定理3.2.1*（對偶原理）如果

44、P是一個命題，它在任何一個布爾代數(shù)中都成立，并且可以由運算,',0,1和關系,來表示，則將P中的運算代換為；代換為；0代換為1，1代換0；換為，換為，所得到的對偶命題也在任何一個布爾代數(shù)中成立。定理3.2.2 若B和B0是兩個布爾代數(shù)，h:BB0是一個同態(tài)映射，則B在h中的同態(tài)象hB是B0的一個子布爾代數(shù)。定義3.2.3（基元）：B,',0,1是一個布爾代數(shù)，aB,a0,如果B中不存在元x,使0<x<a,則稱a是B的一個基元。如果對于任何bB,b0都存在有基元ab,則稱這個布爾代數(shù)是基元的。定理3.2.3 若B,',0,1是一個布爾代數(shù)，aB,a0,則下列命

45、題是等價的。（1）a是一個基元（2）對于所有的xB,若xa,則x=0或x=a（3）對于所有的xB，ax=a, ax0, other推論3.2.1 若a和b是不同的基元，ab=0定理3.2.4 B,',0,1是一個基元的布爾代數(shù)，A是其基元的集合，對任一xB,令x=a|aA,ax,則x=axa,并且作為基元的析取式，這個表達式是唯一的。定理3.2.5 若B,',0,1是一個非空有限的布爾代數(shù)，A是它的所有基元構成的集合，則B,',0,1同構A,',A.推論3.2.2 一個有限的布爾代數(shù)具有2n個元，其中的n是它的基元的個數(shù)。推論3.2.3 對于任意正整數(shù)n,具有2

46、n個元的布爾代數(shù)是同構的。3.3 其他代數(shù)系統(tǒng)定義（環(huán)）3.3.1 若代數(shù)系統(tǒng)R,+, 滿足下列條件：（1）R對于二目運算+是一個可交換的加法群。（2）R對于二目運算 （即乘法）是封閉的。（3）乘法結合律成立，即對R中任何三個元a,b和c,有abc=abc（4）分配律成立，即對R中任何元a,b和c，有abc=ab+acb+ca=ba+ca則稱R,+, 是一個環(huán)。定義3.3.2（交換環(huán)） 一個環(huán)R中的任何兩個元a,b,如果都滿足ab=ba,則稱R是一個交換環(huán)。定義3.3.3 （逆元、零元）一個環(huán)R中如果存在有元e,使得對R中任何一個元都有ea=ae=a,則稱e是R的一個單位元。定義3.3.4（逆

47、元、零元） 在一個有單位元的環(huán)里，如果a和b是環(huán)中的元，滿足ab=ba=1,則稱b是a的逆元。對任意aR,若0a=a0=0,則稱0是R的零元。環(huán)的零元通常用0表示。定義3.3.7（域）：一個可交換的除環(huán)稱為一個域。定義3.3.8（子環(huán)）：一個環(huán)R的一個子集S本身對R的代數(shù)運算也構成一個環(huán)，則稱S為R的子環(huán)。定義3.3.9（理想子環(huán)，理想）：若I是環(huán)R的一個非空子集，滿足（1）a,bIa-bI（2）aI,rRra,arI則稱I是R的一個理想子環(huán)，簡稱理想。第4章 群碼4.1 通信模型和錯誤校正的基本概念4.2 二進制編碼定義4.2.1（海明距離） 設x,yBn,x與y之間的海明距離是xy的權xy

48、，用Hx,y表示。定理4.2.1 設x,y,zBn,則（1） Hx,y=Hy,x（2） Hx,y0（3） Hx,y=0當且僅當x=y（4） Hx,yHx,z+Hz,y定義4.2.2（碼字）：碼字是n元組的碼的最小距離，是該碼中所有碼字之間的海明距離的最小值。定理4.2.2 當且僅當一個編碼的任意兩個碼字之間的最小距離至少k+1時，能夠檢查出k個或至少k個錯誤的所有組合。定理4.2.3 當且僅當任意兩個碼字之間的距離至少是2k+1時，這中編碼就能夠糾正k個或少于k個錯誤的組合。定義4.2.3（群碼） 設Bm,和Bn,是群，函數(shù)e:BmBn,使得eBm=eb|bBm是Bn的子群，則稱e是編碼函數(shù).

49、 eBm是群碼。定理4.2.4 一個群碼的非零碼字的最小權等于它的最小距離。定義4.2.4 設A=aijm×n,B=bijm×n,C=cijm×n,C=AB,其中cij=aijbij,1im,1jm.定義4.2.5（布爾矩陣）： 設D=dijm×r,E=eijr×n是布爾矩陣，布爾矩陣的積F=D*E=fijm×n是布爾矩陣，其中fij=di1e1j+di2d2j+dirdr1.定理4.2.5 設m和n是非負整數(shù)，且m<n,r=n-m,并設H是n×r布爾矩陣，則函數(shù)fH:BnBr,fHx=x*H,xBn是從群Bn到Br的

50、同態(tài)映射。推論4.2.1 設m和n是非負整數(shù)，且m<n,r=n-m,并設H是n×r布爾矩陣，函數(shù)fH:BnBr,fHx=x*H,xBn使得N=x|xBn,x*H=O是正規(guī)子群。定理4.2.6 設x=y1y2ymx1xrBn,則x*H=O當且僅當某bBm,x=eHb.推論4.2.1 eHBm=eb|bBm是Bn的一個子群。4.3 解碼和錯誤校正定義4.3.1（解碼函數(shù)）：若d:BnBm是映上函數(shù)，如果dxi=b'Bm,使得當傳送通道沒有噪聲時，b=b',則稱d是與e對應的n,m解碼函數(shù)。定義4.3.2（k級校正） 設e是一個m,n編碼函數(shù)，d是與e對應的解碼函數(shù)，

51、如果x=eb是正確傳送或具有k級錯誤，則稱e,d是k級校正。定理4.3.1 假設e是m,n編碼函數(shù)，d是對應的最大似然譯碼函數(shù)，則e,d能夠校正k級錯誤，當且僅當e的最小距離至少是2k+1.定義4.3.3（陪集頭）xl的左陪集中，具有最小權的元素稱為陪集頭。定理4.3.2 如果m.n,r,H和fH定義如前，則fH是映上的。定理4.3.3 設x和y是Bn的元素，則x和y處于N的同一左陪集，當且僅當fHx=fHy,即當且僅當它們有相同的并發(fā)錯。第1章 命題演算1.1 命題和邏輯連接詞定義1.1.1（命題）： 如果有一個陳述語句，它可以取值：“真”或“假”，并且只能取其中一個值，這樣的陳述語句就成為

52、一個命題。5中基本邏輯連接詞：（1）¬：否定詞：“非A”（2）：合取詞：“A并且B”（3）：析取詞：“A或者B”（4）：蘊涵詞：“若A則 B”（5）：等值詞：“A等值于B”1.2 合式公式能成為命題的式子稱為合式公式，簡記為wff。定義1.2.1（合式公式）：（1）一個命題變元是wff.（2）若P是一個wff,則¬P是一個wff.（3）若P和Q是wff,則PQ,PQ,PQ和PQ都是wff（4）wff只限于有限次使用（1）（2）（3）所得到的符號串。定義1.2.2（部分合式公式） 如果A和B都是wff, B是A的一部分，則稱B是A的部分合式公式或子公式，部分合式公式簡記為wf

53、p.結論：在A,B都是wff,且A是符號串P的一個組成部分時。如果用B代換P中全部的A,所得到的是Q.當且僅當Q是wff時，P是wff.判斷符號串P是否是wff的算法：（1）空公式不是wff（2）對P中的wfp用命題變元代換，得到新的符號串P（3）檢查P是否還能作進一步代換，以消除邏輯連接詞.如何能則轉（2）（4）檢查最后的符號串P是否是簡單的命題變元，如果是，則原來的P是wff,否則不是。重要例題1.2.71.3 真值表、永真式定義1.3.1（永真式、重言式、有效） 對于一個wff的命題變元無論作何指派，所得到的值永為T,即命題永遠是真命題，則稱該wff為永真式或重言式，并稱它是有效的。定義

54、1.3.2（永假公式、不可滿足公式） 對于一個wff的命題變元無論作何指派，所得到的值永為F,即命題永遠是假命題，則稱該wff為永假公式或不可滿足公式。定義1.3.3（可滿足公式） 不是永真式的wff稱為非永真公式。不是永假公式的wff稱為可滿足公式。定理1.3.1 永真公式的合取式或析取式仍然是永真公式。定理1.3.2 在一個永真公式中，對某個變元用同一個wff置換，其結果仍然為永真公式。定理1.3.3 若A和B都是wff,AB的充要條件是AB是一個永真式。定理1.3.4 一個wff的永真式、永假性、非永真性和可滿足性是可判定的。1.4 命題演算的等價關系定理1.4.1（代換定理）若A是一個

55、wff，A1是它的一個wfp,A1B1,在將A中各處出現(xiàn)的A1中的一個或若干個代換B1時，如果得到的wff為B,則A=B.1.5 邏輯連接詞的可省略性如果能找到一個更小的邏輯連接詞的集合，用它們也能完成上述五個連接詞的全部功能，則我們把這種連接詞的集合稱為連接詞的功能完全集。功能完全集：¬,、¬,、¬,、：讀為“與非”（2）讀為“或非”¬PPPPPPQPPQQPPQQ1.6 范式定義1.6.1（初等積）：命題變元和它們的否定的合取式稱為初等積。定義1.6.2（初等和）：命題變元和它們的否定的析取式稱為初等和。定義1.6.3（析取范式）：如果一個wff具有形式A1A2Ann1而每個Ai都是初等積，則它稱為析取范式。定義1.6.4（合取范式）：如果一個wff具有形式A1A2Ann1而每個Ai都是初等和，則它稱為合取范式。定義1.6.5