第六章代數(shù)系統(tǒng)

第六章代數(shù)系統(tǒng)第一頁(yè)，共五十八頁(yè)，編輯于2023年，星期四第六章代數(shù)系統(tǒng)6.1代數(shù)系統(tǒng)的一般概念6.2同態(tài)與同構(gòu)6.3同余關(guān)系6.4商代數(shù)和積代數(shù)6.5典型代數(shù)系統(tǒng)第二頁(yè)，共五十八頁(yè)，編輯于2023年，星期四6.1代數(shù)系統(tǒng)的一般概念定義：設(shè)S為非空集合，Ω為S上代數(shù)運(yùn)算的非空集合，稱為一個(gè)代數(shù)系統(tǒng)或代數(shù)結(jié)構(gòu)。集合S稱為V的定義域。如果為有限集合，則將記作。如果S為有限集合，則稱V為有限代數(shù)系統(tǒng)，并稱|S|為的階。

例1

通常數(shù)的加法運(yùn)算、乘法運(yùn)算和減法運(yùn)算都可看作是實(shí)數(shù)集R上的二元運(yùn)算，它們構(gòu)成代數(shù)系統(tǒng)。

例2

設(shè)是集合A上的關(guān)系}，是求復(fù)合關(guān)系的運(yùn)算。它們構(gòu)成代數(shù)系統(tǒng)。第三頁(yè)，共五十八頁(yè)，編輯于2023年，星期四代數(shù)系統(tǒng)的一般概念例：設(shè)集合，是一個(gè)一元運(yùn)算，并規(guī)定成

這個(gè)代數(shù)系統(tǒng)稱為時(shí)鐘代數(shù)。它通過重復(fù)地進(jìn)行運(yùn)算，從元素開始，可逐步地產(chǎn)生出M的每一個(gè)元素。因此，可以把1叫做代數(shù)系統(tǒng)的生成元。第四頁(yè)，共五十八頁(yè)，編輯于2023年，星期四代數(shù)系統(tǒng)的一般概念定義：設(shè)為代數(shù)系統(tǒng)。如果非空集合對(duì)于每一個(gè)皆封閉，則也是代數(shù)系統(tǒng)，并稱其為的子代數(shù)系統(tǒng)。例：考慮代數(shù)系統(tǒng)，其中+和是普通意義下的加法和乘法，則是的子代數(shù)系統(tǒng)。第五頁(yè)，共五十八頁(yè)，編輯于2023年，星期四第六章代數(shù)系統(tǒng)6.1代數(shù)系統(tǒng)的一般概念6.2同態(tài)與同構(gòu)6.3同余關(guān)系6.4商代數(shù)和積代數(shù)6.5典型代數(shù)系統(tǒng)第六頁(yè)，共五十八頁(yè)，編輯于2023年，星期四6.2同態(tài)與同構(gòu)定義：設(shè)和是兩個(gè)代數(shù)系統(tǒng)。如果存在雙射，使每個(gè)和對(duì)應(yīng)的有相同的階，則稱代數(shù)系統(tǒng)和是同型的，稱f為從到的同類映射，并記為。例：試說明代數(shù)系統(tǒng)和代數(shù)系統(tǒng)是同型的，其中和定義為：對(duì)任意,解：令并且規(guī)定顯然是個(gè)雙射函數(shù)，并且和和具有相同的階，即都是二元運(yùn)算。所以題目中的兩個(gè)代數(shù)系統(tǒng)是同型的。

第七頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同型關(guān)系注意：代數(shù)系統(tǒng)之間的同型關(guān)系具有自反性，對(duì)稱性和可傳遞性。同型關(guān)系是等價(jià)關(guān)系。第八頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)定義：設(shè)和是兩個(gè)同型的代數(shù)系統(tǒng),f為Ω1到Ω2的同型映射。如果存在函數(shù)g:S1→S2，使得對(duì)任意的及任意的均有則稱和是同態(tài)的，而g則稱為從V1到V2的關(guān)于f的同態(tài)映射，并且：(1)如果g為滿射，則稱g為關(guān)于f的滿同態(tài)映射，簡(jiǎn)稱關(guān)于f的滿同態(tài)。(2)如果g為單射，則稱g為關(guān)于f的單一同態(tài)映射，簡(jiǎn)稱關(guān)于f的單一同態(tài)。

