代數(shù)系統(tǒng)§1 代數(shù)系統(tǒng)的引入《定義》:設(shè)Z是一個(gè)集合,f是一個(gè)函數(shù),f：ZnZ,則稱f為Z中的n元運(yùn)算,整數(shù)n稱為運(yùn)算的階（元,次）。

若n=1,則稱f：ZZ為一元運(yùn)算；若n=2,則f：Z2Z為二元運(yùn)算。

本章主要討論一元運(yùn)算和二元運(yùn)算。

例：（1）在整數(shù)I和實(shí)數(shù)R中,+,-,×均為二元運(yùn)算,而對(duì)÷而言就不是二元運(yùn)算（2）在集合Z的冪集(z)中,,均為二元運(yùn)算,而“~”是一元運(yùn)算；§1 代數(shù)系統(tǒng)的引入（3）{命題公式}中,∨,∧均為二元運(yùn)算,而“

”為一元運(yùn)算（4）{雙射函數(shù)}中,函數(shù)的合成運(yùn)算是二元運(yùn)算；二元運(yùn)算常用符號(hào)：+,,,,,,,等等。《定義》:一個(gè)非空集合A連同若干個(gè)定義在該集合上的運(yùn)算f1,f2,….,fk所組成的系統(tǒng)就稱為一個(gè)代數(shù)系統(tǒng)，記作<A,f1,f2,….,fk>?！? 代數(shù)系統(tǒng)的引入《定義》:若對(duì)給定集合中的元素進(jìn)行運(yùn)算,而產(chǎn)生的象點(diǎn)仍在該集合中,則稱此集合在該運(yùn)算的作用下是封閉的。

在f：Z2Z二元運(yùn)算的定義中,本身要求滿足運(yùn)算是封閉的。例：（1）在正整偶數(shù)的集合E中,對(duì)×,+運(yùn)算是封閉的；

在正整奇數(shù)的集合中,對(duì)×運(yùn)算是封閉的,而對(duì)+運(yùn)算不是封閉的。

（2）在前例中,R,I集合中+,-,×運(yùn)算；(z)的元素中,,~,運(yùn)算等均為封閉的?！?運(yùn)算及其性質(zhì)《定義》:設(shè)*是集合S上的二元運(yùn)算,對(duì)任一x,y

S有x

y∈S則稱

運(yùn)算在S上是封閉的?！抖x》:設(shè)*是集合S上的二元運(yùn)算,對(duì)任一x,y

S有x

y=y

x,則稱

運(yùn)算在S上是可交換的（或者說(shuō)

在S上滿足交換律）?！?運(yùn)算及其性質(zhì)《定義》:設(shè)*是集合S上的二元運(yùn)算,對(duì)任一x,y,z

S都有（x

y）

z=x

（y

z）,則稱

運(yùn)算在S上是可結(jié)合的（或者說(shuō)*在S上滿足結(jié)合律）?！抖x》:設(shè)

和

是集合S上的二個(gè)二元運(yùn)算,

對(duì)任一x,y,z

S有

x

（y

z）=（x

y）

（x

z）；（y

z）

x=（y

x）

（z

x）,則稱運(yùn)算

對(duì)

是可分配的（或稱

對(duì)

滿足分配律）。§2運(yùn)算及其性質(zhì)《定義》:設(shè)

，

是定義在集合S上的兩個(gè)可交換二元運(yùn)算，如果對(duì)于任意的x,yS，都有：

x(xy)=x；x(xy)=x則稱運(yùn)算

和運(yùn)算

滿足吸收律。《定義》:設(shè)*是S上的二元運(yùn)算,若對(duì)任一x

S有x

x=x,則稱

滿足等冪律。討論定義：1)S上每一個(gè)元素均滿足x

x=x,才稱

在S上滿足冪等律；2)若在S上存在元素x

S有x

x=x,則稱x為S上的冪等元素；3)由此定義,若x是冪等元素,則有x

x=x和xn=x成立?！?運(yùn)算及其性質(zhì)例：（1）在實(shí)數(shù)集合R中,+,×是可交換,可結(jié)合的,×對(duì)+是滿足分配律的,“0”對(duì)+是等冪元素,而其它不為等冪元素,對(duì)“-”法是不可交換,不可結(jié)合的；

（2）在(z)中,,均是可交換,可結(jié)合的,

對(duì)

,

對(duì)

均是可分配的；

(z)中任一元素,對(duì),均是等冪元素?！酀M足等冪律；

而(z)中,對(duì)稱差分

是可交換,可結(jié)合的。

除(s)={

}以外不滿足等冪律?！?/p>

=

,而除

以外的A(z)有A

A≠A?！?運(yùn)算及其性質(zhì)《定義》：設(shè)*是S上的二元運(yùn)算,對(duì)任一x

S,則：

x1=x,x2=x*x,…xn=xn-1*x《定理》：設(shè)*是S上的二元運(yùn)算,且x

S,對(duì)任一m,nI+有

（1）xm

xn=xm+n

（2）(xm)n=xmn

證明：（1）xm

xn=(xm

x)x…x=(xm+1x)x…x

n

n-1

=….=xm+n

（2）(xm)n=xm

…xm=xm+m

xm

…xm=…=xmn

nn-1§2運(yùn)算及其性質(zhì)下面定義特異元素幺元,零元和逆元。

《定義》：設(shè)*是集合Z中的二元運(yùn)算,

(1)若有一元素elZ,對(duì)任一xZ有el*x=x；則稱el為Z中對(duì)于*的左幺元(左單位元素)；

(2)若有一元素er

