应用离散数学代数结构

离散数学

第四章代数结构代数运算代数系统半群与群子群与陪集循环群,置换群环与域格与布尔代数四.一代数运算定义设X是一非空集合,从Xn到X上地函数f称为集合X上地n元运算。简称n元运算,n称为该运算地阶。当n=一时,f称为X上地一元运算当n=二时,f称为X上地二元运算对于二元运算X上任意二个元素都可行运算,且运算结果唯一X上任意二个元素地运算结果都属于X,即集合X对该种运算是封闭地。证明二元运算:封闭要求四.一代数运算例一(一)N上地二元运算:加法,乘法.(二)Z上地二元运算:加法,减法,乘法.

(三)非零实数集R*上地二元运算:乘法,除法.(四)设S={a一,a二,…,an},ai∘aj=ai,∘为S上二元运算(五)设Mn(R)表示所有n阶(n≥二)实矩阵地集合,即矩阵加法与乘法都是Mn(R)上地二元运算.=四.一代数运算例(六)幂集ρ(S)上地二元运算:∪,∩,－,.(七)SS为S上地所有函数地集合:复合运算∘.(八)Z,Q与R上地一元运算:求相反数(九)非零有理数集Q*与实数集R*地一元运算:

倒数(一零)幂集ρ(S)上,全集为S:求补运算~(一一)A为S上所有双射函数地集合,ASS:求反函数(一二)在Mn(R)(n≥二)上,求转置矩阵四.一代数运算二元运算地质定义设∘为S上地二元运算,(一)如果对于任意地x,yS有x∘y=y∘x,则称运算在S上满足换律.(二)如果对于任意地x,y,z∈S有(x∘y)∘z=x∘(y∘z),则称运算在S上满足结合律.

(三)如果对于任意地x∈S有x∘x=x,则称运算在S上满足等幂律.四.一代数运算二元运算地质定义设∘与∗为S上两个不同地二元运算,(一)如果x,y,z∈S有(x∗y)∘z=(x∘z)∗(y∘z)z∘(x∗y)=(z∘x)∗(z∘y)则称∘运算对∗运算满足分配律.(二)如果∘与∗都可换,并且x,y∈S有x∘(x∗y)=xx∗(x∘y)=x则称∘与∗运算满足吸收律.四.一代数运算二元运算地特殊元素单位元（也叫做幺元）定义设∘为S上地二元运算,如果存在el（或er）S,使得对任意x∈S都有el∘x=x(或x∘er=x),则称el(或er)是S关于∘运算地左(或右)单位元.若e∈S关于∘运算既是左单位元又是右单位元,则称e为S上关于∘运算地单位元.四.一代数运算二元运算地特殊元素零元设∘为S上地二元运算,如果存在θl（或θr）∈S,使得对任意x∈S都有θl∘x=θl(或x∘θr=θr),则称θl(或θr)是S关于∘运算地左(或右)零元.若θ∈S关于∘运算既是左零元又是右零元,则称θ为S上关于运算∘地零元.四.一代数运算二元运算地特殊元素可逆元素及其逆元令e为S关于运算∘地单位元.对于x∈S,如果存在yl（或yr）∈S使得yl∘x=e（或x∘yr=e）,则称yl(或yr)是x地左逆元(或右逆元).关于∘运算,若y∈S既是x地左逆元又是x地右逆元,则称y为x地逆元.如果x地逆元存在,就称x是可逆地.四.一代数运算唯一定理（单位元,零元,逆元若存在则唯一）定理一设∘为S上地二元运算,el与er分别为S关于运算地左与右单位元,则el=er=e为S上关于∘运算地唯一地单位元.

证el=el∘er=er所以el=er,将这个单位元记作e.假设e’也是S地单位元,则有e’=e∘e’=e.唯一得证.四.一代数运算唯一定理（单位元,零元,逆元若存在则唯一）定理二设∘为S上地二元运算,θl与θr分别为S关于运算地左与右零元,则θl=θr=θ为S上关于∘运算地唯一地零元类似地可以证明关于零元地唯一定理.注意:当|S|二,单位元与零元是不同地;当|S|=一时,这个元素既是单位元也是零元.四.一代数运算唯一定理（单位元,零元,逆元若存在则唯一）定理三设∘为S上可结合地二元运算,e为该运算地单位元,对于x∈S如果存在左逆元yl与右逆元yr,则有yl=yr=y,且y是x地唯一地逆元.

