離散數(shù)學(xué)屈婉玲第十四章

1第五部分代數(shù)系統(tǒng)簡(jiǎn)介主要內(nèi)容二元運(yùn)算及其性質(zhì)

二元運(yùn)算和一元運(yùn)算、二元運(yùn)算性質(zhì)、特異元素代數(shù)系統(tǒng)的概念幾個(gè)典型的代數(shù)系統(tǒng)半群、獨(dú)異點(diǎn)、群環(huán)與域格與布爾代數(shù)代數(shù)系統(tǒng)的同構(gòu)與同態(tài)2第十四章代數(shù)系統(tǒng)簡(jiǎn)介主要內(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)314.1代數(shù)系統(tǒng)的基本概念定義14.1

設(shè)S為集合，函數(shù)f：S

S

S稱(chēng)為S上的二元運(yùn)算，簡(jiǎn)稱(chēng)為二元運(yùn)算．函數(shù)f:S→S稱(chēng)為S上的一元運(yùn)算，簡(jiǎn)稱(chēng)一元運(yùn)算.S中任何元素都可以進(jìn)行運(yùn)算，且運(yùn)算的結(jié)果惟一．S中任何元素的運(yùn)算結(jié)果都屬于S，即S對(duì)該運(yùn)算封閉．例1(1)自然數(shù)集合N上的加法和乘法是N上的二元運(yùn)算，但減法和除法不是．(2)整數(shù)集合Z上的加法、減法和乘法都是Z上的二元運(yùn)算，而除法不是．求一個(gè)數(shù)的相反數(shù)是Z上的一元運(yùn)算.(3)非零實(shí)數(shù)集R*上的乘法和除法都是R*上的二元運(yùn)算，而加法和減法不是．求倒數(shù)是R*上的一元運(yùn)算.4實(shí)例(4)

設(shè)Mn(R)表示所有n階(n≥2)實(shí)矩陣的集合，即

矩陣加法、乘法是Mn(R)上的二元運(yùn)算.轉(zhuǎn)置是一元運(yùn)算.(5)S為任意集合，則∪、∩、－、

為P(S)上二元運(yùn)算.

運(yùn)算為一元運(yùn)算.(6)SS為S上的所有函數(shù)的集合，則合成運(yùn)算

為SS上二元運(yùn)算.求反函數(shù)不一定是一元運(yùn)算.

5二元與一元運(yùn)算的表示1．算符可以用?,?,·,

,

,

等符號(hào)表示二元或一元運(yùn)算，稱(chēng)為算符.對(duì)二元運(yùn)算?，如果x與y運(yùn)算得到z，記做x?y=z對(duì)一元運(yùn)算

,x的運(yùn)算結(jié)果記作

x.2．表示二元或一元運(yùn)算的方法:解析公式和運(yùn)算表公式表示例設(shè)R為實(shí)數(shù)集合，如下定義R上的二元運(yùn)算?：

x,y∈R,x?y=x.那么3?4=3，0.5?(

3)=0.56運(yùn)算表：表示有窮集上的一元和二元運(yùn)算

運(yùn)算表

二元運(yùn)算的運(yùn)算表

一元運(yùn)算的運(yùn)算表7

例2

設(shè)S=P({a,b})，S上的

和

～運(yùn)算的運(yùn)算表如下

運(yùn)算表的實(shí)例8二元運(yùn)算的性質(zhì)定義14.2-4

設(shè)?為S上的二元運(yùn)算,(1)若對(duì)任意x,y∈S有x?y=y?x,則稱(chēng)運(yùn)算在S上滿(mǎn)足交換律.(2)若對(duì)任意x,y,z∈S有(x?y)?z=x?(y?z),則稱(chēng)運(yùn)算在S上滿(mǎn)足結(jié)合律.(3)若對(duì)任意x∈S有x?x=x,則稱(chēng)運(yùn)算在S上滿(mǎn)足冪等律.定義14.5-6

設(shè)?和?為S上兩個(gè)不同的二元運(yùn)算,(1)若對(duì)任意x,y,z∈S有(x?y)?z=(x?z)?(y?z)，

z?(x?y)=(z?x)?(z?y),則稱(chēng)?運(yùn)算對(duì)?運(yùn)算滿(mǎn)足分配律.(2)若

和?都可交換,且對(duì)任意x,y∈S有x?(x?y)=x，x?(x?y)=x,

