离散数学知识点

说明：

定义：红色表示。定理性质：橙色表示。公式：蓝色表示。算法:绿色表示页码：灰色表示数理逻辑：，，，，)，合式公式，子公式赋值，求值函数，真值表，等值式，重言式，矛盾式范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式真值函数，异或，条件否定，与非，或非，联结词完备集CP谓词，个体词，论域，全称量词，存在量词项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入解释，赋值，有效的，可满足的，不可满足的前束范式推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)，+规则(EG),推理集合论：,domRranR自反的,反自反的,对称的,反对称的,传递的,自反闭包r(R),对称闭包s(R),传递闭包t(R)/下界/代数结构：代数系统，子代数，积代数，同态，同构。群与子群：半群,子半群,元素的幂，独异点，群，群的阶数，子群 ,平凡子群，陪集，拉格朗日（Lagrange）定理环，交换环，含幺环，整环，域格与布尔代数：定理图论：图的基本概念：图的同构图的连通性:通路，回路，简单通路，简单回路（迹）初级通路（路径），初级回路（圈），连通图，点割集，割点，边割集，割边，点连通度，边连通度，弱连通图，单向连通图，强连通图，二部图（二分图）关联矩阵，邻接矩阵，可达矩阵欧拉图与哈密顿图：图、半哈密顿图根树，m叉树，最优二叉树，Huffman算法平面图:命题：具有确定真值的陈述句。

数理逻辑：否定词符号：设p是一个命题，p称为p的否定式。p是真的当且仅当p是假的。p是真的当且仅当p是假的。【定义1.1】合取词符号：设p，q是两个命题，命题“p并且q”称为p，q的合取，记以pq，读作p且q。pq是真的当且仅当p和q都是真的。【定义1.2】析取词符号：设p，q是两个命题，命题“p或者q”称为p，q的析取，记以pq，读作p或q。pq是真的当且仅当p，q中至少有一个是真的。【定义1.3】蕴含词符号：设p，q是两个命题，命题“如果p，则q”称为p蕴含q，记以pq。pq是假的当且仅当p是真的而q是假的。【定义1.4】等价词符号：设p，q是两个命题，命题“p当且仅当q”称为p等价q，记以pq。pq是真的当且仅当p，q或者都是真的，或者都是假的。【定义1.5】合式公式:命题常元和变元符号是合式公式；AA)是合式公式，称为AA，BABABAB)，(AB)是合式公式；所有合式公式都是有限次使用(1)，(2)，(3)、(4)得到的符号串。子公式:如果Ｘ是合式公式A的一部分，且Ｘ本身也是一个合式公式，则称Ｘ为公式A的子公式。【定义1.6】赋值（指派，解释）：设是命题变元集合，则称函数v：{1，0}是一个真值赋值。【定义1.8】真值表：公式A在其所有可能的赋值下所取真值的表，称为A的真值表。【定义1.9】重言式（永真式）:任意赋值v，v A矛盾式（永假式）:任意赋值v，有v A【定义1.10】等值式：若等价式AB是重言式，则称A与B等值，记作AB。【定义2.1】基本等值式双重否定律 AA幂等律 AAA,AAA交换律 ABBA,ABBA结合律 (AB)CA(BC),(AB)CA(BC)分配律 A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律 (AB)AB ,(AB)AB吸收律 A(AB)A,A(AB)A零律 A ,同一律 AA,A 排中律 AA 矛盾律 AA蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式ABAB归谬论 (AB)(AB)A置换规则：AYAＸ（X）YB，则AB。文字:A（命题变元集）,则A和AA【定义2.2】析取范式：形如AA1 2

…An