第九頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)(3)如果V1=V2，并且f為恒等映射，則稱g為關(guān)于f的自同態(tài)映射，簡(jiǎn)稱自同態(tài)。(4)如果g為雙射，則稱g為關(guān)于f的同構(gòu)映射，簡(jiǎn)稱關(guān)于f的同構(gòu)，并稱代數(shù)系統(tǒng)V1和V2是同構(gòu)的。(5)如果V1=V2，并且f為恒等映射，則稱g為關(guān)于f的自同構(gòu)映射，簡(jiǎn)稱自同構(gòu)。

第十頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)第十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)例：給定代數(shù)系統(tǒng)和，定義函數(shù)如下：

試證f是V1到V2的滿同態(tài)映射。證：定義函數(shù)如下：顯然g為雙射，故V1和V2是同型的。又對(duì)于任意的,有使第十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)故而所有即f是同態(tài)映射。第十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)又因?yàn)閷?duì)任意的，存在,使所以f是滿同態(tài)映射，即代數(shù)系統(tǒng)V1和V2是滿同態(tài)的。

第十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)定理：若g為從到的關(guān)于f的同態(tài)，h為從到的關(guān)于的同態(tài)，則h?g為從到的關(guān)于的同態(tài)。證：由于g為V1到V2關(guān)于f的同態(tài)，所以V1和V2是同型的；h為V2到V3關(guān)于的同態(tài)，所以V2和V3是同型的。由同型關(guān)系的可傳遞性，可得V1和V3是同型的。任取及得證。第十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)推論：若g為從到的關(guān)于f的同構(gòu)，h為從到的關(guān)于的同構(gòu)，則h?g為從到的關(guān)于的同構(gòu)。第十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)定理：設(shè)g為到的同態(tài),則為的子代數(shù)，并稱V3為V1的同態(tài)象點(diǎn)。

證：顯然，是G2的非空子集。任取及,則,有，使得且表明關(guān)于每個(gè)都是封閉的,故為的子代數(shù)。第十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)定理：設(shè)g為到的關(guān)于f的滿同態(tài)，f為從到的雙射函數(shù)。(1)若二元運(yùn)算是可交換的（或可結(jié)合的），則也是可交換的（或可結(jié)合的）；(2)若二元運(yùn)算關(guān)于二元運(yùn)算是可分配的，則二元運(yùn)算關(guān)于二元運(yùn)算也是可分配的；(3)若關(guān)于二元運(yùn)算有左單位元el（或右單位元er，或單位元e），則（或，或g(e)）為關(guān)于二元運(yùn)算的左單位元（或右單位元，或單位元）；第十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)(4)若關(guān)于二元運(yùn)算有左逆元0l（或右零元0r，或零元0），則g(0l)（或g(0r)，或g(0)）為關(guān)于二元運(yùn)算的左零元（或右零元，或零元）；(5)若關(guān)于二元運(yùn)算有左逆元xl（或右逆元xr，或逆元x-1），則g(xl)(或g(xr)，或g(x-1))為關(guān)于二元運(yùn)算的左逆元（或右逆元，或逆元）。第十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)證：(b)對(duì)任意的，由于，故存在，使g(x)=a，g(y)=b以及g(z)=c，而同理可得第二十頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同態(tài)和同構(gòu)證：(3)對(duì)任意的，存在，使，而故為關(guān)于的單位元。同樣可證和分別為關(guān)于的左單位元和右單位元。從定理可知，滿同態(tài)映射能夠從一個(gè)代數(shù)系統(tǒng)到另一個(gè)代數(shù)系統(tǒng)單向保留所有的性質(zhì)（如交換律、結(jié)合律、含零元、含單位元、元素的可逆性等），故滿同態(tài)映射是確保結(jié)構(gòu)的映射。第二十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期四第六章代數(shù)系統(tǒng)6.1代數(shù)系統(tǒng)的一般概念6.2同態(tài)與同構(gòu)6.3同余關(guān)系6.4商代數(shù)和積代數(shù)6.5典型代數(shù)系統(tǒng)第二十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期四6.3同余關(guān)系定義：設(shè)為代數(shù)系統(tǒng)，R為G上的等價(jià)關(guān)系。(1)若，對(duì)任意的只要a1Rb1,a2Rb2,就有，則稱R關(guān)于具有代換性質(zhì)。(2)若R關(guān)于每個(gè)都有代換性質(zhì)，則稱R為上的同余關(guān)系。第二十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同余關(guān)系例：考察代數(shù)系統(tǒng)，其中I是整數(shù)集合，*是個(gè)一元運(yùn)算，并定義成設(shè)R是I中的這樣一個(gè)關(guān)系:當(dāng)且僅當(dāng)時(shí)，有。試證明R是代數(shù)系統(tǒng)中的同余關(guān)系。解：不難看出，這里R是一種等價(jià)關(guān)系。設(shè)

