离散完整ppt课件5.23.ppt

《离散完整ppt课件5.23.ppt》由会员分享，可在线阅读，更多相关《离散完整ppt课件5.23.ppt（22页珍藏版）》请在优知文库上搜索。

1、1n代数系统定义代数系统定义n同类型与同种的代数系统同类型与同种的代数系统n子代数子代数n积代数积代数5.2 代数系统及其子代数、积代数代数系统及其子代数、积代数2代数系统定义与实例代数系统定义与实例定义定义 非空集合非空集合 S 和和 S 上上 k 个一元或二元运算个一元或二元运算 f1,f2,fk 组成的系统称为一个组成的系统称为一个代数系统代数系统,简称简称代代数数，记做，记做 V=.S 称为代数系统的称为代数系统的载体载体，S 和运算叫做代数系和运算叫做代数系统的成分统的成分.有的代数系统定义指定了有的代数系统定义指定了S中的特殊中的特殊元素，称为代数常数元素，称为代数常数,例如二元运

2、算的单位元例如二元运算的单位元.有时也将代数常数作为系统的成分有时也将代数常数作为系统的成分.3实例实例,是代数系统，是代数系统，+和和 分别表示普通加法和乘法分别表示普通加法和乘法.是代数系统，是代数系统，+和和 分别表示分别表示n 阶阶(n2)实矩阵的加法和乘法实矩阵的加法和乘法.是代数系统，是代数系统，Zn0,1,n-1，和和 分别表示模分别表示模 n 的加法和乘法，的加法和乘法，x,yZn，x y=(xy)mod n，x y=(xy)mod n 也是代数系统，也是代数系统，和和为并和交，为并和交，为绝对补为绝对补4同类型与同种代数系统同类型与同种代数系统定义定义(1)如果两个代数系统中

3、运算的个数相同，如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是则称它们是 同类型的同类型的 代数系统代数系统.(2)如果两个同类型的代数系统规定的运算性质如果两个同类型的代数系统规定的运算性质也相同，则称为也相同，则称为 同种的同种的 代数系统代数系统.例例1 V1=,V2=,为为 n 阶全阶全 0 矩阵，矩阵，E 为为 n 阶单位矩阵阶单位矩阵 V3=5V1V2V3+可交换可交换,可结合可结合 可交换可交换,可结合可结合+满足消去律满足消去律 满足消去律满足消去律 对对+可分配可分配+对对 不可分配不可分配

4、+与与 没有吸收没有吸收律律+可交换可交换,可结合可结合 可交换可交换,可结合可结合+满足消去律满足消去律 满足消去律满足消去律 对对+可分配可分配+对对 不可分配不可分配+与与 没有吸收律没有吸收律可交换可交换,可结合可结合可交换可交换,可结合可结合不满足消去律不满足消去律 不满足消去律不满足消去律对对可分配可分配对对可分配可分配与与满足吸收律满足吸收律V1,V2,V3是同类型的代数系统是同类型的代数系统V1,V2是同种的代数系统是同种的代数系统V1,V2与与V3不是同种的代数系统不是同种的代数系统同类型与同种代数系统（续）同类型与同种代数系统（续）6子代数子代数定义定义 设设V=是代数系统

5、，是代数系统，B 是是 S 的非空子集的非空子集，如果，如果 B 对对 f1,f2,fk 都是封闭的，都是封闭的，且且 B 和和 S 含有相同的代数常数，则称含有相同的代数常数，则称 是是 V 的子代数系统，简称的子代数系统，简称 子代数子代数.有时有时将子代数系统简记为将子代数系统简记为 B.实例实例 N是是 和和的子代数的子代数.N 0是是的子代数，但不是的子代数，但不是的子代数的子代数说明：说明：子代数和原代数是同种的代数系统子代数和原代数是同种的代数系统 对于任何代数系统对于任何代数系统 V，其子代数一定存在，其子代数一定存在.7关于子代数的术语关于子代数的术语最大的子代数最大的子代数

