离散数学 第六章 代数

离散数学第六章代数第1页，共175页，2023年，2月20日，星期二2023/5/2第六章代数

6.1代数结构6.2子代数6.3同态6.4同余关系6.5商代数6.6半群和独异点6.7群6.8环和域第2页，共175页，2023年，2月20日，星期二yuliang@32023/5/26.1代数结构代数系统一个非空集合A，连同若干个定义在该集合上的运算f1,f2,…,fn，所组成的系统称为一个代数系统，简称代数，记为<A,f1,f2,…,fn>。第3页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构

代数系统的组成载体（一个非空集合A）定义在载体上的运算(f1,f2,…,fn)代数常元第4页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构【例题1】(a)正整数集合I+，以及定义在该集合上的普通加法运算“+”组成一个代数系统<I+,+>。(b)一个有限集合S，由S的幂集ρ(S)，及定义在ρ(S)上的交、并、补运算组成一个代数系统 。第5页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构代数运算设A1,A2,…,An,A是非空集合，f是从A1×A2×…×An到A的一个映射，则称f为从集合A1×A2×…×An到A的一个n元代数运算，简称运算，n称为代数运算的阶。xnx3fx2x1y…第6页，共175页，2023年，2月20日，星期二yuliang@72023/5/26.1代数结构 运算的封闭性设f是从A1×A2×…×An到A的一个n元运算，若A=A1=A2=…=An，则称该n元运算在集合A上是封闭的，亦称f是A上的n元运算。特别地，设f是从A到A的映射，则称f是一个在A上封闭的一元运算。设f是从A2到A的映射，则称f是一个在A上的封闭的二元运算。第7页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构【例题2】一台自动售货机能接受五角和一元的硬币。当人们投入任意两枚上述硬币时，自动售货机将供应出相应的饮料，如下表☆5角1元5角雪碧可乐1元可乐酷儿第8页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构设集合A＝{5角，1元}，集合B＝{雪碧，可乐，酷儿}，则上表其实是一个从A×A到B的一个映射，也即一个从A2到B的一个二元运算。问运算☆在A上是否封闭？第9页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构【例题3】

设有正整数集I+，“+”是I+上的普通加法运算。在I+上定义二元运算*为：任取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}问运算*在S和T上是否封闭?

第10页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构 运算表

当集合A是有限集时，例如A={a1,a2,…,an}，则A上一元代数运算和二元代数运算分别用如表(a)和(b)所示的运算表来表示。

a1a2…ana1a2…ana1a1a1a2…

a1ana2a1a2a2…

a2an………ana1ana2…

anan△△(ai)a1a2…an△(a1)△(a2)…△(an)(a)(b)运算符集合A运算结果第11页，共175页，2023年，2月20日，星期二yuliang@122023/5/26.1代数结构代数运算的性质一交换律设*是定义在集合A上的一个二元运算，如果任取x,y∈A，都有x*y=y*x，则称该二元运算是可交换的。【例题4】设Q是有理数集合，☆是Q上的二元运算，对任意a,b∈Q,a☆b=a+b-a●b,其中+和●是普通的加法、乘法运算，问☆是否是可交换的？第12页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构代数运算的性质二结合律设*是定义在集合A上的一个二元运算，如果对于任意x,y,z∈A，都有x*(y*z)=(x*y)*z,则称该二元运算是可结合的。【例题5】设A是一个非空集合，*是A上的一个二元运算，对于任意a,b∈A,有a*b=b,证明运算*是可结合的。第13页，共175页，2023年，2月20日，星期二yuliang@142023/5/26.1代数结构代数运算的性质三分配律设*和是定义在集合A上的二元运算，如果对任意的a,b,c∈A，都有*对左可分配*对右可分配则称*对是可分配的。

第14页，共175页，2023年，2月20日，星期二yuliang@152023/5/26.1代数结构代数运算的性质三【例题6】设集合A={α,β},在A上定义两个二元运算*和☆，如下表(a)和(b)所示。运算☆对运算*可分配吗？运算*对运算☆呢？*α

βαβα

ββ

α☆α

βα

βα

αα

