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

【半群】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。共有j(n)个。【三次对称群】{I(12)(13)(23)(123)(132)}【陪集】a,b∈G,若有h∈H,使得a=bh,则称a合同于b(右模H),a≡b(右modH)。H有限,则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。求右陪集:H本身是一个;任取aÏH而求aH又得到一个;任取bÏH∪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的正规子群。5H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合,则HN是G的子群。【同态映射】K是乘法系统,G到K的一个映射σ(ab)=σ(a)σ(b)。设(G,*),(K,+)是两个群,令σ:x®e,"xÎG,其中e是K的单位元。则σ是G到K内的映射,且对a,bÎG,有σ(a*b)=e=σ(a)+σ(b)。即,σ是G到K的同态映射,G~σ(G)。σ(G)={e}是K的一个子群。这个同态映射是任意两个群之间都有的。【同构映射】K是乘法系统,σ是G到σ(G)上的1-1映射。称G与σ(G)同构,******@G′。同构的群或代数系统,抽象地来看可以说毫无差别。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适