Z,對(duì)任一xZ有x*er=x；則稱er為Z中對(duì)于*的右幺元（右單元元素）?！抖ɡ怼罚喝鬳l和er分別是Z中對(duì)于*的左幺元和右幺元,則對(duì)于每一個(gè)xZ，可有el=er=e和e*x=x*e=x，則稱e為Z中關(guān)于運(yùn)算*的幺元，且eZ是唯一的?！?運(yùn)算及其性質(zhì)∵el和er分別是對(duì)*的左,右左元，則有el*er=er=el

∴有el=er=e成立。

（2）幺元e是唯一的。用反證法：假設(shè)有二個(gè)不同的幺元e1和e2,則有e1*e2=e2=e1,這和假設(shè)相矛盾?！嗳舸嬖阽墼脑捯欢ㄊ俏ㄒ坏?。例：（1）在實(shí)數(shù)集合R中,對(duì)+而言,e+=0；對(duì)×而言,e*=1；（2）在(E)中,對(duì)

而言,e

=E（全集合）；對(duì)

而言,e

=

（空集）；§2運(yùn)算及其性質(zhì)（3）{雙射函數(shù)}中,對(duì)“

”而言，

e

=Ix（恒等函數(shù)）；（4）{命題邏輯}中，對(duì)∨而言，e∨

=F（永假式）；對(duì)∧而言，e∧

=T（永真式）。

《定義》：設(shè)*是對(duì)集合Z中的二元運(yùn)算，（1）若有一元素θlZ，且對(duì)每一個(gè)xZ有

θl*x=θl，則稱θl為Z中對(duì)于*的左零元；

（2）若有一元素θr

Z，且對(duì)每一個(gè)xZ有

x*θr=θr

，則稱θr為Z中對(duì)于*的右零元?！?運(yùn)算及其性質(zhì)《定理》：若θl和θr分別是Z中對(duì)于*的左零元和右零元，于是對(duì)所有的xZ，可有θl=θr=θ，能使θ*x=x*θ=θ。在此情況下，θZ是唯一的，并稱θ是Z中對(duì)*的零元。

證明：方法同幺元。

例：（1）在實(shí)數(shù)集合R中，對(duì)×而言,，θL=θr=0（2）在(E)中，對(duì)

而言，θ

=

；

對(duì)

而言，θ

=E；（3）{命題邏輯}中，對(duì)∨而言，θ∨=T；對(duì)∧而言，θ∧

=F?！?運(yùn)算及其性質(zhì)《定義》：設(shè)*是Z中的二元運(yùn)算，且Z中含幺元e，令xZ，

（1）若存在一xlZ，能使xl*x=e，則稱xL是x的左逆元,并且稱x是左可逆的；

（2）若存在一xr

Z，能使x*xr=e，則稱xr是x的右逆元，并且稱x是右可逆的；

（3）若元素x既是左可逆的，又是右可逆的，則稱x是可逆的，且x的逆元用x-1表示?！?運(yùn)算及其性質(zhì)《定理》：設(shè)Z是集合，并含有幺元e

。*是定義在Z上的一個(gè)二元運(yùn)算，并且是可結(jié)合的。若xZ是可逆的，則它的左逆元等于右逆元，且逆元是唯一的。

證明：（1）先證左逆元=右逆元：設(shè)xL和xr分別是xZ的左逆元和右逆元，∵x是可逆的和*是可結(jié)合的（條件給出）

∴xl*x=x*xr

=e

∵xl*x*xr=（

xl*x）*xr=e*xr=xr

；

xl*x*xr=xl*(x*xr)=xl*e=xl

∴xr=xl§2運(yùn)算及其性質(zhì)（2）證明逆元是唯一的（若有的話）：假設(shè)x1-1和x2-1均是x的二個(gè)不同的逆元，則x1-1=x1-1*e=

x1-1*（x*x2-1

）=（x1-1*x）*x2-1=e*x2-1=x2-1，這和假設(shè)相矛盾。

∴x若存在逆元的話一定是唯一的?！锻普摗?x-1)-1=x,e-1=e

證明：∵x-1*x=(x-1)-1*（x-1

）=x*x-1=e

∴有(x-1)-1=x

∵e-1*e=e=e*e∴有e-1=e

例：（1）在實(shí)數(shù)集合R中，對(duì)“+”運(yùn)算，對(duì)任一x

R有

x-1=-x，∵x+（-x）=0，加法幺元§2運(yùn)算及其性質(zhì)對(duì)“×”運(yùn)算，對(duì)任一x

R有x-1=1x（x

0）

∵x×1x=1，乘法幺元；（2）在函數(shù)的合成運(yùn)算中,每一個(gè)雙射函數(shù)都是可逆的，

f-1（f的逆關(guān)系）；（3）在所有的二元運(yùn)算中,零元一定不存在逆元，∵θ*x=x*θ=θ。

《定義》設(shè)*是Z集合中的二元運(yùn)算，且aZ和x,yZ，若對(duì)每一x，y有

（a*x=a*y）

（x*a=y*a）

（x=y），則稱a是可約的（或稱可消去的）§2運(yùn)算及其性質(zhì)《定理》設(shè)*是Z集合中的二元運(yùn)算,且*是可結(jié)合的,若元素aZ,且對(duì)于*是可逆的,則a也是可約的。（反之不一定,即可約的不一定是可逆的。）

證明：設(shè)任一x，yZ,且有a*x=a*y，下面證明，在*可結(jié)合和a對(duì)*是可逆的條件下，a是可約的。

∵*是可結(jié)合的和aZ對(duì)*是可逆的（條件給出）

∴a-1*（a*x）=（a-1*a）*x=e*x=x

