离散第讲代数结构

离散第讲代数结构第1页，共31页，2023年，2月20日，星期二2逆元举例eg10.<Z,+>每一个元都有逆元(0为单位元)<Z+,>只有1有逆元(1为单位元)<Zn,+n>，Zn={0,1,...,n-1}，+n模n加法(0为单位元)<Zn,*n>，Zn={0,1,...,n-1}，*n模n乘法(1为单位元)第2页，共31页，2023年，2月20日，星期二3常用运算特异元素第3页，共31页，2023年，2月20日，星期二4逆元的特殊作用b∘a=c∘a∘

a-1∘

a-1b∘

e=c∘eb=c第4页，共31页，2023年，2月20日，星期二5消去律定义9.11设A为集合，∘为A上二元运算，若∀a,b,c∈A,（1）a∘b=a∘c∧a≠θ⇒b=c(左消去律)（2）b∘a=c∘a∧a≠θ⇒b=c(右消去律)则称∘运算满足消去律。第5页，共31页，2023年，2月20日，星期二6消去律实例Z,Q,R，+，×满足消去律Mn(R),矩阵+满足消去律，矩阵×不满足消去律P(B),⊕满足消去律，∪、∩、−不满足消去律设Zn={0,1,…,n-1}，其中n是正整数，

V=<Z5,>表示模5乘法的代数系统，V中的运算满足消去律。V=<Z4,>？第6页，共31页，2023年，2月20日，星期二7代数系统在集合上定义若干个运算而组成的系统，常称为代数系统。

定义9.12：一个非空集合A连同若干个定义在该集合上的运算o1,o2,...,ok所组成的系统就称为一个代数系统，记作<A,o1,o2,...,ok>第7页，共31页，2023年，2月20日，星期二88同类型的代数系统定义9.13：如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分，也称它们是同类型的代数系统.

例

V1=<R,+,•,-,0,1>V2=<P(B),∪,∩,～,,B>第8页，共31页，2023年，2月20日，星期二99实例同类型的代数系统仅仅是构成成分相同，不一定具有相同的性质.

V1

V2+和•可交换,可结合∪和∩可交换,可结合•对+可分配∪和∩互相可分配+和•不遵从幂等律∪和∩都有幂等律+和•没有吸收律∪和∩有吸收律+和•都有消去律∪和∩一般没有消去律V1=<R,+,•,-,0,1>V2=<P(B),∪,∩,～,,B>第9页，共31页，2023年，2月20日，星期二10子代数定义9.14设V=<A,o1,o2,…,or>是代数系统，B是A的非空子集.若B对于V中的所有运算封闭（含代数常数在内），则称V’=<B,o1,o2,…,or

>为V的子代数，若B⊂A,子代数V’称为V的真子代数.平凡子代数：V是V的平凡子代数.第10页，共31页，2023年，2月20日，星期二1111子代数实例<N,+

>是<Z,+

>的子代数，<N,+,0

>是<Z,+,0>的子代数<Z+,+,0

>不是<Z,+,0>的子代数注意代数常数一定要在子代数中出现！第11页，共31页，2023年，2月20日，星期二1212积代数的定义定义9.15：设V1=<A,∘>和V2=<B,*>是同类型的代数系统,∘和*为二元运算，在集合A×B上定义二元运算•,∀<a1，b1>,<a2，b2>∈A×B,有<a1，b1>•<a2，b2>=<a1∘a2,b1*

b2>.

称V=<A×B,•>为V1与V2的积代数，记作

V1×

V2.这时也称V1和V2的因子代数.第12页，共31页，2023年，2月20日，星期二1313积代数举例例9.9：设V1和V2分别为模3和模2加的代数系统，给出V1×

V2的运算表，并说明它的运算是否具有交换律与结合律，是否具有单位元。V1×

V2={<0,0>,<0,1>,<1,0>,<1,1>,<2,0>,<2,1>}第13页，共31页，2023年，2月20日，星期二14运算表<0,0><0,1><1,0><1,1><2,0><2,1><0,0><0,0><0,1><1,0><1,1><2,0><2,1><0,1><0,1><0,0><1,1><1,0><2,1><2,0><1,0><1,0><1,1><1,1><2,0><2,0><2,1><2,1>第14页，共31页，2023年，2月20日，星期二1515积代数与因子代数性质定理9.5：设V1=<A,∘>和V2=<B,*>是同类型的代数系统,V1×

V2=<A×B,•>是它们的积代数.(1)如果∘和*运算是可交换（可结合、幂等）的，那么•运算也是可交换（可结合、幂等）的；

(2)如果e1和

e2（θ1和θ2

）分别为∘和*运算的单位元(零元)，那么<e1,e2>（<θ1,θ2>)也是•运算的单位元(零元)；

(3)如果x和

y分别为∘和*运算的可逆元素，那么<x,y>也是

