離散數學第十二章 代數結構基本概念及性質

離散數學第十二章代數結構基本概念及性質第1頁，課件共98頁，創(chuàng)作于2023年2月12.1代數結構的定義與例在正式給出代數結構的定義之前，先來說明什么是在一個集合上的運算，因為運算這個概念是代數結構中不可缺少的基本概念。定義12.1.1

設S是個非空集合且函數 或f:Sn

→S，則稱f為一個n元運算。其中n是自然數，稱為運算的元數或階。當n=1時，稱f為一元運算，當n=2時，稱f為二元運算，等等。第2頁，課件共98頁，創(chuàng)作于2023年2月注意，n元運算首先是一個函數，其次是個閉運算(所謂閉運算是指：集合上的運算，其運算結果都在原來的集合中，我們把具有這種特征的運算稱作封閉的，簡稱閉運算)。封閉性表明了n元運算與一般函數的區(qū)別之處。此外，有些運算存在幺元或零元，它在運算中起著特殊的作用，稱它為S中的特異元或常數。第3頁，課件共98頁，創(chuàng)作于2023年2月運算的例子很多，例如，在數理邏輯中，否定是謂詞集合上的一元運算，合取和析取是謂詞集合上的二元運算；在集合論中，并與交是集合上的二元運算；在整數算術中，加、減、乘運算是二元運算，而除運算便不是二元運算，因為它不滿足封閉性。第4頁，課件共98頁，創(chuàng)作于2023年2月在下面討論的代數結構中，主要限于一元和二元運算，將用'、┐或ˉ等符號表示一元運算符；用

、

、⊙、○、∧、∨、∩、∪等表示二元運算符，一元運算符常常習慣于前置、頂置或肩置，如┐x、、x'；而二元運算符習慣于前置、中置或后置，如：+xy，x+y，xy+。有了集合上運算的概念后，便可定義代數結構了。第5頁，課件共98頁，創(chuàng)作于2023年2月定義12.1.2

設S是個非空集合且fi是S上的ni元運算，其中i=1，2，…，m。由S及f1，f2，…，fm組成的結構，稱為代數結構，記作<S，f1，f2，…，fm>。例：設Z是整數集，“＋”是Z上的普通加法運算，則<Z，＋>是一個代數結構。例：設R是實數集，“＋”與“×”是實數集R上的普通加法和乘法運算，則<R,＋,×>是一個代數結構。第6頁，課件共98頁，創(chuàng)作于2023年2月例：我們可以構造下述的一個代數結構：設有一個由有限個字母組成的集合∑

，叫字母表，在∑上任意長的字母串，叫做∑上句子或字符串，串中字母的個數m叫這個串的長度，我們假定當一個字的長度m=0時用符號

表示，它叫做空串。這樣我們可以構造一個在∑上的所有串的集合∑*。其次，我們定義一個在∑*上的運算“//”——并置運算或者連接運算，設

，

∑*，則

//

＝

。通過并置運算將兩個串聯成一個新的串，而此聯成的新串也在∑*內，這樣構造的<∑*，//>是一個代數結構第7頁，課件共98頁，創(chuàng)作于2023年2月如果令∑+＝∑*－{

}，則<∑+，//>也是一個代數結構。這兩種代數結構都是計算機科學中經常要用到的代數結構。第8頁，課件共98頁，創(chuàng)作于2023年2月例：設有一計算機它的字長是32位，它以定點加、減、乘、除及邏輯加、邏輯乘為運算指令，并分別用01，02，…，06表示之。則在該計算機中由232有限個不同的數字所組成的集合S以及計算機的運算型機器指令就構成了一個代數結構<S，01，02，…，06>。第9頁，課件共98頁，創(chuàng)作于2023年2月因此，一個代數結構需要滿足二個條件：

(1)有一個非空集合S

(2)在集合S上定義的運算一定是封閉的第10頁，課件共98頁，創(chuàng)作于2023年2月此外，我們把集合S的基數即|S|，定義為代數結構的基數。如果S是有限集合，則說代數結構是有限代數結構；否則便說是無窮代數結構.有時，要考察兩個或多個代數結構，這里就有個是否同類型之說，請看下面定義：第11頁，課件共98頁，創(chuàng)作于2023年2月定義12.1.3

設兩個代數結構<S，f1，f2，…，fm>和<T，g1，g2，…，gm>，如果fi和gi(1≤i≤m)具有相同的元數，則稱這兩個代數結構是同類型的。可見，判定兩個代數結構是否同類型，主要是對其運算進行考察：①兩個代數結構是否有相同個數的運算符；②每個相對應的運算符是否有相同的元數。第12頁，課件共98頁，創(chuàng)作于2023年2月例：代數結構<N，＋>與代數結構<Z，×>是相同類型的，因為它們都有一個二元運算符。例：代數結構<Z，＋，×>與<N，＋>的類型是不相同的，因為它們的運算符的個數不同。第13頁，課件共98頁，創(chuàng)作于2023年2月例：設S是非空集合，P(S)是它的冪集。對任意集合A，B∈P(S)上的運算

