离散数学_第5章_代数系统(学生用)课件.pptVIP

离 散 数 学;第五章 代数结构;代数系统也称为近世代数或抽象代数，是近代数学的重要分支。 法国数学家伽罗瓦〔1811-1832〕在1832年运用「群」的思想彻底解决了用根式求解代数方程的可能性问题，成为近世代数的创始人。 中国数学家在抽象代数学的研究始于30年代。当中已在许多方面取得了有意义和重要的成果，其中尤以曾炯之、华罗庚和周炜良的工作更为显著。 抽象代数学对于全部现代数学和一些其它科学领域都有重要的影响。 ;本章讨论的数学结构就是由集合上定义若干运算而组成的系统——代数系统。 在计算机科学中，研究机器可计算性语言、算法计算的复杂性、刻划抽象的数据结构等等，都需要这现代代数系统知识。 ;代数结构的知识体系;§5.1 代数系统的引入;一元运算 例1：将实数集合R上的每一个数a ≠ 0映射成它的倒数 。 例2：求一个复数的共轭复数（复数集合C上的一元运算）。 二元运算 例3：在集合R上，对任意两个数所进行的普通”+”和”×”。 例4： f：N×N→N，f(x,y)＝x +y 是自然数集合N上的二元运算。 以上运算的共同特征：运算结果都是在原来的集合R或N中。;具有这种特征的运算是封闭的，简称闭运算。相反的，没有这种特征的运算就是不封闭的。 例5：f：N×N→N，f(x,y)＝x - y N对减法不封闭。 例6：自动售货机系统{一元硬币，二元硬币}，* 不封闭 思考：例5例6中的运算封闭吗？ ;封闭定义：对于集合A，一个从An到B的映射，称为集合A上的一个n元运算。如果B?A，则称该n元运算是封闭的。 不是所有的代数系统都是封闭的，但一般情况下，我们总是讨论封闭的代数系统。 ;例：以下哪些运算是封闭的？ (1) 自然数集合N上的减法运算。 (2) 整数集合I上的除法运算。 (3) 设A={1,2,3,…,10},二元运算x*y=质数p的个数，使得x ≤p≤y。;代数系统定义：一个非空集合A，连同若干个定义在该集合上的运算f1,f2,…,fk，所组成的系统就称为一个代数系统，记作A， f1,f2,…,fk 。 例：N,＋,Z,＋,·,R,＋,·都是代数系统,其中+和·分别表示普通加法和乘法。 例：Mn(R),＋,·是代数系统,其中＋和·分别表示n阶(n≥2)实矩阵的加法和乘法。 例：ρ(S),∪,∩,~也是代数系统，其中含有两个二元运算∪和∩以及一个一元运算~。 ;＋3;我们主要讨论同种类代数系统的特性。 例如 ：V1=R, +, ·,0, 1 V2=ρ(B), ∪, ∩, ?, B V1、V2是同类型的代数系统，因为它们都含有2个二元运算，2个代数常数。 在V1中，0对于＋运算，1对于×运算是么元，对于×运算是零元；在V2中?对于∪， B对于∩是么元，而?对于∩ ， B对于∪是零元。 可见， V1、V2的运算性质不同。;本节学习要求;§5.2 运算及其性质;二元运算;封闭性;结合性;【例】在自然数集N上，运算 是不可结合的。 (A) a*b=a+b+3 (B) a*b=min{a,b} (C) a*b=a+2b (D) a*b=a·b(mod 3) 答案为C 容易验证： (a*b)*c=(a+2b)*c=a+2b+2c a*(b*c)=a+2(b*c)=a+2(b+2c)=a+2b+4c ;交换性;分配性;【例】设A={a,b}，二元运算*，△定义如下表，问分配律成立否？ 解：（1）运算△对运算*可分配， 即证：?x,y,z?A，x△(y*z)=(x△y)*(x△z)且 (y*z)△x=(y△x)*(z△x) 证明：当x=a时(△运算结果为左侧运算对象)， 即x△(y*z)=x=a；(x△y)*(x△z)=x*x=x=a； 当x=b时(△运算结果为右侧运算对象) ， 即x△(y*z)=y*z；(x△y)*(x△z)=y*z 又：通过观察△运算表，可以发现△运算满足交换律，所以x△(y*z)= (y*z)△x，且x△y=y△x，x△z=z△x，由于已经证得x△(y*z)=(x△y)*(x△z)成立，所以(y*z)△x=(y△x)*(z△x)亦成立。 （2）运算*对运算△不可分配， 证：∵b*(a△b)=b*a=b，而 (b*a)△(b*b)=b△a=a;吸收律;幂等律;【例】设ρ(s)是集合S的幂集，在ρ(s)上定义的两个二元运算，集合的“并”运算∪和集合的“交”运算∩，验证∪,∩满足幂等律。 证明：对于任意的A∈ρ(s)，有A∪A=A和A∩A=A，因此运算∪和∩都满足等幂律。 【例】普通的加法和乘法不适合幂等律。但0是加法的幂等元（0+0=0），0