而a-1*（a*y）=（a-1*a）*y=e*y=y,即x=y。由定義可知a是可約的?！?運(yùn)算及其性質(zhì)下面舉例證明，若元素是可約的，但不一定是可逆的。

例：I為整數(shù)集合，對(duì)“

”運(yùn)算，運(yùn)算是可結(jié)合的。任何非零元素均是可約的，但除1和（-1）以外其他元素均沒(méi)有逆元。1-1=1，(-1)-1=(-1)。

例：Z={0,1,2,3,4},定義Z中二個(gè)運(yùn)算為，對(duì)任一x，yZ有

x+5y=（x+y）mod5x

5y=（x

y）mod5

§2運(yùn)算及其性質(zhì)

e+5=0,0-1=0,1-1=4,2-1=3,3-1=2,4-1=1。

e*5=1,θ*5=1,1-1=1,2-1=3,3-1=2,4-1=4,0沒(méi)有逆元。

以上二元運(yùn)算的性質(zhì)均可運(yùn)用到代數(shù)系統(tǒng)進(jìn)行討論。+501234012340123412340234013401240123*501234012340000001234024130314204321§3半群《定義》：一個(gè)代數(shù)系統(tǒng)<S,>，S為非空集合，

是S上的二元運(yùn)算，如果運(yùn)算

是封閉的，則稱代數(shù)系統(tǒng)<S,>為廣群?！抖x》：設(shè)<S,>是一代數(shù)系統(tǒng)，S為非空集合，

是S上的二元運(yùn)算，若

(1)

運(yùn)算是封閉的。

(2)

運(yùn)算滿足結(jié)合律，則稱<S,>為半群。

例：<N,+>,<N,

>,<IE,+>,<IE,>均為半群《定義》：對(duì)于*運(yùn)算，擁有幺元的半群<M,*>稱為含幺半群。（擬群，幺半群，獨(dú)異點(diǎn)）。

例：<N,+,0>,<N,,1>均為含幺半群，而<IE,>就不為幺半群?！?半群例：設(shè)S為非空集合，

(S)是S的冪集，則<

(S),,>,<

(S),,S>均為含幺半群。而<I,max>，其中max(x1,x2)取二者之大值；<I,min>，其中min(x1,x2)取二者之小值，均不為幺半群（不存在幺元）。<N,max>則為含幺半群，其中e=0《定義》：設(shè)<S,*>是一半群，TS，且*在T上是封閉的，那么<T,*>也是半群，稱<T,*>是

<S,*>的子半群?！?半群討論定義：

（1）因?yàn)?在S上是可結(jié)合的，而TS且*在T上是封閉的，所以*在T上也是可結(jié)合的。（2）由定義可知，∵SS

，∴<S,*>也是<S,*>的子半群（子含幺半群）。為了和其它子半群相互區(qū)別，稱<S,*>是的“平凡子半群”;《定義》設(shè)<S,*,e>是一個(gè)含幺半群，TS，且*在T上是封閉的，則<T,*,e>也是一個(gè)含幺半群，稱<T,*,e>是<S,*,e

>的子含幺半群?！?半群討論定義：

（1）在幺半群中，由于幺元e的存在，

∴保證在運(yùn)算表中一定沒(méi)有相同的行和列。

設(shè)任一x1,x2

Z，且x1

x2

，則e*x1=x1e*x2=x2

；

（2）在<Z,*,e>中若存在零元的話，上述性質(zhì)繼續(xù)存在。

例：半群<{0,1},*>是<{,0,1},*>的子半群，而不是子含幺半群。

*運(yùn)算由運(yùn)算表定義：§3半群

*01000101*

01

0100001101由運(yùn)算表可見(jiàn)：<{0,1},*>中幺元為1，而在<{,0,1},*>中幺元為

。

《定理》：如果半群<S,*>的載體S為有限集，則必有aS，使a*a=a?！?半群證明：因<S,*>是半群，對(duì)任意的bS，

由*的封閉性，b*bS，b3S，b4S，…

由于S是有限集，必有i<j，使bi=bj

設(shè)：p=j－i，則bj=bp*bi，即：bi=bp*bi

當(dāng)q≥i時(shí)，bq=bp*bq，

又因p≥1，總可以找到k≥1，使kp≥i，對(duì)S中的

bkp有bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp

=b2p*(bp*bkp)=b3p*bkp=….=bkp*bkp

令a=bkp，則a*a=a?！?半群《定理》：設(shè)<S,*>是獨(dú)異點(diǎn)，對(duì)于任意a，bS，且a，b均有逆元，則a)(a-1)-1=ab)a*b有逆元，且(a*b)-1=b-1*a-1證明：a)因?yàn)閍-1是a的逆元，即

a*a-1=a-1*a=e

所以(a-1)-1=a b)因?yàn)?a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=e

同理可證：(b-1*a-1)*(a*b)=e

所以(a*b)-1=b-1*a-1§4群與子群1.群的定義《定義》設(shè)<S,*>是一代數(shù)系統(tǒng)，S是非空集合，*為S上的二元運(yùn)算，它滿足以下四個(gè)條件時(shí)，則稱<S,*>為群

（1）*運(yùn)算是封閉的；

（2）*運(yùn)算是可結(jié)合的； （3）存在幺元e；