則稱(chēng)?和?運(yùn)算滿(mǎn)足吸收律.9實(shí)例Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n

2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|

2集合運(yùn)算交換律結(jié)合律冪等律Z,Q,R普通加法+普通乘法

有有有有無(wú)無(wú)Mn(R)矩陣加法+矩陣乘法

有無(wú)有有無(wú)無(wú)P(B)并

交相對(duì)補(bǔ)對(duì)稱(chēng)差有有無(wú)有有有無(wú)有有有無(wú)無(wú)AA函數(shù)復(fù)合

無(wú)有無(wú)10

集合運(yùn)算分配律吸收律Z,Q,R普通加法+與乘法

對(duì)+可分配+對(duì)不分配無(wú)Mn(R)矩陣加法+與乘法

對(duì)+可分配+對(duì)不分配無(wú)P(B)并

與交

對(duì)

可分配

對(duì)

可分配有交

與對(duì)稱(chēng)差

對(duì)

可分配無(wú)實(shí)例Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n

2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|

211特異元素：?jiǎn)挝辉?、零元定義14.7-9

設(shè)?為S上的二元運(yùn)算,(1)如果存在el(或er)

S，使得對(duì)任意x∈S都有

el?x=x(或x?er

=x)，則稱(chēng)el(或er)是S中關(guān)于?運(yùn)算的左(或右)單位元.若e∈S關(guān)于?運(yùn)算既是左單位元又是右單位元，則稱(chēng)e為S上關(guān)于?運(yùn)算的單位元.單位元也叫做幺元.(2)如果存在

l(或

r)∈S，使得對(duì)任意x∈S都有

l?x=

l

(或x?

r

=

r)，則稱(chēng)

l(或

r)是S中關(guān)于?運(yùn)算的左(或右)零元.若

∈S關(guān)于?運(yùn)算既是左零元又是右零元，則稱(chēng)

為S上關(guān)于運(yùn)算?的零元.12可逆元素和逆元(3)設(shè)?為S上的二元運(yùn)算,令e為S中關(guān)于運(yùn)算

的單位元.

對(duì)于x∈S，如果存在yl(或yr)∈S使得

yl?x=e（或x?yr=e）則稱(chēng)yl(或yr)是x的左逆元（或右逆元）.關(guān)于?運(yùn)算，若y∈S既是x的左逆元又是x的右逆元，則稱(chēng)y為x的逆元.如果x的逆元存在，就稱(chēng)x是可逆的.可以證明：對(duì)于給定二元運(yùn)算，單位元或零元如果存在，則是唯一的.對(duì)于可結(jié)合的二元運(yùn)算，給定元素若存在逆元，則是唯一的逆元

13實(shí)例集合運(yùn)算單位元零元逆元Z,Q,R普通加法+普通乘法

01無(wú)0x逆元

xx逆元x

1(x

1

給定集合)Mn(R)矩陣加法+矩陣乘法

n階全0矩陣n階單位矩陣無(wú)n階全0矩陣X逆元

XX的逆元X

1（X可逆）P(B)并

交對(duì)稱(chēng)差

B

B

無(wú)

的逆元為

B的逆元為BX的逆元為X消去律定義14.10設(shè)°為S上的二元運(yùn)算，如果對(duì)于任意的x,y,z

S滿(mǎn)足以下條件：(1)若x°y=x°z且x

，則y=z；(2)若y°x=z°x且x

，則y=z；稱(chēng)?運(yùn)算滿(mǎn)足消去律，其中(1)為左消去律，(2)為右消去律．注意被消去的x不能是運(yùn)算的零元

．整數(shù)集合上的加法和乘法滿(mǎn)足消去律．P(S)上的并和交一般不滿(mǎn)足消去律.對(duì)稱(chēng)差運(yùn)算

滿(mǎn)足消去律,

A,B,C

P(S)，都有A

B=A

C

B=CB

A=C

A

B=C1415代數(shù)系統(tǒng)定義14.11

非空集合S和S上k個(gè)一元或二元運(yùn)算f1,f2,…,fk組成的系統(tǒng)稱(chēng)為代數(shù)系統(tǒng),簡(jiǎn)稱(chēng)代數(shù)，記做<S,f1,f2,…,fk>.實(shí)例：(1)<N,＋>,<Z,＋,·>,<R,＋,·>是代數(shù)系統(tǒng)，+和·分別表示普通加法和乘法.(2)<Mn(R),＋,·>是代數(shù)系統(tǒng)，＋和·分別表示n階(n≥2)實(shí)矩陣的加法和乘法.(3)<Zn,

