1、第7章代數(shù)系統(tǒng),代數(shù)系統(tǒng)的概念；運(yùn)算的性質(zhì)；運(yùn)算的特殊元素；同態(tài)與同構(gòu),運(yùn)算的性質(zhì)；運(yùn)算的特殊元素；代數(shù)系統(tǒng)的同態(tài)與同構(gòu)。,同態(tài)與同構(gòu),7.1運(yùn)算,整數(shù)：存儲(chǔ)方式，值的范圍，可用運(yùn)算,7.1.1引言,C語(yǔ)言中的不同的數(shù)據(jù)類(lèi)型？,整數(shù)的取反運(yùn)算-：F-：ZZ，且：F-（x）=-x;,整數(shù)的加運(yùn)算+：F+：ZZZ，且：F+(）=x+y;,結(jié)論：運(yùn)算是函數(shù)的另一種表示形式：A到A的函數(shù)是一元運(yùn)算;AA到A的函數(shù)是二元運(yùn)算；AAA到A的函數(shù)是三元運(yùn)算。Ak=AAAAA到A的函數(shù)是k元運(yùn)算。,7.1運(yùn)算,7.1.2運(yùn)算,1)集合A上的k元運(yùn)算集合Ak到集合A上的函數(shù)。,顯然，k=1和2時(shí)就是所謂的一元運(yùn)

2、算和二元運(yùn)算。,2)說(shuō)明,作為函數(shù)的另一種形式，運(yùn)算通常寫(xiě)成新的表示形式，即表達(dá)式形式，如：-()=x-yx-y,以后的討論以二元運(yùn)算為主，涉及的運(yùn)算多為廣義的運(yùn)算，比如出現(xiàn)運(yùn)算符*并不代表普通的乘法運(yùn)算（除非特別申請(qǐng)）。,普通的除法，是定義在何集合上的？,7.1運(yùn)算,7.1.2運(yùn)算,3)幾個(gè)術(shù)語(yǔ),運(yùn)算表表示函數(shù)運(yùn)算關(guān)系的表,7.1運(yùn)算,7.1.2運(yùn)算,3)幾個(gè)術(shù)語(yǔ),運(yùn)算封閉性,y,x,z,y,x,z=x*y,作為運(yùn)算（函數(shù)）z自然應(yīng)該在A中，但當(dāng)x,y取自A的子集B時(shí)，Z是否也在B中？,7.1運(yùn)算,7.1.2運(yùn)算,3)幾個(gè)術(shù)語(yǔ),運(yùn)算封閉性,y,x,z=x*y,示例1：R中的普通加法(+)，對(duì)

3、其子集N,示例2：R中的普通減法(-)，對(duì)其子集Z,示例3：R中的普通除法(/)，對(duì)其子集Z,示例4：R中的普通取反(單目-)，對(duì)其子集N,7.1運(yùn)算,7.1.2運(yùn)算,3)幾個(gè)術(shù)語(yǔ),-對(duì)于A上的2元運(yùn)算*，若對(duì)于A的子集B，任意的x,yB,有x*yB，則稱(chēng)運(yùn)算*在B中的封閉的。,如，R中的普通減法運(yùn)算，在整數(shù)集合Z中是？,R的普通減法運(yùn)算，在N中？,R*的普通除法運(yùn)算，在Z中？,R的普通加法運(yùn)算，在x|x的某次冪可被16整除中？,R的普通加法運(yùn)算，在x|x與5互質(zhì)中？,R的普通加法運(yùn)算，在x|x是30的因子中？,R的普通加法運(yùn)算，在x|x是30的倍數(shù)中？,運(yùn)算封閉性,7.1運(yùn)算,7.1.2運(yùn)算

4、的性質(zhì),交換律設(shè)為S上的二元運(yùn)算，若有x,yS，都有xoy=yox，則稱(chēng)運(yùn)算是可交換的（運(yùn)算滿足交換律）。,如，R上普通的加，乘法滿足交換律，而減，除法不滿足交換律。,滿足交換律的運(yùn)算運(yùn)算表的特點(diǎn)：？,滿足交換律的運(yùn)算（特殊的二元關(guān)系）是否就是對(duì)稱(chēng)關(guān)系？,z=xoy=o(),zo,其它可交換與不可交換的例子：,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),交換律設(shè)為S上的二元運(yùn)算，若有x,yS，都有xoy=yox，則稱(chēng)運(yùn)算是可交換的（運(yùn)算滿足交換律）。,滿足交換律的運(yùn)算運(yùn)算表一定是對(duì)稱(chēng)的！,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),結(jié)合律設(shè)為S上的二元運(yùn)算，若有x，y，zS，都有xo(yoz)=(xoy)oz則稱(chēng)

