离散数学PPT教学代数系统.ppt

欢迎进入 离 散 数 学 第 七章 代 数系统,近世代数,第七章 代数系统,7.1 代数系统的引入,前言,7.2 运算及其性质,结束,前言,为什么要研究代数系统？代数是专门研究离散对象的数学，是对符号的操作。它是现代数学的三大支柱之一（另两个为分析与几何）。代数从19世纪以来有惊人的发展，带动了整个数学的现代化。随着信息时代的到来，计算机、信息都是数字（离散化）的，甚至电视机摄像机、照相机都在数字化。知识经济有人也称为数字经济。这一切的背后的科学基础，就是数学，尤其是专门研究离散对象的代数。代数发端于“用符号代替数”，后来发展到以符号代替各种事物。在一个非空集合上，确定了某些运算以及这些运算满足的规律，于是该非空集合中的元素就说是有了一种代数结构。现实世界中可以有许多具体的不相同的代数系统。但事实上，不同的代数系统可以有一些共同的性质。正因为此，我们要研究抽象的代数系统，并假设它具有某一类具体代数系统共同拥有的性质。任何在这个抽象系统中成立的结论，均可适用于那一类代数系统中的任何一个。,抽象代数学在计算机中的应用,代数学历史悠久。代数的发展可分成两个阶段。19世纪这前的代数称为古典代数，19世纪至今的代数称为近世代数（抽象代数）。抽象代数学的研究对象是抽象的，它不是以某一具体事物为研究对象，而是以一大类具有共同性质的事物为研究对象。因此其研究成果适用于这一类事物中的每一个，从而收到事半功倍之效。抽象代数学的主要内容是研究各种各样的代数系统。它把一些形式上很不相同的代数系统，用统一的方法描述、研究和推理，从而得到反映出它们共性的一些本质的结论，然后再把这些结论应用到具体的代数系统中。,抽象代数学在计算机中的应用,抽象代数的概念和方法也是研究计算科学的重要数学工具。有经验和成熟的计算科学家都知道，除了数理逻辑处，对计算科学最有用的数学分支学就是代数，特别是抽象代数。抽象代数是关于运算的学问，是关于计算规则的学问。在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而抽象世代数研究的中心问题就是一种很重要的数学结构-代数系统：半群、群、格与布尔代数等等。计算科学的研究也离不开抽象代数的应用：半群理论在自动机理论和形式语言中发挥了重要作用；有限域理论是编码理论的数学基础，在通讯中起过重要的作用；至于格和布尔代数则更不用说了，是电子线路设计、电子计算机硬件设计和通讯系统设的重要工具。另外描述机器可计算的函数、研究算术计算的复杂性、刻画抽象数据结构、描述作为程序设计基础的形式语义学，都需要抽象代数知识。,学习本章的方法,1、要按照数学的思维方式学习,即观察客观世界,抽象出模型,再分析、推理揭示内在规律的过程。2、领会“抽象”性：代数的抽象性不仅体现在元素的抽象上,还体现在相应运算的抽象上,是在最纯粹的形式下研究代数结构中的运算的规律与性质,从运算的角度来考虑代数结构中的元素。因此,初等代数的相应概念、结论不能直接应用在抽象代数中。如何跨越从直观到抽象是学习抽象代数的重要一步。3、教材的基本思路是：首先严格定义什么是代数结构,并讨论一般代数结构的基本性质。然后讨论代数结构研究的两个方面：其一是通过一些基本性质来规定一类特定的代数结构,并对这类代数结构的性质进行研究。其二是研究代数结构之间的各种关系,通过对代数结构之间关系的研究,就可以把一个代数结构中的某些性质推广到另一个代数结构中。,学习本章的方法,4、结合具体例子与应用来理解抽象代数的概念与结论,特别是“抽象”的概念,在理解的基础上熟悉基本概念与重要结论,掌握基本推理方法,领会抽象代数的研究方法,并尝试去解决具体问题。5、抽象代数以代数结构为研究对象，集合论是研究代数结构的基础。而群是抽象代数所研究的最为重要、最为基础的代数结构,也是抽象代数部分的学习重点,学习好群的相关知识,习惯了代数的“抽象”思维,环、域的学习也就相对容易了。6、阅读教材、课堂听讲、反复思考,并独立完成一定数量的习题,只有如此,才能理解抽象代数的概念,掌握有关理论,从而提高分析问题的能力。,7.1 代数系统的引入,代数系统是由一个集合（此集合称为代数的载体）和定义在集合上的运算构成。,注：载体一般是非空集合，,定义在载体上的n元运算是一个从An到B的映射。,例：）取整 X，求绝对值|X|，是一元运算）+,X是二元运算,）if xyandyz then是三元运算,例：整数集，实数集，符号串集合等。,7.2 运算及其性质,一、二元运算,1、运算封闭性：若x，yA，有x*yA，称*在A上是封闭的,例：A=xx=2n，nN，问运算封 闭否，呢？,解：2r，2sA，2r x 2s=2r+sA（）运算封闭 2，4A，2+4A，运算不封闭 2，4A，2/4A，运算不封闭,2、结合律,证：a，b，cA，a*（b*c）=a*c=c(a*b）*c=b*c=c a*（b*c）=（a*b）*c*满足结合律,已知，若x，y，zA，有x*（y*z）=（x*y）*z，称*满足结合律。,例：，若a，bA，有a*b=b 证明：*满足结合律,7.2 运算及其性质,3、交换律,已知，若x，yA，有x*y=y*x，称*满足交换律。,例：设,*定义如下：a*b=a+b-ab，问*满足交换律否？,证：a，bA，a*b=a+b-ab=b+a-ba=b*a*满足交换律。,7.2 运算及其性质,设，若x，y，zA有:x*(yz)=（x*y）（x*z）;(yz)*x=(y*x)(z*x)称运算*在上可分配,例：设A=，二元运 算*，定义如左:,问分配律成立否？,证明：x(y*z)=(xy)*(xz)证：当x=：x(y*z)=;(xy)*(xz)=当x=：x(y*z)=y*z;(xy)*(xz)=y*z注:若找不到规律,对该例则应用8个式子进行验证。,、运算*对运算不可分配,证：*（）=*=（*）（*）=,7.2.1 运算及其性质,4.分配律,例:N为自然数集,x,yN，x*y=maxx，y,xy=minx，y,证明：x，yN，x*（xy）=maxx，minx，y=x xy=x*满足吸收律 x x y x（x*y）=minx，maxx，y=x xy=x 满足吸收律 x x y,7.2.1 运算及其性质,5.吸收律：设，若x，y，zA有:x*(x z)=x 称运算*满足吸收律;x(x*y)=x；运算 满足吸收律,试证：*，满足吸收律,已知A，*，若xA，x*x=x 则称*满足等幂律,例：已知集合s,（s）,则,满足吸 收律，等幂律,7.2 运算及其性质,6.等幂律,7.2 运算及其性质,二、么元（单位元）和零元,1、定义:,设*是s上二元运算，er，eI，r，e，s，有.若xs，有el*x=x，称el为运算*的左么元若xs，有x*er=x，称er为运算*的右么元,.若xs，有l*x=l，称l为运算*的左零元 若xs，有x*r=r，称r为运算*的右零元,.若xs，有e*x=x，x*e=x称e为运算*的么元 若xs，有*x=x*=，称为运算*的零元,例：代数A=a，b，c，。用下表定义：,则b是左么元，无右么元,a是右零元，b是右零元，无左零元;,二、么元（单位元）和零元,运算。既不满足结合律，也不满足交换律。,例:a）I，x，I为整数集则么元为1，零元为0,二、么元（单位元）和零元,b）（s）,对运算，是么元，s是零元，对运算，s是么元，是零元。,c）N，+有么元0，无零元。,2、性质、Th1:设*是s上的二元运算，满足结合律，具有左么元el，右么元er，则el=er=e证明：er=el*er=el,二、么元（单位元）和零元,推论：二元运算的么元若存在则唯一 证明：反证法：设有二个么元e，e；则e=e*e=e,、Th2:设*是s上的二元运算，具有左零元ol，右零元or，则ol=or=o,推论：二元运算的零元若存在则唯一,三、逆元 1、逆元定义 设*是s上的二元运算，e是运算*的么元,7.2 运算及其性质,、若x*y=e那对于运算*，x是y的左逆元，y是 x的右逆元,、若x*y=e，y*x=e，则称x是y的逆元，y的逆 元通常记为y-1，存在逆元(左逆无，右逆元）的元素称为可逆的（左可逆的，右可逆的）,例：a)、代数 N，+中仅有么元0，有逆元0，R，*中，除零元0外所有元素均有逆元,b)、A=a，b，c，*由下表定义：,b是么元,a的右逆元为c，无左逆元，b的逆元为b，c的右逆元为空，左逆元为a,三、逆元,d）A=0，1，2，k-1，k 模k乘法k定义如下：x ky=x y x y k x y-n k x yk,n0,1，则有些元素存在逆元，有些元素无逆元 当且仅当x与k互质时，x有逆元,三、逆元,Th3:对于可结合运算，如果元素X有 左逆元，右逆元r，则l=r=x,推论：逆元若存在，则唯一,证：=（xr）=（x）逆元存在为r 若存在X的另一个逆元r;则:r r=r(xr)=(rx)r=r r,三、逆元,2、逆元的性质,四、同态和同构,一、同态 1、定义：满同态：单一同态：二、同构 1、定义：,五、同余关系六、积代数七、商代数,谢 谢 使 用,