离散数学第5章课件

《离散数学第5章课件》由会员分享，可在线阅读，更多相关《离散数学第5章课件（94页珍藏版）》请在金锄头文库上搜索。

1、代数系统简介简介1离散数学第5章 这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。我们将介绍代数系统的最基本概念和最基本理论，以及几类常用的代数系统，它们是：半群，幺半群，群，环，域，格和布尔代数。本课程在第五，六章中介绍代数系统的内容。 2离散数学第5章第五章第五章 代数系统的一般性质代数系统的一般性质 第一节 二元运算及性质 3离散数学第5章内容：内容：二元运算，运算律，特殊元素。 重点：重点：(1) 一元和二元运算的概念， (2) 二

2、元运算律 (结合律，交换律，分配律)，(3) 二元运算的特殊元素 (幺元，零元，逆元)。一般：一般：吸收律，消去律，幂等律。4离散数学第5章一、二元运算。一、二元运算。 1、定义：定义：设上的二元运算二元运算(即运算封闭) 为集合，函数称为，元运算， 掌握，即一元，二元运算。5离散数学第5章一、二元运算。一、二元运算。 2、记号：用等符号表示二元运算，称为算符算符。例如：记为(二元运算)记为(一元运算)6离散数学第5章但减法，除法不是。 但除法不是。例例1、(1) 上的加法，乘法都是二元运算， (2)上的加法，乘法，减法都是二元运算，上求相反数的运算是一元运算。 (3) 非零实数集上的乘法和除

3、法都是二元运算。但加法，减法不是， 而求倒数是一元运算。(4) 表示所有 阶实矩阵的集合 则矩阵的加法和乘法都是二元运算。 ，7离散数学第5章都是二元运算，(5) 集合 的幂集 上的 而绝对补集(为全集)是一元运算。 (6) 所有命题公式的集合上的 都是二元运算，而否定 为一元运算。 (7) 表示集合上的所有函数的集合， 函数的合成运算 是 上的二元运算。 8离散数学第5章3、一元，二元运算表。当为有穷集时，都可以用运算表给出。上的一元和二元运算例例2、(1) 设，给出 上的运算绝对和对称差 的运算表。补集解：解：，“ ”为一元运算， “”为二元运算，其运算表如下： 9离散数学第5章10离散数

4、学第5章例2、(2) 设，定义 二元运算如下： 上的两个求运算 和 的运算表。解：解： 分别是 ，的和与积除以5的余数，运算表如下： 11离散数学第5章12离散数学第5章二、有关运算律。二、有关运算律。 设是上的二元运算， 1、若，则称 在 (或称满足交换律交换律)上可交换可交换。2、若，则称 在(或称满足结合律结合律)上可结合可结合。13离散数学第5章二、有关运算律。二、有关运算律。 设是上的二元运算， 3、若则称运算 对 是可分配可分配的。 (或称 对 满足分配律分配律) 14离散数学第5章(2) 矩阵的加法和乘法在上是可结合的，加法可交换，但乘法不可交换，乘法对加法是可分配的。例例3、(

5、1) 普通的加法和乘法在 上都是可结合的，且是可交换的，乘法对加法是可分配的。15离散数学第5章(3)在幂集上可结合，可交换，但是相对补不可结合，不可交换， 和是互相可分配的。(4) 在全体命题公式集合上可结合，可交换，和是相互可分配的。16离散数学第5章三、一些特殊元素。三、一些特殊元素。设 为上的二元运算， 1、幺元幺元：若，对 则称，为运算 的幺元幺元。注：注：(1) 若幺元存在必唯一。(2) 若只有或只有，则， 称为左幺元或右幺元。17离散数学第5章在上，矩阵加法的幺元是 阶0矩阵，矩阵乘法的幺元是阶单位矩阵。 在幂集 上，运算的幺元是，运算的幺元是全集 。例如：在上，加法的幺元是0，

6、乘法的幺元是1。在算没有幺元，只有右幺元0上的减法运18离散数学第5章例例4、在(非零实数集)上定义运算如下：则中的任何元素都是右幺元，但没有左幺元，使，从而没有幺元。19离散数学第5章2、零元零元：若，对，则称 为运算 的零元零元。注：注：(1) 若零元存在必唯一。(2) 若只有，或只有，则分别称为左零元或右零元。如例4的任何元素都是左零元，从而也没有零元。 但没有右零元，20离散数学第5章例如：在上加法没有零元，乘法的零元是0。在上矩阵加法没有零元，矩阵乘法的零元是阶0矩阵。在幂集上，运算的零元是 ，运算的零元是。21离散数学第5章3、逆元逆元： 设 为 上的二元运算，为运算的幺元，若对，

