第六章代数系统精选文档.ppt

《第六章代数系统精选文档.ppt》由会员分享，可在线阅读，更多相关《第六章代数系统精选文档.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章代数系统本讲稿第一页，共五十八页第六章 代数系统6.1代数系统的一般概念6.2同态与同构6.3同余关系6.4商代数和积代数6.5典型代数系统本讲稿第二页，共五十八页6.1代数系统的一般概念定义：设S为非空集合，为S上代数运算的非空集合，称 为一个代数系统或代数结构。集合S称为V的定义域。如果 为有限集合，则将 记作 。如果S为有限集合，则称V为有限代数系统有限代数系统，并称|S|为 的阶。例例1 通通常常数数的的加加法法运运算算、乘乘法法运运算算和和减减法法运运算算都都可可看看作作是是实实数数集集R上上的的二二元元运运算算，它它们们构构成代数系统成代数系统 。例例2 2 设设 是集合是集

2、合A A上的关系上的关系，是求复是求复合关系的运算。它们构成代数系统合关系的运算。它们构成代数系统 。本讲稿第三页，共五十八页代数系统的一般概念例：设集合 ，是一个一元运算，并规定成 这个代数系统 称为时钟代数时钟代数。它通过重复地进行 运算，从元素 开始，可逐步地产生出M的每一个元素。因此，可以把1叫做代数系 统 的生成元。本讲稿第四页，共五十八页代数系统的一般概念定义：设 为代数系统。如果非空集合 对于每一个 皆封闭，则 也是代数系统，并称其为 的子代数系统。例：考虑代数系统 ，其中+和 是普通意义下的加法和乘法，则 是 的子代数系统。本讲稿第五页，共五十八页第六章 代数系统6.1代数系统

3、的一般概念6.2同态与同构6.3同余关系6.4商代数和积代数6.5典型代数系统本讲稿第六页，共五十八页6.2同态与同构定义：设 和 是两个代数系统。如果存在双射 ，使每个 和对应的 有相同的阶，则称代数系统 和 是同型同型的的，称f为从 到 的同类映射，并记 为 。例：试说明代数系统 和代数系统 是同型的，其中 和 定义为：对任意 ,解：令 并且规定 显然是个双射函数，并且 和 和 具有相同的阶，即都是二元运算。所以题目中的两个代数系统是同型的。本讲稿第七页，共五十八页同型关系注意：代数系统之间的同型关系具有自反性，对称性和可传递性。同型关系是等价关系。本讲稿第八页，共五十八页同态和同构定义：

4、设 和 是两个同型的代数系统,f为1到2的同型映射。如果存在函数g:S1S2，使得对任意的 及任意的 均有 则称 和 是同态的，而g则称为从V1到V2的关于f的同态映射，并且：(1)如果g为满射，则称g为关于f的满同态映射满同态映射满同态映射满同态映射，简称关于f的满同态满同态满同态满同态。(2)如果g为单射，则称g为关于f的单一同态映射单一同态映射单一同态映射单一同态映射，简称关于f的单一同态单一同态单一同态单一同态。本讲稿第九页，共五十八页同态和同构(3)如果V1=V2，并且f为恒等映射，则称g为关于f的自同自同自同自同态映射态映射态映射态映射，简称自同态自同态自同态自同态。(4)如果g为

5、双射，则称g为关于f的同构映射同构映射同构映射同构映射，简称关于f的同构同构同构同构，并称代数系统V1和V2是同构的。(5)如果V1=V2，并且f为恒等映射，则称g为关于f的自同自同自同自同构映射构映射构映射构映射，简称自同构自同构自同构自同构。本讲稿第十页，共五十八页同态和同构本讲稿第十一页，共五十八页同态和同构例：给定代数系统 和 ，定义函数 如下：试证f是V1到V2的满同态映射。证：定义函数 如下：显然g为双射，故V1和V2是同型的。又对于任意的 ,有 使 本讲稿第十二页，共五十八页同态和同构故而所有即f是同态映射。本讲稿第十三页，共五十八页同态和同构又因为对任意的 ，存在 ,使 所以f

