離散數(shù)學(xué)：第九章 代數(shù)系統(tǒng)

第三部分代數(shù)結(jié)構(gòu)主要內(nèi)容代數(shù)系統(tǒng)----二元運(yùn)算及其性質(zhì)、代數(shù)系統(tǒng)和子代數(shù)半群與群----半群、獨(dú)異點(diǎn)、群環(huán)與域-----環(huán)、整環(huán)、域格與布爾代數(shù)----格、布爾代數(shù)1計(jì)算機(jī)科學(xué)與工程學(xué)院第九章代數(shù)系統(tǒng)主要內(nèi)容二元運(yùn)算及其性質(zhì)一元和二元運(yùn)算定義及其實(shí)例二元運(yùn)算的性質(zhì)代數(shù)系統(tǒng)代數(shù)系統(tǒng)定義及其實(shí)例子代數(shù)積代數(shù)代數(shù)系統(tǒng)的同態(tài)與同構(gòu)2計(jì)算機(jī)科學(xué)與工程學(xué)院第九章:代數(shù)系統(tǒng)

第一節(jié)：二元運(yùn)算及其性質(zhì)第二節(jié)：代數(shù)系統(tǒng)第三節(jié)：代數(shù)系統(tǒng)的同態(tài)與同態(tài)

計(jì)算機(jī)科學(xué)與工程學(xué)院39.1二元運(yùn)算及其性質(zhì)本部分用代數(shù)方法來(lái)研究數(shù)學(xué)結(jié)構(gòu),故又叫代數(shù)結(jié)構(gòu),它將用抽象的方法來(lái)研究集合上的關(guān)系和運(yùn)算。代數(shù)的概念和方法已經(jīng)滲透到計(jì)算機(jī)科學(xué)的許多分支中,它對(duì)程序理論,數(shù)據(jù)結(jié)構(gòu),編碼理論的研究和邏輯電路的設(shè)計(jì)已具有理論和實(shí)踐的指導(dǎo)意義。

代數(shù)，也稱代數(shù)結(jié)構(gòu)或代數(shù)系統(tǒng)，是指定義有若干運(yùn)算的集合4計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)代數(shù)常由3部分組成：1.一個(gè)集合，叫做代數(shù)的載體。2.定義在載體上的運(yùn)算。3.載體的特異元素，叫做代數(shù)常數(shù)。因此，代數(shù)通常用載體、運(yùn)算和常數(shù)組成的n元組表示5計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)二元運(yùn)算:設(shè)S是個(gè)集合,S×S到S的一個(gè)函數(shù)(映射)f:S×S→S稱為S上的一個(gè)二元代數(shù)運(yùn)算注：映射有存在性和唯一性的要求,運(yùn)算當(dāng)然要此要求。①存在性，x,y∈S，f(<x,y>)要有結(jié)果，并且此結(jié)果∈S②唯一性，x,y∈S，f(<x,y>)只能有一個(gè)結(jié)果∈S6計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)通常用*，·，+，×來(lái)表示二元運(yùn)算，稱為算符例整數(shù)集合上的加法，乘法任意集合S的冪集上的并、交運(yùn)算命題集合上的合取，析取運(yùn)算例:f是A上的二元運(yùn)算，即f是A×A→A的映射。x,y∈A，f(<x,y>)=z∈A,用算符*表示,即x*y=z。例：f是R上的二元運(yùn)算:x,yR，f(<x,y>)=x,用算符*表示,即x*y=x，計(jì)算：3*4，(-5)*0.2。7計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)一元運(yùn)算：設(shè)A是個(gè)集合,函數(shù)f:A→A稱為A上的一個(gè)一元代數(shù)運(yùn)算例：整數(shù)集合、有理數(shù)集合上的相反數(shù)非零有理數(shù)x的倒數(shù)1/x集合的補(bǔ)運(yùn)算邏輯公式的補(bǔ)運(yùn)算8計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)例：在I+上定義運(yùn)算：*，+。x,y∈I+x*y=x,y的最大公約數(shù)，x+y=x,y的最小公倍數(shù)6*8=2，6+8=24，12*15=3，12+15=60例：在R上求平方根運(yùn)算（一元運(yùn)算）不是一個(gè)代數(shù)運(yùn)算！-9不存在平方根，存在性不滿足9有兩個(gè)平方根，3，-3，唯一性不滿足9計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)可以用運(yùn)算表表示：S={a,b,c}上的～，*運(yùn)算*abcaaabbabccaccai~aiabbacc10計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)例：設(shè)S＝{1,2},給出P(S)上的運(yùn)算~和⊕運(yùn)算表，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計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)可交換的運(yùn)算：*為S上的二元運(yùn)算，對(duì)于任意的x，y∈S都有x*y=y*x*滿足交換律實(shí)數(shù)集合的加法、邏輯公式集合的合取可結(jié)合的運(yùn)算：*為S上的二元運(yùn)算，對(duì)于任意的x，y,z∈S都有(x*y)*z=x*(y*z)*滿足結(jié)合律實(shí)數(shù)集合的加法、邏輯公式集合的合取12計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)*適合冪等律：*為S上的二元運(yùn)算，對(duì)于任意的x∈S都有x*x=x滿足x*x=x的x稱為運(yùn)算*的冪等元例集合的并和交適合冪等律集合的減一般不適合冪等律0是加法的冪等元0和1是乘法的冪等元13計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)運(yùn)算*對(duì)⊙是可分配的：⊙和*為S上的二元運(yùn)算，對(duì)于任意的x，y，z∈S都有

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

