离散数学及其应用-06 代数系统的基本概念

第六章代数系统的基本概念6.1二元运算及性质6.2代数系统6.3代数系统的同态与同构6.1.1二元运算的基本概念定义6.1.1设A1,A2,…An,A是非空集合,f是从A1×A2×…×An到A的一个映射,则称f为从集合A1×A2×…×An到A的一个n元代数运算,简称n元运算。其中,n称为代数运算的阶。6.1.1二元运算的基本概念【例6.1.1】(1)整数集合Z上的加法、减法和乘法均为二元运算,而除法不是。(2)A为集合,ρ(A)为其幂集,若f:ρ(A)×ρ(A)→ρ(A)为二元运算,则f可以是∩、∪、-、⊕。(3)设Mn(R)为n阶实矩阵的集合(n≥2),即6.1.1二元运算的基本概念则矩阵加法,减法和乘法都是Mn(R)上的二元运算。(4)设A=a1,a2,…an,ai

○

aj=ai,“○

(复合)”是A上的二元运算。当集合A为有限集时,A上的一元运算和二元运算可以用运算表给出。表6-1-1和表6-1-2分别是A上的一元运算和二元运算的一般形式。6.1.2二元运算的性质定义6.1.2设*为S上的二元运算。(1)若对于任意的x,y∈S都有x*y=y*x,则称运算*在S上是可交换的,或者称运算*在S上满足交换律。(2)若对于任意的x,y,z∈S都有(x*y)*z=x*(y*z),则称运算*在S上是可结合的,或者说运算*在S上满足结合律。(3)若对于任意的x∈S有x*x=x,则称运算*是等幂的,或者称运算*满足幂等律。6.1.2二元运算的性质【例6.1.2】Z、Q、R分别为整数集、有理数集、实数集;Mn(R)为n阶实矩阵集合,n≥2;ρ(S)为幂集,则有如下性质,见表6-1-3。6.1.2二元运算的性质定义6.1.3

设○和*为S上两个不同的二元运算,(1)若对于任意的x,y,z∈S都有:x

○(y*z)=(x

○

y)*(x

○

z)(左分配律)(y

○z)*x=(y*x)

○(z*x)(右分配律)则称运算○对*是可分配的,也称○对*满足分配律。如果以上两式中只有一个成立,则称○对*是可左分配的或可右分配的。(2)若○和*都可交换,并且对于任意的x,y∈S都有:x

○(x*y)=x(左吸收律)(x*y)

○

x=x(右吸收律)则称○和*满足吸收律。6.1.2二元运算的性质【例6.1.3】Z、Q、R分别为整数集、有理数集、实数集;Mn(R)为n阶实矩阵集合,n≥2;ρ(S)为幂集,则有如下性质,见表6-1-4。6.1.3二元运算的特异元素定义6.1.4设*是集合S中的一种二元运算,如果S上存在er∈S(el∈S)且对任意元素x∈S均有x*er=x(el*x=x),则称元素er(el)为S中关于运算*的右幺元(左幺元)或右单位元(左单位元),可以符号化为∃er(er∈S∧∀x(x∈S→x*er=x))或∃el(el∈S∧∀x(x∈S→el*x=x))若e∈S关于运算*既是左幺元,又是右幺元,则称e为S上关于运算*的幺元或单位元。6.1.3二元运算的特异元素定理6.1.1设集合S上关于二元运算*,既存在右幺元er,又存在左幺元el,则er=el=e,且e为S上关于运算*的唯一幺元。证明(1)证明左右幺元相等:因为er和el分别是运算*的右幺元和左幺元,故有el*er=el,el*er=er,所以er=el。(2)证明幺元是唯一的:令er=el=e,假设另有一幺元为右幺元e',那么e=e*e'=e',故e是S上关于运算*的唯一幺元。证毕。显然,对于可交换的二元运算,如果存在左幺元,则必存在右幺元,所以一定存在幺元。6.1.3二元运算的特异元素【例6.1.4】(1)在实数集R中,对加法“+”运算,0是幺元。(2)在实数集R中,对于乘法“×”运算,1是幺元。(3)对于全集E的子集的并“∪”运算,⌀是幺元。(4)对于全集E的子集的交“∩”运算,E是幺元。(5)在命题集合中,对于析取“∨”运算,矛盾式是幺元。(6)在命题集合中,对于合取“∧”运算,重言式是幺元。(7)对于从集合S到S的双射函数的合成运算,恒等函数是幺元。6.1.3二元运算的特异元素定义6.1.5设*是集合S中的一种二元运算,如果存在元素θr∈S(θl∈S)且对任意元素x∈S均有x*θr=θr(θl*x=θl),则称元素θr(θl)是S中关于运算*的右零元(左零元)。符号化类似定义6.1.4,这里不再赘述。6.1.3二元运算的特异元素定理6.1.2设集合S上关于二元运算*,既存在右零元θr又存在左零元θl,则θr=θl=θ,称元素θ是S中关于运算*的唯一零元。证明(1)证明左右零元相等:因为θr

