離散數(shù)學(xué) 第六章 代數(shù)

離散數(shù)學(xué)第六章代數(shù)第1頁，共175頁，2023年，2月20日，星期二2023/5/2第六章代數(shù)

6.1代數(shù)結(jié)構(gòu)6.2子代數(shù)6.3同態(tài)6.4同余關(guān)系6.5商代數(shù)6.6半群和獨(dú)異點(diǎn)6.7群6.8環(huán)和域第2頁，共175頁，2023年，2月20日，星期二yuliang@32023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)系統(tǒng)一個(gè)非空集合A，連同若干個(gè)定義在該集合上的運(yùn)算f1,f2,…,fn，所組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)，簡(jiǎn)稱代數(shù)，記為<A,f1,f2,…,fn>。第3頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)

代數(shù)系統(tǒng)的組成載體（一個(gè)非空集合A）定義在載體上的運(yùn)算(f1,f2,…,fn)代數(shù)常元第4頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)【例題1】(a)正整數(shù)集合I+，以及定義在該集合上的普通加法運(yùn)算“+”組成一個(gè)代數(shù)系統(tǒng)<I+,+>。(b)一個(gè)有限集合S，由S的冪集ρ(S)，及定義在ρ(S)上的交、并、補(bǔ)運(yùn)算組成一個(gè)代數(shù)系統(tǒng) 。第5頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算設(shè)A1,A2,…,An,A是非空集合，f是從A1×A2×…×An到A的一個(gè)映射，則稱f為從集合A1×A2×…×An到A的一個(gè)n元代數(shù)運(yùn)算，簡(jiǎn)稱運(yùn)算，n稱為代數(shù)運(yùn)算的階。xnx3fx2x1y…第6頁，共175頁，2023年，2月20日，星期二yuliang@72023/5/26.1代數(shù)結(jié)構(gòu) 運(yùn)算的封閉性設(shè)f是從A1×A2×…×An到A的一個(gè)n元運(yùn)算，若A=A1=A2=…=An，則稱該n元運(yùn)算在集合A上是封閉的，亦稱f是A上的n元運(yùn)算。特別地，設(shè)f是從A到A的映射，則稱f是一個(gè)在A上封閉的一元運(yùn)算。設(shè)f是從A2到A的映射，則稱f是一個(gè)在A上的封閉的二元運(yùn)算。第7頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)【例題2】一臺(tái)自動(dòng)售貨機(jī)能接受五角和一元的硬幣。當(dāng)人們投入任意兩枚上述硬幣時(shí)，自動(dòng)售貨機(jī)將供應(yīng)出相應(yīng)的飲料，如下表☆5角1元5角雪碧可樂1元可樂酷兒第8頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)設(shè)集合A＝{5角，1元}，集合B＝{雪碧，可樂，酷兒}，則上表其實(shí)是一個(gè)從A×A到B的一個(gè)映射，也即一個(gè)從A2到B的一個(gè)二元運(yùn)算。問運(yùn)算☆在A上是否封閉？第9頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)【例題3】

設(shè)有正整數(shù)集I+，“+”是I+上的普通加法運(yùn)算。在I+上定義二元運(yùn)算*為：任取x,y∈I+,x*y=x+y。令

S={2k|k∈I+}={2,4,6,8,…}

T={n|n∈I+,n能整除30}={1,2,3,5,6,10,15,30}問運(yùn)算*在S和T上是否封閉?

第10頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu) 運(yùn)算表

當(dāng)集合A是有限集時(shí)，例如A={a1,a2,…,an}，則A上一元代數(shù)運(yùn)算和二元代數(shù)運(yùn)算分別用如表(a)和(b)所示的運(yùn)算表來表示。

a1a2…ana1a2…ana1a1a1a2…

a1ana2a1a2a2…

a2an………ana1ana2…

anan△△(ai)a1a2…an△(a1)△(a2)…△(an)(a)(b)運(yùn)算符集合A運(yùn)算結(jié)果第11頁，共175頁，2023年，2月20日，星期二yuliang@122023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)一交換律設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，如果任取x,y∈A，都有x*y=y*x，則稱該二元運(yùn)算是可交換的?！纠}4】設(shè)Q是有理數(shù)集合，☆是Q上的二元運(yùn)算，對(duì)任意a,b∈Q,a☆b=a+b-a●b,其中+和●是普通的加法、乘法運(yùn)算，問☆是否是可交換的？第12頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)二結(jié)合律設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，如果對(duì)于任意x,y,z∈A，都有x*(y*z)=(x*y)*z,則稱該二元運(yùn)算是可結(jié)合的?！纠}5】設(shè)A是一個(gè)非空集合，*是A上的一個(gè)二元運(yùn)算，對(duì)于任意a,b∈A,有a*b=b,證明運(yùn)算*是可結(jié)合的。第13頁，共175頁，2023年，2月20日，星期二yuliang@142023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)三分配律設(shè)*和是定義在集合A上的二元運(yùn)算，如果對(duì)任意的a,b,c∈A，都有*對(duì)左可分配*對(duì)右可分配則稱*對(duì)是可分配的。

第14頁，共175頁，2023年，2月20日，星期二yuliang@152023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)三【例題6】設(shè)集合A={α,β},在A上定義兩個(gè)二元運(yùn)算*和☆，如下表(a)和(b)所示。運(yùn)算☆對(duì)運(yùn)算*可分配嗎？運(yùn)算*對(duì)運(yùn)算☆呢？*α

βαβα

ββ

α☆α

βα

βα

αα

β(a)(b)第15頁，共175頁，2023年，2月20日，星期二yuliang@162023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)四吸收律設(shè)*和是定義在集合A上的兩個(gè)可交換的二元運(yùn)算，如果對(duì)于任意的x,y∈A,都有

