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

时间:2024.4.20

【半群】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(右mod H)。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的正规子群。

5 H是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到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,bÎR,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。乘法同态性:若a≡b,c≡d,则ac≡bd。

【环同态】R是环,S有加乘两种运算,R到S中的一个映射σ(a+b)=σ(a)+σ(b),σ(ab)=σ(a)σ(b)。R到R′同态,记为R~R′。

【环同构】σ是环R到系统R′上的一个一对一的同态映射。R与R′同构,记为R@R′。

若σ是R到S中的一个同态映射,则R的映象R′=σ(R)也是一个环,σ(0)就是R′的零0′,σ(-a)=-σ(a)。若R有壹而R′不只有一个元素,则R′有壹而且σ(1)就是R′的壹1′;若a∈R有逆,则σ(a)在R′中有逆而且σ(a-1)就是σ(a)-1。

【理想】同态映射σ的核N是R的一个~.设a′是R′的任意元素,则a′的逆映象σ-1(a′)={a∈R∣σ(a)=a′}是N的一个剩余类。

1按照剩余类的加法和乘法,R对于理想N的所有剩余类的集合R∕N是一个环,

2规定σ(a)= a+N,则σ是R到R∕N上的一个同态映射,其核为N。R∕N叫做R对于N的剩余环

3设环R同态于R′: R~R′于是R与N之间的子环与R′的子环一一对应,大环对应大环,小环对应小环,理想对应理想。

【极大理想】N Ì R,而R与N之间没有别的理想。极大理想不唯一

若N Ì R,则N是R的极大理想必要而且只要R∕N是单纯环。



【域】任意有壹的交换的单纯环。任意域F是有壹的交换的单纯环。

设R是有壹的交换环,N是R的理想。于是,R∕N是一个域,必要而且只要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实数域上,质式只能是一次式或二次式。二次式aх2+bx+c是质式,当且仅当判别式b2-4ac<0。

设?(х)= a0хn + a1хn-1 … + an 是整系数多项式,若对质数p,p不整除a0,p∣a1,…,p∣an,p2不整除an,则?(х)在有理域上【不可约】。

设 ?(х)= a0хn + a1хn-1 + … + an 是整系数多项式。若有理数b∕c是?(х)的根,其中b和c是互质的整数,则b∣an,c∣a0。

【求有理根】1.分别找a0和an的所有因子ci,bj;2.找互质对( ci,bj );3.判断ci/bj是否为根;4.判断重根。

复数α称为一个代数数,如果α是某个有理系数非0多项式的根。若α不是任何有理系数非0多项式的根,则α称为一个超越数。

复数域中恰有n个n次单位根。它们在乘法下作成一个n元循环群

Φ1(х)=х-1  Φ2(х)=х+1

Φ3(х)=х2+ x + 1Φ4(х)= x2 + 1

х12-1=Φ12Φ6Φ4Φ3Φ2Φ1,

х6-1= Φ6Φ3Φ2Φ1

相除得х6+1 = Φ12Φ4

设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,b∈L,L的子集{a,b}在L中都有一个最大下界(记为inf{a,b})和一个最小上界(记为sup{a,b})。

一个序集是一个格,但是,不是所有部份序集都是。

设(L,≤)是格,S是L的子集,即SÍL,如果(S,≤)是格,则称(S,≤)是格(L,≤)的【子格】。

设L是一个集合,×,Å 是L上两个二元代数运算,如果这两种运算对于L中元素满足:(1)交换律:a×b=b×a, a Å b=b Å a。(2)结合律: a×(b×c)=(a×b)×c, a Å(b Å c)=(a Å b)Åc。(3)吸收律:a×(a Å b)=a,a Å(a×b)=a。则称此代数系统(L,×,Å)为一个【格】。



集合L中的【部份序关系】R与其逆关系R-1,称为互相对偶的两个关系。

对任意x,y∈L, xR-1yÛyRx。若R是部分序关系,则R-1也是。

【格同态】(L,×, Å )和(S,∧,∨)是个格,L到S的映射g对任意a,b∈L,有g(a×b)= g(a)∧g(b)g(aÅb)= g(a)∨g(b)

