离散数学代数系统省公共课一等奖全国赛课获奖课件.pptx

离散数学离散数学(二二)第一讲第一讲计算机学院计算机学院:焦晓鹏焦晓鹏.秋秋第1页个人信息(Personal Information)Instructor:焦晓鹏，副教授，工学博士 Bs.()Xidian University PhD()Xidian University RF(-)National University of SingaporeResearch Direction:新型差错控制编码技术 高密度存放系统信号处理和编码技术 （高密度磁盘和闪存flash memory）数字喷泉码和网络编码技术Laboratory:计算学院计算机科学系Office:主楼I-区,402房间 Tel:[phone] Email:第2页关于学习和考试(1)摆正学习和考试关系摆正学习和考试关系 考试是学习期间副产品考试是学习期间副产品 以考试为目标学习是对知识耍流氓以考试为目标学习是对知识耍流氓(2)勤奋勤奋!诸葛亮诸葛亮 诫子书诫子书 夫君子之行，静以修身，俭以养德。非淡泊无以明志，夫君子之行，静以修身，俭以养德。非淡泊无以明志，非宁静无以致远。夫学须静也，才须学也。非学无以广才，非宁静无以致远。夫学须静也，才须学也。非学无以广才，非志无以成学。韬慢则不能励精，险躁则不能治性。年与时非志无以成学。韬慢则不能励精，险躁则不能治性。年与时驰，意与岁去，遂成枯落，多不接世。悲守穷庐，将复何及驰，意与岁去，遂成枯落，多不接世。悲守穷庐，将复何及？第3页名人话数学 数学是科学之王。高斯高斯 数学支配着宇宙。毕达哥拉斯毕达哥拉斯 自然界书是用数学语言写成。伽利略伽利略 数学是一切知识中最高形式。柏拉图柏拉图 数学是打开科学大门钥匙。培根培根 一门科学，只有当它成功地利用数课时，才能到达真正完善地步。马克思马克思 一个国家只有数学蓬勃发展，才能展现它国力强大。数学发展和至善和国家繁荣兴盛亲密相关。拿破仑拿破仑第4页离散数学(Discrete Mathematics)读史使人明智,读诗使人聪慧,演算使人精密,哲理使人深刻,伦理学使人有涵养,逻辑修辞使人善辩。培根培根 数学史书籍数学史书籍:美 莫里斯.克莱茵 著 英 斯科特 著 广西师范大学出版社 没有一个数学思想,以它被发觉时那个样子公开发表出来。一个问题被处理后,对应地发展为一个形式化技巧,结果把求解过程丢在一边,使炽热创造变成冰凉漂亮炽热创造变成冰凉漂亮。弗赖登塔尔弗赖登塔尔:荷兰著名数学教育家第5页离散数学离散数学课程学程学习特点及方法特点及方法特点特点:强调：逻辑性、抽象性；重视：概念、方法与应用 方法方法:1该课程概念名词多，定义多，公式多，要求记忆准确。2认真/仔细做好课堂笔记。3完成大量习题。考评考评:平时成绩平时成绩15%15%期末考试期末考试85%85%第6页离散数学教材离散数学教材教材：教材：离散数学离散数学 方世昌编著方世昌编著 西安电子科技大学出版社西安电子科技大学出版社.8.8第7页离散数学教材离散数学教材旧版教材：旧版教材：离散数学离散数学 方世昌编著方世昌编著(第二版第二版)西安电子科技大学出版社西安电子科技大学出版社 1996.111996.11第8页离散数学参考离散数学参考书1.1.离散数学离散数学左孝凌、李左孝凌、李为鑑、刘永才编著为鑑、刘永才编著上海科技文件出版社上海科技文件出版社第9页离散数学参考离散数学参考书2.2.离散数学离散数学-理论理论 分析分析 题解，左孝凌等著题解，左孝凌等著上海科技文件出版社上海科技文件出版社第10页离散数学参考离散数学参考书3.3.离散数学习题集离散数学习题集数理逻辑与集合论分册数理逻辑与集合论分册 耿素云耿素云 图论分册，图论分册，耿素云耿素云抽象代数分册，抽象代数分册，张立昂张立昂 北京大学出版社北京大学出版社第11页离散数学参考离散数学参考书第12页离散数学参考离散数学参考书第13页离散数学(二)四、代数系统离散数学教学内容离散数学教学内容 一、数理逻辑 集合 二、关系 函数 三、图论 离散数学(一)第14页高次方程求解历程(1)埃及埃及/古希腊古希腊 一次一次/二次方程二次方程(2)16世纪意大利世纪意大利 三次方程三次方程(卡当公式卡当公式),四次方程四次方程(3)17世纪世纪 四次以上方程四次以上方程 未解出未解出!(4)18世纪世纪 欧拉推断欧拉推断:实系数多项式可分解为一次或二次因式乘积实系数多项式可分解为一次或二次因式乘积 哥德巴赫拒绝接收欧拉推断哥德巴赫拒绝接收欧拉推断问题转换问题转换:每一个这类多项式最少有一个实根或者复根每一个这类多项式最少有一个实根或者复根(代数基本定理代数基本定理)欧拉欧拉,DAlembert,拉格朗日分别给出证实拉格朗日分别给出证实,但并不完善但并不完善高斯高斯(1799,博士论文博士论文)证实了代数基本定理证实了代数基本定理 Vandermonde和高斯研究了和高斯研究了xn-1=0特殊情形特殊情形四次以上方程代数可解普通情况四次以上方程代数可解普通情况 拉格朗日拉格朗日:“关于方程代数解法思索关于方程代数解法思索”,被迫得出结论用代数运算求被迫得出结论用代数运算求解普通高次方程是不可能解普通高次方程是不可能.(5)19世纪世纪 阿贝尔阿贝尔(Abel)和伽罗瓦和伽罗瓦(Galois)彻底处理高次方程代数不可解！彻底处理高次方程代数不可解！第15页近世代数近世代数/抽象代数历史抽象代数历史尼尔斯亨利克阿贝尔(Niels Henrik Abel)188月5日1829年4月6日挪威数学家，以证实五次方程不存在根式解和对椭圆函数论研究而闻名埃瓦里斯特伽罗瓦(variste Galois)1810月25日1832年5月31日法国数学家，以发觉了n次多项式能够用根式解充要条件而闻名.伽罗瓦理论,当代代数与数论基本支柱之一第16页近世代数近世代数/抽象代数历史抽象代数历史第17页近世代数近世代数/抽象代数历史抽象代数历史第18页近世代数近世代数/抽象代数历史抽象代数历史后人对伽罗瓦评论后人对伽罗瓦评论:被被许许多科学家和史学家多科学家和史学家认为认为是是人人类历类历史上最史上最伟伟大大10位数学家之一位数学家之一 著名数学家皮卡著名数学家皮卡评评价价:在开在开创创性和概念深邃性和概念深邃 方面无人能及方面无人能及 20世世纪伟纪伟大数学家外大数学家外尔尔评评价价:伽罗瓦叙述在好几十年中一直被看作是天书伽罗瓦叙述在好几十年中一直被看作是天书;不过不过,它以后对数学整个发展产生愈来愈深远影响它以后对数学整个发展产生愈来愈深远影响.假如从它所包含思想之新假如从它所包含思想之新奇和意义之深远来判断奇和意义之深远来判断,可能是整个人类知识宝库中价值最为重大一件珍品可能是整个人类知识宝库中价值最为重大一件珍品.大数学家大数学家weil评评价价:现现在在,大家都已充分大家都已充分认识认识到到伽罗瓦理论是一个基本分支伽罗瓦理论是一个基本分支,每一个严厉认真数学专业大学生应该在头几年教育中就了解它每一个严厉认真数学专业大学生应该在头几年教育中就了解它.第19页近世代数近世代数/抽象代数历史抽象代数历史第20页第21页第六章、代数结构第六章、代数结构代数系统代数系统:集合和定义在集合上若干运算所组成系统。用抽象方法研究各种代数系统性质理论学科叫“近世代数”或“抽象代数”。“抽象方法抽象方法”是指 (1)不关注组成代数系统详细集合不关注组成代数系统详细集合是什么，也不关注集合上运算怎样定义不关注集合上运算怎样定义 (2)研究抽象数学结构抽象数学结构，研究抽象数学结构普通性质普通性质 线性代数线性代数：命题代数命题代数：集合代数集合代数：第22页第六章、代数结构第六章、代数结构计算机安全，网络安全，密码学基础程序设计学中形式语义学基础刻画抽象数据结构关系数据库理论研究可计算性与计算复杂性差错控制编码理论都需要代数知识 尤其地，半群半群在形式语言和自动机理论中有着主要应用，有限域有限域理论是差错控制编码理论数学基础，在通讯中发挥了主要作用。而电子线路设计、电子计算机硬件设计和通讯系统设计更是离不开布尔代数布尔代数。第23页第六章、代数结构第六章、代数结构 代数概念和方法是研究计算机科学和工程主要数学工具。众所周知，在各种数学问题及许多实际问题研究中都离不开数学模型，要结构一个现象或过程数学模型，就需要某种数学结构，而代数结构就是最惯用数学结构之一。所以，我们有必要掌握代数系统代数系统主要概念和基本方法。第24页第一讲第一讲 代数系统代数系统代数组成与分类代数组成与分类1 11 1子代数子代数2 2主要内容主要内容:代数定义，么元和零元代数定义，么元和零元重点重点:幺元、零元和逆元幺元、零元和逆元难点难点:重点和难点重点和难点:幺元、零元和逆元幺元、零元和逆元3 3第25页一、代数组成与分类一、代数组成与分类代数组成代数组成:运算定义运算定义：函数 f:SmS称为集合S上m元运算，mN叫运算元数(或阶)。m=1,一元运算，SS,RR,f(x)=|x|+1；m=2,一元运算，S2S,R2R,f()=x+y；普通地，n元运算，SnS。代数系统定义代数系统定义：1.一个非空集合A(代数载体)；2.定义若干在A上封闭运算f1,f2,fm；3.代数常数。代数系统惯用一个惯用一个n重组重组来表示来表示,其中A称为代数结构载体，为各种运算。有时为了强调。有时为了强调S有一些元有一些元素地位特殊素地位特殊,也可将它们列入也可将它们列入n重组重组末尾，即末尾，即。第26页一、代数组成与分类一、代数组成与分类代数分类代数分类:1.要有相同组成成份。2.服从一组相同称为公理性质。运算个数相同常数个数相同对应运算元数(阶)相同 例:考虑含有形式组成成份和下述公理代数类(这里“-”是一元运算)。(1)a+b=b+a (2)ab=ba (3)(a+b)+c=a+(b+c)(4)(ab)c=a(bc)(5)a(b+c)=ab+ac (6)a+(-a)=0 (7)a+0=a (8)a1=a 那么 和是同类代数,但但是不一样类是不一样类,因为公理因为公理(6)对这个代数不成立对这个代数不成立(这里“-”表示集合绝对补)。第27页二、子代数二、子代数封闭性定义：封闭性定义：设与是S上二元与一元运算,S S，若对任意a,bS，蕴含着abS，称S关于运算是封闭；若对任意aS，蕴含着aS，称S关于运算是封闭。子代数定义：子代数定义：设A=是一代数,假如(1)S S (2)S对S上运算和封闭(3)kS那么A=是A子代数子代数。比如：比如：(1)是是子代数；子代数；(2)是是一个子代数。一个子代数。第28页三、幺元、零元三、幺元、零元幺元幺元定义：定义：设*是S上二元运算,(1)若存在elS，对全部xS，都有el*x=x，则称el是是关关于于运运算算*左左么么元元(Left Identity Element)，或称左左单单位位元元(Left Unit Element)。(2)若存在元素erS，对全部xS，都有x*er =x，则称er是是关关于于运运算算*右右么么元元(Right Identity Element)，或称右右单单位位元元(Right Unit Element)。(3)若存在eS，它既是左么元也是右么元，则称e是是关关于于运运算算*一一个个么么元元(Identity Element)，或称单单位位元元(Unit Element)，即对全部xS，都有x*e=e*x=x，则e是关于运算*么元。第29页三、幺元、零元三、幺元、零元幺元幺元示例：示例：例2 代数A=以下表所表示：能够看出，代数A左么元为b，没有右么元。例3 中么元为1；中么元为0。*abcaabbbabccaba第30页三、幺元、零元三、幺元、零元零元零元定义：定义：设*是S上二元运算,(1)若存在lS，对全部xS，都有l*x=l，则称l是为关是为关于运算于运算*左零元左零元(Left Zero Element)。(2)若存在rS，对全部xS，都有x*r=r，则称r是是关关于于运运算算*右零元右零元(Right Zero Element)。(3)若存在S，它既是左零元也是右零元，则称是关于运算*零元，即对任意xS，都有*x=x*=，则是是关关于于运运算算*零零元元(Zero Element)。*abcaabbbabccaba在在例例2中代数中代数A=右零元为右零元为a,b；没有左零元。；没有左零元。第31页三、幺元、零元三、幺元、零元例例4：(1)么元：1,零元：0；(2)S非空有限集，代数 么元 零元 对：S 对：S *abcaabbbabccaba例例2代数中：代数中：右零元：右零元：a,b；左零元：无；右么元：无；左么元：；左零元：无；右么元：无；左么元：b能够看出：能够看出：左左(右右)零元零元不一定存在；不一定存在；左左(右右)零元零元存在时也不一定唯一；存在时也不一定唯一；左零元与右零元可能左零元与右零元可能同时存在。同时存在。第32页三、幺元、零元三、幺元、零元 定理定理1：设*是定义在集合A上二元运算，且A中关于运算*左幺元为el，右幺元为er，则el=er=e，且A中幺元是唯一。证实：证实：因为el和er分别为左幺元和右幺元，所以el=el*er=er=e。设另有一幺元e,则e=e*e=e，所以幺元唯一。定理定理2：设*是定义在集合A上二元运算，且A中关于运算*左零元为l，右零元为r，则l=r=，且A中零元是唯一。定理定理3：设是一个代数系统,且集合A中元素个数大于1.假如该代数系统中存在幺元e和零元,则e。证实：证实：用反证法，假如幺元幺元e=零元零元，那么对于任意xA,必有x=e*x=*x=e。于是，A中全部元素都是相同，这与A中含有多个元素相矛盾。第33页四、逆元四、逆元逆元逆元定义：定义：设*是A上二元运算,e是A中关于*么元，(1)若对元素aA，存在bA，使b*a=e，则称b是a左逆元；(2)若对元素aA，存在bA，使a*b=e，则称b是a右逆元；(3)若对元素aA，存在bA，使a*b=b*a=e，则称b是a逆元，记为a-1。比如比如中么元为中么元为0，x 逆元为逆元为-x。普通来说，一个元素左逆元不一定等于该元素右逆元；一个元素能够有左逆元而无右逆元，甚至一个元素左（右）逆元还能够不唯一。第34页四、逆元四、逆元例例5(1)：么元为0，仅0有逆元;么元为1,仅零元0无逆元,其它元素x都有逆元。例例5(2)：设Nk是前k个自然数集,这里k0,Nk=0,1,2,k-1，定义模k加法+k以下:对每一x、yNk，么元为么元为0；Nk每一元素有逆元，每一元素有逆元，0逆元是逆元是0，每一非，每一非0元素元素x逆元是逆元是k-x。例例5(3)：设Nk是前k个自然数集,这里k2,定义模k乘法k以下:x k y=z，这里zNk,且对某一n,xy-z=nk,即 1是么元，元素是么元，元素xNk在在Nk中有逆元仅当中有逆元仅当x和和k互质。互质。第35页四、逆元四、逆元1是幺元，逆元是它本身是幺元，逆元是它本身0,2无逆元，无逆元，3逆元为逆元为30无逆元，无逆元，1逆元为逆元为1，2逆元为逆元为3，3逆元为逆元为2，4逆元为逆元为4第36页四、逆元四、逆元 定理定理4：对于可结合运算：对于可结合运算,假如一个元素假如一个元素x有左逆元有左逆元l和右和右逆元逆元r,那么那么l=r=x1(即逆元是唯一即逆元是唯一)。证实证实:设e对运算*是么元,于是l*x=x*r=e 依据运算*可结合性,得到l=l*e=l*(x*r)=(l*x)*r=e*r=r 设x有两个逆元a,b,那么a=a*e=a*(x*b)=(a*x)*b=e*b=b 所以逆元是唯一。可约性定义可约性定义：设*是S上二元运算,aS,假如对于每一x、yS有(a*x=a*y)(x*a=y*a)(x=y)，则称a是可约可约或可消去可消去。第37页四、逆元四、逆元 定理定理5：若代数：若代数中中 运算满足结合律运算满足结合律,且且aS有逆元有逆元,那么那么a必定是可约。必定是可约。证实证实:设a逆元为a-1，对x、yS，(1)当ax=ay时可得a-1(ax)=a-1(ay)，即(a-1 a)x=(a-1 a)y，可推得x=y。(2)当xa=ya时可得(xa)a-1=(ya)a-1,即x(a a-1)=y(a a-1),也可推得x=y。所以，a是可约。Note：上述定理逆不成立。比如：上述定理逆不成立。比如中，中，aI且且a0,a是可约是可约,但除但除了了1外其它元素都不存在逆元。外其它元素都不存在逆元。第38页五、代数系统：例题五、代数系统：例题 例例:在整数集合I上，定义二元运算。为a*bab2 请回答：(1)集合I和运算*是否组成代数系统?(2)运算*在I上可交换吗？(3)运算*在I上可结合吗？(4)运算*在I上有没有单位元？(5)对运算*是否全部元素都有逆元？若有，逆元是什么？第39页五、代数系统：例题五、代数系统：例题 解答解答:(1)集合I和运算*是否组成代数系统?任任取取a，bI，则则ab2I，即即a*bI，所所以以*在在I上上封封闭，即集合闭，即集合I和运算和运算*组成代数系统。组成代数系统。(2)运算*在I上可交换吗？因为因为a*bab2ba2b*a，所以，所以*在在I上可交换。上可交换。(3)运算。在I上可结合吗？任取任取a，b，c I，因为因为 (a*b)*c(ab2)*c(ab2)c2abc4a*(b*c)a*(bc2)a(bc2)2abc4 所以所以(a*b)*ca*(b*c)，故，故*在在I上可结合。上可结合。第40页五、代数系统：例题五、代数系统：例题 解答解答:(4)运算*在I上有没有单位元？若若e是是I上上关关于于*单单位位元元，则则任任取取aI，应应有有a*ee*aa，由由交交换换律律，只只要要a*ea，即即ae2a，得得e2，而而2I，故故*在在I中有单位元中有单位元2。(5)对运算*是否全部元素都有逆元？若有，逆元是什么？任取任取aI，有，有4aI，而，而a*(4a)a(4a)22(4a)*a(4a)a22 即即I中任一元素中任一元素a都有逆元都有逆元4a。第41页作业：作业：P174 习题习题6.1 1、5、7、11 P176 习题习题6.2 2 第42页