(y⊙z)*x=(y*x)⊙(z*x)（右分配律）*對(duì)⊙是滿足分配律例實(shí)數(shù)上的乘法對(duì)加法是可分配的集合上的交對(duì)并是可分配的邏輯公式上的合取對(duì)析取是可分配的14計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)運(yùn)算*和⊙滿足吸收律：⊙和*為S上的二元運(yùn)算，對(duì)于任意的x，y∈S都有

x*(x⊙y)=x

x⊙(x*y)=x例集合上的交和并滿足吸收律邏輯公式上的合取和析取滿足吸收律15計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)左幺元（右幺元）：設(shè)*是A上的二元運(yùn)算，如果存在元素eL（或er）A，使得對(duì)一切xA，均有eL*

x=x（或x*er=x），則稱eL（er）是A中關(guān)于運(yùn)算*的一個(gè)左幺元（右幺元）若元素e既是左幺元，又是右幺元，則稱e是A中關(guān)于*的一個(gè)幺元（e也可記為1，稱單位元）16計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)例：實(shí)數(shù)集上加法運(yùn)算，0是幺元；乘法運(yùn)算則1是幺元冪集P（A）上的運(yùn)算是幺元，而運(yùn)算則A是幺元例：實(shí)數(shù)集R上定義運(yùn)算a,bR，a*b=a，則不存在左幺元，使得bR，eL*b=b，而對(duì)一

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

該代數(shù)系統(tǒng)不存在左幺元。但是R中的每一個(gè)元素b都是右幺元17計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)定理：若el和er分別是S上對(duì)于*的左幺元和右幺元,那么el=er，且這個(gè)元素就是幺元證明：

el=el*er=er推論：一個(gè)二元運(yùn)算的幺元是唯一的證明：設(shè)e=el=er.假設(shè)e’是S中的單位元，則e’=e

*e’=e18計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)左零元（右零元）：*是A上的二元運(yùn)算，如果存在元素0L（或0r）A，使得對(duì)一切xA，均有0L*

x=0L（或x*0r=0r）則稱0L（0r）是A中關(guān)于運(yùn)算*的一個(gè)左零元（右零元）若元素0既是左零元，又是右零元，則稱0是A中關(guān)于運(yùn)算*的一個(gè)零元注：零元不一定是0！19計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)例：實(shí)數(shù)集合R上,對(duì)×運(yùn)算而言,0是零元P(A)上,對(duì)∪運(yùn)算A是零元；對(duì)∩運(yùn)算是零元{命題}上,對(duì)∨運(yùn)算T是零元；對(duì)∧運(yùn)算F是零元20計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)定理：若0l和0r分別是S上對(duì)于*的左零元和右零元,那么0l=0r，且這個(gè)元素就是零元。而且零元是唯一的定理：設(shè)*為S上的二元運(yùn)算，1和0分別為*運(yùn)算的幺元和零元，如果S至少有兩個(gè)元素，則1≠0證明：反證法。假設(shè)1=0，任意xS有

