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

《离散数学代数结构部分-PPT.pptx》由会员分享，可在线阅读，更多相关《离散数学代数结构部分-PPT.pptx（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学代数结构部分本部分主要内容本部分主要内容二元运算及其性质。二元运算及其性质。二元运算二元运算中得特殊元素中得特殊元素幺元,零元,逆元。逆元。代数系统得定义及其性质。代数系统得定义及其性质。定定义义5、1 设设 为为集集合合,函函数数 称称为为 上得二元运算上得二元运算,简称为二元运算。简称为二元运算。5 5、1 1节节 二元运算及其性质二元运算及其性质在整数集合在整数集合 上上,对任意两个整数所进对任意两个整数所进行得普通加法和乘法行得普通加法和乘法,都就是集合上得二都就是集合上得二元运算。元运算。如何判断一个运算就是否为集合如何判断一个运算就是否为集合 上得上得二元运算二元运算 1唯

2、一性唯一性集合集合S中任意得两个元素都能进行这种运中任意得两个元素都能进行这种运算算,并且结果要就是唯一得。并且结果要就是唯一得。2封闭性封闭性 集合集合S中任意得两个元素运算得结果都就中任意得两个元素运算得结果都就是是属于属于S得得,就就是说就就是说S对该运算就是封闭得对该运算就是封闭得 例例5、1设Ax|x ,nN,问在集合A上通常得乘法运算就是否封闭,对加法运算呢?解:对于任意得 所以乘法运算就是封闭得。而对于加法运算就是不封闭得,因为至少有 定定义义5、2 设设*就就是是定定义义在在集集合合A上上得得二二元元运运算算,如如果果对对于于任任意意得得x,yA,都都有有x*yy*x,则则称称

3、该该二二元元运运算算*就就是是可可交换得。交换得。例例5、2 设设Q就是有理数集合就是有理数集合,*就是就是Q上得上得二元运算二元运算,对任意得对任意得a,bQ,a*ba+b-ab,问运算问运算*就是否可交换。就是否可交换。解解:因为因为a*ba+b-abb+a-bab*a,所以运算所以运算*就是可交换得。就是可交换得。定定义义5、1 设设 为为集集合合,函函数数 称称为为 上得二元运算上得二元运算,简称为二元运算。简称为二元运算。5 5、1 1节节 二元运算及其性质二元运算及其性质在整数集合在整数集合 上上,对任意两个整数所进对任意两个整数所进行得普通加法和乘法行得普通加法和乘法,都就是集合

4、上得二都就是集合上得二元运算。元运算。定定义义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上上得得二二元元运运算算,如如果果对对于于

5、任任意意得得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得幂集得幂集

6、,在在P(S)上定义得两个二元运算上定义得两个二元运算,集合得集合得“并并”运运算算和集合得和集合得“交交”运算运算,验证验证,就就是等幂得。是等幂得。解解:对于任意得对于任意得AP(S),有有AAA和和AAA,因此运算因此运算和和都满足等幂律。都满足等幂律。定定义义5、5 设。和*就是S上得两个二元运算,如果对任意得 有 例例5、5 在实数集R上,对于普通得乘法和加法有 即乘法对加法就是可分配得。大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点可以互相讨论下，但要小声点定定义义5、6 设设。和*就就是是定定

