離散課件 9代數(shù)系統(tǒng)

第九章

代數(shù)系統(tǒng)9.1二元運算及其性質(zhì)9.2代數(shù)系統(tǒng)9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)思想：用抽象的數(shù)去度量和處理任意對象.代數(shù)系統(tǒng)不關(guān)心具體“數(shù)”的研究，而是專注于抽象的代數(shù)元素及其運算！一、二元運算定義：設(shè)S為集合,函數(shù)f:S×S→S稱為S上的二元運算，簡稱為二元運算。

f:S→S稱為S上的一元運算例如

f:N×N→N,

f(<x,y>)=x+y

是N上的二元運算

f:N→N,

f(x)=x+1是N上的一元運算9.1二元運算及其性質(zhì)通常用?,*,?等符號表示二元運算,稱為算符如二元運算中f(<x,y>)=z,可用算符簡記為x?y=z一元運算中f(x)=y,可用算符簡記為?x=y注:(1)S上的二元運算即x,yS,x?yS;(2)S上的一元運算即xS,?xS.運算封閉例1.(1)N上加法,乘法都是二元運算,但減法,除法不是.

(2)Z上加法,乘法,減法都是二元運算,但除法不是.Z上求相反數(shù)的運算是一元運算.

(3)非零實數(shù)集R*上的乘法和除法都是二元運算.但加法,減法不是,而求倒數(shù)是一元運算.(4)Mn表示所有n階實矩陣的集合(n≥2),則矩陣的加法和乘法都是二元運算,矩陣的轉(zhuǎn)置是一元運算.(5)集合S的冪集P(S)上的∪∩-⊕都是二元運算,而絕對補集(S為全集)是一元運算.

(6)所有命題公式的集合上的,,,都是二元運算,而為一元運算.

(7)SS表示集合S上的所有函數(shù)的集合,函數(shù)的復(fù)合運算?是SS上的二元運算.

例2.

判斷普通的加法和乘法運算在下列集合中是否為二元運算.

S1={1,2}

S2={0,1}

S3={2x|xZ+}

S4={2x-1|xZ+}

S5={2n|nZ+}(1)加法、乘法都不是；(2)加法不是，乘法是；(3)加法、乘法都是；(4)加法不是，乘法是；(5)加法不是，乘法是.當(dāng)S為有限集時,S上的一元和二元運算都可以用運算表給出.例3.(1)設(shè)S={1,2},給出P(S)上的運算絕對補集和對稱差的運算表,其中S為全集.(2)設(shè)S={0,1,2,3,4},定義S上的兩個二元運算如下:x?y=(x+y)mod5,x,yS

xy=(xy)mod5,x,yS求運算?和的運算表.二、二元運算的運算律設(shè)?和是S上的二元運算，x,y,zS1.若x?y=y?x,則稱?在S上可交換(?滿足交換律)2.若(x?y)?z

=x?(y

?z),則稱?在S上可結(jié)合(?滿足結(jié)合律)3.若x

(y?z)=(x

y)

?(x

z),

(y

?z)x

=(y

x)

?(z

x),

則稱運算對?是可分配的(對?滿足分配律)

4.若x?x=x,則稱?滿足冪等律5.若?和均可交換,x(x?y)=x,x?(xy)=x,

則稱?和滿足吸收律例4.(1)普通的加法和乘法在N,Z,Q,R上都是可結(jié)合的,且是可交換的,乘法對加法是可分配的.(2)矩陣的加法和乘法在Mn上是可結(jié)合的,加法可交換,但乘法不可交換,乘法對加法是可分配的.

(3)∪,∩,在冪集P(S)上可結(jié)合,可交換,∪和∩是互相可分配的,∪和∩滿足吸收律.(4),在全體命題公式集合上可結(jié)合,可交換,和是相互可分配的，且滿足吸收律.三、一些特殊元素設(shè)?是S上的二元運算，1.幺元e:若eS,對xS,e?x=x?e=x,則稱e為運算?的幺元

注：(1)若幺元存在,則必唯一.(2)若只有el?x=x或只有x?er=x,則el稱為左幺元,er稱為右幺元.(3)若左幺元和右幺元都存在,則必相等.例如：在N,Z,Q,R上,加法的幺元是0,乘法的幺元是1.在Z上的減法運算沒有幺元,只有右幺元0(x-0=x).在Mn上,矩陣加法的幺元是n階0矩陣,矩陣乘法的幺元是n階單位矩陣.在冪集P(S)上,運算∪的幺元是,運算∩的幺元是全集S.例5.

在R*(非零實數(shù)集)上定義運算如下:

a?b=a