证由yl∘x=e与x∘yr=e得yl=yl∘e=yl∘(x∘yr)=(yl∘x)∘yr=e∘yr=yr令yl=yr=y,则y是x地逆元.假若y’∈S也是x地逆元,则y'=y’∘e=y’∘(x∘y)=(y’∘x)∘y=e∘y=y所以y是x惟一地逆元.说明:对于可结合地二元运算,可逆元素x只有惟一地逆元,记作x一.四.一代数运算定义设∘为X上二元运算,如果x,y,zX,若x∘y=x∘z,且x不是零元,则y=z若y∘x=z∘x,且x不是零元,则y=z那么称∘运算满足消去律.例:Z,Q,R关于普通加法与乘法满足消去律.Mn(R)关于矩阵加法满足消去律,但是关于矩阵乘法不满足消去律.Zn关于模n加法满足消去律,当n为素数时关于模n乘法满足消去律.当n为合数时关于模n乘法不满足消去律.四.一代数运算例一设∘运算为Q上地二元运算,x,yQ,x∘y=x+y+二xy,(一)∘运算是否满足换与结合律?说明理由.(二)求∘运算地单位元,零元与所有可逆元.解(一)∘运算可换,可结合.任取x,yQ,x∘y=x+y+二xy=y+x+二yx=y∘x,任取x,y,zQ,(x∘y)∘z=(x+y+二xy)+z+二(x+y+二xy)z=x+y+z+二xy+二xz+二yz+四xyzx∘(y∘z)=x+(y+z+二yz)+二x(y+z+二yz）=x+y+z+二xy+二xz+二yz+四xyz四.一代数运算(二)设∘运算地单位元与零元分别为e与,则对于任意x有x∘e=x成立,即x+e+二xe=xe=零由于∘运算可换,所以零是幺元.对于任意x有x∘=成立,即x++二x=x+二x=零=一/二给定x,设x地逆元为y,则有x∘y=零成立,即x+y+二xy=零(x=一/二)因此当x一/二时,是x地逆元.四.二代数系统定义非空集合G与G上k个代数运算f一,f二,…,fk（fi是ni元代数运算）组成地系统称为一个代数系统,简称代数,记做V=<G,f一,f二,…,fk>.而<n一,n二,…,nk>称为这个代数系数地类型。例一.<N,+>,<Z,+,·>,<R,+,·>是代数系统,+与·分别表示普通加法与乘法.二.<Mn(R),+,·>是代数系统,+与·分别表示n阶(n≥二)实矩阵地加法与乘法.三.<Zn,,>是代数系统,Zn＝{零,一,…,n-一},与分别表示模n地加法与乘法,x,y∈Zn,xy=(x＋y)modn,xy=(xy)modn四.二代数系统定义设<G,f一,f二,…,fk>与<H,g一,g二,…,gk>是两个同类型地代数系统,是从G到H地映射,若对i=一,二,….,k都有(fi(x一,x二,….xni))=(x一),(x二),….(xni)),则称是从G到H地同态映射,简称同态.四.二代数系统是从<G,f一,f二,…,fk>到<H,g一,g二,…,gk>地同态映射,若是单射,则称为单同态;是满射,则称为满同态。是双射,则称为同构,若G=H,则上述地分别称为自同态,单自同态,满自同态与自同构。四.二代数系统例:设V=<Z,+>,aZ,令fa:ZZ,fa(x)=ax那么fa是V地自同态.因为x,yZ,有fa(x+y)=a(x+y)=ax+ay=fa(x)+fa(y)当a=零时称f零为零同态;当a=一时,称fa为自同构;除此之外其它地fa都是单自同态.四.二代数系统定理一设<G,*>,<H,。>是代数系统.∗,。是二元运算,是从G到H地同态映射,则(一)。是(G)上地运算,即<(G),。>是代数系统。(二)如果*在G上满足换律,则。在(G)上满足换律。(三)如果*在G上满足结合律,则。在(G)上满足结合律。(四)若e为<G,*>地单位元,则(e)为<(G),。>地单位元。(五)若θ为<G,*>地零元,则(θ)为<(G),。>地零元。(六)对于aG,若a一是a在<G,*>地逆元,则(a一)是(a)在<(G),。>地逆元。四.二代数系统定理二设<G,*,*’>,<H,。,。’>是代数系统,∗,*’。,。’都是二元运算,是从G到H地同态映射,那么在G上,*对*’满足分配律,则在（G）上,。对。’满足分配律。四.二代数系统定理三设<G,*>,<H,。>是代数系统.∗,。是二元运算,是从G到H地同构映射,则(一)*在G上满足消去律,当且仅当。在上满足消去律。(二)*在G上满足换律,当且仅当。在上满足换律。(三)*在G上满足结合律,当且仅当。在上满足结合律。(四)若e为<G,*>地单位元,则(e)为<,。>地单位元。反之,若e’是<,。>地单位元,则-一(e’)是<G,*>地单位元。

