离散数学第十二章 代数结构基本概念及性质

离散数学第十二章代数结构基本概念及性质第1页，课件共98页，创作于2023年2月12.1代数结构的定义与例在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运算这个概念是代数结构中不可缺少的基本概念。定义12.1.1

设S是个非空集合且函数 或f:Sn

→S，则称f为一个n元运算。其中n是自然数，称为运算的元数或阶。当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等。第2页，课件共98页，创作于2023年2月注意，n元运算首先是一个函数，其次是个闭运算(所谓闭运算是指：集合上的运算，其运算结果都在原来的集合中，我们把具有这种特征的运算称作封闭的，简称闭运算)。封闭性表明了n元运算与一般函数的区别之处。此外，有些运算存在幺元或零元，它在运算中起着特殊的作用，称它为S中的特异元或常数。第3页，课件共98页，创作于2023年2月运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。第4页，课件共98页，创作于2023年2月在下面讨论的代数结构中，主要限于一元和二元运算，将用'、┐或ˉ等符号表示一元运算符；用

、

、⊙、○、∧、∨、∩、∪等表示二元运算符，一元运算符常常习惯于前置、顶置或肩置，如┐x、、x'；而二元运算符习惯于前置、中置或后置，如：+xy，x+y，xy+。有了集合上运算的概念后，便可定义代数结构了。第5页，课件共98页，创作于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页，创作于2023年2月例：我们可以构造下述的一个代数结构：设有一个由有限个字母组成的集合∑

，叫字母表，在∑上任意长的字母串，叫做∑上句子或字符串，串中字母的个数m叫这个串的长度，我们假定当一个字的长度m=0时用符号

表示，它叫做空串。这样我们可以构造一个在∑上的所有串的集合∑*。其次，我们定义一个在∑*上的运算“//”——并置运算或者连接运算，设

，

∑*，则

//

＝

。通过并置运算将两个串联成一个新的串，而此联成的新串也在∑*内，这样构造的<∑*，//>是一个代数结构第7页，课件共98页，创作于2023年2月如果令∑+＝∑*－{

}，则<∑+，//>也是一个代数结构。这两种代数结构都是计算机科学中经常要用到的代数结构。第8页，课件共98页，创作于2023年2月例：设有一计算机它的字长是32位，它以定点加、减、乘、除及逻辑加、逻辑乘为运算指令，并分别用01，02，…，06表示之。则在该计算机中由232有限个不同的数字所组成的集合S以及计算机的运算型机器指令就构成了一个代数结构<S，01，02，…，06>。第9页，课件共98页，创作于2023年2月因此，一个代数结构需要满足二个条件：

(1)有一个非空集合S

(2)在集合S上定义的运算一定是封闭的第10页，课件共98页，创作于2023年2月此外，我们把集合S的基数即|S|，定义为代数结构的基数。如果S是有限集合，则说代数结构是有限代数结构；否则便说是无穷代数结构.有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义：第11页，课件共98页，创作于2023年2月定义12.1.3

设两个代数结构<S，f1，f2，…，fm>和<T，g1，g2，…，gm>，如果fi和gi(1≤i≤m)具有相同的元数，则称这两个代数结构是同类型的。可见，判定两个代数结构是否同类型，主要是对其运算进行考察：①两个代数结构是否有相同个数的运算符；②每个相对应的运算符是否有相同的元数。第12页，课件共98页，创作于2023年2月例：代数结构<N，＋>与代数结构<Z，×>是相同类型的，因为它们都有一个二元运算符。例：代数结构<Z，＋，×>与<N，＋>的类型是不相同的，因为它们的运算符的个数不同。第13页，课件共98页，创作于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页，创作于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页，创作于2023年2月12.2代数结构的基本性质所谓代数结构的性质即是结构中任何运算所具有的性质。以下我们均假设运算为二元运算。1.结合律给定<S，⊙>，则运算“⊙”满足结合律或“⊙”是可结合的，即(

x)(

y)(

z)(x,y,z∈S→(x⊙y)⊙z=x⊙(y⊙z))第16页，课件共98页，创作于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页，创作于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页，创作于2023年2月同样，并不是所有代数结构上运算均满足交换律，如矩阵的乘法就不满足交换律。易见，如果一代数结构中的运算⊙是可结合和可交换的，那么，在计算a1⊙a2⊙···⊙am时可按任意次序计算其值。特别当a1＝a2＝···＝am＝a时，则a1⊙a2⊙···⊙am＝am。称am为a的m次幂，m称a的指数。下面给出am的归纳定义：第19页，课件共98页，创作于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页，创作于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页，创作于2023年2月类似地可定义○对于⊙是满足左或右分配律.若⊙对于○既满足左分配律又满足右分配律，则称⊙对于○满足分配律或是可分配的。同样可定义○对于⊙满足分配律。由定义不难证明下面定理：定理12.2.1