若g是L到S上的同态映射,且是一对一的,则称g是格【同构映射】。

【有界格】格(L,≤)有一个最大元素(记为1)和一个最小元素(记为0),亦即,对任意a∈L,都有0≤a≤1,0,1称为格(L,≤)的界。

在有界格(L,×,Å,0,1)中,一个元素b∈L,称为元素a∈L的【余元素】,如果a×b = 0, a Å b = 1。

在有界格(L,×,Å,0,1)中,任意元素a可以有余元素,也可以没有余元素;如果有余元素,则可以有一个或一个以上的余元素。

有界格(L,×,Å,0,1)说是一个【有余格】,如果对L中每一个元素,都至少有一个余元素。

格(L,×,Å)称为【分配格】,如果对任意a,b,c∈L,恒有a×(bÅc)=(a×b)Å(a×c),a Å(b×c)=(aÅb)×(aÅc)

设格(L,×, Å )是一个有余分配格,则对任意a∈L,a的余元素a′是唯一的。

设(L,≤)是一个格,对任意a,b,c∈L,如果a≤b,都有aÅ(b×c)= b×(aÅc)则称(L,≤)为【模格】。任意一个分配格都是模格,但模格不一定是分配格。

对任意a,b,c∈L,如果a≤b,a×c=b×c,aÅc=bÅc,则必有a=b。

一个有余分配格是一个布尔代数。

【布尔代数】设B是一个至少含有两个不同元素的集合,·,+是定义在B上的两种代数运算,如果对任意a,b,c∈B,满足下面公理:

H1:  a·b = b·a,a+b = b+a

H2:  a·(b+c)=(a·b)+(a·c),

     a+(b·c)=(a+b)·(a+c)。

H3: B中有元素 0和元素1,使得对任意a∈B,有 a·1 = a,     a+0 = a。

H4: 对任意a∈B,有∈B,使得a·=0, a+ =1。 则(B,·,+,ˉ,0,1)是一个布尔代数。

有限布尔代数的基底必是此代数的所有极小元素;反之,此代数的所有极小元素必然做成此代数的基底。

举例说明不要求可除条件而要求消去条件,即要求由aχ=ay可推出χ=y,由χ·a=y·a可推出χ=y,则G不见得是一个群,若G有限怎么样?

解:例如,全体自然数在普通乘法下,适合消去律,但不是群。若G={a1,a2,…an},用a右乘G中各元素得a1a,a2a,…,ana必不相同,否则若aia=aja (i¹j) ,由消去条件有ai=aj,矛盾。对任意bÎG,必有ai,使aia=b,因之方程xa=b有解。同理可知ay=b有解。故G是群。

设K和H都是群G的子群,试证明:若H·K是G的子群,则K·H = H·K。

证明:对任意的k·hÎK·H,

(k·h)-1=h-1·k-1ÎH·K,由于H·K是G的子群,所以((k·h)-1)-1ÎH·K,因此K·HÍ H·K。对于任意的h·kÎH·K,(h·k)-1ÎH·K,即存在h1ÎH,k1ÎK使得(h·k)-1=h1·k1,所以h·k=(h1·k1)-1=k1-1 ·h1-1 ÎK·H,因此H·KÍ K·H。由集合论知识知K·H = H·K。



任意置换σ恰有一法写成不相杂的轮换乘积。

证明:先证σ可以写成不相杂的轮换的乘积,取任意a1∈M。

