《离散数学课件》代数系统

小结代数运算的基本概念11.二元运算（封闭）2.运算的表示（运算表）3.二元运算的性质交换律、结合律、幂等律、消去律分配律、吸收律4.二元运算的特异元素单位元零元可逆元素及其逆元x∘

y=y∘

x(x∘

y)∘

z=x∘

(y

∘

z)el

∘

x=x

且x

∘

er=xθl∘

x=θl

且x∘θr=θryl∘

x=e且x

∘

yr=e2/5511.2代数系统和半群(一)代数系统(二)同态映射、同构映射(三)半群(四)含幺半群(五)子半群3/55代数系统定义1

设A是一个集合，*1，*2，…，*n是A上的n个代数运算，而（A，*1，*2，…，*n）表示集合A，以及A上的n个代数运算*1，*2，…，*n组成的一个代数系统。

主要研究内容：只有一个代数运算的代数系统（A，*）4/55例（N，+）表示自然数集带着数的加法。（N，·）表示自然数集带着数的乘法。（N，－）表示自然数集和数的减法运算。（N，+,·）表示自然数集带着数的加法与乘法。+是N×N到N的代数运算·是N×N到N的代数运算－是N×N到Z的代数运算5实例<N,+>,<Z,+,·>,<R,+,·>是代数系统，

+和·分别表示普通加法和乘法.<Mn(R),+,·>是代数系统，

+和·分别表示n阶(n≥2)实矩阵的加法和乘法.<Zn,,>是代数系统，Zn＝{0,1,…,n-1}，和分别表示模n的加法和乘法，x,y∈Zn，

xy=(x＋y)modn，xy=(xy)modn<P(S),∪,∩,~>也是代数系统，∪和∩为并和交，~为绝对补6/55同态函数定义2：设（A，*），（A1，·）是两个代数系统，*是A上的一个二元运算，·是A1上一个二元运算。一个函数f：A→A1是A到A1的同态函数，若对于A中的任意两个元素a，b，有

f（a*b）=f（a）·f（b）■若f是单射，说f是单一同态函数；■若f是满射，说f是满同态函数；■若f是双射，说f是同构函数。7/55单同态、满同态、同构两个代数系统之间若存在单一同态函数，说这两个代数系统是单同态的；两个代数系统之间若存在满同态函数，说这两个代数系统是满同态的；两个代数系统之间若存在同构函数，说这两个代数系统是同构的。8/55例(p176)Z是整数集，Z上的二元运算是数的加法，即(Z，＋)。A={1，-1}，A上的二元运算是数的乘法，即(A，·)。分别定义三个Z到A的函数如下φ1：Z→A，对于每一个n∊Z，φ1(n)=1。φ2：Z→A，对于每一个n∊Z，若n是偶数，φ2(n)=1；若n是奇数，φ2(n)=-1。φ3：Z→A，对于每一个n∊Z，φ3(n)=-1。则φ1是同态函数，

φ2是满同态函数，

φ3不是同态函数。9/55例(p176)φ1：Z→A={1,-1}，对于每一个n∊Z，φ1(n)=1。显然，对于Z中的任意二个数n和m，有

φ1(n)=1，

φ1(m)=1，

φ1(n+m)=1，∴

φ1(n+m)=φ1(n)·φ1(m)故φ1是同态函数。

f（a*b）=f（a）·f（b）(Z，＋)(A，·)10/55例(p176)φ2：Z→A，对于每一个n∊Z，若n是偶数，φ2(n)=1；若n是奇数，φ2(n)=-1。显然φ2是Z到A的满射。对于Z中的任意的二个数n和m来说：若n和m均是偶数，那么φ2(n+m)=φ2(n)·φ2(m)。若n和m均是奇数，那么φ2(n+m)=φ2(n)·φ2(m)。若n和m一个奇数，一个偶数，不失一般性设n是奇数，m是偶数，那么φ2(n+m)=φ2(n)·φ2(m)。所以φ2是满同态映射。即（Z，+）与（A，·）是两个满同态代数系统。11/55例(p177)φ3：Z→A={1，-1}，对于每一个n∊Z，φ3(n)=-1。取n=2，m=3时，φ3(n)=φ3(m)=-1，而

φ3(n+m)=φ3(5)=-1并且有

φ3(n)·φ3(m)=1于是