5、運(yùn)算o是可結(jié)合的(滿足結(jié)合律)。,如，R上普通的加，乘法滿足結(jié)合律，而減，除法不滿足結(jié)合律。,其它可結(jié)合與不可結(jié)合的例子,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),分配律設(shè)和*為S上的二元運(yùn)算，若有x,y,zS，都有:x*(yz)=(x*y)(x*z)(左分配)(yz)*x=(y*x)(z*x)(右分配)則稱(chēng)運(yùn)算*對(duì)是可分配的(*對(duì)滿足分配律)。,其它可分配與不可分配的例子.,如，R上普通乘對(duì)加,減法滿足分配律，但加,減法對(duì)乘除法不滿足分配律。,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),吸收律設(shè)和*為S上的兩個(gè)可交換的二元運(yùn)算，若x，yS，都有:x*(xy)=x且x(x*y)=x，則稱(chēng)運(yùn)算*和滿足吸收律。,如

6、，與，都滿足吸收律，而R上的普通加，減，乘，除都不滿足吸收律。,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),例1N為自然數(shù)集,x,yN，x*y=maxx，y,xy=minx，y，試證運(yùn)算*，滿足吸收律,證明：x，yN，x*（xy）=maxx，minx，y=xx（x*y）=minx，maxx，y=x運(yùn)算*和滿足吸收律,吸收律設(shè)和*為S上的兩個(gè)可交換的二元運(yùn)算，若x，yS，都有:x*(xy)=x且xo(x*y)=x，則稱(chēng)運(yùn)算*和滿足吸收律。,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),等冪的設(shè)o為S上的二元運(yùn)算，若xS，有xox=x，則稱(chēng)運(yùn)算o是等冪的（稱(chēng)為滿足等冪律）。,如，與，都是等冪的，而R上的普通加，減，乘，

7、除都不是等冪的。,結(jié)論：在代數(shù)系統(tǒng)中，若運(yùn)算*,o滿足吸收律，則必滿足等冪律。,a,b,cS，若有：,a*(aob)=aao(a*b)=a,則必有：a*a=aaoa=a,這是因?yàn)椋篴*a=a*(ao(a*b)=a*(ao()=a,同理可得：aoa=a,7.1運(yùn)算,7.1.2運(yùn)算的性質(zhì),7.1運(yùn)算,7.1.3運(yùn)算的特殊元素,冪等元設(shè)o為S上的二元運(yùn)算，若xS，有xox=x，則稱(chēng)x為運(yùn)算o的冪等元。,R上的普通加，乘法不是等冪的，但是，加法運(yùn)算中，0是冪等元，乘法運(yùn)算中，0和1是冪等元,如，與，都是等冪的運(yùn)算，所以，集合中的任意元素都是冪等元。,7.1運(yùn)算,7.1.3運(yùn)算的特殊元素,么元（單位元）

8、設(shè)o為S上的二元運(yùn)算，若存在元素el(er)，xS，有elox=x(xoer=x)，則稱(chēng)el(er)為左（右）么元。,如，R上的普通減法中的0，普通除法中的1，普通乘法中的1,強(qiáng)調(diào)忘我,7.1運(yùn)算,7.1.3運(yùn)算的特殊元素,么元（單位元）設(shè)o為S上的二元運(yùn)算，若xS，存在元素el(er)，有elox=x(xoer=x)，則稱(chēng)el(er)為左（右）么元。,這是因?yàn)楦鶕?jù)左右么元的特點(diǎn)必有：eloer=el=er=e,若運(yùn)算o既有左么元el，又有右么元er，則其左右么元必相等且惟一，此時(shí)稱(chēng)為運(yùn)算o的么元e（單位元）。,而如果我們假設(shè)還存在另外一個(gè)么元E，則必有：eoE=e=E,么元的例子：邏輯運(yùn)算，