(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。于是我们得到一个轮换

(a1…ar)。

若M已经没有另外的元素,则σ就等于这个轮换,否则设b1不在a1,…,ar之内,则同样作法又可得到一个轮换(b1…bs)。

因为a1,…,ar各自已有变到它的元素,所以b1,…,bs中不会有a1,…,ar出现,即这两个轮换不相杂。若M的元素已尽,则σ就等于这两个轮换的乘积,否则如上又可得到一个轮换。如此类推,由于M有限,最后必得

σ=( a1…ar)(b1…bs)…(c1…ct)  (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+x+1。

其中只有x2+x+1是质式。

但x5+x2+1 = x2(x+1)( x2+x+1)+1,

因此, f (x) 在R2上无二次因式。

即, f(x) 在R2上不可约。

所以,f(x) 在R0上不可约。

5. 求证:j(x)F[x]的极大理想,当且仅当j(x)不可约。

证明:必要性:若j(x)可约,设j(x)=l(x)m(x),次l(x)³1,次m(x)³1。

对任意g(x)Îj(x)F[x],

      g(x)= j(x)f(x)=l(x)m(x)f(x),

故g(x)Îl(x)F[x]。

显然,l(x)Î l(x)F[x],但次l(x)<次j(x),j(x)F[x]中非0元素次数³次j(x),

故l(x)Ïj(x)F[x]。综合以上得: l(x)F[x]Éj(x)F[x],矛盾于j(x)F[x]的极大性。

充分性:若j(x)F[x]不是极大理想,

则另有理想l(x)F[x],非F[x],

而使j(x)F[x]Ìl(x)F[x]。

因为j(x)Î j(x)F[x],

所以, j(x)Î l(x)F[x]

所以, j(x) = l(x)q(x) 且次q(x) ³1。

(为什么?)

与j(x)不可约矛盾。

求证若G的元数是一个质数,则G必是循环群。

证明:设G的元数为质数P,任取G中非单位元a,则(a)是G的一个循环子群,设a的周期为r,则(a)的元数为r,因此r|P。但P是质数。显然r¹1,故r=P,所以G=(a),即G是由a生成的循环群。



定义A所定义的格和定义B所定义的格是等价的,亦即,一个部份序格必是一个代数格;反之亦然。

证明:i)若(L,≤)是一个格,

则对任意a,b∈L,记inf{a,b}为a×b;sup{a,b}为aÅb。由于对任意a,b,其inf{a,b},sup{a,b}是唯一的,所以,如上定义的×,Å是集合L上的两种二元代数运算。不难证明,对于×,Å满足交换律,结合律,吸收律.我们只证明吸收律:

          a×(aÅb)=a

因为a×(aÅb)是a与(aÅb)的最大下界,所以

a×(aÅb)≤a;另一方面,由于a≤a,a≤aÅb,所以,a是a与aÅb的下界,故a≤a×(aÅb),

故a = a×(aÅb)。

因此,根据定义B,(L,×,Å)是一个格。

ii)若代数系统(L,×,Å)是一个格,在集合L上定义一个关系≤如下:

对任意a,b∈L, a≤bÛa×b=a

往证:≤是一个部份序关系。

因为

a×a=a×(aÅ(a×a))=a

所以有a≤a。

若有a≤b,b≤a,则应有a×b=a,b×a=b,

而a×b = b×a,所以a=b。

若 a≤b,b≤c,则有a×b=a,b×c=b,

故a×c=(a×b)×c = a×(b×c)= a×b = a

亦即,有a≤c。

由此证明了关系≤具有反身性,反对称性,传递性。

故≤是部份序关系。

求证循环群的子群仍是循环群。

证明:若循环群G由其中元a生成。H是G的子群,但不是单位元群。则H中必含有幂m>0的元am。因为若m<0,am的逆元a-m也在H内,而-m>0。假定am是H中的最小正幂,显然H包含am的任意乘幂。假如又有H中任意元aS,由S=tm+r。0≤r<m知ar=aS-tm=(aS)·(am)-t是H中元,但m最小。而0≤r<m,故r=0,因此有aS=(am)t这表明H中任意元aS也是am的乘幂,而知H为am生成的循环群。

构造元数为8的有限域,并写出该域的加法和乘法表。

解:由于8=23,所以,p=2,m=3。

(1)首先求Φpm-1(х),即Φ7(х)。

由x7-1=Φ7Φ1,x-1=Φ1,得Φ7(х)=                          

(2)求Φ7(х)在R2[х]中的3次质因式ψ(х)。

Φ7(х)=(x3+x2+1)(x3+x+1),

我们不妨取ψ(х)=x3+x+1,则

