離散數(shù)學(xué)第5章 代數(shù)系統(tǒng)

本文格式為Word版，下載可任意編輯——離散數(shù)學(xué)第5章代數(shù)系統(tǒng)

軟件學(xué)院

第五章代數(shù)系統(tǒng)基礎(chǔ)以前學(xué)過(guò)大量代數(shù)：初等代數(shù)、高等代數(shù)(線性代數(shù))、集合代數(shù)、命題代數(shù)等等它們研究的對(duì)象分別是整數(shù)、有理數(shù)、實(shí)數(shù)、矩陣、集合、命題等等，以及這些對(duì)象上的各種運(yùn)算。我們發(fā)現(xiàn)不同對(duì)象上的運(yùn)算，可能有共同的性質(zhì)。例如，集合代數(shù)與命題代數(shù)，盡管研究的對(duì)象不同，但是它們的性質(zhì)完全一樣，都有對(duì)合律、交換律、結(jié)合律、分派律、吸收律、底-摩根定律、同一律、零律、互補(bǔ)律等。這些促使我們將代數(shù)的研究引導(dǎo)到更高的層次—即拋開(kāi)具體對(duì)象的代數(shù)—抽象代數(shù)—研究代數(shù)的共性。

軟件學(xué)院

代數(shù)系統(tǒng)基礎(chǔ)就專業(yè)知識(shí)而言，計(jì)算機(jī)學(xué)科中要培養(yǎng)學(xué)生三個(gè)能力：理論抽象設(shè)計(jì)理論：就是計(jì)算機(jī)科學(xué)中各種理論課。抽象：要把實(shí)際問(wèn)題抽象成數(shù)學(xué)模型(數(shù)學(xué)系統(tǒng))。設(shè)計(jì)：系統(tǒng)設(shè)計(jì)、程序設(shè)計(jì)。確定數(shù)學(xué)模型，需要了解有哪些代數(shù)結(jié)構(gòu)(系統(tǒng))。

另外，抽象代數(shù)可以培養(yǎng)學(xué)生的抽象規(guī)律思維能力。本章主要探討：代數(shù)結(jié)構(gòu)(系統(tǒng))的概念，運(yùn)算的性質(zhì)、代數(shù)結(jié)構(gòu)(系統(tǒng))的同構(gòu)、半群、獨(dú)異點(diǎn)、群、環(huán)、域等。

軟件學(xué)院

代數(shù)系統(tǒng)基礎(chǔ)代數(shù)系統(tǒng)的定義：X是非空集合，X上的m個(gè)運(yùn)算f1,f2,…fm,構(gòu)成代數(shù)系統(tǒng)U,記作U=X,f1,f2,…fm。定義：假使兩個(gè)代數(shù)系統(tǒng)有一致個(gè)數(shù)的運(yùn)算符，每個(gè)相對(duì)應(yīng)的運(yùn)算符有一致的元數(shù)，則這兩個(gè)代數(shù)系統(tǒng)具有一致的類型。例如：代數(shù)系統(tǒng)(N,+)與代數(shù)系統(tǒng)(I,)是相同類型的，由于它們都有一個(gè)二元運(yùn)算符。而代數(shù)系統(tǒng)(I,+,)和代數(shù)系統(tǒng)(N,+)是不同類型的。

軟件學(xué)院

代數(shù)系統(tǒng)基礎(chǔ)

定義：假使兩個(gè)代數(shù)系統(tǒng)(S,)和(S’,*)若滿足以下條件：

1.S’S2.a∈S’,b∈S’則a*b=ab

則(S’,*)稱為(S,)的子代數(shù)或子系統(tǒng)。

例如(N,+)就是(I,+)的子系統(tǒng)。

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)這一節(jié)是重要的一節(jié)。由于就是根據(jù)運(yùn)算的性質(zhì)將代數(shù)系統(tǒng)分成半群、群、交換群、環(huán)、域、格等，這些性質(zhì)多數(shù)是大家所熟悉的。一.封閉性設(shè)是X上的二元運(yùn)算，假使對(duì)任何x,y∈X,有xy∈X,則稱在X上封閉。