（4）S中每一個(gè)元素均有逆元。例：<I,+>,<Z2,+2>,<Z3,+3>等均為群（其中Z2={0,1},Z3={0,1,2}），而<N,+>,<I,>只是含幺半群而不是群?！?群與子群例：設(shè)M={0o,60o,120o,240o,300o,180o}表示平面上幾何圖形順時(shí)針旋轉(zhuǎn)的六種位置，定義一個(gè)二元運(yùn)算*，對(duì)M中任一元素a,b有a*b=圖形旋轉(zhuǎn)(a+b)的角度，并規(guī)定當(dāng)旋轉(zhuǎn)到360o時(shí)即為0o，試驗(yàn)證<M,*>是一個(gè)群。*0o60o120o180o240o300o0o0o60o120o180o240o300o60o60o120o180o240o300o0o120o120o180o240o300o0o60o180o180o240o300o0o60o120o240o240o300o0o60o120o180o300o300o0o60o120o180o240o§4群與子群（1）運(yùn)算是封閉的（2）*是可結(jié)合的（3）幺元為0o；（4）每一個(gè)元素均有逆元：(0o)-1=0o,(60o)-1=300o,(120o)-1=240o,(180o)-1=180o,(240o)-1=120o,(300o)-1=60o∴<M,*>是一個(gè)群?！?群與子群《定義》設(shè)<G,*>是一個(gè)群，如果G是有限集合，則稱<G,*>為有限群，并把|G|稱為群的階數(shù)，如果G為無(wú)限集合，則稱<G,*>為無(wú)限群。

例：<I,+>為無(wú)限群，上例中<M,*>為有限群，群的階為|M|=6。

至此，可以概括地說(shuō)：廣群僅僅是具有一個(gè)封閉的二元運(yùn)算的非空集合；半群是一個(gè)具有結(jié)合運(yùn)算的廣群；獨(dú)異點(diǎn)是具有幺元的半群；群是每個(gè)元素都有逆元的獨(dú)異點(diǎn)。2.群的性質(zhì)

由群的定義可知:§4群與子群（1）群具有半群和含幺半群所具有的所有性質(zhì)；（2）由于群中存在幺元，∴在群的運(yùn)算表中一定沒(méi)有相同的行（和列）（3）在群中，每一個(gè)元素均存在逆元，所以群相對(duì)半群和含幺半群來(lái)說(shuō)有一些特殊的性質(zhì)。

下面以定理形式介紹群的性質(zhì)§4群與子群《定理1》若<G,*>是一個(gè)群，則對(duì)任一a,bG有：

（1）存在唯一的元素xG

，使a*x=b；（2）存在唯一的元素yG

，使y*a=b。

證明：（1）（a）在G中存在x，使a*x=b成立。

∵a*(a-1*b)=(a*a-1)*b=e*b=b，

∴至少有一x=(a-1*b)滿足a*x=b成立。

（b）下面證明這樣的x是唯一的。若x是G中任一元素，且能使a*x=b成立，則有x=e*x=(a-1*a)*x=a-1*(a*x)=a-1*b，

∴x=(a-1*b)是滿足a*x=b的唯一元素，即x是唯一的。

（2）的證明同上?！?群與子群《定理2》若<G,*>是一個(gè)群，則對(duì)任一a,b,cG有：（1）a*b=a*cb=c（a是左可消去的）；

（2）b*a=c*a

b=c（a是右可消去的）。結(jié)論：在代數(shù)系統(tǒng)中，二元運(yùn)算是可結(jié)合的，且a是可逆的，則a是可約的。

此定理說(shuō)明群滿足消去律?！?群與子群《定理3》一個(gè)群<G,*>中一定不存在零元。

∵零元不存在逆元。

《定義》：代數(shù)系統(tǒng)<G,*>中，如果存在aG,有a*a=a，則稱a為等冪元?！?群與子群《定理4》一個(gè)群中，除了幺元e之外，不存在其它等冪元素。

證明：若任一aG

，有a*a=a的話，則a=e

。

