离散数学下课件代数系统.ppt

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

1、1,离 散 数 学(),吉林大学计算机科学与技术学院智能信息处理教研室卢欣华,2,古典代数与近世代数,古典代数的研究对象：方程 以方程根的计算与分布为其研究中心。近世代数的研究对象：代数系统古典代数的发展过程导致了群的概念的提出，发展成了近世代数。,3,古典代数的发展过程,一元一次方程 公元前1700年一元二次方程 公元前几世纪 根式求解 古巴比伦、古印度一元三次方程 我国：在公元七世纪 一般的近似解法 唐朝数学家王孝通缉古算经 西方：16世纪 意大利数学家 卡丹公式,4,古典代数的发展过程,一元四次方程 Ferrari L(费尔拉里)化为求一个三次方程和两个二次方程的根 一元五次方程 失败：

2、欧拉(1707-1783)、范德蒙德、鲁菲尼、高斯等。,5,拉格朗日(Lagrange)在1770年猜测:这样的求根公式不存在。1824年,挪威数学家阿贝尔(Abel)证明了拉格朗日的看法.但是虽然没有通用公式,有些特殊的五次方程有求根公式,那么自然会问:如何判定一个给定的五次方程是否有这样的求根公式?阿贝尔去世(1829年,26岁)前一直在竭尽全力地研究这个问题.,6,在这一时期,碰巧还有一位年轻人也在勤奋地钻研这个问题,而且最终取得了成功,他就是伽罗华(Galois).可是这位年轻人获得的非凡成果,在他因决斗去世11年后才开始得到数学界的承认.,7,伽罗华1811年10月降生于巴黎近郊.1

3、4岁那年因考试不及格而重上三年级.15岁参加声望很高的巴黎高等工科大学的入学考试时,伽罗华失败了,不得不进入较普通的师范学校.就是在这所学校,伽罗华写出了他的第一篇关于连分数的数学论文,显示了他的能力(17岁).他的下两篇关于多项式方程的论文遭到法国科学院的拒绝.更遭的是,两篇论文手稿还莫名其妙地被丢失了.,8,1829年7月,他在巴黎高等工科大学的入学考试中再次失败.怀着沮丧之情,伽罗华于1830年初又向科学院提交了另一篇论文,这次是为竞争一项数学大奖.科学院秘书傅立叶(Fourier)将其手稿 拿回家去审读,不料在写出评审报告前去世了,此文再也没有找到.,9,三失手稿,加之考巴黎高等工科大

4、学两度失败,伽罗华遂对科学界产生排斥情绪,变成了学生激进分子,被学校开除.担任私人辅导教师谋生,但他的数学研 究工作依然相当活跃.在这一时期写出了最著名的论文“关于方程可根式求解的条件”,并于1831年1月送交科学院.到3月,科学院方面仍杳无音讯,于是他写信给院长打听他的文章的下落,结果又如石沉大海.,10,他放弃了一切希望,参加了国民卫队.在那里和他在数学界一样运气不佳.他刚加入不久,卫队即遭控告阴谋造反而被解散.在1831年5月10日进行的一次抗议聚宴上,伽罗华手中举着出鞘的刀提议为国王干杯,这一手势被同伙们解释成是要国王的命；第2天他就被捕了.后来被判无罪,并于6月15日获释.,11,7

5、月4日,他终于打听到他给科学院的那篇论文的命运:因“无法理解”而遭拒绝.审稿人是著名的数学家泊松(Poisson).7月14日他又遭逮捕并被判了六个月监禁,因为他在公共场所身着已被解散的国民卫队的制服.在获释不久,他陷入了与斯特凡妮小姐的恋情.这导致了他的早亡.这次恋爱事件不知何故引出了一场决斗.,12,1832年5月29日,决斗的前夜,伽罗华写了封很长的信给他的朋友舍瓦利耶(A.Chevalier),其中大致描述了他的数学理论,从而给数学界留下了唯一一份它将蒙受何等损失的提要.在第二天的决斗中(离25步远用手枪射击),伽罗华的胃部中弹,24小时后去世.享年不足21岁.伽罗华留给世界的最核心的

6、概念是(置换)群,他成了群论以至近世代数的创始人.,13,Galois(18111832)-近世代数的创始人,Born:25 Oct 1811 in Bourg La Reine(near Paris),France Died:31 May 1832 in Paris,France,14,近世代数的特点-抽象代数系统：群环域格布尔代数,离散数学II,15,第六章 群 与 环,16,6.1 代 数 系 统,代数运算的定义 代数运算的性质 代数系统的定义,17,设S是一个非空集合，称SS到S的一个映射f为S的一个二元代数运算，即，对于S中任意两个元素a、b，通过f，唯一确定S中一个元素c：f(a,

7、b)=c，常记为a*b=c。注：代数运算是闭运算。该运算具有很强的抽象性，不限于+，-，*，/，意义很广泛。类似地，可定义S的n元代数运算：Sn到S的映射。,1.代数运算的定义,18,例：,S=a,b，则SS=(a,a),(a,b),(b,a),(b,b)映射f为：(a,a)-a(a,b)-a(b,a)-b(b,b)-b f称为S的一个二元代数运算，有 f(a,a)=a f(a,b)=a f(b,a)=b f(b,b)=b也可表示为：a*a=a,a*b=a,b*a=b,b*b=b,19,加法和乘法是自然数集N上的二元代数运算；减法和除法不是N上的二元代数运算。加法、减法、乘法都是整数集Z上的二

