(1.6)--离散数学离散数学.ppt

《(1.6)--离散数学离散数学.ppt》由会员分享，可在线阅读，更多相关《(1.6)--离散数学离散数学.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2024/1/20离散数学12024/1/20离散数学2前面讨论了集合及其运算，这是将集合作为一个整前面讨论了集合及其运算，这是将集合作为一个整前面讨论了集合及其运算，这是将集合作为一个整前面讨论了集合及其运算，这是将集合作为一个整体进行讨论；集合上的关系，进一步讨论了集合中元体进行讨论；集合上的关系，进一步讨论了集合中元体进行讨论；集合上的关系，进一步讨论了集合中元体进行讨论；集合上的关系，进一步讨论了集合中元素的内在联系。素的内在联系。素的内在联系。素的内在联系。而现在我们要讨论的代数系统，是讨论集合中元素而现在我们要讨论的代数系统，是讨论集合中元素而现在我们要讨论的代数系统，是讨论集合中

2、元素而现在我们要讨论的代数系统，是讨论集合中元素的运算问题，讨论代数系统的结构与性质。的运算问题，讨论代数系统的结构与性质。的运算问题，讨论代数系统的结构与性质。的运算问题，讨论代数系统的结构与性质。2024/1/20离散数学3代数系统代数系统这部分内容属于近世代数的范畴，近世代数是研这部分内容属于近世代数的范畴，近世代数是研这部分内容属于近世代数的范畴，近世代数是研这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变究具有运算的集合，它第一次揭示了数学系统的多变究具有运算的集合，它第一次揭示了数学系统的多变究具有运算的集合，它第一次揭示了数学系统的多变性与

3、丰富性。性与丰富性。性与丰富性。性与丰富性。在计算机科学里，很多的知识和代数结构的理论有关系，在计算机科学里，很多的知识和代数结构的理论有关系，在计算机科学里，很多的知识和代数结构的理论有关系，在计算机科学里，很多的知识和代数结构的理论有关系，比如：加法器、纠正码、形式语言和推理机等等，因此，学比如：加法器、纠正码、形式语言和推理机等等，因此，学比如：加法器、纠正码、形式语言和推理机等等，因此，学比如：加法器、纠正码、形式语言和推理机等等，因此，学好该部分内容，为学习其他课程打下了基础。好该部分内容，为学习其他课程打下了基础。好该部分内容，为学习其他课程打下了基础。好该部分内容，为学习其他课程

4、打下了基础。本课程在第五，六章中介绍代数系统的内容。本课程在第五，六章中介绍代数系统的内容。本课程在第五，六章中介绍代数系统的内容。本课程在第五，六章中介绍代数系统的内容。2024/1/20离散数学4第六章第六章 代数系统的一般性质代数系统的一般性质 6.16.1 二元运算及其性质二元运算及其性质二元运算及其性质二元运算及其性质 6.26.2 代数系统及其子代数代数系统及其子代数代数系统及其子代数代数系统及其子代数 6.36.3 代数系统的同态与同构代数系统的同态与同构代数系统的同态与同构代数系统的同态与同构 2024/1/20离散数学5内容：内容：二元运算，运算律，特殊元素。重点：重点：(1

5、)二元运算的概念，(2)二元运算律(结合律，交换律，分配律)，(3)二元运算的特殊元素(幺元，零元，逆元)。一般：一般：吸收律，消去律，幂等律。6.1 6.1 二元运算及其性质二元运算及其性质2024/1/20离散数学6如：集合如：集合如：集合如：集合Z Z对加、减、乘法封闭，但对除法不封闭。对加、减、乘法封闭，但对除法不封闭。对加、减、乘法封闭，但对除法不封闭。对加、减、乘法封闭，但对除法不封闭。验证运算是否为集合验证运算是否为集合验证运算是否为集合验证运算是否为集合S S上的二元运算，首先需要上的二元运算，首先需要上的二元运算，首先需要上的二元运算，首先需要验证集合验证集合验证集合验证集合

6、S S对该运算的封闭性。对该运算的封闭性。对该运算的封闭性。对该运算的封闭性。一、二元运算的概念二元运算：二元运算：二元运算：二元运算：设设设设S S为集合，函数为集合，函数为集合，函数为集合，函数f f:S S S S S S称为称为称为称为S S上上上上 的一个二元运算，简称为二元运算。的一个二元运算，简称为二元运算。的一个二元运算，简称为二元运算。的一个二元运算，简称为二元运算。6.1 6.1 二元运算及其性质二元运算及其性质集合对运算的集合对运算的集合对运算的集合对运算的封闭性：封闭性：封闭性：封闭性：设设设设*是定义在集合是定义在集合是定义在集合是定义在集合A A上的二元运算，上的二

