电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院17 九月 2024电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2第五篇第五篇 代数系统代数系统由于数学和其他科学的发展，人们需要对若干不由于数学和其他科学的发展，人们需要对若干不是数的事物，用类似普通计算的方法进行相似的是数的事物，用类似普通计算的方法进行相似的计算。如矩阵、向量等。计算。如矩阵、向量等。研究代数系统的学科称为研究代数系统的学科称为“近世代数近世代数”或或“抽象抽象代数代数”。 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程3第五篇第五篇 代数系统内容代数系统内容集合的概念集合的概念1集合的表示方法集合的表示方法2环与域环与域3格与布尔代数格与布尔代数4代数系统与性质代数系统与性质1半群与群半群与群22024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程4第十二章第十二章 代数系统代数系统集合的概念集合的概念1同态与同构同态与同构3代数系统与子代数代数系统与子代数1运算性质与特殊元运算性质与特殊元22024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程512.1 12.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 代数系统与代数系统与子代数子代数2 2 二元运算律二元运算律3 3 特殊元特殊元4 4 同态与同构同态与同构 3同态与同构的同态与同构的应用应用2同类型代数系同类型代数系统统2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程6代数运算代数运算定义定义12.2.112.2.1 设设A, B, CA, B, C是非空集合，从是非空集合，从ABAB到到C C的的一个映射（或函数）一个映射（或函数） ：ABCABC称为一个称为一个ABAB到到C C的二元代数运算，简称的二元代数运算，简称二元运算二元运算。称自然数集合称自然数集合N N上的加法上的加法“+ +”为运算，这是因为给为运算，这是因为给定两个自然数定两个自然数a, b, a, b, 由加法由加法“+ +”，可以得到唯一的，可以得到唯一的自然数自然数c = a + bc = a + b。 加法加法“+ +” 是映射吗？是映射吗？ N N上的加法运算上的加法运算“+ +”本质上是一个本质上是一个NNNNNN的映射的映射 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程7代数运算代数运算 一个二元运算就是一个特殊的映射一个二元运算就是一个特殊的映射 ，该映射，该映射能够对能够对a a A A和和b b B B进行运算进行运算 ，得到，得到C C中的一中的一个元个元c , c , 即即 (a, b)(a, b)c c 。中缀方法中缀方法表示为表示为 a a b bc c 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8例例12.2.112.2.1判别下面的映射或表是否是二元运算：判别下面的映射或表是否是二元运算：（1 1）设）设A = 0, 1, B = 1, 2, C = A = 0, 1, B = 1, 2, C = 奇奇, , 偶偶 ，定义映射，定义映射 : ABC: ABC，其中，其中 (0, 1) = (0, 1) = 奇，奇， (0, 2) = (0, 2) = 偶，偶， (1, 1) = (1, 1) = 偶，偶， (1, 2) = (1, 2) = 奇。奇。分析分析 “ ”是一个是一个ABAB到到C C的映射，因此，按定义的映射，因此，按定义12.2.112.2.1，则，则“ ”是一个是一个ABAB到到C C的运算。的运算。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程9例例12.2.112.2.1（续）（续）（2 2）一架自动售货机，能）一架自动售货机，能接受五角和一元硬币，接受五角和一元硬币，而所对应的商品是纯净而所对应的商品是纯净水、矿泉水、橘子水，水、矿泉水、橘子水，当人们投入上述硬币中当人们投入上述硬币中的任何两枚时，自动售的任何两枚时，自动售货机供应出相应的商品货机供应出相应的商品( (右表右表) )。表表 五角五角一元一元五角五角纯净水纯净水矿泉水矿泉水一元一元矿泉水矿泉水橘子水橘子水2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程10例例12.2.112.2.1（续）（续）分析分析 设集合设集合A = A = 五角，一元五角，一元 ，集合，集合C = C = 纯净纯净水，矿泉水，橘子水水，矿泉水，橘子水 ，则表，则表12.2.112.2.1实质上是实质上是AACAAC的映射，也就是的映射，也就是AAAA到到C C的一个运算的一个运算“ ”。解解 (1)(1)、(2)(2)中定义的映射是二元运算。中定义的映射是二元运算。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程11运算表运算表运算表运算表b1b2bma1a1 b1a1 b2a1 bma2a2 b1a2 b2a2 bmanan b1an b2an bm当集合当集合A A和和B B有限时，一个有限时，一个ABAB到到C C的代数运算，可以的代数运算，可以借用一个表，称为借用一个表，称为运算表（乘法表运算表（乘法表 ）来说明。来说明。设设“ ”是是AACAAC的运算，的运算，A = aA = a1 1, a, a2 2, , , , a an n, B = b, B = b1 1, b, b2 2, , , b , bm m,则运算则运算“ ”可用下表可用下表说明。说明。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程12定义定义12.2.212.2.2设设 A A1 1, , A A2 2, , , , A An n， A A是是 非非 空空 集集 合合 ，A A1 1AA2 2AAn n到到A A的的一一个个映映射射( (或或函函数数) ) ：A A1 1AA2 2AAn nAA称称为为一一个个A A1 1AA2 2AAn n到到A A的的n n元元代代数数运运算算，简简称称n n元元运运算算。当当n n = = 1 1时时，称称为为一元运算一元运算。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程131 1元代数运算表元代数运算表当当元元素素有有限限时时，一一元元运运算算也也可可以用运算表来说明。以用运算表来说明。设设“ ”是是A A到到A A的的一一元元运运算算，其其中中A A = = aa1 1, , a a2 2, , , , a an n ，则则一一元元运运算算“ ”可可以以用用右右表表说说明。明。1元运算表元运算表a (a)a1 (a1)a2 (a2)an (an)2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程14代数运算：封闭性代数运算：封闭性定义定义12.2.312.2.3 如果如果“ ”是是AAAA到到A A的二元运算，的二元运算，则称运算则称运算“ ”对集合对集合A A是是封闭封闭的，或者称的，或者称“ ”是是A A上的二元运算上的二元运算。定义定义12.2.4 12.2.4 设设“ ”是一个是一个A A1 1AA2 2AAn n到到A A的的n n元代数运算，如果元代数运算，如果A A1 1A A2 2A An nA A，则称代数运，则称代数运算算“ ”对集合对集合A A是是封闭的封闭的，或者称是，或者称是A A上的上的n n元代元代数运算数运算。 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程15说说 明明一般通常用大写的英文字母表示集合，用符号一般通常用大写的英文字母表示集合，用符号“+”+”、“-”-”、“*”“*”、“/ /” ”、“ “” ”、“ “” ”、“ “” ”、“ “” ”、“ “” ”、“”“”、“”“”、“” ”、“”“”、“ “+”+”、“ “ ” ”、“ “ ” ”等抽象等抽象的符号来表示一个抽象的运算。的符号来表示一个抽象的运算。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程16定义定义12.2.5 12.2.5 设设A A是非空集合，是非空集合， 1 1, , 2 2, , , , m m分别是定义在分别是定义在A A上上k k1 1, , k k2 2, , k, km m元封闭运算，元封闭运算，k ki i是正整数，是正整数，i = 1, 2, i = 1, 2, , , m m。称集合。称集合A A和和 1 1, , 2 2, , , , m m所组成的系统称为所组成的系统称为代数代数系统系统，简称，简称代数代数，记为，记为A, 。当当A A是有限集合时，该代数系统称为是有限集合时，该代数系统称为有限代数系统有限代数系统，否则称为否则称为无限代数系统无限代数系统注意：注意：判断集合判断集合A A和其上的代数运算是否是代数系和其上的代数运算是否是代数系统，关键是判断两点：一是集合统，关键是判断两点：一是集合A A非空非空，二是这些，二是这些运算关于运算关于A A是否满足是否满足封闭性封闭性。 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程17例子例子(1) (1) R R上的上的“+ +”、“”运算；运算； 解解 构成一个代数系统构成一个代数系统R R，+ +，；(2) p(2) p（S S）上的）上的“ “” ”、“ “” ”、“ “” ”运算；运算； 解解 构成代数系统构成代数系统,称称集合代数集合代数；(3) (3) 含有含有n n个命题变元的命题集合个命题变元的命题集合A A与与A A上的上的“” ”、“ “” ”、“ “” ”运算；运算； 解解 构成代数系统构成代数系统A A，称之为，称之为命命题代数题代数。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程18同类型代数系统同类型代数系统定义定义12.2.612.2.6 设设A, 和和B, 是两个代数系统，若是两个代数系统，若“o oi i”和和“ i i”都是都是k ki i元运算，元运算，i = 1, 2, i = 1, 2, , m, m，则称这，则称这两个代两个代数同类型数同类型。如如：代数系统：代数系统Z Z，+ +, ,Z Z，, ,R R，+ +, ,p p（S S），），, ,p p（S S），），都是同类型都是同类型的代数系统。的代数系统。代数系统代数系统I I，+ +，、R R，+ +，、 p p（S S），），都是同类型的代数系统。都是同类型的代数系统。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程19子代数子代数定义定义12.2.712.2.7 设设A, 是代数系是代数系统，如果：统，如果： （1 1）B B A A并且并且B B ； （2 2） 1 1, , 2 2, , , , m m都是都是B B上的封闭运算。上的封闭运算。则则B, 也是一个代数系统，称也是一个代数系统，称之为之为A, 的的子代数系统子代数系统，简称，简称子代数子代数。又若。又若B B A A，则称，则称B, 是是A, 的的真子代数真子代数。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程20子代数子代数子代数是抽象代数学中一个非常重要的概念，通过子代数是抽象代数学中一个非常重要的概念，通过研究子代数的结构和性质，可以得到原代数系统的研究子代数的结构和性质，可以得到原代数系统的某些重要性质。某些重要性质。如在群论中，通过研究子群可得群的某些性质。如在群论中，通过研究子群可得群的某些性质。注意：注意：在后面章节中，将会学习半群、群、格、在后面章节中，将会学习半群、群、格、布尔代数等典型的代数系统。将子代数的概念应布尔代数等典型的代数系统。将子代数的概念应用到这些典型的代数系统，就会得到子半群、子用到这些典型的代数系统，就会得到子半群、子群、子格、子布尔代数。因此，若没有比要，后群、子格、子布尔代数。因此，若没有比要，后面不再赘述某些典型代数系统中子代数的定义。面不再赘述某些典型代数系统中子代数的定义。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程21例例12.2.412.2.4 在代数系统在代数系统中，令中，令Q = 5z | z Q = 5z | z Z Z，证明证明是是的子代数。的子代数。分析分析 根据定义，只需证明两点：根据定义，只需证明两点：（1 1）Q Q是非空子集；（是非空子集；（2 2） “+ +”对集合对集合Q Q封闭。封闭。显然，集合显然，集合Q Q非空。对任意的非空。对任意的5z5z1 1，5z5z2 2QQ，有，有5z5z1 1 + 5z + 5z2 2 = 5(z = 5(z1 1 + z + z2 2)Q)Q，因此因此“+ +”对集合对集合Q Q封闭。封闭。 证明证明 略。略。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2212.3.1 12.3.1 二元运算律二元运算律例例12.3.112.3.1 设设“+ +”是定义在自然数集合是定义在自然数集合N N上的普通上的普通加法运算，试回忆加法运算，试回忆N N上的加法运算上的加法运算“+ +”满足哪些运满足哪些运算性质？算性质？分析分析 对对 a, b, cNa, b, cN，有，有(a + b) + c = a + (b + c)(a + b) + c = a + (b + c)，即，即结合律结合律成立；成立；a + b = b + aa + b = b + a，即，即交换律交换律成立；成立； x, yNx, yN，如果，如果a + x = b + ya + x = b + y，则，则x = yx = y， 即即消去律消去律成立；成立； 0N 0N，0 + 0 = 00 + 0 = 0，即，即0 0是幂等元，但其他自然数不是幂等元，但其他自然数不是幂等元，即不满足是幂等元，即不满足幂等律幂等律。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程23结合律与交换律结合律与交换律定义定义12.3.112.3.1 设设A, 是二元代数系统，如果对是二元代数系统，如果对任意的任意的a, b, cAa, b, cA，都有，都有 (a(a*b) b) *c ca a* (b (b*c)c)则称则称“*”在在A A上是上是可结合的可结合的，或称满足，或称满足结合律结合律。定义定义12.3.212.3.2 设设A, 是二元代数系统，如果对是二元代数系统，如果对任意的任意的a, bAa, bA，都有，都有a a * b bb b * a a则称则称“ ”在在A A上是上是可交换可交换的，或称满足的，或称满足交换律。交换律。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程24消去律消去律定义定义12.3.312.3.3 设设A, 是二元代数系统，元素是二元代数系统，元素aAaA， （1 1）对任意）对任意x, yAx, yA，都有，都有 如果如果a a x = a x = a y y，那么，那么x = yx = y，则称则称a a在在A A中关于中关于“ ”是是左可消去元左可消去元； （2 2）对任意）对任意x, yAx, yA，都有，都有 如果如果x x a = y a = y a a，那么，那么x = yx = y，则称则称a a在在A A中关于中关于“ ”是是右可消去元右可消去元；2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程25消去律（续）消去律（续）（3 3）如果）如果a a既是既是A A左可消去元又是右可消去元，则左可消去元又是右可消去元，则称称a a是是A A的的可消去元可消去元；（4 4）若）若A A中所有元素都是可消去元，则称中所有元素都是可消去元，则称“ ”在在A A上可消去，或称上可消去，或称“ ”满足满足消去律消去律。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程26幂等律幂等律定义定义12.3.412.3.4 设设A, 是二元代数系统，若元素是二元代数系统，若元素aAaA，满足，满足 a a a = aa = a，则称则称a a是是A A中关于中关于“ ”的一个的一个幂等元幂等元，简称，简称a a为为幂幂等元等元。若。若A A中的每一个元素都是幂等元，则称中的每一个元素都是幂等元，则称“ ”在在A A中是中是幂等的幂等的，或称，或称“ ”满足满足幂等律幂等律。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程27幂等律幂等律设设“ ”是集合是集合A A上的二元运算，上的二元运算，aAaA，则，则a a aAaA，a a a a aAaA，, ,由此，可以归纳定义由此，可以归纳定义a a的正整数的正整数幂方幂方：a a1 1 = a = a，a a2 2 = a = a a a，a a3 3 = a = a2 2 a a，a an n = = a an n 1 1 a a，对任意的正整数对任意的正整数n n，m m，有以下等式：，有以下等式： a an n a am m = a = an+mn+m， （a an n）m m = a = anmnm。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程28分配律分配律定义定义12.3.512.3.5 ：设：设“ “ ” ”、“ “” ”是集合是集合A A上的二元运算，上的二元运算，A, , 是一个代数系统，是一个代数系统， 对对 a,b,ca,b,c S S，有，有（1 1）a(b*c)=(ab)*(ac)a(b*c)=(ab)*(ac)，则称运算则称运算“” ”对对“ “* *” ”在在S S上满足上满足左分配律左分配律( (或第一分或第一分配律配律) )；（2) (b*c) a=(ba)*(ca)2) (b*c) a=(ba)*(ca)，则称运算则称运算“” ”对对“ “* *” ”在在S S 上满足上满足右分配律右分配律( (或第二分或第二分配律配律) ) ；（3) 3) 如果如果“” ”对对“ “* *” ”既满足左分配律又满足右分配既满足左分配律又满足右分配律，则称律，则称” ”对对“ “* *” ”在在S S上满足上满足分配律分配律。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程29吸收律吸收律定义定义12.3.612.3.6 设设“ ”、“”是集合是集合A A上的二元上的二元运算，运算，A, 是一个代数系统，如果对任意的是一个代数系统，如果对任意的x, yAx, yA，都有，都有 x x (x (x y) = x y) = x， x x (x (x y) = x y) = x，则称则称“ ”和和“”满足满足吸收律吸收律2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程30特殊元特殊元在代数系统中，有些元素有特殊性质，叫在代数系统中，有些元素有特殊性质，叫特殊元特殊元 。例如在代数系统例如在代数系统N ，其中，其中N N是自然数，是自然数，“”是是普通加法，普通加法，0 N 0 N ，并且对任意的自然数，并且对任意的自然数x N x N ，有，有 x x0 0x x0 0x x 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程31幺元（单位元）幺元（单位元）定义定义12.3.712.3.7 设设A, 是二元代数系统，是二元代数系统，（1 1）若存在）若存在eAeA，对任意，对任意aAaA，都有，都有 a a e = e e = e a = a a = a，则称则称e e是是A A中关于运算中关于运算“ ”的一个的一个幺元（单位元）幺元（单位元）（2 2）若存在）若存在e el lAA，使得对任意，使得对任意aAaA，都有，都有 e el l a = a a = a，则称则称e el l是是A A中关于运算中关于运算“ ”的一个的一个左幺元（左单位元）左幺元（左单位元）（3 3）若存在）若存在e er rAA，使得对任意，使得对任意aAaA，都有，都有 a a e er r = a = a，称称e er r是是A A中关于运算中关于运算“ ”的一个的一个右幺元（右单位元）右幺元（右单位元）2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程32例例12.3.5 12.3.5 下列代数系统是否存在幺元下列代数系统是否存在幺元( (左幺元或右幺元左幺元或右幺元) )，如果，如果存在计算之。存在计算之。（1 1），R R是实数集，是实数集，“+ +”是加法运算；是加法运算；（2 2）R, +，R R+ +是正实数集，是正实数集，“+ +”是加法运算；是加法运算；（3 3）P(AA), ，其中，其中P (AA)P (AA)表示集合表示集合A A上的所上的所有二元关系集合，运算有二元关系集合，运算“ ”表示关系的复合；表示关系的复合；（4 4） A, ，其中，其中A = A = a, b, ca, b, c，二元，二元运算运算“ ”, ,“ ”, ,“ ”如表如表12.3.212.3.2、表、表12.3.312.3.3和和表表12.3.412.3.4分别所示。分别所示。是一样的是一样的。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程33例例12.3.512.3.5（续）（续）分析分析 可以直接通过定义计算幺元，即首先假设幺可以直接通过定义计算幺元，即首先假设幺元存在，然后计算之，最后验证所计算的元是否是元存在，然后计算之，最后验证所计算的元是否是幺元。幺元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程34例例12.3.512.3.5（续）（续）（1 1）设）设x x是是的幺元，则由定义，对任意的的幺元，则由定义，对任意的aRaR，有，有 x + a = a x + a = a，让让a = 1a = 1，有，有x + 1 = 1x + 1 = 1，则，则x = 0x = 0，xRxR。这说明，如果这说明，如果的幺元存在，那么幺元必是的幺元存在，那么幺元必是0 0。对任意的对任意的aRaR，0 + a = a + 0 = a0 + a = a + 0 = a，即验证可得，即验证可得，0 0是是的幺元。的幺元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程35例例12.3.512.3.5（续）（续）（2 2）设）设x x是是R, +的幺元，对任意的的幺元，对任意的aRaR+ +，有，有 x + a = a x + a = a，让让a = 1a = 1，有，有x + 1 = 1x + 1 = 1，则，则x = 0x = 0，但，但0 0 R R+ +。这说明这说明R, + 不存在幺元。同理，左、右幺元也不存在幺元。同理，左、右幺元也不存在。不存在。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程36例例12.3.512.3.5（续）（续）（3 3）设）设X X是是 P 的幺元，对任意的的幺元，对任意的YPYP(AA)(AA)，有，有X X Y = YY = Y，让让Y = IY = IA A，则，则X X I IA A = I = IA A，又，又X X I IA A = = X X，因此，因此X X = = I IA A。这说明，如果这说明，如果P 的幺元存在，则幺元必的幺元存在，则幺元必是是I IA A。对任意的对任意的YPYP(AA)(AA)，I IA A Y Y = Y = Y I IA A = Y = Y，即验证可得即验证可得I IA A是是 P 的幺元。的幺元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程37例例12.3.512.3.5（续）（续）（4 4）由于给出了运算表，因此可以根据运算表直）由于给出了运算表，因此可以根据运算表直接观察可得。接观察可得。解解（1 1）中的幺元是中的幺元是0 0；（2 2）R, +中无幺元；中无幺元；（3 3） P(AA), 中的幺元是恒等关系中的幺元是恒等关系I IA A；（4 4）A, 中关于运算中关于运算“ ”有左幺元有左幺元a a和和b b，但无右幺元，因此无幺元，关于运算，但无右幺元，因此无幺元，关于运算“ ”无左幺元，但有右幺元无左幺元，但有右幺元b b和和c c，因此无幺元；关于运，因此无幺元；关于运算算“ ”有幺元有幺元a a。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程38结论结论（1 1）计算幺元可根据定义直接进行，即）计算幺元可根据定义直接进行，即首先首先假设假设幺元存在，并根据定义计算，幺元存在，并根据定义计算，然后然后进行验证。进行验证。（2 2）可以直接从运算表中看出运算是否有左幺元）可以直接从运算表中看出运算是否有左幺元或右幺元。具体方法是：或右幺元。具体方法是： 如果元素如果元素x x所在的行上的元素与行表头完全相所在的行上的元素与行表头完全相同，则同，则x x是一个左幺元；是一个左幺元； 如果元素如果元素x x所在的列上的元素与列表头完全相所在的列上的元素与列表头完全相同，则同，则x x是一个右幺元；是一个右幺元； 同时满足同时满足和和。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程39零元零元定义定义12.3.812.3.8 设设A, 是一个二元代数系统，是一个二元代数系统，（1 1）若存在）若存在 A A，使得对任意，使得对任意aAaA，都有，都有a a = = a = a = ，则称则称是是A A中关于运算中关于运算“ ”的一个的一个零元零元；（2 2）若存在）若存在 l lAA，使得对任意，使得对任意aAaA，都有，都有 l l a = a = l l，则称则称 l l是是A A中关于运算中关于运算“ ”的一个的一个左零元左零元；（3 3）若存在）若存在 r rAA，使得对任意，使得对任意aAaA，都有，都有a a r r = = r r，则称则称 r r是是A A中关于运算中关于运算“ ”的一个的一个右零元右零元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程40逆元逆元定义定义12.3.912.3.9 设设A, 是二元代数系统，是二元代数系统，e e是幺元，是幺元，aAaA，若存在一个元素，若存在一个元素bAbA，（1 1）使得：）使得： a a b = b b = b a = e a = e，则称则称a a可逆，并称可逆，并称b b是是a a的一个的一个逆元逆元，记为，记为a a 1 1；（2 2）使得：）使得： b b a = ea = e，则称则称a a左可逆，并称左可逆，并称b b是是a a的一个的一个左逆元左逆元，记为，记为a al l 1 1；（3 3）使得：）使得： a a b = e b = e，则称则称a a右可逆，并称右可逆，并称b b是是a a的一个的一个右逆元右逆元，记为，记为a ar r 1 1。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程41定理定理12.3.112.3.1设设A, 是是一一个个代代数数系系统统，“ ” 满满足足结结合合律律，aAaA，a a可逆，则可逆，则a a是可消去元。是可消去元。证明证明 记幺元为记幺元为e e，a a的逆元为的逆元为a a 1 1，设，设x x、y y是是A A中的任中的任意元素，假设意元素，假设a a x = a x = a y y。由由a a x = a x = a y y，有，有a a 1 1 (a (a x) = a x) = a 1 1 (a (a y) y)，又结合律成立，所以有又结合律成立，所以有(a(a 1 1 a) a) x = (a x = (a 1 1 a) a) y y，即即e e x = e x = e y y，可得，可得x = yx = y2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程42定理定理12.3.212.3.2设设A, 是二元代数系统，是二元代数系统，（1 1）如果）如果A, 存在幺元，则幺元唯一；存在幺元，则幺元唯一；（2 2）如果）如果A, 存在幺元，则该幺元一定是左、存在幺元，则该幺元一定是左、右幺元；右幺元；（3 3）如果）如果A, 存在左、右幺元，则该左、右幺存在左、右幺元，则该左、右幺元相等，且是幺元。元相等，且是幺元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程43定理定理12.3.212.3.2（续）（续）证明证明（1 1）（）（反证法反证法）设）设S,*S,*存在两个以上的幺存在两个以上的幺元，不妨假设元，不妨假设e e1 1，e e2 2是是S,*S,*的两个幺元，的两个幺元，则对则对 x x S S， x*ex*e1 1=e=e1 1*x=x*x=x，此时，取，此时，取x=ex=e2 2，有有e e2 2*e*e1 1=e=e1 1*e*e2 2=e=e2 2 则对则对 x x S S，有，有x*ex*e2 2=e=e2 2*x=x*x=x，此时，取，此时，取x=ex=e1 1，有有e e1 1*e*e2 2=e=e2 2*e*e1 1=e=e1 1 由由、可知可知e e1 1=e=e2 2，即即S,*S,*的幺元是唯一的。的幺元是唯一的。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程44定理定理12.3.212.3.2（续）（续）（2 2）显然成立）显然成立（3 3）若）若e el l、e er r是是S,*S,*的左、右幺元，的左、右幺元，则对则对 x x S,S,有有e el l*x=x*x=x，此时，取，此时，取x=ex=er r，有，有e el l*e*er r=e=er r则对则对 x x S,S,有有x*ex*er r=x=x，此时，取，此时，取x=ex=el l，有，有e el l*e*er r=e=el l由由、可知可知e el l=e=er r，即左、右幺元相等；显然可得即左、右幺元相等；显然可得 e=ee=el l。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程45定理定理12.3.3 12.3.3 设设 是二元代数系统，是二元代数系统，（1 1）如果）如果A, 存在零元，则零元唯一；存在零元，则零元唯一；（2 2）如果）如果A, 存在零元，则该零元一定是左、存在零元，则该零元一定是左、右零元；右零元；（3 3）如果）如果A, 存在左、右零元，则该左、右零存在左、右零元，则该左、右零元相等，且是零元。元相等，且是零元。分析分析 该定理的证明方法与定理该定理的证明方法与定理12.3.212.3.2证明相似。证明相似。证明证明 略。略。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程46定理定理12.3.4 12.3.4 设设A, 是二元代数系统，是二元代数系统，“ ”满足满足结合律结合律且设且设e e是幺元，则对任意的是幺元，则对任意的aAaA，（1 1）如果）如果a a存在逆元，则逆元唯一；存在逆元，则逆元唯一；（2 2）如果）如果a a存在逆元，则该逆元一定是左、右逆元；存在逆元，则该逆元一定是左、右逆元；（3 3）如果）如果a a存在左、右逆元，则该左、右逆元相等，存在左、右逆元，则该左、右逆元相等，且是逆元。且是逆元。分析分析 该定理的证明方法与定理该定理的证明方法与定理12.3.212.3.2证明相似证明相似 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程47定理定理12.3.412.3.4（续）（续）证明证明 （1 1）（反证法）设）（反证法）设aAaA存在逆元，且不唯一，存在逆元，且不唯一，不妨设不妨设a a1 1，a a2 2都是都是a a的逆元，则有的逆元，则有a a a a1 1 = a = a1 1 a = e a = e，a a a a2 2 = a = a2 2 a = e a = e，由于由于“ ”满足结合律，所以有满足结合律，所以有a a1 1 = a = a1 1 e = a e = a1 1 (a (a a a2 2) = (a) = (a1 1 a) a) a a2 2 = = e e a a2 2 = a = a2 2，即，即a a1 1 = a = a2 2即即a a的逆元唯一；的逆元唯一；2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程48定理定理12.3.412.3.4（续）（续）（2 2）由逆元、左逆元和右逆元的定义直接可得；）由逆元、左逆元和右逆元的定义直接可得；（3 3）设）设aAaA的左、右逆元分别是的左、右逆元分别是a al l 1 1和和a ar r 1 1，则有，则有a al l 1 1 a = e a = e，a a a ar r 1 1 = e = e，“ ”满足结合律，所以有满足结合律，所以有 a ar r 1 1 = e = e a ar r 1 1 = (a = (al l 1 1 a) a) a ar r 1 1 = a = al l 1 1 (a (a a ar r 1 1) ) = a = al l 1 1 e = a e = al l 1 1，所以，所以a a 1 1 = a = ar r 1 1 = a = al l 1 12024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程49推论推论12.3.1 12.3.1 设设A, 是二元代数系统，是二元代数系统，“ ”满足结合律，满足结合律，a, a, b bAA，（1 1）如果）如果a, ba, b分别有逆元分别有逆元a a 1 1, b, b 1 1，则，则 (a(a b)b) 1 1 = = b b 1 1 a a 1 1；（2 2）如果）如果a a是左（获右）可逆的元素，则是左（获右）可逆的元素，则a a是左（右）是左（右）可消去的元素；可消去的元素；（3 3）如果）如果a a是可逆的元素，则是可逆的元素，则a a是可消去的元素。是可消去的元素。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程50推论推论12.3.112.3.1（续）（续）分析分析 (1) (1) 根据逆元的定义，只需证明根据逆元的定义，只需证明(a (a b) b) (b (b 1 1 a a 1 1) = (b) = (b 1 1 a a 1 1) ) (a (a b) = b) = e e；同理，同理，(2)(2)和和(3)(3)可以直接根据消去元的定义证明。可以直接根据消去元的定义证明。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程51推论推论12.3.112.3.1（续）（续）证明证明 (1) (1) 由于由于“ ”满足结合律，所以有满足结合律，所以有 (a (a b) b) (b (b 1 1 a a 1 1) ) = a = a (b (b b b 1 1) ) a a 1 1 = a = a e e a a 1 1 = a = a a a 1 1 = e = e， (b(b 1 1 a a 1 1) ) (a (a b) b) = b = b 1 1 (a (a 1 1 a) a) b b = b = b 1 1 e e b = b b = b 1 1 b = e b = e，即，即 (a(a b)b) 1 1 = b = b 1 1 a a 1 1。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程52推论推论12.3.112.3.1（续）（续）（2 2）若）若a a是左可逆的元素，设左逆元为是左可逆的元素，设左逆元为a al l 1 1 ，则对，则对任意的任意的x, yx, yA,A,如有如有a a x = ax = a y y，则，则a al l 1 1 (a (a x) = a x) = al l 1 1 (a (a y) y)，即即 (a(al l 1 1 a) a) x = (a x = (al l 1 1 a) a) y y，e e x = e x = e y y，所以，所以x = yx = y则则a a是左可消去元。是左可消去元。同样可证，如果同样可证，如果a a是右可逆的，则是右可逆的，则a a是右可消去元。是右可消去元。（3 3）由）由(2)(2)和定理和定理12.3.412.3.4直接可证。直接可证。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程53例例12.3.712.3.7设设G = fG = fa, ba, b(x) = ax+b | a0, a, bR(x) = ax+b | a0, a, bR，其中，其中R R是实数，是实数， “ ”是是G G上关于函数的复合运算上关于函数的复合运算 。（1 1）验证）验证G, 是代数系统；是代数系统；（2 2）如有幺元计算之；）如有幺元计算之；（3 3）如有零元计算之；）如有零元计算之；（4 4）如有幂等元，计算出这些幂等元；）如有幂等元，计算出这些幂等元；（5 5）说明）说明G G中的那些元有逆元，并计算这些元的逆中的那些元有逆元，并计算这些元的逆元。元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程54例例12.3.712.3.7（续）：封闭性（续）：封闭性分析分析 （1 1）要说明）要说明G, 是代数系统，只需要说是代数系统，只需要说明明“ ”对对G G封闭，即说明对任意封闭，即说明对任意f fa, ba, b，f fc, dc, dGG，f fa, ba, b f fc, dc, dGG，又又 (f(fa, ba, b f fc, dc, d)(x) = f)(x) = fc, dc, d( f( fa, ba, b(x) (x) = f = fc, dc, d(ax+b) = c(ax+b)+d (ax+b) = c(ax+b)+d = cax+bc+d = f = cax+bc+d = fca, bc+dca, bc+d(x)(x)，即，即 f fa, ba, b f fc, dc, d = f = fca, bc+dca, bc+d，显然显然ca 0ca 0，故，故f fca, bc+dca, bc+dGG，所以所以“ ”对对G G是封闭的，即是封闭的，即G, G, 是代数系统是代数系统。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程55例例12.3.712.3.7（续）：幺元（续）：幺元（2 2）不妨假设幺元是）不妨假设幺元是f fc, dc, dGG，则对，则对 f fa, ba, bGG，有，有f fa, ba, b f fc, dc, d = f = fa, ba, b，又，又f fa, ba, b f fc, dc, d = f = fca, bc+dca, bc+d，则，则f fa, ba, b = f = fca, bc+dca, bc+d，因此，因此， xRxR，有，有f fa, ba, b (x) = ax+b = f (x) = ax+b = fca, bc+dca, bc+d (x) = cax+bc+d (x) = cax+bc+d，特别取特别取x = 0, x = 1x = 0, x = 1，可得，可得bc+d = b, ca = abc+d = b, ca = a。由于由于f fa, ba, b是是G G中的任意元，取中的任意元，取a = 1a = 1，b = 2,b = 2,可得可得 c = 1, d = 0c = 1, d = 0。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程56例例12.3.712.3.7（续）：幺元（续）：幺元上面的分析说明，如果上面的分析说明，如果G, 有幺元，则此幺元必有幺元，则此幺元必是是f f1, 01, 0，所以需进一步验证，所以需进一步验证f f1, 01, 0就是幺元。就是幺元。即对任意的即对任意的f fa, ba, bGG，验证等式，验证等式f fa, ba, b f f1, 01, 0 = f = f1, 01, 0 f fa, ba, b = f = fa, ba, b显然此等式成立，所以显然此等式成立，所以f f1, 01, 0是幺元。是幺元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程57例例12.3.712.3.7（续）：零元（续）：零元（3 3）按同样的思路，不妨假设零元是）按同样的思路，不妨假设零元是f fc, dc, dGG，由，由零元的定义，零元的定义， f fa, ba, bGG，有，有f fa, ba, b f fc, dc, d = f = fc, dc, d，f fa, ba, b f fc, dc, d (x) = cax+bc+d = f (x) = cax+bc+d = fc, dc, d (x) = cx+d (x) = cx+d，取取x = 0x = 0，有，有 bc = 0bc = 0, ,又又f fa, ba, b是任意的，取是任意的，取b = 1b = 1，可得，可得c = 0c = 0，又又f fc, dc, dGG，则，则c 0, c 0, 矛盾，故矛盾，故f fc, dc, d是零元不成立，是零元不成立，故代数系统故代数系统G, 没有零元没有零元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程58例例12.3.712.3.7（续）：幂等元（续）：幂等元（4 4）不妨假设幂等元是）不妨假设幂等元是f fc, dc, dGG，有，有f fc, dc, d f fc, dc, d = f = fc, dc, d，f fc, dc, d f fc, dc, d(x) = c(x) = c2 2x+cd+d = fx+cd+d = fc, dc, d(x) = cx+d(x) = cx+d，取取x = 0x = 0，有，有cd = 0cd = 0，又，又c c 0 0，则，则d = 0d = 0，取取x = 1x = 1，有，有c c2 2+cd+d = c+d+cd+d = c+d，又，又d = 0, c d = 0, c 0 0，则，则c = 1c = 1。因此，。因此，f fc, dc, d = f = f1, 01, 0，又，又f f1, 01, 0 f f1, 01, 0 = f = f1, 01, 0，所以，所以f f1, 01, 0是唯一幂等元。是唯一幂等元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程59例例12.3.712.3.7（续）：逆元（续）：逆元（5 5）对）对 f fa, ba, bGG，不妨假设它的逆元为，不妨假设它的逆元为f fc, dc, d，当，当然然f fc, dc, dGG，有，有f fa, ba, b f fc, dc, d = f = f1, 01, 0，f fa,ba,b f fc,dc,d (x) = cax+bc+d = f (x) = cax+bc+d = f1, 01, 0(x) = x(x) = x，特别取特别取x = 0, x = 1x = 0, x = 1，可得，可得bc+d = 0, ca = 1bc+d = 0, ca = 1，因为因为a0a0，显然，显然c = 1/a, d = c = 1/a, d = b /ab /a，故，故f fc, dc, d = f = f1/a, 1/a, b/ab/a，2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程60例例12.3.712.3.7（续）：逆元（续）：逆元同理，上面分析说明，如果同理，上面分析说明，如果f fa, ba, b有逆元，则此逆元有逆元，则此逆元是是f f1/a, 1/a, b/ab/a, ,因此还需验证因此还需验证f f1/a, 1/a, b/ab/a是是f fa, ba, b逆元，即逆元，即验证等式验证等式f fa, ba, b f f1/a, 1/a, b/ab/a = f = f1/a, 1/a, b/ab/a f fa, ba, b = f = f1,01,0，显然此等式成立，所以显然此等式成立，所以f f1/a, 1/a, b/ab/a是是f fa, ba, b的逆元。的逆元。由由f fa, ba, b的任意性，可得的任意性，可得G G中的任何一个元都有逆元。中的任何一个元都有逆元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程61结论结论（1 1）是代数系统；是代数系统；（2 2）幺元是）幺元是f f1, 01, 0；（3 3）中没有零元；中没有零元；（4 4）中唯一幂等元是中唯一幂等元是f f1, 01, 0；（5 5）中任意元中任意元f fa, ba, b的逆元是的逆元是f f1/a, 1/a, b/ab/a 。 计算幺元、零元、幂等元、逆元等特殊元时，计算幺元、零元、幂等元、逆元等特殊元时，首首先先可以假设这些元存在，可以假设这些元存在，然后然后根据定义直接得到根据定义直接得到方程，解这个方程就可以计算出这些元，如果方方程，解这个方程就可以计算出这些元，如果方程无解，则特殊元不存在，如果方程存在解，则程无解，则特殊元不存在，如果方程存在解，则根据特殊元的定义还需要根据特殊元的定义还需要进一步进一步验证所求解是否验证所求解是否是对应的特殊元。是对应的特殊元。 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程62作业作业P268P268：2. (2)2. (2)、（、（3 3）4 4、6 6、9 9、13132024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程6312.4 12.4 同态与同构同态与同构在现实社会中，存在着很多代数系统，但仔细分析在现实社会中，存在着很多代数系统，但仔细分析这些众多的代数系统发现，有些代数系统，他们之这些众多的代数系统发现，有些代数系统，他们之间表面上似乎不相同，但他们实际上间表面上似乎不相同，但他们实际上 “相同相同” 。如有两个代数系统如有两个代数系统 和和 ，其运算，其运算“* *”和和“”“”分别定义如下表分别定义如下表 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程64定义定义12.4.112.4.1设设A, 和和B, 为两个二元代数系统，为两个二元代数系统，是是A A到到B B的映射。对任意的映射。对任意x, yAx, yA，都有，都有(x(x y) = (x) y) = (x) (y) (y)， (1)(1)则称则称是从是从A, 到到B, 的的同态映射同态映射，称，称(A)(A)为为同态象同态象，其中，其中(A) = (x) | xA(A) = (x) | xA。如果存在一个从如果存在一个从A, 到到B, 的同态映射，则的同态映射，则称称A, 与与B, 同态同态，记为，记为A, 。当当A = BA = B时，称其同态为时，称其同态为自同态自同态。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程65定义定义12.4.112.4.1（续）（续）当同态映射当同态映射分别是单射、满射、双射时，分别称分别是单射、满射、双射时，分别称是是单一同态映射单一同态映射、满同态映射满同态映射、同构映射同构映射。如果存在一个从如果存在一个从A, 到到B, 的同构映射（单的同构映射（单一同态映射、满同态映射），则称代数系统一同态映射、满同态映射），则称代数系统A, 与与B, 同构同构（单一同态、满同态单一同态、满同态）。）。用用A, 表示表示A, 与与B, 同构同构。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程66同态与同构同态与同构同态与同构是代数系统中一个非常重要的概念，它同态与同构是代数系统中一个非常重要的概念，它体现了两个代数系统之间的某种联系，后面章节将体现了两个代数系统之间的某种联系，后面章节将会学习半群、群、格、布尔代数等典型的代数系统，会学习半群、群、格、布尔代数等典型的代数系统，那么将同态与同构的概念应用到这些典型的代数系那么将同态与同构的概念应用到这些典型的代数系统，就会得到半群、群、格、布尔代数的同态与同统，就会得到半群、群、格、布尔代数的同态与同态。态。n注意注意，后面章节中半群、群、格、布尔代数的同，后面章节中半群、群、格、布尔代数的同态与同态本质上就是把半群、群、格、布尔代数看态与同态本质上就是把半群、群、格、布尔代数看作一般代数系统的同态与同构，即定义作一般代数系统的同态与同构，即定义12.4.112.4.1。因。因此，后面不再赘述半群、群、格、布尔代数中同态此，后面不再赘述半群、群、格、布尔代数中同态与同构的定义。与同构的定义。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67例例12.4.112.4.1设代数系统设代数系统和和中，中，Z Z、E E分别是整数集分别是整数集和偶数集，和偶数集，“+ +”是加法，证明是加法，证明。分析分析 证明两个代数系统同构，关键是找出同构映证明两个代数系统同构，关键是找出同构映射。假设射。假设f f是是到到的同构映射，根据同构的同构映射，根据同构映射的定义，有映射的定义，有 x, yZx, yZ，f(x + y) = f(x) + f(y),f(x + y) = f(x) + f(y),特别取特别取x = 0, y = 0x = 0, y = 0，有，有f(0) = f(0 + 0) = f(0) + f(0)f(0) = f(0 + 0) = f(0) + f(0)，可得，可得f(0) = 0f(0) = 0。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程68例例12.4.112.4.1（续）（续） nZ, f(n) = f(nnZ, f(n) = f(n 1 + 1) = f(n1 + 1) = f(n 1) + f(1), 1) + f(1), 可得递推公式如下：可得递推公式如下：f(n) = f(nf(n) = f(n 1) + f(1),1) + f(1),如果如果f(1) 0f(1) 0，则，则f(n)f(n)是递增函数，是递增函数，0 = f(0) f(1) f(2)0 = f(0) f(1) f(2)，而而f f又是又是Z Z到到E E的双射，因此此时必有的双射，因此此时必有f(1) = 2f(1) = 2，同理，如果同理，如果f(1) 0f(1) 0，可得，可得 f(1) = f(1) = 2 2。根据以上分析可知，根据以上分析可知， nZ, f(n) = 2nnZ, f(n) = 2n或或f(n) = f(n) = 2n2n，2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程69例例12.4.112.4.1（续）（续）以上说明，如果以上说明，如果f f是同构映射，则是同构映射，则f(n) = 2nf(n) = 2n或或f(n) = f(n) = 2n2n，因此需进一步验证因此需进一步验证f(n) = 2nf(n) = 2n或或f(n) = f(n) = 2n2n是否是同是否是同构映射。构映射。证明证明 nZnZ，令，令f(n) = 2nf(n) = 2n，则显然，则显然f f是是Z Z到到E E的双射，的双射，又对又对 x x，yZyZ，有，有f(x + y) = 2(x + y) = 2x + 2y = f(x) + f(y)f(x + y) = 2(x + y) = 2x + 2y = f(x) + f(y)，因此因此f f是同构映射，同理可证是同构映射，同理可证f(n) = f(n) = 2n2n也是同构映也是同构映射。故有射。故有。 n结论结论 证明两个代数系统的同态与同构关键是构造出同证明两个代数系统的同态与同构关键是构造出同态与同构映射，构造同态与同构映射没有一个通用的方法，态与同构映射，构造同态与同构映射没有一个通用的方法，但一般思路如下：首先可以假设但一般思路如下：首先可以假设f f就是同态或同构映射，就是同态或同构映射，然后利用同态与同构的定义，导出然后利用同态与同构的定义，导出f f的一些性质，并利用的一些性质，并利用这些性质来构造同态与同构映射。这些性质来构造同态与同构映射。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程70定理定理12.4.112.4.1设设是是A, 到到B, 的同态映射，那么的同态映射，那么(A), 是是B 的子代数。的子代数。分析分析 需证需证(A)(A) 非空，且运算非空，且运算“ ”对对(A)(A)封闭。封闭。证明证明 由于由于A A非空，所以显然非空，所以显然(A)(A)为为B B的非空子集。的非空子集。对任意对任意x, y(A)x, y(A)，存在，存在a, bAa, bA，使得，使得(a) = x(a) = x，(b) = y(b) = y，有，有x x y = (a) y = (a) (b) = (a (b) = (a b) b)，因为因为a a bA bA，所以，所以(a (a b) (A) b) (A)，即，即x x y(A) y(A)，故故“ ” (A)(A)对封闭，得证。对封闭，得证。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程71定理定理12.4.2 12.4.2 设设是二元代数系统是二元代数系统A, 到到B, 的满同态，则：的满同态，则：（1 1）若）若“ ”可交换，则可交换，则“ ”也可交换；也可交换；（2 2）若）若“ ”可结合，则可结合，则“ ”也可结合；也可结合；（3 3）若）若e e是是A, 的幺元，则的幺元，则(e)(e)是是B, 的幺的幺元；元；（4 4）若）若 是是A, 的零元，则的零元，则( ) )是是B, 的零的零元；元；2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程72定理定理12.4.212.4.2（续）（续）（5 5）若）若a a是是A, 的幂等元，则的幂等元，则(a)(a)是是B, 的的幂等元；幂等元；（6 6）若）若x x 1 1是是x x在在A, 中的逆元，则中的逆元，则(x(x 1)1)是是(x)(x)在在B, 中的逆元；中的逆元；（7 7）若）若a a是是A, 的（左、右）可消去元，则的（左、右）可消去元，则(a)(a)是是B, 的（左、右）可消去元。的（左、右）可消去元。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程73定理定理12.4.212.4.2（续）（续）证明证明 （1 1）对任意的）对任意的x, yBx, yB，因为，因为是满射，所是满射，所以存在以存在a, bAa, bA，使得，使得(a) = x, (b) = y(a) = x, (b) = y，因为运算因为运算“ ”在在A A中可交换，则有中可交换，则有a a b = b b = b a, a, 于是于是x x y = (a) y = (a) (b) = (a (b) = (a b) = (b b) = (b a) a) = (b) = (b) (a) = y(a) = y x x，所以运算所以运算“ ”在在B B中满足交换律。中满足交换律。（2 2）类似（）类似（1 1），略。），略。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程74定理定理12.4.212.4.2（续）（续）（3 3）对）对 xBxB，因为，因为是满射，所以存在是满射，所以存在aBaB，使，使得得(a) = x(a) = x，又，又e e是是A, 的幺元，则有的幺元，则有a a e = e e = e a = a, a = a,于是于是x x (e) = (a) (e) = (a) (e) (e) = (a = (a e) = (a) = x e) = (a) = x，(e) (e) x = (e) x = (e) (a) (a) = (e = (e a) = (a) = x a) = (a) = x，所以有，所以有 x x (e) = (e) (e) = (e) x = xx = x，由由x x的任意性，可知的任意性，可知(e)(e)是是B, 的幺元。的幺元。其它类似（其它类似（3 3），略。），略。2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程75定理定理12.4.312.4.3设设是代数系统是代数系统A, 到到B, 的满同的满同态，这里态，这里 i i和和i i(i = 1, 2)(i = 1, 2)均为二元运算，那么有均为二元运算，那么有（1 1）若运算）若运算“ 1 1”对对“ 2 2”在在A A中满足分配律，中满足分配律，则则“ 1 1”对对“ 2 2”在在B B中也满足分配律；中也满足分配律；（2 2）若运算）若运算“ 1 1”和和“ 2 2”在在A A中满足吸收律，中满足吸收律，则则“ 1 1”和和“ 2 2”在在B B中也满足吸收律。中也满足吸收律。证明证明 定理的证明类似与定理定理的证明类似与定理12.4.212.4.22024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程76同构关系同构关系令令P = x| xP = x| x是代数系统是代数系统 ， = | x, = | x, yP,yP,且且x x与与y y同构同构 ，则很容易证明，则很容易证明是是P P上等价关上等价关系，由该等价关系可以得到等价类，在同一个等价系，由该等价关系可以得到等价类，在同一个等价类的两个代数系统同构，它们在同构的意义下可以类的两个代数系统同构，它们在同构的意义下可以看作是相同的代数系统，具有完成相同的代数性质。看作是相同的代数系统，具有完成相同的代数性质。称称“”为为同构关系同构关系。 2024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程77作业作业P269P269：1313171722222024/9/172024/9/17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程/ /