β(a)(b)第15页，共175页，2023年，2月20日，星期二yuliang@162023/5/26.1代数结构代数运算的性质四吸收律设*和是定义在集合A上的两个可交换的二元运算，如果对于任意的x,y∈A,都有

则称运算*和满足吸收律。第16页，共175页，2023年，2月20日，星期二yuliang@172023/5/26.1代数结构代数运算的性质五等幂律设*是定义在集合A上的一个二元运算，如果对于任意x∈A,都有x*x=x,则称运算*满足等幂律。第17页，共175页，2023年，2月20日，星期二yuliang@182023/5/26.1代数结构【例题7】设ρ(S)是集合S上的幂集，在ρ(S)上定义两个二元运算：集合的并运算∪和集合的交运算∩，验证∪和∩满足吸收律和等幂律。解答：∪和∩运算是可交换的。A,B∈ρ(S),有

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

A∩A=AA∪A=A所以∪和∩满足等幂律。第18页，共175页，2023年，2月20日，星期二2023/5/26.1代数结构代数运算的性质六消去律设*是定义在集合上的一个二元运算，元素a∈A,如果对于任意x,y∈A,都有

a*x=a*yx=y

a是左可消去的

x*a=y*ax=ya是右可消去的则称a关于运算*是可消去的。若A中的所有元素都是可消去的，则称运算*满足消去律。第19页，共175页，2023年，2月20日，星期二yuliang@202023/5/26.1代数结构代数常元代数系统中，针对某一代数运算表现出具有某些特殊性质的元素称为代数常元，常见的有：幺元、零元、逆元、等幂元等。幺元

左幺元：设*是定义在集合A上的一个二元运算，若存在元素el，对于A中的每一个元素x，都有el*x=x则称el为A中关于运算*的左幺元。

第20页，共175页，2023年，2月20日，星期二yuliang@212023/5/26.1代数结构幺元

右幺元：设*是定义在集合A上的一个二元运算，若存在元素er，对于A中每一个元素x,都有

x*er=x则称er为A中关于运算*的右幺元。第21页，共175页，2023年，2月20日，星期二yuliang@222023/5/26.1代数结构幺元

幺元：设*是定义在集合A上一个二元运算，若A中有一个运算e,它既是左幺元，又是右幺元，则称e为A中关于运算*的幺元，亦称作单位元。

e*x=x*e=x第22页，共175页，2023年，2月20日，星期二yuliang@232023/5/26.1代数结构【例题8】设集合S={a,b,c,d},

S上定义的两个二元运算*和★的运算表如下表所示，试求出其中的左幺元和右幺元。*abcdabcddabcabcdabccabcd★abcdabcdabdcbacdcdabddbc(a)(b)第23页，共175页，2023年，2月20日，星期二yuliang@242023/5/26.1代数结构『定理』设*是定义在集合A上的一个二元运算，且在A中有关于运算*的左幺元el和右幺元er,则el=er=e,且A中的幺元是唯一的。

证明：设el和er分别是A中关于运算*的左幺元和右幺元，则有

el=el*er=er=e

假设另有幺元e’∈A,则有e’=e’*e=e,结论得证。第24页，共175页，2023年，2月20日，星期二yuliang@252023/5/26.1代数结构代数常元零元

左零元：设*是定义在集合A上的一个二元运算，如果有一个元素θl∈A,对于任意的元素x∈A都有θl*x=θl，则称θl为A中关于运算*的左零元。

右零元：如果有一个元素θr∈A,对于任意的元素x∈A都有x*θr=θr，则称θr为A中关于运算*的右零元。第25页，共175页，2023年，2月20日，星期二yuliang@262023/5/26.1代数结构零元

零元：如果A中的一个元素θ，它既是左零元，又是右零元，则称θ为A中关于运算*的零元。

θ*x=x*θ=θ第26页，共175页，2023年，2月20日，星期二yuliang@272023/5/26.1代数结构【例题9】设“浅”表示不易褪色的浅色衣服，“深”表示易褪色的深色衣服，集合S={浅，深}，定义S的一个二元运算“混洗”，记为“”，则的运算表如下表所示。求S中关于运算的幺元和零元。浅深浅深