和

如下:A

B=(A－B)∪(B－A)A

B=A∩B

則<P(S)，

，

>是一代數結構。因為，顯然

和

是閉運算。<R，＋，×>與<P(S)，

，

>是同類型代數結構的。有時還需要在代數結構中集合的某個子集上討論其性質，這就引出子代數結構的概念.第14頁，課件共98頁，創(chuàng)作于2023年2月定義12.1.4

設<S，f1，f2，…，fm>是一代數結構，且非空集T

S在運算f1，f2，…，fm作用下是封閉的，且T含有與S中相同的特異元，則稱<T，f1，f2，…，fm>為代數結構<S，f1，f2，…，fm>的子代數。記為<T，f1，…>

<S，f1，…>。例：設E是所有偶數所組成的集合，則代數結構<E，＋>是<Z，＋>的一個子代數結構例：顯然，<Z，＋，×>

<R，＋，×>.第15頁，課件共98頁，創(chuàng)作于2023年2月12.2代數結構的基本性質所謂代數結構的性質即是結構中任何運算所具有的性質。以下我們均假設運算為二元運算。1.結合律給定<S，⊙>，則運算“⊙”滿足結合律或“⊙”是可結合的，即(

x)(

y)(

z)(x,y,z∈S→(x⊙y)⊙z=x⊙(y⊙z))第16頁，課件共98頁，創(chuàng)作于2023年2月例12.2.1

給定<A，⊙>且對任意a，b∈A有a⊙b=b。證明運算“⊙”是可結合的。證明：因為對任意a，b，c∈A

(a⊙b)⊙c=b⊙c=c

a⊙(b⊙c)=a⊙c=c

故(a⊙b)⊙c=a⊙(b⊙c)注意，不是任何代數結構上的運算都滿足結合律，如整數集上“－”運算就不滿足結合律。如：5－(2－1)＝4,但是(5－2)－1＝2.第17頁，課件共98頁，創(chuàng)作于2023年2月2.交換律給定<S，⊙>，則運算“⊙”滿足交換律或“⊙”是可交換的，即(

x)(

y)(x,y∈S→x⊙y=y⊙x)。例12.2.2

給定<Q，○>，其中Q為有理數集合，并且對任意a，b∈Q有a○b=a+b-a·b，問運算○是否可交換?證：a○b=a+b-a·b=b+a

-b·a＝b○a，故運算○是可交換的。第18頁，課件共98頁，創(chuàng)作于2023年2月同樣，并不是所有代數結構上運算均滿足交換律，如矩陣的乘法就不滿足交換律。易見，如果一代數結構中的運算⊙是可結合和可交換的，那么，在計算a1⊙a2⊙···⊙am時可按任意次序計算其值。特別當a1＝a2＝···＝am＝a時，則a1⊙a2⊙···⊙am＝am。稱am為a的m次冪，m稱a的指數。下面給出am的歸納定義：第19頁，課件共98頁，創(chuàng)作于2023年2月設有<S，⊙>且a

S，對于m

Z+，其中Z+表示正整數集合，可有：(1)a1=a(2)am+1=am⊙a由此利用歸納法不難證明指數定律：(1)am⊙an=am+n(2)(am)n=amn這里，m,n

Z+。類似地定義某代數結構中的負冪和給出負指數定律。第20頁，課件共98頁，創(chuàng)作于2023年2月3.分配律一個代數結構若具有兩個運算時，則分配律可建立這兩個運算之間的某種聯系。給定<S，⊙，○>，稱運算⊙對于○滿足左分配律，或者⊙對于○是可左分配的，如果有(

x)(

y)(

z)(x,y,z∈S→x⊙(y○z))=(x⊙y)○(x⊙z))同理，稱運算⊙對于○滿足右分配律或⊙對于○是可右分配的，如果有(

x)(

y)(

z)(x,y,z∈S→(y○z)⊙x=(y⊙x)○(z⊙x))第21頁，課件共98頁，創(chuàng)作于2023年2月類似地可定義○對于⊙是滿足左或右分配律.若⊙對于○既滿足左分配律又滿足右分配律，則稱⊙對于○滿足分配律或是可分配的。同樣可定義○對于⊙滿足分配律。由定義不難證明下面定理：定理12.2.1

給定<S，⊙，○>且⊙是可交換的。如果⊙對于○滿足左或右分配律，則⊙對于○滿足分配律。第22頁，課件共98頁，創(chuàng)作于2023年2月例12.2.3

