离散数学代数系统PPT学习教案

1、会计学1离散数学代数系统离散数学代数系统q本章的主要内容本章的主要内容一元和二元运算定义及其实例一元和二元运算定义及其实例二元运算的性质二元运算的性质代数系统定义及其实例代数系统定义及其实例子代数子代数 q与后面各章的关系与后面各章的关系是后面典型代数系统的基础是后面典型代数系统的基础第1页/共71页第2页/共71页验证一个运算是否为集合验证一个运算是否为集合S S上的二元运算主要考虑两点：上的二元运算主要考虑两点：q S S中任何两个元素都可以进行这种运算，且运算的结果中任何两个元素都可以进行这种运算，且运算的结果是唯一的。是唯一的。q S S中任何两个元素的运算结果都属于中任何两个元素的运

2、算结果都属于S S，即，即S S对该运算是对该运算是封闭的。封闭的。第3页/共71页不是。（4）设Sa1,a2,an，aiaj =ai为S上二元运算。第4页/共71页111212122212( ), ,1,2,.,nnnijnnnnaaaaaaMRaR i jnaaa 则矩阵加法和乘法都是则矩阵加法和乘法都是Mn(R)上的二元运算上的二元运算。（6）S为任意集合，则为任意集合，则、 为为P(S)上的二元上的二元运算。运算。（7）SS为为S上的所有函数的集合，则合成运算上的所有函数的集合，则合成运算 为为SS上上的二元运算。的二元运算。第5页/共71页集合Q*、非零实数集合R*上的一元运算。（3

3、）求一个复数的共轭复数是复数集合C上的一元运算。第6页/共71页（4 4）在幂集）在幂集P(S)上，如果规定全集为上，如果规定全集为S，则，则求集合的绝对补求集合的绝对补运算是运算是P(S)上的一元运算。上的一元运算。 （5 5）设）设S为集合，令为集合，令A为为S上所有双射函数的上所有双射函数的集合，集合，A SS，求一个双射函数的反函数求一个双射函数的反函数为为A上的一元运算。上的一元运算。（6 6）在）在n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)上上，求求一个矩阵的转置矩阵一个矩阵的转置矩阵是是Mn(R)上的一元运算。上的一元运算。第7页/共71页那么 3 4 = 3，0.5 (3

4、) = 0.5。第8页/共71页 二元运算的运算表二元运算的运算表an an an a2 an a1 ana2 an a2 a2 a2 a1 a2a1 an a1 a2 a1 a1 a1an a2a1 一元运算的运算表一元运算的运算表 an an a2 a2 a1 a1 ai ai第9页/共71页 的的运算表运算表121,21,211,22221,2111,221 1,221 的运算表的运算表1,212211,2 ai ai解解答答第10页/共71页解解答答 1 12 23 34 41 11 12 23 34 42 22 24 41 13 33 33 31 14 42 24 44 43 32

5、21 1第11页/共71页(x+y)+(u+v) x+y+u+v。第12页/共71页第13页/共71页集合集合运算运算交换律交换律结合律结合律幂等律幂等律Z,Q,R普通加法普通加法+ +普通乘法普通乘法 有有有有有有有有无无无无Mn(R)矩阵加法矩阵加法+ +矩阵乘法矩阵乘法 有有无无有有有有无无无无P(B)并并交交相对补相对补 对称差对称差 有有有有无无有有有有有有无无有有有有有有无无无无AA函数复合函数复合 无无有有无无第14页/共71页2n(y1 y2 yn)x (y1x) (y2x) (ynx) 第15页/共71页第16页/共71页Z, Q, R分别为整数、有理数、实数集；分别为整数、

6、有理数、实数集；Mn(R)为为n阶实矩阵阶实矩阵集合集合，n 2；P(B)为幂集为幂集；AA为从为从A到到A的函数集的函数集，|A| 2 。 集合集合运算运算分配律分配律吸收律吸收律Z,Q,R普通加法普通加法+与乘法与乘法 对对+可分配可分配+对对 不分配不分配无无Mn(R)矩阵加法矩阵加法+与乘法与乘法 对对+可分配可分配+对对 不分配不分配无无P(B)并并与交与交 对对可分配可分配对对可分配可分配有有交交与对称差与对称差 对对 可分配可分配无无第17页/共71页定义定义5.85.8 设设 为为S上的二元运算，上的二元运算，q 如果存在元素如果存在元素el（或或er） S，使得对任意使得对任

