离散数学课本定义和定理

1、第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. 定义（幂集）：给定集合A，以A的所有子集为元构成的一个集合，这个集合称为A的幂集，记为 A 或 2A1.2 集合的运算定义1.2.1（并集）：设A和B是两个集合，则包含A和B的所有元，但不包含其他元的集合，称为A和B的并集，记

2、为AB.定义（交集）：A和B是两个集合，包含A和B的所有公共元，但不包含其他元的集合，称为A和B的交集，记为AB.定义（不相交）：A和B是两个集合，如果它们满足AB=，则称集合A和B是不相交的。定义（差集）：A和B是两个集合，属于A而不属于B的所有元构成集合，称为A和B的差集，记为A-B.定义（补集）：若A是空间E的集合，则E中所有不属于A的元构成的集合称为A的补集，记为A'.定义（对称差）：A和B是两个集合，则定义A和B的对称差AB为AB=A-BB-A1.3 包含排斥原理定理 设A1,A2为有限集，其元素个数分别为A1，A2则 A1A1=A1+A2-A1A2定理 设A1,A2,A3为

3、有限集，其元素个数分别为A1,A2,A3，则A1A2A3=A1+A2+A3-A1A2-A1A3-A2A3+A1A2A3定理 设A1,A2,An为有限集，则A1A2An=i=1nAi-1i<jnAiAj+1i<j<knAiAjAk+-1n-1A1A2An重要例题 P11 例第2章 二元关系2.1 关系定义（序偶）：若 x 和 y 是两个元，将它们按前后顺序排列，记为x,y，则y,x成为一个序偶。 对于序偶x,y和a,b，当且仅当x=a并且y=b时，才称x,y和a,b相等，记为x,y=a,b定义（有序n元组）：若x1,x2,xn是个元，将它们按前后顺序排列，记为x1,x2,xn，

4、则成为一个有序n元组（简称n元组）。定义（直接积）：A和B是两个集合，则所有序偶x,y的集合，称为和的直接积（或笛卡尔积），记为A×B.定义（直接积）：设A1,A2,An是n个集合，xiAi,i=1,2,n ，则所有n元组x1,x2,xn的集合，称为A1,A2,An的笛卡尔积（或直接积），记为A1×A2××An.定义（二元关系） 若A和B是两个集合，则A×B的任何子集都定义了一个二元关系，称为A×B上的二元关系。如果A=B，则称为A上的二元关系。定义（恒等关系）：设Ix是X上的二元关系，Ix=x,x|xX，则称Ix是X上的恒等关系。定

5、义（定义域、值域）：若S是一个二元关系，则称DS=x|存在y,使x,yS为S的定义域。RS=y|存在x,使x,yS为S的值域。定义（自反）：设 R 是集合上 X 的关系，若对于任何 xX，都有 xRx 即x,xR则称R关系是自反的。定义（反自反）：设R 是集合上 X 的关系，若对于任何xX，都满足x,xR,即xRx对任何xX都不成立，则称关系R是反自反的。定义（对称）：设R 是集合上 X 的关系，若对于任何x,yX，只要xRy,就有yRx,那么称关系R是对称的。定义（反对称）：设R 是集合上 X 的关系，若对于任何x,yX，只要xRy并且yRx时,就有x=y，那么称关系R是对称的。定义2.1.

6、11（传递） 设R 是集合上 X 的关系，若对于任何x,yX，只要xRy并且yRz时，就有xRz，则称关系R是传递的。定理 设R 是集合上 X 的关系，若R是反自反的和传递的，则R是反对称的。2.2 关系矩阵和关系图定义 无 定理 无2.3 关系的运算定义（连接）：设 R 为X×Y上的关系，S为Y×Z上的关系，则定义关系RS=x,z|存在y,使x,yR且y,zSRS称为关系R和S的连接或复合，有时也记为RS.定义（逆关系）：设 R 为X×Y上的关系，则定义R的逆关系为R-1为Y×X上的关系：R-1=y,x|y,xR.定理 设R和S都是X×Y上的

7、二元关系，则下列各式成立（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定理设R为X×Y上的关系，S为Y×Z上的关系，则RS-1=S-1R-12.4 闭包运算定义（自反闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小自反关系，则称R1是关系R的自反闭包，记为rR.定义（对称闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小对称关系，则称R1是关系R的对称闭包，记为sR.定义（传递闭包）： 设R是集合X上的二元关系，如果R1是包含R的最小传递关系，则称R1是关