則稱運(yùn)算*和滿足吸收律。第16頁，共175頁，2023年，2月20日，星期二yuliang@172023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)五等冪律設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，如果對(duì)于任意x∈A,都有x*x=x,則稱運(yùn)算*滿足等冪律。第17頁，共175頁，2023年，2月20日，星期二yuliang@182023/5/26.1代數(shù)結(jié)構(gòu)【例題7】設(shè)ρ(S)是集合S上的冪集，在ρ(S)上定義兩個(gè)二元運(yùn)算：集合的并運(yùn)算∪和集合的交運(yùn)算∩，驗(yàn)證∪和∩滿足吸收律和等冪律。解答：∪和∩運(yùn)算是可交換的。A,B∈ρ(S),有

A∩(A∪B)=AA∪(A∩B)=A所以∪和∩滿足吸收律。又有

A∩A=AA∪A=A所以∪和∩滿足等冪律。第18頁，共175頁，2023年，2月20日，星期二2023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)運(yùn)算的性質(zhì)六消去律設(shè)*是定義在集合上的一個(gè)二元運(yùn)算，元素a∈A,如果對(duì)于任意x,y∈A,都有

a*x=a*yx=y

a是左可消去的

x*a=y*ax=ya是右可消去的則稱a關(guān)于運(yùn)算*是可消去的。若A中的所有元素都是可消去的，則稱運(yùn)算*滿足消去律。第19頁，共175頁，2023年，2月20日，星期二yuliang@202023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)常元代數(shù)系統(tǒng)中，針對(duì)某一代數(shù)運(yùn)算表現(xiàn)出具有某些特殊性質(zhì)的元素稱為代數(shù)常元，常見的有：幺元、零元、逆元、等冪元等。幺元

左幺元：設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，若存在元素el，對(duì)于A中的每一個(gè)元素x，都有el*x=x則稱el為A中關(guān)于運(yùn)算*的左幺元。

第20頁，共175頁，2023年，2月20日，星期二yuliang@212023/5/26.1代數(shù)結(jié)構(gòu)幺元

右幺元：設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，若存在元素er，對(duì)于A中每一個(gè)元素x,都有

x*er=x則稱er為A中關(guān)于運(yùn)算*的右幺元。第21頁，共175頁，2023年，2月20日，星期二yuliang@222023/5/26.1代數(shù)結(jié)構(gòu)幺元

幺元：設(shè)*是定義在集合A上一個(gè)二元運(yùn)算，若A中有一個(gè)運(yùn)算e,它既是左幺元，又是右幺元，則稱e為A中關(guān)于運(yùn)算*的幺元，亦稱作單位元。

e*x=x*e=x第22頁，共175頁，2023年，2月20日，星期二yuliang@232023/5/26.1代數(shù)結(jié)構(gòu)【例題8】設(shè)集合S={a,b,c,d},

S上定義的兩個(gè)二元運(yùn)算*和★的運(yùn)算表如下表所示，試求出其中的左幺元和右幺元。*abcdabcddabcabcdabccabcd★abcdabcdabdcbacdcdabddbc(a)(b)第23頁，共175頁，2023年，2月20日，星期二yuliang@242023/5/26.1代數(shù)結(jié)構(gòu)『定理』設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，且在A中有關(guān)于運(yùn)算*的左幺元el和右幺元er,則el=er=e,且A中的幺元是唯一的。

證明：設(shè)el和er分別是A中關(guān)于運(yùn)算*的左幺元和右幺元，則有

el=el*er=er=e

假設(shè)另有幺元e’∈A,則有e’=e’*e=e,結(jié)論得證。第24頁，共175頁，2023年，2月20日，星期二yuliang@252023/5/26.1代數(shù)結(jié)構(gòu)代數(shù)常元零元

左零元：設(shè)*是定義在集合A上的一個(gè)二元運(yùn)算，如果有一個(gè)元素θl∈A,對(duì)于任意的元素x∈A都有θl*x=θl，則稱θl為A中關(guān)于運(yùn)算*的左零元。

右零元：如果有一個(gè)元素θr∈A,對(duì)于任意的元素x∈A都有x*θr=θr，則稱θr為A中關(guān)于運(yùn)算*的右零元。第25頁，共175頁，2023年，2月20日，星期二yuliang@262023/5/26.1代數(shù)結(jié)構(gòu)零元

零元：如果A中的一個(gè)元素θ，它既是左零元，又是右零元，則稱θ為A中關(guān)于運(yùn)算*的零元。

θ*x=x*θ=θ第26頁，共175頁，2023年，2月20日，星期二yuliang@272023/5/26.1代數(shù)結(jié)構(gòu)【例題9】設(shè)“淺”表示不易褪色的淺色衣服，“深”表示易褪色的深色衣服，集合S={淺，深}，定義S的一個(gè)二元運(yùn)算“混洗”，記為“”，則的運(yùn)算表如下表所示。求S中關(guān)于運(yùn)算的幺元和零元。淺深淺深

淺深深深第27頁，共175頁，2023年，2月20日，星期二yuliang@282023/5/26.1代數(shù)結(jié)構(gòu)『定理』設(shè)*是定義在集合A上一個(gè)二元運(yùn)算，且在A中有關(guān)于運(yùn)算*的左零元θl和右零元θr,那么θl=θr=θ，且A中的零元是唯一的。第28頁，共175頁，2023年，2月20日，星期二yuliang@292023/5/26.1代數(shù)結(jié)構(gòu)逆元

逆元：設(shè)<A,*>是一個(gè)代數(shù)系統(tǒng)，*是定義在集合A上的一個(gè)二元運(yùn)算，e是A中關(guān)于運(yùn)算*的幺元。x,y∈A,如果x*y=e,那么關(guān)于運(yùn)算*,x是y的左逆元，y是x的右逆元。如果x*y=y*x=e,那么關(guān)于運(yùn)算*,x與y互為逆元。運(yùn)算x的逆元記為x-1。第29頁，共175頁，2023年，2月20日，星期二yuliang@302023/5/26.1代數(shù)結(jié)構(gòu)『定理』設(shè)<A,*>是一個(gè)代數(shù)系統(tǒng)，*是定義在集合A上的一個(gè)二元運(yùn)算，e是A中關(guān)于運(yùn)算*的幺元。若運(yùn)算*是可結(jié)合的，且元素x有左逆元l和右逆元r，則l=r。證明：因?yàn)閑是A中關(guān)于運(yùn)算*的幺元且x有左逆元l和右逆元r,則有