7、意xS都有都有el x = x (或或x er = x)则称则称el (或或er)是是S中关于中关于 运算的一个运算的一个左单位左单位元元(或或右单位元右单位元)。q 若若eS关于关于 运算既是左单位元又是右单位运算既是左单位元又是右单位元元，则称则称e为为S上关于上关于 运算的运算的单位元单位元。单位。单位元也叫做元也叫做幺元幺元。 q运算可以没有左单位元和右单位元。运算可以没有左单位元和右单位元。q运算可以只有左单位元。运算可以只有左单位元。q运算可以只有右单位元。运算可以只有右单位元。q运算可以既有左单位元，又有右单位元。运算可以既有左单位元，又有右单位元。 第18页/共71页q运算可以

8、没有左零元和右零元。运算可以没有左零元和右零元。q运算可以只有左零元。运算可以只有左零元。q运算可以只有右零元。运算可以只有右零元。q运算可以既有左零元，又有右零元。运算可以既有左零元，又有右零元。 第19页/共71页q运算可以没有左逆元和右逆元。运算可以没有左逆元和右逆元。q运算可以只有左逆元。运算可以只有左逆元。q运算可以只有右逆元。运算可以只有右逆元。q运算可以既有左逆元，又有右逆元。运算可以既有左逆元，又有右逆元。 第20页/共71页集合集合运算运算单位元单位元零元零元逆元逆元Z,Q,R普通加法普通加法普通乘法普通乘法01无无0 x的逆元的逆元 xx的逆元的逆元x 1Mn(R)矩阵加法

9、矩阵加法矩阵乘法矩阵乘法n阶全阶全0矩阵矩阵n阶单位矩阵阶单位矩阵无无n阶全阶全0矩阵矩阵x逆元逆元 xx的逆元的逆元x 1（x可逆可逆）P(B)并并交交BB的逆元为的逆元为B的逆元为的逆元为B第21页/共71页 el el er (er为右单位元为右单位元) el er er (el为左单位元为左单位元)所以所以el = er，将这个单位元记作将这个单位元记作e。假设假设e 也是也是S中的单位元，则有中的单位元，则有 e = e e = e所以，所以，e 是是S中关于中关于 运算的唯一的单位元运算的唯一的单位元。证证明明第22页/共71页 l l r ( r为左零元为左零元) l r r (

10、 l为右零元为右零元)所以所以 l = r，将这个零元记作将这个零元记作 。假设假设 也是也是S中的零元，则有中的零元，则有 = = 所以，所以， 是是S中关于中关于 运算的唯一的零元。运算的唯一的零元。证证明明第23页/共71页用反证法。用反证法。假设假设 e = ，则则 xS有有x x e x 这与这与S中至少含有两个元素矛盾。中至少含有两个元素矛盾。所以，假设不所以，假设不 成立，即成立，即e 。证证明明第24页/共71页由由 yl x = e 和和 x yr = e ，得得证证明明yl = yl e令令yl = yr = y，则则y是是x的逆元。的逆元。= yl (x yr) = (y

11、l x) yr= e yr= yr假若假若yS也是也是x的逆元，则的逆元，则y = y e = y (x y) = (y x) y = e y= y所以所以y是是x唯一的逆元，记作唯一的逆元，记作x 1。第25页/共71页去律。幂集P(S)上的并和交运算一般不满足消去律。第26页/共71页解解答答（1） 运算可交换、可结合、是幂等的。运算可交换、可结合、是幂等的。 x Z+，x 1=x ， 1 x=x ，1为单位元。为单位元。 不存在零元。不存在零元。 只有只有1有逆元，是它自己，其他正整数无逆元。有逆元，是它自己，其他正整数无逆元。第27页/共71页 y-z = x y-z y=z由于是可交

12、换的，所以右消去律成立。同理可证明左消去律成立，所以消去律成立。第28页/共71页x+y-xy = 0得(1)xyxx=-1所以，所以，1(1)xxxx=-1第29页/共71页abcaabcbbcaccab 运算满足交换律、结合律和消去律，不满足幂等律。单运算满足交换律、结合律和消去律，不满足幂等律。单位元是位元是a，没有零元，且，没有零元，且a-1=a，b-1=c，c-1=b。 运算满足交换律、结合律和幂等律，不满足消去律。单运算满足交换律、结合律和幂等律，不满足消去律。单位元是位元是a，零元是，零元是b，只有只有a有逆元有逆元，a-1=a。 运算满足结合律和幂等律，不满足交换律和消去律。没

13、运算满足结合律和幂等律，不满足交换律和消去律。没有单位元，没有零元，没有可逆元。有单位元，没有零元，没有可逆元。解解答答abcaabcbbbbccbcabcaabcbabccabc复习复习分析分析第30页/共71页第31页/共71页第32页/共71页n有时为了强调某个代数系统是含有代数常数的系统，也可以把这些代数常数列到系统的表达式中。例如：代数系统。第33页/共71页q 列出所有的成分列出所有的成分：集合、运算、代数常数：集合、运算、代数常数(如果存在如果存在)例如例如 ，q 列出集合和运算列出集合和运算，在规定系统性质时不涉及，在规定系统性质时不涉及具有单位元的性质（无代数常数）具有单位元