给定<S，⊙，○>且⊙是可交换的。如果⊙对于○满足左或右分配律，则⊙对于○满足分配律。第22页，课件共98页，创作于2023年2月例12.2.3

给定<B,⊙,○>，其中B={0,1}。表12.2.1分别定义了运算⊙和○，问运算⊙对于○是可分配的吗？○对于⊙呢？第23页，课件共98页，创作于2023年2月形如表12.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成。当集合S的基数很小，特别限于几个时，代数结构中运算常常用这种表给出。其优点简明直观，一目了然。解可以验证⊙对于○是可分配的，但○对于⊙并非如此。因为1○(0⊙1)

(1○0)⊙(1○1)

10100第24页，课件共98页，创作于2023年2月4.吸收律给定<S，⊙，○>，则⊙对于○满足左吸收律

:=(

x)(

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

:=(

x)(

y)(x,y∈S→(x○y)⊙x=x)第25页，课件共98页，创作于2023年2月若⊙对于○既满足左吸收律又满足右吸收律，则称⊙对于○满足吸收律或可吸收的。○对于和吸收律类似地定义。若⊙对于○是可吸收的且○对于⊙也是可吸收的，则⊙和○是互为吸收的或⊙和○同时满足吸收律。第26页，课件共98页，创作于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页，创作于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页，创作于2023年2月例12.2.5

给定<P(S)，∪，∩>，其中P(S)是集合S的幂集，∪和∩分别为集合的并和交运算。验证：∪和∩是等幂的。证：对任意A

P(S)，有A∪A=A和A∩A=A，故∪和∩是等幂的。第29页，课件共98页，创作于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页，创作于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页，创作于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页，创作于2023年2月定理12.2.4

给定<S，⊙>且θl和θr分别为关于⊙的左零元和右零元，则θl=θr=θ且零元θ是唯一的。定理12.2.5

给定<S，⊙>且|S|＞1。如果θ，e∈S，其中θ和e分别为关于⊙的零元和幺元，则θ≠e。第33页，课件共98页，创作于2023年2月例：代数结构<Z，×>上的零元是“0”，因为对于任何整数x，均有x×0＝0×x＝0。例：正整数集Z+上的运算“min”，叫“取最小”运算。min(a,b)为取a,b的最小者。代数结构<Z+，min>中对应于运算“min”的零元为1。第34页，课件共98页，创作于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页，创作于2023年2月给定<S，⊙>及幺元e；x，y∈S，则y为x的左逆元:=y⊙x=ey为x的右逆元:=x⊙y=ey为x的逆元:=y⊙x=x⊙y=e第36页，课件共98页，创作于2023年2月显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的逆元表示为x-1。一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是唯一的。第37页，课件共98页，创作于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页，创作于2023年2月例：代数结构<Z，＋>上的幺元是“0”，对于任何整数x，它的逆元是－x，因为x＋(－x)＝0。例：代数结构<R，＋，×>中0和1分别为＋和×的幺元。对于“＋”，对每个元素r

R都有逆元－r；对于“×”，对每个元素

r

R都有逆元1/r(r0)

。第39页，课件共98页，创作于2023年2月9.可约律与可约元给定<S，⊙>且零元θ∈S，则⊙满足左可约律或是左可约的

:=(

x)(

y)(

z)((x,y,z∈S∧x≠θ∧x⊙y=x⊙z)→y=z)，并称x是关于⊙的左可约元。⊙满足右可约律或是右可约的

:=(

x)(

y)(

z)((x,y,z∈S∧x≠θ∧y⊙x=z⊙x)→y=z)，并称x是关于⊙的右可约元。第40页，课件共98页，创作于2023年2月若⊙既满足左可约律又满足右可约律或⊙既是左可约又是右可约的，则称⊙满足可约律或⊙是可约的。若x既是关于⊙的左可约元又是关于⊙的右可约元，则称x是关于⊙的可约元。可约律与可约元也可形式地定义如下：第41页，课件共98页，创作于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页，创作于2023年2月例：给定<Z，×>，其Z是整数集合，×是一般乘法运算。显然，每个非零整数都是可约元，而且运算×满足可约律。第43页，课件共98页，创作于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页，创作于2023年2月故得x○y=x○z

y=z，故x是关于○的左可约元。同样可证得y○x=z○x

y=z，故x是关于○的右可约元。故x是关于○的可约元。最后，作一补充说明，用运算表定义一代数结构的运算，从表上很能反映出关于运算的各种性质。为确定起见，假定<S，○>及x，y，θ，e∈S。第45页，课件共98页，创作于2023年2月(1)运算○具有封闭性，当且仅当表中的每个元素都属于S。(2)运算○满足交换律，当且仅当表关于主对角线是对称的。第46页，课件共98页，创作于2023年2月(3)运算○是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元素相同。○abc…aabbcc……第47页，课件共98页，创作于2023年2月(4)元素x是关于○的左零元，当且仅当x所对应的行中的每个元素都与x相同；元素y是关于○的右零元，当且仅当y所对应的列中的每个元素都与y相同；元素

是关于○的零元，当且仅当

所对应的行和列中的每个元素都与

相同。○lmn…axxxx…c…左零元x○mny…aybycy……右零元y○mn

…a

…c

……零元

第48页，课件共98页，创作于2023年2月(5)元素x为关于○的左幺元，当且仅当x所对应的行中元素依次与行表头元素相同；元素y为关于○的右幺元，当且仅当y所对应的列中元素依次与列表头元素相同；元素e是关于○的幺元，当且仅当e所对应的行和列中元素分别依次与行表头元素和列表头元素相同。○lmn…axlmn…c…左幺元x○mny…aabbcc……右幺元y○mne…aaemne…cc……幺元e第49页，课件共98页，创作于2023年2月(6)x为关于○的左逆元，当且仅当位于x所在行的元素中至少存在一个幺元，y为关于○的右逆元，当且仅当位于y所在列的元素中至少存在一个幺元；x与y互为逆元，当且仅当位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是幺元。○lmn…axec…左逆元○mny…aebc…右逆元○mxy…xebye…逆元第50页，课件共98页，创作于2023年2月例12.2.8

给定<S，○>，其中S={α，β，γ，δ，ζ}且○的定义如表12.2.5所示。试指出该代数结构中各元素的左、右逆元情况。表12.2.5解：α是幺元；β的左逆元和右逆元都是γ，即β与γ互为逆元；δ的左逆元是γ而右逆元是β；β有两个左逆元γ和δ；ζ的右逆元是γ，但ζ没有左逆元。○αβγδζαβγδζαβγδζβδαγδγαβαβδαγδγζδαγζ○

eβγδζeβγδζ

eβγδζβδeγδγeβeβδeγδγζδeγζ第51页，课件共98页，创作于2023年2月12.3同态与同构本节将阐明两个重要概念——同态与同构。在以后各节中，它们会经常被使用到。第52页，课件共98页，创作于2023年2月定义12.3.1

设<X，⊙>与<Y，○>是同类型的。称<X，⊙>同态于<Y，○>或<Y，○>为<X，⊙>的同态象，记为<X，⊙>~<Y，○>，其定义如下：

<X，⊙>~

<Y，○>

:=(

f)(f∈YX∧(

x1)(

x2)(x1,x2∈X→f(x1⊙x2)=f(x1)○f(x2)))同时，称f为从<X，⊙>到<Y，○>的同态映射.可以看出，同态映射f不必是惟一的。第53页，课件共98页，创作于2023年2月

Xx1x2x3x1⊙x3f(X)y1=f(x1)f(x1)=f(x2)y3=f(x3)y1○y3Y同态示意图f第54页，课件共98页，创作于2023年2月例12.3.1

给定<R，＋>和<R，×>，其中R是实数集合，＋和×分别是加法和乘法运算，试证<R，＋>~<R，×>。证：关键是找一个同态映射。今构造函数f∈RR如下：f(x)=ax,其中a＞0,x∈R则f为所求的同态映射，这是因为对任意y,z∈R，有f(y＋z)=ay＋z＝ay×az＝f(y)×f(z)因此，<R，＋>~<R，×>第55页，课件共98页，创作于2023年2月两个同类型的代数结构间的同态定义不仅适用于具有一个二元运算的代数结构，也可以推广到具有多个二元运算的任何两个同类型代数结构。例如，对于具有两个二元运算的两个同类型代数结构<X,⊙,○>和<Y,

,

>的同态定义如下：<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页，创作于2023年2月定理12.3.1

如果<X，⊙>~

<Y，○>且f为其同态映射，则<rn(f)，○>

<Y，○>。由于函数f

YX的不同性质，将给出不同种类的同态定义。第57页，课件共98页，创作于2023年2月定义12.3.2

设<X，⊙>~

<Y，○>且f为其同态映射。(i)如果f为满射，则称f是从<X，⊙>到<Y，○>的满同态映射。(ii)如果f为单射(或一对一映射)，则称f为从<X，⊙>到<Y，○>的单一同态映射。第58页，课件共98页，创作于2023年2月(iii)如果f为双射(或一一对应)，则称f为从<X，⊙>到<Y，○>的同构映射。记为<X,⊙>≌<X,○>。显然，若f是从<X，⊙>到<Y，○>的同构映射，则f为从<X，⊙>到<Y，○>的满同态映射及单一同态映射，反之亦然。第59页，课件共98页，创作于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，+>的满同态映射。第60页，课件共98页，创作于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,+>的同态映射。又易知f为单射，故f为<Z,+>到<Z,+>的单一同态映射。当k=-1或k=1时，f为从<Z,+>到<Z,+>的同构映射(我们稍后再来证明)。第61页，课件共98页，创作于2023年2月综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说，它能够保持运算的更多性质，为此，给出如下定理：定理12.3.2

给定<X,⊙,○>~

<Y,

,

>且f为其满同态映射，则(a)如果⊙和○满足结合律，则

和

也满足结合律。(b)如果⊙和○满足交换律，则

和

也满足交换律。第62页，课件共98页，创作于2023年2月(c)如果⊙对于○或○对于⊙满足分配律，则

对于

或

对于

也相应满足分配律。(d)如果⊙对于○或○对于⊙满足吸收律，则

对于

或

对于

也满足吸收律。(e)如果⊙和○满足等幂律，则

和

也满足等幂律。(f)如果e1和e2分别是关于⊙和○的幺元，则f(e1)和f(e2)分别为关于

和

的幺元。第63页，课件共98页，创作于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页，创作于2023年2月定理12.3.2告诉我们，对于满同态映射来说，代数结构的许多性质都能保持，如结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向的，即如果<X，⊙>满同态于<Y，○>，则<X，⊙>所具有的性质，<Y，○>均具有。但反之不然，即<Y，○>所具有的某些性质，<X，⊙>不一定具有。不尽要问，在怎样条件下，<Y，○>所具有的性质<X，⊙>都完全具有呢?为了回答这个问题，需要引出两个代数结构同构的概念。第65页，课件共98页，创作于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，○>的同态映射)第66页，课件共98页，创作于2023年2月<X,⊙>x1x2x1⊙x2<Y，○>f(x1)f(x2)f(x1)○f(x2)同构示意图f第67页，课件共98页，创作于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页，创作于2023年2月续例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页，创作于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)。故它们是同构的。∨01001111＋MHMMHHHH第70页，课件共98页，创作于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页，创作于2023年2月由定义可知，同构的条件比同态强，关键是同构映射是双射，即一一对应。而同态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它们的所有发生“彼此相通”。第72页，课件共98页，创作于2023年2月这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外一个性质已知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的两个代数结构来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是相同的。因此，可以根据这些特征来识别同构的代数结构。第73页，课件共98页，创作于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页，创作于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页，创作于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页，创作于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页，创作于2023年2月同构是一个关系，而且可以证明它是个等价关系，对此有如下定理：定理12.3.3

