离散数学(下)课件6.1-代数系统.ppt

《离散数学(下)课件6.1-代数系统.ppt》由会员分享，可在线阅读，更多相关《离散数学(下)课件6.1-代数系统.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离 散 数 学()吉林大学计算机科学与技术学院吉林大学计算机科学与技术学院智能信息处理教研室智能信息处理教研室卢欣华卢欣华1 1古典代数与近世代数古典代数与近世代数古典代数的研究对象：方程古典代数的研究对象：方程以方程根的计算与分布为其研究中心。以方程根的计算与分布为其研究中心。近世代数的研究对象：代数系统近世代数的研究对象：代数系统古典代数的发展过程导致了群的概念古典代数的发展过程导致了群的概念的提出，发展成了近世代数。的提出，发展成了近世代数。2 2古典代数的发展过程古典代数的发展过程一元一次方程一元一次方程公元前公元前1700年年一元二次方程一元二次方程公元前几世纪公元前几世纪根式求根式

2、求解解古巴比伦、古印度古巴比伦、古印度一元三次方程一元三次方程 我国：在公元七世纪我国：在公元七世纪 一般的近似解法一般的近似解法 唐朝数学家王孝通唐朝数学家王孝通缉古算经缉古算经 西方：西方：16世纪世纪意大利数学家意大利数学家卡丹公式卡丹公式3 3古典代数的发展过程古典代数的发展过程一元四次方程一元四次方程FerrariL(费尔拉里费尔拉里)化为求一个三次方程和两个二次方程的根化为求一个三次方程和两个二次方程的根一元五次方程一元五次方程失败：欧拉失败：欧拉(1707-1783)、范德蒙德、范德蒙德、鲁菲尼、高斯等。鲁菲尼、高斯等。4 4拉格朗日拉格朗日(Lagrange)在在1770年猜测

3、年猜测:这样的求根公式不存在。这样的求根公式不存在。1824年年,挪威数学家阿贝尔挪威数学家阿贝尔(Abel)证明证明了拉格朗日的看法了拉格朗日的看法.但是虽然没有通用公式但是虽然没有通用公式,有些特殊的五有些特殊的五次方程有求根公式次方程有求根公式,那么自然会问那么自然会问:如如何判定一个给定的五次方程是否有这样何判定一个给定的五次方程是否有这样的求根公式的求根公式?阿贝尔去世阿贝尔去世(1829年年,26岁岁)前一直在竭前一直在竭尽全力地研究这个问题尽全力地研究这个问题.5 5在这一时期在这一时期,碰巧还有一位年轻人也在碰巧还有一位年轻人也在勤奋地钻研这个问题勤奋地钻研这个问题,而且最终取

4、得了而且最终取得了成功成功,他就是伽罗华他就是伽罗华(Galois).可是这位年轻人获得的非凡成果可是这位年轻人获得的非凡成果,在他在他因决斗去世因决斗去世11年后才开始得到数学界的年后才开始得到数学界的承认承认.6 6伽罗华伽罗华1811年年10月降生于巴黎近郊月降生于巴黎近郊.14岁那年因考试不及格而重上三年级岁那年因考试不及格而重上三年级.15岁参加声望很高的巴黎高等工科大学岁参加声望很高的巴黎高等工科大学的入学考试时的入学考试时,伽罗华失败了伽罗华失败了,不得不不得不进入较普通的师范学校进入较普通的师范学校.就是在这所学校就是在这所学校,伽罗华写出了他的第伽罗华写出了他的第一篇关于连分

5、数的数学论文一篇关于连分数的数学论文,显示了他显示了他的能力的能力(17岁岁).他的下两篇关于多项式方程的论文遭到他的下两篇关于多项式方程的论文遭到法国科学院的拒绝法国科学院的拒绝.更遭的是更遭的是,两篇论两篇论文手稿还莫名其妙地被丢失了文手稿还莫名其妙地被丢失了.7 71829年年7月月,他在巴黎高等工科大学的他在巴黎高等工科大学的入学考试中再次失败入学考试中再次失败.怀着沮丧之情怀着沮丧之情,伽罗华于伽罗华于1830年初又向年初又向科学院提交了另一篇论文科学院提交了另一篇论文,这次是为竞这次是为竞争一项数学大奖争一项数学大奖.科学院秘书傅立叶科学院秘书傅立叶(Fourier)将其手稿将其手

