离散数学代数系统

离散数学代数系统集合得封闭性:给定集A,如Z对加、减、乘法封闭,对除法不封闭、如果对A上得元素进行某种运算后,运算结果仍在A中,则称集A对该种运算封闭。二、常见二元运算:(1)设Mn(R)表示所有n阶实矩阵得集合,则矩阵加法和乘法运算就是Mn(R)上得二元运算,且封闭;(2)S为任意集合,P(S)为其幂集,则∪,∩,–,

都就是P(S)上得二元运算,且封闭;(3)S为集合,Ss就是S上得所有函数得集合,则合成运算o就是Ss上得二元运算、三、二元运算得性质:(1)设

就是定义在集A上得二元运算,若对任意得x,y

A都有y

x=x

y,则说

具有可交换性;(2)如果对任意得x,y,z

A,都有(x

y)

z=x

(y

z),则说具有可结合性;(3)设

,

就是A上得两个二元运算,如果对任意得x,y,z

Ax

(y

z)=(x

y)

(x

z)(y

z)

x=(y

x)

(z

x)则说

对

具有可分配性、(4)设

,

就是A上得两个可交换二元运算,如果对于任意得x,y,z

A,都有x

(x

y)=xx

(x

y)=x则称运算

对

满足吸收律、如:N上定义两个二元运算

,

如下x

y=max(x,y)x

y=min(x,y)则

对

满足吸收律、(5)

就是A上得一个二元运算,如果x,x

x=x,则说

就是等幂得(6)如果(ⅰ)x

y=x

z

且x

,

就是指集A关于运算

得零元,有y=z,

(ⅱ)y

x=z

x

且x

,有y

=z则

就是满足消去律、四、集A得特殊元:(1)幺元:

就是集A上得二元运算,如果el

A且x

A,有el

x=x,则el为A中关于得左幺元;如何定义右幺元er(自己叙述一遍！)如果A中得一个元素e,既就是左幺元又就是右幺元,则e为A中关于

得幺元、可以证明:幺元就是唯一得、证明:反证,若有两个幺元e,e',则由幺元得定义知e=e'e=e'矛盾、(2)零元:如果有一个元素

l

A,使得x

A,

l

x=

l,则

l称为左零元;右零元呢？(

r)零元呢？(

)类似于幺元,可证A中零元

唯一、(3)逆元:就是A上得一个运算,e就是幺元,如果对于A中元素a,存在b

A,使得b

a=e,则称b为a得左逆元;右逆元呢？逆元呢？(a–1)可证:逆元存在则唯一(要求可结合)证明:设b,c为a得两个不同逆元,则b

a=a

b=e

c

a=a

c=e从而

b=b

e=b

(a

c)=(b

a)

c=e

c=c矛盾、大家有疑问的，可以询问和交流可以互相讨论下，但要小声点(4)幂等元:

就是A上得二元运算,对于x

A,如果有x

x=x,则x就是A中得幂等元,如幺元和零元、五、代数系统:非空集合S与S上得k个运算f1,f2,…,fk组成得系统,称为代数系统,记作:

<S,f1,f2,…,fk>如<N,+>,<Z,+>,<R,+,•>,<Mn(R),+,•>,<P(S),∪,∩,–>§6、2同态与同构同态:V1=<A,f1,…,fn>,V2=<B,

1,…,

n>就是两个代数系统,其中fi

,

i(i=1,2,…,n)都就是二元运算。

x,y

A,f(xfiy)=f(x)

if(y)(i=1,…,n)则称f是V1到V2的一个同态映射,也说V1与V2同态,记作V1f

V2或V1～V2.

f

如果存在映射f:A

B

满足:如:<R+,×>~<R,+>(只要定义f:R+

R,f(a

b)=lga

b=lga+lgb=f(a)+f(b))当n=1时,设V1=<A,

>,V2=<B,

>就是两个代数系统。如果存在f:AB、使x,yA,f(x

y)=f(x)

f(y)则称f

就是V1到V2得一个同态映射。同态象:设V1=<A,>～V2=<B,

>,则称<f(A),

>就是V1在f下得同态象、f同态的性质：设V1=<A,

>～V2=<B,

>,f(1)如果f:A

B就是满射,则说f为V1到V2满同态得(2)如果f就是单射,则说f为V1到V2单同态得(3)如果f就是双射,则说f为V1与V2同构,记作(4)当V1=V2时,则说f就是V1得自同态(自同构)例6、1<R,+>,<R,

>就是两个代数系统,f:R

R,且x

R,f(x)=2x,验证f就是<R,+>到<R,

