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

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

軟件學院

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

軟件學院

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

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

軟件學院

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

軟件學院

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

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

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

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

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

軟件學院

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

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

軟件學院

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

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

是可交換的

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

軟件學院

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

但是(E,-)的運算沒有冪等性

軟件學院

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

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

軟件學院

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

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

軟件學院

代數(shù)系統(tǒng)的性質六.可結合性設是X上的二元運算，假使對任何x,y,z∈X,有(xy)z=x(yz),則稱是可結合的?？山Y合的：數(shù)值的加法、乘法，集合的交、并、對稱差，關系的復合、函數(shù)的復合。是可結合的運算的，元素x的運算，尋?？梢詫懗沙藘绲男问?。如下：xx=x2x2x=xx2=x3xmxn=xm+n(xm)n=xmn

軟件學院

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

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

對乘:

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

(1=1)

軟件學院

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

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

軟件學院

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

九.分派律設和都是X上的二元運算，若對任何x,y,z∈X,有

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

軟件學院

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

性質

十.吸收律設和都是X上的二元運算，若對任何x,y∈X,有

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

和

x(xy)=x

例如

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

軟件學院

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

軟件學院

同態(tài)與同構

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

001

111

*ab

aab

bbb

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

軟件學院

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

假使存在映射f:XY,使得對任何x1,x2∈X,有f(x1x2)=f(x1)f(x2)此式叫同態(tài)關系式則稱f是從X,到Y,的同態(tài)映射，簡稱這兩個代數(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,同構，記作(X,)≌(Y,)。f是X,到X,的同態(tài)(同構),稱之為自同態(tài)(自構)。

軟件學院

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

軟件學院

同構與同態(tài)

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

11

22

23

軟件學院

同構和同態(tài)

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

P,