例如：在N上加法+和乘法都封閉，而減法和除法不封閉。但(I,-)是封閉的，(Q,)封閉。從運(yùn)算表可以很簡(jiǎn)單看出運(yùn)算是否封閉。

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)二.交換性設(shè)是X上的二元運(yùn)算，假使對(duì)任何x,y∈X,有xy=yx,則稱是可交換的。

易知:加法、乘法、交、并、對(duì)稱差是可交換。例如(N,+)中’+’是可交換的(N,)中’’可交換的，但減法和除法不可交換(E,∪)和(E,∩)的運(yùn)算

是可交換的

(E,-)集合的差運(yùn)算不可交換

軟件學(xué)院

三.冪等元、冪等性設(shè)是X上的二元運(yùn)算，假使有a∈X,aa=a,則稱a是冪等元，假使對(duì)任何x∈X,都有xx=x,則稱有冪等性。例如(E,∪)的運(yùn)算有冪等性

但是(E,-)的運(yùn)算沒(méi)有冪等性

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)四.單位元

設(shè)是X上的二元運(yùn)算，假使有1L∈X,使對(duì)任何x∈X,有1Lx=x,則稱1L是相對(duì)的左單位元。假使有1R∈X,使得對(duì)任何x∈X,有x1R=x,則稱1R是相對(duì)的右單位元。假使對(duì)任何x∈X,有1x=x1=x,稱1是相對(duì)的單位元。此時(shí)符號(hào)1〞已經(jīng)不是自然數(shù)1的含義。性質(zhì)：假使對(duì)于一種運(yùn)算存在左單位元和右單位元，則1L=1R。

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)五.零元

設(shè)是X上二元運(yùn)算，假使有0L∈X,使得對(duì)任何x∈X,有0Lx=0L,則稱0L是相對(duì)的左零元。假使有0R∈X,使得對(duì)任何x∈X,有x0R=0R,則稱0R是相對(duì)的右零元。假使對(duì)任何x∈X,有0x=x0=0,稱0是相對(duì)的零元。例如：對(duì)乘法,零元是0,對(duì)并運(yùn)算∪,零元是全集E,對(duì)交運(yùn)算∩,零元是Φ

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)六.可結(jié)合性設(shè)是X上的二元運(yùn)算，假使對(duì)任何x,y,z∈X,有(xy)z=x(yz),則稱是可結(jié)合的。可結(jié)合的：數(shù)值的加法、乘法，集合的交、并、對(duì)稱差，關(guān)系的復(fù)合、函數(shù)的復(fù)合。是可結(jié)合的運(yùn)算的，元素x的運(yùn)算，尋常可以寫(xiě)成乘冪的形式。如下：xx=x2x2x=xx2=x3xmxn=xm+n(xm)n=xmn

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)七.逆元

設(shè)是X上有單位元的二元運(yùn)算，x∈X,若xL-1∈X,使得，xL-1x=1,則稱xL-1是x相對(duì)的左逆元。假使有xR-1∈X,使得xxR-1=1,則稱xR-1是x對(duì)的右逆元。若xL-1=xR-1=x-1,有x-1x=xx-1=1,稱x-1是x相對(duì)的逆元。也稱x-1與x互為逆元。如x1∈X,也稱x可逆。例：實(shí)數(shù)集合R上的+和,x∈R對(duì)加+:x-1=-x(1=0)

對(duì)乘:

x-1=1/x(x≠0)

(1=1)

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)任一代數(shù)系統(tǒng)元素的左逆元與右逆元不一定相等。性質(zhì).設(shè)是X上有單位元且可結(jié)合的二元運(yùn)算，假使x∈X,x的左、右逆元都存在，則x的左、右逆元必相等。且x的逆元是唯一的。八.可消去性設(shè)是X上的二元運(yùn)算，a∈X,假使對(duì)任何x,y∈X,有ax=ay或者xa=yax=y.則稱a相對(duì)是可消去的。

如數(shù)的加法、乘法、減法和除法運(yùn)算都是可削去的。

軟件學(xué)院

代數(shù)系統(tǒng)的性質(zhì)