l*x=x*r=e又運(yùn)算是可結(jié)合的，所以

l=l*e=l*(x*r)=(l*x)*r=e*r=r第30頁，共175頁，2023年，2月20日，星期二yuliang@312023/5/26.1本節(jié)小結(jié)代數(shù)系統(tǒng)組成：載體、定義在載體上的運(yùn)算、代數(shù)常元。設(shè)<A，*>為代數(shù)系統(tǒng)，*是定義在A上的二元運(yùn)算，則運(yùn)算*的某些性質(zhì)以及代數(shù)常元可以直接從運(yùn)算表中得到：運(yùn)算*是封閉的，當(dāng)且僅當(dāng)運(yùn)算表中的每個(gè)元素都屬于A；運(yùn)算*滿足交換律，當(dāng)且僅當(dāng)運(yùn)算表關(guān)于主對(duì)角線對(duì)稱；第31頁，共175頁，2023年，2月20日，星期二yuliang@322023/5/26.1本節(jié)小結(jié)運(yùn)算滿足等冪律，當(dāng)且僅當(dāng)運(yùn)算表中主對(duì)角線上的每一元素與它所對(duì)應(yīng)的行(列)表頭元素相同;運(yùn)算滿足消去律，當(dāng)且僅當(dāng)運(yùn)算表中任意行、任意列沒有相同的兩個(gè)元素；若A中有關(guān)于運(yùn)算*的零元，則該元素所在的行和列中的所有元素都等于該元素；若A中有關(guān)于運(yùn)算*的幺元，則該元素所在的行(列)中的所有元素都依次與列(行)表頭元素相同;第32頁，共175頁，2023年，2月20日，星期二yuliang@332023/5/26.1本節(jié)小結(jié)設(shè)A中有關(guān)于運(yùn)算*的幺元e，元素a與b互逆，當(dāng)且僅當(dāng)運(yùn)算表中a行、b列對(duì)應(yīng)的元素與a列、b行對(duì)應(yīng)的元素都是e。代數(shù)常元：幺元、零元。第33頁，共175頁，2023年，2月20日，星期二yuliang@342023/5/26.1習(xí)題習(xí)題一設(shè)<A,*>為代數(shù)系統(tǒng)，其中A={1,2,3,4},“*”定義如下表所示：(a)運(yùn)算*是可交換的嗎？為什么？(b)運(yùn)算*是可結(jié)合的嗎？為什么？(c)求A中關(guān)于運(yùn)算*的幺元，并給出每個(gè)元素的逆元。(d)A中有關(guān)于運(yùn)算*的零元嗎？*123412341234234134124123第34頁，共175頁，2023年，2月20日，星期二yuliang@352023/5/26.1習(xí)題習(xí)題二設(shè)I是整數(shù)集合，函數(shù)g:I×I→I，定義為：g(x,y)=x*y=x＋y－x·y，其中+和·是普通的加法和乘法運(yùn)算。(a)試證明二元運(yùn)算*是可交換的和可結(jié)合的。(b)求運(yùn)算*的幺元，并指出每個(gè)元素的逆元。第35頁，共175頁，2023年，2月20日，星期二yuliang@362023/5/26.2子代數(shù)子代數(shù)定義設(shè)<A,*,△,k>是一個(gè)代數(shù)系統(tǒng)，*和△分別是載體A上的二元運(yùn)算和一元運(yùn)算，k是代數(shù)常元，如果滿足(1)A’A,(2)*和△運(yùn)算在A’上封閉，(3)k∈A’,那么稱<A’,*,△,k>是<A,*,△,k>的子代數(shù)。第36頁，共175頁，2023年，2月20日，星期二yuliang@372023/5/26.2子代數(shù)平凡子代數(shù)定義設(shè)<A,*,△>是一代數(shù)系統(tǒng)，T是由A中的代數(shù)常元構(gòu)成的集合，且運(yùn)算*和△在T上封閉。稱<A,*,△>和<T,*,△>是<A,*,△>的平凡子代數(shù)，非平凡子代數(shù)亦稱為真子代數(shù)。第37頁，共175頁，2023年，2月20日，星期二yuliang@382023/5/26.2習(xí)題習(xí)題一

I是整數(shù)集合，Ie和Io分別是偶數(shù)集合和奇數(shù)集合，+是I上的普通加法運(yùn)算，則<I，+>是一代數(shù)系統(tǒng)。<Ie，+>和<Io，+>是<I，+>的子代數(shù)嗎？解答：<Ie，+>是<I，+>的子代數(shù)。而<Io，+>不是<I，+>的子代數(shù)，因?yàn)镮o在+上不封閉。第38頁，共175頁，2023年，2月20日，星期二yuliang@392023/5/26.2習(xí)題習(xí)題二

I是整數(shù)集合，I+是正整數(shù)集合，+是I上的普通加法運(yùn)算，則<I,+,0>是一代數(shù)系統(tǒng)。<I+,+>是<I,+,0>的子代數(shù)嗎？

解答：<I+，+>不是<I，+，0>的子代數(shù)，因?yàn)?I+。第39頁，共175頁，2023年，2月20日，星期二yuliang@402023/5/26.3同態(tài)同態(tài)的定義設(shè)A=<S,*,△,k>和A’=<S’,*’,△’,k’>是兩個(gè)具有相同構(gòu)成的代數(shù)系統(tǒng)，f是從S到S’的一個(gè)映射，且對(duì)任意a,b∈S滿足：

f(a*b)=f(a)*’f(b)

