离散数学之代数系统篇

142第三篇代数系统篇第3-1章代数结构本章将从引入一般代数系统出发，研究如群、环、域等这样一些代数系统，而这些代数系统中的运算所具有的性质确定了这些代数系统的数学结构。§3-1-1代数系统的概念在计算机科学中，常用代数系统去描述机器可计算函数，研究运算的复杂性，分析程序设计语言的语义等。由非空集合和该集合上的一个或多个运算所组合的系统，常称为代数系统，有时简称为代数。在研究代数系统之前，首先考察一个非空集合上运算的概念，如将有理数集合Q上的每一个数a的映射成它的整数部分［a］；或者将Q上的每一个数a映射成它的相反数-a，这两个映射可以称为集合Q上的一元运算；而在集合Q上，对任意两个数所进行的普通加法和乘法都是集合Q上的二元运算，也可以看作是将Q中的每两个数映射成一个数；至于对集合Q上的任意三个数x１，x2，x3，代数式x12+x22+x32和x1+x2+x3分别给出了Q上的两个三元运算，它们分别将Q中三个数映射成Q中的一个数。上述这些例子有一个共同的特征，那就是其运算的结果都是在原来的集合中，我们称那些具有这种特征的运算是封闭的，简称闭运算。相反地，没有这种特征的运算就是不封闭的。很容易举出不封闭运算的例子，设N是自然数集，Z是整数集，普通的减法是N×N到Z的运算，但因为两个自然数相减可以不是自然数，所以减法运算不是自然数集N上的闭运算。定义3-1-1.1设A和B都是非空集合，n是一个正整数，若是An到B的一个映射，则称是A到B的一个n元运算。当B=A时，称是A上的n元运算（n-aryoperation），简称A上的运算。并称该n元运算在A上是封闭的。例3-1-1.1（1）求一个数的倒数是非零实数集R*上的一元运算。（2）非零实数集R*上的乘法和除法都是R*上的二元运算，而加法和减法不是。（3）S是一非空集合，SS是S到S上的所有函数的集合，则复合运算○是SS上的二元运算。（4）空间直角坐标系中求点（x，y，z）的坐标在x轴上的投影可以看作实143数集R上的三元运算f(x，y，z)=x，因为参加运算的是有序的3个实数，而结果也是实数。通常用等○，，﹡，……等表示二元运算，称为算符。若f：s×s→s是集合S上的二元运算，对任意x,yS,如果x与y运算的结果是z,即f(x，y)=z,可利用运算○简记为，x○y=z。类似于二元运算，也可以使用算符来表示n元运算。如n元运算f（a1，a2，…，an）=b可简记为○（a1，a2，……，an）=bn=1时○（a1）=b是一元运算n=2时○（a1，a2）=b是二元运算n=3时○（a1，a2，a3）=b是三元运算这些相当于前缀表示法，但对于二元运算用得较多的还是a1○a2=b，以下所涉及的n元运算主要是一元运算和二元运算。若集合X={x1，x2，……，xn}是有限集，X上的一元运算和二元运算也可用运算表给出。表3-1-1.1和3-1-1.2分别是一元运算和二元运算的一般形式。表3-1-1.1表3-1-1.2例3-1-1.2设集合S＝｛0，1｝，给出Ｓ的幂集P(S）上求补运算～和求对称差运算的运算表，其中全集是S解所求运算表如表3-1-1.3和表3-1-1.4所示。表3-1-1.3表3-1-1.4定义3-1-1.2一个非空集合A连同若干个定义在该集合上的运算f1，○S1S2……SnS1S2……SnS1○S1S1○S2……S1○SnS2○S1S2○S2……S2○Sn………………Sn○S1Sn○S2……Sn○SnSi○（Si）S1S2……Sn○(S1)○(S2)……○(Sn)Si～（Si）{0}{1}{0，1}{0，1}{1}{0}{0}{1}{0，1}{0}{1}{0,1}{0}{1}{0，1}{0}{0，1}{1}{1}{0，1}{0}{0，1}{1}{0}144f2，……，fk所组成的系统称为一个代数系统（algbraicsystem）。记作＜A，f1，f2，……，fk＞。如果对集合S，由S的幂集P（S）以及该幂集上的运算“∪”、“∩”、“～”组成一个代数系统＜P（S），∪，∩，～＞，S1∈P（S），S1的补集～S1=S-S1也常记为_S1。又如整数集Z以及Z上的普通加法“+”组成一个系统＜Z，+＞。值得注意的是，虽然代数系统有许多不同的形式，但它们可能有一些共同的运算。例如，考察上述代数系统＜Z，+＞。很明显，在这个代数系统中，关于加法运算，具有以下二个运算规律，即对于任意的x，ｙ，ｚ∈Ｚ，有(1)x+y=y+x(交换律)(2)(x+y)+z=x+(y+z)（结合律）又如，设S是集合，P（S）是S的幂集，则代数系统＜P（S），U＞和＜P（S），∩＞中的∪、∩都适合交换律，结合律，即他们与＜Z，+＞有类似的运算性质。§3-1-2代数系统的运算及其性质对给定的集合，我们可以相当任意地在这个集合上规定运算使它成为代数系统。但我们所研究的是其运算有某些性质的代数系统。在前面考察几个具体的代数系统时，已经涉及到我们所熟悉的运算的某些性质。这一节，主要讨论一般二元运算的一些性质。定义3-1-2.1设是定义在集合S上的二元运算，如果对于任意的x，y∈S，都有xy=yx，则称二元运算是可交换的或称运算满足交换率（commutativelaw）。例3-1-2.1设Z是整数集，，☆分别是Z上的二元运算，其定义为，对任意的a，ｂ∈Ｚ，a△ｂ＝ab－a－b，a☆ｂ＝ab—a＋b，问Ｚ上的运算△，☆分别是否可交换？解:因为a△b＝ab－a－ｂ=ba－ｂ－a＝ｂ△a对Z中任意元素a，b成立，所以运算△是可以交换的。又因为对Z中的数0，1，0☆1=0×1－0+1=1，1☆0=1×0—1+0=－1，145所以，0☆1≠1☆0，从而运算☆是不可交换的。定义3-1-2.2设﹡是定义在集合S上的二元运算，如果对于S上中的任意元素x，y，z都有，（x﹡y）﹡z=x﹡（y﹡z），则称二元运算﹡是可以结合的或称运算﹡满足结合律（associativelaw）。例3-1-2.2设Ｑ是有理数集合，○，﹡分别是Ｑ上的二元运算，其定义为，对于任意的a，b∈Ｑ，a○ｂ＝a，a○b＝a—2b，证明运算○是可结合的并说明运算﹡不满足结合律。证明：因为对任意的a，b，c∈Q，（a○b）○c=a○c=aa○(b○c)=a○b=a所以（a○b）○c=a○(b○c)，即得运算○是可以结合的。又因为对Q中的元0，1（0﹡0）﹡1=0﹡1=0—2=20﹡（0﹡1）=0﹡（—2）=0—2×（—2）=4所以，（0﹡0）﹡1≠0﹡（0﹡1），从而运算﹡不满足结合律。对于满足结合律的二元运算，在一个只有该种运算的表达式中，可以去掉标记运算顺序的括号。例如，实数集上的加法运算是可结合的，所以表达式（x+y）+（u+v）可简写为x+y+u+v。若＜S，○＞是代数系统，其中○是S上的二元运算且满足结合律，n是正整数，a∈S，那么，a○a○a……○a是S中的一个元素，称其为a的n次幂，记为an。关于a的幂，用数学归纳法不难证明以下公式am○an=am+n(am)n=amn其中m，n为正整数。定义3-1-2.3设○，﹡是定义在集合S上的两个二元运算，如果对于任意的ｘ，ｙ，ｚ∈S，都有x○（y﹡z）=（x○y）﹡（x○z）（y﹡z）○x=（y○x）﹡（z○x）则称运算○对运算﹡是可分配的，也称○对运算﹡满足（适合）分配律（distributivelaw）。146例3-1-2.3设集合A={0，1}，在A上定义两个二元运算○和﹡如表3-1-2.1和表3-1-2.2所示。试问运算﹡对运算○和运算○对运算﹡分别是否是可分配的？表3-1-2.1表3-1-2.2表3-1-2.2解：容易验证运算﹡对运算○是可分配的，但运算○对运算﹡是不满足分配律的。因1○（0﹡1）=1○1=1而（1○0）﹡（1○1）=1﹡0=0所以，○对﹡不满足分配律。定义3-1-2.4设○和﹡是集合S上的两个可交换的二元运算，如果对任意x,yS的都有x﹡(x○y)=xx○(x﹡y)=x则称运算○和﹡满足吸收律(absorptivelaw)。例3-1-2.4设P(S)是集合S上的幂集，集合的并“”和交“”是P(S)上的两个二元运算，验证运算和运算满足吸收律。解：对任意A，BP(S)，由集合相等及和的定义可得A(AB)=AA(AB)=A因此，和满足吸收律。定义3-1-2.5设﹡是集合S上的二元运算，如果对于任意的xS，都有x﹡x=x，则称运算﹡是等幂的，或称运算﹡满足幂等律(ildempotentlaw)。例3-1-2.5设Z是整数集，在Z上定义两个二元运算○和﹡，对于任意x,yZ，x○y=max(x，y)；x﹡y=min(x，y)验证运算﹡和○都是幂等的解：对于任意的xZ，有x○x=max(x，x)=x；x﹡x=min(x，x)=x因此运算﹡和运算○都是等幂的。定义3-1-2.6设○是定义在集合S上的一个二元运算，如果有一个元素Sel，使得对于任意元素xS都有xxel则称el为S中关于运算○的左幺元○01001110﹡01000101147(leftidentiy)；如果有一个元素Ser，使对于任意的元Sx都有xexr，则称re为S中关于运算○的右幺元（rightidentity）；如果S中有一个元素e，它既是左幺元又是右幺元，则称e是S中关于运算○的幺元(identity)。在整数集Z中加法的幺元是0，乘法的幺元是1；设S是集合，在S的幂集P(S)中，运算的幺元是，运算的幺元是S。对给定的集合和运算，有些存在幺元，有些不存在幺元。例如，R*是非零的实数的集合，○是R*上如下定义的二元运算，对任意的元素a,bR*，a○b=b则R*中不存右幺元；但对任意的aR*对所有的bR*都有a○b=b所以，R*的任一元素a都是运算○的左幺元，R*中的运算○有无穷多左幺元，没有右幺元和幺元。又如，在偶数集合中，普通乘法运算没有左幺元，右幺元和幺元。定理3-1-2.1设﹡是定义在集合S上的二元运算，le和re分别是S中关于运算﹡的左幺元和右幺元，则有el=er=e且e为S上关于运算﹡的唯一的幺元。证明：因为le和re分别是S中关于运算﹡的左幺元和右幺元，所以rrlleeee把el=er记为e，假设S中存在e1，则有e1=e﹡e1=e所以，e是S中关于运算﹡的唯一幺元。定义3-1-2.7设﹡是定义在集合S上的一个二元运算，如果有一个元lS，使得对于任意的元素xA都有l﹡x=l，则称l为S中关于运算﹡的左零元；如果有一元素rS，对于任意的元素xS都有x﹡r=r，则称r为S中关于运算﹡的右零元；如果S中有一元素，它既是左零元又是右零元，则称为S中关于运算﹡的零元(zero.element)。例如，整数集Z上普通乘法的零元是0，加法没有零元；S是集合，在S的148幂集P(S)中，运算的零元是S，运算的零元是，在非零的实数集R*上定义运算﹡，使对于任意的元素a,bR*，有a﹡b=a那么，R*的任何元素都是运算﹡的左零元，而R*中运算﹡没有右零元，也没有零元。定理3-1-2.2设是集合S上的二元运算，l和r分别是S中运算○左零元和右零元，则有l=r=且是S上关于运算○的唯一的零元。这个定理的证明与定理3-1-2.1类似。定理3-1-2.3设＜S,﹡＞是一个代数系统，其中﹡是S上的一个二元运算，且集合S中的元素个数大于1，若这个代数系统中存在幺元e和零元，则e。证明：(用反证法)若e=，那么对于任意的xS，必有x=e﹡x=﹡x==e,于是S中所有元素都是相同的，即S中只有一个元素，这与S中元素大于1矛盾。所以，e。定义3-1-2.8设＜S，﹡＞是代数系统,其中﹡是S上的二元运算，eS是S中运算﹡的幺元。对于S中任一元素x，如果有S中元素yl使yl﹡x=e，则称yl为x的左逆元；若有S中元素yr使x﹡yr=e，则称yr为x的右逆元；如果有S中的元素y，它既是x