且滿足,因此可有，并可寫出和，這里。于是可寫出第二十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同余關(guān)系所得結(jié)果說明，。所以，R是代數(shù)系統(tǒng)中的同余關(guān)系。

第二十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同余關(guān)系例：設(shè)，驗(yàn)證是上的同余關(guān)系。解：顯然關(guān)系是個(gè)等價(jià)關(guān)系，故只要驗(yàn)證關(guān)于+和具有代換性質(zhì)即可。對(duì)任意的,若且，即存在使而所以，關(guān)于+滿足代換性質(zhì)。

第二十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同余關(guān)系同理，所以，關(guān)于也滿足代換性質(zhì)。

第二十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同余關(guān)系定理：設(shè)f是到的同態(tài)，定義G1上的關(guān)系Rf如下：對(duì)任意的，當(dāng)且僅當(dāng)f(x1)=f(x2)，則Rf是上的同余關(guān)系。定理：設(shè)f是到的同態(tài)，定義G1上的關(guān)系Rf如下：對(duì)任意的，當(dāng)且僅當(dāng)f(x1)=f(x2)，則Rf是上的同余關(guān)系。證：顯然，Rf是G1上的等價(jià)關(guān)系。下面證明Rf關(guān)于每個(gè)滿足代換性質(zhì)。任取，若和，則有(轉(zhuǎn)下頁(yè))第二十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期四同余關(guān)系因?yàn)楣室虼?，Rf是上的同余關(guān)系。這個(gè)定理說明，如果存在到的同態(tài)，則可以定義相應(yīng)于這一同態(tài)的同余關(guān)系。第二十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期四第六章代數(shù)系統(tǒng)6.1代數(shù)系統(tǒng)的一般概念6.2同態(tài)與同構(gòu)6.3同余關(guān)系6.4商代數(shù)和積代數(shù)6.5典型代數(shù)系統(tǒng)第三十頁(yè)，共五十八頁(yè)，編輯于2023年，星期四6.4商代數(shù)和積代數(shù)定義：設(shè)R為代數(shù)系統(tǒng)上的同余關(guān)系，代數(shù)系統(tǒng)稱為關(guān)于R的商代數(shù)，其中，對(duì)于每個(gè)，與同型的運(yùn)算定義為：對(duì)任意的,有第三十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)為了保證確實(shí)是一個(gè)代數(shù)系統(tǒng)，必須驗(yàn)證每個(gè)是良定的，即與等價(jià)類中代表元素的選取無關(guān)。任取,則有，而R是上的同余關(guān)系，所以定義：設(shè)R是集合G上的等價(jià)關(guān)系，定義函數(shù)g:G→G/R為，稱g為G到G/R的正規(guī)映射。第三十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)定理：設(shè)R為代數(shù)系統(tǒng)上的同余關(guān)系，則正則映射是到商代數(shù)的滿同態(tài)，并稱g為自然同態(tài)。證：顯然，和是同型的。任取及,因?yàn)樗?，g是到的同態(tài)。又因?yàn)閷?duì)任意，總有，使g(x)=[x]R=[y]R，所以g是滿射。第三十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)本定理說明，對(duì)于代數(shù)系統(tǒng)上任何同余關(guān)系R，可以定義從到的自然同態(tài)；而對(duì)于代數(shù)系統(tǒng)到的任何同態(tài)f，也可以定義上相應(yīng)的同余關(guān)系。由此可見，同態(tài)與同余之間有著密切的聯(lián)系。第三十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)定理：設(shè)f為到的關(guān)于的同態(tài)，Rf是<>上對(duì)應(yīng)于f的同余關(guān)系，g是到的自然同態(tài)，則存在從到的同構(gòu)映射，且滿足。證：定義函數(shù)如下：對(duì)任意，需要證明是良定的。任取，若，則，因而，這表明是良定的。對(duì)任意的，存在使，則。這表明是滿射。