8、系R的传递闭包，记为tR或R+.定理 设R是集合X上的二元关系，则（1） R是自反的，当且仅当rR=R.（2） R是对称的，当且仅当rR=R.（3） R是传递的，当且仅当tR=R.定理 设R是集合X上的二元关系，则rR=RIx. “R恒等关系”定理 设R是集合X上的二元关系，则sR=RR-1. “R逆关系”定理 设R是集合X上的二元关系，则R+=RR2R3=i=1Ri.“R幂集”定理 设X是一个n元集，R是X上的二元关系，则存在一个正整数kn，使得R+=RR2R3Rk.2.5 等价关系和相容关系定义（覆盖、划分）： S是一个集合，AiS,i=1,2,n,如果i=1nAi=S，则称a=A1,A2

9、,An是S的一个覆盖。如果i=1nAi=S，并且AiAji,j=1,2,n,ij，则称a是S的一个划分，a中的元称为S的划分块。定义（等价关系）：设R是X上的一个关系，如果R具有自反性、对称性和传递性三个性质，则称R是一个等价关系。设R是等价关系，若xRy成立，则称x等价于y.定义（等价类）：设R是X上的一个等价关系，则对任何xX，令xR=y|yX且xRy，称xR为x关于R的等价类，简称为x的等价类，xR也可以简记为x.定义（同余）：对于整数a,b和正整数m,有关系式：a=mk1+r10r1<mb=mk2+r20r2<m如果r1=r2，则称a,b对于模m同余的，记作abmod m定

10、义（商集）：设R是X上的一个等价关系，由R引出的等价类组成的集合x|xX称为集合X上由关系R产生的商集，记为X/R.“等价类的集合”定理若是 X 上的一个等价关系，则由R可以产生唯一的一个对 X 的划分。“商集”定义（相容关系）：设R是X上的一个关系，如果R是自反的和对称的，则称R是一个相容关系。相容关系可以记为.所有的等价关系都是相容关系，但相容关系却不一定是等价关系。定义（最大相容块）：设X是一个集合，是定义在X上的相容关系。如果AX, A中的任何两个元都有关系，而x-A的每一个元都不能和A中所有元具有关系，则称A是X的一个最大相容块。2.6 偏序关系定义（偏序关系）：R是定义在集合X上的

11、一个关系，如果它具有自反性、反对称性和传递性，则称R是X上的一个偏序关系，简称为一个偏序，记为.更一般地讲，若X是一个集合，在X上定义了一个偏序，则我们用符号 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中存

12、在有元z，对任何xX都满足xz，则称z是X,的最大元。定义2.6.5（极小元、极大元）：X,是一个偏序集，如果yX,而X中不存在元x，使x<y,则称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.

13、6.5（良序集）：设X,是一个偏序集，对于偏序，如果X的每个非空子集都具有最小元，则称X,是一个良序集，而称是X上的一个良序。每个良序集都是全序集。第3章 函数和运算3.1 函数定义（映射、象）： 关系f定义在X×Y上，如果对于每一个xX，都有唯一的一个yY，使x,yf，则称f是从X到Y的一个函数（或映射），记为f:XY.x称为函数 f 的变元，y称为变元x在f下的值（或象），记为fx.注意：（1） 定义域Df=X，而不是DfX.（2） 每一个x，有唯一的yY，使x,yf.多值函数不符合定义（3） 值域RfY.定义（受限、扩展）： 若f是从X到Y的一个函数，AX，则fA×Y

14、也是一个函数，它定义于A到Y，我们称它是f在A上的受限。如果f是函数g的一个受限，则称g是f的一个扩展。定义（映上、映内、一对一、一一对应）： 若f:XY，则f的值域Rf=Y时，称函数f是映上的（或满射）。如果f的值域RfY时，则称函数f是映内的。如果x1,x2X,x1x2，则有fx1fx2,则称f是一对一的（单射）（即fx1=fx2时，有x1=x2）.如果f映上的，又是一对一的，则称f是一一对应的（或双射）。定义（复合运算）：若f:XY,g:YZ，则定义f和g的复合运算fg为：fg=x,z|存在yY,使y=fx,且z=gy即fgx=gfx.注：逆函数f-1若要存在需要满足以下条件：（1）函数

15、f是映上的（2）函数f必须是一对一的定义（恒等函数） 函数Ix=x,x|xX称为恒等函数。定理 f:XY,g:YZ，则g=f-1的充分必要条件是gf=Iy，并且fg=Ix3.2 运算定义（二目运算）： 若X是一个集合，f是从X×X到X的一个映射（函数），则称f为一个二目运算。一般地，若f是从Xn到X的一个映射（n是正整数），则称f是一个n目运算。运算的封闭：运算的结果总是集合X中的一个元，因此这个定义保证了运算的施行，这种情况又称为集合X对于该种运算是封闭的。定义（可交换）：若f:X×XX是一个运算，对于任何x,yX，都有fx,y=fy,x，则称运算f是可交换的（或者说，f

