1、第六章 代數(shù)系統(tǒng),授課教師：史哲文,代數(shù)系統(tǒng),代數(shù)系統(tǒng)又稱代數(shù)結(jié)構(gòu)，是用代數(shù)方法研究實(shí)際問題的一門學(xué)科。 研究代數(shù)系統(tǒng)的性質(zhì)和特殊的元素，代數(shù)系統(tǒng)與代數(shù)系統(tǒng)之間的關(guān)系。如代數(shù)系統(tǒng)的同態(tài)、滿同態(tài)和同構(gòu)等。,主要內(nèi)容,代數(shù)系統(tǒng)的基本概念 同態(tài)、同構(gòu)、同余 商代數(shù)、積代數(shù) 典型代數(shù)系統(tǒng),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、2 設(shè) 是集合A上的關(guān)系， 是求復(fù)合關(guān)系的運(yùn)算。它們構(gòu)成代數(shù)系統(tǒng) 。,代數(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) 的生成元。,代數(shù)系統(tǒng)的一般概念,定義：設(shè) 為代數(shù)系統(tǒng)。如果非空集合 對(duì)于每一個(gè) 皆封閉，則 也是代數(shù)系統(tǒng)，并稱其為 的子代數(shù)系統(tǒng)。,對(duì)于任意,是代數(shù)系統(tǒng) 的子代數(shù)。,但 不一定在 B 中，例如 ， 只能得出 是代數(shù)系統(tǒng) 的子代數(shù)。 而B與+、 不能構(gòu)成 的子代數(shù)。,例 設(shè)有代數(shù)系統(tǒng) ，其中Z表示非負(fù)整數(shù)集，和 是通常數(shù)的運(yùn)算。,對(duì)于任意,6

3、.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)是同型的。,同型關(guān)系,注意： 代數(shù)系統(tǒng)之間的同型關(guān)系具有自反性，對(duì)稱性和可傳遞性。 同型關(guān)系是等價(jià)關(guān)系。,同態(tài)和同構(gòu),(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)。,同態(tài)

4、和同構(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)。,同態(tài)和同構(gòu),同態(tài)和同構(gòu),又對(duì)于任意的 ,有 使,同態(tài)和同構(gòu),故,而,所有,即f是同態(tài)映射。,同態(tài)和同構(gòu),又因?yàn)閷?duì)任意的 ，存在 ,使,所以f是滿同態(tài)映射，即代數(shù)系統(tǒng)V1和V2是滿同態(tài)的。,同態(tài)和同構(gòu),定理： 若g為從 到 的關(guān)于f的同態(tài)，h為從 到 的關(guān)于 的同態(tài)，則hg為從 到 的關(guān)于 的同態(tài)。,證：由于g為V1到V2關(guān)于f的

5、同態(tài)，所以V1和V2是同型的；h為V2到V3關(guān)于 的同態(tài)，所以V2和V3是同型的。由同型關(guān)系的可傳遞性，可得V1和V3是同型的。,任取 及,得證。,同態(tài)和同構(gòu),推論： 若g為從 到 的關(guān)于f的同構(gòu)，h為從 到 的關(guān)于 的同構(gòu)，則hg為從 到 的關(guān)于 的同構(gòu)。,同態(tài)和同構(gòu),定理：設(shè)g為 到 的同態(tài),則 為 的子代數(shù)，并稱V3為V1的同態(tài)象點(diǎn)。,證：顯然， 是G2的非空子集。,任取 及 ,則 , 有 ，使得,且,表明 關(guān)于每個(gè) 都是封閉的,故 為 的子代數(shù)。,同態(tài)和同構(gòu),定理：設(shè)g為 到 的關(guān)于f的滿同態(tài)，f為從 到 的雙射函數(shù)。,(1)若二元運(yùn)算 是可交換的（或可結(jié)合的）， 則 也是可交換的（或

6、可結(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)算 的左單位元（或右單位元，或單位元）；,同態(tài)和同構(gòu),同態(tài)和同構(gòu),證： (b)對(duì)任意的 ，由于 ，故存在 ，使g(x)=a，g(y)=b以及g(z)=c，而,同理可得,同態(tài)和同構(gòu),證： (3)對(duì)任意的 ，存在 ，使 ，而,故 為關(guān)于 的單位元。同樣可證 和 分別為關(guān)于 的左單位元和右單位元。,從定理可知，滿同態(tài)映射能夠從一個(gè)代數(shù)系統(tǒng)到另一個(gè)代數(shù)系統(tǒng)單向保留所有的性質(zhì)（如交換律、結(jié)合律、含零元、