6、是满同态映射，即代数系统V1和V2是满同态的。本讲稿第十四页，共五十八页同态和同构定理：若g为从 到 的关于f的同态，h为从 到 的关于 的同态，则hg为从 到 的关于 的同态。证：由于g为V1到V2关于f的同态，所以V1和V2是同型的；h为V2到V3关于 的同态，所以V2和V3是同型的。由同型关系的可传递性，可得V1和V3是同型的。任取 及 得证。本讲稿第十五页，共五十八页同态和同构推论：若g为从 到 的关于f的同构，h为从 到 的关于 的同构，则hg为从 到 的关于 的同构。本讲稿第十六页，共五十八页同态和同构定理：设g为 到 的同态,则 为 的子代数，并称V3为V1的同态象点同态象点。证

7、：显然，是G2的非空子集。任取 及 ,则 ,有 ，使得 且表明 关于每个 都是封闭的,故 为 的子代数。本讲稿第十七页，共五十八页同态和同构定理：设g为 到 的关于f的满同态，f为从 到 的双射函数。(1)若二元运算 是可交换的（或可结合的），则 也是可交换的（或可结合的）；(2)若二元运算 关于二元运算 是可分配的，则二元运算 关于二元运算 也是可分配的；(3)若关于二元运算 有左单位元el（或右单位元er，或单位元e），则 （或 ，或g(e)）为关于二元运算 的左单位元（或右单位元，或单位元）；本讲稿第十八页，共五十八页同态和同构(4)若关于二元运算 有左逆元0l（或右零元0r，或零元0）

