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

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

2、為AB.定義（交集）：A和B是兩個(gè)集合，包含A和B的所有公共元，但不包含其他元的集合，稱為A和B的交集，記為AB.定義（不相交）：A和B是兩個(gè)集合，如果它們滿足AB=，則稱集合A和B是不相交的。定義（差集）：A和B是兩個(gè)集合，屬于A而不屬于B的所有元構(gòu)成集合，稱為A和B的差集，記為A-B.定義（補(bǔ)集）：若A是空間E的集合，則E中所有不屬于A的元構(gòu)成的集合稱為A的補(bǔ)集，記為A'.定義（對(duì)稱差）：A和B是兩個(gè)集合，則定義A和B的對(duì)稱差A(yù)B為AB=A-BB-A1.3 包含排斥原理定理 設(shè)A1,A2為有限集，其元素個(gè)數(shù)分別為A1，A2則 A1A1=A1+A2-A1A2定理 設(shè)A1,A2,A3為

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

4、則成為一個(gè)有序n元組（簡(jiǎn)稱n元組）。定義（直接積）：A和B是兩個(gè)集合，則所有序偶x,y的集合，稱為和的直接積（或笛卡爾積），記為A×B.定義（直接積）：設(shè)A1,A2,An是n個(gè)集合，xiAi,i=1,2,n ，則所有n元組x1,x2,xn的集合，稱為A1,A2,An的笛卡爾積（或直接積），記為A1×A2××An.定義（二元關(guān)系） 若A和B是兩個(gè)集合，則A×B的任何子集都定義了一個(gè)二元關(guān)系，稱為A×B上的二元關(guān)系。如果A=B，則稱為A上的二元關(guān)系。定義（恒等關(guān)系）：設(shè)Ix是X上的二元關(guān)系，Ix=x,x|xX，則稱Ix是X上的恒等關(guān)系。定

5、義（定義域、值域）：若S是一個(gè)二元關(guān)系，則稱DS=x|存在y,使x,yS為S的定義域。RS=y|存在x,使x,yS為S的值域。定義（自反）：設(shè) R 是集合上 X 的關(guān)系，若對(duì)于任何 xX，都有 xRx 即x,xR則稱R關(guān)系是自反的。定義（反自反）：設(shè)R 是集合上 X 的關(guān)系，若對(duì)于任何xX，都滿足x,xR,即xRx對(duì)任何xX都不成立，則稱關(guān)系R是反自反的。定義（對(duì)稱）：設(shè)R 是集合上 X 的關(guān)系，若對(duì)于任何x,yX，只要xRy,就有yRx,那么稱關(guān)系R是對(duì)稱的。定義（反對(duì)稱）：設(shè)R 是集合上 X 的關(guān)系，若對(duì)于任何x,yX，只要xRy并且yRx時(shí),就有x=y，那么稱關(guān)系R是對(duì)稱的。定義2.1.

6、11（傳遞） 設(shè)R 是集合上 X 的關(guān)系，若對(duì)于任何x,yX，只要xRy并且yRz時(shí)，就有xRz，則稱關(guān)系R是傳遞的。定理 設(shè)R 是集合上 X 的關(guān)系，若R是反自反的和傳遞的，則R是反對(duì)稱的。2.2 關(guān)系矩陣和關(guān)系圖定義 無 定理 無2.3 關(guān)系的運(yùn)算定義（連接）：設(shè) R 為X×Y上的關(guān)系，S為Y×Z上的關(guān)系，則定義關(guān)系RS=x,z|存在y,使x,yR且y,zSRS稱為關(guān)系R和S的連接或復(fù)合，有時(shí)也記為RS.定義（逆關(guān)系）：設(shè) R 為X×Y上的關(guān)系，則定義R的逆關(guān)系為R-1為Y×X上的關(guān)系：R-1=y,x|y,xR.定理 設(shè)R和S都是X×Y上的

7、二元關(guān)系，則下列各式成立（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定理設(shè)R為X×Y上的關(guān)系，S為Y×Z上的關(guān)系，則RS-1=S-1R-12.4 閉包運(yùn)算定義（自反閉包）： 設(shè)R是集合X上的二元關(guān)系，如果R1是包含R的最小自反關(guān)系，則稱R1是關(guān)系R的自反閉包，記為rR.定義（對(duì)稱閉包）： 設(shè)R是集合X上的二元關(guān)系，如果R1是包含R的最小對(duì)稱關(guān)系，則稱R1是關(guān)系R的對(duì)稱閉包，記為sR.定義（傳遞閉包）： 設(shè)R是集合X上的二元關(guān)系，如果R1是包含R的最小傳遞關(guān)系，則稱R1是關(guān)

8、系R的傳遞閉包，記為tR或R+.定理 設(shè)R是集合X上的二元關(guān)系，則（1） R是自反的，當(dāng)且僅當(dāng)rR=R.（2） R是對(duì)稱的，當(dāng)且僅當(dāng)rR=R.（3） R是傳遞的，當(dāng)且僅當(dāng)tR=R.定理 設(shè)R是集合X上的二元關(guān)系，則rR=RIx. “R恒等關(guān)系”定理 設(shè)R是集合X上的二元關(guān)系，則sR=RR-1. “R逆關(guān)系”定理 設(shè)R是集合X上的二元關(guān)系，則R+=RR2R3=i=1Ri.“R冪集”定理 設(shè)X是一個(gè)n元集，R是X上的二元關(guān)系，則存在一個(gè)正整數(shù)kn，使得R+=RR2R3Rk.2.5 等價(jià)關(guān)系和相容關(guān)系定義（覆蓋、劃分）： S是一個(gè)集合，AiS,i=1,2,n,如果i=1nAi=S，則稱a=A1,A2