和θl分别是运算*的右零元和左零元,故有θl*θr=θl,θl*θr=θr,所以θr=θl。(2)证明零元是唯一的:令θr=θl=θ,假设另有一零元为右零元θ',那么θ=θ*θ'=θ',故θ是S上关于运算*的唯一零元。证毕。6.1.3二元运算的特异元素【例6.1.5】(1)在实数集R中,对于加法“+”运算,没有零元。(2)在实数集R中,对于乘法“×”运算,0是零元。(3)对于全集E的子集的并“∪”运算,E是零元。(4)对于全集E的子集的交“∩”运算,⌀是零元。(5)在命题集合中,对于析取“∨”运算,重言式是零元。(6)在命题集合中,对于合取“∧”运算,矛盾式是零元。6.1.3二元运算的特异元素定义6.1.6设*为集合S上的二元运算,e∈S为S关于运算*的幺元,如果存在一个元素al∈S(或ar∈S),使得对于元素a∈S,有al*a=e(或a*ar=e)成立,则称a是左可逆的(右可逆的),并称al(或ar)是a的左逆元(右逆元)。若对于a∈S,既存在左逆元又存在右逆元,则称a是可逆的。6.1.3二元运算的特异元素定理6.1.3设*为集合S上的一个可结合的二元运算,e为该运算的幺元。对于x∈S,如果存在左逆元al和右逆元ar,则al=ar=a,即a是x的逆元,且是唯一的。证明(1)证明左右逆元相等:因为e是S上关于运算*的幺元,故有al*x=e和x*ar=e,又因为运算*是可结合的,所以al*x*ar=(al*x)*ar=e*ar=ar