∵e=a*a-1=(a*a）*a-1

=a*(a*a-1)=a*e=a《定義》：設(shè)S是一個(gè)非空集合，從集合S到S的一個(gè)雙射稱為S的一個(gè)置換?！?群與子群《定理5》：群<G,*>的運(yùn)算表中的每一行或每一列都是G的元素的一個(gè)置換。證明：首先，證明運(yùn)算表中的任一行或任一列所含G中的一個(gè)元素不可能多于一次。（反證法）如果對(duì)應(yīng)于元素aG的那一行中有兩個(gè)元素都是c，即有

a*b1=a*b2=c，且b1b2

由可約性，得：b1＝b2，這與b1b2矛盾。其次，證明G中的每一個(gè)元素都在運(yùn)算表的每一行和每一列中出現(xiàn)?！?群與子群

考察對(duì)應(yīng)于元素aG的那一行，設(shè)b是G中的任一元素由于b=a*(a-1*b)，所以b必定出現(xiàn)在對(duì)應(yīng)于a的那一行。再由運(yùn)算表中沒(méi)有兩行（或兩列）是相同的，所以，<G,*>的運(yùn)算表中的每一行都是G的元素的一個(gè)置換，且每一行都是不相同的。同樣，對(duì)于每一列結(jié)論同樣成立?！?群與子群3.子群《定義》設(shè)<G,*>是一個(gè)群，且SG是一個(gè)非空集合。若<S,*>滿足下列三個(gè)條件，則稱<S,*>是<G,*>的子群：

（1）e是<G,*>的幺元，且eS；

（保持幺元）

（2）對(duì)任一aS一定有a-1S

；

（保持逆元）

（3）對(duì)任一a,bS一定有a*bS

。（運(yùn)算的封閉性）討論定義：

（1）任一群<G,*>至少可找到二個(gè)子群，即<{e},*>和<G,*>，為了以示區(qū)別稱此二子群為平凡子群；

（2）除了平凡子群以外的子群稱為的真子群?！?群與子群《定義》設(shè)<S,*>是群<G,*>的真子群，若不再有一個(gè)真子群<T,*>（其中ST），則稱<S,*>是<G,*>的極大子群。例：<I,+>是一個(gè)群，設(shè)S={x|x是6的倍數(shù)}，T={y|y是3的倍數(shù)}，則<S,+>,<T,+>是<I,+>的真子群。

∵ST，

∴<S,+>不是<I,+>的極大子群?！抖ɡ怼吩O(shè)<G,*>是一個(gè)群，B是G的非空子集，如果B是一個(gè)有限集，那么，只要運(yùn)算*在B上是封閉的，則<B,*>必定是<G,*>的子群。§4群與子群證明：設(shè)bB，已知*在B上封閉，則b*bB，即

b2B，b2

*bB，即：b3B，

于是b，b2，b3……均在B中。 由于B是有限集，∴必存在正整數(shù)i和j，i<j,

使得：bi=bj

即：bi=bi*bj-i

由此可說(shuō)明bj-i是<G,*>中的幺元，且這個(gè)幺元也在子集B中。如果j-i>1，那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，且bj-i-1B；§4群與子群如果j-i=1，那么由bi=bi*b可知b就是幺元，且以自身為逆元。因此，<B,*>是<G,*>的一個(gè)子群。例：設(shè)G4={p=<p1,p2,p3,p4>|pi{0,1}}，

是上的二元運(yùn)算，定義為，對(duì)任意X=<x1,x2,x3,x4>，Y=<y1,y2,y3,y4>G4，XY=<x1y1,x2y2,x3y3,x4y4>，其中

的運(yùn)算表如圖所示：證明<{<0,0,0,0>,<1,1,1,1>},>是群<G4,>的子群。

01001110§4群與子群證明：§4群與子群《定理》:設(shè)<G,*>是一個(gè)群，S是G的非空子集，如果對(duì)于S中的任意元素a和b有a*b-1S，則<S,*>是

<G,*>的子群。證明：先證，G中的幺元e也是S中的幺元。 任取aS，a*a-1S，而a*a-1＝e，∴eS

再證，每個(gè)元素都有逆元。又e*a-1S，即a-1S。

最后說(shuō)明，*對(duì)S是封閉的。

a,bS，因b-1S，∴(b-1)-1S§4群與子群 a*b=a*(b-1)-1S，而(b-1)-1＝b∴a*bS

∴<S,*>是<G,*>的子群例：設(shè)<H,*>和<K,*>都是群<G,*>的子群，試證明

<HK,*>也是<G,*>的子群?！?阿貝爾群和循環(huán)群《定義》如果群<G,*>中運(yùn)算*是可交換的，則稱該群為阿貝爾群（或稱為交換群）。例：<I,+>為阿貝爾群。

例：離散函數(shù)代數(shù)系統(tǒng)<F,°>是阿貝爾群。Z={1,2,3,4}，F(xiàn)={f0,f1,f2,f3

}12342341,f2=12343412,f3=12344123,f0=12341234

f

=§5阿貝爾群和循環(huán)群由運(yùn)算表可見(jiàn)：（1）運(yùn)算是封閉的；（2）“°”可結(jié)合；（3）幺元f0

；（4）每一個(gè)元素均可逆;（5）以主對(duì)角線為對(duì)稱。

∴<F,°>為阿貝爾群。

°f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f2§5阿貝爾群和循環(huán)群《定理》設(shè)<G,*>是一個(gè)群，

<G,*>是阿貝爾群的充分必要條件是對(duì)任一a,bG有(a*b)*(a*b)=(a*a)*(b*b)。證明：（1）充分性：(a*b)*(a*b)=(a*a)*(b*b)

<G,*>是阿貝爾群。

對(duì)任一a,bG有(a*b)*(a*b)=(a*a)*(b*b)成立，

∵*是可結(jié)合的，且是可消去的，

∴a*(a*b)*b=(a*a)*(b*b)=(a*b)*(a*b)=a*(b*a)*b

得a*b=b*a，

∴<G,*>是阿貝爾群?！?阿貝爾群和循環(huán)群（2）必要性：

<G,*>是阿貝爾群

(a*b)*(a*b)=(a*a)*(b*b)。

∵阿貝爾群滿足交換律，對(duì)任一a,bG有a*b=b*a，

∴(a*a)*(b*b)=a*(a*b)*b=a*(b*a)*b=(a*b)*(a*b)?！锻普摗吩诎⒇悹柸褐?，對(duì)任一a,bG有

(a*b)–1=b-1*a-1=a-1*b-1§5阿貝爾群和循環(huán)群《定義》設(shè)<G,*>是一個(gè)群，I是整數(shù)集合，若存在一個(gè)元素gG，對(duì)于G中每一個(gè)元素a都能表示成gn的形式（n

I），則稱<G,*>是一個(gè)循環(huán)群，g稱為群<G,*>的生成元。

例：60o就是群<{0o,60o,120o,240o,300o,180o},*>的生成元，所以該群為循環(huán)群。

《定義》設(shè)<G,*>是由g生成的循環(huán)群，若存在一個(gè)正整數(shù)m，使gm=e成立，則整數(shù)中最小的m稱為生成元g的周期，若不存在這樣的m，則稱周期為無(wú)窮大?！?阿貝爾群和循環(huán)群例：（1）<N,+>是一個(gè)群，生成元g=1，而g的周期為無(wú)窮大；

（2）I為整數(shù)集合?！澳同余”是一個(gè)等價(jià)關(guān)系。設(shè)：m=4，N4表示“模4同余”所產(chǎn)生的等價(jià)類的集合，N4={[0],[1],[2],[3]}，定義運(yùn)+4：[i]+4[j]=[(i+j)(mod4)](i,j=0,1,2,3)則：<N4,+4>是群+4[0][1][2][3][0][0][1][2][3][1][1][2][3][0][2][2][3][0][1][3][3][0][1][2]運(yùn)算表：§5阿貝爾群和循環(huán)群由運(yùn)算表可見(jiàn)：（1）由[0]可生成<{[0]},+4>（2）由[1]或[3]可生成<{[0],[1],[2],[3]},+4>（3）由[2]可生成<{[0],[2]},+4>討論定義：

（1）在循環(huán)群中，由生成元的周期分為有限循環(huán)群和無(wú)限循環(huán)群二類；§5阿貝爾群和循環(huán)群（2）在循環(huán)群中，生成元的周期是指gm=e中最小的m

（這里m0且mI+）?！抖ɡ怼访恳粋€(gè)循環(huán)群必然是阿貝爾群。

證明：設(shè)<G,*>是一循環(huán)群，g為生成元，對(duì)任一p,qG一定存在i,j

I（整數(shù)）使得p=gi,q=gj，

則p*q=gi

*gj=gi+j=gj*gi

=q*p。

∴<G,*>循環(huán)群一定是阿貝爾群。§5阿貝爾群和循環(huán)群《定理》設(shè)<G,*>是由元素gG生成的循環(huán)群，若

<G,*>是n階的（即|G|=n），則gn=e，以致G={g1,g2,…gn=e}

，而且n是能使gn=e的最小正整數(shù)。證明：

§5阿貝爾群和循環(huán)群《定理》設(shè)<G,*>是由元素gG生成的循環(huán)群，若

<G,*>是n階的（即|G|=n），則gn=e，以致G={g1,g2,…gn=e}

，而且n是能使gn=e的最小正整數(shù)。證明：

§5阿貝爾群和循環(huán)群例：<G,*>為一群,G中元素和*運(yùn)算見(jiàn)運(yùn)算表：

c1=c,c2=b,c3=d,c4=a(幺元);

d1=d,d2=b,d3=c,d4=a(幺元);而a1=a,a2=a,a3=a,a4=a;b1=b,b2=a,b3=b,b4=a,由上可見(jiàn)：生成元c,d的階為4，等于群<G,*>的階，即|G|的基數(shù)。*abcdaabcdbbadcccdbaddcab§5阿貝爾群和循環(huán)群《定理》設(shè)<G,*>是由元素gG生成的循環(huán)群，若

<G,*>是n階的（即|G|=n），則gn=e，以致G={g1,g2,…gn=e}

，而且n是能使gn=e的最小正整數(shù)。證明：

§5阿貝爾群和循環(huán)群例：<G,*>為一群,G中元素和*運(yùn)算見(jiàn)運(yùn)算表：

c1=c,c2=b,c3=d,c4=a(幺元);

d1=d,d2=b,d3=c,d4=a(幺元);而a1=a,a2=a,a3=a,a4=a;b1=b,b2=a,b3=b,b4=a,由上可見(jiàn)：生成元c,d的階為4，等于群<G,*>的階，即|G|的基數(shù)。*abcdaabcdbbadcccdbaddcab期中復(fù)習(xí)1）命題及其表示法命題真值原子命題復(fù)合命題命題標(biāo)識(shí)符命題常量命題變?cè)幼冊(cè)?）聯(lián)結(jié)詞否定合取析取條件雙條件3）命題公式與翻譯合式公式翻譯優(yōu)先級(jí)4）真值表與等價(jià)公式真值表邏輯等價(jià)子公式定理1-4.1期中復(fù)習(xí)5）重言式與蘊(yùn)含式重言式（永真式）矛盾式（永假式）蘊(yùn)含式定理1-5.1定理1-5.2定理1-5.3定理1-5.47）范式合取范式析取范式主合取范式主析取范式定理1-7.3定理1-7.48）推理理論有效結(jié)論P(yáng)規(guī)則T規(guī)則CP規(guī)則等價(jià)公式表蘊(yùn)含公式表期中復(fù)習(xí)第二章 謂詞邏輯1）謂詞的概念與表示謂詞謂詞填式n元謂詞2）命題函數(shù)與量詞命題函數(shù)復(fù)合命題函數(shù)個(gè)體域全總個(gè)體域全稱量詞存在量詞特性謂詞3）謂詞公式與翻譯合式公式4）變?cè)募s束轄域約束變?cè)杂勺冊(cè)獡Q名代入期中復(fù)習(xí)5）謂詞演算的等價(jià)式與蘊(yùn)含式賦值等價(jià)有效的（永真的）不可滿足的（永假的）可滿足的謂詞演算的等價(jià)式與蘊(yùn)含式6）前束范式前束范式定理2-6.17）謂詞演算的推理理論USUGESEG規(guī)則期中復(fù)習(xí)第一、二章作業(yè)選講期中復(fù)習(xí)第三章 集合與關(guān)系1）集合的概念和表示法集合元素子集真子集空集全集冪集外延性原理定理3-1.1定理3-1.2定理3-1.32）集合的運(yùn)算交并補(bǔ)絕對(duì)補(bǔ)對(duì)稱差集合運(yùn)算的性質(zhì)4）序偶與笛卡爾積序偶三元組n元組笛卡爾積5）關(guān)系及其表示期中復(fù)習(xí)關(guān)系前域值域恒等關(guān)系全域關(guān)系空關(guān)系關(guān)系矩陣關(guān)系圖6）關(guān)系的性質(zhì)自反對(duì)稱傳遞反自反反對(duì)稱7）復(fù)合關(guān)系和逆關(guān)系復(fù)合關(guān)系逆關(guān)系定理3-7.28）關(guān)系的閉包運(yùn)算閉包定理3-8.1----定理3-8.5期中復(fù)習(xí)9）集合的劃分和覆蓋劃分覆蓋10）等價(jià)關(guān)系與等價(jià)類等價(jià)關(guān)系等價(jià)類商集定理3-10.1----定理3-10.412）序關(guān)系偏序集蓋住關(guān)系蓋住集和哈斯圖極大元極小元最大元最小元上界下界最小上界最大下界全序良序擬序期中復(fù)習(xí)第四章 函數(shù)1）函數(shù)的概念函數(shù)定義域值域函數(shù)相等函數(shù)集合滿射入射雙射2）逆函數(shù)和復(fù)合函數(shù)逆函數(shù)左復(fù)合恒等函數(shù)常函數(shù)函數(shù)復(fù)合的結(jié)合性定理4-2.1----定理4-2.7期中復(fù)習(xí)第三、四章作業(yè)選講§6同態(tài)與同構(gòu)1.代數(shù)系統(tǒng)的概念：《定義》由集合和集合上的一個(gè)或多個(gè)n元運(yùn)算所組成的系統(tǒng)稱為代數(shù)系統(tǒng)，用符號(hào)∨=<S,f1,f2…fm>表示，其中S為非空集合，f1,f2…fm表示n元運(yùn)算。

