离散数学 第五章 代数系统.ppt

第三编代数系统，代数历史悠久，早期代数研究对象具体，以方程根的求解和分布为研究中心。 但自20世纪初以来，代数的研究对象和研究方法发生了很大变化，形成了抽象代数学。 这一变化可以追溯到19世纪30年代法国数学家伽罗瓦(Galois )提出的群体概念，证明了四次以上一般代数方程的不可理解性，确立了具体数字系统代数方程不能用根解的判别标准和根解的数字系统代数方程的实例。 抽象代数学与以代数方程的根和根的分布状况为研究中心的古典代数不同，研究抽象代数系统。 处理后的对象和在其上定义的运算(操作)称为代数系统。 由于其研究对象的抽象性，即某一特定对象不作为研究对象，而是以具有某一共同性质的大班对象作为研究对象，因此其研究成果适用于该班对象的每一个，工作效果倍增。 它从高度的角度，对形式上非常不同的代数系统，除个性外，提取共性，用统一的方法表现，研究，推论，得出反映事物本质的结论，在这些系统中应用了广泛的高度抽象化。 具有代数系统运算的集合是抽象代数研究的主要对象，是离散数学的重要组成部分。 广泛应用于机器人、形式语言、逻辑电路设计、编码理论等研究，已成为计算机科学的重要数学工具。 因为抽象代数的内容很多，作为离散数学的内容之一，介绍了代数系统的基本概念和一些典型的代数系统。 第5章代数系统，5.1代数系统的基本概念，也称代数系统，代数结构，是具有运算的集合。 因此，在介绍之前，先导入集体演算的概念。 例如，通过将实数的集合r上的单独的数字a0映射到其倒数或者映射r上的单独的数字y，可以将这些映射称为集合r上的一元运算，而在集合r中，对任意两个个数据进行的通常的加法和乘法是集合r中的二元运算， 集合r上的任何三个元素x、y、z和ALGOL在算法语言中的表达式ifx=0thenyelsez，可以被认为映射至r上的每两个元素中的一个元素，其为集合r上的三元运算。5.1代数系统的基本概念，在上述的一些例子中，具有其运算结果在原集合r中的共同特征，具有此特征的运算被称为闭合运算。 相反，这种没有特征的运算并不封闭。 简单列举无阻塞计算的例子，有五角硬币和接受一元硬币的自动售货机，对应的商品为矿泉水(瓶)、可口可乐(瓶)、冰淇淋(杯)。 人们投入这些硬币中的任意两枚，自动售货机就会如表5-1所示供应该商品。 5.1代数系统的基本概念，表5-1，表左上角的符号*可以理解为二元运算的运算符。 本例的二元运算*是集合五角硬币，一元硬币上的无阻塞运算。 定义5.1、b为两个集合，如果f是从An到b的函数，则将f称为a上的n元运算。 其中n为自然数，且为被称为运算的要素的数目或阶数。 如果是ba的话，据说这个n元运算是关闭的。 5.1代数系统的基本概念是，n=1时，f称为单项运算，n=2时，f称为二项运算。 计算的例子很多。 例如，在数学逻辑中，否定是命题集合上的一元运算，合并解析是命题集合上的二元运算在集合论中，集合的补充是集合上的一元运算，交叉点是集合上的二元运算在实数算术中，加、减、乘、除都是二元运算。 有了集体运算的概念，就可以定义代数系统。5.1代数系统的基本概念，定义5.2是非空集合，fi是a上的ni元运算，I=1，2，m。 由a和f1、f2、fm组成的结构被称作代数结构或代数系统。 另外，定义为集合a的基数|A|、代数系的基数。 如果a是有限集合，代数系统就是有限代数系统，否则就是无限代数系统。 在某些情况下，考察两个以上的代数系统。 在此，关于是否是同一类型，参照下面的定义：5.1代数系统的基本概念，定义：5.3两个代数系统和，fi和gi(1im )具有相同的元数据时，这两个代数系统是同一类型。 这样，为了判定两个代数系统是否是同一类型，主要对其运算进行考察。 以下，举例说明上述各个概念。 5.1代数系统的基本概念，例如5.1s为非空集合，P(S )为其幂集合。 对于任意集合a，BP(S )的演算和定义是：ab=(a-b)(b-a)ab=ab是代数系，是封闭的代数系。 5.1代数系统的基本概念，例5.2是由有限文字构成的集合，被称为字母。 中由字母构成的秩序的集合称为上的列。 字符串中的字符数m称为该字符串的长度。 如果m=0，那么称为空序列，且由来表示。 上的列集合用*表示。 在*上定义并行或连接运算，用表示。 如，*，成为=。 一个代数系统。 设=*|时，也是代数系统。 5.1代数系统的基本概念，例5.3设置字长为8位的计算机，将定点加法、减法、乘法、除法、逻辑加法和逻辑乘法作为运算命令，分别用01、02、06表示。 在计算机上由28个不同的数字组成的集合s和用这个机器演算的命令构成代数系统。 5.1代数系统的基本概念，例5.4是整数集合，是普通的加法运算，代数系统。 显然，在该代数系统中，对于任何x、y、ZZ，“XYZ”具有“闭合性”；2)x y=y x (交换规则)；且“xy”z=x (yz ) (“耦合规则”)易于找到具有相同运算规则的若干代数系统，如表5-2中所示。 5.1代数系统的基本概念，表5-2，结束本节时，声明符号为代数系统，除非另有指定，运算符f1、f2、fm为二元运算。 如果需要，可以为a和f1、f2、fm设置不同的集合和运算符。 5.2演算及其性质，在以前讨论过一些具体的代数系统时，触及了我们熟悉的演算的一些性质。 以下着重研究一般二元运算的一些性质。 代数系统性质的考察方法不是研究个体结构，而是列举一组性质，为具有这些性质的代数系统导出可能的结论。 把被选择的性质看作公理，从这些公理中导出的有效结论，在满足这些公理的代数系统中也一定成立。 5.2由于运算及其性质，为了进行这样的讨论，不考虑特定的集合，对相关的运算不给予特定的意义。 这样的系统的集合或集合上的诸运算被认为是单纯的符号，更具体而言是抽象的对象。 因此，与之相对应的代数系统一般称为抽象代数。 对于那些特定的代数系统，只有这些基本性质中的特定性质。 5.2运算及其性质，性质1 :封闭性设定*是集合a中定义的二元运算，对于任意的x、ya，如果有x*yA即(x)(y)(x，yAx*yA )，则二元运算*关于a。 示例5.5a=x|x=2n，nn，乘法是否关闭？ 加法运算是否关闭？ 解：对于任意2r、2sa、r、sn，由于2r2s=2r sA，因此乘法关闭。 加法运算未关闭。 因为至少有2 22=6A。5.2运算及其性质；2 :交换律设定*是在集合a中定义的二进制运算，如果对于任何x、ya，有x*y=y*x，即(x)(y)(x，yAx*y=y*x )，则二进制运算*满足交换律或可以与其交换。 例如5.6所给出的，其中q是有理数的集合，任何a，bq都具有ab=a b-ab并且询问运算是否可以交换。 解：因为ab=ab-ab=b-ba=ba，所以运算可以交换。 5.2运算及其性质，性质3 :结合律设定*是在集合a中定义的二元运算，对于任何x，y，za，如果有(x*y)*z=x*(y*z )，即(x)(y)(z)(x，y，zA(x*y)*z=x*(y*z ) )，则二元运算*满足结合律或可以与*组合。 根据示例5.7，任何a，ba都有ab=b。 证明运算符“88个循环”是可组合的。 证明：在任意的a、b、c上分别写有(a11、可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡可卡特别是a1=a2=am=a的情况下，将a1a21122可卡可卡可卡可卡可卡可卡可卡am乘以a的m次方am的摘要定义如下所示：安装和aa。 对于mn，n表示正整数集合，(1) a1=a (2)由于其具有am1=am-a，5.2运算及其性质，因此利用归纳法证明指数定律并不困难： (1) am-80，an=amn(2)(am)n=amn其中，m，nN。 类似地，可定义代数系统中的负幂和负指数定律。 5.2运算及其性质，性质4 :分配律设定*、，或集合a中定义的两项运算，对于任意的x、y、za，如果x*(y可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可可5.2演算及其性质，例5.8给出，其中b= 0，1 。 表5-3包括运算*和- 1222222222222226522222222222222222222； 解：运算-可卡可卡可卡可卡可卡可卡可卡，但运算*在运算-可卡可卡可卡可卡可卡可卡可卡653集合的基数小时，特别是在2或3的情况下，代数系的运算多由该表给出优点简洁直观，一目了然。 性质5 :吸收定律是在集合a中定义的两个可交换的二元运算，对于任何x，ya，如果有x * (x-80，y)=x和x-80，x-80 (x*y)=x，即(x)(y)(x，yax * (x-80，xx-80，x-80，x * y )=x )，则为运算*和运算5.2演算及其性质，例如5.9给出的，其中n为自然数集合，*和，定义如下：对于任何a，bn，a*b=max(a，b )，a，ab=min(a，b )，实证试验，*和相互吸收。 证明：任何a，bna*(a111卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡653，5.2演算及其性质，性质6 :幂律设置*是在集合a中定义的二元演算，对于任何xa，x*x=x，即(x ) (xax1112000000000 ) 证明：和是等幂。 证明：对于任意的AP(S )，由于有AA=A和AA=A，所以运算和都满足等幂律。 对于均方律，很难证明下面的定理：5.2演算及其性质，定理5.1对于中-幂等元，对于任意正整数n，xn=x。 证明书留有练习。性质7 :单一复位*是集合a中定义的二进制运算，其中对于任何xa，如果存在元素ela，则对于任何xa，存在el*x=x，即(x)(xAel*x=x )，并且如果对于a的运算*，存在称为左假名的元素era，则对于任何xa，存在x*er=x，即(x ) (xa ) 若存在er=x )，则如果a个元素(被称为用于a的运算*的右侧要素) e是*的左侧要素与*的右侧要素，则e被称为a *的要素(x ) (xae * x=x * e=x )。 5.2演算及其性质，例如给出5.11，表5-4、表5-5和表5-6分别给出*不同定义的演算表，试图指出左还是元、右还是元。 解：在运算表5-4中，是左还是元、右还是元。 是吗？是吗？ 在运算表5-5中，不存在左或元，和是右或元。 在运算表5-6中，是左还是元，不存在右或元。 5.2给出运算及其性质，定理5.2，其中对于-左、右或维，el和er分别是el=er=e且维e唯一的。 证明： el和er分别是s中的- 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 如果相关联的被称为右零元素的a元素是*左零元素和*右零元素，则被称为a *的零元素，即(x ) (xa* x=x *=)。 5.2运算及其性质，例如5.12例5.11中，*如表5-4所定义，为*的零元*如表5-5所定义，与均为*的左零元*如表5-6所定义，为*的右零元。 由定理5.3给出，l和r对于- 80分别是左零元和右零元，l=r=，而零元是唯一的。 本定理的证明可以仿效定理5.2，让读者自己完成。 5.2演算及其性质，定理5.4给出|S|1。 如果，es，其中和e分别是-的零元和欧元，则e。 证明：使用反证法。 令=e，对于任意xs，对于x=e-80、x=- 80和x=e，因此s中的所有元素相同，它与包括在s中的多个元素不一致。 5.2个运算及其性质，性质9 :倒数给出代数系统，88个撒但是在a中定义的二元运算，其中，对于a的运算，e是- 12222222222222226，如果a中的元素y存在，使得对于a中的元素x，yx=e，则x的左倒数，称为y 如果xy=e成立，则x的被称为y的右逆元，即(y ) (yax-y=e )； 如果元素y为x的左反维，且