7、元运算，上的二元运算，上的二元运算，如果对于如果对于如果对于如果对于任意的任意的任意的任意的x x，y yA A，都有都有都有都有x*x*y yA A，则称二元运算，则称二元运算，则称二元运算，则称二元运算*在在在在A A上是封闭的。上是封闭的。上是封闭的。上是封闭的。2024/1/20离散数学7一、二元运算的概念（续）例如：设例如：设例如：设例如：设A=A=x|xx|x=5=5n n,n n Z Z；普通乘法运算在；普通乘法运算在；普通乘法运算在；普通乘法运算在A A上是上是上是上是否封闭否封闭否封闭否封闭?普通加法运算在普通加法运算在普通加法运算在普通加法运算在A A上是否封闭上是否封闭上

8、是否封闭上是否封闭?解：解：解：解：对于任意的对于任意的对于任意的对于任意的5 5n n，5 5mm Z Z，因为，因为，因为，因为5 5n n55mm5 5n+mn+m A A，所以，普通乘法运算在所以，普通乘法运算在所以，普通乘法运算在所以，普通乘法运算在A A上是封闭的；上是封闭的；上是封闭的；上是封闭的；而普通加法运算在而普通加法运算在而普通加法运算在而普通加法运算在A A上不封闭例如，上不封闭例如，上不封闭例如，上不封闭例如，5 5十十十十5 52 23030 A A2024/1/20离散数学8一、二元运算的概念（续）常见二元运算：常见二元运算：常见二元运算：常见二元运算：(1)(1

9、)设设设设f f:N N N N N N，f f()=)=x x+y y，则，则，则，则f f 是集合是集合是集合是集合 N N上的二元运算。即自然数集合上的二元运算。即自然数集合上的二元运算。即自然数集合上的二元运算。即自然数集合N N上的加法运算上的加法运算上的加法运算上的加法运算是是是是N N上的二元运算，乘法运算也是，但减法和除上的二元运算，乘法运算也是，但减法和除上的二元运算，乘法运算也是，但减法和除上的二元运算，乘法运算也是，但减法和除法不是。法不是。法不是。法不是。(2)(2)整数集合整数集合整数集合整数集合Z Z上的加、减、乘法运算是上的加、减、乘法运算是上的加、减、乘法运算是

10、上的加、减、乘法运算是Z Z上的二元上的二元上的二元上的二元运算，但除法不是。运算，但除法不是。运算，但除法不是。运算，但除法不是。(3)(3)设设设设MMn n(R R)表示所有表示所有表示所有表示所有n n阶实矩阵的集合，则矩阵的阶实矩阵的集合，则矩阵的阶实矩阵的集合，则矩阵的阶实矩阵的集合，则矩阵的加法和乘法都是加法和乘法都是加法和乘法都是加法和乘法都是MMn n(R R)上的二元运算。上的二元运算。上的二元运算。上的二元运算。2024/1/20离散数学9一、二元运算的概念（续）(4)(4)S S为任意集合，为任意集合，为任意集合，为任意集合，P P(S S)为其幂集，则为其幂集，则为其

11、幂集，则为其幂集，则,都都都都是是是是P P(S S)上的二元运算。上的二元运算。上的二元运算。上的二元运算。(5)(5)S S为集合，为集合，为集合，为集合，S SS S是是是是S S上的所有函数的集合，则合成上的所有函数的集合，则合成上的所有函数的集合，则合成上的所有函数的集合，则合成运算运算运算运算 是是是是S SS S上的二元运算。上的二元运算。上的二元运算。上的二元运算。(6)(6)非零实数集非零实数集非零实数集非零实数集R R*上的乘法和除法都是二元运算。但上的乘法和除法都是二元运算。但上的乘法和除法都是二元运算。但上的乘法和除法都是二元运算。但加法，加法，加法，加法，减法不是，而

12、求倒数是一元运算。减法不是，而求倒数是一元运算。减法不是，而求倒数是一元运算。减法不是，而求倒数是一元运算。n n元运算：元运算：元运算：元运算：设设设设S S为集合，为集合，为集合，为集合，n n为正整数，则函数为正整数，则函数为正整数，则函数为正整数，则函数 f f:S S S S S S S S称为称为称为称为S S上的一个上的一个上的一个上的一个n n元运算，元运算，元运算，元运算，简称为简称为简称为简称为n n元运算。元运算。元运算。元运算。n n个个个个2024/1/20离散数学10一、二元运算的概念（续）二元运算通常用符号二元运算通常用符号二元运算通常用符号二元运算通常用符号 ,