7、存在 ，使，则称为 的逆元逆元。注：注：(1) 逆元是针对某个元素 而言的(可能有些元素有逆元，有些没有)(2) 若二元运算 满足结合律且存在则必唯一。的逆元22离散数学第5章3、逆元逆元： 设 为 上的二元运算，为运算的幺元，若对，存在 ，使，则称为 的逆元逆元。注：注：(3) 若只有或只有，则 称为左逆元或右逆元。23离散数学第5章例如：普通加法运算在上有幺元0，仅在上任意元素 有逆元，满足在上只有0有逆元0，而其它的自然数就没有逆元。在上矩阵的乘法只有可逆矩阵存在逆元。幂集上关于运算有幺元，但除了 外，其余元素都没有逆元。24离散数学第5章例例5、判断普通的加法和乘法运算在下列集合中是否

8、二元运算。(1) 解：解：加法，乘法都不是二元运算。(2) 解：解：加法不是二元运算，乘法是二元运算。25离散数学第5章例例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(3) 解：解：加法，乘法都是二元运算。(4) 解：解：加法不是二元运算，乘法是二元运算。26离散数学第5章例例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(5) 解：解：加法不是二元运算， 乘法是二元运算。27离散数学第5章例例6、在实数集上定义运算 如下：(1) 是上的二元运算吗？解：解：因，是二元运算。(2) 在上满足交换律，结合律吗？解：解：因，满足交换律，满足结合律。28离散数学第5章例例6、在实数

9、集上定义运算 如下：(3) 关于 有幺元，零元吗？解：解：因对，故0为幺元，因，故为零元。29离散数学第5章例例6、在实数集上定义运算 如下：(4) 关于 每个元素有逆元吗？解：解：，有 且时，无逆元。故 时，30离散数学第5章例例7、设，二元运算 和 定义，问运算如下表和 是否可交换的；是否有零元；是否有幺元；如果有幺元，指出哪些元素有逆元； 逆元是什么？ 31离散数学第5章(1)没有零元，可交换，解：解：运算是幺元，都有逆元，且，互为逆元。 32离散数学第5章(2)不可交换，解：解：运算是左零元， 是幺元，只有 有逆元， 由于，故是的左逆元，的右逆元，是33离散数学第5章(2)解：解：但它

10、们的逆元都不存在。34离散数学第5章四、其它一些运算律和特殊元素。四、其它一些运算律和特殊元素。(了解了解)1、设 和 都是 上的可交换的二元运算，若，则称 和满足吸收律吸收律。35离散数学第5章四、其它一些运算律和特殊元素。四、其它一些运算律和特殊元素。(了解了解)2、设 是上的二元关系，若(不是零元)满足：(1) 若 ，则 (2) 若，则 就称运算 满足消去律消去律。36离散数学第5章四、其它一些运算律和特殊元素。四、其它一些运算律和特殊元素。(了解了解)3、幂等元。是上的二元运算，对设，若，则称 为幂等元幂等元。若 上所有元素都是幂等元，则称运算 满足幂等律幂等律。37离散数学第5章例如

11、：上的运算 和，全体命题公式集合上的运算和都满足吸收律，又分别满足幂等律，但都不满足消去律 (如，不一定有)。上的加法运算都不满足幂等律，但它们都有幂等元，幺元就是幂等元。38离散数学第5章第二节代数系统及其子代数第二节代数系统及其子代数和积代数和积代数 39离散数学第5章内容：内容：代数系统，子代数，积代数。重点：重点：掌握代数系统，子代数的有关概念。了解：了解：积代数的概念。 40离散数学第5章一、代数系统。一、代数系统。1、定义：定义： 非空集合 和 上的个运算 (其中为元运算，)组成的系统称为一个代数系统代数系统，简称代数代数，记作。例如：，都是代数系统。41离散数学第5章2、代数常数

