離散數(shù)學(xué) 課件 課程 考研 大學(xué)課程 數(shù)學(xué)一 第六章 幾個(gè)典型的代數(shù)系統(tǒng)

第6章幾個(gè)典型的代數(shù)系統(tǒng)6.1半群與群6.2環(huán)與域6.3格與布爾代數(shù)

半群與群1.半群:設(shè)<S,*>是代數(shù)系統(tǒng)，*是S上的二元運(yùn)算，如果*滿足結(jié)合律，則稱代數(shù)系統(tǒng)<S,*>為半群。設(shè)<S,*>是半群，如果運(yùn)算*又滿足交換律，則稱半群<S,*>為可交換半群。若S為有限集合，則半群<S,*>稱為有限半群。如果半群<S,*>中的二元運(yùn)算含有幺元，則稱S,*為含幺半群或獨(dú)異點(diǎn)。半群的子代數(shù)叫做子半群。

【例題】設(shè)R是實(shí)數(shù)集，定義R上的二元運(yùn)算*為：

x,yR，x*y=x|y|其中x|y|為實(shí)數(shù)x與實(shí)數(shù)y的絕對(duì)值的乘法運(yùn)算，證明<R,*>是一個(gè)半群。2.群：設(shè)G,*是代數(shù)系統(tǒng)，其中，G是非空集合，*是G上二元運(yùn)算。如果⑴運(yùn)算*在G上是可結(jié)合的。⑵運(yùn)算*存在幺元eG。⑶xG，有x–1G。則稱G,*為群。有時(shí)也可將群G,*簡(jiǎn)稱為群G?！纠}】設(shè)G＝{e,a,b,c}，右表給出了*的運(yùn)算表。證明G,*是群。Klein四元群*eabceeabcaaecbbbceaccbae3.阿貝爾群:設(shè)<G,*>是群，如果二元運(yùn)算*是可交換的，則稱該群為阿貝爾(Abel)群，或稱可交換群。4.子群:設(shè)<G,*>是群，H是G的非空子集，如果<H,*>也構(gòu)成群，則稱<H,*>是<G,*>的子群。5.陪集：設(shè)<H,*>是群<G,*>的子群，a是G中任意一個(gè)元素，則稱集合Ha={h*a|hH}(aH={a*h|hH

})為由a確定的子群H,*在群G,*中的右(左)陪集，簡(jiǎn)稱為H關(guān)于a的右(左)陪集，a叫做右(左)陪集Ha(aH)的代表元。【例】設(shè)G,*是Klein四元群。令H={e,a}，H,*是G,*子群。試求子群H,*在群G,*中的左陪集eH,aH,bH,cH和右陪集He,Ha,Hb,Hc.

解：eH={e*e,e*a}={e,a}=H

aH={a*e,a*a}={a,e}=H

bH={b*e,b*a}={b,c}

cH={

c*e,c*a}={c,b}=bHHe={e*e,a*e}={e,a}=HHa={e*a,a*a}={a,e}=H

Hb={e*b,a*b}={b,c}

Hc={

e*c,a*c}={c,b}=Hb環(huán)與域1.環(huán)：設(shè)A,＋,?是有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，滿足：⑴A,＋是阿貝爾群。⑵A,?是半群。⑶運(yùn)算?對(duì)運(yùn)算＋是可分配的，即a,b,cAa?(b＋c)=(a?b)＋(a?c)(左分配律)(b＋c)?a=(b?a)＋(c?a)(右分配律)則稱代數(shù)系統(tǒng)A,＋,?為環(huán)。幾個(gè)常見的特殊環(huán)：設(shè)A,＋,?是環(huán)。如果A,?是可交換的，則稱A,＋,?為交換環(huán)。如果A,?含有幺元，則稱A,＋,?為含幺環(huán)。(3)如果a,bA，a?b=0，必有a=0或b=0，則稱A,＋,?為無零因子環(huán)。(4)如果A,＋,?是交換環(huán)、含幺環(huán)和無零因子環(huán)。則稱A,＋,?是整環(huán)。(5)如果A,＋,?至少含有2個(gè)元素且是含幺和無零因子的，且aR(a≠0)有a-1R，則稱A,＋,?是除環(huán)。2.域：若環(huán)A,＋,?既是整環(huán)，又是除環(huán)，則稱A,＋,?是域?！纠?/p>

Z,＋,?是整環(huán)不是域，而R,＋,?是域.

環(huán)整環(huán)

除環(huán)

交換環(huán)含幺環(huán)無零因子環(huán)域同時(shí)滿足：至少含有2個(gè)元素，且aR(a≠0)有a-1R格與布爾代數(shù)1.格：設(shè)S,?是偏序集，如果x,yS，集合{x,y}都有最小上界和最大下界，則稱S關(guān)于?構(gòu)成一個(gè)格。說明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最小上界和最大下界看成x與y的二元運(yùn)算∨和∧。

x∨y：表示x與y的最小上界

x∧y：表示x和y的最大下界。

