离散数学课件 第五章 代数结构_1

《离散数学课件 第五章 代数结构_1》由会员分享，可在线阅读，更多相关《离散数学课件 第五章 代数结构_1（52页珍藏版）》请在金锄头文库上搜索。

1、第五章 代数结构由于数学和其他科学的发展，人们需要对若干不是数的事物，用类似普通计算的方法进行相似的计算。如矩阵、向量等。研究代数系统的学科称为“近世代数”或“抽象代数”。 本章主要内容集合的概念1集合的表示方法2同态与同构6阿贝尔群与循环群4陪集与拉格朗日定理5集合的概念1集合的表示方法2群与子群3代数系统与性质1半群25-1 代数系统的引入定义定义5-1.15-1.1 如果 为An到B的一个函数，则称 为集合A上的n元运算（operater）。如果 BA， 则称 该n元运算在A上封闭。代数系统的定义定义5-1.2 一个非空集合A连同若干个定义在该集 合上的运算 f1,f2,fk 所组成的系

2、统称为一个代 数系统（代数结构），记为。代数结构由以下三个部分组成：非空集合S，称为代数结构的载体。载体S上的若干运算。一组刻划载体上各运算所满足性质的公理。代数系统常用一个多元序组来表示 。代数系统举例(1) R上的“+”、“”运算，构成一个代数系统R，+，；(2) (S)上的“”、“”、“”运算，构成代数系统(S),，称集合代数；(3) 含有n个命题变元的命题集合A与A上的“”、“”、“”运算，构成代数系统A，称之为命题代数。5-2 二元运算的性质定义 可以用 o 、*、 、 等符号表示二元 或一元运算,称为算符。定义5-2.1 设*是定义在集合A上的二元运算，如果 对于任意的x，yA，都

3、有x*yA，则称二元运算* 在A上是封闭的。二元运算的主要算律定义 设o为S上的二元运算,(1)如果对于任意的x,yS,有xoy=yox,则称运算o在S上满足交换律。(2)如果对于任意的x,y,zS 有(xoy)oz=xo(yoz),则称运算o在S上满足结合律。(3)如果对于任意的xS有xox=x,则称o运算在S上满足幂等律（等幂律）。二元运算的主要算律（续）定义 设o和*为S上两个不同的二元运算,(1)如果对于任意的x,y,zS有 (x*y)oz=(xoz)*(yoz)和zo(x*y)=(zox)*(zoy),则 称o运算对*运算满足分配律。(2)如果o和*都可交换,并且对于任意的x,yS

4、有xo(x*y)=x和x*(xoy)=x,则称o和*运算满足吸收 律。特殊元素1：幺元（单位元）定义5-2.7 设是二元代数系统， （1）若存在elA，使得对任意aA，都有el a = a， 则称el是A中关于运算“”的一个左幺元（左单位 元） （2）若存在erA，使得对任意aA，都有a er = a， 称er是A中关于运算“”的一个右幺元（右单位元 ） （3）若存在eA，对任意aA，都有a e = e a = a， 则称e是A中关于运算“”的一个幺元（单位元）幺元的性质定理5-2.1 设*是定义在集合A上的一个二元运算 ，且在A中有关于运算的左幺元el和右幺元er，则 el= er= e，且

5、A中的幺元是唯一的。证明：（先证左幺元el=右幺元er=e）el= el er = er= e（再证幺元e是唯一的）设还有一个幺元e A,则e = e e = e特殊元素2：零元定义5-2.8 设是一个二元代数系统， （1）若存在lA，使得对任意aA，都有 l a = l， 则称l是A中关于运算“”的一个左零元； （2）若存在rA，使得对任意aA，都有 a r = r， 则称r是A中关于运算“”的一个右零元。 （3）若存在A，使得对任意aA，都有 a = a =， 则称是A中关于运算“”的一个零元；零元的性质定理5-2.2 设*是定义在集合A上的一个二元运算 ，且在A中有关于运算的左零元l和右