,

>是代數(shù)系統(tǒng)，Zn＝{0,1,…,n-1}，

和

分別表示模n的加法和乘法，對(duì)于x,y∈Zn，x

y=(x＋y)modn，x

y=(xy)modn(4)<P(S),

,

,~>是代數(shù)系統(tǒng)，

和

為并和交，~為絕對(duì)補(bǔ)16代數(shù)系統(tǒng)的成分與表示構(gòu)成代數(shù)系統(tǒng)的成分：集合（也叫載體，規(guī)定了參與運(yùn)算的元素）運(yùn)算（這里只討論有限個(gè)二元和一元運(yùn)算）代數(shù)常數(shù)（通常是與運(yùn)算相關(guān)的特異元素：如單位元等）研究代數(shù)系統(tǒng)時(shí)，如果把運(yùn)算具有它的特異元素也作為系統(tǒng)的性質(zhì)之一，那么這些特異元素可以作為系統(tǒng)的成分，叫做代數(shù)常數(shù).例如：代數(shù)系統(tǒng)<Z,+,0>：集合Z,運(yùn)算+,代數(shù)常數(shù)0代數(shù)系統(tǒng)<P(S),∪,∩>：集合P(S),運(yùn)算∪和∩，無(wú)代數(shù)常數(shù)17代數(shù)系統(tǒng)的表示(1)列出所有的成分：集合、運(yùn)算、代數(shù)常數(shù)（如果存在）如<Z,+,0>,<P(S),∪,∩>(2)列出集合和運(yùn)算，在規(guī)定系統(tǒng)性質(zhì)時(shí)不涉及具有單位元的性質(zhì)（無(wú)代數(shù)常數(shù)）如<Z,+>,<P(S),∪,∩>(3)用集合名稱(chēng)簡(jiǎn)單標(biāo)記代數(shù)系統(tǒng)在前面已經(jīng)對(duì)代數(shù)系統(tǒng)作了說(shuō)明的前提下使用如代數(shù)系統(tǒng)Z,P(B)18同類(lèi)型與同種代數(shù)系統(tǒng)定義14.12(1)如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對(duì)應(yīng)運(yùn)算的元數(shù)相同，且代數(shù)常數(shù)的個(gè)數(shù)也相同，則稱(chēng)它們是同類(lèi)型的代數(shù)系統(tǒng).(2)如果兩個(gè)同類(lèi)型的代數(shù)系統(tǒng)規(guī)定的運(yùn)算性質(zhì)也相同，則稱(chēng)為同種的代數(shù)系統(tǒng).例如V1=<R,+,·,0,1>,V2=<Mn(R),+,·,

,E>,

為n階全0矩陣，E為n階單位矩陣,V3=<P(B),∪,∩,

,B>V1,V2,V3是同類(lèi)型的代數(shù)系統(tǒng)，它們都含有2個(gè)二元運(yùn)算,2個(gè)代數(shù)常數(shù).V1,V2是同種的代數(shù)系統(tǒng)，V1,V2與V3不是同種的代數(shù)系統(tǒng)19V1V2V3+可交換、可結(jié)合·可交換、可結(jié)合+滿(mǎn)足消去律·滿(mǎn)足消去律·對(duì)+可分配+對(duì)·不可分配+與·沒(méi)有吸收律+可交換、可結(jié)合·可交換、可結(jié)合+滿(mǎn)足消去律·不滿(mǎn)足消去律·對(duì)+可分配+對(duì)·不可分配+與·沒(méi)有吸收律∪可交換、可結(jié)合∩可交換、可結(jié)合∪不滿(mǎn)足消去律∩不滿(mǎn)足消去律∩對(duì)∪可分配∪對(duì)∩可分配∪與∩滿(mǎn)足吸收律運(yùn)算性質(zhì)比較2014.2幾個(gè)典型的代數(shù)系統(tǒng)主要內(nèi)容半群、獨(dú)異點(diǎn)與群環(huán)與域格與布爾代數(shù)21半群、獨(dú)異點(diǎn)與群的定義定義14.13(1)設(shè)V=<S,°

>是代數(shù)系統(tǒng)，°為二元運(yùn)算，如果°運(yùn)算是可結(jié)合的，則稱(chēng)V為半群.(2)設(shè)V=<S,°>是半群，若e∈S是關(guān)于°運(yùn)算的單位元，則稱(chēng)V