16、服从交换律）.定义（可结合）：若f:X×XX是一个运算，对于任何x,y,zX,都有ffx,y,z=fx,fy,z，则称运算f是可结合的（或者说，f服从结合律）.定义（可分配）：若f:X×XX是一个运算，g:X×XX是一个运算，对于任何x,y,zX，都有fx,gy,z=gfx,y,fx,z，则称运算f对于运算g是可分配的（或者说，f对于g服从分配律）定义（左单位元、右单位元）：设*是X上的一个运算，如果X中存在有一个元el，对于任何xX，有el*x=x，则称el是运算*的左单位元；如果X中存在有一个元er，对于任何xX，有x*er=x，则称er是运算*的右单位元。定

17、理 若*是X上的一个运算，el和er分别是它的左、右单位元，则el=er=e，并且e是唯一的（因此，称e为运算*的单位元）.定义（左零元、右零元）：设*是X上的一个运算，如果X中存在有一个元Ol，对于任何xX，有Ol*x=Ol，则称Ol是运算*的左零元；如果X中存在有一个元Or，对于任何xX，有x*Or=Or，则称Or是运算*的右零元.定义（等幂）：若*是X上的一个运算，aX，对于运算*，有a*a=a，则称元a对于运算*是等幂的。定义（左逆元、右逆元）：若*是X上的一个运算，它具有单位元e，对于任何一个aX,如果存在有元xlX，使xl*a=e，则称xl是a的左逆元；如果存在有元xrX，使a*x

18、l=e，则称xr是a的右逆元；定理 若*是X上的一个运算，它具有单位元e，并且是可结合的，则当元a可逆时，它的左、右逆元相等，并且唯一的（此时称之为a的逆元，并且记为a-1）.定义（可消去）：若*是X上的一个运算，对于任何x,yX，如果元a满足：a*x=a*y则x=y；或x*a=y*a则x=y，则称元a对于运算*是可消去的。第4章 无限集合4.1 基数定义（等势）： 若 A 和 B 是两个集合，如果在 A 和 B 之间可以建立一个一一对应关系，则称集合A和B等势，并记为AB。定理 令 是由若干个集合为元所组成的集合，则上定义的等势关系是一个等价关系。定义（有限集、无限集）：若 A是一个集合，它

19、和某个自然数集Mn=0,1,2,n等势，则称A是一有限集，不是有限集的集合称为无限集。定理 有限集的任何子集都是有限集定理 有限集不与其任何真子集等势定理 自然数集N=0,1,2,是无限集4.2 可列集定义（可列集）：若A是一个集合，它和所有自然数的集合N等势，则称A是一个可列集。可列集的基数用符号0表示。定理 若A是一个集合，A可列的充分必要条件是可以将它的元排列为a1,a2,an,的序列形式。定理 任何无限集必包含有可列子集。定理 可列集的子集是有限集或可列集（记为：0-n0）定理 若A是可列集，B是有限集，并且AB=，则AB是可列集（记为：0+n=0）.定理若A和B都是可列集，并且AB=

20、，则AB是可列集（记为：0+0=0）推论 设Aii=1,2,n都是可列集，则i=1nAi是可列集（记为：n0=0）定理 设Aii=1,2,n都是可列集，并且AiAj=ij,i,j=1,2,，则 i=1Ai是可列集（记为：00=0）推论设Aii=1,2,n都是可列集，则i=1Ai是可列集.定理 所有有理数的集合是可列集。4.3 不可列集定理 区间0,1中所有实数构成的集合是不可列的。定义（连续基数）： 开区间0,1中所有数组成集合的基数记为，具有基数的集合称为连续统，称为连续基数。推论：集合0,1的基数也是.定理 所有实数的集合是不可列的，它的基数是.定理 对于任何数a,b，若a<b，则区

21、间a,b,a,b,a,b,a,b)以及0,0,)都具有连续基数定理 一个无限集A和一个可列集作并集时，并集的基数等于集A 的基数。推论 一个无限集A和一个有限集的并集，其基数等于集 A 的基数。4.4 基数的比较定义（<） 设集合A的基数是=.如果A与B的真子集等势，而A和B不等势，则称A的基数小于B的基数，记为<.定理：A,B是两个集合，若A与B的某一子集等势，B与A的某一子集等势，则AB.定理：A,B是任意两个集合，A的基数为, B的基数为，则下列三个关系：=,<,>中必有一个且只有个成立。定理：若n是有限集A的基数，则n<0<.定理：若A是无限集合，则

22、0CardA定理：若A1,A2,An,是可列个互不相交的集合，它们的基数都是，则n=1An的基数是（记为：0=）定理：可列集的幂集，其基数是（记为：20=）定理：若A是一个集合，B=A是A的幂集，则CardA<CardB.此定理说明：不存在最大的基数。补充：2>, >第5章 形式语言5.1 文法和语言定义（产生式）： 一个产生式或重写规则是一个有序对U,x，通常写成Ux,其中，U是一个符号，而x是一个符号的非空有限串，U是这个产生式的左部，而x是产生式的右部.产生式将简称为规则。定义（非终极符号、字母表、终极符号、开始符号）：一个文法G是一个四元组VN,VT,P,S.其中，V