8、元代数运算；除法不是Z上的二元代数运算。乘法、除法是非零实数集R*上的二元代数运算；加法和减法不是R*上的二元代数运算。,例：,20,矩阵加法和乘法是n阶实矩阵集合上的二元代数运算。设S是一个非空集合，(S)是S的幂集，则、是(S)上的二元代数运算。、都是真值集合0,1上的二元代数运算。,例：,例：S=a,b,(S)=a,b,a,b,21,设*是集合S上的二元代数运算，如果对于任意a,bS，a*b=b*a都成立，则称运算*满足交换律。例：设Q为有理数集合，对任意a,bQ,定义Q上的运算如下：ab=a+b-ab，则是Q上的二元代数运算，且满足交换律：ab=a+b-ab=b+a-ba=ba,2.代

9、数运算的性质-交换律,22,设*是集合S上的二元代数运算，如果对于任意a,b,cS,(a*b)*c=a*(b*c)都成立，则称运算*满足结合律。例：设A是一个非空集合，对任意a,bA，定义A上的运算如下：ab=b，则是A上的二元代数运算，且满足结合律：(ab)c=bc=ca(bc)=ac=c,2.代数运算的性质-结合律,23,设*是集合S上的二元代数运算，a是S中的元素，如果a*a=a,则称a是关于运算*的幂等元。如果S中每个元素都是关于*的幂等元，则称运算*满足等幂律。结论：若a是关于运算*的幂等元，则对于任意正整数n，an=a。,2.代数运算的性质-等幂律,24,设*和+是集合S上的两个二

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

11、*和+是集合S上的两个二元代数运算，如果对于任意a,bS,a*(a+b)=a，a+(a*b)=a，都成立，则称运算*和+满足吸收律。例：定义自然数集合N上的运算*和+如下：对于任意a,bN,有a*b=maxa,b,a+b=mina,b，则*和+是N上的二元代数运算，且满足吸收律。a*(a+b)=maxa,mina,b=a a+(a*b)=mina,maxa,b=a,2.代数运算的性质-吸收律,27,设*是集合S上的二元代数运算，如果S中存在元素，使得对于S中任意元素a，都有a*=，*a=，则称是S上关于运算*的零元。设*是集合S上的二元代数运算，对于S中任意三个元素a,b,c，其中a不等于零元

12、，如果有：(1)若a*b=a*c，则b=c，(2)若b*a=c*a，则b=c，就称*满足消去律。,2.代数运算的性质-消去律,28,n阶实矩阵集合上的加法满足消去律，但乘法不满足消去律。因为：但,例：,29,整数集Z上的加法、乘法都满足结合律和交换律，乘法对加法满足分配律，但加法对乘法不满足分配律；减法不满足结合律，也不满足交换律；都不满足等幂律，也不满足吸收律。n阶实矩阵集合上的加法满足结合律，也满足交换律；乘法满足结合律，但不满足交换律；它们都不满足等幂律，也不满足吸收律。,例：,(a-b)-ca-(b-c)例：(5-2)-15-(2-1),(ab)+c(a+c)(b+c)例：(34)+2

13、(3+2)(4+2),30,设(S)是非空集合S的幂集，则(S)上的交运算、并运算都满足结合律、交换律；对、对都满足分配律；它们都满足等幂律；也满足吸收律；但、不满足消去律。,例：,对任意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。,31,设S是一个非空集合，f1,fm是S 上的若干代数运算，把S及其运算f1,fm看成一个整体来看，叫做一个代数系统，记为(S,f1,fm)。,3.代数系统的定义,32,设S是一个非空集合，(S)是S的幂集，则(S),)为代数系统。设、是真值集合0,1上的合取与析取运算，则(0,1,)是代数系统。,例：,33,设Z为整数集，Z0为偶数集，N为自然数集，+、是数的加法和乘法，则(Z,+)、(Z,)、(Z,+,)、(Z0,+)、(Z0,)、(Z0,+,)、(N,+)、(N,)、(N,+,)都是代数系统。设、分别表示求最大公约数和求最小公倍数的运算，那么(Z,)、(Z0,)、(N,)都是代数系统。,例：,