•运算的可逆元素，其逆元就是<x-1,y-1>。第15页，共31页，2023年，2月20日，星期二1616积代数性质推广积代数的定义可以推广到具有多个运算的同类型代数系统。在具有两个不同运算的情况下，积代数也保留因子代数中的分配律和吸收律等性质，但是消去律是个例外。第16页，共31页，2023年，2月20日，星期二1717举例例9.10：设Zn={0,1,…,n-1},其中n是正整数，V1=<Z5,>,V2=<Z3,>分别表示模5和模3乘法的代数系统.那么V1和

V2中的运算满足消去律。考虑积代数<Z5×

Z3,>,这里的运算不满足消去律.因为在V1×

V2

中有<2,0><0,2>=<0,0>=<2,0><0,0>,<2,0>不是零元，在上式中用消去律将它消去，就得到<0,2>=<0,0>,显然这是错误的。第17页，共31页，2023年，2月20日，星期二18同态与同构

讨论两个代数系统之间的关系性质同类型的两个代数系统可能有着共同的运算V=<Z2Z2,>,*eabceeabcaaecbbbceaccbae第18页，共31页，2023年，2月20日，星期二19同态定义9.16：设<A,*>，<B,·>是两个代数系统，f是从A到B的一个映射，s.t.对a1,a2∈A，有f(a1*a2)=f(a1)·f(a2)，则称f为由A到B的一个同态映射，称A同态于B，记作AB，称f(A)为A的一个同态像，其中f(A)={x|x=f(a),a∈A}B。第19页，共31页，2023年，2月20日，星期二20说明同态映射必须对所有的运算保持等式，包括0元运算在内，例如则f不是V的自同态，因为不保持0元运算第20页，共31页，2023年，2月20日，星期二21同态和映射的比较回忆映射的性质：①A中的每一个元都有象

②象唯一③可多对一同态：①映射②保持运算第21页，共31页，2023年，2月20日，星期二22同态举例eg1:<Z,>若只对运算结果的正负感兴趣，则此代数系统运算结果的特征可由另一代数系统<B,⊙>来描述，其中B＝{正，负，零}，⊙符合平常的正负运算规律。定义f:ZB

n(n>0)正

0零

n(n<0)负显然，a,b∈Z,有f(ab)=f(a)⊙f(b)此时，f为从<Z,>到<B,⊙>的一个同态。第22页，共31页，2023年，2月20日，星期二23同构定义:设f是从A到B的一个同态，如果f是从A到B的一个满射，则f称为满同态(注意此时f(A)=B)；如果f是从A到B的一个单射，则称f为单一同态；如果f是双射，则f称为同构映射，并称A与B是同构的，记作A≌B第23页，共31页，2023年，2月20日，星期二24同构举例eg2:f:RR+

x5x

则f是从<R,+>,<R+,>的一个单一同态eg3:f:NNk

xxmodk

则f是从<N,+>到<Nk,+k>的一个满同态eg4:f:ZnZ

mnm

则f是从<Z,+>到<nZ,+>的一个同构

第24页，共31页，2023年，2月20日，星期二25同构的意义同构是个很重要的概念，形式上不同的代数结构，若同构，则可抽象地把它们看作是本质上相同的，只是记代的符号不同而已。

*同构的逆仍为同构

第25页，共31页，2023年，2月20日，星期二26自同构定义:从A到A的同态f称为A的自同态，若f为同构，则称为自同构。定理:设G是代数系统的集合，则G中代数系统之间的同构关系是等价关系第26页，共31页，2023年，2月20日，星期二27同态的性质同态的合成仍旧是同态同态像是映到的代数系统的子代数满同态映射（在同态像中）保持原代数系统的下述性质：交换、结合、幂等、分配、吸收单位元、零元、逆元消去律不一定保持第27页，共31页，2023年，2月20日，星期二28实例1(1)V=<Z,+>,fc:Z→Z,fc(x)=cx,c为给定整数c=0,零同态;c=±1，自同构;其它c,单自同态第28页，共31页，2023年，2月20日，星期二29实例2(2)V=<Z6,⊕>,fk:Z6→Z6,fk(x)=(kx)mod6,k=0,1,2,3,4,5k=0,f0

零同态;k=1,f1

恒等映射，自同构k=2,f2={<0,0>,<1,2>,<2,4>,<3,0>,<4,2>,<5,4>},k=3,f3={<0,0>,<1,3>,<2,0>,<3,3>,<4,0>,<5,3>}k=4,f4={<0,0>,<1,4>,<2,2>,<3,0>,<4,4>,<5,2>}k=5,f5={<0,0>,<1,5>,<2,4>,<3,3>,<4,2>,<5,1>}自同构第29页，共31页，2023年，2月20日，星期二30实例3(3)可以推广到fk:Zn→Zn