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

第六章代數(shù)系統(tǒng)第一頁，共五十八頁，2022年，8月28日第六章代數(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)第二頁，共五十八頁，2022年，8月28日6.1代數(shù)系統(tǒng)的一般概念定義：設(shè)S為非空集合，Ω為S上代數(shù)運算的非空集合，稱為一個代數(shù)系統(tǒng)或代數(shù)結(jié)構(gòu)。集合S稱為V的定義域。如果為有限集合，則將記作。如果S為有限集合，則稱V為有限代數(shù)系統(tǒng)，并稱|S|為的階。

例1

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

例2

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

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

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

第九頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)(3)如果V1=V2，并且f為恒等映射，則稱g為關(guān)于f的自同態(tài)映射，簡稱自同態(tài)。(4)如果g為雙射，則稱g為關(guān)于f的同構(gòu)映射，簡稱關(guān)于f的同構(gòu)，并稱代數(shù)系統(tǒng)V1和V2是同構(gòu)的。(5)如果V1=V2，并且f為恒等映射，則稱g為關(guān)于f的自同構(gòu)映射，簡稱自同構(gòu)。

第十頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)第十一頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)例：給定代數(shù)系統(tǒng)和，定義函數(shù)如下：

試證f是V1到V2的滿同態(tài)映射。證：定義函數(shù)如下：顯然g為雙射，故V1和V2是同型的。又對于任意的,有使第十二頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)故而所有即f是同態(tài)映射。第十三頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)又因為對任意的，存在,使所以f是滿同態(tài)映射，即代數(shù)系統(tǒng)V1和V2是滿同態(tài)的。

第十四頁，共五十八頁，2022年，8月28日同態(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是同型的。任取及得證。第十五頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)推論：若g為從到的關(guān)于f的同構(gòu)，h為從到的關(guān)于的同構(gòu)，則h?g為從到的關(guān)于的同構(gòu)。第十六頁，共五十八頁，2022年，8月28日同態(tài)和同構(gòu)定理：設(shè)g為到的同態(tài),則為的子代數(shù)，并稱V3為V1的同態(tài)象點。

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

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

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

第二十六頁，共五十八頁，2022年，8月28日同余關(guān)系同理，所以，關(guān)于也滿足代換性質(zhì)。

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

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

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

第三十九頁，共五十八頁，2022年，8月28日商代數(shù)和積代數(shù)例：和為兩個代數(shù)系統(tǒng),其中，G2={b1,b2,b3}，二元運算*和的運算如下表所示。

求積代數(shù)第四十頁，共五十八頁，2022年，8月28日商代數(shù)和積代數(shù)解：對任意的，第四十一頁，共五十八頁，2022年，8月28日第六章代數(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)第四十二頁，共五十八頁，2022年，8月28日6.5典型代數(shù)系統(tǒng)定義：設(shè)<S,*>是一個代數(shù)系統(tǒng)，*是S上的二元運算；若*是可結(jié)合的，則<S,*>稱為一個半群。定義：如果<S,*>是一個半群，并且關(guān)于*運算有單位元e，則稱<S,*>為獨異點或含幺半群，記作<S,*,e>

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

第四十三頁，共五十八頁，2022年，8月28日典型代數(shù)系統(tǒng)例：如果獨異點<G,?>的每個元素關(guān)于?都是可逆的，則稱<G,?>為群。

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

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

定義：設(shè)<L,≤>是偏序集，對于任意的a,b∈L，{a,b}均有上確界和下確界，則稱<L,≤>為格。第四十六頁，共五十八頁，2022年，8月28日典型代數(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的和，因為偏序集和的任何非空子集的上、下確界若存在，必唯一。所以*和⊕可以看作是集合L上的兩個代數(shù)運算。于是代數(shù)系統(tǒng)<L,*,⊕>是一個格。每個全序結(jié)構(gòu)都是格。但是，不是所有的偏序結(jié)構(gòu)都是格。

第四十七頁，共五十八頁，2022年，8月28日典型代數(shù)系統(tǒng){a},,{c}是格，而aoqogcg{e}{f}是偏序集，但不是格。

第四十八頁，共五十八頁，2022年，8月28日典型代數(shù)系統(tǒng)例：設(shè)D是I+上的整除關(guān)系，亦即，對任意的a,b∈

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

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

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

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