离散数学：第九章 代数系统

第三部分代数结构主要内容代数系统----二元运算及其性质、代数系统和子代数半群与群----半群、独异点、群环与域-----环、整环、域格与布尔代数----格、布尔代数1计算机科学与工程学院第九章代数系统主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构2计算机科学与工程学院第九章:代数系统

第一节：二元运算及其性质第二节：代数系统第三节：代数系统的同态与同态

计算机科学与工程学院39.1二元运算及其性质本部分用代数方法来研究数学结构,故又叫代数结构,它将用抽象的方法来研究集合上的关系和运算。代数的概念和方法已经渗透到计算机科学的许多分支中,它对程序理论,数据结构,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。

代数，也称代数结构或代数系统，是指定义有若干运算的集合4计算机科学与工程学院9.1二元运算及其性质代数常由3部分组成：1.一个集合，叫做代数的载体。2.定义在载体上的运算。3.载体的特异元素，叫做代数常数。因此，代数通常用载体、运算和常数组成的n元组表示5计算机科学与工程学院9.1二元运算及其性质二元运算:设S是个集合,S×S到S的一个函数(映射)f:S×S→S称为S上的一个二元代数运算注：映射有存在性和唯一性的要求,运算当然要此要求。①存在性，x,y∈S，f(<x,y>)要有结果，并且此结果∈S②唯一性，x,y∈S，f(<x,y>)只能有一个结果∈S6计算机科学与工程学院9.1二元运算及其性质通常用*，·，+，×来表示二元运算，称为算符例整数集合上的加法，乘法任意集合S的幂集上的并、交运算命题集合上的合取，析取运算例:f是A上的二元运算，即f是A×A→A的映射。x,y∈A，f(<x,y>)=z∈A,用算符*表示,即x*y=z。例：f是R上的二元运算:x,yR，f(<x,y>)=x,用算符*表示,即x*y=x，计算：3*4，(-5)*0.2。7计算机科学与工程学院9.1二元运算及其性质一元运算：设A是个集合,函数f:A→A称为A上的一个一元代数运算例：整数集合、有理数集合上的相反数非零有理数x的倒数1/x集合的补运算逻辑公式的补运算8计算机科学与工程学院9.1二元运算及其性质例：在I+上定义运算：*，+。x,y∈I+x*y=x,y的最大公约数，x+y=x,y的最小公倍数6*8=2，6+8=24，12*15=3，12+15=60例：在R上求平方根运算（一元运算）不是一个代数运算！-9不存在平方根，存在性不满足9有两个平方根，3，-3，唯一性不满足9计算机科学与工程学院9.1二元运算及其性质可以用运算表表示：S={a,b,c}上的～，*运算*abcaaabbabccaccai~aiabbacc10计算机科学与工程学院9.1二元运算及其性质例：设S＝{1,2},给出P(S)上的运算~和⊕运算表，S为全集合⊕Φ{1}{2}{1,2}ΦΦ{1}{2}{1,2}{1}{1}Φ{1,2}{2}{2}{2}{1,2}Φ{1}{1,2}{1,2}{2}{1}Φai~aiΦ{1,2}{1}{2}{2}{1}{1,2}Φ11计算机科学与工程学院9.1二元运算及其性质可交换的运算：*为S上的二元运算，对于任意的x，y∈S都有x*y=y*x*满足交换律实数集合的加法、逻辑公式集合的合取可结合的运算：*为S上的二元运算，对于任意的x，y,z∈S都有(x*y)*z=x*(y*z)*满足结合律实数集合的加法、逻辑公式集合的合取12计算机科学与工程学院9.1二元运算及其性质*适合幂等律：*为S上的二元运算，对于任意的x∈S都有x*x=x满足x*x=x的x称为运算*的幂等元例集合的并和交适合幂等律集合的减一般不适合幂等律0是加法的幂等元0和1是乘法的幂等元13计算机科学与工程学院9.1二元运算及其性质运算*对⊙是可分配的：⊙和*为S上的二元运算，对于任意的x，y，z∈S都有

x*(y⊙z)=(x*y)⊙(x*z)（左分配律）

(y⊙z)*x=(y*x)⊙(z*x)（右分配律）*对⊙是满足分配律例实数上的乘法对加法是可分配的集合上的交对并是可分配的逻辑公式上的合取对析取是可分配的14计算机科学与工程学院9.1二元运算及其性质运算*和⊙满足吸收律：⊙和*为S上的二元运算，对于任意的x，y∈S都有

