离散数学--代数系统

计算机科学学院刘芳2019/12/201第三部分代数结构引言代数系统群与环格与布尔代数计算机科学学院刘芳2019/12/202引言数学的三大核心领域代数学：数学中研究数的部分几何学：数学中研究形的部分分析学：沟通形与数且涉及极限运算的部分总体来说：数学的三大类数学构成了整个数学的本体与核心。在这一核心的周围，由于数学通过数与形这两个概念，与其它科学互相渗透，而出现了许多边缘学科和交叉学科。现在已经拥有100多个主要分支学科。计算机科学学院刘芳2019/12/203引言代数学代数学是建立在集合论基础上以代数运算为研究对象的学科。其范畴包括：算术、初等代数、高等代数、数论、抽象代数代数学发展的4个阶段:1文字叙述阶段2简化文字阶段3符号代数阶段4结构代数阶段一门科学的历史是那门科学中最宝贵的一部分，因为科学只能给我们知识，而历史却能给我们智慧。计算机科学学院刘芳2019/12/2041文字叙述阶段文字叙述阶段尚未形成任何简化的符号表达法；代数运算法则都是采用通常的语言叙述方式来表达；代数推理也都采用直观的方法。古代中国:算筹法算筹计数筹算开方法（九章算术）计算机科学学院刘芳2019/12/2051文字叙述阶段而古希腊则借助于几何图形的变换方法最典型的代表是毕达哥拉斯(Pythagoras公元前585—497)几何数论方法。1+3+5+……+(2n-1)=n2不要认为简单的几何图形变换只能产生简单的代数结论，恰当地利用几何图形的变换有时也会产生重要的代数结论计算机科学学院刘芳2019/12/2062简化文字阶段简化文字阶段古希腊数学后期，数学家丢番图（Diophantus,公元250年）才开始把通常的语言叙述作简化，利用简化的文字符号代替一些相对固定的代数表达式。《算术》使用简化文字符号12345678910：平方：（希腊文幂”字为dumamis(△YNMIS)）立方：(立方的希腊文为kubos(KYBOS))计算机科学学院刘芳2019/12/2073符号代数阶段符号代数阶段用字母表示数，这一过程使代数学达到了现在我们看到的这种符号演算形式。代数学不再停留在具体的数字计算，有了真正意义的数学公式、运算法则，并由此进化为现代数学符号系统、现代数学公理系统。代表数学家德国数学家M.Stiefel(1486-1567)1553《综合算术》;用10进制小数表示实数法国数学家F.Viete(1540-1603)是第一个系统使用字母表示数的人，韦达在代数方程、三角学等许多方面都作了杰出的贡献。计算机科学学院刘芳2019/12/2084结构代数阶段结构代数（抽象代数、近世代数）代数学的研究对象不再是个别的数字运算，而是抽象的运算系统(如群、环、域等)的代数结构。事实上不管是连续的还是离散的数学结构，常常是对研究对象（自然数,实数,多项式,矩阵,命题,集合,图等）定义种种运算（加,减,乘;与,或,非；交,补等）然后讨论这些对象及运算的有关性质。计算机科学学院刘芳2019/12/2094结构代数阶段代数系统由集合和集合中的一个或多个运算所组成的系统（即数学结构），称为代数系统，又称代数结构或抽象代数，它是用代数的方法构造出来的数学模型。代数系统的应用自动机理论编码理论形式语义学密码学等计算机科学学院刘芳2019/12/2010第9章代数系统9.1二元运算及性质9.2代数系统计算机科学学院刘芳2019/12/20119.1二元运算及其性质9.1.1运算的定义9.1.2运算的表示方法9.1.3二元运算的主要性质9.1.4二元运算的特殊元素小结计算机科学学院刘芳2019/12/20129.1.1运算的定义定义9.2(P166)设S是一个集合，函数f:S→S称为S上的一个一元运算，简称为一元运算。例如：Z,Q和R上求相反数的运算非零有理数集Q*，非零实数集R*上求倒数运算复数集合C上求共轭复数的运算幂集P(S)上,全集为S，求绝对补运算~在Mn(R)(n≥2)上求转置矩阵计算机科学学院刘芳2019/12/20139.1.1运算的定义定义9.1(P165)设S是一个集合，函数f:S×S→S称为S上的一个二元运算，简称为二元运算。问题：如何验证一个运算是否为S上的二元运算？S中任意两个元素可以进行这种运算，且结果唯一。S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。计算机科学学院刘芳2019/12/20149.1.1运算的定义例9.1(P165)N上的＋、×Z上的＋、－、×R*上的×、／Mn(R)上的矩阵加法和乘法P(S)上的∪、∩、－、一般地：函数f:Sn→S称为S上的一个n元运算。计算机科学学院刘芳2019/12/20159.1.2运算的表示方法1.函数解析式f(x1,x2,……,xn)2.算符用○·*等符号表示n元运算，称为算符。几种形式，如：前缀形式:○(x1,x2,…,xn)中缀形式:x1○x2○…○xn后缀形式:(x1,x2,…,xn)○计算机科学学院刘芳2019/12/20169.1.2运算的表示方法3.运算表设S={a1,a2,…,an}，S上的一／二元运算可以用运算表的形式给出：ai○aia1○a1a2○a2…………an○an○a1a2…ana1a1○a1a1○a2…a1○ana2a2○a1a2○a2…a2○an……………anan○a1an○a2…an○an计算机科学学院刘芳2019/12/20179.1.2运算的表示方法运算表的实例例9.4：A＝P({1,2}),,∼分别为对称差和绝对补运算的运算表（注：{1,2}为全集）{1}{2}{1,2}x∼x{1}{2}{1,2}{1}{2}{1,2}{1}{1,2}{2}{2}{1,2}{1}{1,2}{2}{1}{1}{2}{1,2}{1,2}{2}{1}计算机科学学院刘芳2019/12/20189.1.2运算的表示方法例2：Z5＝{0,1,2,3,4},,分别为模5加法与乘法的运算表。0123401234012340123412340234013401240123012340000001234024130314204321计算机科学学院刘芳2019/12/20199.1.3二元运算的性质定义9.3~9.5设∘为S上的二元运算,如果对于任意的x,yS有x∘y=y∘x,则称运算∘在S上满足交换律.如果对于任意的x,y,zS有(x∘y)∘z=x∘(y∘z),则称运算∘在S上满足结合律.如果对于任意的xS有x∘x=x,则称运算∘在S上满足幂等律.(若S中某些x满足x○x＝x,则称x是运算○的幂等元)。计算机科学学院刘芳2019/12/20209.1.3二元运算的性质例:集合运算Z,Q,R普通加法+普通乘法Mn(R)矩阵加法+矩阵乘法P(B)并交相对补对称差交换律结合律幂等律有有无有有无有有无无有无有有有有有有无无无有有无计算机科学学院刘芳2019/12/20219.1.3二元运算的性质定义9.6~9.7设∘和∗为S上两个不同的二元运算如果对于任意的x,y,z∈S有(x∗y)∘z=(x∘z)∗(y∘z)z∘(x∗y)=(z∘x)∗(z∘y)则称∘运算对∗运算满足分配律.如果∘和∗都可交换,并且对于任意的x,y∈S有x∘(x∗y)=xx∗(x∘y)=x则称∘和∗运算满足吸收律.计算机科学学院刘芳2019/12/20229.1.3二元运算的性质集合运算分配律吸收律Z,Q,R普通加法+与乘法Mn(R)矩阵加法+与乘法P(B)并与交交与对称差集合运算分配律吸收律Z,Q,R普通加法+与乘法对+可分配无+对不分配Mn(R)矩阵加法+与乘法对+可分配无+对不分配P(B)并与交对可分配有对可分配交与对称差对可分配无对不分配计算机科学学院刘芳2019/12/20239.1.3二元运算的性质定义9.7设∘为集合S上二元运算，如果对于任意元素x,y,zS,xθ，都有x∘y=x∘zy=z,y∘x=z∘xy=z成立，则称∘运算满足消去律.例如：1.普通加法和乘法满足消去律2.矩阵加法满足消去律3.矩阵乘法不满足消去律.4.集合的并和交运算也不满足消去律计算机科学学院刘芳2019/12/20249.1.4二元运算的特异元素1.单位元定义9.8：设∘为S上的二元运算,如果存在el（或er）S，使得对任意x∈S都有el∘x=x(或x∘er=x)，则称el(或er)是S中关于∘运算的左(或右)单位元.若e∈S关于∘运算既是左单位元又是右单位元，则称e为S上关于∘运算的单位元（幺元）.计算机科学学院刘芳2019/12/202510.1.4二元运算的特异元素2.可逆元素及其逆元定义9.10令e为S中关于运算∘的单位元.对于x∈S，如果存在yl（或yr）∈S使得yl∘x=e（或x∘yr=e），则称yl(或yr)是x的左逆元(或右逆元).关于∘运算，若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元.如果x的逆元存在，就称x是可逆的.计算机科学学院刘芳2019/12/20269.1.4二元运算的特异元素3.零元定义9.9设∘为S上的二元运算,如果存在θl(或θr)∈S，使得对任意x∈S都有θl∘x=θl(或x∘θr=θr)，则称θl(或θr)是S中关于∘运算的左(或右)零元.若θ∈S关于∘运算既是左零元又是右零元，则称θ为S上关于∘运算的零元.计算机科学学院刘芳2019/12/20279.1.4二元运算的特异元素实例：集合运算Z,Q,R普通加法+普通乘法Mn(R)矩阵加法+矩阵乘法P(B)并交对称差单位元零元逆元0无x的逆元x10x的逆元x1(x-1属于给定集合)无X逆元XEX的逆元X1（X是可逆矩阵）B的逆元为BB的逆元为B无X的逆元为X计算机科学学院刘芳2019/12/20289.1.4二元运算的特异元素单位元的惟一性定理9.1：设∘为S上的二元运算，el和er分别为S中关于运算的左和右单位元，则el=er=e为S上关于∘运算的惟一的单位元.证：∵el=el∘er=er∴el=er,将这个单位元记作e.假设e’也是S中的单位元，则有e’=e∘e’=e.惟一性得证.类似地可以证明关于零元的惟一性定理5.2.计算机科学学院刘芳2019/12/20299.1.4二元运算的特异元素逆元的惟一性定理9.4：设∘为S上可结合的二元运算,e为该运算的单位元,对于x∈S如果存在左逆元yl和右逆元yr,则有yl=yr=y,且y是x的惟一的逆元.证明：由yl∘x=e和x∘yr=e得yl=yl∘e=yl∘(x∘yr)=(yl∘x)∘yr=e∘yr=yr令yl=yr=y,则y是x的逆元.假若y’∈S也是x的逆元,则y’=y’∘e=y’∘(x∘y)=(y’∘x)∘y=e∘y=y所以y是x惟一的逆元.说明：对于可结合的二元运算，可逆元素x只有惟一的逆元，记作x-1.计算机科学学院刘芳2019/12/20309.1.4二元运算的特异元素零元的惟一性定理9.2：设∘为S上的二元运算，θl和θr分别为S中关于运算的左和右零元，则θl=θr=θ为S上关于∘运算的惟一的单位元.证：∵θl=θl∘θr=θr∴θl=θr,将这个单位元记作θ.假设θ’也是S中的单位元，则有θ’=θ∘θ’=θ.惟一性得证.计算机科学学院刘芳2019/12/2031例题分析例：设∘运算为Q上的二元运算，x,yQ,x∘y=x+y+2xy,(1)判断∘运算是否满足交换律和结合律，并说明理由.(2)求出∘运算的单位元、零元和所有可逆元素的逆元.解(1)∘运算可交换.任取x,yQ,x∘y=x+y+2xy=y+x+2yx=y∘x,∘运算可结合，任取x,y,zQ,(x∘y)∘z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyzx∘(