离散数学课件

《离散数学》page:12020年1月19日星期日本章知识要点本章重点本章难点第7章代数系统代数系统的概念；运算的性质；运算的特殊元素；同态与同构运算的性质；运算的特殊元素；代数系统的同态与同构。同态与同构《离散数学》page:22020年1月19日星期日7.1运算整数：存储方式，值的范围，可用运算……7.1.1引言C语言中的不同的数据类型？整数的取反运算-：F-：Z→Z，且：F-（x）=-x;整数的加运算+：F+：Z✕Z→Z，且：F+(x,y）=x+y;结论：运算是函数的另一种表示形式：A到A的函数是一元运算;A✕A到A的函数是二元运算；A✕A✕A到A的函数是三元运算。…………Ak=A✕A✕A…✕A✕A到A的函数是k元运算。《离散数学》page:32020年1月19日星期日7.1运算7.1.2运算1)集合A上的k元运算—集合Ak到集合A上的函数。显然，k=1和2时就是所谓的一元运算和二元运算。2)说明①作为函数的另一种形式，运算通常写成新的表示形式，即表达式形式，如：-(x,y)=x-yx-y②以后的讨论以二元运算为主，涉及的运算多为广义的运算，比如出现运算符*并不代表普通的乘法运算（除非特别申请）。普通的除法，是定义在何集合上的？《离散数学》page:42020年1月19日星期日7.1运算7.1.2运算3)几个术语①运算表—表示函数运算关系的表∧0101→010101¬*abcdaaaaabbccccaabcdcbbb0001101101《离散数学》page:52020年1月19日星期日7.1运算7.1.2运算3)几个术语②运算封闭性yxzyxz=x*y作为运算（函数）z自然应该在A中，但当x,y取自A的子集B时，Z是否也在B中？《离散数学》page:62020年1月19日星期日7.1运算7.1.2运算3)几个术语②运算封闭性yxz=x*y示例1：R中的普通加法(+)，对其子集N示例2：R中的普通减法(-)，对其子集Z示例3：R中的普通除法(/)，对其子集Z示例4：R中的普通取反(单目-)，对其子集N《离散数学》page:72020年1月19日星期日7.1运算7.1.2运算3)几个术语---对于A上的2元运算*，若对于A的子集B，任意的x,y∊B,有x*y∊B，则称运算*在B中的封闭的。如，R中的普通减法运算，在整数集合Z中是？R的普通减法运算，在N中？R*的普通除法运算，在Z中？R的普通加法运算，在{x|x的某次幂可被16整除}中？R的普通加法运算，在{x|x与5互质}中？R的普通加法运算，在{x|x是30的因子}中？R的普通加法运算，在{x|x是30的倍数}中？②运算封闭性《离散数学》page:82020年1月19日星期日7.1运算7.1.2运算的性质①交换律设о为S上的二元运算，若有∀x,y∈S，都有xoy=yox，则称运算о是可交换的（运算满足交换律）。如，R上普通的加，乘法满足交换律，而减，除法不满足交换律。满足交换律的运算运算表的特点：？满足交换律的运算（特殊的二元关系）是否就是对称关系？z=xoy=o(x,y)x,y,z∈o其它可交换与不可交换的例子：《离散数学》page:92020年1月19日星期日7.1运算7.1.2运算的性质①交换律设о为S上的二元运算，若有∀x,y∈S，都有xoy=yox，则称运算о是可交换的（运算满足交换律）。*abcdaaaaabbccccaabcdcbbb*abcdaaaaabacbccababdacbc满足交换律的运算运算表一定是对称的！《离散数学》page:102020年1月19日星期日7.1运算7.1.2运算的性质②结合律设о为S上的二元运算，若有∀x，y，z∈S，都有xo(yoz)=(xoy)oz则称运算o是可结合的(满足结合律)。如，R上普通的加，乘法满足结合律，而减，除法不满足结合律。其它可结合与不可结合的例子…《离散数学》page:112020年1月19日星期日7.1运算7.1.2运算的性质③分配律设о和*为S上的二元运算，若有∀x,y,z∈S，都有:x*(yоz)=(x*y)о(x*z)(左分配)(yоz)*x=(y*x)о(z*x)(右分配)则称运算*对о是可分配的(*对о满足分配律)。其它可分配与不可分配的例子…..如，R上普通乘对加,减法满足分配律，但加,减法对乘除法不满足分配律。《离散数学》page:122020年1月19日星期日7.1运算7.1.2运算的性质④吸收律设о和*为S上的两个可交换的二元运算，若∀x，y∈S，都有:x*(xоy)=x且xо(x*y)=x，则称运算*和о满足吸收律。如，∧，∨与∪，∩都满足吸收律，而R上的普通加，减，乘，除都不满足吸收律。《离散数学》page:132020年1月19日星期日7.1运算7.1.2运算的性质例1N为自然数集,x,y∈N，x*y=max{x，y},x△y=min{x，y}，试证运算*，△满足吸收律证明：x，y∈N，x*（x△y）=max{x，min{x，y}}=xx△（x*y）=min{x，max{x，y}}=x∴运算*和△满足吸收律④吸收律设о和*为S上的两个可交换的二元运算，若∀x，y∈S，都有:x*(xоy)=x且xo(x*y)=x，则称运算*和о满足吸收律。《离散数学》page:142020年1月19日星期日7.1运算7.1.2运算的性质⑤等幂的设o为S上的二元运算，若∀x∈S，有xox=x，则称运算o是等幂的（称为满足等幂律）。如，∧，∨与∪，∩都是等幂的，而R上的普通加，减，乘，除都不是等幂的。《离散数学》page:152020年1月19日星期日结论：在代数系统S,*,o中，若运算*,o满足吸收律，则必满足等幂律。∀a,b,c∊S，若有：a*(aob)=aao(a*b)=a则必有：a*a=aaoa=a这是因为：a*a=a*(ao(a*b))=a*(ao(…))=a同理可得：aoa=a7.1运算7.1.2运算的性质《离散数学》page:162020年1月19日星期日7.1运算7.1.3运算的特殊元素①幂等元设o为S上的二元运算，若x∈S，有xox=x，则称x为运算o的幂等元。R上的普通加，乘法不是等幂的，但是，加法运算中，0是幂等元，乘法运算中，0和1是幂等元如，∧，∨与∪，∩都是等幂的运算，所以，集合中的任意元素都是幂等元。《离散数学》page:172020年1月19日星期日7.1运算7.1.3运算的特殊元素②么元（单位元）设o为S上的二元运算，若存在元素el(er)，∀x∈S，有elox=x(xoer=x)，则称el(er)为左（右）么元。oabcdeloerabcdabcdabcd如，R上的普通减法中的0，普通除法中的1，普通乘法中的1…强调忘我《离散数学》page:182020年1月19日星期日7.1运算7.1.3运算的特殊元素②么元（单位元）设o为S上的二元运算，若∀x∈S，存在元素el(er)，有elox=x(xoer=x)，则称el(er)为左（右）么元。这是因为根据左右么元的特点必有：eloer=el=er=e若运算o既有左么元el，又有右么元er，则其左右么元必相等且惟一，此时称为运算o的么元e（单位元）。而如果我们假设还存在另外一个么元E，则必有：eoE=e=E么元的例子：逻辑运算，集合，实数….《离散数学》page:192020年1月19日星期日7.1运算7.1.3运算的特殊元素③零元设o为S上的二元运算，若存在元素，∀x∈S，有zlox=zl(xozr=zr)，则称zl(zr)为左（右）零元。oabcdzlozrabcdzlzlzlzlzrzrzrzr如，R上的普通除法中的0，普通乘法中的0，集合交，并运算中的空集与全集强调自我《离散数学》page:202020年1月19日星期日7.1运算7.1.3运算的特殊元素，逆元，消去律③零元设o为S上的二元运算，若存在元素，∀x∈S，有zlox=zl(xozr=zr)，则称zl(zr)为左（右）零元。这是因为根据左右么元的特点必有：zlozr=zl=zr=z若运算o既有左零元zl，又有右零元zr，则其左右零元必相等且惟一，此时称为运算o的零元z。而如果我们假设还存在另外一个零元Z，则必有：zoZ=z=Z零元的例子：逻辑运算，集合，实数….《离散数学》page:212020年1月19日星期日7.1运算7.1.3运算的特殊元素④逆元设o为S上的有么元的二元运算，若对于元素a∈S，存在元素al-1，有al-1oa=e，则称元素al-1是的a左逆元（右逆元ar-1？）结论：若运算o是有么元的可结合的二元运算，且元素a既有左逆元al-1，又有右逆元ar-1，则其左右逆元必相等且惟一，此时称它为元素a的逆元，记为a-1。如，矩阵乘法运算中的逆矩阵，R上普通加法中，元素x的逆？普通乘法中元素x的逆？显然，任意二元运算的么元都是可逆的，且逆元就是它自己，而零元一般是不可逆的。《离散数学》page:222020年1月19日星期日7.1运算7.1.3运算的特殊元素在讨论了上述概念之后，我们就可以讨论运算的另一个运算性质：消去律设o为S上的二元运算，若对于任意元素x,y,z∈S，满足⑴x非零元，且xoy=xoz⇒y=z⑵x非零元，且yox=zox⇒y=z则称运算o满足消去律。集合的并运算：零元，可消去？集合的笛卡尔积运算：零元，可消去？矩阵乘法运算：零元，可消去？R上普通的加法运算：零元，可消去？《离散数学》page:232020年1月19日星期日课堂练习：P171910111214课外作业：P1721315《离散数学》page:242020年1月19日星期日7.2代数系统非空集合S和定义在S上的若干个运算o1,o2,……on组成的整体称为一个代数系统，简称为代数，记为：V=S，o1,o2,….on7.2.1代数系统N,++为普通的加法Z，+,*,-+，*,-为普通的加乘法和取反M(R)，·,+·，+为矩阵的乘加法P(S)，¬,∪,∩《离散数学》page:252020年1月19日星期日7.2代数系统7.2.1代数系统的代数常数代数系统中运算的特殊元素，即运算的么元和零元统称为代数常数。例2设A={0,1,2,3,4}，定义A上的运算㊉5，⊙5分别为模5的加，乘法，讨论A，㊉5，⊙5的运算性质和代数常数。㊉501234012340123412340234013401240123运算满足：交换律，结合律有么元：0逆元：？1与4，2与3，0与0《离散数学》page:262020年1月19日星期日7.2代数系统7.2.1代数系统的代数常数⊙501234012340000001234024130314204321运算满足：交换律，结合律零元：0逆元：？2与3，4与4，1与1有么元：10没有逆元例2设A={0,1,2,3,4}，定义A上的运算㊉5，⊙5分别为模5的加，乘法，讨论A，㊉5，⊙5的运算性质和代数常数。《离散数学》page:272020年1月19日星期日7.2代数系统设V=S，o1,o2,….on为代数系统，H为S的子集，若V1=H，o1,o2,….on也构成代数系统，则称V1是V的子代数系统。简称子系统。7.2.2子代数系统以V=N,+为例N,+和{0},+为其平凡子代数代数系统均存在子代数，从集合的角度看，最大的是它自己，最小的可能是由代数常数构成的集合（平凡子代数）。{0,2,4,6,8…},+和{0,3,6,9,12…},+是两个非平凡子代数。《离散数学》page:282020年1月19日星期日7.2代数系统7.2.2子代数系统结论1：代数具有父代数系统相同的运算性质。结论2：子代数与父代数系统有相同的代数常数。结论3：设V=S，o1,o2,….on为代数系统，H为S的子集，H，o1,o2,….on构成子代数当且仅当，运算o1,o2,….on在H中是封闭的。对于V=Z,++为整数上普通的加法V1=N偶,+？V2=N奇,+？