离散数学代数结构部分.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三部分 代数结构,.,1,第五章 代数系统,代数结构又称为代数系统，简称代数，是抽象代数的主要研究对象。,代数系统的种类很多，它们在计算机科学的自动机理论、编码理论、形式语言、时序线路、开关线路计数问题以及计算机网络纠错码的纠错能力判断、密码学、计算机理论科学等方面有着非常广泛的应用,。,.,2,本部分主要内容,二元运算及其性质。,二元运算,中的特殊元素,幺元，零元，,逆元。,代数系统的定义及其性质。,.,3,定义,5.1,设 为集合，函数 称为 上的二元运算，简称为二元运算。,5.1,节,二元运算及其性质,在整数集合 上，对任意两个整数所进,行的普通加法和乘法，都是集合上的二,元运算。,.,4,如何判断一个运算是否为集合 上的,二元运算,唯一性,集合,S,中任意的两个元素都能进行这种运,算，并且结果要是唯一的。,封闭性,集合,S,中任意的两个元素运算的结果都是,属于,S,的，就是说,S,对该运算是封闭的,.,5,例,5.1,设,A,x|x,，,nN,，问在集合,A,上通常的乘法运算是否封闭，对加法运算呢,?,解：对于任意的,所以乘法运算是封闭的。,而对于加法运算是不封闭的,因为至少有,.,6,定义,5.2,设*是定义在集合,A,上的二元运算，如果对于任意的,x,yA,，都有,x*y,y*x,，则称该二元运算*是可交换的。,例,5.2,设,Q,是有理数集合，*是,Q,上的二元运算，对任意的,a,，,bQ,，,a*b,a+b-ab,，问运算*是否可交换。,解：因为,a*b,a+b-ab,b+a-ba,b*a,，,所以运算*是可交换的。,.,7,定义,5.1,设 为集合，函数 称为 上的二元运算，简称为二元运算。,5.1,节,二元运算及其性质,在整数集合 上，对任意两个整数所进,行的普通加法和乘法，都是集合上的二,元运算。,.,8,定义,5.2,设*是定义在集合,A,上的二元运算，如果对于任意的,x,yA,，都有,x*y,y*x,，则称该二元运算*是可交换的。,例,5.2,设,Q,是有理数集合，*是,Q,上的二元运算，对任意的,a,，,bQ,，,a*b,a+b-ab,，问运算*是否可交换。,解：因为,a*b,a+b-ab,b+a-ba,b*a,，,所以运算*是可交换的。,.,9,定义,5.3,设*是定义在集合,A,上的二元运算，如果对于任意的,x,，,y,，,zA,，都有,(x*y)*z,x*(y*z),，则称该二元运算*是可结合的，或者说运算*在,A,上适合结合律。,例,5.3,设,A=Z,“+”,是整数中的加法：则,“+”,在,Z,中适合结合律。,“,。”是整数中的减法：则特取,而,运算“,。,”不满足结合律,.,10,定义,5.4,设*是定义在集合,A,上的一个二元运算，如果对于任意的,xA,，都有,x*x,x,，则称运算*是等幂的。,例,5.4,设,P(S),是集合,S,的幂集，在,P(S),上定义的两个二元运算，集合的“并”运算和集合的“交”运算，验证，是等幂的。,解：对于任意的,AP(S),，,有,AA,A,和,AA,A,，,因此运算和都满足等幂律。,.,11,定义,5.5,设,。,和*是,S,上的两个二元运算，如果对任意的 有,例,5.5,在实数集,R,上，,对于普通的乘法和加法有,即乘法对加法是可分配的。,.,12,定义,5.6,设,。,和*,是定义在集合,A,上的两个可交换二元运算，如果对于任意的,x,，,yA,，都有,则称,。运算,和*,满足吸收律,例,5.6,设集合,N,为自然数全体，在,N,上定义两个二元运算*和，对于任意,x,，,yN,，有,x*y,max(x,，,y),，,xy,min(x,，,y),，,验证运算*和满足吸收律。,.,13,解：对于任意,a,，,bN,a*(ab),max(a,，,min(a,，,b),a,a(a*b),min(a,，,max(a,，,b),a,因此，*和满足吸收律。,.,14,定义,5.7,设*是,S,上的二元运算，,5.2,节,二元运算中的特殊元素,1.,幺元,.,15,在自然数集,N,上加法的幺元是,0,，乘法的幺元是,1.,对于给定的集合和运算有的存在幺 元，有的不存在幺元。,.,16,.,17,定理,5.1,设*是,S,上的二元运算，,如果,S,中存在关于运算,*,的）幺元，,则必是唯一的。,所以幺元是唯一的。,.,18,定理,5.2,设*是,S,上的二元运算，,如果,S,中既存在关于运算,*的左幺元,，,又,存在关于运算,的右幺元,则,S,中必存在关于运算,*,的幺元,e,并且,.,19,定义,5.8,设*,是,S,上的二元运算，,2.,零元,.,20,在自然数,集,N,上普通乘法的零元是,0,，而加法没有零元。,.,21,定理,5.3,设*是,S,上的二元运算，如果,S,中存在（关于运算,*的）零元，则必是唯一的。,所以零元是唯一的。,.,22,定理,5.4,设*是,S,上的二元运算，如果,S,中既存在关于运算,*,的左零元 又存在关于运算,*,的右零元,.,23,定义,5.9,设*,是,S,上的二元运算，,2.,逆元,.,24,例,5.8,整数集,Z,上关于加法的幺元是,0,，对任意的整数,m,，它关于加法的逆元是,-m,因为,.,25,定理,5.5,设*是,S,上可结合的二元运算，,e,为,幺元,如果,S,中元素,x,存在,（,关于运算,*,）的逆元，,则必是惟一的。,所以对于可结合的二元运算，逆元是惟一的。,.,26,定理,5.6,设*是,S,上可结合的二元运算，,e,为,幺元,如果,S,中元素,x,既存在关于运算,*,的左逆元 ，又存在关于运算,*,的右逆元 ，则,S,中必存在,x,关于运算,*,的逆元并且,.,27,解：,*运算适合交换律、结合律和消去律，不适合幂等律。单位元是,a,，没有零元，且,运算适合交换律、结合律和幂等律，不适合消去律。单位元是,a,，零元是,b.,只有,a,有逆元，,运算不适合交换律，适合结合律和幂等律，不适合消去律。没有单位元，没有零元，没有可逆元素。,.,28,定义,5.10,设,S,是非空集合，由,S,和,S,上若干个运算 构成的系统称为代数系统，记作,5.3,节 代数系统,代数系统也简称为代数。,例如，,R,是实数集，对于普通的加法和剩法运算，,M,是,n,阶方阵构成的集合，对于矩阵的加法和剩法运算，,.,29,定义,5.11,设,都是封闭的，且,B,和,S,含有相同的代数常数，,则称,.,30,定义,5.12,设,.,31,例,5.11,设,.,32,定义,5.13,设,定义,5.14,设,.,33,.,34,例,5.14,表示求两个数的最小公倍数的运算。则,解：,零元是不存在的，,只有惟一的逆元。,.,35,例,5.15,在有理数集,Q,上定义二元运算*,解,：,.,36,.,37,例,5.16,设有集合,解,：,讨论这,5,个集合对普通的乘法和加法运算是否封闭。,.,38,例,5.17,设,解,：,.,39,第六章 几个典型的代数系统,本章讨论几类重要的代数结构：,半群、群、环、域、格与布尔代数,.,40,定义,6.1,设,6.1,节,半群与群,是可结合的即：,.,41,定义,6.2,若半群,例,6.1,（,1,）普通加法是,（,2,）普通乘法是,N,Z,Q,和,R,上的二元运算，满足 结合律且有幺元,1,.,42,.,43,定义,6.3,设,例,6.2,定义,6.3,设,.,44,定义,6.4,设,定义,6.5,设,.,45,例,6.3,设,证明,G,关于矩阵乘法构成一个群,故,G,关于矩阵乘法是,Z,上的代数运算，矩阵乘法满足结合律，故,G,关于矩阵乘法构成半群,，,在,G,中每个矩阵的逆元都是自己，,所以,G,关于矩阵乘法构成一个群。,.,46,定义,6.6,若群,例,6.4,（,1,）在 中除,0,之外都没有逆元，所以它仅是含幺半群而不是群。,中每个元素都有逆元即它的相反数，且运算满足交换律，所以它们是交换群。,0,没有逆元，所以它们仅是有么半群而不是群。,.,47,.,48,例,6.5,设,G=e,a,b,c,。为,G,上的二元运算，它由以下运算表给出。不难证明,G,是一个群，称该群为,Klein,四元群。,.,49,定义,6.7,设,.,50,例,6.6,在群,解：,.,51,定理,6.1,设,证明：略。,.,52,定义,6.8,设,.,53,定义,6.9,.,54,例,6.7,对于集合,列出其运算表如下表,从表中可以看出，运算满足封闭性，满足结合律和交换律，,0,是单位元，每个元都有逆元，,这个群的阶数是,6,，元素,0,，,1,，,2,，,3,，,4,，,5,的次数分别为,1,，,6,，,3,，,2,，,3,，,6,。,.,55,定理,6.2,设,下面证明唯一性,从而唯一性得证。,.,56,例,6.8,设,.,57,定理,6.3,.,58,定理,6.4,设,.,59,.,60,定理,6.5 G,为有限群，则,G,的运算表中的每一行（每一列）都是,G,中元素的一个置换，且不同的行（或列）的置换都不相同。,定义,6.10,设,.,61,例,6.9,例,6.10,群,.,62,定理,6.6,(,子群判定定理,1),设,H,是群。,证明：必要性是显然的。,.,63,定理,6.7,(,子群判定定理,2),设,H,是群,证明：必要性,充分性证明：,.,64,2025/5/13 周二,65,定理,6.8,(,子群判定定理,3),设,H,是群,证明：必要性是显然的。,.,66,例,6.11,设,.,67,定义,6.11,设,6.2,节,陪集与拉格朗日定理,例,6.12,设,解：,H,的右陪集为,.,68,定理,6.9,设,H,是群,.,69,定理,6.10,设,.,70,.,71,定理,6.11,设,证明：略。,推论,6.1,.,72,定理,6.12,设,.,73,定理,6.13,设,.,74,定义,6.12,群,定理,6.14,（拉格朗日定理）,设,即子群的阶数一定是群的阶数的因子。,根据定理,6.11,的推论有,.,75,推论,6.2,设,推论,6.3,设,根据定理,6.11,的推论有,.,76,定义,6.13,设,任何群,G,都有正规子群，因为,G,的两个平凡子群,.,77,定理,6.15,设,证明：略。,.,78,例,6.13,设,.,79,例,6.14,设,.,80,定理,6.16,设,.,81,定义,6.14,设,6.3,群的同态与同构,.,82,例,6.13,设,.,83,定义,6.15,设,.,84,定理,6.17,设,证明：略。,.,85,定义,6.16,设,.,86,定理,6.18,（群同态基本定理）,设,.,87,定义,6.17,设,6.4,循环群与置换群,.,88,.,89,定理,6.19,设,.,90,例,6.16,例,6.17,设,.,91,定义,6.18,设,例,6.18,设,.,92,.,93,定义,6.19,设,例,6.19,4,元置换,.,94,定义,6.20,设,.,95,定理,6.20,.,96,定义,6.21,例,6.20,如图,进行旋转，也可以围绕它的对称轴进行翻转，但,经过旋转或翻转后仍要与原来的方格重合（方格,中的数字可以改变）。如果把每种旋转或翻转看,作是作用在,.,97,.,98,.,99,.,100,定义,6.22,设,6.5,环和域,.,101,例,6.21,（,1,）整数集,.,102,定理,6.21,设,2,3,证明略。,.,103,例,6.22,.,104,定义,6.23,设,.,105,例,6.23,（,1,）整数环,.,106,例,6.22,模,6,整数环,.,107,定义,6.24,设,.,108,定义,6.22,设,6.5,环和域,.,109,例,6.25,设,.,110,.,111,.,112,定义,6.25,设,6.6,格与布尔代数,.,113,例,6.26,设,n,是正整数,.,114,例,6.27,（,1,）对于,偏序集,.,115,.,116,定理,6.22,设,.,117,定理,6.23,设,.,118,定义,6.26,设,定义,6.27,设,.,119,例,6.28,设格,.,120,定义,6.28,设,.,121,例,6.29,说明下图中的格是否为分配格，,为什么？,.,122,.,123,定义,6.29,设,.,124,定义,6.30,设,例,6.30,例,6.31,.,125,定义,6.31,设,.,126,定义,6.32,设,定义,6.33,如果一个格是有补分配格，则称它为布尔格或布尔代数。,.,127,2025/5/13 周二,128,