23、N是元语言的语法类或变元的集合，它生成语言的串，这些语法类或变元成为非终极符号，VT是符号的非空有穷集合，称为字母表，VT的符号称为终极符号. S是VN之一，是词汇表的一个识别元素，称为开始符号. P是产生式的集合。定义（直接产生、直接推导，直接规约）：设G是一个文法，如果V=xUy,w=xuy，而G中有规则Uu，就称串V直接产生串w，或称w是V直接推导出来的，或w直接规约到V,记为Vw.定义（产生、规约到、推导）：设G是一个文法，如果存在产生式序列P1,P2,Pnn>0,使得VP1P2Pn-1Pn，而Pn=w,就说V产生w（w规约到V,或w是V的推导），记为V+w.定义（句型）：令G是

24、一个文法，如果串x可从开始符号S推导出来，即如果S*x，则x称为一个句型。补充： 若=a,b，则*=,a,b,aa,ab,ba,bb,aaa,其中是空串，+=a,b,aa,ab,ba,bb,aaa,（不含空串）5.2 文法的类型定义（0-型文法）：在上的0-型文法由以下组成：（1） 不在中的不同符号的非空集合V,称为变量表，它包含一个纲符号S, S称为开始变量。（2） 产生式的有限集合。由G产生的所有字集称为由G产生的语言。定义（0-型语言）：在上可由某一0-型文法产生的字集称为0-型语言。定义（1-型文法）：如果在0-型文法中，对于P中的每个产生式，要求,则这文法称为1-型文法或上下文敏感文

25、法.定义（2-型文法）：设文法G=VN,VT,P,S,对于P中的每一个产生式有且VN（有的人要求），则此文法叫2-型文法或前后文无关文法。定义（3-型文法）：设G=VN,VT,P,S为一文法，又设P中的每一个产生式都是AaB或Aa，其中A和B都是变量，而a为终极符号，而此文法为3-型文法或正规文法。第1章 代数系统1.1 代数系统的实例和一般性质定义（代数系统）： 若X,是序偶，X是一个非空集合，是定义在X上的某些运算的非空集合，则称X,是一个代数系统，或称代数。代数系统的类型：（1） 代数系统X,1,2,m的类型是n1,n2,nm，其中1,2,m代表1,2,m目运算符。（2） X,1,2,3

26、，分别为0,1,2目运算符，则X,1,2,3的类型为0,1,2.1.2 同态和同构定义（同态象、同态映射）: X,1和Y,2是两个同类型的代数系统，映射g:XY, 1和2也构成一一对应.如果对于任意n目运算11，及其对应的运算22，当x1,x2,xnX时，都有g1x1,x2,xn=2gx1,gx2,gxn,则称代数Y,2是X,1的同态象，称g是从X,1到Y,2的一个同态映射。定义（同态象、同态映射）：若X,和Y,*是两个同类型的代数系统，和*都是二目运算，映射g:XY.如果对于任何x,yX,都有gxy=gx*gy，则称Y,*是X,的一个同态象，称g是从X,到Y,*的一个同态映射。注：如果Y,*

27、就是X,，则映射g是从X到它自身。当上述条件仍然满足时，我们就称g是X,的一个自同态映射。定义（同构、同构映射、自同构映射）：如果X,和Y,*是同态的，映射g:XY不仅是同态映射，而且是一一对应的，则称Y,*和X,同构，称g是从X,到Y,*的一个同构映射。如果Y,*就是X,，则称g是X,上的一个自同构映射定义（同余关系）：设Z,是一个代数系统，是Z上的一个等价关系，如果存在x1,x2,x3,x4Z,当x1,x2,x3,x4时，x1x3,x2x4成立，则称是Z,上的一个同余关系。定理：设是Z上的一个等价关系，如果存在同态映射g:Z,Y,*,使得当x1,x2Z时，x1x2当且仅当gx1=gx2，则

28、是Z,上的同余关系。1.3 商代数与积代数定义（子代数）：设Z,是一个代数系统，Z1Z在运算下封闭的，则称Z1,是Z,的一个子代数。定义1.3.2（直接积）：设Z,到Y,*是两个同类型的代数系统，如果对任意的x1,x2Z和y1,y2Y，定义运算于Z×Y:x1,y2x2,y2=x1x2,y1*y2，称Z×Y,是Z,和Y,*的直接积，称Z,和Y,*为Z×Y,的因子。第2章 半群和群2.1 半群和有幺半群定义（半群、有幺半群）：S是一个非空集合，如果S中定义了一个二目运算 ，对于任何a,b,cS,都有abc=abc，则称S , 是一个半群.如果半群S , 中具有单位元e