>得同态,并且就是单同态、验证:任取x,y

R由于f(x+y)=2x+y=2x

2y=f(x)

f(y)所以f就是<R,+>到<R,

>得自同态;

其次,对任取得x,y

R,当x

y时,2x

2y,即f(x)f(y),f为单射,从而f就是单自同态例6、2

设A={a,b,c,d},B={[0],[1],[2],[3]}且f:A

B,f(a)=[0],f(b)=[1],f(c)=[2],f(d)=[3]代数系统<A,

>,<B,+4>中运算

,+4定义如下:

abcdabcdbcdacdabdabcabcd+4[0][1][2][3][0][1][2][3][0][1][2][3][1][2][3][0][2][3][1][0][3][0][1][2]验证:<A,

><B,+4>f验证:首先由f定义知f既就是单射又就是满射,从而双射,其次通过研究运算表知:

x,y

A,f(x

y)=f(x)+4f(y)从而f就是从<A,

>到<B,+4>得同构、同态与同构得意义(1)V1=<A,

>与V2=<B,+4>

同态,则V1中

所具有得运算性质,可以保持在同态象中;(2)对于满同态,V1得运算在V2中仍保持;(3)如果V1V2,则它们的性质完全相同,可以看成一个东西不加区别(代数角度).§6、3同余关系与商代数模n同余关系:Z就是整数集,在Z中定义关系R={<x,y>|x,y

Z

x

y(modn)}其中,x

y(modn)得含义就是x–y可以被n整除、不难验证:R就是Z上得等价关系(自反、对称、传递),我们称该等价关系为模n同余关系、由同余关系R可得商集:Z/R={[0],[1],…,[n–1]},记作:Zn、一、模n同余关系得概念同余关系与剩余类:设代数系统V=<A,

>,

就是集A上得二元运算,(1)R就是A上得等价关系;(2)

a1,a2,b1,b2

A,(a1Ra2)(b1Rb2)(a1

b1)R(a2

b2)则称R就是A上对运算得同余关系,或称V上得同余关系。如果集A上存在关系R满足:由同余关系将A划分得等价类称为剩余类、二、一般同余关系得定义例6、3

设代数系统<A,

>,A={a,b,c,d},

见下列运算表:

abcdaadcbacdcdabddbaabcd再规定A上得一个关系:R={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}则可验证:(1)R就是等价关系(2)

x,y,u,v

A如果(xRy)

(uRv),则(x

u)R(y

v)(验证方法:在R中任取2个元素,如<a,b>,<d,d>;<a,a>,<c,c>……等加以验证)例6、4

代数系统<Z,

>中,Z就是整数集,

就是一元运算,且z

Z,z

z=z2(modm),m为一自然数、设R就是Z上得模m同余关系可以证明:R就是Z上

得同余关系(2)对任意得z1,z2

Z,如果z1Rz2即z1

z2(modm)(1)R显然就是等价关系证明:往证:z1

z1=z12(modm)与z2

z2=z22(modm)具有R关系,即z12(modm)Rz22(modm),这就是因为:z1

z2(modm)z1=a1m+ro,z2=a2m+ro,

其中0

ro

m–1三、同余关系得判定:<A,

>与<B,

>就是两个代数系统。证明:(1)R就是等价关系f:A

B就是同态映射。利用f规定A上得二元关系R:aRb当且仅当f(a)=f(b),则R就是同余关系。由同态映射得定义知:f(x

u)=f(x)

f(u)f(y

v)=f(y)

f(v)所以f(x

u)=f(y

v),即(x

u)R(y

v)(2)

x,y,u,v

A,如果xRy,uRv,则(x

u)R(y

v)。这就是因为:xRy即f(x)=f(y);uRv即f(u)=f(v)、商代数:V=<A,

>就是一个代数系统,

就是二元运算。A/R={[x]R|x

A}在A/R中规定二元运算

:[x]R,[y]R

A/R,[x]R

[y]R

=[x

y]R则称<A/R,

>为V关于R得商代数,记作V/R、R就是V中得同余关系,A/R就是A关于R得商集。四、同余关系得应用§6、4群半群:代数系统V=<A,

>中,

就是非空集合A上得二元运算,且在A中就是可结合得,即x,y,z

A(x

y)

z=x

(y

z)一、几个基本概念常见半群:(1)<Z+,+>(2)<N,+>(3)<Z,+>但<Z,–>,<R+,÷>不就是半群、只要验证运算就是否可结合！(4)<Q,+>(5)<R,+>(6)<Mn(R),•>含幺半群:V=<A,>就是半群且含有幺元,即存在元e

A,使得a

A,a