6、零元r，则 l = r= ，且A中的零元是唯一的。证明：（先证左零元l=右零元r= ）l= l r = r= （再证零元是唯一的）设还有一个零元 A,则 = = 幺元、零元举例例：代数A=a，b，c， 。 用下表定义：。 abc aabb babc caba则 b是左么元，无右么元；a是右零元，b是右零元；无左零元;运算：既不满足结合律，也不满足交换律。幺元、零元举例（续）例:求出下列集合的幺元，零元。（1）I， I为整数集则幺元为1，零元为0（2）（A）, 对运算，是幺元， A是零元，对运算，A是幺元 ，是零元。（3）N，+有幺元0，无零元。幺元、零元性质定理5-2.3 如果代数结构有关于

7、运算 的零元 和幺元e ，且集合A中元素个数大于1，则e 。 证明：用反证法：设幺元e =零元 ，则对于任意xA ，必有x = e x = x = = e于是，推出A中所有元素都是相同的，矛盾。 特殊元素3：逆元定义5-2.9 设是二元代数系统，e是幺元， aA，若存在一个元素bA，（1）使得： b a = e，则称b是a的一个左逆元，记为al1；（2）使得： a b = e，则称b是a的一个右逆元，记为ar1。 （3）使得： a b = b a = e，则称a可逆，并称b是a的一个逆元，记为a1；逆元的性质注： 一般地，一个元素的左逆元不一定等于它的 右逆元。一个元素左、右逆元不一定同时存在

8、。甚 至一个元素的左（右）逆元不一定是唯一的。定理 设*为S上可结合的二元运算,e为该运算的 单位元,对于xS如果存在左逆元yl和右逆元yr,则 有yl = yr= y，且y是x的唯一的逆元。 证明： 因为 yl*x = e ， x*yr = e， 故yl = yl*e = yl*(x*yr) = (yl*x)*yr = e*yr = yr令yl = yr = y,则y是x的逆元。设yS也是x的逆元,则y= y *e = y *(x*y) = (y*x)*y = e*y = y所以y是x唯一的逆元。通过运算表观察二元运算的性质1）封闭性：表中的每个元素都属于A。 2）可交换性：运算表关于主对角

9、线是对称的。 3）等幂性：运算表的主对角线上的每一元素与它 所在行（列）的表头元素相同。 4）A中关于运算具有零元：该元素所对应的行和 列中的元素都与该元素相同。 5）A中关于运算具有幺元：该元素所对应的行和 列依次与运算表的首行和首列相一致。 6）A中关于运算具有幺元，a和b互逆：位于a行b 列的元素以及b行a列的元素都是幺元。例：P182 例题9，10，11，12例：设X=e,a,b,c,d，*是X上的二元运算，*的运 算表如下。从本例还可以看到a的逆元也是c, d。运算*满足可交换性，但不满足等幂性。*eabcd eeabcd aaaaee bbaaee cceecc ddeecc从表中

10、可知， 是代数系统，e是关于* 的幺元。X中无零元。 表中 b*c=c*b=e； b*d=d*b=e，故c和d均 为b的逆元，即b的逆元 不唯一。原因在于运算 *不满足结合律。练习：指出下面运算的性质，并求出幺元,零元， 可逆元素的逆元。1、在Q集合上， x,y Q，x*y=x+y-xy2、在I+集合上, x,y I+ ，x*y=lcm(x,y)1、满足交换律、结合律，不满足幂等律，幺元为0 ，零元为1，x的逆元x-1=x/(x-1) (x1)2、满足交换律、结合律、幂等律，幺元为1，无零 元，只有1有逆元，其逆元为1。5-3 半群定义5-3.1 如果集合S上的二元运算是封闭的， 则称代数系统