29、，使得对任何xS,都有ex=xe=x,则称S , 是一个有幺半群。（1）是一个由有限个符号组成的集合，其中的元称为字母。*表示所有的字构成的集合，+表示非空串组成的集合。（2）自由半群：半群的各元相互间没有任何关系。* , 说明：半群是一个定义了二目运算，并且服从结合律的代数系统。有幺半群则是具有单位元的半群。2.2 群和循环群定义2.2.1（群）：在代数系统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 , *是一个群。注

30、：对于群G , *来说，单位元e是唯一的，每个元a的逆元a-1也是唯一的。“存在逆元的有幺半群叫做群”定义（阶数）：若G , *是一个群，当G是有限集时，则称G中元的个数为群的阶数，记为G.定理2.2.1 若G , *是一个群，x,yG，则xy-1=y-1x-1，其中xy即x*y.定义（幂）：G , *是一个群，xG，则记r个x的积x*x*x为xr, xr称为x幂，x-1r记为x-r, x0表示单位元e。定理（指数律）：若m和n是整数，则xmxn=xm+n,xmn=xmn.定理 若xy=yx,则 xmyn=ynxm定义（次数）：若G,*是一个群，xG,使xn=e=x0的最小正整数n，称为元x的

31、次数。定理若G,*是一个群，xG，x的次数为n，则x0=e,x,x2,xn-1都是G中不同的元。定义（循环群、生成元）：由一个单独元素a的一切幂所组成的群称为循环群，a称为这个群的生成元。定理 在阶数为n的循环群，由生成元x所产生的元xr次数为n，即xr是生成元的充分必要条件是r和n互质。定理 若r和n不是互质的，则xr的次数是l/r，其中的l是r和n的最小公倍数。定义（阿贝尔群）： 如果群G,*中的元对于运算*满足交换律，则称这个群是一个阿贝尔群。“满足交换律的群叫做阿贝尔群”循环群是一个阿贝尔群。定理 若A, 和B, *都是有限的阿贝尔群，定义A×B=a,b|aA,bBa1,b1

32、+a2,b2=a1a2,b1*b1则A×B,+是一个阿贝尔群。最简单的一个阿贝尔群是B2群0,1, 为按位加2.3 二面体群、置换群二面体群是从图形的变换中到处，这些图形都是比较正规的图形。定理 ab=ban-1.更一般地讲，arb=ban-r定义2.3.1（置换）：若S是一个非空的有限集合，则S上任何一个到它自身的一一对应的映射，都称为S上的置换。定理 两个置换的乘积仍是一个置换，并且置换的乘积服从结合律。S的恒等映射也是一个置换称为单位置换。S上所有置换的集合，对于置换乘法构成一个群，这个群称为对称群，记为Sn, n是S中元的个数。定义（n阶置换群）若S是非空有限集合，G是S上的

33、n个置换所构成的群，则称G是一个n阶置换群。定理 任何一个（n阶）群都同构于一个（n阶）置换群。2.4 子群、群的同态定义（子群）： G,*是一个群，SG,如果（1）单位元eS（2）若aS，则a的逆元a-1S（3）若a,bS,则a*bS则称S,*是G,*的一个子群。定理 G,*是一个群，SG，S,*是一个子群的充分必要条件是：若a,bS,则a*b-1S定义（同态象、群同态映射）：G,*和H,*是群，g:GH.若对任何a,bG,有ga*b=gagb群的同态映射具有下列性质：（1）将单位元映射为单位元（2）将逆元映射为逆元（3）对运算封闭，即对任何a,bG，有gagb=ga*b定理 若G,*和H,

34、*是群，g:GH是一个群同态映射，则g将G,*的子群映射为H,的子群。定义（同态核）：若g:GH是一个群同态映射，eH是H的单位元，则G中所有满足ga=eH的元a的集合，称为同态核，记为Kerg.定理 同态核是一个子群。定理 若H,*是群G,*的子群，则H定义了G上的一个划分（因而也定义了G上一个等价关系）.群子集：假定A,B都是群G,*中的元构成的集合（称之为群子集），定义AB=a*b|aA,bB特别地，当A是一元集a时，我们简记AB为aB,则aB=a*b|bB定理若A,*是群B,*的子群都是群G,*的子群，则AB,*是一个群的充分必要条件是AB=BA.2.5 陪集、正规子群、商群定义（左陪

35、集）：若H,*是群G,*的子群，对于aG,称aH=a*h|hH称为H的一个左陪集.定理若H,*是群G,*的子群，则H的所有左陪集构成G的一个划分。定理（拉格朗日定理）每个左陪集的元和H中的元都是一样多。推论2.5.1 子群中元的个数一定是群中元的个数的因子。定义（正规子群）：若H,*是群G,*的子群，对于任何aG,都满足aH=Ha,则称H,*是群G,*的一个正规子群.一个阿贝尔群的任何子群都是正规子群。当H,*是群G,*的正规子群时，对于H关于G的陪集.定义运算 为aHbH=a*bH考虑所有H关于G的陪集组成的集合aH|aG和运算 构成的系统aH, 为一个群。这个群称为G关于H的商群，记为G/