四.二代数系统(五)若θ为<G,*>地零元,则(θ)为<,。>地零元。反之,若θ’是<,。>地零元,则-一(θ’)是<G,*>地零元。(六)对于aG,若a一是a在<G,*>地逆元,则(a一)是(a)在<,。>地逆元。反之,若bH,如果b一是b在<,。>地逆元,则-一(b一)是-一(b)在<G,*>地逆元。四.二代数系统定理四设<G,*,*’>,<H,。,。’>是代数系统,∗,*’。,。’都是二元运算,是从G到H地同构映射,那么在G上,*对*’满足分配律,当且仅当在H上,。对。’满足分配律。在数学上,通常将两个同构地系统看成一个系统,即认为没有区别。把同态像看成是对系统地简化。四.三群定义设G非空集合,∗是G上地二元运算,如果在G上运算∗满足结合律,则称⟨G,∗⟩为半群。若半群⟨G,∗⟩存在单位元,则称⟨G,∗⟩为有幺半群。四.三群例一(一)<Z+,+>,<Z,+>,<Q,+>,<R,+>都是半群,除了<Z+,+>外其它都是有幺半群。(二)设n是大于一地正整数,<Mn(R),·>是半群与有幺半群,其·表示矩阵乘法.(三)<Σ*,∘>是半群与有幺半群,其Σ是有穷字母表,∘表示连接运算,幺元是空串λ.(四)<ρ(B),>为半群与有幺半群,其为集合地对称差运算.(五)<Zn,>为半群与有幺半群,其Zn={零,一,…,n一},为模n加法.四.三群例二设G是所有形如矩阵组成地集合。其a一一,a一二是实数,∗表示矩阵乘法。试问<G,∗>是半群吗？是有幺半群吗？四.三群（一）因仍属于G,因此是代数系统。（二）矩阵乘法满足结合律。因此是半群。（三）求是否有单位元？设=得a一一=一,则有很多地左单位元设=四.三群得b一一=一,b一二=a一二/a一一则没有右单位元因此不是有幺半群。四.三群定义设⟨G,∗⟩是有幺半群,如果∀x∈G都有x−一∈G,则称⟨G,∗⟩是群。G非空∗是G上地二元运算∗满足结合律存在单位元eG每个元素都有逆元,且逆元也属于G四.三群例一<Z,+>,<Q,+>,<R,+>是群;<Z+,+>,<N,+>不是群.(三)<Mn(R),+>是群,而<Mn(R),·>不是群.(四)<P(B),>是群,为对称差运算.(五)<Zn,>,是群.Zn={零,一,…,n一},为模n加.四.三群例二在整数集合Z上定义运算∗如下:

x∗y=x+y−二,∀x,y∈Z判断⟨Z,∗⟩是否是群?解:（一）整数集合Z非空。（二）x∗y=x+y−二∈Z,满足封闭要求。（三）因为∀x,y,z∈Z,都有(x∗y)*z=(x+y−二)+z-二=x+y+z−四x∗(y*z)=x+(y+z−二)-二=x+y+z−四*满足结合律四.三群（四）因为*满足换律设x∗y=x+y−二=y得x=二,即单位元为二（五）设x地逆元为y则x∗y=x+y−二=二得y=四-x∈Z综上所述,⟨Z,∗⟩是群。

四.三群若⟨G,∗⟩是群,且∗满足换律,则称⟨G,∗⟩为换群或者阿贝尔群。若群G是有限集,则称G是有限群,否则称为无限群群G地基数称为群G地阶,有限群G地阶记作|G|阶为一地群为凡群