11、为广群。定义5-3.2 如果集合S上的二元运算 是封闭的 并且满足结合律，则称代数结构为半群。 例：P186例题1，例题2子半群定理5-3.1 设为一半群, BS且在B上封 闭，那么也是一个半群，称为的子半 群。例：乘法运算在某些集合上构成的子半群 。含幺半群（独异点）定义5-3.3 设代数结构为半群，若含 有关于 运算的幺元,则称它为独异点，或含幺半 群，有时也记为。独异点的性质运算表中任两行两列不相同定理5-3.3 设是一个独异点,则在关于运 算的运算表中任何两行或两列都是不相同的。例:设I是整数集合，m是任意正整数， Zm是由模m 的同余类组成的同余类集，在Zm上定义两个二元运算+m和m

12、分别如下：对于任意的i，jZm，有i +mj=(i+j)(mod m)imj=(ij)(mod m)试证明在这两个二元运算的运算表中任何两行 或两列都是不相同的。证明思路：1、证明运算的封闭性；Zm 0, 1, 2, , m1, 任意x,yZm, 显然x +myZm, x myZm,所以+m、m运算封闭性成立。 2、证明运算满足结合律；任意x,y,z Zm, 有 (xmy)mz(xy+z)(mod m)xm(ymz) 所以+m满足结合律，同理可证m满足结合律。 3、显然，0、1分别为+m和m的幺元。综上所述， 和 都是独异 点。由定理5-3.3可知，这两个运算的运算表中任 两行或两列都不相等。

13、独异点的性质定理5-3.4 设是一个独异点,如果对于任 意a,bS ，且a,b均有逆元，则a) (a-1)-1=ab) ab 有逆元，且(ab)-1 =b-1 a-1 。 证明: a)因a-1和a为互为逆元，直接得到结论。b)必须证明两种情况：(ab)(b-1a-1) = e 和 (b-1a-1)(ab) = e利用结合律容易得出。子独异点定义5-3.3 设代数结构为半群，若BS且 在B上封闭， B含有关于 运算的幺元,那么 称为子独异点，或子幺半群。独异点举例设是一个非空有限集合，称为字母表，由 中有限个字母组成的有序集合（即字符串）称 为上的一个字，串中的字母个数m称为字长， m=0时，称

14、为空字，即为单位元，记为e。表示 上的字的集合，上的连接运算定义为， ，=，则是一个代数 系统，而且是一个独异点, 是在计算机科学中自 动机理论及形式语言中最基本的结构。的任一 子集就称为语言。 5-4 群与子群定义5-4.1 称代数结构为群(groups),如果（1） 中运算是封闭的；（2） 中运算是可结合的；（3） 中有幺元e；（4） 中每一元素x都有逆元x-1。群举例例题1 R=0,60,120,180,240,300, *是R上的二元运算，a*b表示先旋转a再旋转b的角 度，并规定旋转360等于原来的状态。运算表如 表5-4.1所示。验证代数结构为群。解题思路： 需证明：（1）运算*封

15、闭；（2）运算*是可 结合的；（3）有幺元0;（4）每一元素x都有逆 元x-1。典型的群1、 2、 3、,其中Z6 =0，1，2，3，4，5，单位 元是0；1、5互为逆元，2、4互为逆元，3的逆元为 3，0的逆元为0。 注：不是群，其不存在幺元，且每个元素也 不存在逆元。而存在幺元，除0以外，均不存在逆元， 故其只是半群。代数结构总图代数结构总图封闭广群半群独异点群结合含幺可逆广 群半 群独异点群有限群与无限群定义5-4.2 设 为一群。若G为无限集，则 称为无限群；否则，称 为有限群，此 时G的元素个数称为G的阶,记为|G|。有限群举例Klein四元群*eabceeabcaaecbbbceaccbaeKlein四元群: e为G中的单位元；运算是可交换的；G中任何元素的逆元就是 它自己；在a,b,c三个元素中,任 何两个元素运算的结果都等 于另一个元素。群的性质1