36、H.定理 若g:GH是从群G,*到群H,的映上的同态映射，则核N是正规子群，商群G/N同构于N.群同态基本定理：商群G/N是由陪集aN构成的群，也是同余类的集aN构成的群，所以它同构于象代数，即G/N同构于H.如果群没有真正的正规子群，则该群为单群。正规群的任何子群都是正规子群。第3章 格和布尔代数3.1 格定义（格）：L,表示一个偏序集，如果对于L中的任何两个元a和b,在L中都存在一个元是它们的上确界，存在一个元是它们的下确界，则称L,是一个格。对于L中的元a,b，它们的上确界常常记为ab，它们的下确界常常记为a*b,前者又称为a和b析取或和（ab或a+b），后者又称为a和b的合取或积（ab

37、或ab或ab）。定理3.1.1 若L,是一个格，则对于任何a,bL，有（1） ab的充分必要条件是a*b=a.（2） ab的充分必要条件是ab=b.定理（保序性）若L,是一个格，则对于任何a,b,cL，当bc时，有a*ba*c,ab<ac引理若L,是一个格， a,b,cL,ab,ac，则ab*c定理（分配不等式）：若L,是一个格，则对于任何a,b,cL，ab*cab*aca*bca*ba*c定理（模数不等式）若L,是一个格，则对于任何a,b,cL，ac的充分必要条件是ab*cab*c定理3.1.5 若S,*是一个代数系统，和*是S上的二目运算，它服从交换律、结合律和吸收律.则S,*是一个

38、格.定义（子格） L,*是一个格，SL，当且仅当S对于运算和*是封闭的，运算结果和在L中相同时，则称代数系统S,*是L的一个子格。定义（直接积） 若L,*和S, , 是两个格，则L×S,+, 称为这两个格的直接积，其中的运算+和定义为：对于任何的a1,b1,a2,b2L×S,a1,b1a2,b2=a1*a2,b1b2a1,b1+a2,b2=a1a2,b1b2定义（同态映射）设L,*和S, , 是两个格，g:LS.如果对任何a,bL，有ga*b=gagb,gab=gagb则称g是L,*到S, , 的一个同态映射.特别地，当g是一个一一对应时，称g是一个同构映射，并且称格L,*

39、和S, , 同构的。如果g:LL是格L,*上一个同态映射，则称g是一个自同态映射.如果g:LL是一个同构映射，则称g是一个自同构映射.定义（完备）： 对于一个格，如果它的每一个非空子集在格中都具有一个上确界和下确界，则这个格称为完备的。显然每个有限的格都是完备的。对于一个格，它的上确界和下确界如果存在，我们称它们为这个格的边界，并分别记为1和0，因此有时这种格称为有界格。定义（补元）：L,*,0,1是一个有界格，aL，如果存在元bL,使a*b=0且ab=1，则称b为a的补元。定义（补格）：L,*,0,1中的每个元都至少具有一个补元，则称这个格是一个补格。定义（分配格）：L,*是一个格，如果对任

40、何a,bL，有a*bc=a*ba*c ab*c=ab*ac 则称L,*是一个分配格。定理 任何两个分配格的直接积是分配格。定理 若L,*是一个分配格，则对于任何a,b,cL,如果a*b=a*c，并且ab=ac,则b=c推论3.1.2 如果一个格是分配格，同时又是补格，则它的每一个元都具有唯一的一个补元。3.2 布尔代数定义（布尔代数） 一个既是补格，又是分配格的格，称为布尔代数。定义（对偶命题） 如果B,',0,1是一个布尔代数，P是关于B中变元的一个命题，它可以由B中变元元通过运算,',0,1来表示.如果对P的表示式进行下列代换：代换为；代换为；1代换0；0代换为1，则这样代

41、换后也将得到一个命题Pd,它成为命题P的对偶命题，简称为对偶。定理（对偶原理）如果P是一个命题，它在任何一个布尔代数中都成立，并且可以由运算,',0,1来表示，则对它的对偶命题Pd也在任何一个布尔代数中成立。定理*（对偶原理）如果P是一个命题，它在任何一个布尔代数中都成立，并且可以由运算,',0,1和关系,来表示，则将P中的运算代换为；代换为；0代换为1，1代换0；换为，换为，所得到的对偶命题也在任何一个布尔代数中成立。定理 若B和B0是两个布尔代数，h:BB0是一个同态映射，则B在h中的同态象hB是B0的一个子布尔代数。定义（基元）：B,',0,1是一个布尔代数，aB

