离散数学-代数系统.ppt

《离散数学-代数系统.ppt》由会员分享，可在线阅读，更多相关《离散数学-代数系统.ppt（42页珍藏版）》请在三一办公上搜索。

1、离散数学(二)第一讲,计算机学院:焦晓鹏2014.秋,个人信息(Personal Information),Instructor:焦晓鹏，副教授，工学博士 Bs.(2004)Xidian University PhD(2009)Xidian University RF(2010-2012)National University of SingaporeResearch Direction:新型差错控制编码技术 高密度存储系统信号处理和编码技术（高密度磁盘和闪存flash memory）数字喷泉码和网络编码技术Laboratory:计算学院计算机科学系Office:主楼I-区,402房间,关于学

2、习和考试,(1)摆正学习和考试的关系 考试是学习期间的副产品 以考试为目的的学习是对知识耍流氓(2)勤奋!诸葛亮 诫子书 夫君子之行，静以修身，俭以养德。非淡泊无以明志，非宁静无以致远。夫学须静也，才须学也。非学无以广才，非志无以成学。韬慢则不能励精，险躁则不能治性。年与时驰，意与岁去，遂成枯落，多不接世。悲守穷庐，将复何及？,名人话数学,数学是科学之王。高斯 数学支配着宇宙。毕达哥拉斯 自然界的书是用数学的语言写成的。伽利略 数学是一切知识中的最高形式。柏拉图 数学是打开科学大门的钥匙。培根 一门科学，只有当它成功地运用数学时，才能达到真正完善的地步。马克思 一个国家只有数学蓬勃的发展，才能

3、展现它国力的强大。数学的发展和至善和国家繁荣昌盛密切相关。拿破仑,离散数学(Discrete Mathematics),读史使人明智,读诗使人聪慧,演算使人精密,哲理使人深刻,伦理学使人有修养,逻辑修辞使人善辩。培根 数学史的书籍:美 莫里斯.克莱茵 著 英 斯科特 著 广西师范大学出版社 没有一种数学的思想,以它被发现时的那个样子公开发表出来。一个问题被解决后,相应地发展为一种形式化技巧,结果把求解过程丢在一边,使火热的发明变成冰冷的美丽。弗赖登塔尔:荷兰著名数学教育家,离散数学课程的学习特点及方法,特点:强调：逻辑性、抽象性；注重：概念、方法与应用 方法:1该课程概念名词多，定义多，公式多

4、，要求记忆准确。2认真/仔细做好课堂笔记。3完成大量习题。考核:平时成绩15%期末考试85%,离散数学教材,教材：离散数学 方世昌编著 西安电子科技大学出版社2009.8,离散数学教材,旧版教材：离散数学 方世昌编著(第二版)西安电子科技大学出版社 1996.11,离散数学参考书,1.离散数学左孝凌、李为鑑、刘永才编著上海科技文献出版社,离散数学参考书,2.离散数学-理论分析题解，左孝凌等著上海科技文献出版社,离散数学参考书,3.离散数学习题集数理逻辑与集合论分册 耿素云 图论分册，耿素云抽象代数分册，张立昂 北京大学出版社,离散数学参考书,离散数学参考书,离散数学教学内容,高次方程求解历程,

5、(1)埃及/古希腊 一次/二次方程(2)16世纪意大利 三次方程(卡当公式),四次方程(3)17世纪 四次以上方程 未解出!(4)18世纪 欧拉推断:实系数多项式可分解为一次或二次因式乘积 哥德巴赫拒绝接受欧拉推断问题转换:每一个此类多项式至少有一个实根或者复根(代数基本定理)欧拉,DAlembert,拉格朗日分别给出证明,但并不完善高斯(1799,博士论文)证明了代数基本定理 Vandermonde和高斯研究了xn-1=0的特殊情形四次以上方程代数可解的一般情况 拉格朗日:“关于方程的代数解法的思考”,被迫得出结论用代数运算求解一般高次方程是不可能的.(5)19世纪 阿贝尔(Abel)和伽罗

6、瓦(Galois)彻底解决高次方程代数不可解！,近世代数/抽象代数历史,尼尔斯亨利克阿贝尔(Niels Henrik Abel)1802年8月5日1829年4月6日挪威数学家，以证明五次方程不存在根式解和对椭圆函数论的研究而闻名,埃瓦里斯特伽罗瓦(variste Galois)1811年10月25日1832年5月31日法国数学家，以发现了n次多项式可以用根式解的充要条件而闻名.伽罗瓦理论,当代代数与数论的基本支柱之一,近世代数/抽象代数历史,近世代数/抽象代数历史,近世代数/抽象代数历史,后人对伽罗瓦的评论:被许多科学家和史学家认为是人类历史上最伟大的10位数学家之一 著名数学家皮卡评价:在开