9、,An是S的一個(gè)覆蓋。如果i=1nAi=S，并且AiAji,j=1,2,n,ij，則稱a是S的一個(gè)劃分，a中的元稱為S的劃分塊。定義（等價(jià)關(guān)系）：設(shè)R是X上的一個(gè)關(guān)系，如果R具有自反性、對(duì)稱性和傳遞性三個(gè)性質(zhì)，則稱R是一個(gè)等價(jià)關(guān)系。設(shè)R是等價(jià)關(guān)系，若xRy成立，則稱x等價(jià)于y.定義（等價(jià)類）：設(shè)R是X上的一個(gè)等價(jià)關(guān)系，則對(duì)任何xX，令xR=y|yX且xRy，稱xR為x關(guān)于R的等價(jià)類，簡(jiǎn)稱為x的等價(jià)類，xR也可以簡(jiǎn)記為x.定義（同余）：對(duì)于整數(shù)a,b和正整數(shù)m,有關(guān)系式：a=mk1+r10r1<mb=mk2+r20r2<m如果r1=r2，則稱a,b對(duì)于模m同余的，記作abmod m定

10、義（商集）：設(shè)R是X上的一個(gè)等價(jià)關(guān)系，由R引出的等價(jià)類組成的集合x|xX稱為集合X上由關(guān)系R產(chǎn)生的商集，記為X/R.“等價(jià)類的集合”定理若是 X 上的一個(gè)等價(jià)關(guān)系，則由R可以產(chǎn)生唯一的一個(gè)對(duì) X 的劃分?！吧碳倍x（相容關(guān)系）：設(shè)R是X上的一個(gè)關(guān)系，如果R是自反的和對(duì)稱的，則稱R是一個(gè)相容關(guān)系。相容關(guān)系可以記為.所有的等價(jià)關(guān)系都是相容關(guān)系，但相容關(guān)系卻不一定是等價(jià)關(guān)系。定義（最大相容塊）：設(shè)X是一個(gè)集合，是定義在X上的相容關(guān)系。如果AX, A中的任何兩個(gè)元都有關(guān)系，而x-A的每一個(gè)元都不能和A中所有元具有關(guān)系，則稱A是X的一個(gè)最大相容塊。2.6 偏序關(guān)系定義（偏序關(guān)系）：R是定義在集合X上的

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

12、在有元z，對(duì)任何xX都滿足xz，則稱z是X,的最大元。定義2.6.5（極小元、極大元）：X,是一個(gè)偏序集，如果yX,而X中不存在元x，使x<y,則稱y是X,的極小元。如果zX,而X中不存在元x,使z<x,則稱z是X,的極大元。定義2.6.6（上界、下界、上確界、下確界）：X,是一個(gè)偏序集，AX,x,yX,如果對(duì)于所有的aA,都有ax,則稱x是A的一個(gè)上界。如果對(duì)于所有的aA,都有ya,則稱y是A的一個(gè)下界。如果x是A的一個(gè)上界，對(duì)于A的任一上界z,都有xz,則稱x是A的最小上界（上確界）. 如果y是A的一個(gè)上界，對(duì)于A的任一上界w,都有wy,則稱y是A的最大下界（下確界）.定義2.

13、6.5（良序集）：設(shè)X,是一個(gè)偏序集，對(duì)于偏序，如果X的每個(gè)非空子集都具有最小元，則稱X,是一個(gè)良序集，而稱是X上的一個(gè)良序。每個(gè)良序集都是全序集。第3章 函數(shù)和運(yùn)算3.1 函數(shù)定義（映射、象）： 關(guān)系f定義在X×Y上，如果對(duì)于每一個(gè)xX，都有唯一的一個(gè)yY，使x,yf，則稱f是從X到Y(jié)的一個(gè)函數(shù)（或映射），記為f:XY.x稱為函數(shù) f 的變?cè)?，y稱為變?cè)獂在f下的值（或象），記為fx.注意：（1） 定義域Df=X，而不是DfX.（2） 每一個(gè)x，有唯一的yY，使x,yf.多值函數(shù)不符合定義（3） 值域RfY.定義（受限、擴(kuò)展）： 若f是從X到Y(jié)的一個(gè)函數(shù)，AX，則fA×Y

14、也是一個(gè)函數(shù)，它定義于A到Y(jié)，我們稱它是f在A上的受限。如果f是函數(shù)g的一個(gè)受限，則稱g是f的一個(gè)擴(kuò)展。定義（映上、映內(nèi)、一對(duì)一、一一對(duì)應(yīng)）： 若f:XY，則f的值域Rf=Y時(shí)，稱函數(shù)f是映上的（或滿射）。如果f的值域RfY時(shí)，則稱函數(shù)f是映內(nèi)的。如果x1,x2X,x1x2，則有fx1fx2,則稱f是一對(duì)一的（單射）（即fx1=fx2時(shí)，有x1=x2）.如果f映上的，又是一對(duì)一的，則稱f是一一對(duì)應(yīng)的（或雙射）。定義（復(fù)合運(yùn)算）：若f:XY,g:YZ，則定義f和g的復(fù)合運(yùn)算fg為：fg=x,z|存在yY,使y=fx,且z=gy即fgx=gfx.注：逆函數(shù)f-1若要存在需要滿足以下條件：（1）函數(shù)

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

