離散數(shù)學(xué)-第五章代數(shù)系統(tǒng)的一般性質(zhì)

代數(shù)系統(tǒng)的一般性質(zhì)——理學(xué)院數(shù)學(xué)系仝輝內(nèi)容提綱二元運(yùn)算及其性質(zhì)代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)代數(shù)系統(tǒng)的同態(tài)與同構(gòu)二元運(yùn)算定義5.1:設(shè)S為集合,函數(shù)f:SxSS稱為S上的一個(gè)二元運(yùn)算,簡(jiǎn)稱為二元運(yùn)算.f:SxSS,f(<x,y>)=x+y就是自然數(shù)集合N上的一個(gè)二元運(yùn)算,即普通的加法運(yùn)算.普通的減法不是自然數(shù)集合上的二元運(yùn)算,因?yàn)閮蓚€(gè)自然數(shù)相減可能不是自然數(shù),這時(shí)也稱集合N對(duì)減法運(yùn)算不封閉.驗(yàn)證方法:參加運(yùn)算的兩個(gè)元素是S中的任意兩個(gè)元素,而運(yùn)算的結(jié)果也是S中的一個(gè)元素.例題自然數(shù)集合N上的乘法是N上的二元運(yùn)算,但除法不是.整數(shù)集合Z上的加法,減法和乘法是Z上的二元運(yùn)算,而除法不是.非零實(shí)數(shù)集合R*上的乘法和除法都是R*上的二元運(yùn)算,而加法,減法不是.S為任意集合,則

,,-,為S的冪集P(S)上的二元運(yùn)算.通常用o,*,,...等符號(hào)表示二元運(yùn)算,稱為算符.設(shè)f:SxSS是S上的二元運(yùn)算,對(duì)任意的x,yS,如x與y的運(yùn)算結(jié)果為z,即

f(<x,y>)=z,

可用算符o簡(jiǎn)記為

xoy=z.n元運(yùn)算定義5.2:設(shè)S為集合,n為正整數(shù),則函數(shù)

f:SxSx...xSS

稱為S上的一個(gè)n元運(yùn)算,簡(jiǎn)稱為n元運(yùn)算.求一個(gè)數(shù)的相反數(shù)是實(shí)數(shù)集R上的一元運(yùn)算;在空間直角坐標(biāo)系中求某一點(diǎn)(x,y,z)的坐標(biāo)在x軸上的投影可以看作是實(shí)數(shù)集R上的三元運(yùn)算f(<x,y,z>)=x,因?yàn)閰⒓舆\(yùn)算的有序的3個(gè)實(shí)數(shù),而結(jié)果也是實(shí)數(shù).若f(<a1,a2,...,an>)=b,則可記為(前綴表示法)

o(a1,a2,...,an)=b

o(a)=b一元運(yùn)算,

o(a1,a2)=b二元運(yùn)算.運(yùn)算表aio(ai)a1o(a1)a2o(a2)......ano(an)oa1a2...ana1a1oa1a1oa2...a1oana2a2oa1a2oa2...a2oan...............ananoa1anoa2...anoan例題設(shè)S={1,2},給出P(S)上的運(yùn)算~和的運(yùn)算表,其中全集為S.

{1}{2}{1,2}

{1}{2}{1,2}{1}{1}

{1,2}{2}{2}{2}{1,2}

{1}{1,2}{1,2}{2}{1}

ai~(ai)

{1,2}{1}{2}{2}{1}{1,2}

交換律定義5.3:設(shè)o為S上的二元運(yùn)算,如果對(duì)任意的x,yS都有xoy=yox,則稱運(yùn)算o在S上是可交換的,或者說(shuō)o在S上適合交換律.例如加法,乘法符合交換律,但減法和除法不符合.結(jié)合律定義5.4:設(shè)o為S上的二元運(yùn)算,如果對(duì)任意的x,yS都有(xoy)oz=xo(yoz),則稱運(yùn)算o在S上是可結(jié)合的,或者說(shuō)o在S上適合結(jié)合律.普通的加法和乘法在N,Z,Q,R上都是可結(jié)合的.,,在冪集P(S)上也是可結(jié)合的.對(duì)滿足結(jié)合律的運(yùn)算可去掉括號(hào).