是含幺半群，也叫做獨(dú)異點(diǎn).有時(shí)也將獨(dú)異點(diǎn)V記作

V=<S,°,e>.(3)設(shè)V=<S,°>是獨(dú)異點(diǎn)，e

S關(guān)于°運(yùn)算的單位元，若

a

S，a

1

S，則稱(chēng)V是群.通常將群記作G.22實(shí)例例1

(1)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群，+是普通加法.這些半群中除<Z+,+>外都是獨(dú)異點(diǎn)(2)設(shè)n是大于1的正整數(shù)，<Mn(R),+>和<Mn(R),·>都是半群，也都是獨(dú)異點(diǎn)，其中+和·分別表示矩陣加法和矩陣乘法(3)<P(B),

>為半群，也是獨(dú)異點(diǎn)，其中

為集合對(duì)稱(chēng)差運(yùn)算(4)<Zn,

>為半群，也是獨(dú)異點(diǎn)，其中Zn={0,1,…,n

1}，

為模n加法(5)<AA,?>為半群，也是獨(dú)異點(diǎn)，其中?為函數(shù)的復(fù)合運(yùn)算(6)<R*,?>為半群，其中R*為非零實(shí)數(shù)集合，?運(yùn)算定義如下：

x,y

R*,x?y=y半群：

上的字代數(shù)和語(yǔ)言例2設(shè)

是有窮字母表，

k

N，定義下述集合：

k={a1a2…ak|ai

}是

上所有長(zhǎng)度為k的串的集合.當(dāng)k=0時(shí)，

0={

}，

表示空串.令

表示

上所有有限長(zhǎng)度的串的集合，

+=

*

{

}則表示

上所有長(zhǎng)度至少為1的有限串的集合.在

*上可以定義串的連接運(yùn)算，

1,

2

*，

1=a1a2…am,

2=b1b2…bn有

1

2=a1a2…amb1b2…bn顯然

*關(guān)于連接運(yùn)算構(gòu)成一個(gè)獨(dú)異點(diǎn),稱(chēng)為

上的字代數(shù).

上的語(yǔ)言L就是

*的一個(gè)子集.23群碼例3某二進(jìn)制碼的碼字x=x1x2…x7由7位構(gòu)成，其中x1,x2,x3和x4為數(shù)據(jù)位,x5,x6和x7為校驗(yàn)位，且滿(mǎn)足：

x5=x1

x2

x3

x6=x1

x2

x4

x7=x1

x3

x4這里的

是模2加法.設(shè)G為所有碼字構(gòu)成的集合，在G上定義二元運(yùn)算如下：

x,y

G,x°y=z1z2...z7,zi=xi

yi,i=1,2,…,7.那么<G,°>構(gòu)成群.這樣的碼稱(chēng)為群碼

2425群的相關(guān)概念及子群有限群：若群G是有窮集，則稱(chēng)G是有限群，否則稱(chēng)為無(wú)限群群G的階：群G含有的元素?cái)?shù)，有限群G的階記作|G|.交換群或阿貝爾(Abel)群：群中運(yùn)算可交換實(shí)例：<Z,+>和<R,+>是無(wú)限群，<Zn,

>是n階群．上述所有的群都是交換群，但n階（n

2）實(shí)可逆矩陣的集合（是Mn(R)的真子集）關(guān)于矩陣乘法構(gòu)成的群是非交換群子群：群G的非空子集H關(guān)于群的運(yùn)算構(gòu)成群，稱(chēng)為G的子群.實(shí)例：

H=nZ={nk|k

Z}，n為給定自然數(shù)，是<Z,+>的子群.當(dāng)n=0和1時(shí)，子群分別是{0}和Z，稱(chēng)為平凡子群；

2Z由能被2整除的全體整數(shù)構(gòu)成，也是子群.群的直積定義14.14設(shè)G1=<A,

>和G2=<B,

>是群，

和

分別為它們的二元運(yùn)算，在集合A

B上定義新的二元運(yùn)算?，

<a1,b1>,<a2,b2>

A

B，有<a1,b1>?<a2,b2>=<a1

a2,b1

b2>稱(chēng)G=<A

B,?>為G1與G2的直積，記作G1

G2.例4

G1,G2分別為模2加和模3加群，它們的直積運(yùn)算26