6、 就是就是V 本身本身.如果如果V 中所有代数常数中所有代数常数构成集合构成集合 B，且，且 B 对对V 中所有运算封闭，则中所有运算封闭，则 B 就就构成了构成了V 的的最小的子代数最小的子代数.最大和最小子代数称为最大和最小子代数称为V 的的平凡的子代数平凡的子代数.若若 B 是是 S 的真子集，则的真子集，则 B 构成构成的子代数称为的子代数称为V 的的真子代数真子代数.例例2 设设V=，令，令 nZ=nz|zZ，n 为自然为自然数，则数，则 nZ 是是 V 的子代数的子代数,当当 n=1 和和 0 时，时，nZ 是是 V 的平凡的子代数，其他的都是的平凡的子代数，其他的都是 V 的非平

7、凡的真子的非平凡的真子代数代数.8积代数积代数定义定义 设设 V1=和和 V2=是代数系统，其中是代数系统，其中 o 和和 是二元运算是二元运算.V1 与与 V2 的的 积代数积代数 是是V=,S1 S2,=例例3 V1=,V2=,积代数积代数 ,Z M2(R),o =0212,31012,21101,59积代数的性质积代数的性质定理定理 设设 V1=和和 V2=是代数系统，其中是代数系统，其中 o 和和 是二元运算是二元运算.V1 与与 V2 的的积代数积代数是是 V=(1)若若 o 和和 运算是可交换的，那么运算是可交换的，那么 运算也是可交换的运算也是可交换的 (2)若若 o 和和 运算

8、是可结合的，那么运算是可结合的，那么 运算也是可结合的运算也是可结合的 (3)若若 o 和和 运算是幂等的，那么运算是幂等的，那么 运算也是幂等的运算也是幂等的 (4)若若 o 和和 运算分别具有单位元运算分别具有单位元 e1 和和 e2，那么，那么 运算运算 也具有单位元也具有单位元 (5)若若 o 和和 运算分别具有零元运算分别具有零元 1 和和 2，那么，那么 运算运算 也具有零元也具有零元 (6)若若 x 关于关于 o 的逆元为的逆元为 x 1,y 关于关于 的逆元为的逆元为 y 1，那，那 么么关于关于 运算也具有逆元运算也具有逆元 105.3 代数系统的同态与同构代数系统的同态与同

9、构n同态映射的定义同态映射的定义n同态映射的分类同态映射的分类单同态、满同态、同构单同态、满同态、同构自同态自同态n同态映射的性质同态映射的性质11同态映射的定义同态映射的定义定义定义 设设 V1=和和 V2=是代数系统，其是代数系统，其中中 和和 是二元运算是二元运算.f:S1S2,且且 x,y S1,f(x y)=f(x)f(y),则称则称 f 为为V1到到 V2 的的同态映射同态映射，简称，简称同态同态.12更广泛的同态映射定义更广泛的同态映射定义定义定义 设设 V1=和和 V2=是代数系统，是代数系统，其中其中 和和 是二元运算是二元运算.f:S1S2,且且 x,y S1 f(x y)

10、=f(x)f(y),f(x y)=f(x)f(y)则称则称 f 为为V1到到 V2 的的同态映射同态映射，简称，简称同态同态.设设 V1=和和 V2=是代数系统，是代数系统，其中其中 和和 是二元运算是二元运算.和和 是一元运算，是一元运算，f:S1S2,且且 x,y S1 f(x y)=f(x)f(y),f(xy)=f(x)f(y),f(x)=f(x)则称则称 f 为为V1到到 V2 的的同态映射同态映射，简称，简称同态同态.13例题例题例例1 V=,判断下面的哪些函数是判断下面的哪些函数是V 的自同态？的自同态？(1)f(x)=|x|(2)f(x)=2x (3)f(x)=x2 (4)f(x

11、)=1/x (5)f(x)=x (6)f(x)=x+1解解 (2),(5),(6)不是自同态不是自同态.(1)是同态，是同态，f(x y)=|x y|=|x|y|=f(x)f(y)(3)是同态，是同态，f(x y)=(x y)2=x2 y2=f(x)f(y)(4)是同态，是同态，f(x y)=1/(x y)=1/x 1/y=f(x)f(y)14特殊同态映射的分类特殊同态映射的分类同态映射如果是单射，则称为同态映射如果是单射，则称为单同态单同态；如果是满射，则称为如果是满射，则称为 满同态满同态，这时称，这时称 V2 是是 V1 的的同态像同态像，记作，记作 V1 V2；如果是双射，则称为如果是