8、，则g(0l)（或g(0r)，或g(0)）为关于二元运算 的左零元（或右零元，或零元）；(5)若关于二元运算 有左逆元xl（或右逆元xr，或逆元x-1），则g(xl)(或g(xr)，或g(x-1)为 关于二元运算 的左逆元（或右逆元，或逆元）。本讲稿第十九页，共五十八页同态和同构证：(b)对任意的 ，由于 ，故存在 ，使g(x)=a，g(y)=b以及g(z)=c，而 同理可得本讲稿第二十页，共五十八页同态和同构证：(3)对任意的 ，存在 ，使 ，而 故 为关于 的单位元。同样可证 和 分别为关于 的左单位元和右单位元。从定理可知，满同态映射能够从一个代数系统到另一个代数系统单向保留所有的性质（

9、如交换律、结合律、含零元、含单位元、元素的可逆性等），故满同态映射是确保结构的映射。本讲稿第二十一页，共五十八页第六章 代数系统6.1代数系统的一般概念6.2同态与同构6.3同余关系6.4商代数和积代数6.5典型代数系统本讲稿第二十二页，共五十八页6.3同余关系定义：设 为代数系统，R为G上的等价关系。(1)若 ，对任意的 只要a1Rb1,a2Rb2,就有 ，则称R关于 具有代换性质代换性质。(2)若R关于每个 都有代换性质，则称R为 上的同余关系同余关系。本讲稿第二十三页，共五十八页同余关系例：考察代数系统 ，其中I是整数集合，*是个一元运算，并定义成 设R是I中的这样一个关系:当且仅当 时

10、，有 。试证明R是代数系统 中的同余关系。解：不难看出，这里R是一种等价关系。设 且满足 ,因此可有 ，并可写出 和 ，这里 。于是可写出 本讲稿第二十四页，共五十八页同余关系所得结果说明，。所以，R是代数系统 中的同余关系。本讲稿第二十五页，共五十八页同余关系例：设 ，验证 是 上的同余关系。解：显然关系 是个等价关系，故只要验证 关于+和 具有代换性质即可。对任意的 ,若 且 ，即存在 使 而所以，关于+满足代换性质。本讲稿第二十六页，共五十八页同余关系同理，所以，关于 也满足代换性质。本讲稿第二十七页，共五十八页同余关系定理：设f是 到 的同态，定义G1上的关系Rf如下：对任意的 ，当且

11、仅当f(x1)=f(x2)，则Rf是 上的同余关系。定理：设f是 到 的同态，定义G1上的关系Rf如下：对任意的 ，当且仅当f(x1)=f(x2)，则Rf是 上的同余关系。证：显然，Rf是G1上的等价关系。下面证明Rf关于每个 满足代换性质。任取 ，若 和 ，则有(转下页)本讲稿第二十八页，共五十八页同余关系因为故因此，Rf是 上的同余关系。这个定理说明，如果存在 到 的同态，则可以定义相应于这一同态的同余关系。本讲稿第二十九页，共五十八页第六章 代数系统6.1代数系统的一般概念6.2同态与同构6.3同余关系6.4商代数和积代数6.5典型代数系统本讲稿第三十页，共五十八页6.4商代数和积代数

12、定义：设R为代数系统 上的同余关系，代数系统 称为 关于R的商代数商代数，其中 ，对于每个 ，与 同型的 运算定义为：对任意的 ,有 本讲稿第三十一页，共五十八页商代数为了保证 确实是一个代数系统，必须验证每个 是良定的，即 与等价类中代表元素 的选取无关。任取 ,则有 ，而R是 上的同余关系，所以 定义：设R是集合G上的等价关系，定义函数g:GG/R为 ，称g为G到G/R的正规映正规映射射。本讲稿第三十二页，共五十八页商代数定理：设R为代数系统 上的同余关系，则正则映射 是 到商代数 的满同态，并称g为自然同态。证：显然，和 是同型的。任取 及 ,因为 所以，g是 到 的同态。又因为对任意

13、，总有 ，使g(x)=xR=yR，所以g是满射。本讲稿第三十三页，共五十八页商代数本定理说明，对于代数系统 上任何同余关系R，可以定义从 到 的自然同态；而对于代数系统 到 的任何同态f，也可以定义 上相应的同余关系。由此可见，同态与同余之间有着密切的联系。本讲稿第三十四页，共五十八页商代数和积代数定理：设f为 到 的关于 的同态，Rf是上对应于f的同余关系，g是 到 的自然同态，则存在从 到 的同构映射 ，且满足 。证：定义函数 如下：对任意 ，需要证明 是良定的。任取 ，若 ，则 ，因而 ，这表明 是良定的。对任意的 ，存在 使 ，则 。这表明 是满射。本讲稿第三十五页，共五十八页商代数和

14、积代数任取 ，若 ，即f(x1)=f(x2)，则 ，故 ，表明 是单射。定义函数 如下：对任意 ，令 ，显然h是双射，任取 ,本讲稿第三十六页，共五十八页商代数和积代数综上所述，是到 的同构映射，并且对任意 ，有 本讲稿第三十七页，共五十八页商代数和积代数推论：如果f为 到 的满同态，Rf为对应于f的同余关系，则 为 到 的同构映射。由已知的代数系统构造新代数系统的另一种方法是将同型的代数系统通过“直接积”来构造积代数。本讲稿第三十八页，共五十八页商代数和积代数定义：设 为同型的代数系统A1,A2,Am的积代数 定义为 。其中对每个 及对应的 ，定义 如下：，对任意 ，令称 为积代数 的因子代

15、数。本讲稿第三十九页，共五十八页商代数和积代数例：和 为两个代数系统,其中 ，G2=b1,b2,b3，二元运算*和 的运算如下表所示。求积代数 本讲稿第四十页，共五十八页商代数和积代数解：对任意的 ，本讲稿第四十一页，共五十八页第六章 代数系统6.1代数系统的一般概念6.2同态与同构6.3同余关系6.4商代数和积代数6.5典型代数系统本讲稿第四十二页，共五十八页6.5典型代数系统 定义：设是一个代数系统，*是S上的二元运算；若*是可结合的，则称为一个半群半群半群半群。定义：如果是一个半群，并且关于*运算有单位元e，则称为独异点独异点独异点独异点或含幺半群含幺半群含幺半群含幺半群，记作。例：,都

16、是独异点，其中n为正整数。设是非空有限字母表，则 是独异点，而 不是独异点，其中是空串。本讲稿第四十三页，共五十八页典型代数系统例：如果独异点的每个元素关于都是可逆的，则称为群。设A为任意非空集合，PA是A到A的所有双射函数的集合，于是构成一个群，其中是函数的复合运算，称为对称群，称的子群为A的变换群。例如，A=1,2,3，由A到A的所有双射函数为3!=6个，它们是 本讲稿第四十四页，共五十八页典型代数系统在PA上的运算表如下：可以看出f1是幺元，f2的逆元是f2，f3的逆元是f3，f4的逆元是f4，f5的逆元是f6，f6的逆元是f5，并且，和 都是的子群，所以它们都是变换群。本讲稿第四十五页

17、，共五十八页典型代数系统能否对一个抽象的代数系统进行研究，而这种代数系统具有像命题代数、集合代数等一些具体代数系统所具有的最本质的特征。这种抽象的代数系统就是由布尔（Boole）于1854年建立的布尔代数。实际上，还存在着比布尔代数更一般的代数系统，那就是格。定义：设 是偏序集，对于任意的a,bL，a,b均有上确界和下确界，则称 为格。本讲稿第四十六页，共五十八页典型代数系统通常a*b用表示a,b的下确界,也就是a*b=infa,b，称为a,b的积。用ab表示a,b的上确界，记ab=supa,b，称为a和b的和，因为偏序集和的任何非空子集的上、下确界若存在，必唯一。所以*和可以看作是集合L上的

18、两个代数运算。于是代数系统是一个格。每个全序结构都是格。但是，不是所有的偏序结构都是格。本讲稿第四十七页，共五十八页典型代数系统a,b,c是格，而def是偏序集，但不是格。本讲稿第四十八页，共五十八页典型代数系统例：设D是I+上的整除关系，亦即，对任意的a,b I+，aDb，当且仅当a整除b。于是是一个格，其中a*b=a和b的最大公因子，ab=a和b的最小公倍数。*和的基本性质：等幂律交换律结合律 吸收律本讲稿第四十九页，共五十八页典型代数系统设是格，则在格中每对元素都有上、下确界，设S=a1,a2,an是L的有限子集，则S应有上确界和下确界。一般地，可以把S的下确界和上确界表示成 本讲稿第五

19、十页，共五十八页典型代数系统定义：有最大元素和最小元素的格称为有界格有界格有界格有界格。通常把有界格的最大元素和最小元素分别记为1和0，并称它们为格的界。显然，有限格是有界格，并且，其中L=a1,a2,an,常把有界格记为。对于任意的aL,a1且0a，因此有 本讲稿第五十一页，共五十八页典型代数系统设是有界格，a,bL，如果a*b=0且ab=1，则称b为a的补元，记为b=a。如果L中每个元素都有补元，则称为有补格。补元的定义是相互的。一个元素可以有补元，也可以没有补元，如果有补元，可以有一个补元，也可以有多个补元。本讲稿第五十二页，共五十八页典型代数系统在左图的格中，a和b均为c的补元，a和b

20、的补元均为c。1和0互为补元，且唯一。本讲稿第五十三页，共五十八页典型代数系统定义：设是一个格，如果*对是可分配的，并且对*也是可分配的，则称是分配格分配格分配格分配格。要判断一个格是不是分配格，只须检验一个分配律即可，因为在分配格的定义中，两个分配律是互为对偶的，故对偶原理适用于分配格。均不是分配格本讲稿第五十四页，共五十八页典型代数系统一个格是分配格，当且仅当它没有子格同构于这两个五元素格之一。本讲稿第五十五页，共五十八页典型代数系统定义：一个有补分配格称为一个布尔代数布尔代数布尔代数布尔代数。一般用表示布尔代数。其中是格,是一元的求补运算，0和1为最小元素和最大元素。例：设B=0，1，B

21、上的运算*，和如下表定义：是最简单的布尔代数，称为电路代电路代电路代电路代数数数数。本讲稿第五十六页，共五十八页典型代数系统例：设S是非空集合，不难证明 是布尔代数，称为集合代数。其中任何A S的补元为A=S-A。(S)中的偏序关系是 。如果S有n个元素，则(S)有2n个元素，布尔代数的图是一个n维立方体。例：用S表示含有n个原子的合式公式的集合，代数系统是布尔代数，称为命题代数。其中,和 分别是合取、析取和否定，F和T分别是一个永假式和永真式，并且把等价的合式公式看成是相等的，对应的偏序关系是蕴含 。本讲稿第五十七页，共五十八页典型代数系统定义:令Bn=0,1n,对任意a=,b=Bn定义 这里,和 是0,1上的逻辑运算。代数系统是布尔代数。其中0n和1n分别是成员都为0和成员都为1的n元序偶。这个代数被称为开关代数。本讲稿第五十八页，共五十八页