6、稿拿回家去审读拿回家去审读,不料在写出评审报告前不料在写出评审报告前去世了去世了,此文再也没有找到此文再也没有找到.8 8三失手稿三失手稿,加之考巴黎高等工科大学两加之考巴黎高等工科大学两度失败度失败,伽罗华遂对科学界产生排斥情伽罗华遂对科学界产生排斥情绪绪,变成了学生激进分子变成了学生激进分子,被学校开除被学校开除.担任私人辅导教师谋生担任私人辅导教师谋生,但他的数学研但他的数学研究工作依然相当活跃究工作依然相当活跃.在这一时期写出在这一时期写出了最著名的论文了最著名的论文“关于方程可根式求解关于方程可根式求解的条件的条件”,并于并于1831年年1月送交科学院月送交科学院.到到3月月,科学院

7、方面仍杳无音讯科学院方面仍杳无音讯,于是他于是他写信给院长打听他的文章的下落写信给院长打听他的文章的下落,结果结果又如石沉大海又如石沉大海.9 9他放弃了一切希望他放弃了一切希望,参加了国民卫队参加了国民卫队.在那里和他在数学界一样运气不佳在那里和他在数学界一样运气不佳.他他刚加入不久刚加入不久,卫队即遭控告阴谋造反而卫队即遭控告阴谋造反而被解散被解散.在在1831年年5月月10日进行的一次抗议聚宴日进行的一次抗议聚宴上上,伽罗华手中举着出鞘的刀提议为国伽罗华手中举着出鞘的刀提议为国王干杯王干杯,这一手势被同伙们解释成是要这一手势被同伙们解释成是要国王的命；第国王的命；第2天他就被捕了天他就被

8、捕了.后来被后来被判无罪判无罪,并于并于6月月15日获释日获释.10107月月4日日,他终于打听到他给科学院的那他终于打听到他给科学院的那篇论文的命运篇论文的命运:因因“无法理解无法理解”而遭拒而遭拒绝绝.审稿人是著名的数学家泊松审稿人是著名的数学家泊松(Poisson).7月月14日他又遭逮捕并被判了六个月监日他又遭逮捕并被判了六个月监禁禁,因为他在公共场所身着已被解散的因为他在公共场所身着已被解散的国民卫队的制服国民卫队的制服.在获释不久在获释不久,他陷入了与斯特凡妮小姐他陷入了与斯特凡妮小姐的恋情的恋情.这导致了他的早亡这导致了他的早亡.这次恋爱这次恋爱事件不知何故引出了一场决斗事件不知

9、何故引出了一场决斗.11111832年年5月月29日日,决斗的前夜决斗的前夜,伽罗华伽罗华写了封很长的信给他的朋友舍瓦利耶写了封很长的信给他的朋友舍瓦利耶(A.Chevalier),其中大致描述了他的数其中大致描述了他的数学理论学理论,从而给数学界留下了唯一一份从而给数学界留下了唯一一份它将蒙受何等损失的提要它将蒙受何等损失的提要.在第二天的决斗中在第二天的决斗中(离离25步远用手枪射击步远用手枪射击),伽罗华的胃部中弹伽罗华的胃部中弹,24小时后去世小时后去世.享年不足享年不足21岁岁.伽罗华留给世界的最核心的概念是伽罗华留给世界的最核心的概念是(置换置换)群群,他成了群论以至近世代数的创始

10、人他成了群论以至近世代数的创始人.1212Galois(18111832)(18111832)-近世代数的创始近世代数的创始人人Born:25Oct1811inBourgLaReine(nearParis),FranceDied:31May1832inParis,France1313近世代数的特点近世代数的特点-抽象抽象代数系统：代数系统：群群环环域域格格布尔代数布尔代数离散数学离散数学II1414第六章第六章群群与与环环15156.1代代数数系系统统代数运算的定义代数运算的定义代数运算的性质代数运算的性质代数系统的定义代数系统的定义1616设设S是一个非空集合，称是一个非空集合，称SS到到S