給定<B,⊙,○>，其中B={0,1}。表12.2.1分別定義了運算⊙和○，問運算⊙對于○是可分配的嗎？○對于⊙呢？第23頁，課件共98頁，創(chuàng)作于2023年2月形如表12.2.1的表常常被稱為運算表或復合表，它由運算符、行表頭元素、列表頭元素及復合元素四部分組成。當集合S的基數很小，特別限于幾個時，代數結構中運算常常用這種表給出。其優(yōu)點簡明直觀，一目了然。解可以驗證⊙對于○是可分配的，但○對于⊙并非如此。因為1○(0⊙1)

(1○0)⊙(1○1)

10100第24頁，課件共98頁，創(chuàng)作于2023年2月4.吸收律給定<S，⊙，○>，則⊙對于○滿足左吸收律

:=(

x)(

y)(x,y∈S→x⊙(x○y)=x)⊙對于○滿足右吸收律

:=(

x)(

y)(x,y∈S→(x○y)⊙x=x)第25頁，課件共98頁，創(chuàng)作于2023年2月若⊙對于○既滿足左吸收律又滿足右吸收律，則稱⊙對于○滿足吸收律或可吸收的?！饘τ诤臀章深愃频囟x。若⊙對于○是可吸收的且○對于⊙也是可吸收的，則⊙和○是互為吸收的或⊙和○同時滿足吸收律。第26頁，課件共98頁，創(chuàng)作于2023年2月例12.2.4

給定<N，⊙，○

>，其中N是自然數集合，⊙和○定義如下：對任意a，b∈N有a⊙b=max{a，b}，a○

b=min{a，b}，試證，⊙和○互為吸收的。證明：不妨假設a＞ba⊙(a○b)=max{a，min{a，b}}=a(a○b)⊙a=max{min{a，b}

，a}=a故⊙對于○滿足吸收律。同理可證，○對于⊙滿足吸收律。故⊙和○互為吸收的。第27頁，課件共98頁，創(chuàng)作于2023年2月5.等冪律與等冪元給定<S，⊙>，則“⊙”是等冪的或“⊙”滿足等冪律:=(

x)(x∈S→x⊙x=x)給定<S，⊙>且x∈S，則x是關于“⊙”的等冪元:=x⊙x=x于是，不難證明下面定理：定理12.2.2

若x是<S，⊙>中關于⊙的等冪元，對于任意正整數n，則xn=x。第28頁，課件共98頁，創(chuàng)作于2023年2月例12.2.5

給定<P(S)，∪，∩>，其中P(S)是集合S的冪集，∪和∩分別為集合的并和交運算。驗證：∪和∩是等冪的。證：對任意A

P(S)，有A∪A=A和A∩A=A，故∪和∩是等冪的。第29頁，課件共98頁，創(chuàng)作于2023年2月6.幺元或單位元給定<S，⊙>且el，er，e∈S，則el為關于⊙的左幺元:=(

x)(x∈S→el⊙x=x)er為關于⊙的右幺元:=(

x)(x∈S→x⊙er=x)若e既為⊙的左幺元又為⊙的右幺元，稱e為關于⊙的幺元。亦可定義如下：e為關于⊙的幺元:=(

x)(x∈S→e⊙x=x⊙e=x)。第30頁，課件共98頁，創(chuàng)作于2023年2月定理12.2.3

給定<S，⊙>且el和er分別是關于⊙的左、右幺元，則el=er=e且幺元e唯一。例：實數集R上的代數結構<R，＋，×>的“×”運算的幺元為1，因為對任意x

R有x×1＝1×x＝x。而“＋”運算的幺元為0，因為對任意x

R有x＋0＝0＋x＝x。例：前面例子中關于串的并置運算，它的單位元素是空串

，因為對任一串A，均有

//A=A

//=A。第31頁，課件共98頁，創(chuàng)作于2023年2月7.零元給定<S，○>及θl，θr，θ∈S，則θl為關于○的左零元:=(

x)(x∈S→θl○x=θl)θr為關于○的右零元:=(

x)(x∈S→x○θr=θr)θ為關于○的零元:=(

x)(x∈S→θ○x=x○θ=θ)第32頁，課件共98頁，創(chuàng)作于2023年2月定理12.2.4

給定<S，⊙>且θl和θr分別為關于⊙的左零元和右零元，則θl=θr=θ且零元θ是唯一的。定理12.2.5