16、服從交換律）.定義（可結(jié)合）：若f:X×XX是一個(gè)運(yùn)算，對(duì)于任何x,y,zX,都有ffx,y,z=fx,fy,z，則稱運(yùn)算f是可結(jié)合的（或者說，f服從結(jié)合律）.定義（可分配）：若f:X×XX是一個(gè)運(yùn)算，g:X×XX是一個(gè)運(yùn)算，對(duì)于任何x,y,zX，都有fx,gy,z=gfx,y,fx,z，則稱運(yùn)算f對(duì)于運(yùn)算g是可分配的（或者說，f對(duì)于g服從分配律）定義（左單位元、右單位元）：設(shè)*是X上的一個(gè)運(yùn)算，如果X中存在有一個(gè)元el，對(duì)于任何xX，有el*x=x，則稱el是運(yùn)算*的左單位元；如果X中存在有一個(gè)元er，對(duì)于任何xX，有x*er=x，則稱er是運(yùn)算*的右單位元。定

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

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

19、和某個(gè)自然數(shù)集Mn=0,1,2,n等勢(shì)，則稱A是一有限集，不是有限集的集合稱為無限集。定理 有限集的任何子集都是有限集定理 有限集不與其任何真子集等勢(shì)定理 自然數(shù)集N=0,1,2,是無限集4.2 可列集定義（可列集）：若A是一個(gè)集合，它和所有自然數(shù)的集合N等勢(shì)，則稱A是一個(gè)可列集?？闪屑幕鶖?shù)用符號(hào)0表示。定理 若A是一個(gè)集合，A可列的充分必要條件是可以將它的元排列為a1,a2,an,的序列形式。定理 任何無限集必包含有可列子集。定理 可列集的子集是有限集或可列集（記為：0-n0）定理 若A是可列集，B是有限集，并且AB=，則AB是可列集（記為：0+n=0）.定理若A和B都是可列集，并且AB=

20、，則AB是可列集（記為：0+0=0）推論 設(shè)Aii=1,2,n都是可列集，則i=1nAi是可列集（記為：n0=0）定理 設(shè)Aii=1,2,n都是可列集，并且AiAj=ij,i,j=1,2,，則 i=1Ai是可列集（記為：00=0）推論設(shè)Aii=1,2,n都是可列集，則i=1Ai是可列集.定理 所有有理數(shù)的集合是可列集。4.3 不可列集定理 區(qū)間0,1中所有實(shí)數(shù)構(gòu)成的集合是不可列的。定義（連續(xù)基數(shù)）： 開區(qū)間0,1中所有數(shù)組成集合的基數(shù)記為，具有基數(shù)的集合稱為連續(xù)統(tǒng)，稱為連續(xù)基數(shù)。推論：集合0,1的基數(shù)也是.定理 所有實(shí)數(shù)的集合是不可列的，它的基數(shù)是.定理 對(duì)于任何數(shù)a,b，若a<b，則區(qū)

21、間a,b,a,b,a,b,a,b)以及0,0,)都具有連續(xù)基數(shù)定理 一個(gè)無限集A和一個(gè)可列集作并集時(shí)，并集的基數(shù)等于集A 的基數(shù)。推論 一個(gè)無限集A和一個(gè)有限集的并集，其基數(shù)等于集 A 的基數(shù)。4.4 基數(shù)的比較定義（<） 設(shè)集合A的基數(shù)是=.如果A與B的真子集等勢(shì)，而A和B不等勢(shì)，則稱A的基數(shù)小于B的基數(shù)，記為<.定理：A,B是兩個(gè)集合，若A與B的某一子集等勢(shì)，B與A的某一子集等勢(shì)，則AB.定理：A,B是任意兩個(gè)集合，A的基數(shù)為, B的基數(shù)為，則下列三個(gè)關(guān)系：=,<,>中必有一個(gè)且只有個(gè)成立。定理：若n是有限集A的基數(shù)，則n<0<.定理：若A是無限集合，則

22、0CardA定理：若A1,A2,An,是可列個(gè)互不相交的集合，它們的基數(shù)都是，則n=1An的基數(shù)是（記為：0=）定理：可列集的冪集，其基數(shù)是（記為：20=）定理：若A是一個(gè)集合，B=A是A的冪集，則CardA<CardB.此定理說明：不存在最大的基數(shù)。補(bǔ)充：2>, >第5章 形式語言5.1 文法和語言定義（產(chǎn)生式）： 一個(gè)產(chǎn)生式或重寫規(guī)則是一個(gè)有序?qū),x，通常寫成Ux,其中，U是一個(gè)符號(hào)，而x是一個(gè)符號(hào)的非空有限串，U是這個(gè)產(chǎn)生式的左部，而x是產(chǎn)生式的右部.產(chǎn)生式將簡(jiǎn)稱為規(guī)則。定義（非終極符號(hào)、字母表、終極符號(hào)、開始符號(hào)）：一個(gè)文法G是一個(gè)四元組VN,VT,P,S.其中，V