7、含單位元、元素的可逆性等），故滿同態(tài)映射是確保結(jié)構(gòu)的映射。,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)系。,同余關(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è) 且滿足 ,因此可有 ，并可寫出 和 ，這里 。于是可寫出,同余關(guān)系,所得結(jié)果說明， 。所以，R是代數(shù)系統(tǒng) 中的同余關(guān)系。,同余關(guān)系,例

8、：設(shè) ，驗(yàn)證 是 上的同余關(guān)系。,解：顯然關(guān)系 是個(gè)等價(jià)關(guān)系，故只要驗(yàn)證 關(guān)于+和 具有代換性質(zhì)即可。,對(duì)任意的 ,若 且 ，即存在 使,而,所以， 關(guān)于+滿足代換性質(zhì)。,同余關(guān)系,同理，,所以， 關(guān)于 也滿足代換性質(zhì)。,同余關(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è)),同余關(guān)系,因

9、為,故,因此，Rf是 上的同余關(guān)系。,這個(gè)定理說明，如果存在 到 的同態(tài)，則可以定義相應(yīng)于這一同態(tài)的同余關(guān)系。,6.4商代數(shù)和積代數(shù),定義： 設(shè)R為代數(shù)系統(tǒng) 上的同余關(guān)系，代數(shù)系統(tǒng) 稱為 關(guān)于R的商代數(shù)，其中 ，對(duì)于每個(gè) ，與 同型的 運(yùn)算定義為：對(duì)任意的 ,有,商代數(shù),為了保證 確實(shí)是一個(gè)代數(shù)系統(tǒng)，必須驗(yàn)證每個(gè) 是良定的，即 與等價(jià)類中代表元素 的選取無(wú)關(guān)。,任取 ,則有 ，而R是 上的同余關(guān)系，所以,定義：設(shè)R是集合G上的等價(jià)關(guān)系，定義函數(shù)g: GG/R為 ，稱g為G到G/R的正規(guī)映射。,商代數(shù),定理：設(shè)R為代數(shù)系統(tǒng) 上的同余關(guān)系，則正則映射 是 到商代數(shù) 的滿同態(tài)，并稱g為自然同態(tài)。,證

10、：顯然， 和 是同型的。任取 及 ,因?yàn)?所以，g是 到 的同態(tài)。,又因?yàn)閷?duì)任意 ，總有 ，使g(x)=xR=yR，所以g是滿射。,商代數(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)系。,商代數(shù)和積代數(shù),定理： 設(shè)f為 到 的關(guān)于 的同態(tài)，Rf是上對(duì)應(yīng)于f的同余關(guān)系，g是 到 的自然同態(tài)，則存在從 到 的同構(gòu)映射 ，且滿足 。,證： 定義函數(shù) 如下：,對(duì)任意 ，需要證明 是良定的。任取 ，若 ，則 ，因而 ，這表明 是良定的。,對(duì)任意的 ，存在 使 ，則 。這表明

11、是滿射。,商代數(shù)和積代數(shù),任取 ，若 ，即f(x1)=f(x2)，則 ，故 ，表明 是單射。,定義函數(shù) 如下：對(duì)任意 ，令 ，顯然h是雙射，任取 ,商代數(shù)和積代數(shù),綜上所述， 是到 的同構(gòu)映射，并且對(duì)任意 ，有,商代數(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)通過“直接積”來(lái)構(gòu)造積代數(shù)。,商代數(shù)和積代數(shù),定義：設(shè) 為同型的代數(shù)系統(tǒng)A1,A2,Am的積代數(shù) 定義為 。其中對(duì)每個(gè) 及對(duì)應(yīng)的 ，定義 如下： ，對(duì)任意 ，令 稱 為積代數(shù) 的因子代數(shù)。,商代數(shù)和積代數(shù),例： 和 為兩個(gè)代數(shù)系統(tǒng)

12、,其中 ，G2=b1,b2,b3 ，二元運(yùn)算*和 的運(yùn)算如下表所示。,求積代數(shù),商代數(shù)和積代數(shù),6.5典型代數(shù)系統(tǒng),定義：設(shè)是一個(gè)代數(shù)系統(tǒng)，*是S上的二元運(yùn)算；若*是可結(jié)合的，則稱為一個(gè)半群。,定義： 如果是一個(gè)半群，并且關(guān)于*運(yùn)算有單位元e，則稱為獨(dú)異點(diǎn)或含幺半群，記作 。,例：, 都是獨(dú)異點(diǎn)，其中n為正整數(shù)。,設(shè)是非空有限字母表，則 是獨(dú)異點(diǎn)，而 不是獨(dú)異點(diǎn)，其中是空串。,典型代數(shù)系統(tǒng),例： 如果獨(dú)異點(diǎn)的每個(gè)元素關(guān)于都是可逆的，則稱為群。,設(shè)A為任意非空集合，PA是A到A的所有雙射函數(shù)的集合，于是構(gòu)成一個(gè)群，其中是函數(shù)的復(fù)合運(yùn)算，稱為對(duì)稱群，稱的子群為A的變換群。,例如，A=1,2,3，由

