代数系统Mathematical Structure或Mathematical System 关于代数系统与计算机科学的关系为什么抽象代数是计算机科学的理论基础之一？1）抽象代数研究的对象与计算机科学研究的对象都是一般的通用客体2）代数系统为计算机系统（包括理论系统、计算机系统组成的结构、工具与环境系统的结构、应用系统的结构、系统的结构分类以及它们之间的关系等）提供必要的理论模型；3）不论是计算机科学的基础学科、技术学科和应用学科，还是计算机科学的边缘学科，抽象代数都给它们提供了最基本的思维方法代数系统和以前我们所了解的代数学有什么不同？1）对象：以前的代数学中研究的对象都是数（实数和复数）或用字母表示的数；代数系统研究的对象是某集合元素的总体，甚至有时并不指出这个集合是什么，也不指出集合中是元素是什么；2）运算：以前的代数学中研究的运算是数的四则运算；而代数系统研究的对象不仅仅是加、减、乘、除四则运算，而是满足一定抽象条件的运算，有时也不指出具体的运算是什么；3）两者的关系：以前我们所了解的代数只是代数系统的一个特例。
代数系统究竟是什么？定义一个代数系统时，并不是一个具体的代数系统，而是满足一定抽象条件的一类代数系统的总体，因此，研究的是代数系统的总体结构，提出一个同属于某一大类的所有代数结构的理论模型。
如果对代数系统的对象和运算进行不同的解析，只要在这个解析下可满足这种抽象的结构，则形成一个具体的代数系统。
代数系统和计算机有什么关系？计算机是一个通用的计算模型，其通用性在于：任何一个可计算的问题，如果问题本身是有结果的（例如，最后总可以回答“是”或“非”的），只要不考虑时间和空间的可能性，原则上都可以在计算机上得到结果。
计算机的结构也是一个通用结构。
只要根据某具体需求解的问题，而对计算机系统的对象（数据模型）和运算（所做的操作）进行解析，则计算机系统就成为解决这个问题的具体理论模型。
代数系统的思维方法如何决定计算机科学的思维方法？代数系统的基本思维方法是构造的方法和公理的方法。
1．构造的方法是提供一个由原生概念开始来构造整个理论系统的方法：第一步：确定所研究的对象，指出由已知概念产生新的概念的过程、规则和方法，如由集合的概念产生元素、空集、有限集等；第二步：定义作用于对象的操作，如并集、交集、幂集等；第三步：对所定义的操作进行分析，研究这些操作的性质，如封闭性、交换率、结合率等；第四步：讨论分类问题以及系统和系统之间的关系问题，如同态？同构？第五步：讨论较高层次的理论问题和哲学问题，例如，存在性、唯一性、完全性、协调性等。
2．公理的方法不象构造的方法那样去定义具体的对象和去定义具体的操作，而是用抽象的符号表示对象和操作，提出一系列的断言，那么所研究的系统只是满足这些断言的系统。
例如研究“群”时，首先给出集合和运算，但集合和运算并非具体给出，只要满足四个断言（封闭性、结合率、存在单位元、存在逆元）的所有集合和运算所构成的代数系统就是群。
3．在计算机科学中，语言代数的建立利用了构造方法和公理方法。
现代许多有关计算机系统的生成方面的问题，也非常注重生成的方法，往往以构造的方法和生成的方法为基础。
讨论代数结构是从最基本的概念开始，代数结构中的一切概念都是从集合出发，通过构造的方法和公理的方法而得到。
这个过程是计算机科学的基本思维方法之一——基于离散结构的构造性思维方法。
代数系统复习大纲1．理解：1）为什么要引入代数系统？在更抽象的层次上寻找不同数学分支的共性；2）代数系统的研究对象：某集合元素的总体；代数系统的运算：满足一定抽象条件的运算；3）代数系统实质上是：在集合上定义若干运算而形成的系统；2．定义封闭：思考：加法在自然数集、整数集、实数集上封闭吗？减法呢？定义代数系统：< A ; f1,f2,…,f n>必须同时满足三个条件：1）一个非空集合A2）建立在A上的若干运算f1,f2,…,f n3）这些运算对A封闭3．二元运算及性质：{ 注意：这里的* 号并不表示乘法，可以任意定义} 设* 是定义在A上的二元运算，* 的性质定义如下：1）封闭：运算*在A上是封闭⇔∀x , y ∈ A ，有x*y ∈ A2）可交换⇔∀x , y ∈ A ，x*y = y*x3）可结合⇔∀x , y , z ∈ A ，(x*y)*z = x*(y*z)注意：判断一个运算是否可结合，必须用三个变元！4）可分配：△对★是可分配的⇔∀x , y , z ∈ A ，x△(y★z) = (x△y)★(x△z) (左可分配)(y★z)△x = (y△x)★(z△x) (右可分配) 注意：（1）可分配必须是左可分配且右可分配同时成立（2）△对★是可分配的≠★对△是可分配的5）可吸收：△和★满足吸收率⇔△、★是可交换的，而且∀x , y ∈ A ，x△(x★y) = x 且x★(x△y) = x 6）等幂⇔∀x ∈ A ，x*x = x ( 有时也叫幂等)注意：等幂意味着：对于任意正整数m、n ，x m = x n7）单位元（幺元）⇔ A中的一个元素e ，同时是运算*的左幺元和右幺元运算*的左幺元e ⇔∀x ∈ A ，e*x = x运算*的右幺元e ⇔∀x ∈ A ，x*e = x运算*的幺元(单位元) e ⇔∀x ∈ A ，x*e = e*x = x注意：（1）幺元不一定存在（例如，代数系统<R , ->没有幺元）（2）不同的运算有不同的幺元或者说，幺元依赖于运算（初等代数中，乘法的幺元是1，加法的幺元是0）（3）对于一个二元运算，左右幺元可能都有、可能只有一个、也可能不存在（4）只有当左、右幺元都存在并且相等时，才有幺元（5）存在左幺元、右幺元，则一定存在幺元（6）幺元若存在，必唯一8）零元：⇔ A中的一个元素θ，同时是运算*的左零元和右零元运算*的左零元θ⇔∀x ∈ A ，θ*x=θ运算*的右零元θ⇔∀x ∈ A ，x*θ=θ运算*的零元θ⇔∀x ∈ A ，x*θ=θ*x =θ注意：（1）零元不一定存在（例如，代数系统<R , +>没有零元）（2）不同的运算有不同的零元或者说，零元依赖于运算（数理逻辑中，与的零元是F，或的零元是T）（3）对于一个二元运算，左右零元可能都有、可能只有一个、也可能不存在（4）只有当左、右零元都存在并且相等时，才有零元（5）存在左零元、右零元，则一定存在零元（6）零元若存在，必唯一（7）是非空集合A上的二元运算，若A有不止一个元素，并且运算同时存在幺元和零元，则幺元一定不等于零元9）逆元：二元运算*存在幺元e ，若a,b∈A ，且a*b = e ，则称a是b的左逆元，b是a右逆元，若a*b = b*a = e ，则称a是b的逆元注意：（1）a是b的逆元⇔ b是a的逆元⇔ a、b互逆⇔ a = b-1⇔ b = a-1（2）一个元素的逆元可以是自己（3）对于同一个运算，有些元素有逆元，有些元素可能没有逆元（初等代数中，乘法的幺元是1，2的逆元是0.5，1的逆元是1，0没有逆元）（4）对于某个运算，一个元素的左逆元可以不等于右逆元（5）对于某个运算，一个元素的左、右逆元，可以只有其中的一个，可以两个都有，也可以一个都没有（6）对于某个运算，一个元素的左（右）逆元可以不唯一（7）在某些条件下，逆元是唯一的4．有关运算表的题型：1）从运算表中查看二元运算的性质2）给出集合、二元运算，构造出运算表，一个集合加一个二元运算——半群、独异点、群5．一个代数系统< S,*>，其中S是非空集合，*是S上的二元运算，1）如果*是封闭的，则代数系统< S,*>是广群2）如果*是封闭的，而且*是可结合的，则代数系统< S,*>是半群3）如果< S,*>是半群，B⊆S且*在B上是封闭的，则< B,*>是半群，是< S,*>的子半群4）如果< S,*>是半群，且*是可交换的，则代数系统< S,*>是可交换半群5）含有幺元的半群称为独异点6．相关的定理：1）有限集对应的半群一定有等幂元；2）独异点的运算表中任何两行或两列都不同；3）独异点的元素a,b若有逆元，则(a-1)-1=a 且(a*b)-1=b-1*a-1应用题型：1）当须证明某些代数系统具有以上性质时，可先证明该代数系统是半群或独异点2）证明某个代数系统是半群或独异点：方法一：根据定义，逐项代入判别；方法二：利用同态的性质，见同态部分3）已知代数系统是半群或独异点，利用其性质，证明某些结论7．代数系统<G,*>中，G是非空集合，*是G上的二元运算，若①运算*是封闭的（满足①是广群）②运算*是可结合的（满足①②是半群）③存在幺元e （满足①②③是独异点）④对于每一个元素x∈G，存在其逆元x-1 （满足①②③④是群）可见，{广群} ⊃ {半群} ⊃ {独异点} ⊃ {群}<G,*>是有限群⇔ G是有限集；集合G的基数（G的元素个数）叫有限群的阶数<G,*>是无限群⇔ G是无限集<G,*>是群，S⊆G且S非空，若<S,*>是群，<S,*>是<G,*>的子群<S,*>是<G,*>的子群，若S={e}或S=G，称<S,*>是<G,*>的平凡子群8．群<G,*>的性质：1）群中不存在零元（群的阶等于1、大于1要分开讨论）2）群上的方程a*x = b 和b*x = a（a,b∈G）在群内都有唯一解（先找到解，例如x=a-1*b，再证明其唯一性）3）群满足消去率：∀a,b,c∈G，如果有a*b=a*c或b*a=c*a，则必有b=c （因为a有逆元）注意：若*不可交换，则a*b= c*a，不一定有b=c4）群的运算表中的每一行或每一列都是G元素的一个置换（由消去率推出）5）除单位元外，群不存在幂等元（由消去率推出）6）群的幺元必定是其子群的幺元（因为子群的幺元是该群的幺元）7）（*供参考）G的非空有限．．．．子集B对*封闭，则<B,*>是<G,*>的子群证明方法：有幺元、任一元素有逆元8）（*供参考）G的非空子集．．．．S．（有限或无限），若∀a,b ∈S，a*b-1∈S，则<S,*>是<G,*>的子群证明方法：有幺元、任一元素有逆元、封闭、可结合应用题型：群（子群）的判别方法：1）根据定义，四个条件逐一验证（此题型属于一定要掌握的）2）（*供参考）利用上面的性质7）、8）9．同态homomorphism、同构isomophism：两个代数系统之间的关系1）<A,★>、<B, △>是两个代数系统，f是从A到B的一个映射，并且∀a,b∈A，f (a★b) = f (a)△f (b) ，则称f是从<A,★>到<B, △>的同态映射<A,★>同态于<B, △>，表示为A~B注意：（1）任意两个代数系统之间不一定同态（即不一定存在同态映射）（2）即使两个代数系统之间同态，其同态映射也不一定唯一（3）研究同态的意义在于：在代数系统之间建立关系，把一个代数系统的某些特征转移到另一个代数系统，简化问题，或对不同的代数系统就某些特征进行分类研究2）f是从<A,★>到<B, △>的一个同态，则：f 是满射⇔ f 是满同态f 是入射⇔ f 是单一同态f 是双射⇔ f 是同构映射，记为A ≅ B注意：（1）任意两个同态的代数系统不一定同构（即同态映射不一定是双射）（2）两个代数系统之间的同构映射可以不唯一（3）同构映射的逆也是同构映射（定义域、值域调转）（4）同构不但使两个代数系统具有相同的基数（集合的元素个数），而且对运算保持相同的性质：1》同构保持了结合率、交换率、幂等率；严格的描述：若代数系统<A,★>满足结合率，且f是从<A,★>到<B, △>的同构映射，则<B, △>也满足结合率；2》同构使两个系统同时存在幺元（零元、逆元），并且两个系统中的幺元（零元、逆元）通过同构映射相对应；严格的描述：若代数系统<A,★>存在幺元e1，且f是从<A,★>到<B, △>的同构映射，则<B, △>也存在幺元e2，且f (e1)=e2 （5）研究同构的意义在于：对形式上不同的代数系统，抽象出本质共性，或者说，同构的系统本质上是相同的（6）代数系统之间的同构关系是等价关系有关同构的习题：（书上的这类题目极少，但其他参考书比较多，归纳如下：）（1）判断两个代数系统是否同构的方法（不是严格的证明）：1》集合的基数是否相同；2》运算是否同时满足交换率、结合率、幂等率；3》幺元、零元、逆元是否同时存在，并且相对应；（2）证明两个代数系统同构的方法：1》根据定义，找出同构映射f ：<A,★>和<B, △>是两个代数系统，找出从A到B的映射f ，证明：①f是双射②∀a,b∈A，f (a★b) = f (a)△f (b)所以，<A,★>与<B, △>同构2》这两个代数系统同时与另外一个代数系统同构因为同构关系是等价关系，有传递性（3）证明两个代数系统不同构的方法：1》集合的基数不同；2》运算的性质不同（不同时满足交换率、或结合率、或幂等率，等）；3》特殊的元素（幺元、零元、逆元）不同时存在，或没有对应关系；4》设存在同构映射f ，由具体的元素、具体的运算，得出f 不是双射5》设存在同构映射f ，由具体的元素、具体的运算，得出与原集合或运算矛盾的结果；3）f是从<A,★>到<A,★>的同态⇔ f 是自同态f是从<A,★>到<A,★>的同构⇔ f 是自同构1）f是从<A,★>到<B, △>的一个同态映射，则f (A) ⊆ B，且<A,★>是半群⇒<f (A),△>也是半群<A,★>是群⇒<f (A),△>也是群<A,★>是独异点⇒<f (A),△>也是独异点。