f(△a)=△’f(a)

f(k)=k’則稱f為由A到A’的一個(gè)同態(tài)映射，簡(jiǎn)稱同態(tài)。A同態(tài)于A’,記作A~A’。第40頁，共175頁，2023年，2月20日，星期二yuliang@412023/5/26.3同態(tài)同態(tài)象設(shè)f是從A=<S,*,△,k>到A’=<S’,*’,△’,k’>的一個(gè)同態(tài)映射，稱<f(S),*’,△’,k’>為A在映射f下的同態(tài)象。其中下圖反映了兩個(gè)代數(shù)系統(tǒng)間的同態(tài)關(guān)系。第41頁，共175頁，2023年，2月20日，星期二yuliang@422023/5/26.3同態(tài)△kSS’fk’af(a)bf(b)cf(c)a*bf(a)*’f(b)△(c)△’f(c)**’同態(tài)象<f(S),*’,△’,k’>△’第42頁，共175頁，2023年，2月20日，星期二yuliang@432023/5/26.3同態(tài)【例題1】設(shè)代數(shù)系統(tǒng)<I,·>,

I是整數(shù)集,·是普通乘法運(yùn)算。如果我們只對(duì)運(yùn)算結(jié)果是正數(shù)、負(fù)數(shù)還是零關(guān)心,那么代數(shù)系統(tǒng)<I，·>中的運(yùn)算結(jié)果的特征就可以用另一個(gè)代數(shù)系統(tǒng)<B，⊙>的運(yùn)算結(jié)果來表示,其中B＝{+,-,0},⊙是B上的二元運(yùn)算，運(yùn)算表如下所示，構(gòu)造從<I,·>到<B,⊙>的同態(tài)映射。第43頁，共175頁，2023年，2月20日，星期二yuliang@442023/5/26.3同態(tài)解答：構(gòu)造函數(shù)f:I→B,

f(x)＝顯然，任取a,b∈I,f(a·b)=f(a)⊙f(b)。所以，f是由<I,·>到<B,⊙>的一個(gè)同態(tài)?！?-0+-0+-0-+0000+x>0

-x<00x=0第44頁，共175頁，2023年，2月20日，星期二yuliang@452023/5/26.3同態(tài)同態(tài)的分類設(shè)f是由A={S,*,△,k}到A’={S’,*’,△’,k’}的一個(gè)同態(tài)。

滿同態(tài):若f是滿射的，則稱f為由A到A’的一個(gè)滿同態(tài)。A’就是A在滿同態(tài)f下一個(gè)同態(tài)象。單一同態(tài)：若f是單射的，則稱f為由A到A’的一個(gè)單一同態(tài)。顯然，A在單一同態(tài)f下的同態(tài)象<f(S)，*’,△’,k’>與A同構(gòu)。第45頁，共175頁，2023年，2月20日，星期二yuliang@462023/5/26.3同態(tài)同態(tài)的分類同構(gòu)：若f是雙射的，則稱f為由A到A’的一個(gè)同構(gòu)映射，簡(jiǎn)稱同構(gòu)。A同構(gòu)于A’，記作AA’。自同態(tài)：若A’=A，則稱f為A上的自同態(tài)。自同構(gòu)：若A’=A且f是雙射的，則稱f為A上的自同構(gòu)。第46頁，共175頁，2023年，2月20日，星期二yuliang@472023/5/26.3同態(tài)【例題2】

N是自然數(shù)集合，+是N上的普通加法運(yùn)算，設(shè)Nk={0,1,2,…,k-1},+k是定義在N上的模k加法運(yùn)算。設(shè)函數(shù)f:N→Nk定義為

f(x)=x(modk)

證明：f是從<N,+,0>到<Nk,+k,0)的一個(gè)滿同態(tài)映射。第47頁，共175頁，2023年，2月20日，星期二yuliang@482023/5/26.3同態(tài)證明：(a)顯然，f是從N到Nk的滿射。(b)任取x,y∈N,有

f(x+y)=(x+y)(modk)=(x(modk)+y(modk))(modk)=(x(modk))+k(y(modk))=f(x)+kf(y)(c)f(0)=0。所以，f是從<N,+,0>到<Nk，+k,0>的一個(gè)滿同態(tài)。第48頁，共175頁，2023年，2月20日，星期二yuliang@492023/5/26.3同態(tài)【例題3】設(shè)A={a,b,c,d},在A上定義一個(gè)二元運(yùn)算★如表a所示，又設(shè)B={0,1,2,3},在B上定義一個(gè)二元運(yùn)算*如表b所示。構(gòu)造從代數(shù)系統(tǒng)<A,★>到<B,*>的一個(gè)同構(gòu)映射?！颽bcdabcdaaaaabcdacacadcb*012301232020012322220321(a)(b)第49頁，共175頁，2023年，2月20日，星期二yuliang@502023/5/26.3同態(tài)解答：

設(shè)函數(shù)h:A→B,h(a)=2,h(b)=1,h(c)=0,h(d)=3。容易驗(yàn)證：(a)h是雙射的；(b)任取x,y∈A,h(x★y)=h(x)*h(y);(c)<A,★>中的幺元b,h(b)=1也是<B,*>中的幺元；<A,★>中的零元a,h(a)=2也是<B,*>的零元。所以h是從代數(shù)系統(tǒng)<A,★>到<B,*>的一個(gè)同構(gòu)映射。

第50頁，共175頁，2023年，2月20日，星期二yuliang@512023/5/26.3同態(tài)的性質(zhì)『定理』設(shè)f是從A=<S,*,△,k>到A’=<S’,*’,△’,k’>的一個(gè)同態(tài)映射，那么A的同態(tài)象<f(S),*’,△’,k’>是A’的子代數(shù)。證明：(i)因?yàn)閒是從S到S’的一個(gè)映射,所以f(S)S’。(ii)因?yàn)閗∈S,f(k)=k’,所以k’∈f(S).(iii)任取a,b∈f(S)，存在x,y∈S,使得f(x)=a,f(y)=b。因?yàn)閤*y=z∈S,所以