23、N是元語言的語法類或變?cè)募?，它生成語言的串，這些語法類或變?cè)蔀榉墙K極符號(hào)，VT是符號(hào)的非空有窮集合，稱為字母表，VT的符號(hào)稱為終極符號(hào). S是VN之一，是詞匯表的一個(gè)識(shí)別元素，稱為開始符號(hào). P是產(chǎn)生式的集合。定義（直接產(chǎn)生、直接推導(dǎo)，直接規(guī)約）：設(shè)G是一個(gè)文法，如果V=xUy,w=xuy，而G中有規(guī)則Uu，就稱串V直接產(chǎn)生串w，或稱w是V直接推導(dǎo)出來的，或w直接規(guī)約到V,記為Vw.定義（產(chǎn)生、規(guī)約到、推導(dǎo)）：設(shè)G是一個(gè)文法，如果存在產(chǎn)生式序列P1,P2,Pnn>0,使得VP1P2Pn-1Pn，而Pn=w,就說V產(chǎn)生w（w規(guī)約到V,或w是V的推導(dǎo)），記為V+w.定義（句型）：令G是

24、一個(gè)文法，如果串x可從開始符號(hào)S推導(dǎo)出來，即如果S*x，則x稱為一個(gè)句型。補(bǔ)充： 若=a,b，則*=,a,b,aa,ab,ba,bb,aaa,其中是空串，+=a,b,aa,ab,ba,bb,aaa,（不含空串）5.2 文法的類型定義（0-型文法）：在上的0-型文法由以下組成：（1） 不在中的不同符號(hào)的非空集合V,稱為變量表，它包含一個(gè)綱符號(hào)S, S稱為開始變量。（2） 產(chǎn)生式的有限集合。由G產(chǎn)生的所有字集稱為由G產(chǎn)生的語言。定義（0-型語言）：在上可由某一0-型文法產(chǎn)生的字集稱為0-型語言。定義（1-型文法）：如果在0-型文法中，對(duì)于P中的每個(gè)產(chǎn)生式，要求,則這文法稱為1-型文法或上下文敏感文

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

26、，分別為0,1,2目運(yùn)算符，則X,1,2,3的類型為0,1,2.1.2 同態(tài)和同構(gòu)定義（同態(tài)象、同態(tài)映射）: X,1和Y,2是兩個(gè)同類型的代數(shù)系統(tǒng)，映射g:XY, 1和2也構(gòu)成一一對(duì)應(yīng).如果對(duì)于任意n目運(yùn)算11，及其對(duì)應(yīng)的運(yùn)算22，當(dāng)x1,x2,xnX時(shí)，都有g(shù)1x1,x2,xn=2gx1,gx2,gxn,則稱代數(shù)Y,2是X,1的同態(tài)象，稱g是從X,1到Y(jié),2的一個(gè)同態(tài)映射。定義（同態(tài)象、同態(tài)映射）：若X,和Y,*是兩個(gè)同類型的代數(shù)系統(tǒng)，和*都是二目運(yùn)算，映射g:XY.如果對(duì)于任何x,yX,都有g(shù)xy=gx*gy，則稱Y,*是X,的一個(gè)同態(tài)象，稱g是從X,到Y(jié),*的一個(gè)同態(tài)映射。注：如果Y,*

27、就是X,，則映射g是從X到它自身。當(dāng)上述條件仍然滿足時(shí)，我們就稱g是X,的一個(gè)自同態(tài)映射。定義（同構(gòu)、同構(gòu)映射、自同構(gòu)映射）：如果X,和Y,*是同態(tài)的，映射g:XY不僅是同態(tài)映射，而且是一一對(duì)應(yīng)的，則稱Y,*和X,同構(gòu)，稱g是從X,到Y(jié),*的一個(gè)同構(gòu)映射。如果Y,*就是X,，則稱g是X,上的一個(gè)自同構(gòu)映射定義（同余關(guān)系）：設(shè)Z,是一個(gè)代數(shù)系統(tǒng)，是Z上的一個(gè)等價(jià)關(guān)系，如果存在x1,x2,x3,x4Z,當(dāng)x1,x2,x3,x4時(shí)，x1x3,x2x4成立，則稱是Z,上的一個(gè)同余關(guān)系。定理：設(shè)是Z上的一個(gè)等價(jià)關(guān)系，如果存在同態(tài)映射g:Z,Y,*,使得當(dāng)x1,x2Z時(shí)，x1x2當(dāng)且僅當(dāng)gx1=gx2，則

28、是Z,上的同余關(guān)系。1.3 商代數(shù)與積代數(shù)定義（子代數(shù)）：設(shè)Z,是一個(gè)代數(shù)系統(tǒng)，Z1Z在運(yùn)算下封閉的，則稱Z1,是Z,的一個(gè)子代數(shù)。定義1.3.2（直接積）：設(shè)Z,到Y(jié),*是兩個(gè)同類型的代數(shù)系統(tǒng)，如果對(duì)任意的x1,x2Z和y1,y2Y，定義運(yùn)算于Z×Y:x1,y2x2,y2=x1x2,y1*y2，稱Z×Y,是Z,和Y,*的直接積，稱Z,和Y,*為Z×Y,的因子。第2章 半群和群2.1 半群和有幺半群定義（半群、有幺半群）：S是一個(gè)非空集合，如果S中定義了一個(gè)二目運(yùn)算 ，對(duì)于任何a,b,cS,都有abc=abc，則稱S , 是一個(gè)半群.如果半群S , 中具有單位元e

29、，使得對(duì)任何xS,都有ex=xe=x,則稱S , 是一個(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)G , *中，如果二目運(yùn)算*滿足（1）對(duì)于任何a,b,cG,有a*b*c=a*b*c；（2）G中存在單位元e，對(duì)任何aG,有a*e=e*a=a；（3）對(duì)于任何aG，存在有逆元a-1G,使a*a-1=a-1*a=e則稱G , *是一個(gè)群。注