13、A到A的所有雙射函數(shù)為3!=6個(gè)，它們是,典型代數(shù)系統(tǒng),在PA上的運(yùn)算表如下：,可以看出f1是幺元，f2的逆元是f2，f3的逆元是f3，f4的逆元是f4，f5的逆元是f6，f6的逆元是f5，并且， 和 都是的子群，所以它們都是變換群。,典型代數(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è) 是偏序集，對(duì)于任意的a,bL，a,b均有上確界和下確界，則稱 為格。,典型代數(shù)系統(tǒng),通常a*b用表示

14、a,b的下確界,也就是a*b=infa,b，稱為a,b的積。用ab表示a,b的上確界，記ab=supa,b，稱為a和b的和，因?yàn)槠蚣偷娜魏畏强兆蛹纳?、下確界若存在，必唯一。所以*和可以看作是集合L上的兩個(gè)代數(shù)運(yùn)算。于是代數(shù)系統(tǒng)是一個(gè)格。,每個(gè)全序結(jié)構(gòu)都是格。但是，不是所有的偏序結(jié)構(gòu)都是格。,典型代數(shù)系統(tǒng),a,b,c是格，而def是偏序集，但不是格。,典型代數(shù)系統(tǒng),例：設(shè)D是I+上的整除關(guān)系，亦即，對(duì)任意的a,b I+，aDb，當(dāng)且僅當(dāng)a整除b。于是是一個(gè)格，其中a*b=a和b的最大公因子，ab=a和b的最小公倍數(shù)。,*和的基本性質(zhì)：,等冪律,交換律,結(jié)合律,吸收律,典型代數(shù)系統(tǒng),設(shè)是格，

15、則在格中每對(duì)元素都有上、下確界，設(shè)S=a1,a2,an是L的有限子集，則S應(yīng)有上確界和下確界。一般地，可以把S的下確界和上確界表示成,典型代數(shù)系統(tǒng),定義：有最大元素和最小元素的格稱為有界格。通常把有界格的最大元素和最小元素分別記為1和0，并稱它們?yōu)楦竦慕纭?顯然，有限格是有界格，并且 ，其中L=a1,a2,an ,常把有界格記為。對(duì)于任意的aL,a1且0a，因此有,典型代數(shù)系統(tǒng),設(shè)是有界格，a,bL，如果a*b=0且ab=1，則稱b為a的補(bǔ)元，記為b=a。如果L中每個(gè)元素都有補(bǔ)元，則稱為有補(bǔ)格。,補(bǔ)元的定義是相互的。一個(gè)元素可以有補(bǔ)元，也可以沒有補(bǔ)元，如果有補(bǔ)元，可以有一個(gè)補(bǔ)元，也可以有多個(gè)補(bǔ)

16、元。,典型代數(shù)系統(tǒng),在左圖的格中，a和b均為c的補(bǔ)元，a和b的補(bǔ)元均為c。1和0互為補(bǔ)元，且唯一。,典型代數(shù)系統(tǒng),定義： 設(shè)是一個(gè)格，如果*對(duì)是可分配的，并且對(duì)*也是可分配的，則稱是分配格。,要判斷一個(gè)格是不是分配格，只須檢驗(yàn)一個(gè)分配律即可，因?yàn)樵诜峙涓竦亩x中，兩個(gè)分配律是互為對(duì)偶的，故對(duì)偶原理適用于分配格。,均不是分配格,典型代數(shù)系統(tǒng),一個(gè)格是分配格，當(dāng)且僅當(dāng)它沒有子格同構(gòu)于這兩個(gè)五元素格之一。,典型代數(shù)系統(tǒng),定義： 一個(gè)有補(bǔ)分配格稱為一個(gè)布爾代數(shù)。,一般用表示布爾代數(shù)。其中是格,是一元的求補(bǔ)運(yùn)算，0和1為最小元素和最大元素。,例：設(shè)B=0，1，B上的運(yùn)算*，和如下表定義：,是最簡(jiǎn)單的布爾代數(shù)，稱為電路代數(shù)。,典型代數(shù)系統(tǒng),例：設(shè)S是非空集合，不難證明 是布爾代數(shù)，稱為集合代數(shù)。其中任何AS的補(bǔ)元為A=S