a*’b=f(x)*’f(y)=f(x*y)=f(z)∈f(S)故f(S)在運(yùn)算*’下是封閉的。第51頁，共175頁，2023年，2月20日，星期二yuliang@522023/5/26.3同態(tài)的性質(zhì)(iv)任取a∈f(S),存在x∈S使得f(x)=a。因?yàn)椤鱴∈S,所以△’a=△’f(x)=f(△x)∈f(S),故f(S)在運(yùn)算△’下是封閉的。由(i)(ii)(iii)(iv)可知，<f(S)，*’,△’,k’>是A’的子代數(shù)。fA=<S,*,△,k>同態(tài)象<f(S),*’,△’,k’>A’=<S’,*’,△’,k>第52頁，共175頁，2023年，2月20日，星期二yuliang@532023/5/26.3同態(tài)的性質(zhì)『定理』設(shè)f是從A=<S,*,°>到A’=<S’,*’,°’>的一個(gè)同態(tài)映射，A’’=<f(S),*’,°’>是A在同態(tài)映射f下的同態(tài)象，則有(1)若*在A中可交換,則*’在A’’中也是可交換的;(2)若*在A中可結(jié)合,則*’在A’’中也是可結(jié)合的;(3)若在A中*對(duì)°可分配,則在A’’中*’對(duì)°’也可分配;第53頁，共175頁，2023年，2月20日，星期二yuliang@542023/5/26.3同態(tài)的性質(zhì)(4)若e是A中關(guān)于運(yùn)算*的幺元，則f(e)是A’’中關(guān)于運(yùn)算*’的幺元；(5)若θ是A中關(guān)于運(yùn)算*的零元，則f(θ)是A’’中關(guān)于運(yùn)算*’的零元；(6)任取x∈S,x對(duì)運(yùn)算*有逆元x-1,在f(S)中，f(x)也有關(guān)于運(yùn)算*’的逆元f(x-1)。第54頁，共175頁，2023年，2月20日，星期二yuliang@552023/5/26.3小結(jié)子代數(shù)概念：一個(gè)代數(shù)系統(tǒng)載體A的一個(gè)子集A’，如果在該代數(shù)系統(tǒng)的所有運(yùn)算下都封閉，則稱以A’為載體的代數(shù)系統(tǒng)是原代數(shù)系統(tǒng)的子代數(shù)。同態(tài)概念：同態(tài)映射不僅建立了兩個(gè)代數(shù)系統(tǒng)載體間的映射關(guān)系，更重要的是同時(shí)還建立了兩個(gè)代數(shù)系統(tǒng)對(duì)應(yīng)運(yùn)算間的映射關(guān)系。第55頁，共175頁，2023年，2月20日，星期二yuliang@562023/5/26.3小結(jié)同態(tài)象概念：一個(gè)代數(shù)系統(tǒng)與其同態(tài)象之間有許多相似的地方。同態(tài)的分類：根據(jù)同態(tài)映射的性質(zhì)可以將同態(tài)分為：滿同態(tài)、單一同態(tài)和同構(gòu)。同態(tài)性質(zhì)：在同態(tài)映射下，同態(tài)象的運(yùn)算能夠保持原代數(shù)系統(tǒng)中對(duì)應(yīng)運(yùn)算的交換性、結(jié)合性和分配性，并且幺元、零元和逆元也滿足映射對(duì)應(yīng)關(guān)系。第56頁，共175頁，2023年，2月20日，星期二yuliang@572023/5/26.3本節(jié)習(xí)題習(xí)題一設(shè)h是從A=<S,*,k>到A’=<S’,*’,k’>的同態(tài)，證明如果<T,*’,k’>是A’的子代數(shù)，那么<h-1(T),*,k>是A的子代數(shù)。h-1(T)Thh-1hA=<S,*,k>A’=<S’,*’,k’>第57頁，共175頁，2023年，2月20日，星期二yuliang@582023/5/26.3本節(jié)習(xí)題證明：(i)因?yàn)?lt;T,*’,k’>是<S’,*’,k’>的子代數(shù)，所以TS’。故有h-1(T)h-1(S’)S。(ii)任取x,y∈h-1(T),存在x’,y’∈T使得h(x)=x’,h(y)=y’因?yàn)閤,y∈S且h是從A到A’的同態(tài)，所以有

h(x*y)=h(x)*’h(y)=x’*’y’∈T故x*y∈h-1(T),即h-1(T)對(duì)*運(yùn)算是封閉的。(iii)因?yàn)閔(k)=k’∈T,所以k∈h-1(T)。由(i)(ii)(iii)可知，<h-1(T),*,k>是<S,*,k>的子代數(shù)。第58頁，共175頁，2023年，2月20日，星期二yuliang@592023/5/26.4同余關(guān)系同余的定義運(yùn)算上的同余關(guān)系：設(shè)A=<S,*,△>是一個(gè)代數(shù)系統(tǒng)，~是載體S上的等價(jià)關(guān)系，任取a,b,c∈S。(1)當(dāng)a~b時(shí)，若△a~△b,則等價(jià)關(guān)系~在一元運(yùn)算△下是可保持的，稱~是關(guān)于運(yùn)算△同余關(guān)系。(2)當(dāng)a~b和c~d時(shí)，若有a*c~b*d，則等價(jià)關(guān)系~在二元運(yùn)算*下是可保持的，稱~是關(guān)于運(yùn)算*同余關(guān)系。第59頁，共175頁，2023年，2月20日，星期二yuliang@602023/5/26.4同余關(guān)系ab△a△bcd△c△d△’[a]=[△a]△’[c]=[△c]aba*cb*dcd[a]*’[c]=[a*c]第60頁，共175頁，2023年，2月20日，星期二yuliang@612023/5/26.4同余關(guān)系【例題1】設(shè)+是整數(shù)集合I上的普通加法運(yùn)算，~是I上的模k(k∈I+)相等關(guān)系，問~在運(yùn)算+上是否是I上的同余關(guān)系？分析：任意a,b和c,d有：

