离散数学第1讲代数

1、1离散数学（二）离散数学（二） 数学是科学之王。 高斯高斯 数学支配着宇宙。毕达哥拉斯毕达哥拉斯 自然界的书是用数学的语言写成的。伽利略伽利略 数学是一切知识中的最高形式。柏拉图柏拉图 数学是打开科学大门的钥匙。 培根培根 一门科学，只有当它成功地运用数学时，才能达到真正完善的地步。马克思马克思 一个国家只有数学蓬勃的发展，才能展现它国力的强大。数学的发展和至善和国家繁荣昌盛密切相关。拿破仑拿破仑 数学数学l 研究离散量的结构及其相互关系的数学学科，是现代数学现代数学的一个重要分支l 在计算机科学与技术领域有着广泛的应用，是计算机必不可少的先行课程、核心课程l 数字电子计算机是一个离散结构，它

2、只能处理离散化的数量关系。因此，无论计算机科学本身，还是与计算机科学密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 离散数学离散数学教材：教材：方世昌编著方世昌编著 西安电子科技大学出版社西安电子科技大学出版社2009.82009.81. 1.离散数学离散数学左孝凌、左孝凌、李为鑑、刘永才编著李为鑑、刘永才编著上海科技文献出版社上海科技文献出版社参考书参考书2. 2. 离散数学离散数学- -理论理论 分析分析 题解，左孝凌等著题解，左孝凌等著上海科技文献出版社上海科技文献出版社3. 3.离散数学习

3、题集离散数学习题集数理逻辑与集合论分册数理逻辑与集合论分册 耿素云耿素云北京大学出版社北京大学出版社离散数学课程的学习特点及方法离散数学课程的学习特点及方法特点特点: :强调：逻辑性、抽象性； 注重：概念、方法与应用 方法方法: :1该课程概念名词多，定义多，公式多，要求记忆准确。 2认真/仔细做好课堂笔记。 3完成大量习题。 离散数学课程的学习目标离散数学课程的学习目标l 培养抽象推理、逻辑思维和归纳构造等能力，提高利用数学方法解决问题的技能，为进一步学习奠定计算机数学的基础。l 通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严

4、格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。离散数学(二) 四、代数系统离散数学教学内容离散数学教学内容 一、数理逻辑 集合 二、关系 函数 三、图论 离散数学(一)考核方式考核方式总成绩构成总成绩构成: :平时成绩占15% 期末成绩占85% 平时成绩构成平时成绩构成: :课堂练习+课后作业+考勤第六章第六章 代数代数代数系统代数系统: : 集合和定义在集合上的若干运算所组成的系统。用抽象方法研究各种代数系统性质的理论学科叫“近世代数”或“抽象代数”。 “抽象方法抽象方法”是指 (1)不关注组成代数系统的具体集合不关注组成代数系统的具体集合是什么，也不关注集合上不关注集合

5、上的运算如何定义的运算如何定义 (2)研究抽象的数学结构抽象的数学结构，研究抽象数学结构的一般性质一般性质线性代数线性代数：命题代数命题代数：集合代数集合代数：计算机安全，网络安全，密码学的基础程序设计学中的形式语义学基础刻画抽象数据结构关系数据库理论研究可计算性与计算复杂性差错控制编码理论都需要代数知识 特别地，半群半群在形式语言和自动机理论中有着重要的应用，有限域有限域理论是差错控制编码理论的数学基础，在通讯中发挥了重要作用。而电子线路设计、电子计算机硬件设计和通讯系统设计更是离不开布尔代数布尔代数。第六章第六章 代数代数 代数的概念和方法是研究计算机科学和工程的重要数学工具。 众所周知，

6、在各种数学问题及许多实际问题的研究中都离不开数学模型，要构造一个现象或过程的数学模型，就需要某种数学结构，而代数结构就是最常用的数学结构之一。因此，我们有必要掌握代数系统代数系统的重要概念和基本方法。第六章第六章 代数代数第一讲第一讲 代数结构代数结构代数的构成与分类代数的构成与分类1 11 1子代数子代数2 2主要内容主要内容: :代数定义，么元和零元代数定义，么元和零元重点重点: : 幺元、零元和逆元幺元、零元和逆元难点难点: :重点和难点重点和难点: :幺元、零元和逆元幺元、零元和逆元3 3一、代数的构成与分类一、代数的构成与分类代数的构成代数的构成: : 运算的定义运算的定义：函数 f

7、: 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. 要有相同的构成成

8、分 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)对这个代数不成立对这个代数不成立 (这里“-” 表示集合的绝对补)。二、子代数二、子代数封闭性定义：封闭性定义： 设与是S上的二元与一元运算, S

9、S， 若对任意a,bS，蕴含着abS，称S关于运算是封闭的； 若对任意aS，蕴含着aS，称S关于运算是封闭的 。子代数的定义：子代数的定义： 设A=是一代数, 如果 (1) S S (2) S对S上的运算和封闭 (3) kS那么A= 是A的子代数子代数。 例如：例如：(1) 是是的子代数；的子代数； (2) 是是的一个子代数。的一个子代数。三、幺元、零元三、幺元、零元么元么元定义：定义：设*是S上的二元运算, (1)若存在elS，对所有xS，都有el * x =x，则称el是关于运是关于运算算*的左么元的左么元(Left Identity Element)，或称左单位元左单位元(Left Un

10、it 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是关于运算*的么元。三、幺元、零元三、幺元、零元么元么元示例：示例：例2 代数A=如下表所示： 可以看出，代数A左么元为b，没有右

11、么元。例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*=，则是关于运算是关于运算*的零元的零元(Zero Element)。在在例例2中代数中代数A=的右零元为的右零元为a, b

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

13、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中含有多个元素相矛盾。四、逆元四、逆元逆元逆元定义：定义：设*是A

14、上的二元运算,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。 一般来说，一个元素的左逆元不一定等于该元素的右逆元；一个元素可以有左逆元而无右逆元，甚至一个元素的左（右）逆元还可以不唯一。四、逆元四、逆元例例6(1)：么元为0，仅0有逆元; 么元为1,仅零元0无逆元,其它元素x均有逆元。例例6(2)：设Nk是前k个自然数的集, 这里k0, Nk =

15、0, 1, 2, ,k-1，定义模k加法+k如下: 对每一x、yNk， 么元为么元为0； Nk的每一元素有逆元，的每一元素有逆元，0的逆元是的逆元是0，每一非，每一非0元素元素x的逆的逆元是元是k-x。例例6(3)：设Nk是前k个自然数的集, 这里k2, 定义模k乘法k如下:x k y = z，这里zNk,且对某一n, xy-z=nk,即 1是么元，元素是么元，元素xNk在在Nk中有逆元仅当中有逆元仅当x和和k互质。互质。ky xk,yxky x,y x)mod(yxkyx)mod(yxkxyky xk,yxky x,y x)mod(yxkyx四、逆元四、逆元12340424130331420

16、243210100000043210512303202023210100000321041是么元，逆元是它本身是么元，逆元是它本身0,2无逆元，无逆元，3的逆元为的逆元为30无逆元，无逆元， 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

17、 * 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是可约的可约的或可消可消去的去的。四、逆元四、逆元 定理定理5：若代数：若代数中中 运算满足结合律运算满足结合律,且且aS有逆元有逆元,那那么么a必定是可约的。必定是可约的。证明证明 :设a的逆元为a-1，对x、yS， (1)当ax

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