(x+y)+(z+u)=x+y+z+u

xoxoxo...ox=xn

xmoxn=xm+n冪等律定義5.5:設(shè)o為S上的二元運(yùn)算,如果對(duì)任意的xS都有xox=x,則稱運(yùn)算o在S上適合冪等律.也可以說(shuō)S中的全體元素都是冪等元.P(S)上的和運(yùn)算適合冪等律;對(duì)稱差不符合:AAA.分配律定義5.6:設(shè)o和*為S上的兩個(gè)二元運(yùn)算,如果對(duì)任意的x,y,zS都有

x*(yoz)=(x*y)o(x*z),

(yoz)*x=(y*z)o(z*x),

則稱運(yùn)算*對(duì)o是可分配的,或者說(shuō)*對(duì)o適合分配律.乘法對(duì)加法.P(S)上的,是相互可分配的.吸收律定義5.7:設(shè)o和*為S上的兩個(gè)二元運(yùn)算,如果對(duì)任意的x,yS都有

x*(xoy)=x,

xo(x*y)=x,

則稱運(yùn)算*和o滿足吸收律.P(S)上和滿足吸收律.幺元定義5.8:設(shè)o為S上的二元運(yùn)算,如果存在元素el(或er)S使得對(duì)任何xS都有

elox=x(或xoer=x),則稱el(或er)是S 中關(guān)于運(yùn)算o的一個(gè)左幺元(右幺元),若eS關(guān)于o既是左幺元又是右幺元,則稱e為S上關(guān)于運(yùn)算o的幺元.自然數(shù)集合上加法的幺元是0,乘法的幺元是1;矩陣的加法幺元是全0矩陣,矩陣的乘法幺元是主對(duì)角線為1,其它為0的矩陣.P(S)上,U運(yùn)算的幺元是,的幺元是S.判斷幺元對(duì)于給定的集合和運(yùn)算有的存在幺元,有的不存在幺元.R*是非零實(shí)數(shù)集,o是R*上的二元運(yùn)算,任取a,bR*有

aob=a,那么不存在el使得對(duì)所有的bR*都有

elob=b,所以運(yùn)算o沒(méi)有左幺元.但對(duì)任意的aR*,對(duì)所有的bR*,都有boa=b,所以,任意R*的元素a都是運(yùn)算o的右幺元.R*中有無(wú)數(shù)多的右幺元,但沒(méi)有幺元.定理定理5.1:設(shè)o為S上的二元運(yùn)算,el,er分別為運(yùn)算o的左幺元和右幺元,則有

el=er=e.

且e為S上關(guān)于運(yùn)算o的唯一的幺元.證明:el=eloer

eloer=er

el=er

把el=er記作e,假設(shè)S中存在幺元e’,則有

e’=eoe’=e.

所以,e是S中關(guān)于運(yùn)算o的唯一的幺元.零元定義5.9:設(shè)o為S上的二元運(yùn)算,如果存在元素θl(或θr)S使得對(duì)任何xS都有

θlox=θl(或xoθr=θr),則稱θl(或θr)是S中關(guān)于運(yùn)算o的一個(gè)左零元(右零元),若θS關(guān)于o既是左零元又是右零元,則稱θ為S上關(guān)于運(yùn)算o的零元.自然數(shù)集N上普通乘法的零元是0,而加法沒(méi)有零元.矩陣的乘法零元為全0矩陣P(S)上的運(yùn)算的零元是S,運(yùn)算的零元是.在R*上如果定義運(yùn)算o,使得對(duì)任意a,bR*滿足

aob=a,

那么R*的任何元素都是關(guān)于o運(yùn)算的左零元,R*中沒(méi)有右零元,也沒(méi)有零元.定理定理5.2:設(shè)o為S上的二元運(yùn)算,θl和θr分別為運(yùn)算o的左零元和右零元,則有

θl=θr=θ,

且θ是S上關(guān)于運(yùn)算o的唯一的零元.逆元定義5.10:設(shè)o為S上的二元運(yùn)算,eS為運(yùn)算o的幺元.對(duì)于xS,如果存在ylS(或yrS)都有

