【离散数学】知识点及典型例题整理.doc

.【半群】G非空，为G上的二元代数运算，满足结合律。【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1a=a1=a,恰有一个元素a-1适合aa-1=a-1a=1。【Abel群/交换群】适合交换律。可能不只有两个元素适合x2=1【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。【子群】按照G中的乘法运算,子集H仍是一个群。单位子群1和G称为平凡子群。【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，1，2， 做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有j（n）个。【三次对称群】I（12）（13）（23）（123）（132）【陪集】a，bG，若有hH，使得a =bh，则称a合同于b（右模H），ab（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取aH而求aH又得到一个；任取bHaH而求bH又一个。G=HaHbH【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意gG都成立） Lagrange定理 G为有限群，则任意子群H的元数整除群G的元数。1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。2设G为有限群,元数为n,对任意aG，有an=1。3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。【同态映射】K是乘法系统，G到K的一个映射（ab）=（a）（b）。设（G，*），（K，+）是两个群，令：xe，xG，其中e是K的单位元。则是G到K内的映射，且对a，bG，有（a*b）=e=（a）+ （b）。即，是G到K的同态映射，G（G）。（G）=e是K的一个子群。这个同态映射是任意两个群之间都有的。【同构映射】K是乘法系统，是G到（G）上的1-1映射。称G与（G）同构，GG。同构的群或代数系统，抽象地来看可以说毫无差别。G和G同态，则可以说G是G的一个缩影。【同态核】是G到G上的同态映射，核N为G中所有变成G中1的元素g的集合，即N=-1（1）=gG（g）=1。N是G的一个正规子群。对于G的任意元素a，-1(a)=x|xG ,(x)= a是N在G中的一个陪集。G的元素和N在G中的陪集一一对应。设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。;.【环】R非空，有加、乘两种运算a+b=b+a2）a+（b+c）=（a+b）+c，3）R中有一个元素0，适合a+0=a，4）对于R中任意a,有-a,适合a+(-a)=0，5）a（bc）=（ab）c，6）a（b+c）=ab+ac,（a+b）c=ac+bc。交换环：乘法适合交换律 ab=ba 。含壹环：R不只有一个元素且有一个元素1适合1a =a1=a。1不为零。无零因子环：不含 a，bR，a0，b0,但ab=0，a，b为零因子。又叫消去环。消去环： 消去律成立。不为0的元素在加法下的周期或为0或为质数。整区：有壹无零因子的交换环。体：如果去掉0，环R的其余元素作成一个乘法群。体有壹而且无零因子，其中任意非零元素有逆。域是交换体。 单纯环：R除自己和0外没有别的理想。【子环】环R的非空子集S在R的加法和乘法下仍是环。若aS，bS，则a-bS;若aS，bS，则abS。 对于乘法群，其壹恒与子群的壹一致；但对于环，其壹却未必与子环的壹一致。 【理想】环R的子集N (理想子环)N非空；若aN，bN，则a-bN;若aN,R,则aN,aN。1理想一定是子环，但子环未必是理想。2任意体R只有平凡理想。3设R是有壹的交换环,aR,则aR=ar|rR是R的理想，且包含a。【主理想（a）】R是有壹的交换环，aR,则aR称为由a生成的。(0)=0,(1)=R。 环R的主理想（a）是R中包含a的理想中最小的理想。【合同】设R是环，N是理想。a，bR，如果a-b=nN，或a=b+n，nN，则称a和b模N合同，记为ab（mod N）。在环R中，对于模N，有：反身性：aa;对称性：若ab， 则ba;传递性：若ab，bc，则ac;加法同态性：若ab，cd，则acbd。乘法同态性：若ab，cd，则acbd。【环同态】R是环，S有加乘两种运算，R到S中的一个映射（a+b）=（a）+（b），（ab）=（a）（b）。R到R同态，记为RR。【环同构】是环R到系统R上的一个一对一的同态映射。R与R同构,记为RR。若是R到S中的一个同态映射,则R的映象R=（R）也是一个环,（0）就是R的零0,(-a)=-（a）。若R有壹而R不只有一个元素,则R有壹而且（1）就是R的壹1;若aR有逆,则（a）在R中有逆而且(a-1)就是(a)-1。【理想】同态映射的核N是R的一个.设a是R的任意元素,则a的逆映象-1(a)=aR(a)=a是N的一个剩余类。1按照剩余类的加法和乘法，R对于理想N的所有剩余类的集合RN是一个环，2规定（a）= a+N，则是R到RN上的一个同态映射，其核为N。RN叫做R对于N的剩余环3设环R同态于R： RR于是R与N之间的子环与R的子环一一对应，大环对应大环，小环对应小环，理想对应理想。【极大理想】N R，而R与N之间没有别的理想。极大理想不唯一若N R，则N是R的极大理想必要而且只要RN是单纯环。【域】任意有壹的交换的单纯环。任意域F是有壹的交换的单纯环。设R是有壹的交换环，N是R的理想。于是，RN是一个域，必要而且只要N是一个极大理想。 任意域F的特征P是零或一质数。【最小域/素域】没有真子域的域，特征P的最小域为R (p为0或质数)。设p为质数或等于0，特征为p的任意域F包含Rp为其最小子域。域F上的多项式作成的环F是一个【整区】。【多项式】 1以-除()所得的余式等于（）。 2 -(),当且仅当是()的根。 3说是非0多项式（）的k重根，如果（-）k（），（-）k+1不整除（）。 4若是非常数多项式（）的k重根，则它至少是（）的k-1重根。5是（）的重根，当且仅当它是（）和（）的公共根。6复数域上任意非常数多项式必有根。7实数域上，质式只能是一次式或二次式。二次式a2+bx+c是质式，当且仅当判别式b2-4ac0。设（）= a0n + a1n-1 + an 是整系数多项式，若对质数p，p不整除a0，pa1，pan，p2不整除an，则（）在有理域上【不可约】。设 （）= a0n + a1n-1 + + an 是整系数多项式。若有理数bc是（）的根，其中b和c是互质的整数，则ban，ca0。【求有理根】1.分别找a0和an的所有因子ci,bj;2.找互质对（ ci,bj ）；3.判断ci/bj是否为根；4.判断重根。复数称为一个代数数，如果是某个有理系数非0多项式的根。若不是任何有理系数非0多项式的根，则称为一个超越数。复数域中恰有n个n次单位根。它们在乘法下作成一个n元循环群1（）=-1 2（）=+13（）=2+ x + 14（）= x2 + 112-1=1264321， 6-1= 6321 相除得6+1 = 124 设n不是F的特征的倍数，并设n（）在F中有根。于是，F中恰有n个n次单位根，它们在乘法下作成一个n元循环群，其j（n）个生成元素恰是n（）的所有的根。F中的q-1个非0元素恰是所有q-1次单位根，而F的所有q个元素是多项式q-的所有的根。F的q-1个非0元素在乘法下作成一个q-1元循环群，其j（q-1）个生成元素恰是q-1（）的所有的根。【有限域】的元数必为pn的形式，其中p为其特征。如果同构的域看作是一样的，则对任意q=pn恰有一个q元有限域，【格】部份序集(L，），对于任意a，bL，L的子集a，b在L中都有一个最大下界（记为infa，b）和一个最小上界(记为supa，b)。一个序集是一个格，但是，不是所有部份序集都是。设（L，）是格,S是L的子集,即SL，如果（S，）是格，则称（S，）是格（L，）的【子格】。设L是一个集合, 是L上两个二元代数运算，如果这两种运算对于L中元素满足：（1）交换律：ab=ba， a b=b a。（2）结合律： a（bc）=（ab）c， a （b c）=（a b）c。（3）吸收律：a(a b)=a,a (ab)=a。则称此代数系统（L,）为一个【格】。集合L中的【部份序关系】R与其逆关系R-1,称为互相对偶的两个关系。对任意x，yL， xR-1yyRx。若R是部分序关系，则R-1也是。【格同态】（L， ）和（S，）是个格，L到S的映射g对任意a，bL，有g（ab）= g（a）g（b）g（ab）= g（a）g（b）若g是L到S上的同态映射，且是一对一的，则称g是格【同构映射】。【有界格】格（L，）有一个最大元素(记为1)和一个最小元素(记为0)，亦即，对任意aL，都有0a1，0，1称为格（L，）的界。在有界格(L,0,1)中，一个元素bL,称为元素aL的【余元素】,如果ab = 0， a b = 1。在有界格（L,0,1）中，任意元素a可以有余元素，也可以没有余元素；如果有余元素，则可以有一个或一个以上的余元素。有界格（L,0,1）说是一个【有余格】，如果对L中每一个元素，都至少有一个余元素。格（L，）称为【分配格】，如果对任意a，b，cL，恒有a（bc）=（ab）（ac），a （bc）=（ab）（ac）设格（L， ）是一个有余分配格，则对任意aL，a的余元素a是唯一的。设（L，）是一个格，对任意a，b，cL，如果ab，都有a（bc）= b（ac）则称（L，）为【模格】。任意一个分配格都是模格，但模格不一定是分配格。对任意a，b，cL，如果ab，ac=bc，ac=bc,则必有a=b。一个有余分配格是一个布尔代数。【布尔代数】设B是一个至少含有两个不同元素的集合，+是定义在B上的两种代数运算，如果对任意a，b，cB，满足下面公理： H1： ab = ba，a+b = b+a H2： a（b+c）=（ab）+（ac）， a+（bc）=（a+b）（a+c）。 H3： B中有元素 0和元素1,使得对任意aB,有 a1 = a， a+0 = a。 H4： 对任意aB，有B，使得a=0， a+ =1。 则（B，+，0，1）是一个布尔代数。 有限布尔代数的基底必是此代数的所有极小元素；反之，此代数的所有极小元素必然做成此代数的基底。举例说明不要求可除条件而要求消去条件，即要求由a=ay可推出=y，由a=ya可推出=y，则G不见得是一个群，若G有限怎么样？ 解：例如，全体自然数在普通乘法下，适合消去律，但不是群。若G=a1，a2，an，用a右乘G中各元素得a1a，a2a，ana必不相同，否则若aia=aja (ij) ，由消去条件有ai=aj，矛盾。对任意bG，必有ai，使aia=b，因之方程xa=b有解。同理可知ay=b有解。故G是群。设K和H都是群G的子群，试证明：若HK是G的子群，则KH = HK。证明：对任意的khKH,(kh)-1=h-1k-1HK,由于HK是G的子群,所以(kh)-1)-1HK，因此KH HK。对于任意的hkHK，(hk)-1HK，即存在h1H，k1K使得(hk)-1=h1k1，所以hk=(h1k1)-1=k1-1 h1-1 KH，因此HK KH。由集合论知识知KH = HK。 任意置换恰有一法写成不相杂的轮换乘积。证明：先证可以写成不相杂的轮换的乘积，取任意a1M。（1）若（a1）= a1,则a1自己就作成一个轮换。（2）设(a1)= a2,(a2)= a3，。这样下去，由于M有限，故到某一个元素ar,其（ar）必然不能再是新的元素，即这（ar）必在a1，ar之内。由于是一对一的,我们已有(ai)= ai+1，i=1，2， ，r-1，所以(ar)只能是a1。于是我们得到一个轮换（a1ar）。若M已经没有另外的元素，则就等于这个轮换，否则设b1不在a1，ar之内，则同样作法又可得到一个轮换（b1bs）。因为a1，ar各自已有变到它的元素，所以b1，bs中不会有a1，ar出现，即这两个轮换不相杂。若M的元素已尽，则就等于这两个轮换的乘积，否则如上又可得到一个轮换。如此类推，由于M有限，最后必得=( a1ar)(b1bs)(c1ct) （1）即表成了不相杂的轮换的乘积。 证明f（x） = 3x5+7x2+5在有理域R0上不可约。证明：本例不能使用Eisenstein定则。因为，若f（x）在R0上可约，3不是2的倍数，则f（x）在R2上可约。因此，只需证明f（x） 在R2上不可约，则可知f（x）在R0上不可约。而在R2上， f（x） = x5+x2+1。（1）证明无一次因式。 由R2=0，1，f（0）=f（1）=1知， f （x） 在R2上无根，即无一次因式。 （2）证明无二次因式。 在R2上二次因式只有： x2， x2+1， x2+x， x2