R2[x]/(ψ(х))=

(3) 若取ξ=   ,则ψ(ξ)=                       ,

,GF(8)={a0 +a1ξ+a2ξ2|a0,a1,a2∈R2}={0,1,ξ,ξ+1,ξ2,ξ2+1,ξ2+ξ,ξ2+ξ+1}.


更多相关推荐:
离散数学知识点

第一章1.将下列命题符号化:解:令p:天下雨,q:我骑自行车上班,则(1)只要不下雨,我就骑自行车上班?p是q的充分条件,所以符号化为:?p→q(2)只有不下雨,我才骑自行车上班?p是q的必要条件,所以符号化为…

离散数学必备知识点总结

总结离散数学知识点第二章命题逻辑1前键为真后键为假才为假ltgt相同为真不同为假2主析取范式极小项m之和主合取范式极大项M之积3求极小项时命题变元的肯定为1否定为0求极大项时相反4求极大极小项时每个变元或变元的...

离散数学复习总结+试题

离散数学第一章命题逻辑目标语言表达判断的一些语言的汇集判断对事物有肯定或否定的一种思维模式命题能表达判断语言的陈述句原子命题不能分解为更简单陈述句的语句复合命题由联结词标点符号和原子命题复合构成的命题称作复合命...

离散数学第一章知识点总结

离散数学第一章知识点总结(仅供参考)1.判断给定的句子是否为命题的基本步骤:首先应是陈述句;其次要有唯一的真值。例:(1)我正在说谎。不是命题。因为无法判定其真假值,若假设它为假即我正在说谎,则意味着它的反为真…

离散数学第九章树知识点总结

图论部分第九章树91无向树及生成树无向树森林无向树的性质定理设GltVEgt是n阶m条边的无向图则下面各命题是等价的1G是树连通无回路2G中任意两个顶点之间存在惟一的路径3G中无回路且mn14G是连通的且mn1...

离散数学学期总结

学号**********姓名***班级************离散数学是描绘一些离散量与量之间的相互逻辑结构及关系的学科。它的思想方法及内容渗透到计算机学科的各个领域中。因此它成为计算机及相关专业的一门重要专业…

离散数学课程总结

离散数学课程总结一、对该课程的理解:离散数学是现代数学的一个重要分支,是计算机科学专业的专业主干课之一,课程结合计算科学的特点研究离散对象和相互关系,对提高学生的抽象思维与逻辑推理能力有很重要的作用。它以研究离…

离散数学知识点整理

1推理所谓推理就是由一个或几个判断推出一个新判断的思维形式2命题具有唯一真值的陈述语句345678按照量词与特性谓词的搭配不同在全称量词中特性谓词是条件式的前提在存在量词中特性谓词后跟一个合取项910集合的表示...

离散数学第八章一些特殊的图知识点总结

图论部分第八章一些特殊的图81二部图二部图定义设无向图GltVEgt若能将V划分成V1和V2V1V2VV1V2使得G中的每条边的两个端点都一个属于V1另一个属于V2则称G为二部图记为ltV1V2Egt称V1和V...

离散数学(数学教育)知识点

一蕴涵设PQ是两个命题命题若P则Q称为P蕴涵Q记作PQ规定PQ是假的当且仅当P是真的而Q是假的二1设A是非空集合R是A上的二元关系R的自反闭包对称闭包传递闭包R满足如下条件1R是自反的对称的传递的2RR3对A上...

离散数学第二章一阶逻辑知识点总结

数理逻辑部分第2章一阶逻辑21一阶逻辑基本概念个体词个体所研究对象中可以独立存在的具体或抽象的客体个体常项具体的事物用abc表示个体变项抽象的事物用xyz表示个体域个体变项的取值范围有限个体域如abc12无限个...

安徽省中考数学知识点总结

初中数学高考知识点大全1一元二次方程根的情况yax2bxcb24ac当gt0时一元二次方程有2个不相等的实数根当0时一元二次方程有2个相同的实数根当lt0时一元二次方程没有实数根2平行四边形的性质两组对边分别平...

离散数学知识点总结(15篇)