12、 (特异元素)。在某些代数系统中对于给定的二元运算存在幺元或零元，它们对该系统的性质起着重要作用，称为代数常数代数常数(特异元素特异元素)。例如：的幺元0，也可记为，中和的幺元分别为和，同样可记为。42离散数学第5章二、子代数系统。二、子代数系统。1、定义：定义：设是代数系统，且，若对运算都是封闭的，且和 含有相同的代数常数，则称为的子代数系统子代数系统，简称子代数子代数。43离散数学第5章例如：是的子代数，是的子代数，但是的子代数，却不是的子代数，因代数常数。44离散数学第5章2、平凡子代数，真子代数。设是代数系统的子代数，当和时，称为平凡子代数平凡子代数 (分别是最大和最小的子代数)，当时

13、，称为的真子代数真子代数。45离散数学第5章例例1、设，令为自然数，那么是的子代数。，证明：证明：，则即对+封闭，又，所以是的子代数。46离散数学第5章证明：证明：当时，当时，它们是的平凡子代数，而其它的子代数都是的非平凡的真子代数。例例1、设，令为自然数，那么是的子代数。47离散数学第5章例例1、设，令为自然数，那么是的子代数。当时，当时，它们是的平凡子代数，而其它的子代数都是的非平凡的真子代数。48离散数学第5章三、积代数。三、积代数。设是代数系统，其中 和 是二元运算，令，对则为代数系统，称为的积代数积代数，记。49离散数学第5章例如：和的积代数为其中运算 为二元运算，对，50离散数学第

14、5章例如：和的积代数为，有代数常数0， 有代数常数，有代数常数。51离散数学第5章第三节第三节 代数系统的同态与同构代数系统的同态与同构 52离散数学第5章内容：内容：代数系统的同态映射，同构映射。一般：一般：掌握同态，单同态，满同态，同构的定义及判定。一、同态映射，同构映射的概念。一、同态映射，同构映射的概念。代数系统的同态和同构是研究两个代数系统之间的关系。53离散数学第5章1、定义定义： 设是代数系统，其中 和 都是二元运算，若存在映射 (即函数) ，满足对任意的，有则称 是到的同态映射同态映射，简称同态同态。满同态，记单同态同构，记注：注：若存在从到的满同态，则称为在 下的同态象。54

15、离散数学第5章例例1、(1)，其中为普通加法，为模 加法，即，有，这里令，则对，55离散数学第5章例例1、(1)，其中为普通加法，为模 加法，即，有，这里令，所以是到的同态。显然是满射，所以，即满同态，但不是单同态56离散数学第5章例例1、(2)，则对令，所以是到的同态。由于是双射，所以是同构，思考：思考：，是同构映射吗？57离散数学第5章2、自同态，自同构。自同态从一个代数系统到自己的同态称为自同态。 自同构从一个代数系统到自己的同构称为自同构。 58离散数学第5章则对例例2、，给定，令，所以是到的同态，即自同态。当时，有，称为零同态。59离散数学第5章则对例例2、，给定，令，所以是到的同态

16、，即自同态。当时，有，即恒等映射，它是双射的，这时是的自同构，同理可证也是的自同构。60离散数学第5章则对例例2、，给定，令，所以是到的同态，即自同态。当且时，易证是单射的，这时是的单自同态。61离散数学第5章3、同态，同构概念的推广。(1)，62离散数学第5章例例3、，其中为普通的加法，乘法，为模加法，乘法令，则对，63离散数学第5章例例3、，其中为普通的加法，乘法，为模加法，乘法令，所以是到的同态，且是满同态。64离散数学第5章(2) ，(3) ，65离散数学第5章例例4、(1)，其中为普通加法和乘法，表示求的相反数， 表示的倒数。令，则对，所以是到的同态。66离散数学第5章例例4、(2)

17、，其中0是加法幺元，1是乘法幺元，都是代数常数，同(1)，即则有，所以是到的同态。67离散数学第5章二、性质。设是从到的满同态，则1、若 可结合，则 也是可结合。2、若 可交换，则 也是可交换。3、若 是关于 的幺元，则是关于的幺元。4、若 是关于 的零元，则是关于的零元。68离散数学第5章二、性质。设是从到的满同态，则5、若 是关于 的幂等元，则是关于的幂等元。6、若是中元素关于 的逆元，则是中元素关于 的逆元。注：注：若分别有两个二元运算，且中分配律成立，则中分配律也成立。69离散数学第5章第五章第五章 小结与例题小结与例题 70离散数学第5章一、二元运算及其性质。一、二元运算及其性质。1