11、的一个映的一个映射射f为为S的一个的一个二元代数运算二元代数运算，即，对于，即，对于S中中任意两个元素任意两个元素a、b，通过通过f，唯一确定唯一确定S中中一个元素一个元素c：f(a,b)=c，常记为常记为a*b=c。注：注：1.代数运算是闭运算。代数运算是闭运算。2.该运算具有很强的抽象性，不限于该运算具有很强的抽象性，不限于+，-，*，/，意义很广泛。意义很广泛。3.类似地，可定义类似地，可定义S的的n元代数运算：元代数运算：Sn到到S的映射。的映射。1.代数运算的定义代数运算的定义1717例：例：S=a,b，则，则SS=(a,a),(a,b),(b,a),(b,b)映射映射f为：为：(a

12、,a)-a(a,b)-a(b,a)-b(b,b)-b f称为称为S的一个二元代数运算，有的一个二元代数运算，有f(a,a)=af(a,b)=af(b,a)=bf(b,b)=b也可表示为：也可表示为：a*a=a,a*b=a,b*a=b,b*b=b1818加加法法和和乘乘法法是是自自然然数数集集N上上的的二二元元代代数数运运算算；减法和除法不是减法和除法不是N上的二元代数运算。上的二元代数运算。加加法法、减减法法、乘乘法法都都是是整整数数集集Z上上的的二二元元代代数运算；除法不是数运算；除法不是Z上的二元代数运算。上的二元代数运算。乘乘法法、除除法法是是非非零零实实数数集集R*上上的的二二元元代代

13、数数运运算；加法和减法不是算；加法和减法不是R*上的二元代数运算。上的二元代数运算。例：例：1919矩矩阵阵加加法法和和乘乘法法是是n阶阶实实矩矩阵阵集集合合上上的的二元代数运算。二元代数运算。设设S是是一一个个非非空空集集合合，(S)是是S的的幂幂集集，则则、是是(S)上的二元代数运算。上的二元代数运算。、都是真值集合都是真值集合0,1上的二元代数运算。上的二元代数运算。例：例：例：例：S=a,b,(S)=a,b,a,b,2020设设*是集合是集合S上的二元代数运算，如上的二元代数运算，如果对于果对于任意任意a,bS，a*b=b*a都成立，都成立，则称运算则称运算*满足满足交换律交换律。例：

14、例：设设Q为有理数集合，对任意为有理数集合，对任意a,bQ,定义定义Q上的运算上的运算如下如下：ab=a+b-ab，则则是是Q上的二元代上的二元代数运算，且满足交换律：数运算，且满足交换律：ab=a+b-ab=b+a-ba=ba2.代数运算的性质代数运算的性质-交换律交换律2121设设*是是集集合合S上上的的二二元元代代数数运运算算，如如果果对对于于任任意意a,b,cS,(a*b)*c=a*(b*c)都成立，则称运算都成立，则称运算*满足满足结合律结合律。例：例：设设A是一个非空集合，对任意是一个非空集合，对任意a,bA，定义定义A上的运算上的运算如下：如下：ab=b，则，则是是A上的二元代数

15、运算，上的二元代数运算，且满足结合律：且满足结合律：(ab)c=bc=ca(bc)=ac=c2.代数运算的性质代数运算的性质-结合律结合律2222设设*是是集集合合S上上的的二二元元代代数数运运算算，a是是S中中的的元元素素，如如果果a*a=a,则则称称a是是关关于于运运算算*的的幂幂等等元元。如如果果S中中每每个个元元素素都都是是关关于于*的的幂幂等等元元，则则称称运运算算*满满足足等幂律等幂律。结结论论：若若a是是关关于于运运算算*的的幂幂等等元元，则对于任意正整数则对于任意正整数n，an=a。2.代数运算的性质代数运算的性质-等幂律等幂律2323设设*和和+是集合是集合S上的两个二元代数

16、上的两个二元代数运算，如果对于任意运算，如果对于任意a,b,cS,a*(b+c)=(a*b)+(a*c),(b+c)*a=(b*a)+(c*a)都成立，则称运算都成立，则称运算*对对+满足满足分配律分配律。注注意意：*未未必必满满足足交交换换律律，所所以以一一个个等等式成立，另一个未必成立。式成立，另一个未必成立。2.代数运算的性质代数运算的性质-分配律分配律2424例：例：设设A=,，二元运算二元运算*,+定义如下：问定义如下：问分配律成立否？分配律成立否？*+运算运算+对运算对运算*满足分配律。因为：满足分配律。因为：x+(y*z)=(x+y)*(x+z);(y*z)+x=(y+x)*(z

17、+x)证：证：当当x=,x+(y*z)=;(x+y)*(x+z)=当当x=,x+(y*z)=y*z;(x+y)*(x+z)=y*z运算运算*对运算对运算+不可分配。不可分配。证：证：*(+)=*=(*)+(*)=+=2525设设*和和+是集合是集合S上的两个二元代数运算，上的两个二元代数运算，如果对于任意如果对于任意a,bS,a*(a+b)=a，a+(a*b)=a，都成立，则称运算都成立，则称运算*和和+满足满足吸收律吸收律。例：例：定义自然数集合定义自然数集合N上的运算上的运算*和和+如下：如下：对于任意对于任意a,bN,有有a*b=maxa,b,a+b=mina,b，则，则*和和+是是N上