13、来表示。来表示。来表示。来表示。如：如：如：如：f f:N N N N N N，对，对，对，对 x x,y y N N，f f()=)=x x+y y 可简记为可简记为可简记为可简记为 (x x,y y)=x x+y y 或或或或x x y y=x x+y y。g g:N N N N，g g(x x)=)=y y 可简记为可简记为可简记为可简记为 (x x)=y y。2024/1/20离散数学11一、二元运算的概念（续）有限集上的一元、二元运算也可用运算表给出。有限集上的一元、二元运算也可用运算表给出。有限集上的一元、二元运算也可用运算表给出。有限集上的一元、二元运算也可用运算表给出。a a1

14、1a a11 a a11a a11 a a22a a11 a an n a a1 1a a22a an na a22a a22 a a11a a22 a a22a a22 a an n a an n a an n a a11a an n a a22a an n a an n a an n (a an n)(a ai i)a a11 (a a1 1)a a22 (a a2 2)2024/1/20离散数学12一、二元运算的概念（续）例例例例1 1：设：设：设：设S S=0,1,2,3,4=0,1,2,3,4，定义，定义，定义，定义S S上的二元运算如下：上的二元运算如下：上的二元运算如下：上的二元

15、运算如下：x x y y=(=(x+yx+y)mod mod 5 5，x x,y y S S;x x y y=(=(xyxy)mod mod 5 5，x x,y y S S.求求求求 和和和和*的运算表。的运算表。的运算表。的运算表。001 12342340 01 12 23 34 40 01 12 23 31 12 23 34 42 23 34 40 03 34 40 01 14 40 01 12 24 40 01 12 23 32024/1/20离散数学13一、二元运算的概念（续）例例例例1 1：设：设：设：设S S=0,1,2,3,4=0,1,2,3,4，定义，定义，定义，定义S S上的

16、二元运算如下：上的二元运算如下：上的二元运算如下：上的二元运算如下：x x y y=(=(x+yx+y)mod mod 5 5，x x,y y S S;x x y y=(=(x x y y)mod mod 5 5，x x,y y S S.求求求求 和和和和*的运算表。的运算表。的运算表。的运算表。001 12342340 01 12 23 34 40 00 00 00 00 01 12 23 30 02 24 41 10 03 31 14 40 04 43 32 20 04 43 32 21 12024/1/20离散数学14例如：例如：例如：例如：设设设设QQ是有理数集合，是有理数集合，是有理

17、数集合，是有理数集合，是是是是QQ上的二元运算，对任意的上的二元运算，对任意的上的二元运算，对任意的上的二元运算，对任意的a a，b b QQ，有，有，有，有a a b ba a十十十十b b一一一一abab，运算，运算，运算，运算 是否可交换是否可交换是否可交换是否可交换?事实上，事实上，事实上，事实上，因为因为因为因为a a b ba a十十十十b b一一一一abab=b b十十十十a a一一一一baba=b b a a所以是可交换的所以是可交换的所以是可交换的所以是可交换的二、二元运算的性质1 1、交换律交换律交换律交换律：设：设：设：设 是是是是S S上的二元运算，若对上的二元运算，若

18、对上的二元运算，若对上的二元运算，若对 x x,y y S S都都都都有有有有x x y y=y y x x，则称运算，则称运算，则称运算，则称运算 在在在在S S上是可交换的。上是可交换的。上是可交换的。上是可交换的。如：如：如：如：Z Z上的加法满足交换律，但减法不满足交换律。上的加法满足交换律，但减法不满足交换律。上的加法满足交换律，但减法不满足交换律。上的加法满足交换律，但减法不满足交换律。幂集幂集幂集幂集P P(S S)上的上的上的上的,满足交换律。满足交换律。满足交换律。满足交换律。2024/1/20离散数学15如：如：如：如：Z Z上的减法不满足结合律。幂集上的减法不满足结合律。

19、幂集上的减法不满足结合律。幂集上的减法不满足结合律。幂集P P(S S)上的上的上的上的,满足结合律。满足结合律。满足结合律。满足结合律。二、二元运算的性质2 2、结合律结合律结合律结合律：设：设：设：设 是是是是S S上的二元运算，若对上的二元运算，若对上的二元运算，若对上的二元运算，若对 x x,y y,z z S S 都有都有都有都有(x x y y)z z=x x (y y z z)，则称运算，则称运算，则称运算，则称运算 在在在在S S上上上上是可结合的。是可结合的。是可结合的。是可结合的。例例例例:设设设设A A是一个非空集合，是一个非空集合，是一个非空集合，是一个非空集合，*是是

20、是是A A上的二元运算上的二元运算上的二元运算上的二元运算,对任意对任意对任意对任意a,ba,b A A，有，有，有，有a*b=b.a*b=b.问问问问*是否为可结合的？是否为可结合的？是否为可结合的？是否为可结合的？因为因为因为因为 对于任意的对于任意的对于任意的对于任意的a a，b b，c c A A，有，有，有，有(a*b)*c=b*c=c,a*(b*c)=a*c=c,(a*b)*c=b*c=c,a*(b*c)=a*c=c,则则则则(a*b)*=a*(b*c)(a*b)*=a*(b*c)，所以是可结合的。所以是可结合的。所以是可结合的。所以是可结合的。2024/1/20离散数学16二、二

21、元运算的性质（续）3 3、幂等律幂等律幂等律幂等律：设：设：设：设 是是是是S S上的二元运算，若对上的二元运算，若对上的二元运算，若对上的二元运算，若对 x x S S都都都都有有有有x x x x=x x，则称运算，则称运算，则称运算，则称运算 适合幂等律。适合幂等律。适合幂等律。适合幂等律。也即是也即是也即是也即是 S S中的所有元素都是幂等元。中的所有元素都是幂等元。中的所有元素都是幂等元。中的所有元素都是幂等元。如：幂集如：幂集如：幂集如：幂集P P(S S)上的上的上的上的,运算适合幂等律，但运算适合幂等律，但运算适合幂等律，但运算适合幂等律，但 运算运算运算运算不适合幂等律。不适

22、合幂等律。不适合幂等律。不适合幂等律。对于任意的对于任意的对于任意的对于任意的A AP(S)P(S)，有，有，有，有A AA AA A和和和和AAAAA A，因此运算，因此运算，因此运算，因此运算和和和和 都都都都满足等幂律。满足等幂律。满足等幂律。满足等幂律。2024/1/20离散数学174 4、分配律分配律分配律分配律：设：设：设：设 和和和和 是是是是S S上的两个二元运算，若对上的两个二元运算，若对上的两个二元运算，若对上的两个二元运算，若对 x x,y y,z z S S都有都有都有都有x x (y y z z)=(=(x x y y)(x x z z)和和和和(y y z z)x

23、x=(=(y y x x)(z z x x)，则称运算，则称运算，则称运算，则称运算 对对对对 适合分配律。适合分配律。适合分配律。适合分配律。二、二元运算的性质（续）如：如：如：如：R R上的乘法对加法满足分配律，加法对乘法不上的乘法对加法满足分配律，加法对乘法不上的乘法对加法满足分配律，加法对乘法不上的乘法对加法满足分配律，加法对乘法不满足分配律。幂集满足分配律。幂集满足分配律。幂集满足分配律。幂集P P(S S)上的上的上的上的和和和和 是相互可分是相互可分是相互可分是相互可分配的。配的。配的。配的。2024/1/20离散数学18例：设集合例：设集合例：设集合例：设集合A A ，在，在，

24、在，在A A上定义两个二元运算上定义两个二元运算上定义两个二元运算上定义两个二元运算 和和和和*，运算要求如表，运算要求如表，运算要求如表，运算要求如表1 1、表、表、表、表2 2所示所示所示所示运算运算运算运算*对对对对 可分配吗可分配吗可分配吗可分配吗?对对对对*可分配吗可分配吗可分配吗可分配吗?*表表表表1 1表表表表2 22024/1/20离散数学19(1)对对对对*可分配可分配可分配可分配.（验证所有可能的情况）（验证所有可能的情况）（验证所有可能的情况）（验证所有可能的情况）(2)(2)*对对对对 不可分配。不可分配。不可分配。不可分配。2024/1/20离散数学206 6、消去律

25、消去律消去律消去律：设：设：设：设 是是是是S S上的二元运算，若对上的二元运算，若对上的二元运算，若对上的二元运算，若对 x x,y y,z z S S，满足：满足：满足：满足：(1)(1)若若若若x x y y=x x z z且且且且x x不是零元，则不是零元，则不是零元，则不是零元，则y y=z z。(2)(2)若若若若y y x x=z z x x且且且且x x不是零元，则不是零元，则不是零元，则不是零元，则y y=z z。则称运算则称运算则称运算则称运算 满足消去律。满足消去律。满足消去律。满足消去律。5 5、吸收律吸收律吸收律吸收律：设：设：设：设 和和和和 是是是是S S上的两个

26、可交换的二元运算，上的两个可交换的二元运算，上的两个可交换的二元运算，上的两个可交换的二元运算，若对若对若对若对 x x,y y S S，都有，都有，都有，都有x x (x x y y)=x x 和和和和 x x (x x y y)=x x，则称运算，则称运算，则称运算，则称运算 和和和和 满足吸收律。满足吸收律。满足吸收律。满足吸收律。二、二元运算的性质（续）如：幂集如：幂集如：幂集如：幂集P P(S S)上的上的上的上的和和和和 运算满足吸收律。运算满足吸收律。运算满足吸收律。运算满足吸收律。2024/1/20离散数学21例：例：例：例：2024/1/20离散数学22例例例例3 3：判断普

27、通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二元运算。元运算。元运算。元运算。(1)(1)S S1 1=1,2,(2)=1,2,(2)S S2 2=0,1,(3)=0,1,(3)S S3 3=2=2x x x x Z Z+,(4)(4)S S4 4=2=2x x-1-1 x x Z Z+,(5),(5)S S5 5=x x=2=2n n n n Z Z+.三、集合S S的特殊元（续）解：解：解：解：(1)(1)(1)(1)因因因因1+2=31+2=31+2=31+2=3 S S1

28、 1,2,2,2,22=42=42=42=4 S S1 1 ，所以关于加法，所以关于加法，所以关于加法，所以关于加法，乘法运算不封闭，不是二元运算。乘法运算不封闭，不是二元运算。乘法运算不封闭，不是二元运算。乘法运算不封闭，不是二元运算。(2)(2)(2)(2)因因因因1+1=21+1=21+1=21+1=2 S S2 2,故故故故S S2 2关于加法运算不封闭，不是关于加法运算不封闭，不是关于加法运算不封闭，不是关于加法运算不封闭，不是二元运算。二元运算。二元运算。二元运算。0 0 0 00=00=00=00=0，0 0 0 01=0,11=0,11=0,11=0,10=0,10=0,10=

29、0,10=0,11=1 1=1 1=1 1=1 S S2 2 ，所以，所以，所以，所以S S2 2关于乘法运算封闭，是二元运算。关于乘法运算封闭，是二元运算。关于乘法运算封闭，是二元运算。关于乘法运算封闭，是二元运算。2024/1/20离散数学23例例例例3 3：判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二元运算。元运算。元运算。元运算。(1)(1)S S1 1=1,2,(2)=1,2,(2)S S2 2=0,1,(3)=0,1,(3)S S3 3=2=2x x x x

30、Z Z+,(4)(4)S S4 4=2=2x x-1-1 x x Z Z+,(5),(5)S S5 5=x x=2=2n n n n Z Z+.三、集合S S的特殊元（续）解：解：解：解：(3)(3)(3)(3)因因因因2 2x x是偶数，是偶数，是偶数，是偶数，S S3 3是全体偶数的集合，偶数是全体偶数的集合，偶数是全体偶数的集合，偶数是全体偶数的集合，偶数偶数，偶数偶数，偶数偶数，偶数偶数，偶数偶数都是偶数，所以关于加法，乘偶数都是偶数，所以关于加法，乘偶数都是偶数，所以关于加法，乘偶数都是偶数，所以关于加法，乘法运算封闭，是二元运算。法运算封闭，是二元运算。法运算封闭，是二元运算。法运

31、算封闭，是二元运算。(4)(4)(4)(4)因因因因2 2x x-1-1是奇数，是奇数，是奇数，是奇数，S S4 4是全体奇数的集合，奇数是全体奇数的集合，奇数是全体奇数的集合，奇数是全体奇数的集合，奇数奇数奇数奇数奇数=偶数，奇数偶数，奇数偶数，奇数偶数，奇数奇数奇数，所以加法不是二奇数奇数，所以加法不是二奇数奇数，所以加法不是二奇数奇数，所以加法不是二元运算，乘法是二元运算。元运算，乘法是二元运算。元运算，乘法是二元运算。元运算，乘法是二元运算。2024/1/20离散数学24例例例例3 3：判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二判断普通的加法和

32、乘法运算在下列集合中是否二判断普通的加法和乘法运算在下列集合中是否二元运算。元运算。元运算。元运算。(1)(1)S S1 1=1,2,(2)=1,2,(2)S S2 2=0,1,(3)=0,1,(3)S S3 3=2=2x x x x Z Z+,(4)(4)S S4 4=2=2x x-1-1 x x Z Z+,(5),(5)S S5 5=x x=2=2n n n n Z Z+.三、集合S S的特殊元（续）解：解：解：解：(5)(5)(5)(5)因因因因2 2，4 4 S S5 5，但，但，但，但2+4=6 2+4=6 2+4=6 2+4=6 S S5 5,故加法不是二故加法不是二故加法不是二故

33、加法不是二元运算，元运算，元运算，元运算，2 2k k 2 2l l2 2k kl l S S5 5，所以乘法运算封闭，所以乘法运算封闭，所以乘法运算封闭，所以乘法运算封闭，是二元运算。是二元运算。是二元运算。是二元运算。2024/1/20离散数学25三、集合S S的特殊元1 1、左幺元（右幺元）左幺元（右幺元）左幺元（右幺元）左幺元（右幺元）：设：设：设：设 是是是是S S上的二元运算，上的二元运算，上的二元运算，上的二元运算，若存在元素若存在元素若存在元素若存在元素e el l(或或或或e er r)S S，使得对，使得对，使得对，使得对 x x S S都有都有都有都有 e el l x

34、x=x x(或或或或x x e er r=x x)，则称，则称，则称，则称e el l(或或或或e er r)是是是是S S中中中中 关于运算关于运算关于运算关于运算 的一个左幺元（或右幺元）。的一个左幺元（或右幺元）。的一个左幺元（或右幺元）。的一个左幺元（或右幺元）。如：自然数集上的加法运算的幺元是如：自然数集上的加法运算的幺元是如：自然数集上的加法运算的幺元是如：自然数集上的加法运算的幺元是0 0，乘法运算的，乘法运算的，乘法运算的，乘法运算的幺元是幺元是幺元是幺元是1 1，幂集，幂集，幂集，幂集P P(S S)上的上的上的上的运算和运算和运算和运算和 运算的幺元运算的幺元运算的幺元运算

35、的幺元是是是是，运算的幺元是运算的幺元是运算的幺元是运算的幺元是S S。若若若若e e S S关于运算关于运算关于运算关于运算 既是左幺元又是右幺元，既是左幺元又是右幺元，既是左幺元又是右幺元，既是左幺元又是右幺元，则称则称则称则称e e为为为为S S上关于运算上关于运算上关于运算上关于运算 的幺元。的幺元。的幺元。的幺元。2024/1/20离散数学26例如：例如：例如：例如：2024/1/20离散数学27因为因为因为因为例如：例如：例如：例如：2024/1/20离散数学28例：设集合例：设集合例：设集合例：设集合S S 浅色，深色浅色，深色浅色，深色浅色，深色，在，在，在，在S S上定义一个

36、二元运上定义一个二元运上定义一个二元运上定义一个二元运算算算算*，运算规则如表所示，试指出么元，运算规则如表所示，试指出么元，运算规则如表所示，试指出么元，运算规则如表所示，试指出么元*浅色浅色 深色深色浅色浅色 浅色浅色 深色深色深色深色 深色深色 深色深色左幺元左幺元左幺元左幺元右幺元右幺元右幺元右幺元所以，浅色是么元所以，浅色是么元所以，浅色是么元所以，浅色是么元解解解解:因为因为因为因为浅色浅色浅色浅色*深色深色，深色深色，深色深色，深色深色，浅色浅色浅色浅色*浅色浅色，浅色浅色，浅色浅色，浅色浅色，深色深色深色深色*浅色深色，浅色深色，浅色深色，浅色深色，2024/1/20离散数学2

37、9如：自然数集上的加法运算无零元，乘法运算的零元如：自然数集上的加法运算无零元，乘法运算的零元如：自然数集上的加法运算无零元，乘法运算的零元如：自然数集上的加法运算无零元，乘法运算的零元是是是是0 0，幂集，幂集，幂集，幂集P P(S S)上的上的上的上的运算的零元是运算的零元是运算的零元是运算的零元是S S，运算的运算的运算的运算的零元是零元是零元是零元是。三、集合S S的特殊元（续）2 2、左零元（右零元）左零元（右零元）左零元（右零元）左零元（右零元）：设：设：设：设 是是是是S S上的二元运算，上的二元运算，上的二元运算，上的二元运算，若存在元素若存在元素若存在元素若存在元素 l l(

38、或或或或 r r)S S，使得对，使得对，使得对，使得对 x x S S都有都有都有都有 l l x x=l l (或或或或x x r r=r r)，则称，则称，则称，则称 l l(或或或或 r r)是是是是S S 中关于运算中关于运算中关于运算中关于运算 的一个左零元（或右零元）。的一个左零元（或右零元）。的一个左零元（或右零元）。的一个左零元（或右零元）。若若若若 S S关于运算关于运算关于运算关于运算 既是左零元又是右零元，既是左零元又是右零元，既是左零元又是右零元，既是左零元又是右零元，则称则称则称则称 为为为为S S上关于运算上关于运算上关于运算上关于运算 的零元。的零元。的零元。的

39、零元。2024/1/20离散数学30指出下表所定义的运算的左（右）零元：指出下表所定义的运算的左（右）零元：指出下表所定义的运算的左（右）零元：指出下表所定义的运算的左（右）零元：123112322223312*abcdabbdabbbbbcdbbcdabcd1231133222333132024/1/20离散数学31例：设集合例：设集合例：设集合例：设集合S S 浅色，深色浅色，深色浅色，深色浅色，深色，在，在，在，在S S上定义一个二元运上定义一个二元运上定义一个二元运上定义一个二元运算算算算*，运算规则如表所示，试指出零元，运算规则如表所示，试指出零元，运算规则如表所示，试指出零元，运算

40、规则如表所示，试指出零元*浅色浅色 深色深色浅色浅色 浅色浅色 深色深色深色深色 深色深色 深色深色 解解解解:因为因为因为因为深色深色深色深色*深色深色，深色深色，深色深色，深色深色，浅色浅色浅色浅色*深色深色，深色深色，深色深色，深色深色，深色深色深色深色*浅色深色，浅色深色，浅色深色，浅色深色，所以，深色是零元所以，深色是零元所以，深色是零元所以，深色是零元2024/1/20离散数学32三、集合S S的特殊元（续）设设设设e el l,e er r 分别是分别是分别是分别是S S上关于二元运算上关于二元运算上关于二元运算上关于二元运算 的左幺元的左幺元的左幺元的左幺元和右幺元，则有和右幺

41、元，则有和右幺元，则有和右幺元，则有e el l =e er r=e e，且，且，且，且e e是是是是S S上关于上关于上关于上关于二元运算二元运算二元运算二元运算 的唯一幺元。的唯一幺元。的唯一幺元。的唯一幺元。证明：证明：证明：证明：由由由由e el l 是左幺元有：是左幺元有：是左幺元有：是左幺元有：e el l e er r=e er r，由由由由e er r 是右幺元有：是右幺元有：是右幺元有：是右幺元有：e el l e er r=e el l ，于是有：于是有：于是有：于是有：e er r=e el l ，记，记，记，记e er r=e el l=e e又设又设又设又设S S上有

42、幺元上有幺元上有幺元上有幺元e e，则有：，则有：，则有：，则有：e e =e e e e=e e，于是于是于是于是e e是是是是S S上关于二元运算上关于二元运算上关于二元运算上关于二元运算 的唯一幺元。的唯一幺元。的唯一幺元。的唯一幺元。2024/1/20离散数学33三、集合S S的特殊元（续）设设设设 l l,r r 分别是分别是分别是分别是S S上关于二元运算上关于二元运算上关于二元运算上关于二元运算 的左零的左零的左零的左零元和右零元，则有元和右零元，则有元和右零元，则有元和右零元，则有 l l =r r=，且，且，且，且 是是是是S S上上上上关于二元运算关于二元运算关于二元运算关

43、于二元运算 的唯一零元。的唯一零元。的唯一零元。的唯一零元。（证明过程与定理（证明过程与定理（证明过程与定理（证明过程与定理1 1类似）类似）类似）类似）常见二元运算的特殊元素常见二元运算的特殊元素2024/1/20离散数学34实数实数R，+：幺元幺元0，零元零元不存在不存在实数实数R，：幺元：幺元1，零元零元0全集全集U，：幺元幺元，零元零元U全集全集U，：幺元幺元U，零元零元全集全集U，：幺元幺元幺元幺元，零元零元零元零元不存在不存在不存在不存在 命题公式集，命题公式集，：幺元：幺元0，零元零元1命题公式集，命题公式集，：幺元：幺元1，零元零元0n阶实矩阵阶实矩阵Mn(R)，+：幺元：幺元

44、O，零元零元不存在不存在n阶实矩阵阶实矩阵Mn(R)，：幺元：幺元I，零元零元O集集S S=0,1,n-1,=0,1,n-1,：幺元：幺元：幺元：幺元00零元零元零元零元 不存在不存在不存在不存在集集S S=0,1,n-1,=0,1,n-1,：幺元：幺元：幺元：幺元1 1，零元零元零元零元0 02024/1/20离散数学35如：整数集中元素如：整数集中元素如：整数集中元素如：整数集中元素x x 的加法逆元是的加法逆元是的加法逆元是的加法逆元是-x x，只有，只有，只有，只有1 1和和和和-1-1分别分别分别分别有乘法逆元有乘法逆元有乘法逆元有乘法逆元1 1和和和和-1-1，其他元素无乘法逆元。

45、，其他元素无乘法逆元。，其他元素无乘法逆元。，其他元素无乘法逆元。三、集合S S的特殊元（续）3 3、左逆元（右逆元）左逆元（右逆元）左逆元（右逆元）左逆元（右逆元）：设：设：设：设 是是是是S S上的二元运算，上的二元运算，上的二元运算，上的二元运算，e e S S是运算是运算是运算是运算 的幺元，对于的幺元，对于的幺元，对于的幺元，对于x x S S，若存在，若存在，若存在，若存在元素元素元素元素y yl l(或或或或y yr r)S S，使得，使得，使得，使得y yl l x x=e e(或或或或x x y yr r=e e)，则称则称则称则称y yl l(或或或或y yr r)是是是是

46、x x 的左逆元（或右逆元）。的左逆元（或右逆元）。的左逆元（或右逆元）。的左逆元（或右逆元）。若若若若y y S S 既是既是既是既是x x 的左逆元又是的左逆元又是的左逆元又是的左逆元又是x x 的右逆元，的右逆元，的右逆元，的右逆元，则称则称则称则称y y是是是是x x 的逆元，并记为的逆元，并记为的逆元，并记为的逆元，并记为x x 11。2024/1/20离散数学36例：设集合例：设集合例：设集合例：设集合S S，定义在，定义在，定义在，定义在S S上的一个二上的一个二上的一个二上的一个二元运算元运算元运算元运算*如表所示。如表所示。如表所示。如表所示。试指出代数系统试指出代数系统试指

47、出代数系统试指出代数系统S 中各个元素的左、右逆元情况。中各个元素的左、右逆元情况。中各个元素的左、右逆元情况。中各个元素的左、右逆元情况。解解解解 a a是幺元；是幺元；是幺元；是幺元；b b的左逆元和的左逆元和的左逆元和的左逆元和右逆元都是右逆元都是右逆元都是右逆元都是c c；即；即；即；即b b和和和和c c互互互互为逆元；为逆元；为逆元；为逆元；d d的左逆元是的左逆元是的左逆元是的左逆元是c c而而而而右逆元是右逆元是右逆元是右逆元是b b；有两个左逆有两个左逆有两个左逆有两个左逆元元元元 和和和和；e e的右逆元是的右逆元是的右逆元是的右逆元是c c，但，但，但，但e e没有左逆元

48、。没有左逆元。没有左逆元。没有左逆元。*abcdeaabcdebbdacdccababddacdceedace2024/1/20离散数学37例例例例:试构造某集合上的一个运算，使得其中只有一个试构造某集合上的一个运算，使得其中只有一个试构造某集合上的一个运算，使得其中只有一个试构造某集合上的一个运算，使得其中只有一个元素具有逆元。元素具有逆元。元素具有逆元。元素具有逆元。解：如设解：如设解：如设解：如设mm，n nN N，T Tx|xx|xN N，mxnmxn，那么，代数系统那么，代数系统那么，代数系统那么，代数系统Tmax中有一个幺元是中有一个幺元是中有一个幺元是中有一个幺元是mm，且只有且

49、只有且只有且只有mm有逆元有逆元有逆元有逆元因为因为因为因为mmmax(mmax(m，m)m)。2024/1/20离散数学38于是于是于是于是y yl l =y yr r=y y是是是是S S上上上上x x关于运算关于运算关于运算关于运算 的唯一逆元。的唯一逆元。的唯一逆元。的唯一逆元。三、集合S S的特殊元（续）设运算设运算设运算设运算 为为为为S S上可结合的二元运算，上可结合的二元运算，上可结合的二元运算，上可结合的二元运算，e e是是是是 的的的的幺元，对于幺元，对于幺元，对于幺元，对于 x x S S，若存在左逆元，若存在左逆元，若存在左逆元，若存在左逆元y yl l 和右逆和右逆和

50、右逆和右逆元元元元y yr r，则有，则有，则有，则有y yl l =y yr r=y y，且，且，且，且y y是是是是x x 的唯一逆元。的唯一逆元。的唯一逆元。的唯一逆元。证明：证明：证明：证明：由由由由y yl l 是是是是x x 的左逆元有：的左逆元有：的左逆元有：的左逆元有：y yl l x x =e e，由由由由y yr r 是是是是x x 的右逆元有：的右逆元有：的右逆元有：的右逆元有：x x y yr r=e e，则：则：则：则：y yl l=y yl l e e=y yl l (x x y yr r)=()=(y yl l x x)y yr r=e e y yr r=y yr