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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学代数结构部分,本部分主要内容,二元运算及其性质。,二元运算,中得特殊元素,幺元,零元,逆元。,代数系统得定义及其性质。,定义5、1 设 为集合,函数 称为 上得二元运算,简称为二元运算。,5、1节,二元运算及其性质,在整数集合 上,对任意两个整数所进,行得普通加法和乘法,都就是集合上得二,元运算。,如何判断一个运算就是否为集合 上得,二元运算,唯一性,集合S中任意得两个元素都能进行这种运,算,并且结果要就是唯一得。,封闭性,集合S中任意得两个元素运算得结果都就是,属于S得,就就是说S对该运算就是封闭得,例5、1,设Ax|x ,nN,问在集合A上通常得乘法运算就是否封闭,对加法运算呢?,解:对于任意得,所以乘法运算就是封闭得。,而对于加法运算就是不封闭得,因为至少有,定义5、2 设*就是定义在集合A上得二元运算,如果对于任意得x,yA,都有x*yy*x,则称该二元运算*就是可交换得。,例5、2 设Q就是有理数集合,*就是Q上得二元运算,对任意得a,bQ,a*ba+b-ab,问运算*就是否可交换。,解:因为,a*ba+b-abb+a-bab*a,所以运算*就是可交换得。,定义5、1 设 为集合,函数 称为 上得二元运算,简称为二元运算。,5、1节,二元运算及其性质,在整数集合 上,对任意两个整数所进,行得普通加法和乘法,都就是集合上得二,元运算。,定义5、2 设*就是定义在集合A上得二元运算,如果对于任意得x,yA,都有x*yy*x,则称该二元运算*就是可交换得。,例5、2 设Q就是有理数集合,*就是Q上得二元运算,对任意得a,bQ,a*ba+b-ab,问运算*就是否可交换。,解:因为,a*ba+b-abb+a-bab*a,所以运算*就是可交换得。,定义5、3 设*就是定义在集合A上得二元运算,如果对于任意得x,y,zA,都有(x*y)*zx*(y*z),则称该二元运算*就是可结合得,或者说运算*在A上适合结合律。,例5、3 设A=Z,“+”就是整数中得加法:则,“+”在Z中适合结合律。,“,。”就是整数中得减法:则特取,而,运算“,。,”不满足结合律,定义5、4 设*就是定义在集合A上得一个二元运算,如果对于任意得xA,都有x*xx,则称运算*就是等幂得。,例5、4 设P(S)就是集合S得幂集,在P(S)上定义得两个二元运算,集合得“并”运算和集合得“交”运算,验证,就是等幂得。,解:对于任意得AP(S),有AAA和AAA,因此运算和都满足等幂律。,定义5、5,设,。,和*就是S上得两个二元运算,如果对任意得 有,例5、5,在实数集R上,对于普通得乘法和加法有,即乘法对加法就是可分配得。,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,定义5、6 设,。,和*,就是定义在集合A上得两个可交换二元运算,如果对于任意得x,yA,都有,则称,。运算,和*,满足吸收律,例5、6 设集合N为自然数全体,在N上定义两个二元运算*和,对于任意,x,yN,有x*ymax(x,y),xymin(x,y),验证运算*和满足吸收律。,解:对于任意a,bN,a*(ab)max(a,min(a,b)a,a(a*b)min(a,max(a,b)a,因此,*和满足吸收律。,定义5、7,设*就是S上得二元运算,5、2节 二元运算中得特殊元素,1、幺元,在自然数集N上加法得幺元就是0,乘法得幺元就是1、,对于给定得集合和运算有得存在幺 元,有得不存在幺元。,定理5、1 设*就是S,上得二元运算,如果S中存在关于运算,*,得)幺元,则必就是唯一得。,所以幺元就是唯一得。,定理5、2 设*就是S,上得二元运算,如果,S,中既存在关于运算,*得左幺元,又,存在关于运算,得右幺元,则S中必存在关于运算,*,得幺元e并且,定义5、8,设*,就是,S上得二元运算,2、零元,在自然数,集N上普通乘法得零元就是0,而加法没有零元。,定理5、3 设*就是S,上得二元运算,如果,S,中存在(关于运算,*得)零元,则必就是唯一得。,所以零元就是唯一得。,定理5、4 设*就是S,上得二元运算,如果,S,中既存在关于运算,*,得左零元 又存在关于运算,*,得右零元,定义5、9,设*,就是,S上得二元运算,2、逆元,例5、8 整数集Z上关于加法得幺元就是0,对任意得整数m,她关于加法得逆元就是-m,因为,定理5、5 设*就是S,上可结合得二元运算,e为,幺元,如果S,中元素x存在,(,关于运算,*,)得逆元,则必就是惟一得。,所以对于可结合得二元运算,逆元就是惟一得。,定理5、6 设*就是S,上可结合得二元运算,e为,幺元,如果S,中元素x既存在关于运算,*,得左逆元 ,又存在关于运算,*,得右逆元 ,则,S,中必存在x关于运算,*,得逆元并且,解:,*运算适合交换律、结合律和消去律,不适合幂等律。单位元就是a,没有零元,且,运算适合交换律、结合律和幂等律,不适合消去律。单位元就是a,零元就是b、只有a有逆元,运算不适合交换律,适合结合律和幂等律,不适合消去律。没有单位元,没有零元,没有可逆元素。,定义5、10 设,S,就是非空集合,由,S和S上若干个运算 构成得系统称为代数系统,记作,5、3节 代数系统,代数系统也简称为代数。,例如,R就是实数集,对于普通得加法和剩法运算,M就是n阶方阵构成得集合,对于矩阵得加法和剩法运算,定义5、11,设,都就是封闭得,且B和S含有相同得代数常数,则称,定义5、12 设,例5、11,设,定义5、13 设,定义5、14 设,例5、14,表示求两个数得最小公倍数得运算。则,解:,零元就是不存在得,只有惟一得逆元。,例5、15 在有理数集Q上定义二元运算*,解,:,例5、16 设有集合,解,:,讨论这5个集合对普通得乘法和加法运算就是否封闭。,例5、17 设,解,:,第六章 几个典型得代数系统,本章讨论几类重要得代数结构:,半群、群、环、域、格与布尔代数,定义6、1,设,6、1节,半群与群,就是可结合得即:,定义6、2,若半群,例6、1(1)普通加法就是,(2)普通乘法就是N,Z,Q和R上得二元运算,满足 结合律且有幺元1,定义6、3 设,例6、2,定义6、3 设,定义6、4 设,定义6、5 设,例6、3 设,证明G关于矩阵乘法构成一个群、,故G关于矩阵乘法就是Z上得代数运算,矩阵乘法满足结合律,故G关于矩阵乘法构成半群,在G中每个矩阵得逆元都就是自己,所以 G关于矩阵乘法构成一个群。,定义6、6 若群,例6、4,(1)在 中除0之外都没有逆元,所以她仅就是含幺半群而不就是群。,中每个元素都有逆元即她得相反数,且运算满足交换律,所以她们就是交换群。,0没有逆元,所以她们仅就是有么半群而不就是群。,例6、5设G=e,a,b,c,。为G上得二元运算,她由以下运算表给出。不难证明G就是一个群,称该群为Klein四元群。,定义6、7 设,例6、6,在群,解:,定理6、1,设,证明:略。,定义6、8 设,定义6、9,例6、7,对于集合,列出其运算表如下表,从表中可以看出,运算满足封闭性,满足结合律和交换律,0就是单位元,每个元都有逆元,这个群得阶数就是6,元素0,1,2,3,4,5得次数分别为1,6,3,2,3,6。,定理6、2 设,下面证明唯一性,从而唯一性得证。,例6、8 设,定理6、3,定理6、4 设,定理6、5 G为有限群,则G得运算表中得每一行(每一列)都就是G中元素得一个置换,且不同得行(或列)得置换都不相同。,定义6、10 设,例6、9,例6、10 群,定理6、6,(子群判定定理1)设H就是群。,证明:必要性就是显然得。,定理6、7,(子群判定定理2)设H就是群,证明:必要性,充分性证明:,定理6、8,(子群判定定理3)设H就是群,证明:必要性就是显然得。,例6、11 设,定义6、11,设,6、2节,陪集与拉格朗日定理,例6、12,设,解:H得右陪集为,定理6、9,设H就是群,定理6、10,设,定理6、11,设,证明:略。,推论6、1,定理6、12,设,定理6、13,设,定义6、12,群,定理6、14(拉格朗日定理),设,即子群得阶数一定就是群得阶数得因子。,根据定理6、11得推论有,推论6、2,设,推论6、3,设,根据定理6、11得推论有,定义6、13,设,任何群G都有正规子群,因为G得两个平凡子群,定理6、15 设,证明:略。,例6、13 设,例6、14 设,定理6、16 设,定义6、14 设,6、3 群得同态与同构,例6、13 设,定义6、15 设,定理6、17,设,证明:略。,定义6、16 设,定理6、18 (群同态基本定理),设,定义6、17 设,6、4 循环群与置换群,定理6、19,设,例6、16,例6、17,设,定义6、18,设,例6、18,设,定义6、19,设,例6、19,4元置换,定义6、20,设,定理6、20,定义6、21,例6、20,如图,进行旋转,也可以围绕她得对称轴进行翻转,但,经过旋转或翻转后仍要与原来得方格重合(方格,中得数字可以改变)。如果把每种旋转或翻转看,作就是作用在,定义6、22 设,6、5 环和域,例6、21,(1)整数集,定理6、21 设,2,3证明略。,例6、22,定义6、23,设,例6、23(1)整数环,例6、22,模6整数环,定义6、24,设,定义6、22 设,6、5 环和域,例6、25 设,定义6、25,设,6、6 格与布尔代数,例6、26 设n就是正整数,例6、27,(1)对于,偏序集,定理6、22设,定理6、23,设,定义6、26,设,定义6、27,设,例6、28,设格,定义6、28,设,例,6、29 说明下图中得格就是否为分配格,为什么？,