a≡b(modk)其實(shí)就是a-b=n*k

c≡d(modk)其實(shí)就是c-d=m*k那么(a+c)-(b+d)=(m+n)*k，即(a+c)≡(b+d)(modk)第61頁，共175頁，2023年，2月20日，星期二yuliang@622023/5/26.4同余關(guān)系【例題2】設(shè)△是集合I上的一元運(yùn)算，任取a∈I,

△a=a2,~是I上的模k(k∈I)相等關(guān)系，問~在運(yùn)算△是否是I上的同余關(guān)系？~是否是代數(shù)系統(tǒng)A＝<I,+,△>上A的同余關(guān)系？分析：a≡b(modk)就相當(dāng)于(a-b)=n*k

△a-△b=(a+b)(a-b)=(a+b)*n*k，即△a≡△b整數(shù)m第62頁，共175頁，2023年，2月20日，星期二yuliang@632023/5/26.4同余關(guān)系代數(shù)系統(tǒng)上的同余關(guān)系：設(shè)A=<S,*,△>是一個(gè)代數(shù)系統(tǒng)，~是載體S上的等價(jià)關(guān)系，若~在A上的所有運(yùn)算下都是可保持的，則稱~為代數(shù)系統(tǒng)A上的同余關(guān)系。第63頁，共175頁，2023年，2月20日，星期二yuliang@642023/5/26.4同余關(guān)系『定理』設(shè)g是從代數(shù)系統(tǒng)A=<S,*,△,k>到A’=<S’,*’,△’,k’>的一個(gè)同態(tài)映射，那么由g誘導(dǎo)的S上的等價(jià)關(guān)系~是代數(shù)系統(tǒng)A上同余關(guān)系。證明：由函數(shù)g誘導(dǎo)的S上的等價(jià)關(guān)系~為：任取a,b∈S,a~b當(dāng)且僅當(dāng)g(a)=g(b)。(i)若a~b,則g(a)=g(b),

△’g(a)=△’g(b)。第64頁，共175頁，2023年，2月20日，星期二yuliang@652023/5/26.4同余關(guān)系又g是從A到A’的同態(tài)映射，所以有

△’g(a)=g(△a)=△’g(b)=g(△b)故△a~△b，這說明~在運(yùn)算△下是可保持的。(ii)若a~b且c~d,且有g(shù)(a)=g(b),g(c)=g(d),所以g(a)*’g(c)=g(b)*’g(d),又因g是從A到A’的同態(tài)映射，所以有g(shù)(a)*’g(c)=g(a*c)=g(b)*’g(d)=g(b*d)故a*c~b*d,這說明等價(jià)關(guān)系~在運(yùn)算*下是可保持的。由(i)(ii)可得，~是代數(shù)系統(tǒng)A上的同余關(guān)系。第65頁，共175頁，2023年，2月20日，星期二yuliang@662023/5/26.4同余關(guān)系運(yùn)算上的同余關(guān)系：等價(jià)關(guān)系在運(yùn)算下的可保持性是指參與運(yùn)算的對(duì)應(yīng)元素，如果在同一個(gè)等價(jià)類中，則運(yùn)算后所得的結(jié)果也必在同一個(gè)等價(jià)類中。代數(shù)系統(tǒng)上的同余關(guān)系：等價(jià)關(guān)系R如果在一個(gè)代數(shù)系統(tǒng)中的所有運(yùn)算下都是可保持的，則R是A上的同余關(guān)系。同余關(guān)系使得元素所在的等價(jià)類在運(yùn)算上可以作為一個(gè)整體來看待。第66頁，共175頁，2023年，2月20日，星期二yuliang@672023/5/26.5商代數(shù)商代數(shù)定義:設(shè)A=<S,*,△,k>是一個(gè)代數(shù)系統(tǒng)，~是A上的同余關(guān)系，A關(guān)于~的商代數(shù)A/~=<S/~,*’,△’,[k]>。其中

△’[a]=[△a][a]*’[b]=[a*b]注意：S/~是集合的集合，即等價(jià)類的集合，形如：{[a],[b],…}*’,△’是集合之間的運(yùn)算

[k]是代數(shù)常元的集合

第67頁，共175頁，2023年，2月20日，星期二yuliang@682023/5/26.5商代數(shù)【例題】代數(shù)系統(tǒng)A=<S,△,~>，其中S={a1,a2,a3,a4,a5},一元運(yùn)算△和~由下表所示的運(yùn)算表定義。又S上的等價(jià)關(guān)系R產(chǎn)生的S上的劃分

л={{a1,a3},{a2,a5},{a4}}(a)證明：R是A上的同余關(guān)系。(b)給出A/R。a1a2a3a4a5△~a4a3a4a2a1a3a2a1a3a5第68頁，共175頁，2023年，2月20日，星期二yuliang@692023/5/26.5小結(jié)商代數(shù)：由等價(jià)關(guān)系R可以得到代數(shù)系統(tǒng)A的載體的一個(gè)劃分，以這個(gè)劃分為新的載體，按照原運(yùn)算的規(guī)則建立等價(jià)類之間新的運(yùn)算，這樣得到的代數(shù)系統(tǒng)是原代數(shù)系統(tǒng)的商代數(shù)。第69頁，共175頁，2023年，2月20日，星期二yuliang@702023/5/26.6半群和獨(dú)異點(diǎn)半群：一個(gè)代數(shù)系統(tǒng)<S,*>，其中S是非空集合，*是S上一個(gè)二元運(yùn)算，如果滿足：運(yùn)算*是封閉的；運(yùn)算*是可結(jié)合的，即任取x,y,z∈S,有

