北大离散数学chap5.ppt

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

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

2、3)二元运算的特殊元素(幺元，零元，逆元)。一般：一般：吸收律，消去律，幂等律。一、二元运算。一、二元运算。1、定义：定义：设上的二元运算二元运算(即运算封闭)为集合，函数称为，元运算，掌握，即一元，二元运算。一、二元运算。一、二元运算。2、记号：用等符号表示二元运算，称为算符算符。例如：记为(二元运算)记为(一元运算)但减法，除法不是。但除法不是。例例1、(1)上的加法，乘法都是二元运算，(2)上的加法，乘法，减法都是二元运算，上求相反数的运算是一元运算。(3)非零实数集上的乘法和除法都是二元运算。但加法，减法不是，而求倒数是一元运算。(4)表示所有 阶实矩阵的集合 则矩阵的加法和乘法都是二

3、元运算。，都是二元运算，(5)集合 的幂集 上的 而绝对补集(为全集)是一元运算。(6)所有命题公式的集合上的 都是二元运算，而否定 为一元运算。(7)表示集合上的所有函数的集合，函数的合成运算 是 上的二元运算。3、一元，二元运算表。当为有穷集时，都可以用运算表给出。上的一元和二元运算例例2、(1)设，给出 上的运算绝对和对称差 的运算表。补集解：解：，“”为一元运算，“”为二元运算，其运算表如下：例2、(2)设，定义 二元运算如下：上的两个求运算 和 的运算表。解：解：分别是，的和与积除以5的余数，运算表如下：二、有关运算律。二、有关运算律。设是上的二元运算，1、若，则称 在(或称满足交换

4、律交换律)上可交换可交换。2、若，则称 在(或称满足结合律结合律)上可结合可结合。二、有关运算律。二、有关运算律。设是上的二元运算，3、若则称运算 对 是可分配可分配的。(或称 对 满足分配律分配律)(2)矩阵的加法和乘法在上是可结合的，加法可交换，但乘法不可交换，乘法对加法是可分配的。例例3、(1)普通的加法和乘法在 上都是可结合的，且是可交换的，乘法对加法是可分配的。(3)在幂集上可结合，可交换，但是相对补不可结合，不可交换，和是互相可分配的。(4)在全体命题公式集合上可结合，可交换，和是相互可分配的。三、一些特殊元素。三、一些特殊元素。设 为上的二元运算，1、幺元幺元：若，对 则称，为运

5、算 的幺元幺元。注：注：(1)若幺元存在必唯一。(2)若只有或只有，则，称为左幺元或右幺元。在上，矩阵加法的幺元是 阶0矩阵，矩阵乘法的幺元是阶单位矩阵。在幂集 上，运算的幺元是，运算的幺元是全集。例如：在上，加法的幺元是0，乘法的幺元是1。在算没有幺元，只有右幺元0上的减法运例例4、在(非零实数集)上定义运算如下：则中的任何元素都是右幺元，但没有左幺元，使，从而没有幺元。2、零元零元：若，对，则称 为运算 的零元零元。注：注：(1)若零元存在必唯一。(2)若只有，或只有，则分别称为左零元或右零元。如例4的任何元素都是左零元，从而也没有零元。但没有右零元，例如：在上加法没有零元，乘法的零元是0

6、。在上矩阵加法没有零元，矩阵乘法的零元是阶0矩阵。在幂集上，运算的零元是，运算的零元是。3、逆元逆元：设 为 上的二元运算，为运算的幺元，若对，存在，使，则称为 的逆元逆元。注：注：(1)逆元是针对某个元素 而言的(可能有些元素有逆元，有些没有)(2)若二元运算 满足结合律且存在则必唯一。的逆元3、逆元逆元：设 为 上的二元运算，为运算的幺元，若对，存在，使，则称为 的逆元逆元。注：注：(3)若只有或只有，则 称为左逆元或右逆元。例如：普通加法运算在上有幺元0，仅在上任意元素 有逆元，满足在上只有0有逆元0，而其它的自然数就没有逆元。在上矩阵的乘法只有可逆矩阵存在逆元。幂集上关于运算有幺元，但