本章出現(xiàn)的∨和∧符號(hào)只代表格中的運(yùn)算，而不再有其它的含義?！纠吭O(shè)n是正整數(shù)，Sn是n的正因子的集合.D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格.【例】圖中給出了一些偏序集的哈斯圖，判斷它們是否構(gòu)成格。

答：都不是格.abcdefabcdeabcdefabcdef格的對(duì)偶原理設(shè)S,?是偏序集，在S上定義二元關(guān)系?={a,b|b,a?}則S,?也是偏序集。設(shè)f是含有格中元素以及符號(hào)=,?,?,∨(最小上界運(yùn)算)和∧(最小下界運(yùn)算)的命題。將f中的?替換成?，?替換成?，∨替換成∧，∧替換成∨，得到一個(gè)新命題，所得的命題叫做f的對(duì)偶命題，記為f*。設(shè)f是含有格中元素以及符號(hào)=,?,?,∨和∧的命題，若f對(duì)一切格為真，則f的對(duì)偶命題f*也對(duì)一切格為真。該原理稱為格的對(duì)偶原理。格的性質(zhì)設(shè)L,?是格，則a,b,cL有⑴a∨b=b∨a，

a∧b=b∧a(交換律)⑵(a∨b)∨c=a∨(b∨c) (a∧b)∧c=a∧(b∧c)(結(jié)合律)⑶a∨a=a，a∧a=a(冪等律)⑷a∨(a∧b)=a

a∧(a∨b)=a(吸收律)

格的代數(shù)系統(tǒng)形式：設(shè)S,*,°是代數(shù)系統(tǒng)，其中*和°都是二元運(yùn)算，如果*和°在S上滿足交換律、結(jié)合律和吸收律，則可適當(dāng)定義S中的偏序關(guān)系使得S,*,°構(gòu)成一個(gè)格?！纠緽是一個(gè)有限集，P(B)是集合B的冪集，則<P(B),∩,∪>是格。2.分配格:設(shè)L,?是格，L,∨,∧是L,?導(dǎo)出的代數(shù)系統(tǒng)，如果a,b,cL有

a∨(b∧c)=(a∨b)∧(a∨c)

a∧(b∨c)=(a∧b)∨(a∧c)則稱L,∨,∧為分配格。abc(1)(2)(3)(4)【例題】判斷下面哈斯圖哪些是分配格。分配格不是分配格3.子格：

設(shè)S,∨,∧是格，B是S的非空子集，如果B關(guān)于運(yùn)算∨和∧也構(gòu)成格，則稱B,∨,∧是S,∨,∧的子格。【例】設(shè)S12＝{1,2,3,4,6,12}，D為整除關(guān)系，<S12,D>是格。

令B1＝{1,2,3,6}，B2＝{2,4,6,12}，則B1,∨,∧和B2,∨,∧是格S12,∨,∧的子格。

令B3＝{1,2,3,12}，由于2∨3=6，而6B3，所以B3,∨,∧不是格S12,∨,∧的子格。鉆石格五角格定理：一個(gè)格是分配格的充分必要條件是該格中不含有與鉆石格或五角格同構(gòu)的子格。推論1

設(shè)A,?是格，如果|A|＜5，則A,?一定是分配格。推論2

設(shè)A,?是格，如果A,?是全序集，則A,?

一定是分配格。4.全下(上)界：設(shè)L,?是格，如果aL，xL都有

a?x(x?a)則稱a為格L,?的全下(上)界，記為0(1)。設(shè)L,?是格，若格L,?有全下界或全上界，則它們一定是惟一的。具有全上界和全下界的格稱為有界格，記作L,∨,∧,0,1.5.補(bǔ)元：設(shè)L,∨,∧,0,1為有界格，如果aL，bL，使得a∨b=1且a∧b=0，則稱b是a的補(bǔ)元。如果格中每個(gè)元素都至少有一個(gè)補(bǔ)元，則稱這個(gè)格為有補(bǔ)格?！纠?與1互補(bǔ)a,b,c

沒補(bǔ)元0與1互補(bǔ)a,b,c中任兩個(gè)元素都互補(bǔ)0與1互補(bǔ)a與b,c互補(bǔ)有補(bǔ)格【例題】右圖是一個(gè)有界格的哈斯圖。找出a,b,c,d,e的補(bǔ)元。

解：a的補(bǔ)元是e；b沒有補(bǔ)元；c的補(bǔ)元是d；d的補(bǔ)元是c和e；e的補(bǔ)元是a和d；0和1互為補(bǔ)元。補(bǔ)元的性質(zhì)：

對(duì)分配格L來說，如果aL有補(bǔ)元，則一定有唯一補(bǔ)元，記為a′

。【例】6.布爾代數(shù)：如果L,∨,∧,0,1是有補(bǔ)分配格，則稱L為布爾格，也叫做布爾代數(shù)。布爾代數(shù)L可記為

L,∨,∧,′,0,1，其中′表示求補(bǔ)運(yùn)算

。布爾代數(shù)中的兩個(gè)二元運(yùn)算滿足交換律、結(jié)合律、冪等律和吸收律。此外，