x=x*1=x*0=0與假設(shè)矛盾！21計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)設(shè)*是集合A上的二元運(yùn)算，1A是運(yùn)算*的幺元，對(duì)于xA，如果存在一個(gè)元素yA，使得x*y=1，y*x=1，則稱y是x的逆元，記y=x-1，如果x的逆元存在，則稱x是可逆的如果x*y=1，那么關(guān)于運(yùn)算*，x是y的左逆元，y是x的右逆元例：I上的加法運(yùn)算，則任一元素的逆元就是它的相反數(shù)；而對(duì)N上的加法運(yùn)算，只有0存在逆元是022計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)代數(shù)A＝<{a,b,c},*>由下表定義可以看出，b是幺元。a的逆元是c,b的逆元是自身，c的逆元是a和c*abcaaabbabccbcb23計(jì)算機(jī)科學(xué)與工程學(xué)院9.1二元運(yùn)算及其性質(zhì)定理10.4：設(shè)Z是集合,*是Z上的二元運(yùn)算,并且是可結(jié)合的，運(yùn)算*的幺元是1。若x∈Z有左逆元和右逆元,則它的左逆元等于右逆元,且逆元是唯一的。證明：（1）先證左逆元=右逆元：設(shè)xl和xr分別是x的左逆元和右逆元,

∵x是可逆的和可結(jié)合的（條件給出）∴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二元運(yùn)算及其性質(zhì)（2）證明逆元是唯一的：假設(shè)y和z是x的二個(gè)不同的逆元,則y=y*1=y*（x*z）=（y*x）*z=1*z=z,與假設(shè)相矛盾。

∴x若存在逆元的話一定是唯一的（前提*是可結(jié)合的）9.1二元運(yùn)算及其性質(zhì)*滿足消去律：*是S上的二元運(yùn)算，對(duì)于每一x,y,z∈S有若x*y=x*z,且x≠0,則y=z；若y*x=z*x,且x≠0,則y=z；例：整數(shù)集合上加法，乘法運(yùn)算都滿足消去律冪集合上交和并運(yùn)算不滿足消去律對(duì)稱差運(yùn)算滿足消去律（為什么？）26計(jì)算機(jī)科學(xué)與工程學(xué)院第九章:代數(shù)系統(tǒng)

第一節(jié)：二元運(yùn)算及其性質(zhì)第二節(jié)：代數(shù)系統(tǒng)第三節(jié)：代數(shù)系統(tǒng)的同態(tài)與同態(tài)

計(jì)算機(jī)科學(xué)與工程學(xué)院279.2代數(shù)系統(tǒng)代數(shù)系統(tǒng)：非空集合S和集合上k個(gè)一元或二元運(yùn)算f1,…,fk所組成的系統(tǒng)符號(hào)V=<S,f1,f2,…fk>構(gòu)成一個(gè)代數(shù)系統(tǒng)必須具備的條件：一個(gè)非空集合S,稱為載體在S上的運(yùn)算28計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)常見(jiàn)代數(shù)系統(tǒng)：<N,+><Z,+,·><Mn(R),+,·>，其中Mn(R)為實(shí)矩陣集合<P(S),∪,

∩,～>特異元素（代數(shù)常元）：二元運(yùn)算中的單位元與零元<Z,+>中的+運(yùn)算的單位元0<P(S),∪,

∩,～>中∪和∩運(yùn)算的單位元和S29計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)通常也可把特異元素（常數(shù)）放在代數(shù)系統(tǒng)之中,形成<S,f1,f2,…fk,x>：<N,+,0><P(S),∪,

∩,～,

,S

>代數(shù)系統(tǒng)的基數(shù)|V|=|S|,就是非空集合的基數(shù)30計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)同類型的代數(shù)系統(tǒng)：兩個(gè)代數(shù)系統(tǒng)中有相同個(gè)數(shù)的運(yùn)算和常數(shù)，且對(duì)應(yīng)運(yùn)算的元數(shù)相同例：V1=<R,+,·,-,0,1>V2=<P(S),∪,

∩,～,

,S