給定<S，⊙>且|S|＞1。如果θ，e∈S，其中θ和e分別為關于⊙的零元和幺元，則θ≠e。第33頁，課件共98頁，創(chuàng)作于2023年2月例：代數結構<Z，×>上的零元是“0”，因為對于任何整數x，均有x×0＝0×x＝0。例：正整數集Z+上的運算“min”，叫“取最小”運算。min(a,b)為取a,b的最小者。代數結構<Z+，min>中對應于運算“min”的零元為1。第34頁，課件共98頁，創(chuàng)作于2023年2月8．逆元給定<S，⊙>且幺元e，x∈S，則x為關于⊙的左逆元:=(

y)(y∈S∧x⊙y=e)x為關于⊙的右逆元:=(

y)(y∈S∧y⊙x=e)x為關于⊙可逆的:=(

y)(y∈S∧y⊙x=x⊙y=e)第35頁，課件共98頁，創(chuàng)作于2023年2月給定<S，⊙>及幺元e；x，y∈S，則y為x的左逆元:=y⊙x=ey為x的右逆元:=x⊙y=ey為x的逆元:=y⊙x=x⊙y=e第36頁，課件共98頁，創(chuàng)作于2023年2月顯然，若y是x的逆元，則x也是y的逆元，因此稱x與y互為逆元。通常x的逆元表示為x-1。一般地說來，一個元素的左逆元不一定等于該元素的右逆元。而且，一個元素可以有左逆元而沒有右逆元，反之亦然。甚至一個元素的左或右逆元還可以不是唯一的。第37頁，課件共98頁，創(chuàng)作于2023年2月定理12.2.6

給定<S，⊙>及幺元e∈S。如果⊙是可結合的并且一個元素x的左逆元xl-1和右逆元xr-1存在，則xl-1=xr-1。定理12.2.7

給定<S，⊙>及幺元e∈S。如果⊙是可結合的并且x的逆元x-1存在，則x-1是唯一的。第38頁，課件共98頁，創(chuàng)作于2023年2月例：代數結構<Z，＋>上的幺元是“0”，對于任何整數x，它的逆元是－x，因為x＋(－x)＝0。例：代數結構<R，＋，×>中0和1分別為＋和×的幺元。對于“＋”，對每個元素r

R都有逆元－r；對于“×”，對每個元素

r

R都有逆元1/r(r0)

。第39頁，課件共98頁，創(chuàng)作于2023年2月9.可約律與可約元給定<S，⊙>且零元θ∈S，則⊙滿足左可約律或是左可約的

:=(

x)(

y)(

z)((x,y,z∈S∧x≠θ∧x⊙y=x⊙z)→y=z)，并稱x是關于⊙的左可約元?！褲M足右可約律或是右可約的

:=(

x)(

y)(

z)((x,y,z∈S∧x≠θ∧y⊙x=z⊙x)→y=z)，并稱x是關于⊙的右可約元。第40頁，課件共98頁，創(chuàng)作于2023年2月若⊙既滿足左可約律又滿足右可約律或⊙既是左可約又是右可約的，則稱⊙滿足可約律或⊙是可約的。若x既是關于⊙的左可約元又是關于⊙的右可約元，則稱x是關于⊙的可約元?？杉s律與可約元也可形式地定義如下：第41頁，課件共98頁，創(chuàng)作于2023年2月⊙滿足可約律:=(

x)(

y)(

z)(x,y,z∈S∧x≠θ∧((x⊙y=x⊙z∧y⊙x=z⊙x)→y=z))x是關于⊙的可約元:=(

y)(

z)(y,z∈S∧x≠θ∧((x⊙y)=x⊙z∧y⊙x=z⊙x)→y=z))第42頁，課件共98頁，創(chuàng)作于2023年2月例：給定<Z，×>，其Z是整數集合，×是一般乘法運算。顯然，每個非零整數都是可約元，而且運算×滿足可約律。第43頁，課件共98頁，創(chuàng)作于2023年2月定理12.2.8

給定<S，○>且○是可結合的，如果x是關于○可逆的且x≠θ，則x也是關于○的可約元。證明設任意y,z

S且有x○y=x○z或y○x=z○x。因為○是可結合的及x是關于○可逆的，則有x-1○(x○y)=(x-1○x)○y=e○y=yx-1○(x○z)=(x-1○x)○z=e○z=z第44頁，課件共98頁，創(chuàng)作于2023年2月故得x○y=x○z

y=z，故x是關于○的左可約元。同樣可證得y○x=z○x

y=z，故x是關于○的右可約元。故x是關于○的可約元。最后，作一補充說明，用運算表定義一代數結構的運算，從表上很能反映出關于運算的各種性質。為確定起見，假定<S，○>及x，y，θ，e∈S。第45頁，課件共98頁，創(chuàng)作于2023年2月(1)運算○具有封閉性，當且僅當表中的每個元素都屬于S。(2)運算○滿足交換律，當且僅當表關于主對角線是對稱的。第46頁，課件共98頁，創(chuàng)作于2023年2月(3)運算○是等冪的，當且僅當表的主對角線上的每個元素與所在行或列表頭元素相同?！餫bc…aabbcc……第47頁，課件共98頁，創(chuàng)作于2023年2月(4)元素x是關于○的左零元，當且僅當x所對應的行中的每個元素都與x相同；元素y是關于○的右零元，當且僅當y所對應的列中的每個元素都與y相同；元素