al*x*ar=al*(x*ar)=al*e=al显然,左右逆元相等。(2)证明逆元是唯一的:令al=ar=a,假设x有两个不同的逆元a1和a2,由逆元的定义知a1=a1*e=a1*(x*a2)=(a1*x)*a2=e*a2=a2与假设矛盾,于是x的逆元是唯一的。证毕。6.1.3二元运算的特异元素定理6.1.4设*是集合S中的一个可结合的二元运算,且e为S中对于*的幺元,x有逆元x-1,则(x-1)-1=x。证明(x-1)-1=(x-1)-1*e=(x-1)-1*(x-1*x)=((x-1)-1*x-1)*x=e*x=x。证毕。6.1.3二元运算的特异元素【例6.1.6】给定⊗是集合S上的二元运算,其中S=α,β,γ,δ,ξ表6-1-5。试指出该代数系统中各元素的左、右逆元情况。6.1.3二元运算的特异元素解α是幺元,β的左逆元和右逆元都是γ,即β与γ互为逆元。δ的左逆元是γ,而右逆元是β,β有两个左逆元γ和δ。ξ的右逆元是γ,但ξ没有左逆元。6.1.3二元运算的特异元素定义6.1.7设*为集合S上的二元运算,如果对任意的x,y,z∈S满足以下条件:(1)若x*y=x*z且x不是零元,则y=z。(2)若y*x=z*x且x不是零元,则y=z。就称运算*满足消去律。其中(1)称作左消去律,(2)称作右消去律。6.1.3二元运算的特异元素【例6.1.7】设*运算为集合Q上的二元运,∀x,y∈Q,x*y=x+y+2xy:(1)判断*运算是否满足交换律和结合律,并说明理由。(2)求出*运算的单位元、零元和所有可逆元素的逆元。解(1)任取x,y∈Q,x*y=x+y+2xy=y+x+2yx=y*x任取x,y,z∈Q,(x*y)*z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyzx*(y*z)=x+(y+z+2yz)+2x(y+z+2yz)=x+y+z+2xy+2xz+2yz+4xyz所以,*运算可交换、可结合,即满足交换律和结合律。6.1.3二元运算的特异元素(2)设*运算的单位元和零元分别为e和θ,则对于任意x有x*e=x成立,即x+e+2xe=x⇒e=0由于*运算可交换,所以0是幺元。对于任意x有x*θ=θ成立,即x+θ+2xθ=θ⇒x+2xθ=0⇒θ=-1/2由于*运算可交换,所以-1/2是零元。给定x,设x的逆元为y,则有x*y=0成立,即x+y+2xy=0⇒y=-x/(1+2x)(x≠-1/2)因此当x≠-1/2时,-x/(1+2x)(是x的逆元。6.2.1代数系统的基本概念定义6.2.1

设S是非空集合,f1,f2,…,fk

是S上的k个一元或二元运算,则S称为基集,各运算组成的集合称为运算集,集合S连同其上的代数运算组成的系统称为代数系统,简称代数,记作<S,f1,f2,…,fk

>。对于代数系统<S,f1,f2,…,fk>的理解,需要注意以下几点:(1)S≠⌀。(2)f1,f2,…,fk(k>1)。(3)如果S是有限集合,则称代数系统是有限代数系统,否则称为无限代数系统。(4)代数运算fi(i=1,2,…,k)不仅限于一元或二元运算,还有其他n元n>2数运算类,但较复杂,故代数系统通常研究一元或二元运算。6.2.1代数系统的基本概念【例6.2.1】(1)以实数集R为基集,数加运算“+”为二元运算,组成一代数系统,记为<R,+>。(2)以全体n×n实数矩阵组成的集合M为基集,矩阵加“○

”为二元运算,组成一代数系统,记为<M,

○

>。(3)以集合S的幂集ρ(S)为基集,以集合并、交、补为其二元运算和一元运算,组成一代数系统,记为<ρ(S),,∪,∩,~>。这个系统就是常说的幂集代数系统。以上的(1)(2)(3)均称为具体代数系统,其运算满足的性质未列出。(4)设S为一非空集合,

○为S上满足结合律、交换律的二元运算,那么<S,

○>为代数ρ(S)结构,称为一个代数抽象系统,即一类具体代数系统的抽象。例如<R,+>,<M,

○

>,<ρ(S),∪,∩,~>都是<S,

○

>的具体例子。<R,+,-,×>,<Z,+,-,×>均是代数系统,但我们不能写<Z,÷>,<R,÷>,<N,->,因为它们不是代数系统,它们的运算不封闭。6.2.1代数系统的基本概念定义6.2.2

如果两个代数系统中运算个数相同,对应运算的阶数相同,且代数常数的个数也相同,则称它们是同类型的代数系统。如果两个同类型的代数系统规定的运算性质也相同,则称为同种的代数系统。例如命题代数与幂集代数:<ρ(S),∪,∩,~,S,Φ>与<R,+,×,-,0,1>。6.2.1代数系统的基本概念定义6.2.3设V=<S,f1,f2,…,fk>是一个代数系统,B⊆S且B≠⌀,如果B在运算f1,f2,…,fk作用下都是封闭的,且B和S含有相同的代数常数,则称<B,f1,f2,…,fk>是V的子代数系统,简称子(subalgebra)。根据定义有以下几点结论:(1)对任何代数系统V=<S,f1,f2,…,fk>,其子代数一定存在。(2)最大的子代数就是V本身。(3)如果令V中所有的代数常数构成的集合是B,且对V中所有的运算都是封闭的,那么,B就构成了V的最小的子代数。(4)最大与最小的子代数称为V的平凡的子代数。(5)如果V的子代数V'=<S,f1,f2,…,fk>,其子代数一定存在。满足B⊂S,则称V'是V的真子代数。6.2.1代数系统的基本概念【例6.2.2】(1)<N,+,0>是<Z,+,0>的子代数,因为N对加法封闭,且它们都有相同的代数常数0。(2)设E为非负偶数集,M为非负奇数集,则对<N,+>而言,<E,+>为其子代数,<N,+>,<0,+>为其平凡子代数,<M,+>不构成其子代数。6.2.2代数系统的同态与同构定义6.2.4设<S,*>与<T,○

>是同类型的代数系统,如果函数f:S→T对S中任何元素a,b有f(a*b)=f(a)

○

f(b)称函数f为(代数系统S到T的)同态映射,简称同态(homomorphism),当同态f为单射时,又称f为单同态;当f为满射时,又称f为满同态;当f为双射时,又称f为同构映射,或同构(isomorphism)。当两个代数系统间存在同构映射时,也称这两个代数系统同构,记为S≅T。当f为<S,*>到<S,*>的同态(同构)时,称f为S的自同态(自同构)。f(a*b)=f(a)