ylox=e(或xoyr=e),則稱yl(或yr)是S中關(guān)于運(yùn)算o的一個(gè)左逆元(右逆元),若yS關(guān)于o既是左逆元,又是右逆元,則稱y是x的逆元.自然數(shù)中只有0有加法逆元,整數(shù)集合,加法幺元為0,對(duì)任何整數(shù)x,它的加法逆元都存在,即它的相反數(shù).定理定理5.3設(shè)o為S上可結(jié)合的二元運(yùn)算,e為該運(yùn)算的幺元.對(duì)于xS,如果存在左逆元yl和右逆元yr,則有

yl=yr=y,

且y是x的唯一的逆元.證明yl=yloe=ylo(xoyr)

=(ylox)oyr=eoyr=yr

令yl=yr=y,假設(shè)y’S是x的逆元,則有

y’=y’oe=y’o(xoy)=(y’ox)oy=eoy=y.

由這個(gè)定理可知,對(duì)于可結(jié)合的二元運(yùn)算來(lái)說(shuō),元素x的逆元如果存在則是唯一的.通常把這個(gè)唯一的逆元記作x-1.消去律定義5.11設(shè)o為S上的二元運(yùn)算,如果對(duì)任意的x,y,zS滿足以下條件若xoy=xoz且x不是零元,則y=z,若yox=zox且x不是零元,則y=z,

就稱運(yùn)算o滿足消去律.例題例5.4:設(shè)是字母的有窮集,稱為字母集,中的有限個(gè)字母組成的序列稱為上串.對(duì)任何串,串中字母的個(gè)數(shù)叫作串的長(zhǎng)度,記作||.長(zhǎng)度為0的串叫做空串().

k={vi1,vi2,...,vik|Vij,j=1,2,3,..,k}

0={

}

+=

1

2...

*=

0

1

2...串的連接o為*上的二元運(yùn)算,,*,=a1a2..am,=b1b2...bn,

o=a1a2..amb1b2...bn,

運(yùn)算ｏ把串接到串的后面，稱之為連接運(yùn)算．反串，回文

＝a1a2...an,反串為＝anan-1...a2a1

如果=’則稱該串為回文.語(yǔ)言*的任何子集稱為上的一個(gè)語(yǔ)言,記作L,L*.內(nèi)容提綱二元運(yùn)算及其性質(zhì)代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)代數(shù)系統(tǒng)的同態(tài)與同構(gòu)代數(shù)系統(tǒng)定義5.12:非空集合S和S上的k個(gè)運(yùn)算f1,f2,...,fk(其中fi為ni元運(yùn)算,i=1,2,...,k)組成的系統(tǒng)稱為代數(shù)系統(tǒng),簡(jiǎn)稱代數(shù),記作<S,f1,f2,...,fk>.例如:<N,+>,<Z,+,*>,<R,+,*><P(S),,,~>在某些代數(shù)系統(tǒng)中對(duì)于給定的二元運(yùn)算存在幺元或零元,對(duì)代數(shù)系統(tǒng)起著很重要作用,稱之為該系統(tǒng)的特殊元素或代數(shù)常數(shù).<Z,+,0><P(S),,,~,>子代數(shù)系統(tǒng)定義5.13:設(shè)V=<S,f1,f2,...,fn>是代數(shù)系統(tǒng),BS且B,如果B對(duì)f1,f2,...,fn都是封閉的,且B和S含有相同的代數(shù)常數(shù),則稱<B,f1,f2,...,fn>是V的子代數(shù)系統(tǒng),簡(jiǎn)稱子代數(shù).如:<N,+>是<Z,+>的子代數(shù);如:<N,+,0>是<Z,+,0>的子代數(shù);如:<N-{0},+>不是<Z,+>的子代數(shù);代數(shù)系統(tǒng)的公理:運(yùn)算的性質(zhì).如有的代數(shù)系統(tǒng)決定該系統(tǒng)的二元運(yùn)算存在幺元.子代數(shù)與代數(shù)系統(tǒng)的關(guān)系:不僅具有相同的代數(shù)運(yùn)算,而且這些運(yùn)算也具有相同的性質(zhì),它們