42、,a0,如果B中不存在元x,使0<x<a,则称a是B的一个基元。如果对于任何bB,b0都存在有基元ab,则称这个布尔代数是基元的。定理 若B,',0,1是一个布尔代数，aB,a0,则下列命题是等价的。（1）a是一个基元（2）对于所有的xB,若xa,则x=0或x=a（3）对于所有的xB，ax=a, ax0, other推论3.2.1 若a和b是不同的基元，ab=0定理 B,',0,1是一个基元的布尔代数，A是其基元的集合，对任一xB,令x=a|aA,ax,则x=axa,并且作为基元的析取式，这个表达式是唯一的。定理 若B,',0,1是一个非空有限的布尔代数，A

43、是它的所有基元构成的集合，则B,',0,1同构A,',A.推论3.2.2 一个有限的布尔代数具有2n个元，其中的n是它的基元的个数。推论3.2.3 对于任意正整数n,具有2n个元的布尔代数是同构的。3.3 其他代数系统定义（环）3.3.1 若代数系统R,+, 满足下列条件：（1）R对于二目运算+是一个可交换的加法群。（2）R对于二目运算 （即乘法）是封闭的。（3）乘法结合律成立，即对R中任何三个元a,b和c,有abc=abc（4）分配律成立，即对R中任何元a,b和c，有abc=ab+acb+ca=ba+ca则称R,+, 是一个环。定义（交换环） 一个环R中的任何两个元a,b,如

44、果都满足ab=ba,则称R是一个交换环。定义3.3.3 （逆元、零元）一个环R中如果存在有元e,使得对R中任何一个元都有ea=ae=a,则称e是R的一个单位元。定义（逆元、零元） 在一个有单位元的环里，如果a和b是环中的元，满足ab=ba=1,则称b是a的逆元。对任意aR,若0a=a0=0,则称0是R的零元。环的零元通常用0表示。定义3.3.7（域）：一个可交换的除环称为一个域。定义（子环）：一个环R的一个子集S本身对R的代数运算也构成一个环，则称S为R的子环。定义（理想子环，理想）：若I是环R的一个非空子集，满足（1）a,bIa-bI（2）aI,rRra,arI则称I是R的一个理想子环，简称

45、理想。第4章 群码4.1 通信模型和错误校正的基本概念4.2 二进制编码定义（海明距离） 设x,yBn,x与y之间的海明距离是xy的权xy，用Hx,y表示。定理 设x,y,zBn,则（1） Hx,y=Hy,x（2） Hx,y0（3） Hx,y=0当且仅当x=y（4） Hx,yHx,z+Hz,y定义（码字）：码字是n元组的码的最小距离，是该码中所有码字之间的海明距离的最小值。定理 当且仅当一个编码的任意两个码字之间的最小距离至少k+1时，能够检查出k个或至少k个错误的所有组合。定理 当且仅当任意两个码字之间的距离至少是2k+1时，这中编码就能够纠正k个或少于k个错误的组合。定义（群码） 设Bm,

46、和Bn,是群，函数e:BmBn,使得eBm=eb|bBm是Bn的子群，则称e是编码函数. eBm是群码。定理 一个群码的非零码字的最小权等于它的最小距离。定义4.2.4 设A=aijm×n,B=bijm×n,C=cijm×n,C=AB,其中cij=aijbij,1im,1jm.定义（布尔矩阵）： 设D=dijm×r,E=eijr×n是布尔矩阵，布尔矩阵的积F=D*E=fijm×n是布尔矩阵，其中fij=di1e1j+di2d2j+dirdr1.定理 设m和n是非负整数，且m<n,r=n-m,并设H是n×r布尔矩阵，则函

47、数fH:BnBr,fHx=x*H,xBn是从群Bn到Br的同态映射。推论4.2.1 设m和n是非负整数，且m<n,r=n-m,并设H是n×r布尔矩阵，函数fH:BnBr,fHx=x*H,xBn使得N=x|xBn,x*H=O是正规子群。定理 设x=y1y2ymx1xrBn,则x*H=O当且仅当某bBm,x=eHb.推论4.2.1 eHBm=eb|bBm是Bn的一个子群。4.3 解码和错误校正定义（解码函数）：若d:BnBm是映上函数，如果dxi=b'Bm,使得当传送通道没有噪声时，b=b',则称d是与e对应的n,m解码函数。定义（k级校正） 设e是一个m,n编码函

48、数，d是与e对应的解码函数，如果x=eb是正确传送或具有k级错误，则称e,d是k级校正。定理 假设e是m,n编码函数，d是对应的最大似然译码函数，则e,d能够校正k级错误，当且仅当e的最小距离至少是2k+1.定义（陪集头）xl的左陪集中，具有最小权的元素称为陪集头。定理 如果m.n,r,H和fH定义如前，则fH是映上的。定理 设x和y是Bn的元素，则x和y处于N的同一左陪集，当且仅当fHx=fHy,即当且仅当它们有相同的并发错。第1章 命题演算1.1 命题和逻辑连接词定义（命题）： 如果有一个陈述语句，它可以取值：“真”或“假”，并且只能取其中一个值，这样的陈述语句就成为一个命题。5中基本逻辑