九.分派律設(shè)和都是X上的二元運(yùn)算，若對(duì)任何x,y,z∈X,有

x(yz)=(xy)(xz)或(xy)z=(xz)(yz)則稱對(duì)可分派。例如乘法對(duì)加法可分派。集合的∪與∩相互可分派。

軟件學(xué)院

代數(shù)系統(tǒng)的

性質(zhì)

十.吸收律設(shè)和都是X上的二元運(yùn)算，若對(duì)任何x,y∈X,有

x(xy)=x則與滿足吸收律。

和

x(xy)=x

例如

集合的∪與∩滿足吸收律。

軟件學(xué)院

a)

b)ccab

c)cccc

d)cccc

aaabbcc

bbca

aaabbcc

bbac

aaabaca

bbbb

aaabbcc

bbbc

cccb

a)b)c)d)

交換性冪等元冪等性單位元有零元有可逆元素YaNaNa,b,cYa,cNaca,bNa,b,cYN,左1N,右零NYa,bNaNa

軟件學(xué)院

同態(tài)與同構(gòu)

有些代數(shù)系統(tǒng)表面上看起來(lái)不一致，但是實(shí)際上是‘一致’的，如下兩個(gè)代數(shù)系統(tǒng)：01

001

111

*ab

aab

bbb

細(xì)心觀測(cè)可發(fā)現(xiàn)，兩個(gè)代數(shù)系統(tǒng)中的對(duì)應(yīng)現(xiàn)象類似，若將其次個(gè)代數(shù)系統(tǒng)中元素a,b換成第一個(gè)代數(shù)系統(tǒng)中元素0、1,運(yùn)算表的形式是不改變，為了表示代數(shù)系統(tǒng)之間的這種關(guān)系，我們提出同態(tài)的概念。

軟件學(xué)院

同態(tài)與同構(gòu)設(shè)X,,Y,是兩個(gè)代數(shù)系統(tǒng)，和都是二元運(yùn)算，

假使存在映射f:XY,使得對(duì)任何x1,x2∈X,有f(x1x2)=f(x1)f(x2)此式叫同態(tài)關(guān)系式則稱f是從X,到Y(jié),的同態(tài)映射，簡(jiǎn)稱這兩個(gè)代數(shù)

系統(tǒng)同態(tài)。并稱f(X),為X,的同態(tài)像。假使f是滿射的，稱此同態(tài)f是滿同態(tài)。假使f是單射的，稱此同態(tài)f是單同態(tài)。假使f是雙射的，稱X,與Y,同構(gòu)，記作(X,)≌(Y,)。f是X,到X,的同態(tài)(同構(gòu)),稱之為自同態(tài)(自構(gòu))。

軟件學(xué)院

同態(tài)與同構(gòu)例1.R+,:是正實(shí)數(shù)R+上的乘法;R,+:是實(shí)數(shù)R上的加法+。表面上看這兩個(gè)代數(shù)系統(tǒng)完全不同，實(shí)際它們運(yùn)算的性質(zhì)卻完全一樣，都滿足：可交換、可結(jié)合、有單位元、元素可逆。那如何反映它們的一致性呢？通過(guò)一個(gè)映射f:R+R任何x∈R+,f(x)=lnx(是雙射)任何x,y∈R+,f(xy)=ln(xy)=lnx+lny=f(x)+f(y)

軟件學(xué)院

同構(gòu)與同態(tài)

例2.設(shè)S={4,5,6},在S上的二元運(yùn)算可用下表1定義。又有P上的二元運(yùn)算*,其運(yùn)算組合如表2,這樣所構(gòu)成的兩個(gè)代數(shù)系統(tǒng)(S,)與(P,*)是同構(gòu)的。456444455556456*123112231

11

22

23

軟件學(xué)院

同構(gòu)和同態(tài)

證明：這兩個(gè)代數(shù)系統(tǒng)間存在一個(gè)函數(shù)g:Sg(a)=a-3顯然它是一一對(duì)應(yīng)的，同時(shí)它滿足條件：g(ab)=g(a)*g(b)

P,