离散数学#95;6代数系统#x2d;07.pptxVIP

第六章 代数系统（抽象代数）;就是计算机科学中各种理论课。;6-1代数结构（系统）的概念;=J;2.二元运算的运算表 有时用一个表来表示二元 运算的运算规律。;二.代数系统的概念;6-2二元运算的性质;X;四.幺元（单位元、恒等元）;定理6.2.1.设★是X上的二元运算，如果有左幺元eLex, 也有右幺元eRex,贝ij eL= eR =e ,且幺元e是唯一的。 证明：因为eL是左幺元，又eRex,所以eL*eR=eR 因为eR是右幺元，又eL ex,所以eL★ eR= eL 于是 eL= eR =e。 下面证明幺元的唯一性。 假设有两个幺元e2, 因为e［是幺元，Xe2^X,所以ei★ e2=e2 因为是幺元，又ei^X,所以ei*e2=ei 则e1=e2=e o所以幺元是唯一的。 思考题.减法运算是否有幺元？;五.零元 设★是X上的二元运算，如果有eLex，使得对任何 xex,有OL*x=0L,则称缶是相对★的左零元。如果 有0r6X，使得对任何xex,有x夫0R=0R ,则称Or 是相对★的右零元。如果0l=0r=0，对任何NX,有;定理6.2.2.设★是X上的二元运算，如果有左零兀0, ex, 也有右零元0Rex,贝iJ0l=0r=。,且零元0是唯一的。 证明的方法与前定理类似，从略。 六.可结合性;o;定理6.2.3.设★是X上有幺元e且可结合的二元运算，如果 xex, x的左、右逆元都存在，则x的左、右逆元必相等, 且X的逆元是唯一的。;八.可消去性 设★是X上的二元运算，aex,如果对任何X,yex,有 (a*x=a*y)V(x*a=y*a) = x=y. 则称a相对★是可消去的。 例如对乘法而言，a/O,a就是可消去的。即 a^O ax=ay 则可得 x=y. 而集合的u和n都不满足可消去性。因为 _____ AUB=AUC 或 AAB=AAC 不一定有B=C 定理6.2.5.(可消去性的判定定理)设★是X上且可结合的 二元运算，如a￡X,且a」EX.则a是可消去的。 证明.如a仁X,且a-1E X.任取x,y e X,设有a ★ x=a ★ y贝ij a1 ★ (a★ x)= a1 ★ (a★ y) (a-1 ★ a)★ x= (a-1 ★ a)★ y 所以 e*x=e*y x=y a相对★是可消去的。 如果有x*a=y*a类似可得x=y (此定理只是充分条件);■ IB Us;小结：＜X,★＞和＜X,*,o＞是代数系统，是一元运算: 1 .封闭性：Vx,yeX,有 x*y￡X。 2. 可交换性：Vx,y￡X,有 x*y=y* x。 3. 幕等性：VxEX,有 x*x=Xo 4. 仃幺元：e￡X, Vx《X,有 e*x=x*e=x. 5. 有零元：OExRxEX,有O*x=x*O=O.;无幺元：;⑵ ★ a b c;6-3代数系统的同态与同构;f;同态、同构的定义;设I是整数集合，R是I上模k(k是正整数)同余关系，因R 是I上等价???系，所以得商集I/R,将I/R记作*即： Nk={[0],[l],[2],...,[k-l]} 在Nk上定义运算+k和乂女，我们分别称之为以k为模的加 法和乘法。定义为： 任取[x] ,[y| e Nk, [x] +k [y]=[(x+y)(mod k)] [x]Xk[y]=[(xXy)(mod k)] 例如 k=4 N4={[0|,|l|,|2],|3]} [2]+4 [3]=[(2+3)(mod 4)]=[1] |2]X4|3]=[(2X3)(mod 4)]=[2] 下面为了方便，我们将={[0],[1],[2],[3]}简记成： N4={0,l,2,3} ffi^x,yeN4, x+4 y=(x+y)(mod 4);例2. N4={0,l,2,3},N4 上定义运算+4：;下面看看同态代数系统运算表的相似性:;例3 .证明＜N4,+4＞与vX,。＞同构。构造映射f:N4^X如下：;下面.看看同构的两个代数系统运算表的相同性:;注意：代数系统VX,*和〈丫, O 同构的必要条件:;三二代数系统间的同构关系纟是等价关系 1. 纟有自反性：任何代数系统＜X,*＞，有X^Xo 证明：因为有双射Ix：X—X,任取X1 ,x2eX，有 IX(X!★ x2)= Xt★ x2 =1x(x0★ Ix(x2)所以 X竺X。 2. 丝有对称性：任何代数系统vX,*＞ vY,十〉,如果有XMY 则必有Y丝X。 证明：因有X竺Y,.??有双射f:X—Y,任取X1,x2ex,有 f(x1*x2)=f(x1)?f(x2) 因f是双射，..?有f-1:Yrx,任取yi ,y2 e Y 因 f:XtY是满射，3X1 ,x2 e X,使得 y「f(X|), y2=f(x2) ??? x1=f-1(y1)