离散数学-第1讲-代数

1离散数学（二）数学是科学之王。——高斯数学支配着宇宙。——毕达哥拉斯自然界的书是用数学的语言写成的。——伽利略数学是一切知识中的最高形式。——柏拉图数学是打开科学大门的钥匙。——培根一门科学，只有当它成功地运用数学时，才能达到真正完善的地步。——马克思一个国家只有数学蓬勃的发展，才能展现它国力的强大。数学的发展和至善和国家繁荣昌盛密切相关。——拿破仑数学研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支在计算机科学与技术领域有着广泛的应用，是计算机必不可少的先行课程、核心课程数字电子计算机是一个离散结构，它只能处理离散化的数量关系。因此，无论计算机科学本身，还是与计算机科学密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。离散数学教材：方世昌编著西安电子科技大学出版社2009.81.《离散数学》左孝凌、李为鑑、刘永才编著上海科技文献出版社参考书2.《离散数学》--理论•分析•题解，左孝凌等著上海科技文献出版社3.《离散数学习题集》数理逻辑与集合论分册耿素云北京大学出版社离散数学课程的学习特点及方法特点:强调：逻辑性、抽象性；注重：概念、方法与应用方法:1．该课程概念名词多，定义多，公式多，要求记忆准确。2．认真/仔细做好课堂笔记。3．完成大量习题。离散数学课程的学习目标培养抽象推理、逻辑思维和归纳构造等能力，提高利用数学方法解决问题的技能，为进一步学习奠定计算机数学的基础。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。离散数学(二)四、代数系统离散数学教学内容一、数理逻辑集合二、关系函数三、图论离散数学(一)考核方式总成绩构成:平时成绩占15%期末成绩占85%平时成绩构成:课堂练习+课后作业+考勤第六章代数代数系统:集合和定义在集合上的若干运算所组成的系统。用抽象方法研究各种代数系统性质的理论学科叫“近世代数”或“抽象代数”。“抽象方法”是指(1)不关注组成代数系统的具体集合是什么，也不关注集合上的运算如何定义(2)研究抽象的数学结构，研究抽象数学结构的一般性质线性代数：Mn(R)，+，•命题代数：X，﹁，∧，∨集合代数：ρ(A)，∩，∪，—计算机安全，网络安全，密码学的基础程序设计学中的形式语义学基础刻画抽象数据结构关系数据库理论研究可计算性与计算复杂性差错控制编码理论都需要代数知识特别地，半群在形式语言和自动机理论中有着重要的应用，有限域理论是差错控制编码理论的数学基础，在通讯中发挥了重要作用。而电子线路设计、电子计算机硬件设计和通讯系统设计更是离不开布尔代数。第六章代数代数的概念和方法是研究计算机科学和工程的重要数学工具。众所周知，在各种数学问题及许多实际问题的研究中都离不开数学模型，要构造一个现象或过程的数学模型，就需要某种数学结构，而代数结构就是最常用的数学结构之一。因此，我们有必要掌握代数系统的重要概念和基本方法。第六章代数第一讲代数结构代数的构成与分类11子代数2主要内容:代数定义，么元和零元重点:幺元、零元和逆元难点:重点和难点:幺元、零元和逆元3一、代数的构成与分类代数的构成:运算的定义：函数f:Sm→S称为集合S上的m元运算，m∈N叫运算的元数(或阶)。m=1,一元运算，S→S,R→R,f(x)=|x|+1；m=2,二元运算，S2→S,R2→R,f(x,y)=x+y；一般地，n元运算，Sn→S。代数系统的定义：1.一个非空集合A(代数的载体)；2.定义的若干在A上封闭的运算f1,f2,…,fm；3.代数常数。代数系统常用一个n重组A，，，…，来表示,其中A称为代数结构的载体，，，…为各种运算。有时为了强调S有某些元素地位特殊,也可将它们列入n重组的末尾，即A，，，…，k1，…，km。代数的分类:1.要有相同的构成成分2.服从一组相同的称为公理的性质运算的个数相同常数的个数相同对应运算元数(阶)相同例:考虑具有I,+,·,-,0,1形式构成成分和下述公理的代数类(这里“-”是一元运算)。(1)a+b=b+a(2)a·b=b·a(3)(a+b)+c=a+(b+c)(4)(a·b)·c=a·(b·c)(5)a·(b+c)=a·b+a·c(6)a+(-a)=0(7)a+0=a(8)a·1=a那么Q,+,·,-,0,1和R,+,·,-,0,1是同类代数,但ρ(S),∪,∩,¯,Ø,S是不同类的,因为公理(6)对这个代数不成立(这里“-”表示集合的绝对补)。二、子代数封闭性定义：设◦与∆是S上的二元与一元运算,S′⊆S，若对任意a,b∈S′，蕴含着a◦b∈S′，称S′关于运算◦是封闭的；若对任意a∈S′，蕴含着∆a∈S′，称S′关于运算∆是封闭的。子代数的定义：设A=S,◦,△,k是一代数,如果(1)S′⊆S(2)S′对S上的运算◦和△封闭(3)k∈S′那么A′=S′,◦,△,k是A的子代数。例如：(1)I,+,0是R,+，0的子代数；(2){0,2},+4,0是{0,1,2,3},+4,0的一个子代数。三、幺元、零元么元定义：设*是S上的二元运算,(1)若存在el∈S，对所有x∈S，都有el*x=x，则称el是关于运算*的左么元(LeftIdentityElement)，或称左单位元(LeftUnitElement)。(2)若存在元素er∈S，对所有x∈S，都有x*er=x，则称er是关于运算*的右么元(RightIdentityElement)，或称右单位元(RightUnitElement)。(3)若存在e∈S，它既是左么元也是右么元，则称e是关于运算*的一个么元(IdentityElement)，或称单位元(UnitElement)，即对所有x∈S，都有x*e=e*x=x，则e是关于运算*的么元。三、幺元、零元么元示例：例2代数A={a,b,c},*如下表所示：可以看出，代数A左么元为b，没有右么元。例3R,×中么元为1；R,+中么元为0。*abcaabbbabccaba三、幺元、零元零元定义：设*是S上的二元运算,(1)若存在θl∈S，对所有x∈S，都有θl*x=θl，则称θl是为关于运算*的左零元(LeftZeroElement)。(2)若存在θr∈S，对所有x∈S，都有x*θr=θr，则称θr是关于运算*的右零元(RightZeroElement)。(3)若存在θ∈S，它既是左零元也是右零元，则称θ是关于运算*的零元，即对任意x∈S，都有θ*x=x*θ=θ，则θ是关于运算*的零元(ZeroElement)。*abcaabbbabccaba在例2中代数A={a,b,c},*的右零元为a,b；没有左零元。三、幺元、零元例4：(1)I,×么元：1,零元：0；(2)S非空有限集，代数ρ(S),∪,∩,¯,Ø,S么元零元对∪：ØS对∩：SØ*abcaabbbabccaba例2的代数中：右零元：a,b；左零元：无；右么元：无；左么元：b可以看出：左(右)零元不一定存在；左(右)零元存在时也不一定唯一；左零元与右零元可能同时存在。三、幺元、零元定理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,*是一个代数系统,且集合A中元素的个数大于1.如果该代数系统中存在么元e和零元θ,则θ≠e。证明：用反证法，假如么元e=零元，那么对于任意xA,必有x=e*x=θ*x=θ=e。于是，A中所有元素都是相同的，这与A中含有多个元素相矛盾。四、逆元逆元定义：设*是A上的二元运算,e是A中关于*的么元，(1)若对元素a∈A，存在b∈A，使b*a=e，则称b是a的左逆元；(2)若对元素a∈A，存在b∈A，使a*b=e，则称b是a的右逆元；(3)若对元素a∈A，存在b∈A，使a*b=b*a=e，则称b是a的逆元，记为a-1。例如I,+中么元为0，x的逆元为-x。一般来说，一个元素的左逆元不一定等于该元素的右逆元；一个元素可以有左逆元而无右逆元，甚至一个元素的左（右）逆元还可以不唯一。四、逆元例6(1)：N,+么元为0，仅0有逆元;R,·么元为1,仅零元0无逆元,其它元素x均有逆元。例6(2)：设Nk是前k个自然数的集,这里k＞0,Nk={0,1,2,…,k-1}，定义模k加法+k如下:对每一x、y∈Nk，么元为0；Nk的每一元素有逆元，0的逆元是0，每一非0元素x的逆元是k-x。例6(3)：设Nk是前k个自然数的集,这里k≥2,定义模k乘法×k如下:x×ky=z，这里z∈Nk,且对某一n,xy-z=nk,即1是么元，元素x∈Nk在Nk中有逆元仅当x和k互质。kyxk,yxkyx,yx)mod(yxkyx)mod(yxkxykyxk,yxkyx,yx)mod(yxkyx四、逆元12340424130331420243210100000043210512303202023210100000321041是么元，逆元是它本身0,2无逆元，3的逆元为30无逆元，1的逆元为1，2的逆元为3，3的逆元为2，4的逆元为4四、逆元定理4：对于可结合运算,如果一个元素x有左逆元l和右逆元r,那么l=r=x－1(即逆元是唯一的)。证明:设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上的二元运算,a∈S,如果对于每一x、y∈S有(a*x=a*y)∨(x*a=y*a)(x=y)，则称a是可约的或可消去的。四、逆元定理5：若代数S,中运算满足结合律,且a∈S有逆元,那么a必定是可约的。证明:设a的逆元为a-1，对∀x、y∈S，(1)当ax=ay时可得a-1(ax)=a-1(ay)，即(a-1a)x=(a-1a)y，可推得x=y。(2)当xa=ya时可得(xa)a-1=(ya)a-1,即x(aa-1)=y(aa-1),也可推得x=y。因此，a是可约的。Note：上述定理的逆不成立。例如I,·中，∀a∈I且a≠0,a是可约的,但除了1外其他元素都不存在逆元。五、代数系统：例题例:在整数集合I上，定义二元运算。为a*b＝a＋b－2请回答：(1)集合I和运算*是否构成代数系统?(2)运算*在I上可交换吗？(3)运算*在I上可结合吗？(4)运算*在I上有无单位元？(5)对运算*是否所有的元素都有逆元？若有，逆元是什么？五、代数系统：例题解答:(1)集合I和运算*是否构成代数系统?任取a，b∈I，则a＋b－2∈I，即a*b∈I，所以*在I上封闭，即集合I和运算*构成代数系统。(2)运算*在I上可交换吗？因为a*b＝a＋b－2＝b＋a－2＝b*a，所以*在I上可交换。(3)运算。在I上可结合吗？任取a，b，c∈I，因为(a*b)*c＝(a＋b－2)*c＝(a＋b－2)＋c－2＝a＋b＋c－4a*(b*c)＝a*(b＋c－2)＝a＋(b＋c－2)－2＝a＋b＋c－4所以(a*b)*c＝a*(b*c)，故*在I上可结合。五、代数系统：例题解答:(4)运算*在I上有无单位元？若e是I上关于*的单位元，则任取a∈I，应有a*e＝e*a＝a，由交换律，只要a*e＝a，