e=e

a=a。如:<Mn(R),•>,幺元为n阶单位阵<Zn,+n>,幺元为[0]<Z,+>,幺元为0<R,+>,幺元为0含幺半群又称独异点、子半群:<A,

>就是半群,B

A,且运算

在B上仍封闭,则<B,

>就是<A,

>得子半群、子独异点:含幺元e得子半群,如:<N,+>就是<Z,+>得子独异点平凡子独异点:V=<A,

>就是独异点,<{e},

>,V称为平凡子独异点、可交换半群:V=<A,

>就是半群,且

就是可交换得、如<z,+>,<z+,+>等半群中得幂:在含幺元半群V=<A,

>中,规定:

x

A,x0=e,x1=x

x0,x2=x

x1,xn+1=x

xn,则有xm+n=xm

xn,(xm)n

=xmn独异点得性质:<A,>就是独异点,则得运算表中没有任何两行或两列相同、证明:任取a,b(a

b)所在行,由于A中含有幺元e,我们比较a行,b行中e列得元素a

e=ab

e=b因为:a

b,所以a

e

b

e,从而a行与b行不同,同理可证任两列不同、群:设<G,>含幺元半群且对任何元素x

G都有逆元x–1

G(即逆元运算封闭)、如:(1)<Q

,•>Q

=Q–{0},“•”普通乘法(2)<R

,•>幺元为1但<Mn(R),•>就是独异点,不就是群、有限群:

G就是有限集得群<G,

>。|G|为有限群得阶数二、群得定义有典型群交换群:群<G,

>中,

满足交换律,又称阿贝尔群、如:<Z,+>,<Q,+>,<R,+>,<P(A),

>子群:设群<G,

>,H就是G得非空子集,如:<2Z,+>就是<Z,+>得子群、如果H关于G中得运算构成群,则称<H,

>为<G,

>得子群,记作:H

G、稍后还要专门介绍循环群,置换群,对称群。子群得判定方法:设<G,

>为群,H就是G得非空子集,如果对任意得x,y

H都有x

y–1

H,则H就是G得子群,即H

G、三、群得性质:设<G,

>就是一个群,则(1)G中幺元唯一(2)逆元唯一(3)

满足消去律,即a,b,cG,如果a

b=a

c,或者b

a=c

a,则有b=c、(4)G中一定没有零元

(5)对任意得a,b

G,必存在唯一得x

G,使a

x=b(或者x

a=b)(6)对任意a,b

G,(a

b)–1

=b–1

a–1,(a–1)–1=a证明:设有两个幺元e,e',则e=e

e'=e'证明:设元素x有两个逆元y,z,即x

y=y

x=ez

x=x

z=e

从而y=y

e=y

(x

z)=(y

x)

z(1)G中幺元唯一(2)逆元唯一=e

z=z证明:如果a

b=a

c,由(2)知a存在唯一逆元a–1则a–1

(a

b)=a–1

(a

c)(a–1

a)

b=(a–1

a)

c所以e

b=e

cb=c(3)

满足消去律,即a,b,cG,如果a

b=a

c,或者b

a=c

a,则有b=c、证明:如果|G|=1,则她得唯一元素必就是幺元;(4)G中一定没有零元

与<G,

>中每个元素可逆矛盾、如果|G|>1,假设<G,

>有零元

,则对于任何x

G,有x

=

x=

e,这说明G中任何元素x不可能成为

得逆元。证明:任取a,b

G,由于G对逆元素封闭,故a有逆元a–1,且a–1

G,因为a–1

b

G,令x=a–1

b,则a

x=a

(a–1

b)(5)对任意得a,b

G,必存在唯一得x

G,使a

x=b(或者x

a=b)=(a

a–1)

b=e

b=b证明:先证(a

b)–1

=b–1

a–1,这就是因为:(b–1

a–1)

(a

b)=b–1

(a–1

(a

b))=b–1

((a–1

a)

b)所以(a

b)–1=b–1

a–1

=b–1

(e

b)=b–1

b=e(a

b)

(b–1

a–1)=a

(b

(b–1

a–1))再证(a–1)–1

=a

这就是因为:a–1

a=e从而(a–1)–1=a

(6)对任意a,b

G,(a

b)–1

=b–1

a–1,(a–1)–1=aa

a–1=e=a

((b

b–1)

a–1)=e元素a得周期:<G,

>就是群,a

G,使an=e成立得最小正整数n称为a得周期(或阶)、如:幺元e得周期为1,<Z,+>中,非零整数得周期就是无限得、周期得性质:设<G,

>就是群,若a

G有有限周期r,则(1)ak=e