(n1A(i=1,…,n)是由文字组成的合取范式。i合取范式：形为AA1 2

…An

(n1) 的公式称为合取范式，其中A,…,A1 n

都是由文字组成的析取式。【定义2.3】极小项：文字的合取式称为极小项，其中公式中每个命题符号的文字都在该合取式中出现一次。极大项：文字的析取式称为极大项，其中公式中每个命题符号的文字都在该合取式中出现一次。【定义2.4】主析取范式：主合取范式：【定义2.5】公式的真值表中真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。真值函数：称F:{0,1}n{0,1}为n元真值函数.【定义2.6】联结词的完备集：设C是联结词的集合，若对于任意一个合式公式均存在一个与之等价的公式，而后者只含有C中的联结词，则称C是联结词的完备集。【定义2.7】{，，，，，，，}，{，}，{，}是联结词的完备集。2.6】异或PQc P条件否定PQ：(PQ)与非PQ： (PQ)或非PQ： (PQ)【定义2.8】{},{↓}都是联结词的完备集【定理2.7】重言蕴含式：当且仅当PQ是一个重言式时，称P重言蕴含Q，记为PQ。有效结论：设A、C是两个命题公式，若AC，称C是A的有效结论。【定义3.1】推理定律——重言蕴涵式A(AB) 附加律(AB)A 化简律(AB)AB 假言推理(AB)BA 拒取式(AB)BA 析取三段论(AB)(BC)(AC) 假言三段论(AB)(BC)(AC) 等价三段8. (AB)(CD)(AC)(BD) 构造性二难(AB)(AB)B 构造性二难(特殊形式9. (AB)(CD)(BD)(AC) 破坏性二难形式系统:一个形式系统I由下面四个部分组成：非空的字母表，记作A(I).X推理规则集，记作记I=<A(I),E(I),A(I),R(I)>,其中<A(I),E(I)>是I的形式语言系统,<A(I),R(I)>是I的形式演算系统.X X自然推理系统:无公理,即A(I)=X公理推理系统:推出的结论是系统中的重言式,称作定理【定义3.2】P规则：在推导过程中,可以随时添加前提。T规则：在推导过程中,可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到的。推理（证明）：从前提A,A,,A到结论B的推理是一个公式序列C,C,,C.其中C(1il)是某个A,或者可由1 2 k 1 2 l i j序列中前面的公式应用推理规则得到,并且Cl

=B。【定义3.3】CP规则(演绎定理)：若{R}|-S，则|-RS,其中为命题公式的集合。个体词：个体常元表示确指个体。个体变元表示不确指个体。个体域:个体变元的取值范围，常用D表示。量词：限定个体数量特性的词。全称量词：对所有的存在量词：有些谓词语言个体变元符号：x，y，z，…个体常元符号：a，b，c，…函数符号：f，g，…谓词符号：P，Q，R，…命题常元符号：量词符号：，连接词符号：,,,,辅助符号：）,（ 【定义4.1】项:(1)个体常元和变元是项；fn，t1,tnf(t1tn)是项；仅仅有限次使用(1)，(24.2】原子公式:若P是一个元谓词符号，t1,…,tn是项,则P(t1,…,tn)是原子公式。【定义4.3】合式公式：(1)原子公式是公式；AA)是合式公式；A，BAB)，(AB)，AB)，(AB)是公式；AxxA，xA仅仅有限次使用１～４得到的符号串才是合式公式。4.4设公式的一个子公式为xA或xA。则称：指导变元：x是或的指导变元。辖域：A是相应量词的辖域。约束出现：辖域中x的一切出现，以及(x)中的x称为x在中的约束出现。自由出现：变元的非约束出现。约束变元：约束出现的变元。自由变元：自由出现的变元。【定义4.5】封闭的：一个公式A是封闭的，若其中不含自由变元。【定义4.6】变元换名：（1）换名的范围是量词的指导变元,及其相应辖域中的变元，其余部分不变。（2）换名时最好选用辖域中未出现的变元名。变元代入：代入对自由变元进行。不能改变约束关系。解释：谓词语言的一个解释I=(D,)包括：D，称之为论域；对应于每一个个体常元a，(a)D；nf(f):DnD；nAn(A)Dn。4.7】赋值：解释I中的赋值v为每一个个体变元x指定一个值v(x）D，即设V为所个体变元的集合，则赋值v是函数v:VD.可满足的：给定公式A，若在某一解释中至少有一种赋值使A取值为1，则称A为可满足的。否则称A是不可满足的。等值式AB：若AB是有效的【定义5.1】几类等值式命题公式的推广e.g.P(x)Q(x)P(x)Q(x)否定深入xP(x)x(P(x))xP(x)x(P(x))量词作用域的扩张与收缩设B中不含x的自由出现，则x(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(BA(x))BxA(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)多个量词的使用xyA(x,y)yxA(x,y)xyA(x,y)yxA(x,y)置换规则：设(A)是含A的公式,那么,若AB,则(A)(B).换名规则：AAAAA.前束范式：如果谓词公式A有如下形状：Qx…QxM，其中Qx或者是x，或者是x，i=1，…，n，M是不含量11 nn ii i i词的公式，Qx…Qx称为首标，M称为母式。【定义5.2】11 nn前束范式存在定理：对于任意谓词公式，都存在与它逻辑等价的前束范式。【定理5.1】前束范式的算法：步1.对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。步2.将所有的否定号深入到量词后面。步3.将量词符号移至公式最外层。逻辑蕴含式AC：当且仅当AC是有效的。几类逻辑蕴涵式第一组命题逻辑推理定理的代换实例如,xF(x)yG(y)第二组基本等值式生成的推理定理如,xF(x)xF(x),xF(x)xF(x)xF(x)xF(x), xF(x)第三组其它常用推理定律(1)xA(x)xB(x)x(A(x)B(x))(2)x(A(x)B(x))xA(x)xB(x)(3)x(A(x)B(x))xA(x)xB(x)(4)x(A(x)B(x))xA(x)xB(x)推理规则-规则(US)：或 x,y个体变项，c个体常项+规则(UG)： x个体变项-规则(ES)： x个体变项,c个体常项+规则(EG)：或 x,y个体变项，c个体常项或先用ES，再用US自然推理系统N ：LL的字母表L的合式公式推理规则:前提引入规则结论引入规则置换规则假言推理规则附加规则化简规则拒取式假言三段论规则析取三段论规则构造性二难推理规则合取引入规则-规则+规则-规则+规则 【定义5.3】集合论：ABx(xAxB)【定义6.1】A=BABBA【定义6.2】ABABAB 6.3】A Bx(xAxB)空集：不含有任何元素的集合【定义6.4】空集是任何集合的子集。6.1)={x|xA6.5】如果|A|=n，则|P(A)|=2n全集E：包含了所有元素的集合【定义6.6】并AB ={x|xAxB}交AB ={x|xAxB}差（相对补）AB={x|xAxB}【定义6.7】对称差AB =(AB)(BA)【定义6.8】补（绝对补）AEA{x|xA}6.9】广义并Ax|zzA)}6.10】广义交Ax|zzAxz6.11】集合恒等式交换A交换AB=BAAB=BAAB=BA结合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A2．涉及两个不同运算的算律：与与分配 A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收 A(AB)=AA(AB)=A3．涉及补运算的算律：A(BC)=(AB)(AC)D.MD.MA(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定A=A补元律零律补元律零律否定AA=A=A=A=EEAA=EAE=EAE=AE=序偶（有序对）：由两个元素x和y，按照一定的顺序组成的二元组，记作<x,y>.【定义7.1】笛卡儿积:设A,B为集合，A与B的笛卡儿积记作AB定义为AB={<x,y>|xAyB}.【定义7.2】笛卡尔积性质：A=或B=时,AB=“”不满足结合律A(BC)=(AB)(AC)关系：（两个定义）R。R中任一序偶<x,y>,可记作<xy>RxRy7.3】笛卡尔积的子集：R【定义7.4】空关系:全域关系：A×B恒等关系IA

{<x,x>|x∈A} 7.5】关系矩阵：若A={x,x,…,x}，B={y,y,…,y}，R是从A到B的关系，R的关系矩阵是布尔矩阵M

=[r] ,其1 2 m

1 2 n

R ij mn中r=1<x,y>R.ij i j关系图：若{x,x,…,x}，R是从A上的关系，R的关系图是G其中A为结点集，R为边集. 如果1 2 m R<x,x>属于关系R，在图中就有一条从x到x的有向边.ij i j前域(定义域)dom(R)={x|y.<x,y>R}值域ran(R)={y|x.<x,y>R}域fld(R)=domRranR 【定义7.6】逆关系1={,>|,>R}【定义7】互逆(1)1=R(RS)

=R

S1(RS)1=R1S1(AB)1(R-S)

=BA=R

-S1复合关系RS={<x,z>|y(<x,y>R<y,z>S)}【定义7.8】(RS)P=R(SP)Rm=RR…R设R XY,S YZ,则(RS)

=S1R

【定理7.2】R在A上的限制R↾A={<x,y>|xRy∧x∈A}A在R下的像R[A]=ran(R↾A) 【定义7.9】自反的：若x∈A，都有<x,x>R,则称R是自反的反自反的：若x∈A，都有<x,x>R,则称R是反自反的.【定义7.11】对称的：对任意x,yA,满足,若<x,y>R,则<y,x>R反对称的：对任意x,yA,满足，若<x,y>R且<y,x>R,则x=y【定义7.12】传递的：对任意的x,y,zA,满足:若<x,y>R且<y,z>R,则<x,z>R,则称R是传递的【定义7.13】自反闭包（对称、传递）：设R是A上的二元关系,如果有另一个关系R'满足:① R'是自反（对称、传递）的;② R'R;③ R”,R"RR"R'.则称关系R'为R的自反闭包.记为r(R)（对称闭包s(R)和传递闭包t(R)）。【定义7.14】RAr(R)=R∪IA(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…（若t(R)=R∪R2∪…∪Rn）等价关系：设R为集合A上的一个二元关系。若R是自反的,对称的,传递的, 则称R为A上的等价关系【定7.15】等价类：设R为集合A上的等价关系,对aA,定义:[a]R【定义7.16】

={x|xA且<a,x>R}称之为元素a关于R的等价类。给定A上的等价关系R,对于a,bA有<a,b>当且仅当[a]R=[b]R【定理17.4】商集：设R是A上的等价关系，定义A/R={[a]|aA}称之为A关于R的商集.【定义7.17】R划分：设A为非空集合,若A的子集族π(πP(A))满足:(1)π(2)xy(x,yπ∧x≠yx∩y=)(3)∪π=A则称π是A的一个划分,称π中的元素为A的划分块.【定义7.18】给定集合A上的等价关系R,则商集A/R是A的一个划分.AπAR.RR={<x,y>|x,yAx,yπRR1 2

AR1

RA/R2

=A/R.2偏序：设A是一个集合.如果A上的二元关系R是自反的,反对称的和传递的,则称R是A上的一个偏序关系.记R为“”,且称序偶<A,>为偏序集。【定义7.19】【定义7.22】全序（线序）：设<A,>为偏序集,若对任意的x,yA满足:xy或yx则称为全序关系.<A,>为全序集.【定义7.21】覆盖：设<A,>为偏序集,若x,yA,xy,xy且没有其它元素z满足xz,zy,则称y覆盖x. 记covA={<x,y>|x,yA且y覆盖x}【定义7.23】哈斯图：作图规则① 用小元圈代表元素;② xyxy,yx③ 若<x,y>covAx,y你极小元/极大元：设<A,>为偏序集,BAbBBxbxxb则称bBbBBxbxbx则称bB最小元/最大元：设<A,>为偏序集,BA,若有某个bBBxbxbBBxxbbB7.24】下界/上界：设<A,>为偏序集,BAaA,且对xB满足axaB下界。进一步:设a为B的下界,若B的所有下界y均有ya,则称a为B的下确界，记为glbB。aA,且对xB满足xaaB上界。进一步:设a为B的上界,若B的所有上界y均有ay,则称a为B的上确界，记为lubB。【定义7.25】函数：设X,Y为两个集合,fXY,若对xX,!(唯一的)yY,满足:<x,y>f,则称f为函数.记为:f:XY定义域:domf=X值域:ranf(有时记为f(X))={f(x)|xX}【定义8.1】函数相等：设f和g都是从A到B的函数,若对任意xA,有f(x)=g(x),则称f和g相等.记为f=g【定义8.2】f:AB,|A|=m,|B|=n.记BA={f|f:AB},则|满射(到上映射)：设f:XY,若ranf=Y,则称f为满射的.

|=nm入射（单射）(一对一映射)：fXYxxXxxf(xf(xf为入射的.1 2 1 2 1 2双射(一一对应映射)：设f:XY,若f既是满射的,又是入射的.则称f是双射的.【定义8.6】常函数:设f:A→B,如果存在c∈B使得对所有的x∈A都有f(x)=c,则称f:A→B是常函数.恒等函数:称A上的恒等关系IA为A上的恒等函数,对所有的x∈A都有IA(x)=x.单调递增:设<A,≼>,<B,≼>为偏序集，f:A→B，如果对任意的x,x∈A,x≺x,就有f(x)≼f(x),则称f为单调递增的；1 2 1 2 1 2严格单调递增:如果对任意的x,x∈A,x≺x,就有f(x)≺f(x),则称f为严格单调递增的.1 2 1 2 1 2类似的也可以定义单调递减和严格单调递减的函数特征函数：设A为集合,对于任意的A'A,A'的特征函数':A→{0,1}定义为'(a)=1,a∈A';'(a)=0,a∈AA'A A A自然映射：设R是A上的等价关系,令g:A→A/R；g(a)=[a],a∈A称g是从A到商集A/R的自然映射【定义8.7】复合函数：设f:XY,g:YZ,定义:fg={<x,z>|xX且zZ且可找到yY使y=f(x),z=g(y)}称fg为f与g的复合函数.设f:A→B,g:B→C如果f:A→B,g:B→Cfg:A→C如果f:A→B,g:B→Cfg:A→C如果f:A→B,g:B→Cfg:A→C也是双射的8.2】反函数（逆函数）：设f:XY是一个双射函数，那么f-1是YX的双射函数.称f-1为f的反函数.互逆(f

-1)-1=fB设:→B是双射的,则f1f=I,ffB

=I【定理8.5】A基数：用来衡量集合大小的一个概念.对于有限集合集来说,集合的基数就是其中所含元素的个数.等势的：设A,B是集合,如果存在着从A到B的双射函数,就称A和B是等势的,记作A≈B.如果A不与B等势,则记作A≉B. 注：通常将A的基数记为|A|.【定义8.8】N≈Z≈Q≈N×N任何实数区间都与实数集合R等势{0,1}N≈R康托定理N≉R；AA≉P(A).8.7】有限集(有穷集)/无限集(无穷集)：设A为一个集合.若存在某个自然数n,使得A与集合{0,1,…,n-1}等势,则称A是有限的.若集合A不是有限的,则称A是无限的.【定义8.11】：实数集R的基数记作,即cardR=【定义8.12】可数集(可列集)：设A为集合，若cardA≤，则称A为可数集或可列集。【定义8.14】0与自然数集N等势的任意集合称为可数的.其基数为0结论：AA={a,a,a1 2 n任一无限集必含有可数子集.可数集的任何无限子集是可数的.可数个两两不相交的可数集合的并集,仍是一个可数集.NN有理数的全体组成的集合是可数集.R基数的常识：①对于有穷集合A,基数是其元素个数n，|A|=n;②没有最大的基数。将已知的基数按从小到大的顺序排列就得到：0,1,2,…,n,…,,,…0代数结构运算：对于集合A，f是从An到A的函数，称f为集合A上的一个n元运算。【定义9.1】交换律：已知<A，*>，若x，y∈A，有x*y=y*x，称*在A上是可交换的。【定义9.3】结合律：已知<A，*>，若x，y，z∈A，有x*（y*z）=（x*y）*z，称*在A上是可结合的。【定义9.4】幂等律：已知〈A，*〉，若x∈A，x*x=x 则称满足幂等律。【定义9.5】分配律：设<A，*，△>，若x，y，z∈A有:x*(y△z)=（x*y）△（x*z）;(y△z)*x=(y*x)△(z*x)称运算*对△是可分配的。【定义9.6】吸收律：设,是定义在集合A上的两个可交换二元运算，若对x,yA,都有:x(xy)=x；x(xy)=x则称运算和满足吸收律.【定义9.7】单位元（幺元）: 设*是A上二元运算，e,e,eAl r左幺元：若xA，有e*x=x，称e为运算*的左幺元；l l右幺元：若xA，有x*e=x，称e为运算*的右幺元；r r若e既是左幺元又是右幺元，称e为运算*的幺元【定义9.8】设*Aelee=e=e9.1】零元: 设*是A上二元运算，,,

r l rl r左零元：若xA，有*x=l l

，称为运算*的左零元；l右零元：若xA，有x*=，称为运算*的右零元；r r r若既是左零元又是右零元，称为运算*的零元。【定义9.9】设*是A上的二元运算，具有左零元l

，右零元，则 =r l

=【定理9.2】r逆元：设*是A上的二元运算，e是运算*的幺元，若x*y=e那对于运算*，x是y的左逆元，y是x的右逆元存在逆元(左逆无，右逆元）的元素称为可逆的（左可逆的，右可逆的）9.10】对于可结合运算οxｌ，rl=r=x－１9.4消去律：已知<A，*>，若x，y，z∈A，有x*yx*zxy=z；(左消去律)y*xz*xxy=z；（右消去律）那么称*满足消去律。9.11】代数系统：设A为非空集合，为A上运算的集合,称<A,>为一个代数系统.【定义9.12】同类型的代数系统：如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.【定义9.13】子代数：V=<Sf1f2fk>BSBf1f2fkBSf1f2fk>是V9.14】最大的子代数：就是V本身最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数平凡的子代数:最大和最小的子代数称为V的平凡的子代数真子代数：若B是S的真子集，则B构成的子代数称为V的真子代数.因子代数：设V=<A,◦>和V=<B,>是同类型的代数系统，◦和为二元运算，在集合AB上如下定义二元运算▪，1 2<a,b>,<a,b>AB，有<a,b>▪<a,b>=<a◦a,bb>称V=<AB,▪>为V与V的积代数，记作VV.这时1 1 2

1 1 2

1 2 1 2

1 2 1 2也称V和V1 2

为V的因子代数.【定义9.15】V=<A,◦V=<B,>是同类型的代数系统，VV1 2 1 2如果◦和运算是可交换（可结合、幂等）的，那幺▪运算也是可交换（可结合、幂等）的如果

和e（和）分别为◦和运算的单位元（零元），那幺<e,e>（<,>）也是▪运算的单位元1（零元）

2 1 2

1 2 1 2如果x和y分别为◦和运算的可逆元素，那幺<x,>也是▪运算的可逆元素，其逆元就是1>【定理9.5】同态:设V>和V=<B,>是同类型的代数系统，f:AB，对有y)=则称f是V到V的1 2 1 2同态映射，简称同态f如果是单射，则称为单同态。如果是满射，则称为满同态VVVV2 1 1 2。如果是双射，则称为同构，也称代数系统V同构于VVV1 2V=V，则称作自同态。9.16】

1 2。1 2半群：设V=<S, >是代数系统， 为二元运算，如果 运算是可结合的，则称V为半群。独异点：设V=<S, >是半群，若e∈S是关于 运算的单位元，则称V是含幺半群，也叫做独异点。有时也将异点V记作V=<S, ,e>.群：设, 是独异点，G关于 运算的单位元，若 ，则称V是群.通常将群记作G.【定义10.1】群的阶数：设<G,>是一个群有限群：如果G是有限集，那么称<G,>为有限群阶数：|G|为该有限群的阶数；无限群：如果G是无限集，则称<G,>为无限群。平凡群：阶数为1（即只含单位元）的群称为平凡群【定义10.2】群的性质：设<G,>是一个群。非平凡群中不可能有零元.对于a,bG,xGax=b.对于{a,b,c}Gabacbacab=c(消去律)。运算表中的每一行或每一列都是一个置换。ee n0anann0n0,nm元素的幂：设G是群，a∈G，n∈Z，则a的n次幂 【定义10.3】元素的阶：设G是群，a∈G，使得等式ak=e成立的最小正整数k称为元素a的阶，记作|a|=k，称a为k阶元。若不存在这样的正整数k，则称a为无限阶元。【定义10.4】幂运算性质：(1)∈，(11=a(2),∈，(a)=1∈，m=，,∈Z=G为交换群，则(=10.1】元素的阶的性质：G为群，a∈G且k是整数，则(1)er|k(r(2)||=||【定理10.3】子