第三十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)任取，若，即f(x1)=f(x2)，則，故，表明是單射。定義函數(shù)如下：對(duì)任意，令，顯然h是雙射，任取,第三十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)綜上所述，是到的同構(gòu)映射，并且對(duì)任意，有第三十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)推論：如果f為到的滿同態(tài)，Rf為對(duì)應(yīng)于f的同余關(guān)系，則為到的同構(gòu)映射。

由已知的代數(shù)系統(tǒng)構(gòu)造新代數(shù)系統(tǒng)的另一種方法是將同型的代數(shù)系統(tǒng)通過“直接積”來構(gòu)造積代數(shù)。第三十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)定義：設(shè)為同型的代數(shù)系統(tǒng)A1,A2,…,Am的積代數(shù)定義為。其中對(duì)每個(gè)及對(duì)應(yīng)的，定義如下：，對(duì)任意，令稱為積代數(shù)的因子代數(shù)。

第三十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)例：和為兩個(gè)代數(shù)系統(tǒng),其中，G2={b1,b2,b3}，二元運(yùn)算*和的運(yùn)算如下表所示。

求積代數(shù)第四十頁(yè)，共五十八頁(yè)，編輯于2023年，星期四商代數(shù)和積代數(shù)解：對(duì)任意的，第四十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期四第六章代數(shù)系統(tǒng)6.1代數(shù)系統(tǒng)的一般概念6.2同態(tài)與同構(gòu)6.3同余關(guān)系6.4商代數(shù)和積代數(shù)6.5典型代數(shù)系統(tǒng)第四十二頁(yè)，共五十八頁(yè)，編輯于2023年，星期四6.5典型代數(shù)系統(tǒng)定義：設(shè)<S,*>是一個(gè)代數(shù)系統(tǒng)，*是S上的二元運(yùn)算；若*是可結(jié)合的，則<S,*>稱為一個(gè)半群。定義：如果<S,*>是一個(gè)半群，并且關(guān)于*運(yùn)算有單位元e，則稱<S,*>為獨(dú)異點(diǎn)或含幺半群，記作<S,*,e>

。例：<N,+,0>,<N,?,1>,<I,+,0>,<R,?,1>,<Nn,?n,1>都是獨(dú)異點(diǎn)，其中n為正整數(shù)。設(shè)Σ是非空有限字母表，則<Σ*,?,ε>是獨(dú)異點(diǎn)，而<Σ+,?>不是獨(dú)異點(diǎn)，其中ε是空串。

第四十三頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)例：如果獨(dú)異點(diǎn)<G,?>的每個(gè)元素關(guān)于?都是可逆的，則稱<G,?>為群。