討論定義：（1）構(gòu)成一個(gè)代數(shù)系統(tǒng)必須具備三個(gè)條件：

?一個(gè)非空集合S，稱為載體；

?在S上的運(yùn)算f1,f2…fm,；

?在S上的運(yùn)算是封閉的。

（2）有些書(shū)上把特異元素（常數(shù)）放在代數(shù)系統(tǒng)之中，形成<S,f1,f2…fm,k>；

§6同態(tài)與同構(gòu)2.同態(tài)和同構(gòu)

同態(tài)和同構(gòu)是討論二個(gè)代數(shù)系統(tǒng)之間的關(guān)系?！抖x》設(shè)U=<A,>和V=<B,*>是二個(gè)代數(shù)系統(tǒng)，又設(shè)U到V存在一個(gè)映射f:AB，對(duì)任一a1,a2A，若有f(a1a2)=f(a1)*f(a2)，則稱f是從代數(shù)系統(tǒng)U到V的同態(tài)映射。稱U同態(tài)于V。把<f(A),*>稱為<A,>的一個(gè)同態(tài)象。其中：

f(A)={x|x=f(a)，aA}B

討論定義：§6同態(tài)與同構(gòu)

（1）f:AB為同態(tài)函數(shù)，它不單是自變量和象點(diǎn)的對(duì)應(yīng)，還有自變量的運(yùn)算和象點(diǎn)運(yùn)算之間的對(duì)應(yīng)；

