离散数学.ppt

离散数学离散数学离散数学离散数学 page:109 五月 2024本章本章知识知识要点要点本章本章重点重点本章本章难点难点第第 7 章章 代数系统代数系统代数系统的概念；代数系统的概念；运算的性质；运算的性质；运算的特殊元素；运算的特殊元素；同态与同构同态与同构运算的性质；运算的性质；运算的特殊元素；运算的特殊元素；代数系统的同态与同构。代数系统的同态与同构。同态与同构同态与同构离散数学离散数学离散数学离散数学 page:209 五月 20247.1 运算运算 整数：存储方式，值的范围，可用运算整数：存储方式，值的范围，可用运算7.1.1 引言引言 C语言中的不同的数据类型？语言中的不同的数据类型？整数的取反运算整数的取反运算-：F-：ZZ，且：，且：F-（x）=-x;整数的加运算整数的加运算+：F+：ZZZ，且：，且：F+(）=x+y;结论：运算是函数的另一种表示形式：结论：运算是函数的另一种表示形式：A到到A的函数是一元运算的函数是一元运算;AA到到A的函数是二元运算；的函数是二元运算；AAA到到A的函数是三元运算。的函数是三元运算。Ak=AAA AA到到A的函数是的函数是k元运算。元运算。离散数学离散数学离散数学离散数学 page:309 五月 20247.1 运算运算7.1.2 运算运算 1)集合集合A上的上的k元运算元运算集合集合Ak到集合到集合A 上的上的函数函数。显然，显然，k=1和和2时就是所谓的一元运算和二元运算。时就是所谓的一元运算和二元运算。2)说明说明 作为函数的另一种形式，运算通常写成新的表示形作为函数的另一种形式，运算通常写成新的表示形式，即表达式形式，如：式，即表达式形式，如：-()=x-y x-y 以后的讨论以二元运算为主，涉及的运算多为广义以后的讨论以二元运算为主，涉及的运算多为广义的运算，比如出现运算符的运算，比如出现运算符*并不代表普通的乘法运算（除非并不代表普通的乘法运算（除非特别申请）。特别申请）。普通的除法，是定义在何集合上的？普通的除法，是定义在何集合上的？离散数学离散数学离散数学离散数学 page:409 五月 20247.1 运算运算7.1.2 运算运算 3)几个术语几个术语 运算表运算表表示函数运算关系的表表示函数运算关系的表0101010101*abcdaaaaabbccccaabcdcbbb0001101101离散数学离散数学离散数学离散数学 page:509 五月 20247.1 运算运算7.1.2 运算运算 3)几个术语几个术语 运算封闭性运算封闭性yxzyxz=x*y作为运算（函数）作为运算（函数）z自然应该在自然应该在A中，但当中，但当x,y取自取自A的子集的子集B时，时，Z是否也在是否也在B中？中？离散数学离散数学离散数学离散数学 page:609 五月 20247.1 运算运算7.1.2 运算运算 3)几个术语几个术语 运算封闭性运算封闭性yxz=x*y 示例示例1：R中的普通加法中的普通加法(+)，对其子集对其子集N 示例示例2：R中的普通减法中的普通减法(-)，对其子集对其子集Z 示例示例3：R中的普通除法中的普通除法(/)，对其子集对其子集Z 示例示例4：R中的普通取反中的普通取反(单目单目-)，对其子集对其子集N离散数学离散数学离散数学离散数学 page:709 五月 20247.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:809 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 交换律交换律设设为为S上的二元运算，若有上的二元运算，若有x,y S，都有，都有xoy=yox，则称运算则称运算是可交换的（运算满足交换律）。是可交换的（运算满足交换律）。如，如，R上普通的加，乘法满足交换律，而减，除法不上普通的加，乘法满足交换律，而减，除法不满足交换律。满足交换律。满足交换律的运算运算表的特点：？满足交换律的运算运算表的特点：？满足交换律的运算（特殊的二元关系）是否就是对称满足交换律的运算（特殊的二元关系）是否就是对称关系？关系？z=xoy=o(),z o 其它可交换与不可交换的例子：其它可交换与不可交换的例子：离散数学离散数学离散数学离散数学 page:909 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 交换律交换律设设为为S上的二元运算，若有上的二元运算，若有x,y S，都有，都有xoy=yox，则称运算则称运算是可交换的（运算满足交换律）。是可交换的（运算满足交换律）。*abcdaaaaabbccccaabcdcbbb*abcdaaaaabacbccababdacbc 满足交换律的运算运算表一定是对称的！满足交换律的运算运算表一定是对称的！离散数学离散数学离散数学离散数学 page:1009 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 结合律结合律 设设为为S上的二元运算，若有上的二元运算，若有x，y，z S，都有，都有 xo(yoz)=(xoy)oz则称运算则称运算o是可结合的是可结合的(满足满足结合律结合律)。如，如，R上普通的加，乘法满足结合律，而减，除法不上普通的加，乘法满足结合律，而减，除法不满足结合律。满足结合律。其它可结合与不可结合的例子其它可结合与不可结合的例子离散数学离散数学离散数学离散数学 page:1109 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 分配律分配律 设设和和*为为S上的二元运算，若有上的二元运算，若有x,y,z S，都有，都有:x*(yz)=(x*y)(x*z)(左分配左分配)(yz)*x=(y*x)(z*x)(右分配右分配)则称运算则称运算*对对是可分配的是可分配的(*对对满足满足分配律分配律)。其它可分配与不可分配的例子其它可分配与不可分配的例子.如，如，R上普通乘对加上普通乘对加,减法满足分配律，但加减法满足分配律，但加,减法对乘减法对乘除法不满足分配律。除法不满足分配律。离散数学离散数学离散数学离散数学 page:1209 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 吸收律吸收律设设和和*为为S上的两个可交换的二元运算，上的两个可交换的二元运算，若若x，y S，都有，都有:x*(xy)=x 且且 x(x*y)=x，则称运算则称运算*和和满足吸收律。满足吸收律。如，如，与与，都满足吸收律，而都满足吸收律，而R上的普通加，上的普通加，减，乘，除都不满足吸收律。减，乘，除都不满足吸收律。离散数学离散数学离散数学离散数学 page:1309 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 例例1 N为自然数集为自然数集,x,y N，x*y=maxx，y,x y=minx，y，试证运算，试证运算*，满足吸收律满足吸收律 证明：证明：x，y N，x*（x y）=maxx，minx，y=x x（x*y）=minx，maxx，y=x 运算运算*和和满足吸收律满足吸收律 吸收律吸收律设设和和*为为S上的两个可交换的二元运算，上的两个可交换的二元运算，若若x，y S，都有，都有:x*(xy)=x 且且 xo(x*y)=x，则称运算则称运算*和和满足吸收律。满足吸收律。离散数学离散数学离散数学离散数学 page:1409 五月 20247.1 运算运算7.1.2 运算的性质运算的性质 等幂的等幂的 设设o为为S上的二元运算，若上的二元运算，若 x S，有，有 xox=x，则称运算则称运算o是等幂的（称为满足等幂律）。是等幂的（称为满足等幂律）。如，如，与与，都是等幂的，而都是等幂的，而R上的普通加，减，上的普通加，减，乘，除都不是等幂的。乘，除都不是等幂的。离散数学离散数学离散数学离散数学 page:1509 五月 2024 结论结论：在代数系统：在代数系统中，若运算中，若运算*,o满足吸收律，满足吸收律，则必满足等幂律。则必满足等幂律。a,b,c S，若有：，若有：a*(aob)=a ao(a*b)=a则必有：则必有：a*a=a aoa=a这是因为：这是因为：a*a =a*(ao(a*b)=a*(ao()=a 同理可得：同理可得：aoa=a 7.1 运算运算7.1.2 运算的性质运算的性质离散数学离散数学离散数学离散数学 page:1609 五月 20247.1 运算运算7.1.3 运算的特殊元素运算的特殊元素 幂等元幂等元 设设o为为S上的二元运算，若上的二元运算，若x S，有，有xox=x，则称，则称x为为运算运算o的幂等元。的幂等元。R上的普通加，乘法不是等幂的，但是，加法运算中，上的普通加，乘法不是等幂的，但是，加法运算中，0是幂等元，乘法运算中，是幂等元，乘法运算中，0和和1是幂等元是幂等元 如，如，与与，都是等幂的运算，所以，集合中的都是等幂的运算，所以，集合中的任意元素都是幂等元。任意元素都是幂等元。离散数学离散数学离散数学离散数学 page:1709 五月 20247.1 运算运算7.1.3 运算的特殊元素运算的特殊元素 么元（单位元）么元（单位元）设设o为为S上的二元运算，若存在元素上的二元运算，若存在元素el(er)，x S，有，有elox=x (xoer=x)，则称则称el(er)为左（右）么元。为左（右）么元。oabcdeloerabcdabcdabcd 如，如，R上的普通减法中的上的普通减法中的0，普通除法中的，普通除法中的1，普通乘，普通乘法中的法中的1 强调忘我强调忘我离散数学离散数学离散数学离散数学 page:1809 五月 20247.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:1909 五月 20247.1 运算运算7.1.3 运算的特殊元素运算的特殊元素 零元零元 设设o为为S上的二元运算，若存在元素，上的二元运算，若存在元素，x S，有，有zlox=zl (xozr=zr)，则称则称 zl(zr)为左（右）零元。为左（右）零元。oabcdzlozrabcdzl zl zl zlzrzrzrzr 如，如，R上的普通除法中的上的普通除法中的0，普通乘法中的，普通乘法中的0，集合交，集合交，并运算中的空集与全集并运算中的空集与全集强调自我强调自我离散数学离散数学离散数学离散数学 page:2009 五月 20247.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:2109 五月 20247.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:2209 五月 20247.1 运算运算7.1.3 运算的特殊元素运算的特殊元素 在讨论了上述概念之后，我们就可以讨论运算的另一在讨论了上述概念之后，我们就可以讨论运算的另一个运算性质：消去律个运算性质：消去律 设设o为为S上的二元运算，若对于任意元素上的二元运算，若对于任意元素x,y,z S，满，满足足 x非零元，且非零元，且xoy=xoz y=z x非零元，且非零元，且yox=zox y=z 则称运算则称运算o满足满足消去律消去律。集合的并运算：零元，可消去？集合的并运算：零元，可消去？集合的笛卡尔积运算：零元，可消去？集合的笛卡尔积运算：零元，可消去？矩阵乘法运算：零元，可消去？矩阵乘法运算：零元，可消去？R上普通的加法运算：零元，可消去？上普通的加法运算：零元，可消去？离散数学离散数学离散数学离散数学 page:2309 五月 2024 课堂练习：课堂练习：P171 9 10 11 12 14 课外课外作业作业：P172 13 15 离散数学离散数学离散数学离散数学 page:2409 五月 20247.2 代数系统代数系统 非空集合非空集合S和定义在和定义在S上的若干个运算上的若干个运算o1,o2,on组组成的整体称为一个成的整体称为一个代数系统代数系统，简称为代数，记为：，简称为代数，记为：V=7.2.1 代数系统代数系统 +为普通的加法为普通的加法 +，*,-为普通的加乘法和取反为普通的加乘法和取反 ，+为矩阵的乘加法为矩阵的乘加法 离散数学离散数学离散数学离散数学 page:2509 五月 20247.2 代数系统代数系统7.2.1 代数系统的代数常数代数系统的代数常数 代数系统中运算的特殊元素，即运算的么元和零元统代数系统中运算的特殊元素，即运算的么元和零元统称为称为代数常数代数常数。例例2设设A=0,1,2,3,4，定义，定义A上的运算上的运算 5，5 分分别别为模为模5的加，乘法，讨论的加，乘法，讨论的运算性质和的运算性质和代数常数。代数常数。501234012340123412340234013401240123运算满足：运算满足：交换律，结合律交换律，结合律有么元：有么元：0逆元：？逆元：？1与与4，2与与3，0与与0离散数学离散数学离散数学离散数学 page:2609 五月 20247.2 代数系统代数系统7.2.1 代数系统的代数常数代数系统的代数常数501234012340000001234024130314204321运算满足：运算满足：交换律，结合律交换律，结合律零元：零元：0逆元：？逆元：？2与与3，4与与4，1与与1有么元：有么元：10没有逆元没有逆元 例例2设设A=0,1,2,3,4，定义，定义A上的运算上的运算 5，5 分分别别为模为模5的加，乘法，讨论的加，乘法，讨论的运算性质和的运算性质和代数常数。代数常数。离散数学离散数学离散数学离散数学 page:2709 五月 20247.2 代数系统代数系统 设设V=为代数系统，为代数系统，H为为S的子集，的子集，若若V1=也构成代数系统，则称也构成代数系统，则称V1是是V的的子子代数系统代数系统。简称子系统。简称子系统。7.2.2 子代数系统子代数系统 以以 V=为例为例 和和为其平凡子代数为其平凡子代数 代数系统均存在子代数，从集合的角度看，最大的是代数系统均存在子代数，从集合的角度看，最大的是它自己，最小的可能是由代数常数构成的集合（平凡子代它自己，最小的可能是由代数常数构成的集合（平凡子代数）。数）。和和是两个非平凡是两个非平凡子代数。子代数。离散数学离散数学离散数学离散数学 page:2809 五月 20247.2 代数系统代数系统7.2.2 子代数系统子代数系统 结论结论1：代数具有父代数系统相同的运算性质。：代数具有父代数系统相同的运算性质。结论结论2：子代数与父代数系统有相同的代数常数。：子代数与父代数系统有相同的代数常数。结论结论3：设：设V=为代数系统，为代数系统，H为为S的的子集，子集，构成子代数当且仅当，运算构成子代数当且仅当，运算o1,o2,.on在在H中是封闭的。中是封闭的。对于对于 V=+为整数上普通的加法为整数上普通的加法 V1=？V2=？则则V1是是V的子代数，而的子代数，而V2不是不是V的子代数。的子代数。N奇奇对运算对运算+不满足封闭性。不满足封闭性。？-为整数上普通的减法为整数上普通的减法离散数学离散数学离散数学离散数学 page:2909 五月 20247.3 同态与同构同态与同构 考察：考察：7.3.1 引例引例 1)它们是两个完全无关的代数系统它们是两个完全无关的代数系统 2)它们具有非常相似的运算性质它们具有非常相似的运算性质 （交换律，结合律，吸收律，分配律，德（交换律，结合律，吸收律，分配律，德摩根律）。摩根律）。难道它们之间一点关系都没有？难道它们之间一点关系都没有？离散数学离散数学离散数学离散数学 page:3009 五月 20247.3 同态与同构同态与同构 1)同类型代数系统同类型代数系统两个代数系统，若拥有相同的运两个代数系统，若拥有相同的运算且对应的运算元数也相同。算且对应的运算元数也相同。7.3.2 同态与同构同态与同构 与与 是相同类型的代数系统。是相同类型的代数系统。与与 不是同类型的代数系统。不是同类型的代数系统。离散数学离散数学离散数学离散数学 page:3109 五月 20247.3 同态与同构同态与同构 2)设设V1=，V2=均为代数均为代数系统，其中的系统，其中的o1，o2 为二元运算，为二元运算，1，2 为一元运算，为一元运算，如果存在映射如果存在映射f：S1S2，使得，使得x,y,z S1有：有：7.3.2 同态与同构同态与同构yxxo1yf(x)f(y)f(x)o2f(y)f(xo1y)=f(x)o2f(y)f(1(x)=2(f(x)则函数则函数f为为V1到到V2的的同态映射同态映射。z 1(z)f(z)2(f(z)离散数学离散数学离散数学离散数学 page:3209 五月 20247.3 同态与同构同态与同构 3)设设V1与与V2是两个同类型的代数系统，如果存在两个是两个同类型的代数系统，如果存在两个集合之间映射，对每对运算都为同态映射，则称这两个代集合之间映射，对每对运算都为同态映射，则称这两个代数系统是数系统是同态的代数系统同态的代数系统，简称同态。，简称同态。7.3.2 同态与同构同态与同构 若映射为单射，则称为若映射为单射，则称为单同态单同态。若映射为满射，则称为若映射为满射，则称为满同态满同态。若映射为双射，则称为若映射为双射，则称为同构同构。离散数学离散数学离散数学离散数学 page:3309 五月 20247.3 同态与同构同态与同构 例例3设设V1=，V2=，这里的，这里的+，*是是R上上的普通加法和乘法，定义的普通加法和乘法，定义f：RR为：为：f(x)=5x，证明，证明V1与与V2为单同态。为单同态。7.3.2 同态与同构同态与同构 显然有：显然有：f(x+y)=5x+y 而：而：f(x)=5x f(y)=5y 所以有：所以有：f(x+y)=f(x)*f(y)=5x*5y=5x+y 所以所以f为同态映射为同态映射 且且xy时，有：时，有：5x 5y 所以所以V1与与V2为单同态映射。为单同态映射。证明：证明：离散数学离散数学离散数学离散数学 page:3409 五月 20247.3 同态与同构同态与同构 例例4设设V1=，V2=，这里的，这里的+，*是是R上的普通加法和乘，证明，上的普通加法和乘，证明，V1与与V2同构。同构。7.3.2 同态与同构同态与同构 证明：可取证明：可取 f(x)=ex 据前例显然有：据前例显然有：f为单同态为单同态 下证下证f为满同态：为满同态：设设y R+，取，取x=y，显然有：，显然有：ex=ey=y 即任意的即任意的y R+，均存在源与其对应。，均存在源与其对应。f为满同态。为满同态。综上所述，综上所述，V1与与V2同构。同构。离散数学离散数学离散数学离散数学 page:3509 五月 20247.3 同态与同构同态与同构 例例5 对于非空集合对于非空集合S，证明代数系统，证明代数系统 与与是满同态。是满同态。7.3.2 同态与同构同态与同构 事实上，正是因为上述两个代数系统是满同态的，所事实上，正是因为上述两个代数系统是满同态的，所以它们才有许多相同的运算性质。以它们才有许多相同的运算性质。证明思想：证明思想：构造构造两个代数系统间的满同态映射？两个代数系统间的满同态映射？由于由于S非空，我们任取元素非空，我们任取元素a S，我们定义，我们定义P(S)到到0,1上的映射如下：上的映射如下：f(A)=集合集合A中包含元素中包含元素a（逻辑值（逻辑值0或或1）即：即：f(A)=1 当当a A0 当当a A离散数学离散数学离散数学离散数学 page:3609 五月 20247.3 同态与同构同态与同构 例例5 对于非空集合对于非空集合S，证明代数系统，证明代数系统 与与是满同态。是满同态。7.3.2 同态与同构同态与同构 容易证明，上述映射是满同态的：容易证明，上述映射是满同态的：对于一元运算对于一元运算，显然有：，显然有：f(A)=f(A)对于二元对于二元，显然有：，显然有：f(AB)=f(A)f(B)对于二元对于二元，显然有：，显然有：f(AB)=f(A)f(B)f对每个运算都为同态映射，且为满同态。对每个运算都为同态映射，且为满同态。离散数学离散数学离散数学离散数学 page:3709 五月 20247.3 同态与同构同态与同构 例例5 对于非空集合对于非空集合S，证明代数系统，证明代数系统 与与是满同态。是满同态。7.3.2 同态与同构同态与同构 我们注意到：我们注意到：么元么元零元零元SS 10 01 且有：且有：f()=0 f(S)=1 么元映射到么元，么元映射到么元，零元映射到零元零元映射到零元离散数学离散数学离散数学离散数学 page:3809 五月 20247.3 同态与同构同态与同构7.3.2 同态的性质同态的性质 o1(或或*1)是可交换的是可交换的 o2(或或*2)是可交换的；是可交换的；设设V1=，V2=均为代数系均为代数系统，且统，且V1与与V2存在满同态映射存在满同态映射f，则：，则：o1(或或*1)是可结合的是可结合的 o2(或或*2)是可结合的是可结合的 o1对对*1是可吸收的是可吸收的 o2 对对*2 是可吸收的；是可吸收的；o1对对*1是可分配的是可分配的 o2 对对*2 是可分配的；是可分配的；e是是o1(或或*1)的么元的么元 f(e)是是o2(或或*2)的么元；的么元；z是是o1(或或*1)的零元的零元 f(z)是是o2(或或*2)的零元；的零元；x-1是是x关于关于o1运算的逆元运算的逆元 f(x-1)是是f(x)关于关于o2运算运算的逆元。的逆元。o1(或或*1)是幂等的是幂等的 o2(或或*2)是幂等的；是幂等的；离散数学离散数学离散数学离散数学 page:3909 五月 20247.3 同态与同构同态与同构7.3.2 同态的性质同态的性质 o1(或或*1)是可交换的是可交换的o2(或或*2)是可交换的；是可交换的；作为示例，我们证明：作为示例，我们证明：证明证明：u,v S2，需要证明，需要证明u,v对对o2是可交换的是可交换的:由于由于S1满足交换律，即有：满足交换律，即有：xo1y=yo1x 当然有：当然有：f(xo1y)=f(yo1x)根据同态映射性质有：根据同态映射性质有：f(x)o2f(y)=f(y)o2f(x)即：即：uo2v=v o2u 由于映射由于映射f是满同态，故是满同态，故u,v S2，存在元素存在元素x,y S1，使得：，使得：f(x)=u,f(y)=v离散数学离散数学离散数学离散数学 page:4009 五月 20247.3 同态与同构同态与同构7.3.2 同态的性质同态的性质 再来证明：再来证明：o1对对*1是可吸收的是可吸收的 o2 对对*2 是可吸收的；是可吸收的；证明证明：u,v S2，需要证明：，需要证明：uo2(u*2v)=u 由于由于o1对对*1是可吸收的，即有：是可吸收的，即有：xo1(x*1y)=x 当然有：当然有：f(xo1(x*1y)=f(x)根据同态映射性质有：根据同态映射性质有：f(x)o2(f(x)*2 f(y)=f(x)即：即：uo2(u*2v)=u 由于映射由于映射f是满同态，故是满同态，故u,v S2，存在元素存在元素x,y S1，使得：，使得：f(x)=u,f(y)=v离散数学离散数学离散数学离散数学 page:4109 五月 20247.3 同态与同构同态与同构7.3.2 同态的性质同态的性质 最后，我们证明：最后，我们证明：z是是o1的零元的零元 f(z)是是o2的零元；的零元；证明证明：u S2，需要证明，需要证明f(z)满足满足:f(z)o2u=u o2 f(z)=f(z)由于由于z是是o1运算的零元，故有：运算的零元，故有：x o1z=zo1x=z 当然有：当然有：f(xo1z)=f(zo1x)=f(z)根据同态映射性质有：根据同态映射性质有：f(x)o2f(z)=f(z)o2f(x)=f(z)即：即：f(z)o2u=u o2f(z)=f(z)由于映射由于映射f是满同态，故是满同态，故u S2，存在元素存在元素x S1，使得：，使得：f(x)=u 所以，所以，f(z)为运算为运算o2的零元。的零元。离散数学离散数学离散数学离散数学 page:4209 五月 20247.3 同态与同构同态与同构 例例6 设设V1=，V2=，其中：，其中：C为为复数集合，复数集合，+，*为复数的加、乘法，为复数的加、乘法，M为二阶实矩阵，为二阶实矩阵，且且满足：主对角线上元素相同，次对角线上元素相反，满足：主对角线上元素相同，次对角线上元素相反，+，o为矩阵的加、乘法为矩阵的加、乘法。试证明这两个代数系统同构。试证明这两个代数系统同构。7.3.2 同态与同构同态与同构 分析：核心问题是构造下列两个元素间的同态双射：分析：核心问题是构造下列两个元素间的同态双射：a+bix -yy x 事实上，可行的方案可能是：事实上，可行的方案可能是：a+bia -bb a a b-b a 或或离散数学离散数学离散数学离散数学 page:4309 五月 20247.3 同态与同构同态与同构7.3.2 同态与同构同态与同构a -bb a c -dd c*因为因为(a+bi)*(c+di)=ac-bd+(bc+ad)i=ac-bd -ad-bcbc+ad ac-bd 故构造构造的映射应该是：故构造构造的映射应该是：f(a+bi)=a -bb a 容易证明这是一个双射，故容易证明这是一个双射，故同构。同构。离散数学离散数学离散数学离散数学 page:4409 五月 2024 课堂练习：课堂练习：P171 7.8.11.（子代数？）（子代数？）16.f(x)=2x 课外课外作业作业：设设V1=，V2=，其中：，其中：*,&分别为分别为普通的乘法和逻辑与运算。普通的乘法和逻辑与运算。试证明：试证明：V1与与V2同态，同态，离散数学离散数学离散数学离散数学 page:4509 五月 2024 关于求最大公因子的方法：关于求最大公因子的方法：1）简单算法：从大到小进行判断）简单算法：从大到小进行判断 2）欧几里德算法：余数）欧几里德算法：余数 关于质数的特殊函数：关于质数的特殊函数：1）为判断范围：）为判断范围：2-？2）不同的判断方法）不同的判断方法 作业问题选讲：作业问题选讲：0，1与与（1/4，1/2）等势）等势 （构造的不是函数：无（构造的不是函数：无0/1的像）的像）离散数学离散数学离散数学离散数学 page:4609 五月 2024 *、