第5章代数系统的一些性质

1第五章代数系统的一般性质代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而近世代数研究的中心问题是代数系统的结构：半群、群、格与布尔代数等等。近世代数的基本概念、方法和结果已成为计算机科学与工程领域中研究人员的基本工具。在研究形式语言与自动机理论、编码理论、关系数据库理论、抽象数据类型理论中，在描述机器可计算的函数、研究计算复杂性、刻画抽象数据结构、研究程序设计学中的语义学、设计逻辑电路中有着十分广泛的应用。5.1代数运算及其性质5.1.1代数运算的定义定义5.1.1设S是一个非空集合，（1）函数f：SS,称为一个S上的一个一元运算。（2）函数f：SSS,称为一个S上的一个二元运算。记号：f(x,y)=z,xfy=zxy=z（3）函数f：SS…SS,称为一个S上的一个n元运算。［例5.1.1］(1)数理逻辑中的联结词；集合论中的并运算、交运算和补运算；整数集中的加法、减法和乘法运算都是相应集合上的运算.(2)但Z中的除法不是一个二元运算。(3)在Z商定义xy=x+y-2,则是一个二元运算。当S是有限集时，S上的一元、二元运算可用运算表来定义。定义5.1.2设是集合S上的n元运算，S是S的一个非空子集。若对x1，x2，…，xnS，有（x1，x2，…，xn）S，则称S关于运算是封闭的。［例5.1.2］实数集关于数的普通除法是封闭的，整数集关于数的普通加法不是封闭的。25.1.2代数运算的性质定义5.1.3设是集合S上的二元运算。若x，y∈S，xy=yx，则称运算满足交换律（或称是可交换的）。定义5.1.4设是集合S上的二元运算。若x，y，z∈S，(xy)z=x(yz)，则称运算满足结合律（或称是可结合的）。定义5.1.5设是集合S上的二元运算。若x∈S，xx=x，则称运算满足幂等律。定义5.1.8设和是集合S上的二元运算。若x，y，z∈S，x(yz)=(xy)xz），(yz)x=(yx)(zx)，则称关于满足分配律。定义5.1.9设和是集合S上的二元运算。若x，y∈S，x(xy)=xx(xy)=x则称关于满足分配律。［例5.1.3］R上的加法和乘法运算是可交换的，也是可结合的；但减法却是不可交换和不可结合的；乘法关于加法是可分配的，但加法关于乘法则是不可分配的。任一集合的幂集上的并和交运算是可交换和可结合的，并且它们是相互可分配的。注：若运算是可结合的，则有时我们简称为乘法，而把xy简记为xy，称为x与y的积。5.1.3特殊元素：单位元、零元、逆元定义5.1.10设是集合S上的二元运算。（1）若el∈S，使得x∈S，有elx=x，则称el是关于运算的左单位元（左么元）；（2）若er∈S，使得x∈S，有xer=x，则称er是关于运算的右单位元（右么元）；（3）若e∈S，使得x∈S，有ex＝xe=x，则称e是关于运算的单位元（么元）。定理5.1.3设是集合S上的二元运算，且el，er分别为关于运算的左和右么元，则3关于运算存在唯一么元e且e=el=er。证明：el=eler=er记e=el=er定义5.1.11设是集合S上的二元运算。(1)若0l∈S，使得x∈S，有0lx=0l，则称0l是关于运算的左零元；(2)若0r∈S，使得对x∈S，有x0r=0r，则称0r是关于运算的右零元；(3)若0∈S，使得对x∈S，有0x＝x0=0，则称0是关于运算的零元。定理5.1.4设是集合S上的二元运算，且0l，0r分别为关于运算的左和右零元，则关于运算存在唯一零元0且0=0l=0r。［例5.1.4］R上，关于加法的单位元是0，但无零元；关于乘法的单位元为1，零元为0；关于减法的右单位元是0，但无左单位元，故无单位元。在任一集合S的幂集(S)上，是集合并运算的单位元、交运算的零元，S是集合交运算的单位元、并运算的零元。定义5.1.12设是S上的二元运算，e为关于运算的单位元，x∈S，(1)若存在xl∈S，有xlx=e，则称xl是关于运算的左逆元；(2)若存在xr∈S，有xxr=e，则称xr是关于运算的右逆元；(3)若存在a∈S，有ax＝xa=e，则称a是关于运算的逆元。定理5.1.5设是集合S上可结合的二元运算，e为关于运算的单位元，x∈S，且xl，xr分别为x关于运算的左和右逆元，则xl=xr且它是x关于运算的唯一逆元。对S上可结合的二元运算，若x∈S可逆，则其逆元惟一，因此我们可将之记为x－1。x和x－1互为逆元，即（x－1）－1＝x。［例5.1.5］在R中，任一实数关于加法的逆元是它的相反数，任一非零实数关于乘法的逆元是它的倒数；但零关于乘法是不可逆的。定义5.1.13设是A上的二元运算，x，y，z∈A，xy=xzy=z；yx=zxx=y，则称满足消去律。［例5.1.6］任一实数关于加法满足消去律；任一非零实数关于乘法满足消去律；n4阶方阵的乘法运算不满足满足消去律。5.2代数系统及其子代数和积代数5.2.1代数系统定义5.2.1设S为非空集合，若1，2，…，n为S上的代数运算，则称S，1，2，…，n为一个代数系统（代数结构）。称S为该代数系统的定义域。若|S|是有限数，则称之为有限代数系统，并称|S|为该代数系统的阶。［例5.2.1］（1）R，+，，(A)，∩，∪，都是代数系统；（2）设∑是有限个字母组成的集合，∑表示∑上的串集合，∑上的连接运算定义为α，β∈∑，αβ=αβ，则∑，是一个代数系统。说明：单位元、零元等叫代数常数。5.2.2子代数定义5.1.2设S，1，2，…，n为一个代数系统，T为S的非空子集。若T关于1，2，…，n都封闭，且T为S含有相同的代数常数，则称代数结构T，1，2，…，n为S，1，2，…，n的子代数。［例5.2.1］I，+，是Q，+，的子代数，而Q，+，是R，+，的子代数。5.2.3积代数定义5.1.2设V1=S1，,V2=S2,是两个代数系统，V1与V2的积代数V1V2=S,其中S=S1S2，,,,,2211yxyx对于21212211,,,yyxxyxyx5.3同态与同构定义5.3.1设V1=S1，,V2=S2,是两个代数系统，如果存在映射：S1S2，使得x,yS1都有)()()(yxyx5则称是从V1到V2的同态映射，并称V1和V2是同态的。特别地（1）若是单射，则称为单一同态；（2）若是满射，则称为满同态，记为V1∽V2；（3）若是双射，则称为同构映射，并称V1和V2是同构的，记为V1≌V2；（4）若V1=V2，则称为自同态；（5）若V1=V2，且为双射，则称为自同构。［例5.3.1］xxRR2)(,:是R,+到R+,•的同态映射,也是同构映射.［例5.3.2］][)(,:xxZZn是Z,+到mZ,•的同态映射,不是同构映射.定义5.2.3设V1＝S，,和V2＝S，′，′是两个代数系统，函数f：SS。若f保持运算,即：)()()(yfxfyxf，)()()(yfxfyxf则称f是从V1到V2的同态映射，并称V1和V2是同态的。类似定义单同态、满同态、同构映射、自同态、自同构等概念。［例5.2.3］][)(,:xxZZn是Z,+，•到,,mZ（,表示模n加乘）定理5.2.4若h是从A＝S，，＋到A′＝S′，，的满同态映射，，＋为S上的二元运算，则1)若满足交换律，则也满足交换律；2)若满足结合律，则也满足结合律；3)若对+满足分配律，则对也满足分配律；4)若e为关于运算的么元，则h(e)是关于的么元；5)若为关于运算的零元，则h()是关于的零元；6)若a∈S关于运算是可逆的，则h(a)关于也是可逆的，且h(a-1)=h(a)-1。