30、：對(duì)于群G , *來說，單位元e是唯一的，每個(gè)元a的逆元a-1也是唯一的?！按嬖谀嬖挠戌郯肴航凶鋈骸倍x（階數(shù)）：若G , *是一個(gè)群，當(dāng)G是有限集時(shí)，則稱G中元的個(gè)數(shù)為群的階數(shù)，記為G.定理2.2.1 若G , *是一個(gè)群，x,yG，則xy-1=y-1x-1，其中xy即x*y.定義（冪）：G , *是一個(gè)群，xG，則記r個(gè)x的積x*x*x為xr, xr稱為x冪，x-1r記為x-r, x0表示單位元e。定理（指數(shù)律）：若m和n是整數(shù)，則xmxn=xm+n,xmn=xmn.定理 若xy=yx,則 xmyn=ynxm定義（次數(shù)）：若G,*是一個(gè)群，xG,使xn=e=x0的最小正整數(shù)n，稱為元x的

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

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

33、n個(gè)置換所構(gòu)成的群，則稱G是一個(gè)n階置換群。定理 任何一個(gè)（n階）群都同構(gòu)于一個(gè)（n階）置換群。2.4 子群、群的同態(tài)定義（子群）： G,*是一個(gè)群，SG,如果（1）單位元eS（2）若aS，則a的逆元a-1S（3）若a,bS,則a*bS則稱S,*是G,*的一個(gè)子群。定理 G,*是一個(gè)群，SG，S,*是一個(gè)子群的充分必要條件是：若a,bS,則a*b-1S定義（同態(tài)象、群同態(tài)映射）：G,*和H,*是群，g:GH.若對(duì)任何a,bG,有g(shù)a*b=gagb群的同態(tài)映射具有下列性質(zhì)：（1）將單位元映射為單位元（2）將逆元映射為逆元（3）對(duì)運(yùn)算封閉，即對(duì)任何a,bG，有g(shù)agb=ga*b定理 若G,*和H,

34、*是群，g:GH是一個(gè)群同態(tài)映射，則g將G,*的子群映射為H,的子群。定義（同態(tài)核）：若g:GH是一個(gè)群同態(tài)映射，eH是H的單位元，則G中所有滿足ga=eH的元a的集合，稱為同態(tài)核，記為Kerg.定理 同態(tài)核是一個(gè)子群。定理 若H,*是群G,*的子群，則H定義了G上的一個(gè)劃分（因而也定義了G上一個(gè)等價(jià)關(guān)系）.群子集：假定A,B都是群G,*中的元構(gòu)成的集合（稱之為群子集），定義AB=a*b|aA,bB特別地，當(dāng)A是一元集a時(shí)，我們簡(jiǎn)記AB為aB,則aB=a*b|bB定理若A,*是群B,*的子群都是群G,*的子群，則AB,*是一個(gè)群的充分必要條件是AB=BA.2.5 陪集、正規(guī)子群、商群定義（左陪

35、集）：若H,*是群G,*的子群，對(duì)于aG,稱aH=a*h|hH稱為H的一個(gè)左陪集.定理若H,*是群G,*的子群，則H的所有左陪集構(gòu)成G的一個(gè)劃分。定理（拉格朗日定理）每個(gè)左陪集的元和H中的元都是一樣多。推論2.5.1 子群中元的個(gè)數(shù)一定是群中元的個(gè)數(shù)的因子。定義（正規(guī)子群）：若H,*是群G,*的子群，對(duì)于任何aG,都滿足aH=Ha,則稱H,*是群G,*的一個(gè)正規(guī)子群.一個(gè)阿貝爾群的任何子群都是正規(guī)子群。當(dāng)H,*是群G,*的正規(guī)子群時(shí)，對(duì)于H關(guān)于G的陪集.定義運(yùn)算 為aHbH=a*bH考慮所有H關(guān)于G的陪集組成的集合aH|aG和運(yùn)算 構(gòu)成的系統(tǒng)aH, 為一個(gè)群。這個(gè)群稱為G關(guān)于H的商群，記為G/

36、H.定理 若g:GH是從群G,*到群H,的映上的同態(tài)映射，則核N是正規(guī)子群，商群G/N同構(gòu)于N.群同態(tài)基本定理：商群G/N是由陪集aN構(gòu)成的群，也是同余類的集aN構(gòu)成的群，所以它同構(gòu)于象代數(shù)，即G/N同構(gòu)于H.如果群沒有真正的正規(guī)子群，則該群為單群。正規(guī)群的任何子群都是正規(guī)子群。第3章 格和布爾代數(shù)3.1 格定義（格）：L,表示一個(gè)偏序集，如果對(duì)于L中的任何兩個(gè)元a和b,在L中都存在一個(gè)元是它們的上確界，存在一個(gè)元是它們的下確界，則稱L,是一個(gè)格。對(duì)于L中的元a,b，它們的上確界常常記為ab，它們的下確界常常記為a*b,前者又稱為a和b析取或和（ab或a+b），后者又稱為a和b的合取或積（ab