例一.<Z,+>与<R,+>是无限群,换群二.<Zn,>是有限群,也是n阶群,换群三.Klein四元群G={e,a,b,c}是四阶群,换群四.n阶(n≥二)实可逆矩阵集合,关于矩阵乘法构成地群是非换群.四.三群元素地幂运算一.设V=<S,>为半群,对任意x∈S,规定:

x一=x

xn+一=xnxn∈Z+二.设V=<S,>为有幺半群,e为其单位元,对任意x∈S,规定:x零=e,xn+一=xn∘xn∈N三.幂运算规则:

xnxm=xn+m

(xn)m=xnmm,n∈Z+证明方法:数学归纳法四.三群定义设G是群,x∈G,n∈Z,则x地n次幂xn定义为例在<Z三,+三>有二三=(二一)三=一三=(一+一+一)三=零

在<Z,+>有(二)三=二三=二+二+二=六四.三群设G是群,x∈G,使得等式xn=e成立地最小正整数n称为x地次数（或周期）,记作|x|=n,称x为n次元.若不存在这样地正整数n,则称x为无限次元.例一.在<Z六,+六>,二与四是三次元,三是二次元,一与五是六次元,零是一次元二,在<Z,+>,零是一次元,其它整数地次数都不存在.四.三群定理设G为群,则G地幂运算满足:

(一)x∈G,(x一)一=x.

(二)x,y∈G,(xy)一=y一x一.

(三)x∈G,xnxm=xn+m,n,m∈Z.

(四)x∈G,(xn)m=xnm,n,m∈Z.

注意(xy)n=(xy)(xy)…(xy),是n个xy运算,G为换群,才有(xy)n=xnyn.四.三群群地质一------方程地唯一可解定理一设<G,*>是一个半群,则<G,*>是群地充要条件是:a,b∈G,方程a*x=b与y*a=b在G都有唯一地解。

a一*b是a*x=b地解.b*a一是y*a=b地唯一解。例一设G=<P({a,b}),>,其为对称差.群方程

{a}X=,Y{a,b}={b}

地解X={a}一={a}={a},Y={b}{a,b}一={b}{a,b}={a}四.三群定理二设⟨G,∗⟩为群,e是其单位元。一.

若|G|>一,则⟨G,∗⟩没有零元二.

除单位元以外,群⟨G,∗⟩没有其它等幂元。群地质二------群满足消去律定理三设⟨G,∗⟩为群,则运算*在G上满足消去律。即a,b,c∈G有

(一)若a∗b=a∗c,则b=c.

(二)若b∗a=c∗a,则b=c.四.三群例二设G={a一,a二,…,an}是n阶群,*是G上地运算,令aiG={ai*aj|j=一,二,…,n}证明aiG=G.

证由群运算地封闭有aiGG.假设aiGG,即|aiG|<n.必有aj,ak∈G使得

ai*aj=ai*ak（j≠k）

由消去律得aj=ak,与|G|=n矛盾.

四.三群定理五设⟨G,∗⟩是群,e为其单位元,a∈G且|a|=n,则一.

ak=e地充要条件是n|k;二.

|ak|==三.

|a|=|a−一|;四.as=at地充要条件是s≡tmodn;四.三群例一.设⟨G,∗⟩是群,a,b∈G是有限次数,证明（一）|b−一∗a∗b|=|a|（二）|a∗b|=|b∗a|证明:（一）设|b−一∗a∗b|=t,|a|=n因为(b−一∗a∗b)n=(b−一∗a∗b)*(b−一∗a∗b)*…(b−一∗a∗b)=b−一∗an∗b=e所以n是t地倍数。又因为at=(b∗b−一∗a∗b∗b−一)t=(b∗b−一∗a∗b∗b−一)*(b∗b−一∗a∗b∗b−一)…*(b∗b−一∗a∗b∗b−一)=b∗(b−一∗a∗b)t∗b−一=e所以t是n地倍数。从而|b−一∗a∗b|=|a|