12、双射，则称为 同构同构，也称代数系统，也称代数系统 V1 同构于同构于V2，记作，记作 V1 V2.对于代数系统对于代数系统 V，它到自身的同态称为，它到自身的同态称为自同态自同态.类似地可以定义类似地可以定义单自同态单自同态、满自同态满自同态和和自同构自同构.15同态映射的实例同态映射的实例例例2 设设V=，a Z，令，令 fa：ZZ，fa(x)=ax那么那么 fa是是V的自同态的自同态.因为因为 x,y Z，有，有 fa(x+y)=a(x+y)=ax+ay=fa(x)+fa(y)当当 a=0 时称时称 f0为零同态；为零同态；当当a=1时，称时，称 fa为自同构；为自同构；除此之外其他的除

13、此之外其他的 fa 都是单自同态都是单自同态.16例例3 设设V1=,V2=，其中，其中Q*=Q 0，令，令 f：QQ*,f(x)=ex 那么那么 f 是是V1到到V2的同态映射，因为的同态映射，因为 x,y Q有有 f(x+y)=ex+y=ex ey=f(x)f(y).不难看出不难看出 f 是单同态是单同态.同态映射的实例（续）同态映射的实例（续）17同态映射的实例（续）同态映射的实例（续）例例4 V1=，V2=，Zn=0,1,n-1,是模是模 n 加加.令令 f：ZZn，f(x)=(x)mod n则则 f 是是V1到到 V2 的满同态的满同态.x,yZ有有 f(x+y)=(x+y)mod

14、n =(x)mod n (y)mod n =f(x)f(y)18例例5 设设 V=，可以证明恰有，可以证明恰有 n 个个G 的自同态，的自同态，fp：ZnZn,fp(x)=(px)mod n，p=0,1,n 1例如例如 n=6,那么那么 f0为零同态；为零同态；f1与与 f5为同构；为同构；f2 与与 f4的同态像是的同态像是 0,2,4；f3 的同态像是的同态像是 0,3.同态映射的实例（续）同态映射的实例（续）19同态映射保持运算的算律同态映射保持运算的算律设设V1,V2是代数系统是代数系统.o,是是V1上的二元运算，上的二元运算，o,是是V2上对应的二元运算，如果上对应的二元运算，如果

15、f：V1V2是满同态，是满同态，那么那么 (1)若若o运算是可交换的（可结合、幂等的），则运算是可交换的（可结合、幂等的），则o运运算也是可交换的（可结合、幂等的）算也是可交换的（可结合、幂等的）.(2)若若o运算对运算对 运算是可分配的，则运算是可分配的，则o运算对运算对 运运算也是可分配的；若算也是可分配的；若o 和和 运算是可吸收的，则运算是可吸收的，则 o和和 运算也是可吸收的。运算也是可吸收的。20(3)若若e为为o 运算的单位元，则运算的单位元，则 f(e)为为o运算的单位元运算的单位元.(4)若若 为为o 运算的零元，则运算的零元，则 f()为为o运算的零元运算的零元.(5)设设

16、 u V1，若，若 u 1 是是 u 关于关于o运算的逆元，则运算的逆元，则 f(u 1)是是 f(u)关于关于o运算的逆元。运算的逆元。同态映射保持运算的特异元素同态映射保持运算的特异元素21同态映射的性质同态映射的性质说明：说明：上述性质仅在满同态时成立，如果不是满同态，上述性质仅在满同态时成立，如果不是满同态，那么相关性质在同态像中成立那么相关性质在同态像中成立.同态映射不一定能保持消去律成立同态映射不一定能保持消去律成立.例如例如 f:ZZn 是是 V1=到到 V2=的同的同态，态，f(x)=(x)mod n,V1中满足消去律，但是当中满足消去律，但是当 n 为合数时为合数时,V2中不满足消去律中不满足消去律.22例题例题证证 假设假设 f 是是 V2 到到 V1 的同构，那么有的同构，那么有f：V2V1，f(1)=0.于是有于是有 f(1)+f(1)=f(1)(1)=f(1)=0从而从而 f(1)=0，又有，又有 f(1)=0，这与，这与 f 的单射性矛盾的单射性矛盾.例例3 设设V1=，V2=，其中，其中 Q 为有理数为有理数集合，集合，Q*=Q 0，+和和 分别表示普通加