<0,0><0,1><1,0><1,1><2,0><2,1><0,0><0,1><1,0><1,1><2,0><2,1><0,0><0,1><1,0><1,1><2,0><2,1><0,1><0,0><1,1><1,0><2,1><2,0><1,0><1,1><2,0><2,1><0,0><0,1><1,1><1,0><2,1><2,0><0,1><0,0><2,0><2,1><0,0><0,1><1,0><1,1><2,1><2,0><0,1><0,0><1,1><1,0>27環(huán)與域

定義10.15

設(shè)<R,+,·>是代數(shù)系統(tǒng)，+和·是二元運(yùn)算.如果滿(mǎn)足以下條件:(1)<R,+>構(gòu)成交換群(2)<R,·>構(gòu)成半群(3)·運(yùn)算關(guān)于+運(yùn)算適合分配律則稱(chēng)<R,+,·>是一個(gè)環(huán).通常稱(chēng)+運(yùn)算為環(huán)中的加法，·運(yùn)算為環(huán)中的乘法.定義14.16

設(shè)<R,+,·>是環(huán)，若(1)環(huán)中乘法可交換；(2)R中至少含有兩個(gè)元素.且

a∈R

{0}，都有a－1∈R；則稱(chēng)R是域.0指加法單位元，a－1指a的乘法逆元28環(huán)與域的實(shí)例例5(1)整數(shù)集、有理數(shù)集、實(shí)數(shù)集和復(fù)數(shù)集關(guān)于普通的加法和乘法構(gòu)成環(huán)，分別稱(chēng)為整數(shù)環(huán)Z，有理數(shù)環(huán)Q，實(shí)數(shù)環(huán)R

和復(fù)數(shù)環(huán)C.Q、R和C也稱(chēng)為有理數(shù)域、實(shí)數(shù)域、復(fù)數(shù)

域.(2)n(n≥2)階實(shí)矩陣的集合Mn(R)關(guān)于矩陣的加法和乘法構(gòu)成環(huán)，稱(chēng)為n階實(shí)矩陣環(huán).(3)集合的冪集P(B)關(guān)于集合的對(duì)稱(chēng)差運(yùn)算和交運(yùn)算構(gòu)成環(huán).(4)設(shè)Zn＝{0,1,...,n－1}，

和

分別表示模n的加法和乘法，則<Zn,

,

>構(gòu)成環(huán)，稱(chēng)為模n的整數(shù)環(huán).當(dāng)n為素?cái)?shù)

時(shí)Zn構(gòu)成域.29格的定義與性質(zhì)

定義14.17

設(shè)<S,?>是偏序集，如果

x,y

S，{x,y}都有最小上界和最大下界，則稱(chēng)S關(guān)于偏序?作成一個(gè)格.求{x,y}最小上界和最大下界看成x與y的二元運(yùn)算∨和∧，例6

設(shè)n是正整數(shù)，Sn是n的正因子的集合.D為整除關(guān)系，則偏序集<Sn,D>構(gòu)成格.

x,y∈Sn，x∨y是lcm(x,y)，即x與y的最小公倍數(shù).x∧y是gcd(x,y)，即x與y的最大公約數(shù).30圖2例7

判斷下列偏序集是否構(gòu)成格，并說(shuō)明理由.

(1)<P(B),

>，其中P(B)是集合B的冪集.

(2)<Z,≤>，其中Z是整數(shù)集，≤為小于或等于關(guān)系.

(3)偏序集的哈斯圖分別在下圖給出.實(shí)例

(1)冪集格.

x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y.(2)是格.x,y∈Z，x∨y=max(x,y)，x∧y=min(x,y)，(3)都不是格.可以找到兩個(gè)結(jié)點(diǎn)缺少最大下界或最小上界31格的性質(zhì)：算律設(shè)<L,?>是格,則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即(1)

a,b∈L

有

a∨b=b∨a,a∧b=b∧a(2)

a,b,c∈L

有

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

a∈L

有

a∨a=a,a∧a=a(4)

a,b∈L

有

a∨(a∧b)=a,a∧(a∨b)=a

32格作為代數(shù)系統(tǒng)的定義設(shè)<S,?,?>是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng),若對(duì)于?和?運(yùn)算適合交換律、結(jié)合律、吸收律,則可以適當(dāng)定義S中的偏序?,使得<S,?>構(gòu)成格,且

a,b∈S有

a∧b=a?b,a∨b