7、除了 外，其余元素都没有逆元。例例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(1)解：解：加法，乘法都不是二元运算。(2)解：解：加法不是二元运算，乘法是二元运算。例例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(3)解：解：加法，乘法都是二元运算。(4)解：解：加法不是二元运算，乘法是二元运算。例例5、判断普通的加法和乘法运算在下列集合中是否二元运算。(5)解：解：加法不是二元运算，乘法是二元运算。例例6、在实数集上定义运算 如下：(1)是上的二元运算吗？解：解：因，是二元运算。(2)在上满足交换律，结合律吗？解：解：因，满足交换律，满足结合律。例例6、在实数集上定义运

8、算 如下：(3)关于 有幺元，零元吗？解：解：因对，故0为幺元，因，故为零元。例例6、在实数集上定义运算 如下：(4)关于 每个元素有逆元吗？解：解：，有 且时，无逆元。故 时，例例7、设，二元运算 和 定义，问运算如下表和 是否可交换的；是否有零元；是否有幺元；如果有幺元，指出哪些元素有逆元；逆元是什么？(1)没有零元，可交换，解：解：运算是幺元，都有逆元，且，互为逆元。(2)不可交换，解：解：运算是左零元，是幺元，只有 有逆元，由于，故是的左逆元，的右逆元，是(2)解：解：但它们的逆元都不存在。四、其它一些运算律和特殊元素。四、其它一些运算律和特殊元素。(了解了解)1、设 和 都是 上的可

9、交换的二元运算，若，则称 和满足吸收律吸收律。四、其它一些运算律和特殊元素。四、其它一些运算律和特殊元素。(了解了解)2、设 是上的二元关系，若(不是零元)满足：(1)若，则(2)若，则 就称运算 满足消去律消去律。四、其它一些运算律和特殊元素。四、其它一些运算律和特殊元素。(了解了解)3、幂等元。是上的二元运算，对设，若，则称 为幂等元幂等元。若 上所有元素都是幂等元，则称运算 满足幂等律幂等律。例如：上的运算 和，全体命题公式集合上的运算和都满足吸收律，又分别满足幂等律，但都不满足消去律(如，不一定有)。上的加法运算都不满足幂等律，但它们都有幂等元，幺元就是幂等元。第二节代数系统及其子代数

10、第二节代数系统及其子代数和积代数和积代数 内容：内容：代数系统，子代数，积代数。重点：重点：掌握代数系统，子代数的有关概念。了解：了解：积代数的概念。一、代数系统。一、代数系统。1、定义：定义：非空集合 和 上的个运算(其中为元运算，)组成的系统称为一个代数系统代数系统，简称代数代数，记作。例如：，都是代数系统。2、代数常数(特异元素)。在某些代数系统中对于给定的二元运算存在幺元或零元，它们对该系统的性质起着重要作用，称为代数常数代数常数(特异元素特异元素)。例如：的幺元0，也可记为，中和的幺元分别为和，同样可记为。二、子代数系统。二、子代数系统。1、定义：定义：设是代数系统，且，若对运算都是

11、封闭的，且和 含有相同的代数常数，则称为的子代数系统子代数系统，简称子代数子代数。例如：是的子代数，是的子代数，但是的子代数，却不是的子代数，因代数常数。2、平凡子代数，真子代数。设是代数系统的子代数，当和时，称为平凡子代数平凡子代数(分别是最大和最小的子代数)，当时，称为的真子代数真子代数。例例1、设，令为自然数，那么是的子代数。，证明：证明：，则即对+封闭，又，所以是的子代数。证明：证明：当时，当时，它们是的平凡子代数，而其它的子代数都是的非平凡的真子代数。例例1、设，令为自然数，那么是的子代数。例例1、设，令为自然数，那么是的子代数。当时，当时，它们是的平凡子代数，而其它的子代数都是的非

12、平凡的真子代数。三、积代数。三、积代数。设是代数系统，其中 和 是二元运算，令，对则为代数系统，称为的积代数积代数，记。例如：和的积代数为其中运算 为二元运算，对，例如：和的积代数为，有代数常数0，有代数常数，有代数常数。第三节第三节 代数系统的同态与同构代数系统的同态与同构 内容：内容：代数系统的同态映射，同构映射。一般：一般：掌握同态，单同态，满同态，同构的定义及判定。一、同态映射，同构映射的概念。一、同态映射，同构映射的概念。代数系统的同态和同构是研究两个代数系统之间的关系。1、定义定义：设是代数系统，其中 和 都是二元运算，若存在映射(即函数)，满足对任意的，有则称 是到的同态映射同态