37、或ab或ab）。定理3.1.1 若L,是一個(gè)格，則對(duì)于任何a,bL，有（1） ab的充分必要條件是a*b=a.（2） ab的充分必要條件是ab=b.定理（保序性）若L,是一個(gè)格，則對(duì)于任何a,b,cL，當(dāng)bc時(shí)，有a*ba*c,ab<ac引理若L,是一個(gè)格， a,b,cL,ab,ac，則ab*c定理（分配不等式）：若L,是一個(gè)格，則對(duì)于任何a,b,cL，ab*cab*aca*bca*ba*c定理（模數(shù)不等式）若L,是一個(gè)格，則對(duì)于任何a,b,cL，ac的充分必要條件是ab*cab*c定理3.1.5 若S,*是一個(gè)代數(shù)系統(tǒng)，和*是S上的二目運(yùn)算，它服從交換律、結(jié)合律和吸收律.則S,*是一個(gè)

38、格.定義（子格） L,*是一個(gè)格，SL，當(dāng)且僅當(dāng)S對(duì)于運(yùn)算和*是封閉的，運(yùn)算結(jié)果和在L中相同時(shí)，則稱代數(shù)系統(tǒng)S,*是L的一個(gè)子格。定義（直接積） 若L,*和S, , 是兩個(gè)格，則L×S,+, 稱為這兩個(gè)格的直接積，其中的運(yùn)算+和定義為：對(duì)于任何的a1,b1,a2,b2L×S,a1,b1a2,b2=a1*a2,b1b2a1,b1+a2,b2=a1a2,b1b2定義（同態(tài)映射）設(shè)L,*和S, , 是兩個(gè)格，g:LS.如果對(duì)任何a,bL，有g(shù)a*b=gagb,gab=gagb則稱g是L,*到S, , 的一個(gè)同態(tài)映射.特別地，當(dāng)g是一個(gè)一一對(duì)應(yīng)時(shí)，稱g是一個(gè)同構(gòu)映射，并且稱格L,*

39、和S, , 同構(gòu)的。如果g:LL是格L,*上一個(gè)同態(tài)映射，則稱g是一個(gè)自同態(tài)映射.如果g:LL是一個(gè)同構(gòu)映射，則稱g是一個(gè)自同構(gòu)映射.定義（完備）： 對(duì)于一個(gè)格，如果它的每一個(gè)非空子集在格中都具有一個(gè)上確界和下確界，則這個(gè)格稱為完備的。顯然每個(gè)有限的格都是完備的。對(duì)于一個(gè)格，它的上確界和下確界如果存在，我們稱它們?yōu)檫@個(gè)格的邊界，并分別記為1和0，因此有時(shí)這種格稱為有界格。定義（補(bǔ)元）：L,*,0,1是一個(gè)有界格，aL，如果存在元bL,使a*b=0且ab=1，則稱b為a的補(bǔ)元。定義（補(bǔ)格）：L,*,0,1中的每個(gè)元都至少具有一個(gè)補(bǔ)元，則稱這個(gè)格是一個(gè)補(bǔ)格。定義（分配格）：L,*是一個(gè)格，如果對(duì)任

40、何a,bL，有a*bc=a*ba*c ab*c=ab*ac 則稱L,*是一個(gè)分配格。定理 任何兩個(gè)分配格的直接積是分配格。定理 若L,*是一個(gè)分配格，則對(duì)于任何a,b,cL,如果a*b=a*c，并且ab=ac,則b=c推論3.1.2 如果一個(gè)格是分配格，同時(shí)又是補(bǔ)格，則它的每一個(gè)元都具有唯一的一個(gè)補(bǔ)元。3.2 布爾代數(shù)定義（布爾代數(shù)） 一個(gè)既是補(bǔ)格，又是分配格的格，稱為布爾代數(shù)。定義（對(duì)偶命題） 如果B,',0,1是一個(gè)布爾代數(shù)，P是關(guān)于B中變?cè)囊粋€(gè)命題，它可以由B中變?cè)ㄟ^運(yùn)算,',0,1來表示.如果對(duì)P的表示式進(jìn)行下列代換：代換為；代換為；1代換0；0代換為1，則這樣代

41、換后也將得到一個(gè)命題Pd,它成為命題P的對(duì)偶命題，簡(jiǎn)稱為對(duì)偶。定理（對(duì)偶原理）如果P是一個(gè)命題，它在任何一個(gè)布爾代數(shù)中都成立，并且可以由運(yùn)算,',0,1來表示，則對(duì)它的對(duì)偶命題Pd也在任何一個(gè)布爾代數(shù)中成立。定理*（對(duì)偶原理）如果P是一個(gè)命題，它在任何一個(gè)布爾代數(shù)中都成立，并且可以由運(yùn)算,',0,1和關(guān)系,來表示，則將P中的運(yùn)算代換為；代換為；0代換為1，1代換0；換為，換為，所得到的對(duì)偶命題也在任何一個(gè)布爾代數(shù)中成立。定理 若B和B0是兩個(gè)布爾代數(shù)，h:BB0是一個(gè)同態(tài)映射，則B在h中的同態(tài)象hB是B0的一個(gè)子布爾代數(shù)。定義（基元）：B,',0,1是一個(gè)布爾代數(shù)，aB

42、,a0,如果B中不存在元x,使0<x<a,則稱a是B的一個(gè)基元。如果對(duì)于任何bB,b0都存在有基元ab,則稱這個(gè)布爾代數(shù)是基元的。定理 若B,',0,1是一個(gè)布爾代數(shù)，aB,a0,則下列命題是等價(jià)的。（1）a是一個(gè)基元（2）對(duì)于所有的xB,若xa,則x=0或x=a（3）對(duì)于所有的xB，ax=a, ax0, other推論3.2.1 若a和b是不同的基元，ab=0定理 B,',0,1是一個(gè)基元的布爾代數(shù)，A是其基元的集合，對(duì)任一xB,令x=a|aA,ax,則x=axa,并且作為基元的析取式，這個(gè)表達(dá)式是唯一的。定理 若B,',0,1是一個(gè)非空有限的布爾代數(shù)，A

