离散数学第十二章节代数结构基本概念及性质幻灯片.ppt

第十二章 代数结构概念及性质,12.1 代数结构的定义与例 12.2 代数结构的基本性质 12.3 同态与同构 12.4 同余关系 12.5 商代数 12.6 积代数,12.1 代数结构的定义与例,在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运算这个概念是代数结构中不可缺少的基本概念 定义12.1.1 设S是个非空集合且函数 或 f : Sn →S，则称 f 为一个n元运算其中n是自然数，称为运算的元数或阶当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等注意，n元运算首先是一个函数，其次是个闭运算(所谓闭运算是指：集合上的运算，其运算结果都在原来的集合中，我们把具有这种特征的运算称作封闭的，简称闭运算)封闭性表明了n元运算与一般函数的区别之处此外，有些运算存在幺元或零元，它在运算中起着特殊的作用，称它为S中的特异元或常数运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。

在下面讨论的代数结构中，主要限于一元和二元运算，将用'、┐或ˉ等符号表示一元运算符；用、、⊙、○、∧、∨、∩、∪等表示二元运算符，一元运算符常常习惯于前置、顶置或肩置，如┐x、 、x'；而二元运算符习惯于前置、中置或后置，如：+xy，x+y，xy+ 有了集合上运算的概念后，便可定义代数结构了定义12.1.2 设S是个非空集合且fi是S上的ni元运算，其中i=1，2，…，m由S及f1，f2，…，fm组成的结构，称为代数结构，记作 例：设Z是整数集， “＋”是Z上的普通加法运算，则是一个代数结构 例：设R是实数集 ，“＋”与“×”是实数集R上的普通加法和乘法运算，则是一个代数结构例：我们可以构造下述的一个代数结构： 设有一个由有限个字母组成的集合∑ ，叫字母表，在∑上任意长的字母串，叫做∑上句子或字符串，串中字母的个数m叫这个串的长度，我们假定当一个字的长度m=0时用符号表示，它叫做空串这样我们可以构造一个在∑上的所有串的集合∑* 其次，我们定义一个在∑*上的运算“//”——并置运算或者连接运算，设， ∑*，则 //＝通过并置运算将两个串联成一个新的串，而此联成的新串也在∑*内，这样构造的 是一个代数结构,如果令∑+＝ ∑*－{}，则也是一个代数结构。

这两种代数结构都是计算机科学 中经常要用到的代数结构例：设有一计算机它的字长是32位，它以定点加、减、乘、除及逻辑加、逻辑乘为运算指令，并分别用01，02，…，06表示之则在该计算机中由232有限个不同的数字所组成的集合S以及计算机的运算型机器指令就构成了一个代数结构因此，一个代数结构需要满足二个条件： (1)有一个非空集合S (2) 在集合S上定义的运算一定是封闭的,此外，我们把集合S的基数即|S|，定义为代数结构的基数如果S是有限集合，则说代数结构是有限代数结构；否则便说是无穷代数结构. 有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义：,定义12.1.3 设两个代数结构和，如果fi和gi(1≤i≤m)具有相同的元数，则称这两个代数结构是同类型的 可见，判定两个代数结构是否同类型，主要是对其运算进行考察： ①两个代数结构是否有相同个数的运算符； ②每个相对应的运算符是否有相同的元数例：代数结构与代数结构是相同类型的，因为它们都有一个二元运算符 例：代数结构与的类型是不相同的，因为它们的运算符的个数不同例：设S是非空集合，P(S)是它的幂集对任意集合A，B∈P(S)上的运算和如下: AB =(A－B)∪(B－A) AB = A∩B 则是一代数结构。