是關于○的零元，當且僅當

所對應的行和列中的每個元素都與

相同?！餷mn…axxxx…c…左零元x○mny…aybycy……右零元y○mn

…a

…c

……零元

第48頁，課件共98頁，創(chuàng)作于2023年2月(5)元素x為關于○的左幺元，當且僅當x所對應的行中元素依次與行表頭元素相同；元素y為關于○的右幺元，當且僅當y所對應的列中元素依次與列表頭元素相同；元素e是關于○的幺元，當且僅當e所對應的行和列中元素分別依次與行表頭元素和列表頭元素相同?！餷mn…axlmn…c…左幺元x○mny…aabbcc……右幺元y○mne…aaemne…cc……幺元e第49頁，課件共98頁，創(chuàng)作于2023年2月(6)x為關于○的左逆元，當且僅當位于x所在行的元素中至少存在一個幺元，y為關于○的右逆元，當且僅當位于y所在列的元素中至少存在一個幺元；x與y互為逆元，當且僅當位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是幺元?！餷mn…axec…左逆元○mny…aebc…右逆元○mxy…xebye…逆元第50頁，課件共98頁，創(chuàng)作于2023年2月例12.2.8

給定<S，○>，其中S={α，β，γ，δ，ζ}且○的定義如表12.2.5所示。試指出該代數結構中各元素的左、右逆元情況。表12.2.5解：α是幺元；β的左逆元和右逆元都是γ，即β與γ互為逆元；δ的左逆元是γ而右逆元是β；β有兩個左逆元γ和δ；ζ的右逆元是γ，但ζ沒有左逆元?！穰力娄忙摩痞力娄忙摩痞力娄忙摩痞娄摩力忙摩忙力娄力娄摩力忙摩忙痞摩力忙啤?/p>

eβγδζeβγδζ

eβγδζβδeγδγeβeβδeγδγζδeγζ第51頁，課件共98頁，創(chuàng)作于2023年2月12.3同態(tài)與同構本節(jié)將闡明兩個重要概念——同態(tài)與同構。在以后各節(jié)中，它們會經常被使用到。第52頁，課件共98頁，創(chuàng)作于2023年2月定義12.3.1

設<X，⊙>與<Y，○>是同類型的。稱<X，⊙>同態(tài)于<Y，○>或<Y，○>為<X，⊙>的同態(tài)象，記為<X，⊙>~<Y，○>，其定義如下：

<X，⊙>~

<Y，○>

:=(

f)(f∈YX∧(

x1)(

x2)(x1,x2∈X→f(x1⊙x2)=f(x1)○f(x2)))同時，稱f為從<X，⊙>到<Y，○>的同態(tài)映射.可以看出，同態(tài)映射f不必是惟一的。第53頁，課件共98頁，創(chuàng)作于2023年2月

Xx1x2x3x1⊙x3f(X)y1=f(x1)f(x1)=f(x2)y3=f(x3)y1○y3Y同態(tài)示意圖f第54頁，課件共98頁，創(chuàng)作于2023年2月例12.3.1

給定<R，＋>和<R，×>，其中R是實數集合，＋和×分別是加法和乘法運算，試證<R，＋>~<R，×>。證：關鍵是找一個同態(tài)映射。今構造函數f∈RR如下：f(x)=ax,其中a＞0,x∈R則f為所求的同態(tài)映射，這是因為對任意y,z∈R，有f(y＋z)=ay＋z＝ay×az＝f(y)×f(z)因此，<R，＋>~<R，×>第55頁，課件共98頁，創(chuàng)作于2023年2月兩個同類型的代數結構間的同態(tài)定義不僅適用于具有一個二元運算的代數結構，也可以推廣到具有多個二元運算的任何兩個同類型代數結構。例如，對于具有兩個二元運算的兩個同類型代數結構<X,⊙,○>和<Y,

,

>的同態(tài)定義如下：<X,⊙,○>~<Y,

,