43、是它的所有基元構(gòu)成的集合，則B,',0,1同構(gòu)A,',A.推論3.2.2 一個(gè)有限的布爾代數(shù)具有2n個(gè)元，其中的n是它的基元的個(gè)數(shù)。推論3.2.3 對(duì)于任意正整數(shù)n,具有2n個(gè)元的布爾代數(shù)是同構(gòu)的。3.3 其他代數(shù)系統(tǒng)定義（環(huán)）3.3.1 若代數(shù)系統(tǒng)R,+, 滿足下列條件：（1）R對(duì)于二目運(yùn)算+是一個(gè)可交換的加法群。（2）R對(duì)于二目運(yùn)算 （即乘法）是封閉的。（3）乘法結(jié)合律成立，即對(duì)R中任何三個(gè)元a,b和c,有abc=abc（4）分配律成立，即對(duì)R中任何元a,b和c，有abc=ab+acb+ca=ba+ca則稱R,+, 是一個(gè)環(huán)。定義（交換環(huán)） 一個(gè)環(huán)R中的任何兩個(gè)元a,b,如

44、果都滿足ab=ba,則稱R是一個(gè)交換環(huán)。定義3.3.3 （逆元、零元）一個(gè)環(huán)R中如果存在有元e,使得對(duì)R中任何一個(gè)元都有ea=ae=a,則稱e是R的一個(gè)單位元。定義（逆元、零元） 在一個(gè)有單位元的環(huán)里，如果a和b是環(huán)中的元，滿足ab=ba=1,則稱b是a的逆元。對(duì)任意aR,若0a=a0=0,則稱0是R的零元。環(huán)的零元通常用0表示。定義3.3.7（域）：一個(gè)可交換的除環(huán)稱為一個(gè)域。定義（子環(huán)）：一個(gè)環(huán)R的一個(gè)子集S本身對(duì)R的代數(shù)運(yùn)算也構(gòu)成一個(gè)環(huán)，則稱S為R的子環(huán)。定義（理想子環(huán)，理想）：若I是環(huán)R的一個(gè)非空子集，滿足（1）a,bIa-bI（2）aI,rRra,arI則稱I是R的一個(gè)理想子環(huán)，簡(jiǎn)稱

45、理想。第4章 群碼4.1 通信模型和錯(cuò)誤校正的基本概念4.2 二進(jìn)制編碼定義（海明距離） 設(shè)x,yBn,x與y之間的海明距離是xy的權(quán)xy，用Hx,y表示。定理 設(shè)x,y,zBn,則（1） Hx,y=Hy,x（2） Hx,y0（3） Hx,y=0當(dāng)且僅當(dāng)x=y（4） Hx,yHx,z+Hz,y定義（碼字）：碼字是n元組的碼的最小距離，是該碼中所有碼字之間的海明距離的最小值。定理 當(dāng)且僅當(dāng)一個(gè)編碼的任意兩個(gè)碼字之間的最小距離至少k+1時(shí)，能夠檢查出k個(gè)或至少k個(gè)錯(cuò)誤的所有組合。定理 當(dāng)且僅當(dāng)任意兩個(gè)碼字之間的距離至少是2k+1時(shí)，這中編碼就能夠糾正k個(gè)或少于k個(gè)錯(cuò)誤的組合。定義（群碼） 設(shè)Bm,

46、和Bn,是群，函數(shù)e:BmBn,使得eBm=eb|bBm是Bn的子群，則稱e是編碼函數(shù). eBm是群碼。定理 一個(gè)群碼的非零碼字的最小權(quán)等于它的最小距離。定義4.2.4 設(shè)A=aijm×n,B=bijm×n,C=cijm×n,C=AB,其中cij=aijbij,1im,1jm.定義（布爾矩陣）： 設(shè)D=dijm×r,E=eijr×n是布爾矩陣，布爾矩陣的積F=D*E=fijm×n是布爾矩陣，其中fij=di1e1j+di2d2j+dirdr1.定理 設(shè)m和n是非負(fù)整數(shù)，且m<n,r=n-m,并設(shè)H是n×r布爾矩陣，則函

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

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

49、連接詞：（1）¬：否定詞：“非A”（2）：合取詞：“A并且B”（3）：析取詞：“A或者B”（4）：蘊(yùn)涵詞：“若A則 B”（5）：等值詞：“A等值于B”1.2 合式公式能成為命題的式子稱為合式公式，簡(jiǎn)記為wff。定義（合式公式）：（1）一個(gè)命題變?cè)莣ff.（2）若P是一個(gè)wff,則¬P是一個(gè)wff.（3）若P和Q是wff,則PQ,PQ,PQ和PQ都是wff（4）wff只限于有限次使用（1）（2）（3）所得到的符號(hào)串。定義（部分合式公式） 如果A和B都是wff, B是A的一部分，則稱B是A的部分合式公式或子公式，部分合式公式簡(jiǎn)記為wfp.結(jié)論：在A,B都是wff,且A是符號(hào)串