>31計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)如果具有相同構(gòu)成成分的代數(shù)系統(tǒng)也有一組相同的稱為公理的規(guī)則，那么他們同是某種特殊的代數(shù)系統(tǒng)例：代數(shù)系統(tǒng)<N,+,0>有如下公理a+b=b+a(a+b)+c=a+(b+c)a+0=a代數(shù)系統(tǒng)<Z,*,1>,<p(S),∪,Ф>和它類似，都是可交換獨(dú)異點(diǎn)這種代數(shù)類型的成員32計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)例：集合代數(shù)<P(A),∪,∩>構(gòu)成代數(shù)系統(tǒng)∩,∪是P(A)上代數(shù)運(yùn)算例：邏輯代數(shù)<A,∧,∨>A為命題公式的全體∧,∨是A上兩個(gè)邏輯運(yùn)算33計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)運(yùn)算封閉：設(shè)*和?是集合S上的二元和一元運(yùn)算，S’是S的子集如果a,b∈S’蘊(yùn)涵著a*b∈S’，那么S’對(duì)*是封閉的如果a∈S’蘊(yùn)涵著?a∈S’，那么S’對(duì)?是封閉的例：減法是Z上的運(yùn)算，Z的子集自然數(shù)N可能x,y∈N，但x-yN減法在N上不是封閉的，即N對(duì)減法不封閉例：N對(duì)Z的加法運(yùn)算+是封閉的34計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)子代數(shù)系統(tǒng)：<S,f1,…,fk>是一個(gè)代數(shù)系統(tǒng)BS,B≠ΦB對(duì)運(yùn)算f1,f2,…,fk是封閉的B和S有相同的代數(shù)常元<B,f1,…,fk>是<S,f1,…,fk>的代數(shù)子系統(tǒng)例：整數(shù)集合Z在加法下構(gòu)成一個(gè)代數(shù)系統(tǒng)<Z,+,0>Z2是偶數(shù)集合,<Z2,+,0>是否其子代數(shù)系統(tǒng)？Z1是奇數(shù)集合,<Z1,+>是否其子代數(shù)系統(tǒng)？35計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)例：<Z,->是代數(shù)系統(tǒng)

<N,->不是子代數(shù)系統(tǒng)N對(duì)減法不封閉的注：任何V=<S,f1,…,fk>的子代數(shù)一定存在最大的子代數(shù)是它自己最小子代數(shù)：所有常元構(gòu)成的子代數(shù)可能不存在！36計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)積代數(shù)V：設(shè)V1=<A,>和V2=<B,＊>是同類型的代數(shù)系統(tǒng)，和＊為二元代數(shù)系統(tǒng)V=<A×B,>為V1,V2的積代數(shù),定義為<a1,b1><a2,b2>=<a1a2,b1＊b2>V1和V2為V的因子代數(shù)37計(jì)算機(jī)科學(xué)與工程學(xué)院9.2代數(shù)系統(tǒng)定理：設(shè)V1=<A,>和V2=<B,＊>是同類型的代數(shù)系統(tǒng)，V=<A×B,>為V1和V2的積代數(shù)如果和＊運(yùn)算是可交換(可結(jié)合、冪等)的，那么運(yùn)算也是可交換(可結(jié)合、冪等)的如果e1和e2(01,02)分別為和＊運(yùn)算的單位元(零元)，那么<e1,e2>(<01,02>)也是運(yùn)算的單位元(零元)如果x和y分別為和＊運(yùn)算的可逆元素，那么<x,y>也是運(yùn)算的可逆元素，逆元為<x-1,y-1>38計(jì)算機(jī)科學(xué)與工程學(xué)院第九章:代數(shù)系統(tǒng)

第一節(jié)：二元運(yùn)算及其性質(zhì)第二節(jié)：代數(shù)系統(tǒng)第三節(jié)：代數(shù)系統(tǒng)的同態(tài)與同態(tài)

39計(jì)算機(jī)科學(xué)與工程學(xué)院9.3同態(tài)和同構(gòu)動(dòng)機(jī)：不同代數(shù)系統(tǒng)可能類型相同更進(jìn)一步，可能有共同的運(yùn)算性質(zhì)有些系統(tǒng)在結(jié)構(gòu)上相似或相同同態(tài)和同構(gòu)討論代數(shù)系統(tǒng)的相似或相同的關(guān)系40計(jì)算機(jī)科學(xué)與工程學(xué)院9.3同態(tài)和同構(gòu)例子：給定V1=<Z3,3>,V2=<A,6>,