（2）對(duì)同態(tài)講，二個(gè)代數(shù)系統(tǒng)的基數(shù)可以不相等，只要滿足函數(shù)的條件就行；

（3）上述定義可以推廣到多個(gè)n元運(yùn)算的同一類型的代數(shù)系統(tǒng)中去。（4）一個(gè)代數(shù)系統(tǒng)到另一個(gè)代數(shù)系統(tǒng)可能存在多于一個(gè)同態(tài)?！?同態(tài)與同構(gòu)例：給定二代數(shù)系統(tǒng)F={I,+}，I為整數(shù)，“+”為一般加；

G={Nm,+m}，其中，Nm={0,1,2…m-1},“+m”為模m加法并定義成

x1+mx2=(x1+x2)modm。對(duì)任一iI和m

I

+，

(i)modm定義了除以m所得之非負(fù)余數(shù)且0

(i)modm<m?！?同態(tài)與同構(gòu)定義FG的一個(gè)函數(shù)：f:I

Nm且有f(i)=i(modm)，

(其中iI，f(i)

Nm),f(i1+i2)=(i1+i2)modm=(i1modm)+m(i2modm)，其中i1I,i2I；

i1modm

Nm,i2modm

Nm

。則f是一同態(tài)函數(shù)：自變量和象點(diǎn)的對(duì)應(yīng)，并保持運(yùn)算的對(duì)應(yīng)?！?同態(tài)與同構(gòu)《定義》若f:AB是從U=<A,>

到V=<B,*>的同態(tài)，于是有：

（1）若f是滿射函數(shù)，則稱f是從U到V的滿同態(tài)；

（2）若f是入射函數(shù)，則稱f是從U到V的單一同態(tài)；

（3）若f是雙射函數(shù)，則稱f是從U到V的同構(gòu)。

《定義》設(shè)V是一個(gè)代數(shù)系統(tǒng)，如果f是由V到V的同態(tài)，則稱f為自同態(tài)。如果g是V到V的同構(gòu)，則稱g為自同構(gòu)?！?同態(tài)與同構(gòu)

<F,>f=1234

2341

f0f1f2f3f0f0f1f2f3f1f1f2f3f0f2f2f3f0f1f3f3f0f1f2<N4,+4>+4[0][1][2][3][0][0][1][2][3][1][1][2][3][0][2][2][3][0][1][3][3][0][1][2]例：離散函數(shù)代數(shù)系統(tǒng)和剩余類加代數(shù)系統(tǒng)是同構(gòu)的。

§6同態(tài)與同構(gòu)定義一函數(shù)h:FN4，h(fi)=[i]，其中i{0,1,2,3}，元素一一對(duì)應(yīng)；