因为，显然和是闭运算 与是同类型代数结构的 有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数结构的概念.,定义12.1.4 设是一代数结构，且非空集TS在运算f1，f2，…，fm作用下是封闭的，且T含有与S中相同的特异元，则称为代数结构的子代数 例：设 E是所有偶数所组成的集合，则代数结构是的一个子代数结构 例： 显然，  .,12.2 代数结构的基本性质,所谓代数结构的性质即是结构中任何运算所具有的性质以下我们均假设运算为二元运算 1.结合律 给定，则运算“⊙”满足结合律或“⊙”是可结合的，即 (x)(y)(z)(x,y,z∈S→(x⊙y)⊙z=x⊙(y⊙z)),例12.2.1 给定且对任意a，b∈A有a⊙b=b证明运算“⊙”是可结合的 证明：因为对任意a，b，c∈A (a⊙b)⊙c=b⊙c=c a⊙(b⊙c)=a⊙c=c 故 (a⊙b)⊙c=a⊙(b⊙c) 注意，不是任何代数结构上的运算都满足结合律，如整数集上“－”运算就不满足结合律如：5－(2－1)＝4,但是(5－2)－1＝2.,2.交换律 给定，则运算“⊙”满足交换律或“⊙”是可交换的，即 (x)(y)(x,y∈S→x⊙y=y⊙x)。

例12.2.2 给定，其中Q为有理数集合，并且对任意a，b∈Q有a○b = a + b - a·b，问运算○是否可交换? 证： a○b = a + b - a·b= b + a - b·a ＝ b ○ a ，故运算○是可交换的同样，并不是所有代数结构上运算均满足交换律，如矩阵的乘法就不满足交换律 易见，如果一代数结构中的运算⊙是可结合和可交换的，那么，在计算a1⊙a2⊙···⊙am时可按任意次序计算其值 特别当a1＝a2＝···＝am＝a时，则a1⊙a2⊙···⊙am＝am称am为a的m次幂，m称a的指数 下面给出am的归纳定义：,设有且aS，对于mZ+，其中Z+表示正整数集合，可有： (1) a1=a (2)am+1=am⊙a 由此利用归纳法不难证明指数定律： (1)am⊙an=am+n (2)(am)n=amn 这里，m,nZ+ 类似地定义某代数结构中的负幂和给出负指数定律3.分配律 一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系 给定，称运算⊙对于○满足左分配律，或者⊙对于○是可左分配的，如果有(x)(y)(z)(x,y,z∈S→x⊙(y○z))=(x⊙y)○(x⊙z)) 同理，称运算⊙对于○满足右分配律或⊙对于○是可右分配的，如果有(x)(y)(z)(x,y,z∈S→(y○z)⊙x=(y⊙x)○(z⊙x)),类似地可定义○对于⊙是满足左或右分配律. 若⊙对于○既满足左分配律又满足右分配律，则称⊙对于○满足分配律或是可分配的。

同样可定义○对于⊙满足分配律 由定义不难证明下面定理： 定理12.2.1 给定且⊙是可交换的如果⊙对于○满足左或右分配律，则⊙对于○满足分配律例12.2.3 给定，其中B={0,1}表12.2.1分别定义了运算⊙和○，问运算⊙对于○是可分配的吗？○对于⊙呢？,形如表12.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成当集合S的基数很小，特别限于几个时，代数结构中运算常常用这种表给出其优点简明直观，一目了然 解 可以验证⊙对于○是可分配的，但○对于⊙并非如此因为 1○(0⊙1)(1○0)⊙(1○1) 1 0 1 0 0,4.吸收律 给定，则 ⊙对于○满足左吸收律 :=(x)(y)(x,y∈S→x⊙(x○y)=x) ⊙对于○满足右吸收律 :=(x)(y)(x,y∈S→(x○y)⊙x=x),若⊙对于○既满足左吸收律又满足右吸收律，则称⊙对于○满足吸收律或可吸收的 ○对于 和吸收律类似地定义 若⊙对于○是可吸收的且○对于⊙也是可吸收的，则⊙和○是互为吸收的或⊙和○同时满足吸收律例12.2.4 给定，其中N是自然数集合，⊙和○定义如下： 对任意a，b∈N有a⊙b = max{a，b}，a ○ b = min{a，b}，试证，⊙和○互为吸收的。