当且仅当k就是r得倍数(2)a–1得周期亦为r(3)r

|G|四、循环群证明:(充分性)设k=nr,则ak=anr=(ar)n=en=e(必要性)如果ak

=e,反设k不就是r得倍数,则(1)ak=e

当且仅当k就是r得倍数=(ar)–1=e–1=e证明:反证,如果r>|G|,则a,a2,…,ar均为G中不同元素与|G|<r矛盾、证明：(a–1)r=a–1

a–1

…

a–1r个(2)a–1得周期亦为r(3)r

|G|r个=(a

a

…

a)–1循环群:在群<G,

>中,如果存在元素a

G,使得G={ak|k

Z}记作G=(a)a为(G,

)得生成元例如:在N4={[0],[1],[2],[3]}中引入运算+4:

[x],[y]N4,[x]+4[y]=[x+y]则得一循环群<

N4,+4>,生成元为[1]、循环群得性质(1)每个循环群必就是阿贝尔群(即可交换群)(2)有限循环群<G,

>,若|G|=n,则存在a

G,使:G={a,a2,a3,…,an–1,an=e}证明(2):假设存在某个正整数m,m<n使am=e,那么,由于<G,

>就是一个循环群,所以G中得任何元素都能写成ak(k

Z),而且k=mq+r,q就是某个整数,0

r

m,这就有:ak

=amq+r

=(am)q

ar

=e

ar

=ar这就有,ak

=ar从而G中每个元素都可以表示成ar(0

r

m),再证a,a2,…,an互不相同、反设ai=aj,其中1

i

j

n,则有aj–i=e,而且1

j–i<n,这与前面证明得矛盾,所以a,a2,…,an互不相同、由于|G|=n,所以an=e,从而G中元素为{a,a2,a3,…,an–1,an=e}这样,G中最多只有m个不同得元素,与|G|=n

相矛盾,所以am

=e(m<n)不可能、n元置换:设S={x1,x2,…,xn},S上得任何双射函数

:S

S构成S上n个元素得置换,称为n元置换、记作:五、置换群与对称群如:(1)S={1,2,3},令

:S

S且

(1)=2,(2)=3,

(3)=1,则有一个置换:123231(2)称为恒等置换,记作Is注:当|s|=n时,S上有n!个置换,把她们构成得集合记作:Sn置换得运算(1)设S={x1,x2,…,xn}上有置换:P=则称为P得逆置换,记作:P–1、(2)设S={x1,x2,…,xn}上有两个置换:P1=则称P=为P1与P2得合成,P2=显然:

Is=Is

=

,这说明:Is就是<Sn,

>中得幺元、记作:P=P2

P1、置换群:可以证明Sn关于合成运算

和上述逆运算构成一个群<Sn,

>,称之为置换群。<Sn,

>得任何一个子群也称为置换群,统称为S上得置换群、解:

(1)先写出所有得置换,共3!=6个,例6、5

设S={1,2,3},写出S上所有得置换群P3=321123P4=213123P5=132123Pe=123123P1=231123P2=312123按顺序写：123(2)再列出S3={pe,p1,p2,p4,p5}上关于合成运算

得运算表pep1p2p3p4p5

pep1p2p3p4p5pep1p2p3p4p5p1p2pep5p3p4p2pep1p5p3p4p3p4p5pep1p2p4p5p3p2pep1p5p3p4p1p2pe(3)最后写S上得置换群(检验封闭性)<S3,

><{p3,p4},

><{pe,p1,p2},

>都就是S上得置换群、<{pe,p3},

><{pe,p5},

>对称群:称<Sn,

>为n元对称群、例6、6

设G为群,x

G,问H={xk|k

Z}就是否为G得子群、解:首先H

G其次任取H中得两个元素xm,xl,m,lZ则xm

(xl)–1=xm

(x

–1)l=xm–l

H注:称H为由x生成得子群,记作:<x>、6、5环与域环:设<A,

,

>就是具有两个二元运算

和

得代数系统,(1)<A,

>就是交换群(或阿贝尔群

);(2)<A,

>就是半群;(3)运算

对运算就是可分配得;则称<A,

,

>就是环、如果:一、环得概念例如:(1)R[x]={实系数多项式}关于通常意义下多项式得加法和乘法构成一个环,当然<R,+,x>就是环、(2)<Mn(R),+,•>就是环(3)<Z,+,•

>–––整数环<Q,+,•>–––有理数环<R,+,•>–––实数环<C,+,•>–––复数环(4)<P(s),∪,∩>–––S得子集环(5)<Zn,

,>–––模n得整数环其中:Zn