7、创性和概念的深邃 方面无人能及 20世纪伟大数学家外尔评价:伽罗瓦的论述在好几十年中一直被看作是天书;但是,它后来对数学的整个发展产生愈来愈深远的影响.如果从它所包含思想之新奇和意义之深远来判断,也许是整个人类知识宝库中价值最为重大的一件珍品.大数学家weil评价:现在,大家都已充分认识到伽罗瓦理论是一个基本分支,每一个严肃认真的数学专业大学生应该在头几年的教育中就了解它.,近世代数/抽象代数历史,第六章、代数结构,代数系统:集合和定义在集合上的若干运算所组成的系统。用抽象方法研究各种代数系统性质的理论学科叫“近世代数”或“抽象代数”。“抽象方法”是指(1)不关注组成代数系统的具体集合是什么，

8、也不关注集合上的运算如何定义(2)研究抽象的数学结构，研究抽象数学结构的一般性质 线性代数：命题代数：集合代数：,第六章、代数结构,特别地，半群在形式语言和自动机理论中有着重要的应用，有限域理论是差错控制编码理论的数学基础，在通讯中发挥了重要作用。而电子线路设计、电子计算机硬件设计和通讯系统设计更是离不开布尔代数。,第六章、代数结构,代数的概念和方法是研究计算机科学和工程的重要数学工具。众所周知，在各种数学问题及许多实际问题的研究中都离不开数学模型，要构造一个现象或过程的数学模型，就需要某种数学结构，而代数结构就是最常用的数学结构之一。因此，我们有必要掌握代数系统的重要概念和基本方法。,第一讲

9、 代数系统,主要内容:,重点和难点:,一、代数的构成与分类,代数的构成:运算的定义：函数 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重组的末尾，即。,一、代数的构成与分类,代数的分类:1.要有相同的构成成分。2.服从一组相同

10、的称为公理的性质。,例:考虑具有形式构成成分和下述公理的代数类(这里“-”是一元运算)。(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)对这个代数不成立(这里“-”表示集合的绝对补)。,二、子代数,封闭性定义：设与是S上的二元与一元运算,S S，若对任意a,bS，蕴含着abS，称S关于运算是封闭的；若对任意aS，蕴含着aS，称S关于运算是封闭的。,子代数的定义：设A=是一代数,如果(1)S S(2)S对S上的运算

11、和封闭(3)kS那么A=是A的子代数。例如：(1)是的子代数；(2)是的一个子代数。,三、幺元、零元,幺元定义：设*是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 Elemen

12、t)，或称单位元(Unit Element)，即对所有xS，都有x*e=e*x=x，则e是关于运算*的么元。,三、幺元、零元,幺元示例：例2 代数A=如下表所示：可以看出，代数A左么元为b，没有右么元。例3 中么元为1；中么元为0。,三、幺元、零元,零元定义：设*是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

13、*=，则是关于运算*的零元(Zero Element)。,在例2中代数A=的右零元为a,b；没有左零元。,三、幺元、零元,例4：(1)么元：1,零元：0；(2)S非空有限集，代数 么元 零元 对：S 对：S,例2的代数中：右零元：a,b；左零元：无；右么元：无；左么元：b,可以看出：左(右)零元不一定存在；左(右)零元存在时也不一定唯一；左零元与右零元可能同时存在。,三、幺元、零元,定理1：设*是定义在集合A上的二元运算，且A中关于运算*的左幺元为el，右幺元为er，则el=er=e，且A中的幺元是唯一的。证明：因为el和er分别为左幺元和右幺元，所以el=el*er=er=e。设另有一幺元e

14、,则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中含有多个元素相矛盾。,四、逆元,逆元定义：设*是A上的二元运算,e是A中关于*的么元，(1)若对元素aA，存在bA，使b*a=e，则称b是a的左逆元；(2)若对元素aA，存在bA，使a*b=e，则称b是a的右逆元；(3)若对元素aA，存在b

15、A，使a*b=b*a=e，则称b是a的逆元，记为a-1。,例如中么元为0，x 的逆元为-x。一般来说，一个元素的左逆元不一定等于该元素的右逆元；一个元素可以有左逆元而无右逆元，甚至一个元素的左（右）逆元还可以不唯一。,四、逆元,例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,且对某

16、一n,xy-z=nk,即 1是么元，元素xNk在Nk中有逆元仅当x和k互质。,四、逆元,1是幺元，逆元是它本身0,2无逆元，3的逆元为3,0无逆元，1的逆元为1，2的逆元为3，3的逆元为2，4的逆元为4,四、逆元,定理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、y

17、S有(a*x=a*y)(x*a=y*a)(x=y)，则称a是可约的或可消去的。,四、逆元,定理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外其他元素都不存在逆元。,五、代数系统：例题,例:在整数集合I上，定义二元运算。为a*bab2 请

18、回答：(1)集合I和运算*是否构成代数系统?(2)运算*在I上可交换吗？(3)运算*在I上可结合吗？(4)运算*在I上有无单位元？(5)对运算*是否所有的元素都有逆元？若有，逆元是什么？,五、代数系统：例题,解答:(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上可结合。,五、代数系统：例题,解答:(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。,作业：P174 习题6.1 1、5、7、11 P176 习题6.2 2,