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

【半群】G非空，·为G上的二元代数运算，满足结合律。【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=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。共有（n）个。【三次对称群】{I（12）（13）（23）（123）（132）}【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。求右陪集：H本身是一个；任取aH而求aH又得到一个；任取bH∪aH而求bH又一个。G=H∪aH∪bH∪…【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立）Lagrange定理 G为有限群，则任意子群H的元数整除群G的元数。1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。2设G为有限群,元数为n,对任意a∈G，有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′）={g∈G∣σ（g）=1′}。N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(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，a≠0，b≠0,但ab=0，a，b为零因子。又叫消去环。消去环：消去律成立。不为0的元素在加法下的周期或为0或为质数。整区：有壹无零因子的交换环。体：如果去掉0，环R的其余元素作成一个乘法群。体有壹而且无零因子，其中任意非零元素有逆。域是交换体。单纯环：R除自己和{0}外没有别的理想。【子环】环R的非空子集S在R的加法和乘法下仍是环。若a∈S，b∈S，则a-b∈S;若a∈S，b∈S，则ab∈S。对于乘法群，其壹恒与子群的壹一致；但对于环，其壹却未必与子环的壹一致。【理想】环R的子集N(理想子环)N非空；若a∈N，b∈N，则a-b∈N;若a∈N,х∈R,则aх∈N,хa∈N。1理想一定是子环，但子环未必是理想。2任意体R只有平凡理想。3设R是有壹的交换环,a∈R,则aR={ar|r∈R}是R的理想，且包含a。【主理想（a）】R是有壹的交换环，a∈R,则aR称为由a生成的。(0)={0},(1)=R。环R的主理想（a）是R中包含a的理想中最小的理想。【合同】设R是环，N是理想。a，b∈R，如果a-b=n∈N，或a=b+n，n∈N，则称a和b模N合同，记为a≡b（mod N）。在环R中，对于模N，有：反身性：a≡a;对称性：若a≡b，则b≡a;传递性：若a≡b，b≡c，则a≡c;加法同态性：若a≡b，c≡d，则a±c≡b±d