a,bR*則R*中任何元素都是右幺元,但無左幺元,從而無幺元.2.零元θ:若θS,對xS,θ?x=x?θ=θ,則稱θ為運算?的零元.注：(1)若零元存在,則必唯一.(2)若只有θl?x=θl或只有x?θr=θr,則θl稱為左零元,θr稱為右零元.(3)若左零元和右零元都存在,則必相等.如例4(a?b=a),R*的任何元素都是左零元,但沒有右零元,從而沒有零元.例如：在N,Z,Q,R上加法沒有零元,乘法的零元是0.在Mn上矩陣加法沒有零元,矩陣乘法的零元是n階0矩陣.在冪集P(S)上,運算∪的零元是全集S,運算∩的零元是.定理：設(shè)?為S上的二元運算,e和θ分別為?的幺元和零元.如果|S|2,則eθ.3.逆元:設(shè)?是S上的二元運算,eS為運算?的幺元.若對xS,存在x-1S,x-1?x=x?x-1=e,則稱x-1為x的逆元.注：(1)逆元是針對某個元素而言的.(可能有的元素有逆元，有的沒有)(2)若只有xl-1?x=e或只有x?xr-1=e,xl-1稱為左逆元,xr-1稱為右逆元.(3)若二元運算?滿足結(jié)合律且x的左逆元和右逆元都存在,則左、右逆元必相等.例如：普通加法運算在N,Z,Q,R上有幺元0，僅在Z,Q,R上任意元素x有逆元(-x),在N上只有0有逆元0,而其他自然數(shù)都沒有逆元.在Mn上矩陣的乘法只有可逆矩陣存在逆元.冪集P(S)上關(guān)于運算∪有幺元,但除了外,其余元素都沒有逆元.例6.

在實數(shù)集R上定義運算如下：a,bR,ab=a+b+2ab是R上的二元運算嗎？在R上滿足交換律、結(jié)合律嗎？R關(guān)于有幺元、零元嗎？R關(guān)于每個元素有逆元嗎？(1)是；(2)滿足交換律、結(jié)合律；(3)0為幺元，-1/2是零元；(4)-1/2無逆元，其余元素均有逆元.例7.

設(shè)A={a,b,c,d}，二元運算?和如下表定義,問：運算?和是否可交換？是否有零元？是否有幺元？如果有幺元,指出哪些元素有逆元,逆元是什么？(1)(2)解：(1)運算?可交換,沒有零元,a是幺元;a,b,c,d都有逆元,a-1=a,c-1=c,b,d互為逆元;(2)運算不可交換,a是左零元,b是幺元,只有b有逆元,b-1=b,由于cd=b,故c是d的左逆元,d是c的右逆元,但a,c,d的逆元都不存在.四、二元運算運算律的補充設(shè)?是S上的二元運算,θ為?的零元,x,y,zS若x?y=x?z且xθ,則y=z;若y?x=z?x且xθ,則y=z;則稱?滿足消去律,其中(1)稱為左消去律,(2)稱為右消去律.9.2代數(shù)系統(tǒng)一、代數(shù)系統(tǒng)定義1.

非空集合S和S上的k個一元或二元運算f1,f2,…,fk組成的系統(tǒng)稱為一個代數(shù)系統(tǒng),簡稱代數(shù),記作<S,f1,f2,…,fk>.例如:<N,+>,<Z,+,?>,<R,+,?>,<Mn,+,?>,<P(S),∪,∩,>定義2.在某些代數(shù)系統(tǒng)中對于給定的二元運算存在幺元或零元，它們對該系統(tǒng)的性質(zhì)起著重要作用，稱為代數(shù)常數(shù)

(特異元素)例如:<Z,+>的幺元是0,也可記為<Z,+,0><P(S),∪,∩,>中∪和∩的幺元分別為和S,同樣可記為<P(S),∪,∩,,,S>

定義3.

如果兩個代數(shù)系統(tǒng)中運算的個數(shù)相同,對應(yīng)運算的元數(shù)相同,且代數(shù)常數(shù)的個數(shù)也相同,則稱這兩個代數(shù)系統(tǒng)具有相同的構(gòu)成成分(同類型的代數(shù)系統(tǒng)).例如:<R,+,?,–,0,1>和<P(S),∪,∩,,,S>都含有兩個二元運算、一個一元運算和兩個代數(shù)常數(shù)，因而它們是同類型的代數(shù)系統(tǒng).同類型的代數(shù)系統(tǒng)不一定具有相同的運算性質(zhì).定義4.

設(shè)V=<S,f1,f2,…,fk>是代數(shù)系統(tǒng),BS,如果B對f1,f2,…,fk都是封閉的,且B和S含有相同的代數(shù)常數(shù),則稱<B,f1,f2,…,fk>是V的子代數(shù)系統(tǒng),簡稱子代數(shù).有時將子代數(shù)系統(tǒng)簡記為B.例如：

<N,+>是<Z,+>的子代數(shù)，<N,+,0>是<Z,+,0>的子代數(shù)；但<N*,+>是<Z,+>的子代數(shù),卻不是<Z,+,0>的子代數(shù).定義4.

設(shè)V=<S,f1,f2,…,fk>是代數(shù)系統(tǒng),BS,如果B對f1,f2,…,fk都是封閉的,且B和S含有相同的代數(shù)常數(shù),則稱<B,f1,f2,…,fk>是V的子代數(shù)系統(tǒng),簡稱子代數(shù).有時將子代數(shù)系統(tǒng)簡記為B.注:(1)子代數(shù)與原代數(shù)是同類型的代數(shù)系統(tǒng),而且對應(yīng)的二元運算都具有相同的運算性質(zhì).(2)B=V是V最大的子代數(shù)；