9、集合，實(shí)數(shù).,7.1運(yùn)算,7.1.3運(yùn)算的特殊元素,零元設(shè)o為S上的二元運(yùn)算，若存在元素，xS，有zlox=zl(xozr=zr)，則稱(chēng)zl(zr)為左（右）零元。,如，R上的普通除法中的0，普通乘法中的0，集合交，并運(yùn)算中的空集與全集,強(qiáng)調(diào)自我,7.1運(yùn)算,7.1.3運(yùn)算的特殊元素，逆元，消去律,零元設(shè)o為S上的二元運(yùn)算，若存在元素，xS，有zlox=zl(xozr=zr)，則稱(chēng)zl(zr)為左（右）零元。,這是因?yàn)楦鶕?jù)左右么元的特點(diǎn)必有：zlozr=zl=zr=z,若運(yùn)算o既有左零元zl，又有右零元zr，則其左右零元必相等且惟一，此時(shí)稱(chēng)為運(yùn)算o的零元z。,而如果我們假設(shè)還存在另外一個(gè)零元Z

10、，則必有：zoZ=z=Z,零元的例子：邏輯運(yùn)算，集合，實(shí)數(shù).,7.1運(yùn)算,7.1.3運(yùn)算的特殊元素,逆元設(shè)o為S上的有么元的二元運(yùn)算，若對(duì)于元素aS，存在元素al-1，有al-1oa=e，則稱(chēng)元素al-1是的a左逆元（右逆元ar-1？）,結(jié)論：若運(yùn)算o是有么元的可結(jié)合的二元運(yùn)算，且元素a既有左逆元al-1，又有右逆元ar-1，則其左右逆元必相等且惟一，此時(shí)稱(chēng)它為元素a的逆元，記為a-1。,如，矩陣乘法運(yùn)算中的逆矩陣，R上普通加法中，元素x的逆？普通乘法中元素x的逆？,顯然，任意二元運(yùn)算的么元都是可逆的，且逆元就是它自己，而零元一般是不可逆的。,7.1運(yùn)算,7.1.3運(yùn)算的特殊元素,在討論了上述

11、概念之后，我們就可以討論運(yùn)算的另一個(gè)運(yùn)算性質(zhì)：消去律,設(shè)o為S上的二元運(yùn)算，若對(duì)于任意元素x,y,zS，滿足x非零元，且xoy=xozy=zx非零元，且yox=zoxy=z,則稱(chēng)運(yùn)算o滿足消去律。,集合的并運(yùn)算：零元，可消去？,集合的笛卡爾積運(yùn)算：零元，可消去？,矩陣乘法運(yùn)算：零元，可消去？,R上普通的加法運(yùn)算：零元，可消去？,課堂練習(xí)：P171910111214課外作業(yè)：P1721315,7.2代數(shù)系統(tǒng),非空集合S和定義在S上的若干個(gè)運(yùn)算o1,o2,on組成的整體稱(chēng)為一個(gè)代數(shù)系統(tǒng)，簡(jiǎn)稱(chēng)為代數(shù)，記為：V=,7.2.1代數(shù)系統(tǒng),+為普通的加法+，*,-為普通的加乘法和取反，+為矩陣的乘加法,7.

12、2代數(shù)系統(tǒng),7.2.1代數(shù)系統(tǒng)的代數(shù)常數(shù),代數(shù)系統(tǒng)中運(yùn)算的特殊元素，即運(yùn)算的么元和零元統(tǒng)稱(chēng)為代數(shù)常數(shù)。,例2設(shè)A=0,1,2,3,4，定義A上的運(yùn)算5，5分別為模5的加，乘法，討論的運(yùn)算性質(zhì)和代數(shù)常數(shù)。,運(yùn)算滿足：交換律，結(jié)合律,有么元：0,逆元：？,1與4，2與3，0與0,7.2代數(shù)系統(tǒng),7.2.1代數(shù)系統(tǒng)的代數(shù)常數(shù),運(yùn)算滿足：交換律，結(jié)合律,零元：0,逆元：？,2與3，4與4，1與1,有么元：1,0沒(méi)有逆元,例2設(shè)A=0,1,2,3,4，定義A上的運(yùn)算5，5分別為模5的加，乘法，討論的運(yùn)算性質(zhì)和代數(shù)常數(shù)。,7.2代數(shù)系統(tǒng),設(shè)V=為代數(shù)系統(tǒng)，H為S的子集，若V1=也構(gòu)成代數(shù)系統(tǒng)，則稱(chēng)V1是V

