离散数学的代数理论

2020/2/22zhengjin,csu1第六章代数代数:也叫代数结构，或代数系统，是指定义有若干运算的集合。如整数集合，在其上定义了加法、乘法，就成为一个代数系统。抽象代数：1.不关心代数系统的具体集合是什么2.不关心集合上的运算如何定义3.假设这些运算满足某些规则(如结合律，交换律，分配律等)，然后根据这样的抽象代数系统，来讨论该系统应具有的性质，使所得结论具有普遍意义。2020/2/22zhengjin,csu2本章主要内容1.代数的基本概念，如代数的构成、代数的表示、代数的特异元素；子代数的概念(6.1,6.2)2.代数间的同构、同态概念，同态象的概念(6.3)3.一种特殊的等价关系—同余关系,商代数(6.4,6.5)4.特殊的代数：半群，独异点,群(6.6,6.7)5.特殊的代数：环和域(6.8)2020/2/22zhengjin,csu3代数的结构代数由3部分构成：1.一个集合--（代数的载体）2.定义在载体上的运算3.载体中的特异元素，叫做代数的常数（么元和零元）代数通常用载体、运算和常数的n重组表示通俗地说：代数就是由集合及定义在其上的运算及相关常数组成。2020/2/22zhengjin,csu4载体与载体上的运算（１）运算的概念具有一定的广泛性与抽象性，它不仅包括日常用的“+”，“-”，“×”，“/”等运算，也包括抽象的运算，如集合的“并”，“交”，字符串的“并”等。（２）在集合S上的运算可以有多个，如在实数域上的“+”，“×”。运算可以是一元的，也可以是二元的，也可以是多元的。即是从Sm到S的函数。但一般代数系统在S上的运算最多不超过三个，而且以研究一元、二元为限。2020/2/22zhengjin,csu5运算的表示naaa21)(~)(~)(~21naaaia)(~ia),(),(),(),(),(),(),(),(),(212221212111nnnnnnaaaaaaaaaaaaaaaaaanaaa21naaa2175311357ia)(~ia753173717535753375317531例如:A={1,3,5,7},定义一种一元运算~和二元运算*表示如下:2020/2/22zhengjin,csu6载体上的运算（３）运算符的表示：“”或“*”、“△”等。有时也用“+”，“×”等表示。但此时“+”，“×”的含义不一定就是普通算术运算中的“加”与“乘”的含义，所有这些运算符的含义可以根据不同的定义而具有不同的意义。（４）运算在载体S上还应该是封闭的。(载体S中的元素经某一运算后它的结果仍在S中，则此称运算在集合S上是封闭的)2020/2/22zhengjin,csu7代数举例例1整数集，加法和常数0可构成代数：记为：I，+，0例2幂集合ρ(S)，集合的并，交，补运算，常数ф，和S可构成代数。记为：ρ(S)，∪，∩，ˉ，φ，S例3自然数集N，乘法和常数1可构成代数。记为：N,*,1例4自然数集N，乘法、加法和常数0和1可构成代数。记为：N，+,*,0,12020/2/22zhengjin,csu8代数分类通常我们不去研究单个的具体的代数，而是对代数进行分类研究。分类原则如下：1.有相同的构成成分。（即如果两个代数包含同样个数的运算和常数，且对应运算的元数相同，则这两个代数有相同的构成成分。）2.服从相同的公理规则。如：交换律，结合律，分配律，吸收律等。具有相同构成成分和服从相同的公理规则的代数就称为是同种类的。对同一种类的代数，根据它的公理推出的定理对该种类的一切代数都成立。2020/2/22zhengjin,csu9(1)如代数N,.,1和I,-,0有相同的构成成分.(都只有一个运算,且都是二元运算,和1个常数).(2)代数{0,1},۷,۸,0,1和{ρ(S),∪，∩,φ,S(都有两个二元运算,两个常数)2020/2/22zhengjin,csu10公理规则例3：对于自然数集N，及定义其上的加法运算+，构成的代数：N，+，0服从公理规则：a+b=b+a交换律(a+b)+c=a+(b+c)结合律a+0=a0是么元（单位元）则：I，•，1和ρ(S)，∪，φ等是和其同一类的代数(因为都只有一个二元运算，都满足交换律，结合律，一个常数是么元)。2020/2/22zhengjin,csu11公理规则例4考虑具有I，+，·，-，0,1形式构成成分和下述公理的代数类(+：加法，·：乘法运算，-：一元运算，0和1：常数)(1)a+b=b+a(2)a.b=b.a(3)(a+b)+c=a+(b+c)(4)(a.b).c=a.(b.c)(5)a.(b+c)=a.b+a.c(6)a+(-a)=0(7)a+0=a(8)a.1=a则Q，+，·，-，0,1，R，+，·，-，0,1是与之同一类的代数。2020/2/22zhengjin,csu12么元和零元前面已介绍：代数常数是关于某些运算的特异元素，具体地说就是下面要介绍的么元和零元定义1设*是S上的二元运算，1l是S的元素，如果对S中的每个元素x,有1l*x=x则称1l对运算*的左么元。S中的元素0l,,如果对S中的每一元素x,都有0l*x=0l则称0l是对运算*的左零元。类似地，有右么元和右零元的定义。2020/2/22zhengjin,csu13例5代数A的运算*如下表所示很显然:a是*的左么元a也是*的右么元，b是*的左零元。没有右零元。*abcabcabcbbbccb判断方法：观察运算的行和列：若存在某一行和上边行相同，则其左边的元素就是运算的左么元。若存在某一列与左列相同，则其上方的元素就是运算的右么元。2020/2/22zhengjin,csu14么元和零元的定义定义2设*是S上的二元运算，1是S的元素，如果对S中的每一元素x,有1*x=x*1=x则称元素1对运算*是么元。若0是S中的元素，且对S中的每一元素x，有0*x=x*0=0则称元素0对运算*是零元。2020/2/22zhengjin,csu15例6(1)代数I，·，1,0，·表示乘法，有一个么元1和零元0(2)代数N，+有么元0，但无零元。(3)代数N，min有一个零元0，但无么元。2020/2/22zhengjin,csu16么元和零元的性质定理：设*是S上的一个二元运算，若同时具有左么元a和右么元b，则a=b,a就是么元。证明：由a是左么元知：a*b=b由b是右么元知：a*b=a所以a=b,所以a也是右么元。a就是么元(这个定理说明：如果同时存在左么元和右么元，则二者相等，且就是么元，么元若存在，只有一个)对于零元也有类似结果。定理：设*是S上的一个二元运算，若同时具有左零元a和右零元b，则a=b,a就是零元。2020/2/22zhengjin,csu17逆元如果在一代数中存在么元，则可定义逆元。定义3设*是S上的二元运算，1是对运算*的么元，如果x*y=1,则对运算*，x是y的左逆元，y是x的右逆元，若x*y=1和y*x=1同时成立，则对运算*，x是y的逆元(当然y也是x的逆元)，通常x的逆元记为:x-12020/2/22zhengjin,csu18例7（1）代数A={a,b,c},*的运算*如右表定义：对于运算*：b是么元。a的右逆元是c,c的左逆元是a，b的逆元是b.*abcabcaababcacc2020/2/22zhengjin,csu19逆元的性质（2）代数N，+有么元0，但只有0有逆元，而其它元素都无逆元。(3)代数R，.有么元1，但只有0无逆元，而其它元素都有逆元。其它如例6(P166)(e,f,g)2020/2/22zhengjin,csu20逆元的唯一性定理对于可结合运算*，如果一个元素x有左逆元a和右逆元b，则a=b(即逆元是唯一的)证明：设1是运算*的么元，则a*x=x*b=1由*的可结合性，得：a=a*1=a*(x*b)=(a*x)*b=1*b=b2020/2/22zhengjin,csu21定义4设*是S上的二元运算，a∈S,如果对于每一x、y∈S都满足：如果a*x=a*y或x*a=y*a则有x=y,则称a是可约的或可消去的。2020/2/22zhengjin,csu22定理：设*是S上的可结合运算，如果元素a是可逆的，则a也是可约的.证明：由于a是可逆的，记a的逆元为a-1,设a*x=a*y，于是a-1*(a*x)=a-1*(a*y)而a-1*(a*x)=(a-1*a)*x=xa-1*(a*y)=(a-1*a)*y=y所以x=y，即a是可约的。2020/2/22zhengjin,csu23但反之却不一定成立。即是可约的，则不一定是可逆的。如在整数集I中，对于乘法，除0外的元素都是可约的，但除1之外，都不是可逆的。2020/2/22zhengjin,csu24本节要求掌握代数系统的概念,对运算的封闭性、么元、零元、逆元等相关结论有清晰的理解，给定集合和集合上的运算，能够判断该集合对运算是否封闭,能够通过运算表确定么元、零元、逆元（如果存在的话）。对交换律、结合律、分配律等的表示要十分清楚。给定集合及集合的二元运算表，能够判断运算是否满足交换律、是否满足结合律。掌握可约性的概念和相关结论。2020/2/22zhengjin,csu25本节作业课堂作业：1，5，9,46，7，8，10，112020/2/22zhengjin,csu26课堂练习１．ρ(S)，∪，∩＞对∪运算的单位元（么元）是什么，零元是什么？对∩运算的单位元（么元）是什么？零元是什么？2．(判断)设*是Ｓ上的可结合运算，若a∈S是可逆的，则a也是可约的．反之，也成立．2020/2/22zhengjin,csu276.2子代数以后常研究的代数形式：S，о，△，kо代表二元运算。△表示一元运算，k表示常数。定义1设о和△是集合S上的二元运算和一元运算，S′是S的子集。如果a、b∈S′，一定有aоb∈S′,则称S′对运算о是封闭的。如果a∈S′,一定有△a∈S′,那么S′对△是封闭的。例如：集合S′={1,2,3,4}，对加法不封闭，但对max,min,绝对值运算等是封闭的。2020/2/22zhengjin,csu28定义2设A=S，о，△，k是一代数，如果(1)S′S(2)S′对S上的运算о和△封闭。(3)k∈S′那么A′=S′，о，△，k是A的子代数。子代数的定义例7(1)代数系统E，+，0是I，+，0的子代数。(2)设E：偶数集合，M：奇整数集合，则E，+，0是I，+，0的子代数，但M，+不是I，+的子代数。M,*,1是I,*,1的子代数2020/2/22zhengjin,csu29子代数的有关说法如果A′是A的子代数，那么A′和A有相同的构成成分和服从相同的公理。A的最大子代数是它自己。如果A的常数集合在A的运算下封闭，则它是A的最小子代数。这两种子代数称为A的平凡子代数。其它子代数称为真子代数。2020/2/22zhengjin,csu30课堂练习P1691,22020/2/22zhengjin,csu31两节小结1.掌握代数的概念2.代数的表示(n重组表示）3.两个代数是否是同一种类的条件4.常用到的公理规则(方程式表示)5.会由运算表求代数的运算的(左、右)么元，零元，及逆元。)６．子代数的概念7.可逆与可约两个概念的相互关系.2020/2/22zhengjin,csu326.3同构与同态1.同构世界上存在着很多的代数系统，但有些代数系统，它们之间虽然表面上似乎不相同，但是它们实际上是“相同”的。如两个代数系统:{0,1}，∨与{a,b},*仅仅是元素和运算符的表示形式不同，而它们的实质是一样的。称它们是同构的。∨01010１11*abababbb2020/2/22zhengjin,csu33同构的定义同构的必要条件：(1)它们必须有相同的构成成分。（2)它们的载体的元素“个数”要相同。(