7、义义在在集集合合A上上得得两两个个可可交交换换二二元元运运算算,如如果果对对于于任任意得意得x,yA,都有都有则称则称。运算。运算和*满足吸收律满足吸收律 例例5、6 设集合设集合N为自然数全体为自然数全体,在在N上定上定义两个二元运算义两个二元运算*和和,对于任意对于任意 x,yN,有有x*ymax(x,y),xymin(x,y),验证运算验证运算*和和满足吸收律。满足吸收律。解解:对于任意对于任意a,bNa*(ab)max(a,min(a,b)aa(a*b)min(a,max(a,b)a 因此因此,*和和满足吸收律。满足吸收律。定义定义5、7 设*就是S上得二元运算,5 5、2 2节节 二

8、元运算中得特殊元素二元运算中得特殊元素1 1、幺元幺元在自然数集N上加法得幺元就是0,乘法得幺元就是1、对于给定得集合和运算有得存在幺 元,有得不存在幺元。定理定理5、1 设设*就是就是S上得二元运算,如果S中存在关于运算*得)幺元,则必就是唯一得。所以幺元就是唯一得。定理定理5 5、2 2 设设*就是就是S S上得二元运算,如果S S中既存在关于运算*得左幺元得左幺元 ,又又存在关于运算得右幺元得右幺元 则S中必存在关于运算*得幺元e并且 定义定义5、8 设*就是就是S上得二元运算,2 2、零元零元在在自自然然数数集N上普通乘法得零元就是0,而加法没有零元。定定理理5、3 设设*就就是是S上

9、得二元运算,如果S中存在(关于运算*得得)零零元元,则则必必就就是是唯唯一一得。得。所以零元就是唯一得。定定理理5、4 设设*就就是是S上得二元运算,如果S中既存在关于运算*得左零元 又存在关于运算*得右零元 定义定义5、9 设*就是就是S上得二元运算,2 2、逆元逆元 例例5、8 整数集整数集Z上关于加法得幺元就是上关于加法得幺元就是0,对任意得整数对任意得整数m,她关于加法得逆元就是她关于加法得逆元就是-m,因为因为定定理理5、5 设设*就就是是S上可结合得二元运算,e为幺幺元元,如如果果S中元素x存在(关于运算*)得逆元得逆元,则必就是惟一得。所以对于可结合得二元运算,逆元就是惟一得。定

10、定理理5、6 设设*就就是是S上可结合得二元运算,e为幺幺元元,如如果果S中元素x既存在关于运算*得左逆元 ,又存在关于运算*得右逆元 ,则 S中必存在x关于运算*得逆元并且 解解:*运算适合交换律、结合律和消去律,不适合幂等律。单位元就是a,没有零元,且 运算适合交换律、结合律和幂等律,不适合消去律。单位元就是a,零元就是b、只有a有逆元,运算不适合交换律,适合结合律和幂等律,不适合消去律。没有单位元,没有零元,没有可逆元素。定定义义5、10 设设S就就是是非非空空集集合合,由由S和S上若干个运算 构成得系统称为代数系统,记作 5 5、3 3节节 代数系统代数系统 代数系统也简称为代数。例如

11、,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 设 解解:第六章第六章 几个典型得代数系统几个典型得代数系统 本章讨论几类重要得代数结构本章讨论几类重要得代数结构:半群、群、环

12、、域、格与布尔代数半群、群、环、域、格与布尔代数 定义定义6、1 设 6 6、1 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之外都没有逆元,所以她仅就是含

13、幺半群而不就是群。中每个元素都有逆元即她得相反数,且运算满足交换律,所以她们就是交换群。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

14、得次数分别为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就是群 证明:必要性就是

15、显然得。例例6、11 设设 定义定义6、11 设 6 6、2 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

16、设设 定理定理6、16 设设 定义定义6、14 设设6 6、3 3 群得同态与同构群得同态与同构 例例6、13 设设 定义定义6、15 设设定理定理6、17 设 证明:略。定义定义6、16 设设定理定理6、18 (群同态基本定理群同态基本定理)设 定义定义6、17 设设6 6、4 4 循环群与置换群循环群与置换群 定理定理6、19 设 例例6、16例例6、17 设 定义定义6、18 设 例例6、18 设 定义定义6、19 设 例例6、19 4元置换定义定义6、20设 定理定理6、20定义定义6、21例例6、20 如图进行旋转,也可以围绕她得对称轴进行翻转,但经过旋转或翻转后仍要与原来得方格重合

17、(方格中得数字可以改变)。如果把每种旋转或翻转看作就是作用在 定义6、22 设 6 6、5 5 环和域环和域例例6、21(1)整数集 定理定理6、21 设设 2,3证明略。例例6、22 定义定义6、23 设 例例6、23(1)整数环整数环 例例6、22模6整数环 定义定义6、24 设 定义6、22 设 6 6、5 5 环和域环和域例例6、25 设设 定义定义6、25 设 6 6、6 6 格与布尔代数格与布尔代数 例例6、26 设设n就是正整数就是正整数 例例6、27(1)对于偏序集 定理定理6、22设设 定理定理6、23 设 定义定义6、26 设 定义定义6、27 设 例例6、28 设格 定义定义6、28 设 例例6、29 说明下图中得格就是否为分配格,为什么？