(x*y)*z=x*(y*z)則稱<S,*>為半群。第70頁，共175頁，2023年，2月20日，星期二yuliang@712023/5/26.6半群與獨(dú)異點(diǎn)【例題1】設(shè)集合Sk={x|x∈I,x≥k},其中I是整數(shù)集合，k∈I,且k≥1,+是普通加法運(yùn)算。證明<Sk,+>是一個(gè)半群。

證明：因?yàn)?運(yùn)算在Sk上封閉的和可結(jié)合的，所以<Sk,+>是半群。

考慮：如果k≥0呢？如果k≥-1呢？第71頁，共175頁，2023年，2月20日，星期二yuliang@722023/5/26.6半群與獨(dú)異點(diǎn)【例題2】設(shè)I+是正整數(shù)集合，R是實(shí)數(shù)集合，R+和R-分別表示正實(shí)數(shù)和負(fù)實(shí)數(shù)集合。問<I+,->、<R+,·>、<R-,·>和<R,÷>都是半群?jiǎn)?？為什么？解答?lt;R+,·>滿足半群的定義，它是半群。

<I+,->、<R-,·>、<R,÷>的運(yùn)算不封閉，因此均不是半群。第72頁，共175頁，2023年，2月20日，星期二yuliang@732023/5/26.6半群與獨(dú)異點(diǎn)『定理』設(shè)<S,*>是一個(gè)半群，TS且*在T上是封閉的，那么<T,*>是<S,*>的子代數(shù)，<T,*>也是一個(gè)半群，稱為<S,*>的子半群。獨(dú)異點(diǎn)：含有幺元的半群。

由于結(jié)合律在子代數(shù)上是可繼承的，因此半群的子代數(shù)也是半群。第73頁，共175頁，2023年，2月20日，星期二yuliang@742023/5/26.6半群與獨(dú)異點(diǎn)【例題3】判斷以下代數(shù)系統(tǒng)是否是獨(dú)異點(diǎn)。(a)<I+,+>;(b)<N,+>。解答：(a)<I+,+>是半群，但不是獨(dú)異點(diǎn)，因?yàn)椴缓戌墼?。(b)<N,+>是半群，因?yàn)楹戌墼?，所以它也是獨(dú)異點(diǎn)。第74頁，共175頁，2023年，2月20日，星期二yuliang@752023/5/26.6半群與獨(dú)異點(diǎn)【例題4】設(shè)A={0,1,2,3},+4和×4分別是模4加法和模4乘法，其運(yùn)算表分別如下頁(a)、(b)所示，即任意a,b∈A有

a+4b=(a+b)(mod4)

a×4b=(a×b)(mod4)(a)<A,+4>和<A,×4>是獨(dú)異點(diǎn)嗎?為什么?(b)A中的元素在運(yùn)算+4和×4上有逆元嗎?第75頁，共175頁，2023年，2月20日，星期二yuliang@762023/5/26.6半群與獨(dú)異點(diǎn)+4012301230123123023013012×4012301230000012302020321(a)(b)第76頁，共175頁，2023年，2月20日，星期二yuliang@772023/5/26.6半群與獨(dú)異點(diǎn)子獨(dú)異點(diǎn)：設(shè)<S,*,e>是一個(gè)獨(dú)異點(diǎn)，TS且*在T上是封閉的，那么<T,*,e>是<S,*,e>的子代數(shù),<T,*,e>也是一個(gè)獨(dú)異點(diǎn)，稱為<S,*,e>的子獨(dú)異點(diǎn)。原代數(shù)系統(tǒng)的子代數(shù)本身是獨(dú)異點(diǎn)在相同運(yùn)算下，幺元相同第77頁，共175頁，2023年，2月20日，星期二yuliang@782023/5/26.6半群與獨(dú)異點(diǎn)【例題5】設(shè)N10={0,1,2,3,…,9},×10是模10乘法運(yùn)算，則<N10,×10>是一個(gè)獨(dú)異點(diǎn)，(a)寫出×10的運(yùn)算表；(b)取N10的一個(gè)子集A={0,2,4,6,8},證明<A,×10>是一個(gè)獨(dú)異點(diǎn)，但不是<N10,×10>的子獨(dú)異點(diǎn)；(c)構(gòu)造<N10,×10>的一個(gè)含有5個(gè)元素的子獨(dú)異點(diǎn)。第78頁，共175頁，2023年，2月20日，星期二yuliang@792023/5/26.6半群與獨(dú)異點(diǎn)交換半群（獨(dú)異點(diǎn)）：在半群（獨(dú)異點(diǎn)）中，若二元運(yùn)算是可交換的，則稱該半群（獨(dú)異點(diǎn)）為交換半群（獨(dú)異點(diǎn)）。注：概念只作了解。第79頁，共175頁，2023年，2月20日，星期二yuliang@802023/5/26.6半群和獨(dú)異點(diǎn)的性質(zhì)『定理』設(shè)<S,*>是一個(gè)半群，如果S是一個(gè)有限集，則必存在a∈S,使得a*a=a。證明：設(shè)|S|=n,因?yàn)?lt;S,*>是半群，任取b∈S,由運(yùn)算*的封閉性以及S為有限集知

b,b*b=b2,b*b*b=b3,…,bn,bn+1∈S根據(jù)抽屜原理，必有兩個(gè)元素相等,不妨設(shè)為bi=bj(其中j>i)。n+1第80頁，共175頁，2023年，2月20日，星期二yuliang@812023/5/26.6半群與獨(dú)異點(diǎn)的性質(zhì)令p=j-i,顯然有p≥1。由此可得bi=bj=bp+i=bp*bi。

bi=bp*bibi+1=bp*bi+1…bkp=bp*bkp又由bkp=bp*bkp知

bkp=b(k+1)pb(k+1)p=

b(k+2)p….b(2k-1)p=b2kp因此有

bkp＝b2kp＝bkp*