x*(x⊙y)=x

x⊙(x*y)=x例集合上的交和并满足吸收律逻辑公式上的合取和析取满足吸收律15计算机科学与工程学院9.1二元运算及其性质左幺元（右幺元）：设*是A上的二元运算，如果存在元素eL（或er）A，使得对一切xA，均有eL*

x=x（或x*er=x），则称eL（er）是A中关于运算*的一个左幺元（右幺元）若元素e既是左幺元，又是右幺元，则称e是A中关于*的一个幺元（e也可记为1，称单位元）16计算机科学与工程学院9.1二元运算及其性质例：实数集上加法运算，0是幺元；乘法运算则1是幺元幂集P（A）上的运算是幺元，而运算则A是幺元例：实数集R上定义运算a,bR，a*b=a，则不存在左幺元，使得bR，eL*b=b，而对一

切aR，bR，有a*b=a，

该代数系统不存在左幺元。但是R中的每一个元素b都是右幺元17计算机科学与工程学院9.1二元运算及其性质定理：若el和er分别是S上对于*的左幺元和右幺元,那么el=er，且这个元素就是幺元证明：

el=el*er=er推论：一个二元运算的幺元是唯一的证明：设e=el=er.假设e’是S中的单位元，则e’=e

*e’=e18计算机科学与工程学院9.1二元运算及其性质左零元（右零元）：*是A上的二元运算，如果存在元素0L（或0r）A，使得对一切xA，均有0L*

x=0L（或x*0r=0r）则称0L（0r）是A中关于运算*的一个左零元（右零元）若元素0既是左零元，又是右零元，则称0是A中关于运算*的一个零元注：零元不一定是0！19计算机科学与工程学院9.1二元运算及其性质例：实数集合R上,对×运算而言,0是零元P(A)上,对∪运算A是零元；对∩运算是零元{命题}上,对∨运算T是零元；对∧运算F是零元20计算机科学与工程学院9.1二元运算及其性质定理：若0l和0r分别是S上对于*的左零元和右零元,那么0l=0r，且这个元素就是零元。而且零元是唯一的定理：设*为S上的二元运算，1和0分别为*运算的幺元和零元，如果S至少有两个元素，则1≠0证明：反证法。假设1=0，任意xS有

x=x*1=x*0=0与假设矛盾！21计算机科学与工程学院9.1二元运算及其性质设*是集合A上的二元运算，1A是运算*的幺元，对于xA，如果存在一个元素yA，使得x*y=1，y*x=1，则称y是x的逆元，记y=x-1，如果x的逆元存在，则称x是可逆的如果x*y=1，那么关于运算*，x是y的左逆元，y是x的右逆元例：I上的加法运算，则任一元素的逆元就是它的相反数；而对N上的加法运算，只有0存在逆元是022计算机科学与工程学院9.1二元运算及其性质代数A＝<{a,b,c},*>由下表定义可以看出，b是幺元。a的逆元是c,b的逆元是自身，c的逆元是a和c*abcaaabbabccbcb23计算机科学与工程学院9.1二元运算及其性质定理10.4：设Z是集合,*是Z上的二元运算,并且是可结合的，运算*的幺元是1。若x∈Z有左逆元和右逆元,则它的左逆元等于右逆元,且逆元是唯一的。证明：（1）先证左逆元=右逆元：设xl和xr分别是x的左逆元和右逆元,

∵x是可逆的和可结合的（条件给出）∴xl*x=x*xr=1∵xl*x*xr=(xl*x)*xr=1*xr=xr；

xl*x*xr=xl*(x*xr)=xl*1

=xl；∴xl=xr9.1二元运算及其性质（2）证明逆元是唯一的：假设y和z是x的二个不同的逆元,则y=y*1=y*（x*z）=（y*x）*z=1*z=z,与假设相矛盾。

∴x若存在逆元的话一定是唯一的（前提*是可结合的）9.1二元运算及其性质*满足消去律：*是S上的二元运算，对于每一x,y,z∈S有若x*y=x*z,且x≠0,则y=z；若y*x=z*x,且x≠0,则y=z；例：整数集合上加法，乘法运算都满足消去律幂集合上交和并运算不满足消去律对称差运算满足消去律（为什么？）26计算机科学与工程学院第九章:代数系统