B={V中的代數(shù)常數(shù)}是V最小的子代數(shù)；統(tǒng)稱為平凡子代數(shù).(3)當(dāng)BV時,B是V的真子代數(shù).例1.

設(shè)V=<Z,+,0>,令

nZ=<nz|zZ>,n為自然數(shù)，

則nZ是V的子代數(shù).證明：任取nZ中兩個元素nz1,nz2(z1,z2

Z),則有nz1+nz2=n(z1+z2)nZ,即nZ對+運算是封閉的.又0=n?0nZ,所以nZ是V的子代數(shù).注：當(dāng)n=1時,nZ=Z;

當(dāng)n=0時,0Z={0};它們是V的平凡子代數(shù),而其他的子代數(shù)都是V的非平凡的真子代數(shù).二、積代數(shù)定義5.

設(shè)V1=<S1,?>,V2=<S2,>是同類型的代數(shù)系統(tǒng),?和為二元運算.令S=S1S2,對<x1,y1>,<x2,y2>S1S2,<x1,y1>?<x2,y2>=<x1?x2,y1y2>,則<S,?>為代數(shù)系統(tǒng),稱為V1與V2的積代數(shù),記作V1V2.也稱V1和V2為V1V2的因子代數(shù).例如：V1=<Z,+>,V2=<M3,>對<z1,A>,<z2,B>ZM3,<z1,A>?<z2,B>=<z1+z2,AB>,故V1V2=<ZM3,?>.V1有代數(shù)常數(shù)0,V2有代數(shù)常數(shù)I3,V1V2有代數(shù)常數(shù)<0,I3>.定理：設(shè)V1=<S1,?>,V2=<S2,>是同類型的代數(shù)系統(tǒng),V1V2=<S1S2,?>.如果?和運算是可交換(可結(jié)合、冪等)的,那么?運算也是可交換(可結(jié)合、冪等)的；

如果e1和e2(θ1和θ2)分別為?和運算的幺元(零元),那么<e1,e2>(<

θ1,θ2>)也是?運算的幺元(零元)；

如果x和y分別為?和運算的可逆元素,那么<x,y>也是?運算的可逆元素,其逆元就是<x-1,y-1>.注：積代數(shù)也保留因子代數(shù)的分配律和吸收律等性質(zhì)，但不保留消去律.例：

V1=<Z,?>,V2=<Z,?>，

V1和V2中的?運算都滿足消去律；

V1V2中?運算不滿足消去律<0,1>?<2,3>=<0,3>=<0,1>?<4,3><0,1>不是零元,若消去,則<2,3>=<4,3>,錯誤.9.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)定義1.

設(shè)V1=<S1,?>,V2=<S2,>是同類型的代數(shù)系統(tǒng),如果存在映射f:S1→S2滿足對x,yS1有

f(x?y)=f(x)f(y),則稱f是V1到V2的同態(tài)映射,簡稱同態(tài)．xyf(x)f(y)x?yf(x?y)=f(x)f(y)先運算后取像等同于先取像后運算定義1.

設(shè)V1=<S1,?>,V2=<S2,>是同類型的代數(shù)系統(tǒng),如果存在映射f:S1→S2滿足對x,yS1有

f(x?y)=f(x)f(y),則稱f是V1到V2的同態(tài)映射,簡稱同態(tài)．注:(1)若f是單射,則稱為單同態(tài);

若f是滿射,則稱為滿同態(tài),記作V1V2;

若f是雙射,則稱為同構(gòu),記作V1V2(2)若f:VV,則稱為自同態(tài).例1.(1)設(shè)V1

=<Z,＋>,V2=<Zn,>,其中＋是普通加法,是模n加法,令f:Z→Zn,f(x)=(x)modn,證明:

f是V1到V2的滿同態(tài).證:顯然f是滿射.x,y∈Z,

f(x＋y)=(x＋y)modn=(x)modn(y)modn

=f(x)f(y),所以f是V1到V2的滿同態(tài).

f(0)=(0)modn=0注:

滿同態(tài)映射把幺元映到幺元.例1.(2)設(shè)V=<Z,＋>,給定a∈Z,令fa:Z→Z,fa(x)=ax,x∈Z,證明:fa

是V的自同態(tài).證:任取z1,z2∈Z,有

fa(z1＋z2)=a(z1＋z2)=az1＋az2

=fa(z1)＋fa(z2),所以

fa

是V的自同態(tài).注:

a=0時,f0(x)=0(x∈Z),稱為零同態(tài);

a=1時,f1(x)=x(x∈Z),稱為自同構(gòu);

a0,1時,fa

都是單同態(tài)性質(zhì)1.設(shè)f是V1=<S1,?>到V2=<S2,>的滿同態(tài),則若?可交換,則也可交換;若?可結(jié)合,則也可結(jié)合;

若e是關(guān)于?的幺元,則f(e)是關(guān)于