13、映射，简称同态同态。满同态，记单同态同构，记注：注：若存在从到的满同态，则称为在 下的同态象。例例1、(1)，其中为普通加法，为模 加法，即，有，这里令，则对，例例1、(1)，其中为普通加法，为模 加法，即，有，这里令，所以是到的同态。显然是满射，所以，即满同态，但不是单同态例例1、(2)，则对令，所以是到的同态。由于是双射，所以是同构，思考：思考：，是同构映射吗？2、自同态，自同构。自同态从一个代数系统到自己的同态称为自同态。自同构从一个代数系统到自己的同构称为自同构。则对例例2、，给定，令，所以是到的同态，即自同态。当时，有，称为零同态。则对例例2、，给定，令，所以是到的同态，即自同态。当

14、时，有，即恒等映射，它是双射的，这时是的自同构，同理可证也是的自同构。则对例例2、，给定，令，所以是到的同态，即自同态。当且时，易证是单射的，这时是的单自同态。3、同态，同构概念的推广。(1)，例例3、，其中为普通的加法，乘法，为模加法，乘法令，则对，例例3、，其中为普通的加法，乘法，为模加法，乘法令，所以是到的同态，且是满同态。(2)，(3)，例例4、(1)，其中为普通加法和乘法，表示求的相反数，表示的倒数。令，则对，所以是到的同态。例例4、(2)，其中0是加法幺元，1是乘法幺元，都是代数常数，同(1)，即则有，所以是到的同态。二、性质。设是从到的满同态，则1、若 可结合，则 也是可结合。2

15、、若 可交换，则 也是可交换。3、若 是关于 的幺元，则是关于的幺元。4、若 是关于 的零元，则是关于的零元。二、性质。设是从到的满同态，则5、若 是关于 的幂等元，则是关于的幂等元。6、若是中元素关于 的逆元，则是中元素关于 的逆元。注：注：若分别有两个二元运算，且中分配律成立，则中分配律也成立。第五章第五章 小结与例题小结与例题 一、二元运算及其性质。一、二元运算及其性质。1、基本概念。一元运算和二元运算；二元运算的结合律，交换律，分配律，幂等律，吸收律，消去律；二元运算的特殊元素：幺元，零元，逆元；一元运算和二元运算的运算表。一、二元运算及其性质。一、二元运算及其性质。2、运用。(1)判

16、断给定的二元运算是否满足结合律，交换律，分配律，幂等律，吸收律，消去律等。(2)求幺元，零元，逆元。(3)列出一元运算和二元运算的运算表。二、代数系统及其子代数和积代数。二、代数系统及其子代数和积代数。1、基本概念。代数系统；子代数；积代数。2、运用。判断代数系统的子集能否构成子代数系统。三、代数系统的同态与同构。三、代数系统的同态与同构。1、基本概念。同态，单同态，满同态；同构。2、运用。判断两个代数系统是否同态，单同态，满同态，同构。例例1、数的加，减，乘，除是否为下述集合上的二元运算。(1)实数集解：解：加、减、乘是二元运算，除不是二元运算。(2)非零实数集 解：解：加、减不是二元运算，

17、乘、除是二元运算。例例1、数的加，减，乘，除是否为下述集合上的二元运算。(3)正整数集解：解：加、乘是二元运算，减、除不是二元运算。(4)解：解：乘是二元运算，加、减、除都不是二元运算。例例1、数的加，减，乘，除是否为下述集合上的二元运算。(5)解：解：乘、除是二元运算，加、减不是二元运算。例例2、正整数集上的二元运算 表示两个数 的最小公倍数。(1)求解：解：(2)问 在上满足交换律，结合律，幂等律吗？解：解：因对任意的正整数有，故满足交换律，结合律，幂等律。例例2、正整数集上的二元运算 表示两个数 的最小公倍数。(3)求幺元，零元。(4)中任意元都有逆元吗？解：解：因，故1是幺元，不存在零

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

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