設(shè)A為任意非空集合，PA是A到A的所有雙射函數(shù)的集合，于是<PA,?>構(gòu)成一個(gè)群，其中?是函數(shù)的復(fù)合運(yùn)算，稱<PA,?>為對(duì)稱群，稱<PA,?>的子群為A的變換群。

例如，A={1,2,3}，由A到A的所有雙射函數(shù)為3!=6個(gè)，它們是第四十四頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)?在PA上的運(yùn)算表如下：可以看出f1是幺元，f2的逆元是f2，f3的逆元是f3，f4的逆元是f4，f5的逆元是f6，f6的逆元是f5，并且<{f1,f2},?>，<{f1,f3},?>，<{f1,f4},?>和<{f1,f5,f6},?>都是<PA,?>的子群，所以它們都是變換群。第四十五頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)能否對(duì)一個(gè)抽象的代數(shù)系統(tǒng)進(jìn)行研究，而這種代數(shù)系統(tǒng)具有像命題代數(shù)、集合代數(shù)等一些具體代數(shù)系統(tǒng)所具有的最本質(zhì)的特征。這種抽象的代數(shù)系統(tǒng)就是由布爾（Boole）于1854年建立的布爾代數(shù)。實(shí)際上，還存在著比布爾代數(shù)更一般的代數(shù)系統(tǒng)，那就是格。

定義：設(shè)<L,≤>是偏序集，對(duì)于任意的a,b∈L，{a,b}均有上確界和下確界，則稱<L,≤>為格。第四十六頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)通常a*b用表示{a,b}的下確界,也就是a*b=inf{a,b}，稱為a,b的積。用a⊕b表示{a,b}的上確界，記a⊕b=sup{a,b}，稱為a和b的和，因?yàn)槠蚣偷娜魏畏强兆蛹纳?、下確界若存在，必唯一。所以*和⊕可以看作是集合L上的兩個(gè)代數(shù)運(yùn)算。于是代數(shù)系統(tǒng)<L,*,⊕>是一個(gè)格。每個(gè)全序結(jié)構(gòu)都是格。但是，不是所有的偏序結(jié)構(gòu)都是格。

第四十七頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng){a},,{c}是格，而c5zz1oi{e}{f}是偏序集，但不是格。

第四十八頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)例：設(shè)D是I+上的整除關(guān)系，亦即，對(duì)任意的a,b∈

I+，aDb，當(dāng)且僅當(dāng)a整除b。于是<I+,D>是一個(gè)格，其中a*b=a和b的最大公因子，a⊕b=a和b的最小公倍數(shù)。*和⊕的基本性質(zhì)：

等冪律交換律結(jié)合律吸收律第四十九頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)設(shè)<L,*,⊕>是格，則在格中每對(duì)元素都有上、下確界，設(shè)S={a1,a2,…,an}是L的有限子集，則S應(yīng)有上確界和下確界。一般地，可以把S的下確界和上確界表示成第五十頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)定義：有最大元素和最小元素的格稱為有界格。通常把有界格的最大元素和最小元素分別記為1和0，并稱它們?yōu)楦竦慕纭?/p>

顯然，<L,*,⊕>有限格是有界格，并且，其中L={a1,a2,…,an}

,常把有界格記為<L,*,⊕,0,1>。對(duì)于任意的a∈L,a≤1且0≤a，因此有第五十一頁(yè)，共五十八頁(yè)，編輯于2023年，星期四典型代數(shù)系統(tǒng)設(shè)是<L,*,⊕,0,1>有界格，a,b∈L，如果a*b=0且a⊕b=1，則稱b為a的補(bǔ)元，記為b=a'。如果L中每個(gè)元素都有補(bǔ)元，則稱<L,*,⊕,0,1>為有補(bǔ)格。補(bǔ)元的定義是相互的。一個(gè)元素可以有補(bǔ)元