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

第五章 代数系统的一般性质 代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而近世代数研究的中心问题是代数系统的结构：半群、群、格与布尔代数等等。近世代数的基本概念、方法和结果已成为计算机科学与工程领域中研究人员的基本工具。在研究形式语言与自动机理论、编码理论、关系数据库理论、抽象数据类型理论中，在描述机器可计算的函数、研究计算复杂性、刻画抽象数据结构、研究程序设计学中的语义学、设计逻辑电路中有着十分广泛的应用。5.1代数运算及其性质5.1.1代数运算的定义定义5.1.1 设S是一个非空集合，（1）函数f：SS,称为一个S上的一个一元运算。（2）函数f：SSS,称为一个S上的一个二元运算。 记号： f(x,y)=z, xfy=z xy=z（3）函数f：SSS S,称为一个S上的一个n元运算。例5.1.1(1)数理逻辑中的联结词；集合论中的并运算、交运算和补运算；整数集中的加法、减法和乘法运算都是相应集合上的运算.(2)但Z中的除法不是一个二元运算。(3) 在Z商定义xy=x+y-2,则是一个二元运算。当S是有限集时，S上的一元、二元运算可用运算表来定义。定义5.1.2 设是集合S上的n元运算，S是S的一个非空子集。若对x 1，x 2，x nS，有（x 1，x 2，x n）S，则称S关于运算是封闭的。例5.1.2实数集关于数的普通除法是封闭的，整数集关于数的普通加法不是封闭的。5.1.2代数运算的性质定义5.1.3 设是集合S上的二元运算。若x，yS，xy=yx，则称运算满足交换律（或称是可交换的）。定义5.1.4 设是集合S上的二元运算。若x，y，zS，(xy)z = x(yz)，则称运算满足结合律（或称是可结合的）。定义5.1.5 设是集合S上的二元运算。若xS，xx = x，则称运算满足幂等律。定义5.1.8 设和是集合S上的二元运算。若x，y，zS，x(yz)=(xy)xz），(yz)x =(yx)(zx)，则称关于满足分配律。定义5.1.9 设和是集合S上的二元运算。若x，yS，x(xy)=xx(xy)=x则称关于满足分配律。例5.1.3R上的加法和乘法运算是可交换的，也是可结合的；但减法却是不可交换和不可结合的；乘法关于加法是可分配的，但加法关于乘法则是不可分配的。任一集合的幂集上的并和交运算是可交换和可结合的，并且它们是相互可分配的。注：若运算是可结合的，则有时我们简称为乘法，而把xy简记为xy，称为x与y的积。5.1.3特殊元素：单位元、零元、逆元定义5.1.10 设是集合S上的二元运算。（1）若elS，使得xS，有elx=x，则称el是关于运算的左单位元（左么元）；（2）若erS，使得xS，有xer=x，则称er是关于运算的右单位元（右么元）；（3）若eS，使得xS，有exxe=x，则称e是关于运算的单位元（么元）。定理5.1.3 设是集合S上的二元运算，且el，er分别为关于运算的左和右么元，则关于运算存在唯一么元e且 e=el=er。证明： el= el er= er 记e=el=er定义5.1.11 设是集合S上的二元运算。(1)若0lS，使得xS，有0lx=0l，则称0l是关于运算的左零元；(2)若0rS，使得对xS，有x0r =0r，则称0r是关于运算的右零元；(3)若0S，使得对xS，有0xx0=0，则称0是关于运算的零元。定理5.1.4 设是集合S上的二元运算，且0l，0r分别为关于运算的左和右零元，则关于运算存在唯一零元0且 0=0l=0r。例5.1.4R上，关于加法的单位元是0，但无零元；关于乘法的单位元为1，零元为0；关于减法的右单位元是0，但无左单位元，故无单位元。在任一集合S的幂集(S)上，是集合并运算的单位元、交运算的零元，S是集合交运算的单位元、并运算的零元。定义5.1.12 设是S上的二元运算，e 为关于运算的单位元，xS，(1)若存在x lS，有xlx= e，则称xl是关于运算的左逆元；(2)若存在xrS，有xxr = e，则称xr是关于运算的右逆元；(3)若存在S，有xx= e，则称是关于运算的逆元。定理5.1.5 设是集合S上可结合的二元运算，e 为关于运算的单位元，xS，且x l，x r分别为x关于运算的左和右逆元，则x l= x r 且它是x关于运算的唯一逆元。 对S上可结合的二元运算，若x S可逆，则其逆元惟一，因此我们可将之记为x1。x和x1互为逆元，即（x1）1x。例5.1.5在R中，任一实数关于加法的逆元是它的相反数，任一非零实数关于乘法的逆元是它的倒数；但零关于乘法是不可逆的。定义5.1.13 设是A上的二元运算，x，y，zA，xy=xzy=z； yx= zx x=y，则称满足消去律。例5.1.6任一实数关于加法满足消去律；任一非零实数关于乘法满足消去律；n阶方阵的乘法运算不满足满足消去律。5.2代数系统及其子代数和积代数5.2.1代数系统定义5.2.1 设S为非空集合，若，为S上的代数运算，则称为一个代数系统（代数结构）。称S为该代数系统的定义域。若|S|是有限数，则称之为有限代数系统，并称|S|为该代数系统的阶。例5.2.1（1），都是代数系统；（2） 设是有限个字母组成的集合，表示上的串集合，上的连接运算定义为，=，则是一个代数系统。说明：单位元、零元等叫代数常数。5.2.2 子代数定义5.1.2 设为一个代数系统，T为S的非空子集。若T关于，都封闭，且T为S含有相同的代数常数，则称代数结构为的子代数。例5.2.1是的子代数，而是的子代数。5.2.3积代数定义5.1.2设V1=, V2=是两个代数系统，V1与V2的积代数V1V2=其中S=S1S2，5.3同态与同构定义5.3.1 设V1=, V2=是两个代数系统，如果存在映射：S1 S2，使得x,y S1都有则称是从V1到 V2的同态映射，并称V1和 V2是同态的。 特别地（1）若是单射，则称为单一同态；（2）若是满射，则称为满同态，记为V1V2；（3）若是双射，则称为同构映射，并称V1和V2是同构的，记为V1V2；（4）若V1=V2，则称为自同态；（5）若V1=V2，且为双射，则称为自同构。例5.3.1是到的同态映射,也是同构映射.例5.3.2是到的同态映射,不是同构映射.定义5.2.3 设V1和V2是两个代数系统，函数f：S。若f保持运算,即： ， 则称f是从V1到V2的同态映射，并称V1和V2是同态的。类似定义单同态、满同态、同构映射、自同态、自同构等概念。例5.2.3是到（表示模n加乘）定理5.2.4 若h是从A到A的满同态映射，为S上的二元运算，则1) 若满足交