49、连接词：（1）¬：否定词：“非A”（2）：合取词：“A并且B”（3）：析取词：“A或者B”（4）：蕴涵词：“若A则 B”（5）：等值词：“A等值于B”1.2 合式公式能成为命题的式子称为合式公式，简记为wff。定义（合式公式）：（1）一个命题变元是wff.（2）若P是一个wff,则¬P是一个wff.（3）若P和Q是wff,则PQ,PQ,PQ和PQ都是wff（4）wff只限于有限次使用（1）（2）（3）所得到的符号串。定义（部分合式公式） 如果A和B都是wff, B是A的一部分，则称B是A的部分合式公式或子公式，部分合式公式简记为wfp.结论：在A,B都是wff,且A是符号串

50、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.3 真值表、永真式定义（永真式、重言式、有效） 对于一个wff的命题变元无论作何指派，所得到的值永为T,即命题永远是真命题，则称该wff为永真式或重言式，并称它是有效的。定义（永假公式、不可满足公式） 对于一个wff的命题变元无论作何指派，

51、所得到的值永为F,即命题永远是假命题，则称该wff为永假公式或不可满足公式。定义（可满足公式） 不是永真式的wff称为非永真公式。不是永假公式的wff称为可满足公式。定理 永真公式的合取式或析取式仍然是永真公式。定理 在一个永真公式中，对某个变元用同一个wff置换，其结果仍然为永真公式。定理 若A和B都是wff,AB的充要条件是AB是一个永真式。定理 一个wff的永真式、永假性、非永真性和可满足性是可判定的。1.4 命题演算的等价关系定理（代换定理）若A是一个wff，A1是它的一个wfp,A1B1,在将A中各处出现的A1中的一个或若干个代换B1时，如果得到的wff为B,则A=B.1.5 逻辑连

52、接词的可省略性如果能找到一个更小的逻辑连接词的集合，用它们也能完成上述五个连接词的全部功能，则我们把这种连接词的集合称为连接词的功能完全集。功能完全集：¬,、¬,、¬,、：读为“与非”（2）读为“或非”¬PPPPPPQPPQQPPQQ1.6 范式定义（初等积）：命题变元和它们的否定的合取式称为初等积。定义（初等和）：命题变元和它们的否定的析取式称为初等和。定义（析取范式）：如果一个wff具有形式A1A2Ann1而每个Ai都是初等积，则它称为析取范式。定义（合取范式）：如果一个wff具有形式A1A2Ann1而每个Ai都是初等和，则它称为合取范式。定义1.6

53、.5 （最小项）：在初等积中，每个命题变元和它的否定不能同时出现，但两者中必须出现一个，而且只能出现一次，这样的初等积称为最小项。定义（标准析取范式）：对于一个wff，仅由它的最小项的析取组成的等价公式称为它的标准析取范式。定理 在真值表中，一个wff的真值为T的指派所对应的最小项的析取式，即为此wff的标准析取范式。“真值为T的并集，变元取正”定义（最大项）：在初等和中，每个命题变元和它的否定不能同时出现，但两者中必须出现一个，而且只能出现一次，这样的初等和称为最大项。定义（标准合取范式）：对于一个wff,仅由它的最大项的合取组成的等价公式称为它的标准合取范式。定理 一个wff的真值为F的指

54、派所对应的最大项的合取式，即为此的标准合取范式。“真值为F的交集，变元取反”1.7 推理和证明方法定义（逻辑前提、有效结论）：A1,A2,An和A都是wff,如果对于A1A2An取值1的任何代入，A也一定取值1，则称A1,A2,An是A的逻辑前提，A是A1,A2,An的有效结论，并记为A1,A2,AnA.定理：A1,A2,AnA的充分必要条件是A1,A2,AnA为永真公式。判断命题是否是有效结论的方法：（1）真值表法（2）直接证法l P规则：在推导的任一步都可以引用任一前提l T规则：如果公式S在前面的推导中已经提到，则S可以在以后的推导过程中引用，否则不得引用。l CP规则：若结论形如BA,则B可作为前提，与前提P一起推出A,即P,BA等价PBA永真.即PBA可改写成P,BA.（3）反证法定义（相容、不相容）：若A1,A2,An是一组wff, P1,P2,Pm是它们中出现的全部命题变元，在对 P1,P2,Pm的各组真值指派中，至少有一组使A1A2An的取值为1，则称A1A2An是相容的. 如果对于P1,P2,Pm的任何真值指派A1A2An都取值0，则称A1,A2,An是不相容的.定理 若A1,A2,An和A是wff，则A1,A2