浅深深深第27页，共175页，2023年，2月20日，星期二yuliang@282023/5/26.1代数结构『定理』设*是定义在集合A上一个二元运算，且在A中有关于运算*的左零元θl和右零元θr,那么θl=θr=θ，且A中的零元是唯一的。第28页，共175页，2023年，2月20日，星期二yuliang@292023/5/26.1代数结构逆元

逆元：设<A,*>是一个代数系统，*是定义在集合A上的一个二元运算，e是A中关于运算*的幺元。x,y∈A,如果x*y=e,那么关于运算*,x是y的左逆元，y是x的右逆元。如果x*y=y*x=e,那么关于运算*,x与y互为逆元。运算x的逆元记为x-1。第29页，共175页，2023年，2月20日，星期二yuliang@302023/5/26.1代数结构『定理』设<A,*>是一个代数系统，*是定义在集合A上的一个二元运算，e是A中关于运算*的幺元。若运算*是可结合的，且元素x有左逆元l和右逆元r，则l=r。证明：因为e是A中关于运算*的幺元且x有左逆元l和右逆元r,则有

l*x=x*r=e又运算是可结合的，所以

l=l*e=l*(x*r)=(l*x)*r=e*r=r第30页，共175页，2023年，2月20日，星期二yuliang@312023/5/26.1本节小结代数系统组成：载体、定义在载体上的运算、代数常元。设<A，*>为代数系统，*是定义在A上的二元运算，则运算*的某些性质以及代数常元可以直接从运算表中得到：运算*是封闭的，当且仅当运算表中的每个元素都属于A；运算*满足交换律，当且仅当运算表关于主对角线对称；第31页，共175页，2023年，2月20日，星期二yuliang@322023/5/26.1本节小结运算满足等幂律，当且仅当运算表中主对角线上的每一元素与它所对应的行(列)表头元素相同;运算满足消去律，当且仅当运算表中任意行、任意列没有相同的两个元素；若A中有关于运算*的零元，则该元素所在的行和列中的所有元素都等于该元素；若A中有关于运算*的幺元，则该元素所在的行(列)中的所有元素都依次与列(行)表头元素相同;第32页，共175页，2023年，2月20日，星期二yuliang@332023/5/26.1本节小结设A中有关于运算*的幺元e，元素a与b互逆，当且仅当运算表中a行、b列对应的元素与a列、b行对应的元素都是e。代数常元：幺元、零元。第33页，共175页，2023年，2月20日，星期二yuliang@342023/5/26.1习题习题一设<A,*>为代数系统，其中A={1,2,3,4},“*”定义如下表所示：(a)运算*是可交换的吗？为什么？(b)运算*是可结合的吗？为什么？(c)求A中关于运算*的幺元，并给出每个元素的逆元。(d)A中有关于运算*的零元吗？*123412341234234134124123第34页，共175页，2023年，2月20日，星期二yuliang@352023/5/26.1习题习题二设I是整数集合，函数g:I×I→I，定义为：g(x,y)=x*y=x＋y－x·y，其中+和·是普通的加法和乘法运算。(a)试证明二元运算*是可交换的和可结合的。(b)求运算*的幺元，并指出每个元素的逆元。第35页，共175页，2023年，2月20日，星期二yuliang@362023/5/26.2子代数子代数定义设<A,*,△,k>是一个代数系统，*和△分别是载体A上的二元运算和一元运算，k是代数常元，如果满足(1)A’A,(2)*和△运算在A’上封闭，(3)k∈A’,那么称<A’,*,△,k>是<A,*,△,k>的子代数。第36页，共175页，2023年，2月20日，星期二yuliang@372023/5/26.2子代数平凡子代数定义设<A,*,△>是一代数系统，T是由A中的代数常元构成的集合，且运算*和△在T上封闭。称<A,*,△>和<T,*,△>是<A,*,△>的平凡子代数，非平凡子代数亦称为真子代数。第37页，共175页，2023年，2月20日，星期二yuliang@382023/5/26.2习题习题一