18、、基本概念。一元运算和二元运算；二元运算的结合律，交换律，分配律，幂等律，吸收律，消去律；二元运算的特殊元素：幺元，零元，逆元；一元运算和二元运算的运算表。 71离散数学第5章一、二元运算及其性质。一、二元运算及其性质。2、运用。(1) 判断给定的二元运算是否满足结合律，交换律，分配律，幂等律，吸收律，消去律等。(2) 求幺元，零元，逆元。(3) 列出一元运算和二元运算的运算表。 72离散数学第5章二、代数系统及其子代数和积代数。二、代数系统及其子代数和积代数。1、基本概念。代数系统；子代数；积代数。2、运用。判断代数系统的子集能否构成子代数系统。 73离散数学第5章三、代数系统的同态与同构。

19、三、代数系统的同态与同构。1、基本概念。同态，单同态，满同态；同构。2、运用。判断两个代数系统是否同态，单同态，满同态，同构。74离散数学第5章例例1、数的加，减，乘，除是否为下述集合上的二元运算。(1) 实数集解：解：加、减、乘是二元运算，除不是二元运算。 (2) 非零实数集 解：解：加、减不是二元运算， 乘、除是二元运算。75离散数学第5章例例1、数的加，减，乘，除是否为下述集合上的二元运算。(3) 正整数集解：解：加、乘是二元运算， 减、除不是二元运算。(4) 解：解：乘是二元运算， 加、减、除都不是二元运算。76离散数学第5章例例1、数的加，减，乘，除是否为下述集合上的二元运算。(5)

20、 解：解：乘、除是二元运算，加、减不是二元运算。77离散数学第5章例例2、正整数集上的二元运算 表示两个数 的最小公倍数。(1) 求解：解：(2) 问 在上满足交换律，结合律，幂等律吗？解：解：因对任意的正整数有，故满足交换律，结合律，幂等律。78离散数学第5章例例2、正整数集上的二元运算 表示两个数 的最小公倍数。(3) 求幺元，零元。(4) 中任意元都有逆元吗？解：解：因，故1是幺元， 不存在零元。解：解：中只有1有逆元，其它元素都没有逆元。79离散数学第5章例例3、在有理数集上定义二元运算 ，有(1) 求，解：解：80离散数学第5章例例3、在有理数集上定义二元运算 ，有(2)在上满足结合

21、律吗？解：解：对任意的故满足结合律。81离散数学第5章例例3、在有理数集上定义二元运算 ，有(3) 求幺元。解：解：对任意的故0是幺元。82离散数学第5章例例3、在有理数集上定义二元运算 ，有(4) 中哪些元素存在逆元？解：解：对任意的，设是 的逆元，则解得：即时，有逆元83离散数学第5章例例4、如下定义实数集上的二元运算 ，判断是否可交换，可结合？是否有幺元？若有幺元，指出中哪些元素有逆元？(1)解：解：可交换； 但不可结合，如：，而，即；无幺元。84离散数学第5章例例4、如下定义实数集上的二元运算 ，判断是否可交换，可结合？是否有幺元？若有幺元，指出中哪些元素有逆元？(2)解：解：可交换，

22、可结合，无幺元。85离散数学第5章例例4、如下定义实数集上的二元运算 ，判断是否可交换，可结合？是否有幺元？若有幺元，指出中哪些元素有逆元？(3)解：解：不可交换，如，即。86离散数学第5章例例4、如下定义实数集上的二元运算 ，判断是否可交换，可结合？是否有幺元？若有幺元，指出中哪些元素有逆元？(3)解：解：不可结合，如，即，无幺元。87离散数学第5章例例4、如下定义实数集上的二元运算 ，判断是否可交换，可结合？是否有幺元？若有幺元，指出中哪些元素有逆元？(4)解：解：可交换，如，即，无幺元。不可结合，88离散数学第5章例例5、设，其中和，如下：(1)满足交换律吗?解：解：由于运算表关于主对角线对称， 所以是可交换的。89离散数学第5章例例5、设，其中和，如下：(2)有幺元、零元吗？解：解：有幺元， 零元。90离散数学第5章例例5、设，其中和，如下：(3) 设，问，是否为代数系统的子代数？解：解：由于的非空子集，都是其中对运算 是封闭的，故，是的子代数。91离散数学第5章例例5、设，其中和，如下：(3) 设，问，是否为代数系统的子代数？解：解：但不封闭，对运算如，故不是的子代数。92离散数学第5章例例5、设，其中和，如下：定义同态，且，(4)是单同态吗？是满同态吗？93离散数学第5章例例5、设，其中和，如下：定义同态，且，(5)在下的同态象是什么？94离散数学第5章