50、P的一個(gè)組成部分時(shí)。如果用B代換P中全部的A,所得到的是Q.當(dāng)且僅當(dāng)Q是wff時(shí)，P是wff.判斷符號(hào)串P是否是wff的算法：（1）空公式不是wff（2）對(duì)P中的wfp用命題變?cè)鷵Q，得到新的符號(hào)串P（3）檢查P是否還能作進(jìn)一步代換，以消除邏輯連接詞.如何能則轉(zhuǎn)（2）（4）檢查最后的符號(hào)串P是否是簡(jiǎn)單的命題變?cè)?，如果是，則原來的P是wff,否則不是。重要1.3 真值表、永真式定義（永真式、重言式、有效） 對(duì)于一個(gè)wff的命題變?cè)獰o論作何指派，所得到的值永為T,即命題永遠(yuǎn)是真命題，則稱該wff為永真式或重言式，并稱它是有效的。定義（永假公式、不可滿足公式） 對(duì)于一個(gè)wff的命題變?cè)獰o論作何指派，

51、所得到的值永為F,即命題永遠(yuǎn)是假命題，則稱該wff為永假公式或不可滿足公式。定義（可滿足公式） 不是永真式的wff稱為非永真公式。不是永假公式的wff稱為可滿足公式。定理 永真公式的合取式或析取式仍然是永真公式。定理 在一個(gè)永真公式中，對(duì)某個(gè)變?cè)猛粋€(gè)wff置換，其結(jié)果仍然為永真公式。定理 若A和B都是wff,AB的充要條件是AB是一個(gè)永真式。定理 一個(gè)wff的永真式、永假性、非永真性和可滿足性是可判定的。1.4 命題演算的等價(jià)關(guān)系定理（代換定理）若A是一個(gè)wff，A1是它的一個(gè)wfp,A1B1,在將A中各處出現(xiàn)的A1中的一個(gè)或若干個(gè)代換B1時(shí)，如果得到的wff為B,則A=B.1.5 邏輯連

52、接詞的可省略性如果能找到一個(gè)更小的邏輯連接詞的集合，用它們也能完成上述五個(gè)連接詞的全部功能，則我們把這種連接詞的集合稱為連接詞的功能完全集。功能完全集：¬,、¬,、¬,、：讀為“與非”（2）讀為“或非”¬PPPPPPQPPQQPPQQ1.6 范式定義（初等積）：命題變?cè)退鼈兊姆穸ǖ暮先∈椒Q為初等積。定義（初等和）：命題變?cè)退鼈兊姆穸ǖ奈鋈∈椒Q為初等和。定義（析取范式）：如果一個(gè)wff具有形式A1A2Ann1而每個(gè)Ai都是初等積，則它稱為析取范式。定義（合取范式）：如果一個(gè)wff具有形式A1A2Ann1而每個(gè)Ai都是初等和，則它稱為合取范式。定義1.6

53、.5 （最小項(xiàng)）：在初等積中，每個(gè)命題變?cè)退姆穸ú荒芡瑫r(shí)出現(xiàn)，但兩者中必須出現(xiàn)一個(gè)，而且只能出現(xiàn)一次，這樣的初等積稱為最小項(xiàng)。定義（標(biāo)準(zhǔn)析取范式）：對(duì)于一個(gè)wff，僅由它的最小項(xiàng)的析取組成的等價(jià)公式稱為它的標(biāo)準(zhǔn)析取范式。定理 在真值表中，一個(gè)wff的真值為T的指派所對(duì)應(yīng)的最小項(xiàng)的析取式，即為此wff的標(biāo)準(zhǔn)析取范式?！罢嬷禐門的并集，變?cè)≌倍x（最大項(xiàng)）：在初等和中，每個(gè)命題變?cè)退姆穸ú荒芡瑫r(shí)出現(xiàn)，但兩者中必須出現(xiàn)一個(gè)，而且只能出現(xiàn)一次，這樣的初等和稱為最大項(xiàng)。定義（標(biāo)準(zhǔn)合取范式）：對(duì)于一個(gè)wff,僅由它的最大項(xiàng)的合取組成的等價(jià)公式稱為它的標(biāo)準(zhǔn)合取范式。定理 一個(gè)wff的真值為F的指

54、派所對(duì)應(yīng)的最大項(xiàng)的合取式，即為此的標(biāo)準(zhǔn)合取范式。“真值為F的交集，變?cè)》础?.7 推理和證明方法定義（邏輯前提、有效結(jié)論）：A1,A2,An和A都是wff,如果對(duì)于A1A2An取值1的任何代入，A也一定取值1，則稱A1,A2,An是A的邏輯前提，A是A1,A2,An的有效結(jié)論，并記為A1,A2,AnA.定理：A1,A2,AnA的充分必要條件是A1,A2,AnA為永真公式。判斷命題是否是有效結(jié)論的方法：（1）真值表法（2）直接證法l P規(guī)則：在推導(dǎo)的任一步都可以引用任一前提l T規(guī)則：如果公式S在前面的推導(dǎo)中已經(jīng)提到，則S可以在以后的推導(dǎo)過程中引用，否則不得引用。l CP規(guī)則：若結(jié)論形如BA,則B可作為前提，與前提P一起推出A,即P,BA等價(jià)PBA永真.即PBA可改寫成P,BA.（3）反證法定義（相容、不相容）：若A1,A2,An是一組wff, P1,P2,Pm是它們中出現(xiàn)的全部命題變?cè)?，在?duì) P1,P2,Pm的各組真值指派中，至少有一組使A1A2An的取值為1，則稱A1A2An是相容的. 如果對(duì)于P1,P2,Pm的任何真值指派A1A2An都取值0，則稱A1,A2,An是不相容的.定理 若A1,A2,An和A是wff，則A1,A2