I是整数集合，Ie和Io分别是偶数集合和奇数集合，+是I上的普通加法运算，则<I，+>是一代数系统。<Ie，+>和<Io，+>是<I，+>的子代数吗？解答：<Ie，+>是<I，+>的子代数。而<Io，+>不是<I，+>的子代数，因为Io在+上不封闭。第38页，共175页，2023年，2月20日，星期二yuliang@392023/5/26.2习题习题二

I是整数集合，I+是正整数集合，+是I上的普通加法运算，则<I,+,0>是一代数系统。<I+,+>是<I,+,0>的子代数吗？

解答：<I+，+>不是<I，+，0>的子代数，因为0I+。第39页，共175页，2023年，2月20日，星期二yuliang@402023/5/26.3同态同态的定义设A=<S,*,△,k>和A’=<S’,*’,△’,k’>是两个具有相同构成的代数系统，f是从S到S’的一个映射，且对任意a,b∈S满足：

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

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

f(k)=k’则称f为由A到A’的一个同态映射，简称同态。A同态于A’,记作A~A’。第40页，共175页，2023年，2月20日，星期二yuliang@412023/5/26.3同态同态象设f是从A=<S,*,△,k>到A’=<S’,*’,△’,k’>的一个同态映射，称<f(S),*’,△’,k’>为A在映射f下的同态象。其中下图反映了两个代数系统间的同态关系。第41页，共175页，2023年，2月20日，星期二yuliang@422023/5/26.3同态△kSS’fk’af(a)bf(b)cf(c)a*bf(a)*’f(b)△(c)△’f(c)**’同态象<f(S),*’,△’,k’>△’第42页，共175页，2023年，2月20日，星期二yuliang@432023/5/26.3同态【例题1】设代数系统<I,·>,

I是整数集,·是普通乘法运算。如果我们只对运算结果是正数、负数还是零关心,那么代数系统<I，·>中的运算结果的特征就可以用另一个代数系统<B，⊙>的运算结果来表示,其中B＝{+,-,0},⊙是B上的二元运算，运算表如下所示，构造从<I,·>到<B,⊙>的同态映射。第43页，共175页，2023年，2月20日，星期二yuliang@442023/5/26.3同态解答：构造函数f:I→B,

f(x)＝显然，任取a,b∈I,f(a·b)=f(a)⊙f(b)。所以，f是由<I,·>到<B,⊙>的一个同态。⊙+-0+-0+-0-+0000+x>0

-x<00x=0第44页，共175页，2023年，2月20日，星期二yuliang@452023/5/26.3同态同态的分类设f是由A={S,*,△,k}到A’={S’,*’,△’,k’}的一个同态。

满同态:若f是满射的，则称f为由A到A’的一个满同态。A’就是A在满同态f下一个同态象。单一同态：若f是单射的，则称f为由A到A’的一个单一同态。显然，A在单一同态f下的同态象<f(S)，*’,△’,k’>与A同构。第45页，共175页，2023年，2月20日，星期二yuliang@462023/5/26.3同态同态的分类同构：若f是双射的，则称f为由A到A’的一个同构映射，简称同构。A同构于A’，记作AA’。自同态：若A’=A，则称f为A上的自同态。自同构：若A’=A且f是双射的，则称f为A上的自同构。第46页，共175页，2023年，2月20日，星期二yuliang@472023/5/26.3同态【例题2】

N是自然数集合，+是N上的普通加法运算，设Nk={0,1,2,…,k-1},+k是定义在N上的模k加法运算。设函数f:N→Nk定义为

f(x)=x(modk)