13、的子代數(shù)系統(tǒng)。簡(jiǎn)稱(chēng)子系統(tǒng)。,7.2.2子代數(shù)系統(tǒng),以V=為例和為其平凡子代數(shù),代數(shù)系統(tǒng)均存在子代數(shù)，從集合的角度看，最大的是它自己，最小的可能是由代數(shù)常數(shù)構(gòu)成的集合（平凡子代數(shù)）。,和是兩個(gè)非平凡子代數(shù)。,7.2代數(shù)系統(tǒng),7.2.2子代數(shù)系統(tǒng),結(jié)論1：代數(shù)具有父代數(shù)系統(tǒng)相同的運(yùn)算性質(zhì)。,結(jié)論2：子代數(shù)與父代數(shù)系統(tǒng)有相同的代數(shù)常數(shù)。,結(jié)論3：設(shè)V=為代數(shù)系統(tǒng)，H為S的子集，構(gòu)成子代數(shù)當(dāng)且僅當(dāng)，運(yùn)算o1,o2,.on在H中是封閉的。,對(duì)于V=+為整數(shù)上普通的加法,V1=？,V2=？,則V1是V的子代數(shù)，而V2不是V的子代數(shù)。,N奇對(duì)運(yùn)算+不滿足封閉性。,？-為整數(shù)上普通的減法,7.3同態(tài)與同構(gòu),考

14、察：,7.3.1引例,1)它們是兩個(gè)完全無(wú)關(guān)的代數(shù)系統(tǒng),2)它們具有非常相似的運(yùn)算性質(zhì)（交換律，結(jié)合律，吸收律，分配律，德摩根律）。,難道它們之間一點(diǎn)關(guān)系都沒(méi)有？,7.3同態(tài)與同構(gòu),1)同類(lèi)型代數(shù)系統(tǒng)兩個(gè)代數(shù)系統(tǒng)，若擁有相同的運(yùn)算且對(duì)應(yīng)的運(yùn)算元數(shù)也相同。,7.3.2同態(tài)與同構(gòu),與是相同類(lèi)型的代數(shù)系統(tǒng)。,與不是同類(lèi)型的代數(shù)系統(tǒng)。,7.3同態(tài)與同構(gòu),2)設(shè)V1=，V2=均為代數(shù)系統(tǒng)，其中的o1，o2為二元運(yùn)算，1，2為一元運(yùn)算，如果存在映射f：S1S2，使得x,y,zS1有：,7.3.2同態(tài)與同構(gòu),y,x,xo1y,f(x),f(y),f(x)o2f(y),f(xo1y)=f(x)o2f(y)f(

15、1(x)=2(f(x)則函數(shù)f為V1到V2的同態(tài)映射。,z,1(z),f(z),2(f(z),7.3同態(tài)與同構(gòu),3)設(shè)V1與V2是兩個(gè)同類(lèi)型的代數(shù)系統(tǒng)，如果存在兩個(gè)集合之間映射，對(duì)每對(duì)運(yùn)算都為同態(tài)映射，則稱(chēng)這兩個(gè)代數(shù)系統(tǒng)是同態(tài)的代數(shù)系統(tǒng)，簡(jiǎn)稱(chēng)同態(tài)。,7.3.2同態(tài)與同構(gòu),若映射為單射，則稱(chēng)為單同態(tài)。,若映射為滿射，則稱(chēng)為滿同態(tài)。,若映射為雙射，則稱(chēng)為同構(gòu)。,7.3同態(tài)與同構(gòu),例3設(shè)V1=，V2=，這里的+，*是R上的普通加法和乘法，定義f：RR為：f(x)=5x，證明V1與V2為單同態(tài)。,7.3.2同態(tài)與同構(gòu),顯然有：f(x+y)=5x+y,而：f(x)=5xf(y)=5y,所以有：f(x+y

16、)=f(x)*f(y)=5x*5y=5x+y,所以f為同態(tài)映射,且xy時(shí)，有：5x5y,所以V1與V2為單同態(tài)映射。,證明：,7.3同態(tài)與同構(gòu),例4設(shè)V1=，V2=，這里的+，*是R上的普通加法和乘，證明，V1與V2同構(gòu)。,7.3.2同態(tài)與同構(gòu),證明：可取f(x)=ex,據(jù)前例顯然有：f為單同態(tài),下證f為滿同態(tài)：,設(shè)yR+，取x=y，顯然有：ex=ey=y,即任意的yR+，均存在源與其對(duì)應(yīng)。f為滿同態(tài)。,綜上所述，V1與V2同構(gòu)。,7.3同態(tài)與同構(gòu),例5對(duì)于非空集合S，證明代數(shù)系統(tǒng)與是滿同態(tài)。,7.3.2同態(tài)與同構(gòu),事實(shí)上，正是因?yàn)樯鲜鰞蓚€(gè)代數(shù)系統(tǒng)是滿同態(tài)的，所以它們才有許多相同的運(yùn)算性質(zhì)。,

17、證明思想：構(gòu)造兩個(gè)代數(shù)系統(tǒng)間的滿同態(tài)映射？,由于S非空，我們?nèi)稳≡豠S，我們定義P(S)到0,1上的映射如下：,f(A)=集合A中包含元素a（邏輯值0或1）,即：f(A)=,1當(dāng)aA,0當(dāng)aA,7.3同態(tài)與同構(gòu),例5對(duì)于非空集合S，證明代數(shù)系統(tǒng)與是滿同態(tài)。,7.3.2同態(tài)與同構(gòu),容易證明，上述映射是滿同態(tài)的：,對(duì)于一元運(yùn)算，顯然有：f(A)=f(A),對(duì)于二元，顯然有：f(AB)=f(A)f(B),對(duì)于二元，顯然有：f(AB)=f(A)f(B),f對(duì)每個(gè)運(yùn)算都為同態(tài)映射，且為滿同態(tài)。,7.3同態(tài)與同構(gòu),例5對(duì)于非空集合S，證明代數(shù)系統(tǒng)與是滿同態(tài)。,7.3.2同態(tài)與同構(gòu),我們注意到：,且有：f