代数结构间的同构关系是等价关系。第78页，课件共98页，创作于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，

>的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构关系是等价关系。第79页，课件共98页，创作于2023年2月由于同构关系是等价关系，故令所有的代数结构构成一个集合S，于是可按同构关系将其分类，得到商集S/≌

。因为同构的代数结构具有相同的性质，故实际上代数结构所需要研究的总体并不是S而是S/≌

。在同态与同构中有一个特例，即具有相同集合的任两个代数结构的同态与同构，这便是自同态与自同构。第80页，课件共98页，创作于2023年2月定义12.3.4

给定<S，⊙>及f∈SS。f为自同态映射:=f为从<S，⊙>到<S，⊙>的同态映射。f为自同构映射:=f为从<S，⊙>到<S，⊙>的同构映射。例12.3.7

在例12.3.4中，当k≠0时，f=kx是从<Z，+>到<Z，+>的自同态映射；当k=1或k=-1时，f=kx是从<Z，+>到<Z，+>的自同构映射。第81页，课件共98页，创作于2023年2月12.4同余关系本节主要阐明同态与同余关系之间的联系。主要内容如下：定义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页，创作于2023年2月与此同时，称同余关系E的等价类为同余类。由定义可知，同余关系是代数结构的集合中的一类特殊的等价关系，并且在运算的作用下，能够保持关系的等价类。即在x1⊙y1中，如果用集合S中的与x1等价的任何其它元素x2代换x1，并且用与y1等价的任何其它元素y2代换y1，则所求的结果x2⊙y2与x1⊙y1位于同一等价类之中。第83页，课件共98页，创作于2023年2月亦即若[x1]E=[x2]E并且[y1]E=[y2]E，则[x1⊙y1]E=[x2⊙y2]E。此外，同余关系与运算密切相关。如果一个代数结构中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质。如果有，则说该代数结构存在同余关系；否则，同余关系不存在。第84页，课件共98页，创作于2023年2月[x1]Ex1x2[x1⊙y1]Ex1⊙y1x2⊙y2[y1]Ey1y2同余关系示意图第85页，课件共98页，创作于2023年2月例12.4.1

给定<Z,+,

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

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

Z试问，R为该结构的同余关系吗？第86页，课件共98页，创作于2023年2月解显然，R为Z中的等价关系。接着先考察R对于+运算的代换性质：若取i1,-i1,i2

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

(i1+i2)R(-i1+i2)不真。这是因为前件为真，后件为假。故R对于+运算不具有代换性质。第87页，课件共98页，创作于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页，创作于2023年2月可见，考察一个等价关系E对于有多个运算的代数结构是否为同余关系，这里有个次序先后问题，选择得好，马上就考察到了E对某个运算是不具有代换性质，那么便可立刻断定E不是该结构