证明：不妨假设a＞b a⊙(a○b) = max{a， min{a，b}}= a (a○b)⊙a = max{min{a，b} ，a}= a 故⊙对于○满足吸收律 同理可证， ○对于⊙满足吸收律故⊙和○互为吸收的5.等幂律与等幂元 给定，则 “⊙”是等幂的或“⊙”满足等幂律:=( x)(x∈S→x⊙x=x) 给定且x∈S，则 x是关于“⊙”的等幂元:=x⊙x=x 于是，不难证明下面定理： 定理12.2.2 若x是中关于⊙的等幂元，对于任意正整数n，则xn=x例12.2.5 给定，其中P(S)是集合S的幂集，∪和∩分别为集合的并和交运算验证：∪和∩是等幂的 证：对任意A P(S)，有A∪A=A和A∩A=A，故∪和∩是等幂的6. 幺元或单位元 给定且el，er，e∈S，则 el为关于⊙的左幺元:=( x)(x∈S→el⊙x=x) er为关于⊙的右幺元:=( x)(x∈S→x⊙er=x) 若e既为⊙的左幺元又为⊙的右幺元，称e为关于⊙的幺元亦可定义如下： e为关于⊙的幺元 :=( x)(x∈S→e⊙x=x⊙e=x)定理12.2.3 给定且el和er分别是关于⊙的左、右幺元，则el=er=e且幺元e唯一。

例：实数集R上的代数结构的“×”运算的幺元为1，因为对任意xR有x×1＝1×x＝x而“＋”运算的幺元为0，因为对任意xR有x＋0＝0＋x＝x 例：前面例子中关于串的并置运算，它的单位元素是空串，因为对任一串A，均有 // A = A //  = A7.零元 给定及θl，θr，θ∈S，则 θl为关于○的左零元 :=( x)(x∈S→θl○x=θl) θr为关于○的右零元 :=( x)(x∈S→x○θr=θr) θ为关于○的零元 :=( x)(x∈S→θ○x=x○θ=θ),定理12.2.4 给定且θl和θr分别为关于⊙的左零元和右零元，则θl=θr=θ且零元θ是唯一的 定理12.2.5 给定且|S|＞1如果θ，e∈S，其中θ和e分别为关于⊙的零元和幺元，则θ≠e例：代数结构上的零元是“0”，因为对于任何整数x，均有x×0＝0×x＝0 例：正整数集Z+上的运算“min”，叫“取最小”运算min(a,b)为取a,b的最小者代数结构中对应于运算“min”的零元为18．逆元 给定且幺元e，x∈S，则 x为关于⊙的左逆元:=(y)(y∈S∧x⊙y=e) x为关于⊙的右逆元:=(y)(y∈S∧y⊙x=e) x为关于⊙可逆的 :=(y)(y∈S∧y⊙x=x⊙y=e),给定及幺元e；x，y∈S，则 y为x的左逆元:=y⊙x=e y为x的右逆元:=x⊙y=e y为x的逆元:=y⊙x=x⊙y=e,显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。

通常x的逆元表示为x-1 一般地说来，一个元素的左逆元不一定等于该元素的右逆元而且，一个元素可以有左逆元而没有右逆元，反之亦然甚至一个元素的左或右逆元还可以不是唯一的定理12.2.6 给定及幺元e∈S如果⊙是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1 定理12.2.7 给定及幺元e∈S如果⊙是可结合的并且x的逆元x-1存在，则x-1是唯一的例：代数结构上的幺元是“0”，对于任何整数x，它的逆元是－x，因为 x＋(－x)＝0 例：代数结构中0和1分别为＋和×的幺元对于“＋”，对每个元素rR都有逆元－r；对于“×”，对每个元素 rR都有逆元1/r(r 0) 9.可约律与可约元 给定且零元θ∈S，则 ⊙满足左可约律或是。