bkp令a=bkp，則有a=a*a，證畢。第81頁，共175頁，2023年，2月20日，星期二yuliang@822023/5/26.6半群與獨(dú)異點(diǎn)【思考題】設(shè)<S,*>是一個(gè)獨(dú)異點(diǎn)，*的運(yùn)算表中可能出現(xiàn)兩行或兩列完全相同嗎？解答：不可能。設(shè)S中關(guān)于運(yùn)算*的幺元是e。任取a,b∈S,若a≠b,則有

e*a≠e*b(任何兩列不同)

a*e≠b*e(任何兩行不同)所以運(yùn)算*的運(yùn)算表中任何兩行和兩列都是不同的。第82頁，共175頁，2023年，2月20日，星期二yuliang@832023/5/26.6半群與獨(dú)異點(diǎn)循環(huán)獨(dú)異點(diǎn)：設(shè)<S,*,e>是一個(gè)獨(dú)異點(diǎn)，若存在一個(gè)元素g∈S,對(duì)于S中的每一個(gè)元素a,都有一個(gè)對(duì)應(yīng)的k∈N使得a=gk，則稱此獨(dú)異點(diǎn)為循環(huán)獨(dú)異點(diǎn)。g稱為此循環(huán)獨(dú)異點(diǎn)的生成元。第83頁，共175頁，2023年，2月20日，星期二yuliang@842023/5/26.6半群與獨(dú)異點(diǎn)【例題6】判斷以下代數(shù)系統(tǒng)是否是循環(huán)獨(dú)異點(diǎn)，若是，指出生成元。(a)<N,+,0>;(b)<{a,b,c,d},*>,*的運(yùn)算表如下表所示。*abcdabcdabcdbadccdbadcab第84頁，共175頁，2023年，2月20日，星期二yuliang@852023/5/26.6本節(jié)小結(jié)半群半群定義：封閉、可結(jié)合子半群：子集、封閉，子代數(shù)，子半群半群性質(zhì)：有限半群中必有等冪元交換半群：可交換第85頁，共175頁，2023年，2月20日，星期二yuliang@862023/5/26.6本節(jié)小結(jié)獨(dú)異點(diǎn)獨(dú)異點(diǎn)定義：含幺元半群子獨(dú)異點(diǎn)：子集、封閉、含有幺元e，子代數(shù)交換獨(dú)異點(diǎn)：可交換循環(huán)獨(dú)異點(diǎn)：有一個(gè)生成元g,每個(gè)元素都可以用gk表示第86頁，共175頁，2023年，2月20日，星期二yuliang@872023/5/26.7群群：設(shè)<G,*>是一個(gè)代數(shù)系統(tǒng)，其中G是非空集合，*是G上一個(gè)二元運(yùn)算。如果滿足運(yùn)算*是封閉的，運(yùn)算*是可結(jié)合的，存在幺元e，對(duì)于每一個(gè)元素x∈G,都存在逆元x-1∈G，則稱<G,*>是一個(gè)群。半群獨(dú)異點(diǎn)群半群獨(dú)異點(diǎn)群第87頁，共175頁，2023年，2月20日，星期二yuliang@882023/5/26.7群【例題1】判斷以下代數(shù)系統(tǒng)是否是群？(a)<I,+>,I是整數(shù)集合，+是普通加法運(yùn)算。(b)<Q-{0},·>,Q是有理數(shù)集合，·是普通乘法運(yùn)算。(c)<I,·>，I是整數(shù)集合，·是普通乘法運(yùn)算。(d)<{a,b,c},*>,運(yùn)算*如下表所示。*abcabcabcbcacab第88頁，共175頁，2023年，2月20日，星期二yuliang@892023/5/26.7群【例題2】設(shè)有代數(shù)系統(tǒng)<I,°>，其中I是整數(shù)集合，運(yùn)算°的定義為，對(duì)任意a,b∈I,有

a°b=a+b-2試問<I,°>是否是群？解答：(i)對(duì)任意a,b∈I,a°b∈I,所以運(yùn)算°在I上是封閉的。第89頁，共175頁，2023年，2月20日，星期二yuliang@902023/5/26.7群(ii)對(duì)任意的a,b,c∈I,有

(a°b)°c=(a+b-2)°c=(a+b-2)+c-2=a+b+c-4

a°(b°c)=a+(b°c)-2=a+(b+c-2)-2=a+b+c-4所以°運(yùn)算滿足結(jié)合律。(iii)任取a∈I,a°e=a+e-2=a,得到e=2,所以2是幺元。(iv)任取a∈I,a°a-1=a+a-1-2=2,得到a-1=4-a∈I,因此I中每個(gè)元素都有逆元。由以上可知<I,°>是一個(gè)群。第90頁，共175頁，2023年，2月20日，星期二yuliang@912023/5/26.7群有限群：設(shè)<G,*>是一個(gè)群，如果G是有限集，則稱<G,*>為有限群。無限群：設(shè)<G,*>是一個(gè)群，如果G是無限集，則稱<G,*>為無限群。群的階數(shù)：有限群<G,*>的載體G的基數(shù)|G|，稱為群的階。第91頁，共175頁，2023年，2月20日，星期二yuliang@922023/5/26.7群的性質(zhì)性質(zhì)一：群中無零元。說明：當(dāng)群中只有一個(gè)元素的時(shí)候，一般的把它看作幺元，如果它是零元的話，它就不符合群的定義了。因?yàn)榱阍獩]有逆元，零元與任何元素進(jìn)行操作結(jié)果都是零元。如果群中有零元，則不符合群的定義了(任何一個(gè)元素都有逆元)。第92頁，共175頁，2023年，2月20日，星期二yuliang@932023/5/26.7群的性質(zhì)性質(zhì)二：群中每個(gè)元素的逆元都是唯一的。說明：前面我們學(xué)過一個(gè)定理6.1-3，對(duì)于可結(jié)合運(yùn)算，如果一個(gè)元素x有左逆元l和右逆元r,那么l=r（即逆元是唯一的）