14、的性质（无代数常数） 例如例如 ，q 用集合名称简单标记代数系统用集合名称简单标记代数系统例如例如 在前面已经对代数系统作了说明的前在前面已经对代数系统作了说明的前提下，上述两个代数系统可以简记为提下，上述两个代数系统可以简记为Z, P(S) 第34页/共71页第35页/共71页V1=V2=+ 和和可交换、可结合可交换、可结合 对对 + 可分配可分配+ 和和不满足幂等律不满足幂等律+ 与与 没有吸收律没有吸收律+ 和和满足消去律满足消去律和和可交换、可结合可交换、可结合和和互相可分配互相可分配和和都有幂等律都有幂等律和和满足吸收律满足吸收律和和一般不满足消去律一般不满足消去律 第36页/共71

15、页q在规定了一个代数系统的构成成分，即集合、运算以在规定了一个代数系统的构成成分，即集合、运算以及代数常数以后，如果在对这些性质所遵从的算律加及代数常数以后，如果在对这些性质所遵从的算律加以限制，那么满足这些条件的代数系统就具有完全相以限制，那么满足这些条件的代数系统就具有完全相同的性质，从而构成了一类特殊的代数系统。同的性质，从而构成了一类特殊的代数系统。例如：代数系统例如：代数系统V，如果，如果*是可结合的，则称是可结合的，则称V为半群。如为半群。如、等都是半群。等都是半群。q从代数系统的构成成分和遵从的算律出发，将代数系从代数系统的构成成分和遵从的算律出发，将代数系统分类，然后研究每一类

16、代数系统的共同性质，并将统分类，然后研究每一类代数系统的共同性质，并将研究的结果运用到具体的代数系统中去。研究的结果运用到具体的代数系统中去。(抽象代数抽象代数的基本方法的基本方法)第37页/共71页nN0是的子代数，但不是的子代数。q子代数和原代数具有相同的成分，运算性质也相同，子代数和原代数具有相同的成分，运算性质也相同，是同类型的代数系统，在许多方面与原代数非常相似是同类型的代数系统，在许多方面与原代数非常相似，不过可能小一些。，不过可能小一些。 q对于任何代数系统，其子代数一定存在。对于任何代数系统，其子代数一定存在。第38页/共71页第39页/共71页例例5.85.8 设设V=，令令

17、 nZ=nz | z Z，n为自然数，为自然数， 则则nZ是是V的子代数。的子代数。 任取任取nZ中的两个元素中的两个元素nz1和和nz2(z1,z2 Z )，则有则有nz1+nz2 n(z1+z2 ) nZ即即nZ对对+运算是封闭的。又运算是封闭的。又0=n0 nZ所以，所以，nZ是是V的子代数。的子代数。 证证明明q当当n=1和和0时，时，nZ是是V的平凡子代数，其他的都是的平凡子代数，其他的都是V的非的非平平 凡的真子代数。凡的真子代数。第40页/共71页bababa),(Q试讨论 的运算性质,有单位元例 在 中, 为有理数Q),(Q零元、逆元吗？Qcba,解: 对任意集. 对Qba ,

18、第41页/共71页abbaba)1abbaab)()()2cbcbacba)(cbcbacba)(cabbacabba)()(cbcba第42页/共71页aeaeaeaa0)1 ( ae0e)3设单位元为e)4设零元为aa0)1 (a1第43页/共71页,)5Qa0axxa0exa逆元1aax1a时11aaa设a的逆元为x第44页/共71页单位元也是零元,问A是什么集合?例 * 为 上的二元运算,它的A解: 设aA, 且a为A上*的单位元和零元,对任意xA, 有xaxxaaaxxa单位元零 元 必为单元素集.Aax 即aA 第45页/共71页A例 设 上 满足结合律,且对试证 对任意的自然数 , 有naan证明: 对 用归纳法n,Aba由, abba得ba 第46页/共71页当 时,aa 11naaaaaa)()(, abba得ba aaakn 时aa 2aak成立时,aaa22n结合第47页/共71页aaaaaakk1所以对任意的 ,有. aann第48页/共71页5.3代数系统的同构与同态两个代数系统(0,1, )和(a,b,*)0 10 11 101*a ba bb bab0 a 1 b第49页/共71页第50页/共71页第51页/共71页g(xg(x1 1) )g(xg(x2 2 ) )g(xg(x1 1) ) * *g