h(fi

fj)=h(fi)+4h(fj)=[i]+4[j]，運(yùn)算是一一對(duì)應(yīng)的；∴<F,>和<N4,+4>是二個(gè)同構(gòu)的代數(shù)系統(tǒng)。在實(shí)際中，把對(duì)應(yīng)的元素和運(yùn)算進(jìn)行交換，就能得到相同的運(yùn)算表。例：試考定下列二代數(shù)系統(tǒng)U和V是否同構(gòu)：U=<{,A,~A,E},~,,>，V=<{1,2,5,10},ˉ,,>,其運(yùn)算表如下：

§6同態(tài)與同構(gòu)S~S

EA~A~AAE

A~AE

A~AEAAAEE~A~AE~AEEEEEE

A~AE

A

A

A~A

~A~AE

A~AE§6同態(tài)與同構(gòu)Xˉ1102552101X

12510112510222101055105101010101010

125101111121212511551012510§6同態(tài)與同構(gòu)定義V中：

：求二數(shù)的最小公倍數(shù)；

：求二數(shù)的最大公約數(shù)；“ˉ”：10被x除所得之商。由運(yùn)算表可見(jiàn)：定義一函數(shù)f:{1,2,5,10}{,A,~A,E}f(1)=

，f(2)=A,，f(5)=~A,，f(10)=E元素一一對(duì)應(yīng)；x§6同態(tài)與同構(gòu)對(duì)任一

a,b{1,2,5,10}有f(ˉ)=~f(a)af(ab)=f(a)f(b)

f(ab)=f(a)f(b)運(yùn)算一一對(duì)應(yīng)。

∴f是一雙射函數(shù)，U和V二個(gè)代數(shù)系統(tǒng)同構(gòu)。

若二個(gè)代數(shù)系統(tǒng)同構(gòu)，則此二個(gè)代數(shù)系統(tǒng)具有完全相同的性質(zhì),所以對(duì)于同構(gòu)的代數(shù)系統(tǒng),只要研究其中一個(gè)代數(shù)系統(tǒng),其它的代數(shù)系統(tǒng)的問(wèn)題也就解決了,給我們研究問(wèn)題帶來(lái)了方便。

§6同態(tài)與同構(gòu)《定理》代數(shù)系統(tǒng)中的同構(gòu)關(guān)系是一個(gè)等價(jià)關(guān)系。證：（1）自反性：因?yàn)槿魏我粋€(gè)代數(shù)系統(tǒng)可以通過(guò)恒等映射與它自身同構(gòu)； （2）對(duì)稱性：設(shè)U和V同構(gòu)且有對(duì)應(yīng)的同構(gòu)映射f，f是雙射函數(shù)，f的逆是V到U的同構(gòu)映射，即V和U同構(gòu)； （3）傳遞性：設(shè)f是U到V的同構(gòu)映射，g是V到W的同構(gòu)映射，因?yàn)閒和g是雙射函數(shù)，f

g是U到W的同構(gòu)映射。即U和W同構(gòu)。所以，同構(gòu)關(guān)系是等價(jià)關(guān)系。§6同態(tài)與同構(gòu)《定理》設(shè)f是從代數(shù)系統(tǒng)U=<A,>到V=<B,*>的同態(tài)映射，（1）如果U是半群，那么在f作用下，同態(tài)象<f(A),*>也是半群；（2）如果U是獨(dú)異點(diǎn)，那么在f作用下，同態(tài)象<f(A),*>也是獨(dú)異點(diǎn)；（3）如果U是群，那么在f作用下，同態(tài)象<f(A),*>也是群；§6同態(tài)與同構(gòu)證明：§6同態(tài)與同構(gòu)3.同余關(guān)系：

這是討論同一代數(shù)系統(tǒng)中的關(guān)系。

同余關(guān)系是代數(shù)系統(tǒng)的集合中的等價(jià)關(guān)系，在運(yùn)算的作用下，能保持運(yùn)算的等價(jià)類，同余關(guān)系是相等關(guān)系的推廣。

在介紹同余關(guān)系之前先看一個(gè)例子。例：設(shè)<F,+,-,

>是一代數(shù)系統(tǒng),其中F是所有分?jǐn)?shù)的集合,+,-,

為一般的加,減,乘法。則在F中,可把相等的分?jǐn)?shù)作為元素的集合是F的子集:[1/2]={…,-2/-4,-1/-2,1/2,2/4,3/6,…},[1/3]={…,-2/-6,-1/-3,1/3,2/6,….}。若對(duì)二個(gè)等價(jià)類中的元素進(jìn)行+,-,

運(yùn)算，則運(yùn)算結(jié)果必定屬于同一等價(jià)類中?！?同態(tài)與同構(gòu)如：1/2+1/3=(1/2+2/6)=(2/4+1/3)[5/6];1/21/3=(1/22/6)=(2/41/3)[1/6];1/2–1/3=(1/2–2/6)=(2/4–1/3)[1/6]。∴在F中，二個(gè)等價(jià)類的元素對(duì)+,-,

運(yùn)算均滿足代換性質(zhì)，即分?jǐn)?shù)集合的相等關(guān)系，對(duì)+,-,

運(yùn)算滿足代換性質(zhì)?！?同態(tài)與同構(gòu)《定義》設(shè)代數(shù)系統(tǒng)U=<Z,*>,*是二元運(yùn)算，R是Z中的等價(jià)關(guān)系，當(dāng)且僅當(dāng)對(duì)任一x1,x2Zy1,y2Z有

x1Rx2y1Ry2x1*y1R

x2*

y2時(shí)，則對(duì)于運(yùn)算*，等價(jià)關(guān)系R滿足代換性質(zhì)（置換性質(zhì)）。

《定義》設(shè)U=<Z,*>是一代數(shù)系統(tǒng)，R是Z中的等價(jià)關(guān)系