证明：f是从<N,+,0>到<Nk,+k,0)的一个满同态映射。第47页，共175页，2023年，2月20日，星期二yuliang@482023/5/26.3同态证明：(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>的一个满同态。第48页，共175页，2023年，2月20日，星期二yuliang@492023/5/26.3同态【例题3】设A={a,b,c,d},在A上定义一个二元运算★如表a所示，又设B={0,1,2,3},在B上定义一个二元运算*如表b所示。构造从代数系统<A,★>到<B,*>的一个同构映射。★abcdabcdaaaaabcdacacadcb*012301232020012322220321(a)(b)第49页，共175页，2023年，2月20日，星期二yuliang@502023/5/26.3同态解答：

设函数h:A→B,h(a)=2,h(b)=1,h(c)=0,h(d)=3。容易验证：(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是从代数系统<A,★>到<B,*>的一个同构映射。

第50页，共175页，2023年，2月20日，星期二yuliang@512023/5/26.3同态的性质『定理』设f是从A=<S,*,△,k>到A’=<S’,*’,△’,k’>的一个同态映射，那么A的同态象<f(S),*’,△’,k’>是A’的子代数。证明：(i)因为f是从S到S’的一个映射,所以f(S)S’。(ii)因为k∈S,f(k)=k’,所以k’∈f(S).(iii)任取a,b∈f(S)，存在x,y∈S,使得f(x)=a,f(y)=b。因为x*y=z∈S,所以

a*’b=f(x)*’f(y)=f(x*y)=f(z)∈f(S)故f(S)在运算*’下是封闭的。第51页，共175页，2023年，2月20日，星期二yuliang@522023/5/26.3同态的性质(iv)任取a∈f(S),存在x∈S使得f(x)=a。因为△x∈S,所以△’a=△’f(x)=f(△x)∈f(S),故f(S)在运算△’下是封闭的。由(i)(ii)(iii)(iv)可知，<f(S)，*’,△’,k’>是A’的子代数。fA=<S,*,△,k>同态象<f(S),*’,△’,k’>A’=<S’,*’,△’,k>第52页，共175页，2023年，2月20日，星期二yuliang@532023/5/26.3同态的性质『定理』设f是从A=<S,*,°>到A’=<S’,*’,°’>的一个同态映射，A’’=<f(S),*’,°’>是A在同态映射f下的同态象，则有(1)若*在A中可交换,则*’在A’’中也是可交换的;(2)若*在A中可结合,则*’在A’’中也是可结合的;(3)若在A中*对°可分配,则在A’’中*’对°’也可分配;第53页，共175页，2023年，2月20日，星期二yuliang@542023/5/26.3同态的性质(4)若e是A中关于运算*的幺元，则f(e)是A’’中关于运算*’的幺元；(5)若θ是A中关于运算*的零元，则f(θ)是A’’中关于运算*’的零元；(6)任取x∈S,x对运算*有逆元x-1,在f(S)中，f(x)也有关于运算*’的逆元f(x-1)。第54页，共175页，2023年，2月20日，星期二yuliang@552023/5/26.3小结子代数概念：一个代数系统载体A的一个子集A’，如果在该代数系统的所有运算下都封闭，则称以A’为载体的代数系统是原代数系统的子代数。同态概念：同态映射不仅建立了两个代数系统载体间的映射关系，更重要的是同时还建立了两个代数系统对应运算间的映射关系。第55页，共175页，2023年，2月20日，星期二yuliang@562023/5/26.3小结同态象概念：一个代数系统与其同态象之间有许多相似的地方。同态的分类：根据同态映射的性质可以将同态分为：满同态、单一同态和同构。同态性质：在同态映射下，同态象的运算能够保持原代数系统中对应运算的交换性、结合性和分配性，并且幺元、零元和逆元也满足映射对应关系。第56页，共175页，2023年，2月20日，星期二yuliang@572023/5/26.3本节习题习题一设h是从A=<S,*,k>到A’=<S’,*’,k’>的同态，证明如果<T,*’,k’>是A’的子代数，那么<h-1(T),*,k>是A的子代数。h-1(T)Thh-1hA=<S,*,k>A’=<S’,*’,k’>第57页，共175页，2023年，2月20日，星期二yuliang@582023/5/26.3本节习题证明：(i)因为<T,*’,k’>是<S’,*’,k’>的子代数，所以TS’。故有h-1(T)h-1(S’)S。(ii)任取x,y∈h-1(T),存在x’,y’∈T使得h(x)=x’,h(y)=y’因为x,y∈S且h是从A到A’的同态，所以有

h(x*y)=h(x)*’h(y)=x’*’y’∈T故x*y∈h-1(T),即h-1(T)对*运算是封闭的。(iii)因为h(k)=k’∈T,所以k∈h-1(T)。由(i)(ii)(iii)可知，<h-1(T),*,k>是<S,*,k>的子代数。第58页，共175页，2023年，2月20日，星期二yuliang@592023/5/26.4同余关系同余的定义运算上的同余关系：设A=<S,*,△>是一个代数系统，~是载体S上的等价关系，任取a,b,c∈S。(1)当a~b时，若△a~△b,则等价关系~在一元运算△下是可保持的，称~是关于运算△同余关系。(2)当a~b和c~d时，若有a*c~b*d，则等价关系~在二元运算*下是可保持的，称~是关于运算*同余关系。第59页，共175页，2023年，2月20日，星期二yuliang@602023/5/26.4同余关系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同余关系【例题1】设+是整数集合I上的普通加法运算，~是I上的模k(k∈I+)相等关系，问~在运算+上是否是I上的同余关系？分析：任意a,b和c,d有：

a≡b(modk)其实就是a-b=n*k

c≡d(modk)其实就是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同余关系【例题2】设△是集合I上的一元运算，任取a∈I,

△a=a2,~是I上的模k(k∈I)相等关系，问~在运算△是否是I上的同余关系？~是否是代数系统A＝<I,+,△>上A的同余关系？分析：a≡b(modk)就相当于(a-b)=n*k

△a-△b=(a+b)(a-b)=(a+b)*n*k，即△a≡△b整数m第62页，共175页，2023年，2月20日，星期二yuliang@632023/5/26.4同余关系代数系统上的同余关系：设A=<S,*,△>是一个代数系统，~是载体S上的等价关系，若~在A上的所有运算下都是可保持的，则称~为代数系统A上的同余关系。第63页，共175页，2023年，2月20日，星期二yuliang@642023/5/26.4同余关系『定理』设g是从代数系统A=<S,*,△,k>到A’=<S’,*’,△’,k’>的一个同态映射，那么由g诱导的S上的等价关系~是代数系统A上同余关系。证明：由函数g诱导的S上的等价关系~为：任取a,b∈S,a~b当且仅当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同余关系又g是从A到A’的同态映射，所以有

△’g(a)=g(△a)=△’g(b)=g(△b)故△a~△b，这说明~在运算△下是可保持的。(ii)若a~b且c~d,且有g(a)=g(b),g(c)=g(d),所以g(a)*’g(c)=g(b)*’g(d),又因g是从A到A’的同态映射，所以有g(a)*’g(c)=g(a*c)=g(b)*’g(d)=g(b*d)故a*c~b*d,这说明等价关系~在运算*下是可保持的。由(i)(ii)可得，~是代数系统A上的同余关系。第65页，共175页，2023年，2月20日，星期二yuliang@662023/5/26.4同余关系运算上的同余关系：等价关系在运算下的可保持性是指参与运算的对应元素，如果在同一个等价类中，则运算后所得的结果也必在同一个等价类中。代数系统上的同余关系：等价关系R如果在一个代数系统中的所有运算下都是可保持的，则R是A上的同余关系。同余关系使得元素所在的等价类在运算上可以作为一个整体来看待。第66页，共175页，2023年，2月20日，星期二yuliang@672023/5/26.5商代数商代数定义:设A=<S,*,△,k>是一个代数系统，~是A上的同余关系，A关于~的商代数A/~=<S/~,*’,△’,[k]>。其中

△’[a]=[△a][a]*’[b]=[a*b]注意：S/~是集合的集合，即等价类的集合，形如：{[a],[b],…}*’,△’是集合之间的运算

[k]是代数常元的集合

第67页，共175页，2023年，2月20日，星期二yuliang@682023/5/26.5商代数【例题】代数系统A=<S,△,~>，其中S={a1,a2,a3,a4,a5},一元运算△和~由下表所示的运算表定义。又S上的等价关系R产生的S上的划分

л={{a1,a3},{a2,a5},{a4}}(a)证明：R是A上的同余关系。(b)给出A/R。a1a2a3a4a5△~a4a3a4a2a1a3a2a1a3a5第68页，共175页，2023年，2月20日，星期二yuliang@692023/5/26.5小结商代数：由等价关系R可以得到代数系统A的载体的一个划分，以这个划分为新的载体，按照原运算的规则建立等价类之间新的运算，这样得到的代数系统是原代数系统的商代数。第69页，共175页，2023年，2月20日，星期二yuliang@702023/5/26.6半群和独异点半群：一个代数系统<S,*>，其中S是非空集合，*是S上一个二元运算，如果满足：运算*是封闭的；运算*是可结合的，即任取x,y,z∈S,有

(x*y)*z=x*(y*z)则称<S,*>为半群。第70页，共175页，2023年，2月20日，星期二yuliang@712023/5/26.6半群与独异点【例题1】设集合Sk={x|x∈I,x≥k},其中I是整数集合，k∈I,且k≥1,+是普通加法运算。证明<Sk,+>是一个半群。

证明：因为+运算在Sk上封闭的和可结合的，所以<Sk,+>是半群。

考虑：如果k≥0呢？如果k≥-1呢？第71页，共175页，2023年，2月20日，星期二yuliang@722023/5/26.6半群与独异点【例题2】设I+是正整数集合，R是实数集合，R+和R-分别表示正实数和负实数集合。问<I+,->、<R+,·>、<R-,·>和<R,÷>都是半群吗？为什么？解答：<R+,·>满足半群的定义，它是半群。

<I+,->、<R-,·>、<R,÷>的运算不封闭，因此均不是半群。第72页，共175页，2023年，2月20日，星期二yuliang@732023/5/26.6半群与独异点『定理』设<S,*>是一个半群，TS且*在T上是封闭的，那么<T,*>是<S,*>的子代数，<T,*>也是一个半群，称为<S,*>的子半群。独异点：含有幺元的半群。

由于结合律在子代数上是可继承的，因此半群的子代数也是半群。第73页，共175页，2023年，2月20日，星期二yuliang@742023/5/26.6半群与独异点【例题3】判断以下代数系统是否是独异点。(a)<I+,+>;(b)<N,+>。解答：(a)<I+,+>是半群，但不是独异点，因为不含有幺元0。(b)<N,+>是半群，因为含有幺元0，所以它也是独异点。第74页，共175页，2023年，2月20日，星期二yuliang@752023/5/26.6半群与独异点【例题4】设A={0,1,2,3},+4和×4分别是模4加法和模4乘法，其运算表分别如下页(a)、(b)所示，即任意a,b∈A有

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

a×4b=(a×b)(mod4)(a)<A,+4>和<A,×4>是独异点吗?为什么?(b)A中的元素在运算+4和×4上有逆元吗?第75页，共175页，2023年，2月20日，星期二yuliang@762023/5/26.6半群与独异点+4012301230123123023013012×4012301230000012302020321(a)(b)第76页，共175页，2023年，2月20日，星期二yuliang@772023/5/26.6半群与独异点子独异点：设<S,*,e>是一个独异点，TS且*在T上是封闭的，那么<T,*,e>是<S,*,e>的子代数,<T,*,e>也是一个独异点，称为<S,*,e>的子独异点。原代数系统的子代数本身是独异点在相同运算下，幺元相同第77页，共175页，2023年，2月20日，星期二yuliang@782023/5/26.6半群与独异点【例题5】设N10={0,1,2,3,…,9},×10是模10乘法运算，则<N10,×10>是一个独异点，(a)写出×10的运算表；(b)取N10的一个子集A={0,2,4,6,8},证明<A,×10>是一个独异点，但不是<N10,×10>的子独异点；(c)构造<N10,×10>的一个含有5个元素的子独异点。第78页，共175页，2023年，2月20日，星期二yuliang@792023/5/26.6半群与独异点交换半群（独异点）：在半群（独异点）中，若二元运算是可交换的，则称该半群（独异点）为交换半群（独异点）。注：概念只作了解。第79页，共175页，2023年，2月20日，星期二yuliang@802023/5/26.6半群和独异点的性质『定理』设<S,*>是一个半群，如果S是一个有限集，则必存在a∈S,使得a*a=a。证明：设|S|=n,因为<S,*>是半群，任取b∈S,由运算*的封闭性以及S为有限集知

b,b*b=b2,b*b*b=b3,…,bn,bn+1∈S根据抽屉原理，必有两个元素相等,不妨设为bi=bj(其中j>i)。n+1第80页，共175页，2023年，2月20日，星期二yuliang@812023/5/26.6半群与独异点的性质令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半群与独异点【思考题】设<S,*>是一个独异点，*的运算表中可能出现两行或两列完全相同吗？解答：不可能。设S中关于运算*的幺元是e。任取a,b∈S,若a≠b,则有

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

a*e≠b*e(任何两行不同)所以运算*的运算表中任何两行和两列都是不同的。第82页，共175页，2023年，2月20日，星期二yuliang@832023/5/26.6半群与独异点循环独异点：设<S,*,e>是一个独异点，若存在一个元素g∈S,对于S中的每一个元素a,都有一个对应的k∈N使得a=gk，则称此独异点为循环独异点。g称为此循环独异点的生成元。第83页，共175页，2023年，2月20日，星期二yuliang@842023/5/26.6半群与独异点【例题6】判断以下代数系统是否是循环独异点，若是，指出生成元。(a)<N,+,0>;(b)<{a,b,c,d},*>,*的运算表如下表所示。*abcdabcdabcdbadccdbadcab第84页，共175页，2023年，2月20日，星期二yuliang@852023/5/26.6本节小结半群半群定义：封闭、可结合子半群：子集、封闭，子代数，子半群半群性质：有限半群中必有等幂元交换半群：可交换第85页，共175页，2023年，2月20日，星期二yuliang@862023/5/26.6本节小结独异点独异点定义：含幺元半群子独异点：子集、封闭、含有幺元e，子代数交换独异点：可交换循环独异点：有一个生成元g,每个元素都可以用gk表示第86页，共175页，2023年，2月20日，星期二yuliang@872023/5/26.7群群：设<G,*>是一个代数系统，其中G是非空集合，*是G上一个二元运算。如果满足运算*是封闭的，运算*是可结合的，存在幺元e，对于每一个元素x∈G,都存在逆元x-1∈G，则称<G,*>是一个群。半群独异点群半群独异点群第87页，共175页，2023年，2月20日，星期二yuliang@882023/5/26.7群【例题1】判断以下代数系统是否是群？(a)<I,+>,I是整数集合，+是普通加法运算。(b)<Q-{0},·>,Q是有理数集合，·是普通乘法运算。(c)<I,·>，I是整数集合，·是普通乘法运算。(d)<{a,b,c},*>,运算*如下表所示。*abcabcabcbcacab第88页，共175页，2023年，2月20日，星期二yuliang@892023/5/26.7群【例题2】设有代数系统<I,°>，其中I是整数集合，运算°的定义为，对任意a,b∈I,有

a°b=a+b-2试问<I,°>是否是群？解答：(i)对任意a,b∈I,a°b∈I,所以运算°在I上是封闭的。第89页，共175页，2023年，2月20日，星期二yuliang@902023/5/26.7群(ii)对任意的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所以°运算满足结合律。(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中每个元素都有逆元。由以上可知<I,°>是一个群。第90页，共175页，2023年，2月20日，星期二yuliang@912023/5/26.7群有限群：设<G,*>是一个群，如果G是有限集，则称<G,*>为有限群。无限群：设<G,*>是一个群，如果G是无限集，则称<G,*>为无限群。群的阶数：有限群<G,*>的载体G的基数|G|，称为群的阶。第91页，共175页，2023年，2月20日，星期二yuliang@922023/5/26.7群的性质性质一：群中无零元。说明：当群中只有一个元素的时候，一般的把它看作幺元，如果它是零元的话，它就不符合群的定义了。因为零元没有逆元，零元与任何元素进行操作结果都是零元。如果群中有零元，则不符合群的定义了(任何一个元素都有逆元)。第92页，共175页，2023年，2月20日，星期二yuliang@932023/5/26.7群的性质性质二：群中每个元素的逆元都是唯一的。说明：前面我们学过一个定理6.1-3，对于可结合运算，如果一个元素x有左逆元l和右逆元r,那么l=r（即逆元是唯一的）