离散代数运算

主要内容：代数运算定义性质特殊元1§7.1代数运算与代数系统

1.代数运算定义(1)定义：设A为非空集合，nI+,f:An→A称为A上的n元运算，n称为运算的阶。例1：R上的加法+、乘法

运算是R上的二元运算。例2：幂集

(U)上,集合的补是

(U)上的一元运算，交、并是二元运算。例3：字符串的连接运算是字符串集合上的二元运算。

Σ–字母集合，Σ*–由Σ中的字母构成的字符串集合，o–字符串的连接运算,o:(Σ*)2→Σ*

例4：设A={深色，浅色}*深色浅色深色浅色深色深色深色浅色*：A2→A*是A上的二元运算。封闭性性质»单位元»零元»逆元»可约»判别2封闭性设o是A上的n元运算，SA且S，如果a1,…,anS,均有o(a1,…,an)S,则称S关于运算o是封闭的。定理7.1.1:设o是A上的n元运算，C是

(A)的非空子集，若SC,S关于运算o是封闭的，则∩C关于运算o也是封闭的。证明：设a1,…,an

∩C，则SC,有a1,…,anS,

∵S关于运算o是封闭的,∴o(a1,…,an)S,∴o(a1,…,an)∩C,

故∩C关于运算o也是封闭的。§7.1代数运算与代数系统

2.代数运算的性质(1)3设*,o是集合A上的二元运算交换律：

a,bA,有a*b=b*a结合律：

a,b,cA,有(a*b)*c=a*(b*c)常用an表示a*a*…*a,并称为a的n次幂，n为a的指数。定理7.1.3若*是集合A上的可结合的二元运算，则

aA，m,nI,有am*an=am+n;(am)n=amn分配律：*对o既是左可分配，又是右可分配；*对o左可分配:

a,b,cA,有a*(boc)=(a*b)o(a*c)*对o右可分配：

a,b,cA,有(aob)*c=(a*c)o(b*c).分析例1-4§7.1代数运算与代数系统

2.代数运算的性质(2)4单位元（幺元）定义：设*是A上的二元运算，0+a=aa+0=a0+a=a+0=a

①若

elA,使得aA,有el*a=a,则称el为关于*的左单位元.②若

erA,使得aA,有a*er=a,则称er为关于*的右单位元.③若

eA,使得aA,有e*a=a*e=a,则称e为关于*的单位元.例1中：§7.1代数运算与代数系统

3.与二元运算相关的特殊元(1)R关于+:左单位元、右单位元、单位元均为0。R关于

:左单位元、右单位元、单位元均为1。例2中：(U)关于

:左单位元、右单位元、单位元均为

。

(U)关于

:左单位元、右单位元、单位元均为U。例3中：Σ*关于o:左单位元、右单位元、单位元均为空串

。例4中：A关于*:左单位元、右单位元、单位元均为“浅色”。5例5：N上定义*：

a,bN,a*b=bN关于*的左单位元

右单位元单位元§7.1代数运算与代数系统

3.与二元运算相关的特殊元(2)：每个元素都是左单位元；：无；：无定理7.1.4设*是A上的二元运算，el和er分别是关于*的左右单位元，则el=er，且它是关于*的唯一单位元。证明：el*er=erel=令e=er=el,则e是关于*的单位元，设e’也是关于*的单位元，则e’=e*e’=e,所以，e是关于*的唯一单位元零元»可约»6R关于+:左零元、右零元、零元均无。R关于

:左零元、右零元、零元均为0。§7.1代数运算与代数系统

3.与二元运算相关的特殊元(3)零元：定义：设*是A上的二元运算，

①若

zlA,使得aA,有zl*a=zl,则称zl为关于*的左零元.②若

zrA,使得aA,有a*zr=zr,则称zr为关于*的右零元.③若

zA,使得aA,有z*a=a*z=z,则称z为关于*的零元.例1中:例2中:(U)关于

:左零元、右零元、零元均为U。

(U)关于

:左零元、右零元、零元均为

。例3中:Σ*关于o:无左零元、右零元和零元。例4中：A关于*:左零元、右零元、零元均为“深色”例5中：N关于*:每个元素都是右零元、无左零元和零元。定理7.1.5若关于*的左右零元都存在，则他们相等，是唯一零元。7逆元：定义：设*是A上的二元运算，e是关于*的单位元，aA

①若

alA,使得al*a=e,则称al为a关于*的左逆元.②若

arA,使得a*ar=e,则称ar为a关于*的右逆元.③若

a’A,使得a’*a=a*a’=e,则称a’为a关于*的逆元.例1中：§7.1代数运算与代数系统

3.与二元运算相关的特殊元(4)关于+:aR的左逆元、右逆元和逆元均为-a。关于

:aRa0,a的左逆元、右逆元和逆元均为1/a。例2中：关于

:(A)中，的左逆元、右逆元和逆元均为

。关于

:(A)中，U左逆元、右逆元和逆元均为U。例3中：关于o:Σ*中，空串的左逆元、右逆元和逆元均为

。例4中：关于*:A中，浅色的左逆元、右逆元和逆元均为浅色。8定理7.1.6设*是A上的可结合的二元运算，e是关于*的单位元，

al,ar分别为a关于*的左右逆元，则al=ar且它是a关于*的唯一逆元。§7.1代数运算与代数系统

3.与二元运算相关的特殊元(5)幂等元：定义：设*是A上二元运算，aA，若a*a=a,则称a是关于*的幂等元。可约元：定义：设*是A上二元运算，aA，

①x,yA,a*x=a*yx=y,则称a关于*左可约；②x,yA,x*a=y*a

x=y,则称a关于*右可约；③若a关于*既左可约又右可约，则称a关于*可约；

④若aA都是可约的，则称*满足消去律。分析例1-4

9例1中：关于+:aR均为左可约，右可约，也是可约的；关于

:aRa0均为左可约，右可约，也是可约的；

+满足消去律。例2中：关于：是可约的；关于：U可约。例3中：关于o:*均可约。例4中：关于*:浅色可约。例5中：关于*:iN均左可约。定理7.1.7设*为A上的可结合的二元运算，aA，若a关于*可逆，则a关于*可约。*此定理的逆不成立。例6：N中的乘法运算.§7.1代数运算与代数系统

3.与二元运算相关的特殊元(6)10定理7.1.7:设*为A上的可结合的二元运算，aA，

若a关于*可逆，则a关于*可约。证明：

x,yA，如果a*x=a*y,∵a关于*可逆,=e*x由a*x=a*y，又有a-1*(a*x)=a-1*(a*y)

=(a-1*a)*y=e*y=y

=x

∴x=y故a关于*左可约。∴有a-1,使a-1*a=a*a-1=e;∴a-1*(a*x)=(a-1*a)*x

同理可证a关于*右可约。分析例4的运算表