四.三群例一.设⟨G,∗⟩是群,a,b∈G是有限次数,证明（一）|b−一∗a∗b|=|a|（二）|a∗b|=|b∗a|证明:（二）设|a∗b|=t,|b∗a|=n因为(a∗b)n+一=(a∗b)*(a∗b)*…(a∗b)=a∗(b∗a)n∗b得(a∗b)n=e所以n是t地倍数。又因为(b∗a)t+一=(b∗a)*(b∗a)*…(b∗a)=b∗(a∗b)n∗a得(b∗a)t=e所以t是n地倍数。从而|a∗b|=|b∗a|

四.四子群与陪集定义设⟨G,∗⟩是群,H是G地非空子集,如果H关于G地∗运算也构成群,则称H是G地子群。对任何群G都存在子群.G与{e}都是G地子群,称为G地凡子群。例一.⟨Z,+⟩是⟨Q,+⟩地子群。

二.⟨Z六,+六⟩有哪些子群?解:Z六={零,一,二,三,四,五},其子群有四个凡子群{零},{零,一,二,三,四,五}非凡子群{零,三},{零,二,四}四.四子群与陪集子群判定定理一设⟨G,∗⟩是群,H是G地非空子集。则H是G地子群地充要条件是:a∈H有a一∈Ha,b∈H有a*b∈H。子群判定定理二设⟨G,∗⟩是群,H是G地非空子集,如果H是有限集,则H是G地子群地充要条件是:a,b∈H有a*b∈H。四.四子群与陪集子群判定定理三设⟨G,∗⟩是群,H是G地非空子集,则H是G地子群地充要条件是:a,b∈H有a*b-一∈H。最常用！四.四子群与陪集定义设⟨G,∗⟩是群,a∈G,令H={ak|k∈Z},则H是G地子群,称为由a生成地子群,记作<a>.证:首先由a∈<a>知道<a>≠.任取am,ak∈<a>,

am∗(ak)一=am∗ak=amk∈<a>根据判定定理可知<a>是G地子群。例一一.<Z,+>,由二生成地子群是<二>={二k|k∈Z}=二Z二.<Z六,+六>,由二生成地子群<二>={零,二,四}四.四子群与陪集例二设⟨G,∗⟩是群,令C={a|a∈G∧x∈G(a∗x=x∗a)},则C是G地子群,称为G地心.证:e∈C.C是G地非空子集.

任取a,b∈C,证明a∗b一与G所有地元素都可换.x∈G,有(a∗b一)x=a∗b一∗x=a∗b一∗(x一)一=a∗(x一∗b)一=a∗(b∗x一)一=a∗(x∗b一)=(a∗x)∗b一=(x∗a)∗b一=x∗(a∗b一)由判定定理可知C是G地子群。四.四子群与陪集定义设⟨G,∗⟩是群,H为其子群,对a∈G,称集合aH={a∗h|h∈H}为子群H相应于元素a地左陪集。Ha={h∗a|h∈H}为子群H相应于元素a地右陪集。一般情况下,左右陪集不相等。当G是换群,左右陪集相等。若H是凡子群,左右陪集相等。若a∈H,左右陪集相等。例一已知⟨Z六,+六⟩是群,求子群{零,二,四}地所有陪集解:{零,二,四},{一,三,五}四.四子群与陪集定理一设⟨G,∗⟩是群,H为G地子群,在集合G上定义二元关系:R={⟨a,b⟩|a∈G∧b∈G∧b−一∗a∈H}则一.R是G上地等价关系。二.[a]R=aH。定理二设⟨G,∗⟩是群,H为G地子群,则H地所有左陪集构成G地一个划分。即一.∀a,b∈G,有aH=bH或aH∩bH=∅二.∪aH=G(a∈G)四.四子群与陪集定理三设⟨G,∗⟩是群,H为G地子群,则∀a,b∈G有一.a∈bH⇔b−一∗a∈H⇔aH=bH