18、的二元代上的二元代数运算，且数运算，且满足吸收律。满足吸收律。a*(a+b)=maxa,mina,b=aa+(a*b)=mina,maxa,b=a2.代数运算的性质代数运算的性质-吸收律吸收律2626设设*是是集集合合S上上的的二二元元代代数数运运算算，如如果果S中中存存在在元元素素，使使得得对对于于S中中任任意意元元素素a，都都有有a*=，*a=，则则称称 是是S上上关关于于运运算算*的的零元零元。设设*是是集集合合S上上的的二二元元代代数数运运算算，对对于于S中中任任意意三三个个元元素素a,b,c，其其中中a不不等等于于零零元元，如果有：如果有：(1)若若a*b=a*c，则则b=c，(2)

19、若若b*a=c*a，则则b=c，就称就称*满足满足消去律消去律。2.代数运算的性质代数运算的性质-消去律消去律2727n阶实矩阵集合上的加法满足消去律，阶实矩阵集合上的加法满足消去律，但乘法不满足消去律。因为：但乘法不满足消去律。因为：但但例：例：2828整整数数集集Z上上的的加加法法、乘乘法法都都满满足足结结合合律律和和交交换换律律，乘乘法法对对加加法法满满足足分分配配律律，但但加加法对乘法不满足分配律；法对乘法不满足分配律；减法不满足结合律，也不满足交换律；减法不满足结合律，也不满足交换律；都不满足等幂律，也不满足吸收律。都不满足等幂律，也不满足吸收律。n阶阶实实矩矩阵阵集集合合上上的的加

20、加法法满满足足结结合合律律，也也满满足足交交换换律律；乘乘法法满满足足结结合合律律，但但不不满满足足交交换换律律；它它们们都都不不满满足足等等幂幂律律，也也不不满足吸收律。满足吸收律。例：例：(a-b)-ca-(b-c)例例：(5-2)-15-(2-1)(ab)+c(a+c)(b+c)例例：(34)+2(3+2)(4+2)2929设设(S)是非空集合是非空集合S的幂集，则的幂集，则(S)上的交运算上的交运算、并运算、并运算都满足结合律、都满足结合律、交换律；交换律；对对、对对都满足分配律；都满足分配律；它们都满足等幂律；也满足吸收律；它们都满足等幂律；也满足吸收律；但但、不满足消去律不满足消去

21、律。例：例：对任意对任意A,B,C(S)：结合律：结合律：(AB)C=A(BC)，(AB)C=A(BC)。交换律：交换律：AB=BA，AB=BA。分配律：分配律：A(BC)=(AB)(AC)，(BC)A=(BA)(CA)；A(BC)=(AB)(AC)，(BC)A=(BA)(CA)。等幂律：等幂律：AA=A，AA=A。吸收律：吸收律：A(AB)=A，A(AB)=A。消去律：消去律：AB=AC，未必有，未必有B=C；AB=AC，未必有，未必有B=C。3030设设S是一个非空集合，是一个非空集合，f1,fm是是S上的若干代数运算，把上的若干代数运算，把S及其运算及其运算f1,fm看成一个整体来看，叫

22、做一个看成一个整体来看，叫做一个代数系统，记为代数系统，记为(S,f1,fm)。3.代数系统的定义代数系统的定义3131设设S是是一一个个非非空空集集合合，(S)是是S的的幂幂集集，则则(S),)为代数系统。为代数系统。设设、是是真真值值集集合合0,1上上的的合合取取与与析析取取运运算算，则则(0,1,)是是代代数数系系统。统。例：例：3232设设Z为整数集，为整数集，Z0为偶数集，为偶数集，N为自然数为自然数集，集，+、是数的加法和乘法，则是数的加法和乘法，则(Z,+)、(Z,)、(Z,+,)、(Z0,+)、(Z0,)、(Z0,+,)、(N,+)、(N,)、(N,+,)都是代数系统。都是代数系统。设设、分分别别表表示示求求最最大大公公约约数数和和求求最最小小公公倍倍数数的的运运算算，那那么么(Z,)、(Z0,)、(N,)都是代数系统。都是代数系统。例：例：3333