18、()=0f(S)=1么元映射到么元，零元映射到零元,7.3同態(tài)與同構(gòu),7.3.2同態(tài)的性質(zhì),o1(或*1)是可交換的o2(或*2)是可交換的；,設(shè)V1=，V2=均為代數(shù)系統(tǒng)，且V1與V2存在滿同態(tài)映射f，則：,o1(或*1)是可結(jié)合的o2(或*2)是可結(jié)合的,o1對(duì)*1是可吸收的o2對(duì)*2是可吸收的；,o1對(duì)*1是可分配的o2對(duì)*2是可分配的；,e是o1(或*1)的么元f(e)是o2(或*2)的么元；,z是o1(或*1)的零元f(z)是o2(或*2)的零元；,x-1是x關(guān)于o1運(yùn)算的逆元f(x-1)是f(x)關(guān)于o2運(yùn)算的逆元。,o1(或*1)是冪等的o2(或*2)是冪等的；,7.3同態(tài)與同構(gòu)

19、,7.3.2同態(tài)的性質(zhì),o1(或*1)是可交換的o2(或*2)是可交換的；,作為示例，我們證明：,證明：u,vS2，需要證明u,v對(duì)o2是可交換的:,由于S1滿足交換律，即有：xo1y=yo1x,當(dāng)然有：f(xo1y)=f(yo1x),根據(jù)同態(tài)映射性質(zhì)有：f(x)o2f(y)=f(y)o2f(x),即：uo2v=vo2u,由于映射f是滿同態(tài)，故u,vS2，存在元素x,yS1，使得：f(x)=u,f(y)=v,7.3同態(tài)與同構(gòu),7.3.2同態(tài)的性質(zhì),再來(lái)證明：,o1對(duì)*1是可吸收的o2對(duì)*2是可吸收的；,證明：u,vS2，需要證明：uo2(u*2v)=u,由于o1對(duì)*1是可吸收的，即有：xo1(x*1y)=x,當(dāng)然有：f(xo1(x*1y)=f(x),根據(jù)同態(tài)映射性質(zhì)有：f(x)o2(f(x)*2f(y)=f(x),即：uo2(u*2v)=u,由于映射f是滿同態(tài)，故u,vS2，存在元素x,yS1，使得：f(x)=u,f(y)=v,7.3同態(tài)與同構(gòu),7.3.2同態(tài)的性質(zhì),最后，我們證明：,z是o1的零元f(z)是o2的零元；,證明：uS2，需要證明f(z)滿足:f(z)o2u=uo2f(z)=f(z),由于z是o1運(yùn)算的