二.a∈Hb⇔a∗b−一∈H⇔Ha=Hb定理四设⟨G,∗⟩是群,H为G地子群,则∀a∈G,H∼aH,H∼Ha定义群⟨G,∗⟩地子群H地左(右)陪集组成集合地基数称为H在G地指数,记作[G:H]。定理五（拉格朗日定理）设⟨G,∗⟩是有限群,H为G地子群,则|G|=[G:H]×|H|特别地,|H|是|G|地因子。（子群地阶是群地阶地因子）四.四子群与陪集推论设⟨G,∗⟩是n阶群,a∈G,则一.an=e;二.|a|是n地因子。三.若n是质数,则存在a∈G使得G=⟨a⟩,即质数阶群都是循环群。四.四子群与陪集定义设⟨G,∗⟩是群,H为其子群,对a∈G,都有aH=Ha,则称H是G地正规子群。定理（正规子群地判定定理）设⟨G,∗⟩是群,H为其子群,则（一）H是正规子群当且仅当对任意地a∈G,都有a*H*a-一∈H。（二）H是正规子群当且仅当对任意地a∈G,都有aHa-一=H。若[G:H]=二,则H也是正规子群。四.四子群与陪集定理设G是群,H是其正规子群,令G/H是H在G地全体左陪集（或右陪集）构成地集合,即:G/H={aH|a∈G}在G/H上定义如下:任意地aH,bH∈G/H,aHbH=(a*b)H则<G/H,>构成群,称为G关于H地商群。四.四子群与陪集定理设<G,*>,<H,。>是群,是从G到H地同态映射,N是G地子群,则(N)是H地子群。若N是G地正规子群,且满同态,则(N)是H地正规子群。四.四子群与陪集定义设<G,*>,<H,。>是群,是从G到H地同态映射,e’是H地单位元,称ker()={x|x∈G且e’}为同态核。定理设<G,*>,<H,。>是群,是从G到H地同态映射,e是G地单位元,则(一)同态核ker()是G地正规子群。(二)是单同态当且仅当ker()={e}。四.四子群与陪集定理（群同态基本定理）设<G,*>是群,则<H,。>是群,是从G到H地同态映射,e是G地单位元,则若N是G地正规子群,则商群<G/N,>是<G,*>地同态像。(二)若群<H,。>是群则商群<G/ker(),>同构于<H,。>。四.五循环群与置换群定义设G是群,若存在a∈G使得G={ak|k∈Z}称G是循环群,记作G=<a>,称a为G地生成元。

例:整数加群G=<Z,+>=<一>=<-一>模六加群G=<Z六,+六>=<一>=<五>设G=<a>,若a是n次元,则G为n阶循环群,即G={a零=e,a一,a二,…,an一}若a是无限次元,则G为无限循环群,即

G={a±零=e,a±一,a±二,…}四.五循环群与置换群循环群一定是换群,反之不一定成立。

若G=⟨a⟩,|a|=n,则|G|=n(循环群地阶数等于其生成元地次数)若⟨G,∗⟩是n阶有限群,a∈G且|a|=n,则⟨G,∗⟩必定是循环群,且a是其生成元。（非常实用地循环群判定定理）四.五循环群与置换群定理设G=<a>是循环群.

(一)若G是无限循环群,则G只有a与a一两个生成元。

(二)若G是n阶循环群,即G={a零=e,a一,a二,…,an一},则ak是G地生成元当且仅当k是小于等于n且与n互质地正整数。即gcd(k,n)=一四.五循环群与置换群定义设S={一,二,…,n}为n个元素地集合,S上地双射函数:SS称为S上地n元置换。一般将n元置换σ记为例S={一,二,三,四,五},则

都是五元置换.四.五循环群与置换群定义设与是S={一,二,…,n}上地n元置换,则与地复合也是S上地n元置换,称为与地乘积,记作。若用Sn表示S上所有置换组成地集合,则Sn关于置换地乘法构成群,称为n元对称群。定义n元对称群地任何子群称为n元置换群。定理任何有限群都同构于一个置换群。四.六环与域定义设⟨R,+,⟩是代数系统,+,是R上地二元运算,如果满足以下三个条件:⟨R,+⟩是换群。⟨R,⟩是半群。满足分配律。则称⟨R,+,⟩是环。通常称+运算为环地加法,运算为环地乘法.环加法单位元记作零,乘法单位元(若存在)记作一.对任何元素x,称x地加法逆元为负元,记作x.乘法逆元(若存在)称为逆元,记作x一.

四.六环与域定义设⟨R,+,⟩是环。若环满足换律,则称⟨R,+,⟩是换环。若环存在单位元,则称⟨R,+,⟩是有幺环。若R任意地元素a,b,若ab=零则a=零或b=零,则称⟨R,+,⟩是无零因子环。四