>:=(

f)(f

YX∧(

x1)(

x2)(x1,x2

X

(f(x1⊙x2)=f(x1)

f(x2)∧f(x1○x2)=f(x1)

f(x2)))第56頁，課件共98頁，創(chuàng)作于2023年2月定理12.3.1

如果<X，⊙>~

<Y，○>且f為其同態(tài)映射，則<rn(f)，○>

<Y，○>。由于函數f

YX的不同性質，將給出不同種類的同態(tài)定義。第57頁，課件共98頁，創(chuàng)作于2023年2月定義12.3.2

設<X，⊙>~

<Y，○>且f為其同態(tài)映射。(i)如果f為滿射，則稱f是從<X，⊙>到<Y，○>的滿同態(tài)映射。(ii)如果f為單射(或一對一映射)，則稱f為從<X，⊙>到<Y，○>的單一同態(tài)映射。第58頁，課件共98頁，創(chuàng)作于2023年2月(iii)如果f為雙射(或一一對應)，則稱f為從<X，⊙>到<Y，○>的同構映射。記為<X,⊙>≌<X,○>。顯然，若f是從<X，⊙>到<Y，○>的同構映射，則f為從<X，⊙>到<Y，○>的滿同態(tài)映射及單一同態(tài)映射，反之亦然。第59頁，課件共98頁，創(chuàng)作于2023年2月例12.3.3

設<Σ*，∥>與<N，+>是同類型的，其中Σ*為有限字母表上的字母串集合，∥為并置運算，N為自然數集合，+為普通加法。若定義f：Σ*→N為f(x)=|x|其中x∈Σ*，|x|表示字母串的長度。因為對任意x，y∈Σ*，有f(x∥y)=|x∥y|=|x|+|y|=f(x)+f(y)，故<Σ*，∥>~<N，+>。顯然，f是滿射，因此，f為從<Σ*，∥>到<N，+>的滿同態(tài)映射。第60頁，課件共98頁，創(chuàng)作于2023年2月例12.3.4

給定<Z,+>，其中Z為整數集合，+為一般加法。作函數f

ZZ：f(x)=kx，(此處乘法是一般乘法)其中x,k

Z則當k

0時，由于f(y+z)=k(y+z)=ky+kz=f(y)+f(z)，故f為<Z,+>到<Z,+>的同態(tài)映射。又易知f為單射，故f為<Z,+>到<Z,+>的單一同態(tài)映射。當k=-1或k=1時，f為從<Z,+>到<Z,+>的同構映射(我們稍后再來證明)。第61頁，課件共98頁，創(chuàng)作于2023年2月綜上可以看出，同態(tài)映射具有一個特性，即“保持運算”。對于滿同態(tài)映射來說，它能夠保持運算的更多性質，為此，給出如下定理：定理12.3.2

給定<X,⊙,○>~

<Y,

,

>且f為其滿同態(tài)映射，則(a)如果⊙和○滿足結合律，則

和

也滿足結合律。(b)如果⊙和○滿足交換律，則

和

也滿足交換律。第62頁，課件共98頁，創(chuàng)作于2023年2月(c)如果⊙對于○或○對于⊙滿足分配律，則

對于

或

對于

也相應滿足分配律。(d)如果⊙對于○或○對于⊙滿足吸收律，則

對于

或

對于

也滿足吸收律。(e)如果⊙和○滿足等冪律，則

和

也滿足等冪律。(f)如果e1和e2分別是關于⊙和○的幺元，則f(e1)和f(e2)分別為關于

和

的幺元。第63頁，課件共98頁，創(chuàng)作于2023年2月(g)如果θ1和θ2分別是關于⊙和○的零元，則f(θ1)和f(θ2)分別為關于

和

的零元。(h)如果對每個x∈X均存在關于⊙的逆元x-1，則對每個f(x)∈Y也均存在關于

的逆元f(x-1)；如果對每個z∈X均存在關于○的逆元z-1，則對每個f(z)∈Y也均存在關于

的逆元f(z-1)。第64頁，課件共98頁，創(chuàng)作于2023年2月定理12.3.2告訴我們，對于滿同態(tài)映射來說，代數結構的許多性質都能保持，如結合律、交換律、分配律、等冪律、幺元、零元、逆元等，但這種保持性質是單向的，即如果<X，⊙>滿同態(tài)于<Y，○>，則<X，⊙>所具有的性質，<Y，○>均具有。但反之不然，即<Y，○>所具有的某些性質，<X，⊙>不一定具有。不盡要問，在怎樣條件下，<Y，○>所具有的性質<X，⊙>都完全具有呢?為了回答這個問題，需要引出兩個代數結構同構的概念。第65頁，課件共98頁，創(chuàng)作于2023年2月定義12.3.3

設<X，⊙>與<Y，○>是同類型的。稱<X，⊙>同構于<Y，○>，記為<X，⊙>≌<Y，○>，其定義如下：<X，⊙>≌<Y，○>:=(

f)(f為從<X，⊙>到<Y，○>的同構映射)或更詳細地定義為：<X，⊙>≌<Y，○>:=(

f)(f∈YX∧f為雙射∧f為從<X，⊙>到<Y，○>的同態(tài)映射)第66頁，課件共98頁，創(chuàng)作于2023年2月<X,⊙>x1x2x1⊙x2<Y，○>f(x1)f(x2)f(x1)○f(x2)同構示意圖f第67頁，課件共98頁，創(chuàng)作于2023年2月例代數結構<R+，×>與<R，＋>是同構的。其中R為實數，R+為正實數。證：關鍵是找一個雙射。對<R+，×>與<R，＋>，有一個函數h：R+→R，h(x)=lnx此函數是雙射的。因為對每個x>0,均存在一個y=lnx

R，同時，對每個y

R，均存在一個x=ey

R+.又因為h(y×z)=ln(y×z)=lny＋lnz=h(y)＋h(z)故<R+，×>與<R，＋>是同構的。注：當然，我們也可以取函數h(x)=lgx，第68頁，課件共98頁，創(chuàng)作于2023年2月續(xù)例12.3.4

給定<Z,+>，其中Z為整數集合，+為一般加法。作函數f

ZZ：f(x)=kx，(此處乘法是一般乘法)其中x,k

Z，則當k=-1或k=1時，f為從<Z,+>到<Z,+>的同構映射。證：先證明當k=-1或k=1時f為雙射。因為對每個x

Z,均存在一個y=kx(即y=x或y=-x)

Z，同時，對每個y

Z，均存在一個x=y/k

(即x=y或x=-y)

Z。(顯然，若k取

1以外的值，y/k不一定是整數，或者y/k無意義，此時f就不是雙射了.)又由于f(y+z)=k(y+z)=ky+kz=f(y)+f(z)，故f為<Z,+>到<Z,+>的同構映射。第69頁，課件共98頁，創(chuàng)作于2023年2月例代數結構<{0,1}，∨>與<{M,H}，＋>是同構的。其中M,H分別表示低電平、高電平，“＋”表示或門，它們的運算表如下。證：這兩個代數結構間存在一個函數f:{0,1}→{M,H}，且f(0)=M,f(1)=H，顯然這是一個雙射，而且有f(x∨y)=f(x)+f(y)。故它們是同構的?！?1001111＋MHMMHHHH第70頁，課件共98頁，創(chuàng)作于2023年2月例設S={4,5,6},在S上的二元運算“

”其定義如下表所示。又有P={1,2,3}及在P上的二元運算“

”，其運算表如下表所示。這樣所構成的兩個代數結構<S，

>與<P，

>是同構的。證：這兩個代數結構間存在一個函數f:{4,5,6}→{1,2,3}，f(x)=x-3，其中x

S。顯然這是一個雙射，而且有f(x

y)=f(x)

f(y)。故它們是同構的。

456445454556456

123112121223123第71頁，課件共98頁，創(chuàng)作于2023年2月由定義可知，同構的條件比同態(tài)強，關鍵是同構映射是雙射，即一一對應。而同態(tài)映射不一定要求是雙射。正因為如此，同構不再僅僅象滿同態(tài)那樣對保持運算是單向的了，而對保持運算成為雙向的。兩個同構的代數，表面上似乎很不相同，但在結構上實際是沒有什么差別，只不過是集合中的元素名稱和運算的標識不同而已，而它們的所有發(fā)生“彼此相通”。第72頁，課件共98頁，創(chuàng)作于2023年2月這樣，當探索新的代數結構的性質時，如果發(fā)現或者能夠證明該結構同構于另外一個性質已知的代數結構，便能直接地知道新的代數結構的各種性質了。對于同構的兩個代數結構來說，在它們的運算表中除了元素和運算的標記不同外，其它一切都是相同的。因此，可以根據這些特征來識別同構的代數結構。第73頁，課件共98頁，創(chuàng)作于2023年2月下面給出兩個二元運算的代數結構的同構定義定義設兩個代數結構<X，⊙，○>與<Y，

，

>，如果它們之間存在一個雙射f：X→Y，使得任意x1,x2

X，有f(x1⊙x2)=f(x1)

f(x2)f(x1○x2)=f(x1)

f(x2)則說此兩個代數結構是同構的。第74頁，課件共98頁，創(chuàng)作于2023年2月例12.3.6

給定<S，∪，∩>，其中S={

，A，B，C}，∪和∩是一般的集合運算；又有<T，

，

>，這里T={1，2，5，10}，且對于a，b∈T有a

b=lcm{a，b}(最小公倍數)，a

b=gcd{a，b}(最大公約數)，表12.3.3至表12.3.6給出四個運算表。試說明<S，∩，∪>≌<T，

，

>.第75頁，課件共98頁，創(chuàng)作于2023年2月 表12.3.3 表12.3.4

表12.3.5 表12.3.6∪

ABC

ABCAAACCBBCBCCCCCC∩

ABC

A

A

AB

BBC

ABC

1

25101

1

2510222101055105101010101010

1

25101

1

11121212511551012510第76頁，課件共98頁，創(chuàng)作于2023年2月解：令f

TS：f(

)=1，f(A)=2，f(B)=5，f(C)=10。顯然，f是從S到T的雙射。經驗證，對任意x1,x2

S，又有f(x1∪x2)=f(x1)

f(x2)f(x1∩x2)=f(x1)

f(x2)故<S，∩，∪>與<T，

，

>是同構的。第77頁，課件共98頁，創(chuàng)作于2023年2月同構是一個關系，而且可以證明它是個等價關系，對此有如下定理：定理12.3.3

代數結構間的同構關系是等價關系。第78頁，課件共98頁，創(chuàng)作于2023年2月證明顯然<S，⊙>≌<S，⊙>，因為恒等映射是同構映射。又若<S，⊙>≌<T,○>且f為其同構映射，則f--1為從<T,○>到<S，⊙>的同構映射。因此，<T,○>≌<S，⊙>。再令<S，⊙>≌<T,○>及<T,○>≌<R，

>，則<S，⊙>≌<R，

>。這里因為若f為<S，⊙>到<T,○>的同構映射，g為<T,○>到<R，

>的同構映射，則g

f為從<S，⊙>到<R，

>的同構映射?？梢娡瑯嬯P系滿足自反性、對稱性和傳遞性。因此，同構關系是等價關系。第79頁，課件共98頁，創(chuàng)作于2023年2月由于同構關系是等價關系，故令所有的代數結構構成一個集合S，于是可按同構關系將其分類，得到商集S/≌

。因為同構的代數結構具有相同的性質，故實際上代數結構所需要研究的總體并不是S而是S/≌

。在同態(tài)與同構中有一個特例，即具有相同集合的任兩個代數結構的同態(tài)與同構，這便是自同態(tài)與自同構。第80頁，課件共98頁，創(chuàng)作于2023年2月定義12.3.4

給定<S，⊙>及f∈SS。f為自同態(tài)映射:=f為從<S，⊙>到<S，⊙>的同態(tài)映射。f為自同構映射:=f為從<S，⊙>到<S，⊙>的同構映射。例12.3.7

在例12.3.4中，當k≠0時，f=kx是從<Z，+>到<Z，+>的自同態(tài)映射；當k=1或k=-1時，f=kx是從<Z，+>到<Z，+>的自同構映射。第81頁，課件共98頁，創(chuàng)作于2023年2月12.4同余關系本節(jié)主要闡明同態(tài)與同余關系之間的聯系。主要內容如下：定義12.4.1

給定<S，⊙>，且E為S中的等價關系。E有代換性質:=(

x1)(

x2)(

y1)(

y2)((x1,x2,y1,y2∈S∧x1Ex2∧y1Ey2)→(x1⊙y1)E(x2⊙y2))。E為<S，⊙>中的同余關系:=E有代換性質。第82頁，課件共98頁，創(chuàng)作于2023年2月與此同時，稱同余關系E的等價類為同余類。由定義可知，同余關系是代數結構的集合中的一類特殊的等價關系，并且在運算的作用下，能夠保持關系的等價類。即在x1⊙y1中，如果用集合S中的與x1等價的任何其它元素x2代換x1，并且用與y1等價的任何其它元素y2代換y1，則所求的結果x2⊙y2與x1⊙y1位于同一等價類之中。第83頁，課件共98頁，創(chuàng)作于2023年2月亦即若[x1]E=[x2]E并且[y1]E=[y2]E，則[x1⊙y1]E=[x2⊙y2]E。此外，同余關系與運算密切相關。如果一個代數結構中有多個運算，則需要考察等價關系對于所有這些運算是否都有代換性質。如果有，則說該代數結構存在同余關系；否則，同余關系不存在。第84頁，課件共98頁，創(chuàng)作于2023年2月[x1]Ex1x2[x1⊙y1]Ex1⊙y1x2⊙y2[y1]Ey1y2同余關系示意圖第85頁，課件共98頁，創(chuàng)作于2023年2月例12.4.1

給定<Z,+,

>，其中Z是整數集合，+和

是一般加、乘法。假設Z中的關系R定義如下：i1Ri2:=|i1|=|i2|，其中i1、i2

Z試問，R為該結構的同余關系嗎？第86頁，課件共98頁，創(chuàng)作于2023年2月解顯然，R為Z中的等價關系。接著先考察R對于+運算的代換性質：若取i1,-i1,i2

Z，則有|i1|=|-i1|和|i2|=|i2|，于是，下式(i1R(-i1))∧(i2Ri2)

(i1+i2)R(-i1+i2)不真。這是因為前件為真，后件為假。故R對于+運算不具有代換性質。第87頁，課件共98頁，創(chuàng)作于2023年2月至此可以說，R不是該結構的同余關系。但為了熟悉驗證一個關系是否為同余關系，還是來考察R對于

的代換性質。令i1,i2,j1,j2

Z且i1Ri2和j1Rj2。于是，對任意i1,i2,j1,j2都有：(i1Ri2)和(j1Rj2)

(i1

j1)R(i2

j2)因此，E對于

具有代換性質。第88頁，課件共98頁，創(chuàng)作于2023年2月可見，考察一個等價關系E對于有多個運算的代數結構是否為同余關系，這里有個次序先后問題，選擇得好，馬上就考察到了E對某個運算是不具有代換性質，那么便可立刻斷定E不是該結構