第一节：二元运算及其性质第二节：代数系统第三节：代数系统的同态与同态

计算机科学与工程学院279.2代数系统代数系统：非空集合S和集合上k个一元或二元运算f1,…,fk所组成的系统符号V=<S,f1,f2,…fk>构成一个代数系统必须具备的条件：一个非空集合S,称为载体在S上的运算28计算机科学与工程学院9.2代数系统常见代数系统：<N,+><Z,+,·><Mn(R),+,·>，其中Mn(R)为实矩阵集合<P(S),∪,

∩,∼>特异元素（代数常元）：二元运算中的单位元与零元<Z,+>中的+运算的单位元0<P(S),∪,

∩,∼>中∪和∩运算的单位元和S29计算机科学与工程学院9.2代数系统通常也可把特异元素（常数）放在代数系统之中,形成<S,f1,f2,…fk,x>：<N,+,0><P(S),∪,

∩,∼,

,S

>代数系统的基数|V|=|S|,就是非空集合的基数30计算机科学与工程学院9.2代数系统同类型的代数系统：两个代数系统中有相同个数的运算和常数，且对应运算的元数相同例：V1=<R,+,·,-,0,1>V2=<P(S),∪,

∩,∼,

,S

>31计算机科学与工程学院9.2代数系统如果具有相同构成成分的代数系统也有一组相同的称为公理的规则，那么他们同是某种特殊的代数系统例：代数系统<N,+,0>有如下公理a+b=b+a(a+b)+c=a+(b+c)a+0=a代数系统<Z,*,1>,<p(S),∪,Ф>和它类似，都是可交换独异点这种代数类型的成员32计算机科学与工程学院9.2代数系统例：集合代数<P(A),∪,∩>构成代数系统∩,∪是P(A)上代数运算例：逻辑代数<A,∧,∨>A为命题公式的全体∧,∨是A上两个逻辑运算33计算机科学与工程学院9.2代数系统运算封闭：设*和∆是集合S上的二元和一元运算，S’是S的子集如果a,b∈S’蕴涵着a*b∈S’，那么S’对*是封闭的如果a∈S’蕴涵着∆a∈S’，那么S’对∆是封闭的例：减法是Z上的运算，Z的子集自然数N可能x,y∈N，但x-yN减法在N上不是封闭的，即N对减法不封闭例：N对Z的加法运算+是封闭的34计算机科学与工程学院9.2代数系统子代数系统：<S,f1,…,fk>是一个代数系统BS,B≠ΦB对运算f1,f2,…,fk是封闭的B和S有相同的代数常元<B,f1,…,fk>是<S,f1,…,fk>的代数子系统例：整数集合Z在加法下构成一个代数系统<Z,+,0>Z2是偶数集合,<Z2,+,0>是否其子代数系统？Z1是奇数集合,<Z1,+>是否其子代数系统？35计算机科学与工程学院9.2代数系统例：<Z,->是代数系统

<N,->不是子代数系统N对减法不封闭的注：任何V=<S,f1,…,fk>的子代数一定存在最大的子代数是它自己最小子代数：所有常元构成的子代数可能不存在！36计算机科学与工程学院9.2代数系统积代数V：设V1=<A,>和V2=<B,＊>是同类型的代数系统，和＊为二元代数系统V=<A×B,>为V1,V2的积代数,定义为<a1,b1><a2,b2>=<a1a2,b1＊b2>V1和V2为V的因子代数37计算机科学与工程学院9.2代数系统定理：设V1=<A,>和V2=<B,＊>是同类型的代数系统，V=<A×B,>为V1和V2的积代数如果和＊运算是可交换(可结合、幂等)的，那么运算也是可交换(可结合、幂等)的如果e1和e2(01,02)分别为和＊运算的单位元(零元)，那么<e1,e2>(<01,02>)也是运算的单位元(零元)如果x和y分别为和＊运算的可逆元素，那么<x,y>也是运算的可逆元素，逆元为<x-1,y-1>38计算机科学与工程学院第九章:代数系统

第一节：二元运算及其性质第二节：代数系统第三节：代数系统的同态与同态

39计算机科学与工程学院9.3同态和同构动机：不同代数系统可能类型相同更进一步，可能有共同的运算性质有些系统在结构上相似或相同同态和同构讨论代数系统的相似或相同的关系40计算机科学与工程学院9.3同态和同构例子：给定V1=<Z3,3>,V2=<A,6>,