φ3(n+m)≠φ3(n)·φ3(m)所以φ3不是同态映射。12/55定理1（A1，*）和（A2，·）是两个代数系统，且（A1，*）与（A2，·）满同态。若“*”适合交换律，则“·”也适合交换律；若“*”适合结合律，则“·”也适合结合律。13/55半群定义3：设（A，*）是一个代数系统，A是一个非空集，*是A上的一个二元运算。若*是A上的闭运算，且*适合结合律，则称（A，*）是一个半群。14实例（1）<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群，+是普通加法.（2）设n是大于1的正整数，<Mn(R),+>和<Mn(R),·>都是半群，其中+和·分别表示矩阵加法和矩阵乘法.（3）<P(B),>为半群，其中为集合的对称差运算.（4）<Zn,>为半群，其中Zn={0,1,…,n1}，为模n加法.（5）<AA,>为半群，其中为函数的复合运算.（6）<R*,>为半群，其中R*为非零实数集合，运算定义如下：x,y∈R*,xy=y15/55例对于任意二个自然数m和n，定义“*”运算：m*n=m+n+m·n不难验证，（N，*）也是一个半群。在自然数集上还可以定义许多的二元运算，使它们构成半群。(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac+bc+abca*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac+bc+abc16/55含幺半群定义5

称含有幺元的半群为含幺半群。也叫做独异点.例■

0是半群（N，+）的么元，（N，+）是含幺半群。■

1是半群（N，·）的么元，（N，·）是含幺半群。

可记为（N，+，0）（N，·，1）17/55子半群定义6：（A，*）是一个半群，Ø≠B⊆A，若（B，*）本身是一个半群，则称（B，*）是（A，*）的子半群。18/6411.3群的基本概念(一)逆元(二)群的定义(三)群的同态、同构(四)无限群、有限群、交换群、元的阶19/64群定义2：设A是一个非空集，（A，*）是一个代数系统，*是A上的一个二元运算，若（A，*）满足： ①*是A上的闭运算； ②*适合结合律； ③存在e

∊

A，是幺元（又称单位元）； ④对于A中的任意元素a，存在a-1

∊

A，使得

a*a-1=a-1*a=e。则称（A，*）是一个群。20/64例（N，+）不是群，是含幺半群，幺元是0。（Z，+）是群。（Q，+）是群。（R，+）是群。（Z，·）不是群，也是含幺半群，幺元是1。（Q，·）也不是群，因为0∊Q，但0没有逆元。（Q*，·）是群，这里Q*=Q-{0}.（R*，·）也是群，这里R*=R-{0}。21/64Klein四元群设G={e,a,b,c},*为G上的二元运算，它由运算表给出。

不难证明:e是G中的幺元；G中任何元素的逆元就是它自己;G是一个群。

在a,b,c三个元素中，任何两个元素运算的结果都等于另一个元素。*eabceeabcaaecbbbceaccbae22群中的术语若群G是有穷集，则称G是有限群，否则称为无限群.群G的基数称为群G的阶有限群G的阶记作|G|.若群G中的二元运算是可交换的，则称G为交换群或阿贝尔(Abel)群.

23实例

<Z,+>和<R,+>是无限群

<Zn,>是有限群，也是n阶群

Klein四元群

G={e,a,b,c}是4阶群

上述群都是交换群

n阶(n≥2)实可逆矩阵集合关于矩阵乘法构成的群是非交换群.

24/64定义4群同态映射设（G，*）和（A，*）是二个群，

f是G到A的一个映射， 若对于任意的g1，g2∊G，有

f（g1*g2）=f（g1）*f（g2），则称f是（G，*）到（A，*）的群同态映射。■若f是单射，说f是单一同态；■若f是满射，说f是满同态，也说（A，*）是（G，*）的同态象；■若f是双射，说f是同构映射。25/64同态的群、同构的群说群（G，*）和（A，*）是二个同态的群，若存在（G，*）到（A，*）的满同态映射；说群（G，*）和（A，·）是二个同构的群，若存在（G，*）到（A，·）的同构映射。26/64例3(p182)设（G，*）和（A，·）是二个任意的群，e1和e2分别是它们的幺元。则φ

：G→A，对于任意的g∊G，φ(g)=e2是一个同态映射。证明：因为，对于任意的g1，g2∊G，

φ（g1*g2）=e2，

φ（g1）=φ（g2）=e2。 所以

φ（g1*g2）=φ（g1）·φ（g2）

=e2·e