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

第6章代數(shù)系統(tǒng)6.1代數(shù)系統(tǒng)的基本概念6.2二元運(yùn)算的性質(zhì)6.3子代數(shù)和積代數(shù)返回總目錄6.1代數(shù)系統(tǒng)的基本概念6.1.1運(yùn)算

1.運(yùn)算的定義定義6.1.1設(shè)A是非空集合，從笛卡爾積A×A×…×A到A的映射f稱為集合A上的n元運(yùn)算。簡稱為n元運(yùn)算。在定義6.1.1中，當(dāng)n=1時(shí)，f稱為集合A上的一元運(yùn)算；當(dāng)n=2時(shí)，f稱為集合A上的二元運(yùn)算。在討論抽象運(yùn)算時(shí)，“運(yùn)算”常記為“*”、“°”等。設(shè)*是二元運(yùn)算，如果a與b運(yùn)算得到c，記作a*b=c；若*是一元運(yùn)算，a的運(yùn)算結(jié)果記作*a或*(a)。第6章

代數(shù)系統(tǒng)設(shè)A=

1,a,

，其中，a是非零實(shí)數(shù)。f：A→A，定義為：

a

A，f(a)=

。容易看出f是A上的一元運(yùn)算。又如，f：N×N→N，定義為：

m,n

N，f(m,n)=m＋n，f是自然數(shù)集合N上的二元運(yùn)算，它就是普通加法運(yùn)算。普通減法不是自然數(shù)集合N上的二元運(yùn)算，因?yàn)閮蓚€(gè)自然數(shù)相減可能得到負(fù)數(shù)，而負(fù)數(shù)不是自然數(shù)。所以普通的減法不是自然數(shù)集合N上的二元運(yùn)算。通過以上討論可以看出，一個(gè)運(yùn)算是否為集合A上的運(yùn)算必須滿足以下兩點(diǎn)：①A中任何元素都可以進(jìn)行這種運(yùn)算，且運(yùn)算的結(jié)果是惟一的。②A中任何元素的運(yùn)算結(jié)果都屬于A。A中任何元素的運(yùn)算結(jié)果都屬于A通常稱為運(yùn)算在A是封閉的?！纠?.1】設(shè)N為自然數(shù)集合，*和°是N×N到N映射，規(guī)定為：

m,n

N，m?n=min

m,n

m°n=max

m,n

則?和°是N上的二元運(yùn)算?！纠?.2】設(shè)Nk=

0,1,…,k-1

。Nk上的二元運(yùn)算+k定義為：對于Nk中的任意兩個(gè)元素i和j，有稱二元運(yùn)算+k為模k加法。稱二元運(yùn)算×k為模k的乘法。模k加法+k和模k乘法×k是兩種重要的二元運(yùn)算。在N7=

0,1,2,3,4,5,6

中，有4+72=6，4+75=2。如果把N7中的元素：0，1，2，3，4，5，6分別看作是：星期日、星期一、星期二、星期三、星期四、星期五、星期六。那么4+72=6可解釋為：星期四再過兩天后是星期六；4+75=2可解釋為：星期四再過五天后是星期二。這是模7加法實(shí)際意義的一種解釋。

Nk上的二元運(yùn)算×k定義為：對于Nk中的任意兩個(gè)元素i和j，有

2.運(yùn)算的表示表示運(yùn)算的方法通常有兩種：解析公式和運(yùn)算表。解析公式是指用運(yùn)算符號和運(yùn)算對象組成的表達(dá)式。如

f(a)=，

運(yùn)算表是指運(yùn)算對象和運(yùn)算結(jié)果構(gòu)成的二維表。經(jīng)常使用運(yùn)算表來定義有限集合上的二元運(yùn)算，特別當(dāng)有限集合上的二元運(yùn)算不能用表達(dá)式簡明地表示時(shí)，借助于運(yùn)算表來定義二元運(yùn)算會帶來方便。另外，運(yùn)算表還便于對二元運(yùn)算的某些性質(zhì)進(jìn)行討論，更形象地了解二元運(yùn)算的有關(guān)特征。設(shè)N4=

0,1,2,3

，N4上的模4加法＋4可以用運(yùn)算表表示，它的運(yùn)算表如表6.1所示。N4上的模4乘法×4也可以用運(yùn)算表表示，它的運(yùn)算表如表6.2所示。表6.1+4012300123112302230133012表6.2×40123000001012320202303216.1.2代數(shù)系統(tǒng)定義6.1.2一個(gè)非空集合A連同若干個(gè)定義在該集合上的運(yùn)算?1,?2,…,?k所組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)，記作<A,?1,?2,…,?k>。

根據(jù)定義6.1.2，一個(gè)代數(shù)系統(tǒng)需要滿足下面兩個(gè)條件：①有一個(gè)非空集合A。②有一些定義在集合A上的運(yùn)算。集合和定義在集合A上的運(yùn)算是一個(gè)代數(shù)系統(tǒng)的兩個(gè)要素，缺一不可。【例6.3】設(shè)B是一個(gè)集合，A=P

(B)是A冪集合。集合的求補(bǔ)運(yùn)算是A上的一元運(yùn)算，集合的并和交運(yùn)算是A上的是二元運(yùn)算。于是<A,∪,∩,~>構(gòu)成一個(gè)代數(shù)系統(tǒng)，該代數(shù)系常稱為集合代數(shù)?！纠?.4】設(shè)R-

0

是全體非零實(shí)數(shù)集合，*是R-

0

上二元運(yùn)算，定義為：

a,b

R-

0

，a*b=b。則<R-

0

,*>是代數(shù)系統(tǒng)。6.2二元運(yùn)算的性質(zhì)6.2.1運(yùn)算的基本性質(zhì)

1.交換律定義6.2.1設(shè)*是非空集合A上的二元運(yùn)算，如果對于任意的a,b

A，有a?b=b?a，則稱二元運(yùn)算?在A上是可交換的，也稱二元運(yùn)算*在A上滿足交換律。例如，設(shè)R為實(shí)數(shù)集合，對于任意的a,b

R，規(guī)定

a?b=(a–b)2a°b=a2+b2a?b=a+b–ab則運(yùn)算?、°和?都是可交換的。

2.結(jié)合律定義6.2.2設(shè)*是非空集合A上的二元運(yùn)算，如果對于任意的a,b,c

A，有(a*b)*c=a*(b*c)，則稱二元運(yùn)算*在A上是可結(jié)合的，也稱二元運(yùn)算?在A上滿足結(jié)合律返回章目錄實(shí)數(shù)集合上的普通加法和乘法是二元運(yùn)算，滿足結(jié)合律；矩陣的加法和乘法也是二元運(yùn)算，也滿足結(jié)合律；向量的內(nèi)積、外積是二元運(yùn)算，但不滿足結(jié)合律?！纠?.5】設(shè)*是非空集合A上的二元運(yùn)算，定義為：

a,b

A，a?b=b。證明運(yùn)算*是可結(jié)合的。證明：對于任意的a,b,c

A，

有(a?b)?c=c，而a?(b?c)=a?c=c，故有(a?b)?c=a?(b?c)，即運(yùn)算?是可結(jié)合的。當(dāng)二元運(yùn)算*在A上適合結(jié)合律時(shí)，在只有該運(yùn)算符的表達(dá)式中，表示運(yùn)算順序的括號常被省略。所以將(x*y)*z=x*(y*z)常寫成x*y*z。這樣，可以令

當(dāng)運(yùn)算*滿足結(jié)合律時(shí)，an的也可以遞歸定義如下：⑴a1=a⑵an+1=an?a

由此利用數(shù)學(xué)歸納法，不難證明下列的公式：⑴am?an=am+n⑵(am)n=amn

3.分配律定義6.2.3設(shè)*和是非空集合A上的兩個(gè)二元運(yùn)算，如果對于任意a,b,c

A，有a*(b°c)=(a*b)°(a*c)(左分配律)(b°c)*a=(b*a)°(c*a)(右分配律)則稱運(yùn)算*對運(yùn)算是可分配的。也稱運(yùn)算*對運(yùn)算滿足分配律。【例6.6】設(shè)A=

0,1

，*和°都是A上的二元運(yùn)算，定義為：0?0=1*1=0，0*1=1*0=10°0=0°1=1°0=0，1°1=1則容易驗(yàn)證°對于運(yùn)算*是可分配的，但*對于運(yùn)算°是不可分配的。如1*(0°1)=1≠0=(1*0)°(1*1)定理6.2.1設(shè)*和°是非空集合A上的兩個(gè)二元運(yùn)算，*是可交換的。如果*對于運(yùn)算°滿足左分配律或右分配律，則運(yùn)算*對于運(yùn)算°是可分配的。證明：設(shè)*對于運(yùn)算°滿足左分配律，且?是可交換的，則對于任意a,b,c

A，有(b°c)?a=a?(b°c)=(a?b)°(a?c)=(b?a)°(c?a)即(b°c)?a=(b?a)°(c?a)故?對于運(yùn)算°是可分配的。同理可證另一半。4.吸收律定義6.2.4設(shè)*和°是非空集合A上的兩個(gè)可交換的二元運(yùn)算，如果對于任意a,b

A，有a*(a°b)=aa°(a*b)=a則稱運(yùn)算?和運(yùn)算°滿足吸收律。【例6.7】設(shè)N為自然數(shù)集合，*和°是集合N上的二元運(yùn)算，定義為：

a

N，

b

N

a*b=max(a,b)，a°b=min(a,b)驗(yàn)證運(yùn)算*和°適合吸收律。解：

a

N，

b

N若a＞b，a*(a°b)=a*min(a,b)=a*b=max(a,b)=a若a＜b，a*(a°b)=a*min(a,b)=a*a=max(a,a)=a若a＝b，a*(a°b)=a*min(a,b)=a*a=max(a,a)=a即a*(a°b)=a同理可證a°(a*b)=a

因此運(yùn)算*和°適合吸收律。

5.冪等律定義6.2.5設(shè)*是非空集合A上的二元運(yùn)算，如果對于任意的a

A，有a?a=a，則稱運(yùn)算*是冪等的或運(yùn)算?滿足冪等律。如果A的某個(gè)元素a滿足a?a=a，則稱a為運(yùn)算*的冪等元。易見，集合的并、交運(yùn)算滿足冪等律，每一個(gè)集合都是冪等元。由定義6.2.5不難證明下面定理。

定理6.2.2設(shè)?是非空集合A上的二元運(yùn)算，a為運(yùn)算?的冪等元，對任意的正整數(shù)n，則an=a。6.2.2特殊元素1.幺元定義6.2.6設(shè)?是定義在集合A上的二元運(yùn)算，如果有一個(gè)el

A，對于任意的a

A，有el?

a=a，則稱el為A中關(guān)于運(yùn)算?的左單位元或左幺元；如果有一個(gè)er

A，對于任意的a

A，有a?

er=a，則稱er為A中關(guān)于運(yùn)算?的右單位元或右幺元；如果在A中有一個(gè)元素，它既是左單位元又是右單位元，則稱為A中關(guān)于運(yùn)算?的單位元或幺元。

定理6.2.3設(shè)?是定義在集合A上的二元運(yùn)算，el為A中關(guān)于運(yùn)算?的左幺元，er為A中關(guān)于運(yùn)算?的右幺元，則el=er=e，且A中的幺元是惟一的。證明：因?yàn)閑l和er分別是A中關(guān)于運(yùn)算?的左幺元和右幺元，所以el=el?

er=er=e設(shè)另一幺元e1

A，則e1=e1?

e=e2.零元定義6.2.7設(shè)?是集合A上的二元運(yùn)算，如果有一個(gè)θl

A，對于任意的a

A都有θl?

a=θl，則稱θl為A中關(guān)于運(yùn)算?的左零元；如果有一個(gè)θr

A，對于任意的a

A，都有a?θr=θr，則稱θr為A中關(guān)于運(yùn)算?的右零元；如果A中有一個(gè)元素θ

A，它既是左零元又是右零元，則稱θ為A中關(guān)于運(yùn)算?的零元。

定理6.2.4設(shè)?是集合A上的二元運(yùn)算，θl為A中關(guān)于運(yùn)算?的左零元，θr為A中關(guān)于運(yùn)算?的右零元，則θl=θr=θ，且A中的零元是惟一的。證明：因?yàn)棣萳和θr分別是A中關(guān)于運(yùn)算?的左零元和右零元，所以θl=θl?θr=θr=θ設(shè)另一零元θ1

A，則θ1=θ1?

θ=θ

定理6.2.5設(shè)?是集合A上的二元運(yùn)算，集合A中元素的個(gè)數(shù)大于1。如果A中存在幺元e和零元θ，則e≠θ。

證明：用反證法。設(shè)e=θ，那么對于任意的a

A，必有

a=e?a=θ?a=θ，于是A中的所有元素都是零元

，與A中至少有兩個(gè)元素矛盾。

3.逆元定義6.2.8設(shè)?是集合A上的二元運(yùn)算，e為A中關(guān)于運(yùn)算?的幺元。如果對于A中的元素a存在著A中的某個(gè)元素b，使得b?a=e，那么稱b為a的左逆元；如果存在A中的某個(gè)元素b，使得a?b=e，那么稱b為a的右逆元；如果存在著A中的某個(gè)元素b，它既是a的左逆元又是a的右逆元，那么稱b為a的逆元。a的逆元記為a–1。如果a

A存在逆元a–1

A，那么稱a為可逆元。

一般地說，一個(gè)元素的左逆元不一定等于該元素的右逆元。一個(gè)元素可以有左逆元而沒有右逆元，同樣可以有右逆元而沒有左逆元。甚至一個(gè)元素的左逆元或者右逆元還可以不是惟一的。定理6.2.6設(shè)?為A中的一個(gè)二元運(yùn)算，A中存在幺元e且每個(gè)元素都有左逆元。如果?是可結(jié)合的運(yùn)算，則在A中任何元素的左逆元必定是該元素的右逆元，且每個(gè)元素的逆元是惟一的。證明：設(shè)a,b,c

A，b是a的左逆元，c是b的左逆元。于是(b?a)?b=e?b=b，所以

e=c?b=c?((b?a)?b)=(c?(b?a))?b=((c?b)?a)?b=(e?a)?b=a?b因此，b也是a的右逆元。設(shè)元素a有兩個(gè)逆元b和d，那么b=b?e=b?(a?d)=(b?a)?d=e?d=d故a的逆元是惟一的。4.消去律定義6.2.9設(shè)?是集合A上的二元運(yùn)算，θ為A中關(guān)于運(yùn)算?的零元，

a,b,c

A，a≠θ。如果⑴若a?b=a?c，便有b=c，則稱運(yùn)算?滿足左消去律，稱a為運(yùn)算?的左可消元。⑵若b?a=c?a，便有b=c，則稱運(yùn)算?滿足右消去律，稱a為運(yùn)算?的右可消元。若運(yùn)算?既滿足左消去律又滿足右消去律，則稱運(yùn)算?滿足消去律，稱a為運(yùn)算?的可消元。注意可消元a不能是零元θ。

定理6.2.7設(shè)?是A中可結(jié)合的二元運(yùn)算，如果a的逆存在且a≠θ，則a為關(guān)于?的可消元。證明：設(shè)b,c

A，且有a?b=a?c或b?a=c?a。由于?為可結(jié)合的二元運(yùn)算、a的逆存在且a≠θ，則a–1?(a?b)=(a–1?

a)?

b=e?b=ba–1?(a?c)=(a–1?

a)?

c=e?c=c而

a–1?(a?b)=a–1?(a?c)于是b=c，同理由b?a=c?a，得b=c，故a為關(guān)于?的可消元。【例6.8】實(shí)數(shù)集R上的下列二元運(yùn)算是否滿足結(jié)合律和交換律？⑴a?b=a+b?ab

⑵a°b=(a+b)

解：⑴因?yàn)?/p>

a,b,c

R，有(a?b)?c=(a+b-ab)?c=(a+b-ab)+c-(a+b-ab)c=a+b+c-ab-ac-bc+abc又a?(b?c)=a?(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-ac-bc+abc所以(a?b)?c=a?(b?c)因此運(yùn)算?滿足結(jié)合律。又a?b=a+b?ab=b+a?ba=b?a所以運(yùn)算?滿足交換律。⑵因?yàn)?/p>

a,b,c

R，有(a°b)°c=(a+b)°c=((a+b)+c)=(a+b+2c)a°(b°c)=a°

(b+c)=

(a+(b+c))=

(2a+b+c)在一般情況下(a+b+2c)≠(2a+b+c)所以運(yùn)算°不滿足結(jié)合律。而a°b=

(a+b)=

(b+a)=b°a所以運(yùn)算°滿足交換律?！纠?.9】在例6.8中，運(yùn)算*是否有單位元，零元和冪等元？若有單位元，哪些元素有逆元？

解：運(yùn)算?的定義為：a?b=a+b?ab

⑴若e是單位元，則對任意元素a

R，有a?e=e?a=a，由于元素?是可交換的，僅考慮e?a=a，即e?a=e+a?ea=a，于是e?ea=0，即e(1?a)=0。由于a是任意的，要使上式成立，只有e=0。因此0是運(yùn)算?的單位元。⑵若θ是零元，則對任意元素a

R，有a?θ=θ?a=θ。僅考慮θ?a=θ，即θ?a=θ+a?θa=θ，于是a?aθ=0，即a(1?θ)=0。由于a是任意的，要使上式成立，只有θ=1。因此1是運(yùn)算?的零元。⑶若a

R是冪等元，則應(yīng)有a?a=a，即a+a?a2=a。于是a?aa=0，即a(1?a)=0。要使上式成立，只有a=0或a=1。因此0或1是運(yùn)算?的冪等元。⑷設(shè)b是a的逆元，則應(yīng)有a?b=a+b?ab=0(?的單位元)，于是b=

，因此對于R中的任何元素a(只要a≠1)均有逆元，其逆元是。返回章目錄6.3子代數(shù)和積代數(shù)定義6.3.1如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對應(yīng)運(yùn)算的元數(shù)相同，且代數(shù)常數(shù)的個(gè)數(shù)也相同，則稱這兩個(gè)代數(shù)系統(tǒng)具有相同的構(gòu)成成分，也稱它們是同類型的代數(shù)系統(tǒng)。例如：V1=

R,＋,?,-,0,1

V2=

P(A),∪,∩,~,?,A

V1和V2都含有兩個(gè)二元運(yùn)算、一個(gè)一元運(yùn)算和兩個(gè)代數(shù)常數(shù)，它們是同類型的代數(shù)系統(tǒng)。同類型的代數(shù)系統(tǒng)僅僅是構(gòu)成成分相同，不一定具有相同的運(yùn)算性質(zhì)。

定義6.3.2設(shè)V=<A,?1,?2,…,?k>是代數(shù)系統(tǒng)，B

A。如果?1,?2,…,?k都在B上封閉，B和A含有相同的代數(shù)常數(shù)，則稱代數(shù)系統(tǒng)<A,?1,?2,…,?k>是V的子代數(shù)系統(tǒng)，簡稱子代數(shù)。

例如

I,＋,0

是代數(shù)系統(tǒng)，N

I，加法在N上封閉，0

N，所以

N,＋,0

是

I,＋,0

的子代數(shù)，當(dāng)然

N,＋

也是

I,＋

的子代數(shù)。

N-

0

,＋

是

I,＋

的子代數(shù)，但不是

I,＋,0

的子代數(shù)，因?yàn)?/p>

I,＋,0

中的代數(shù)常數(shù)0

N-

0

?！纠?.10】設(shè)I是整數(shù)集合，＋是普通加法，

I,＋,0

是代數(shù)系統(tǒng)，設(shè)B=

x|x=2n∧n

I

，證明

B,＋,0

是

I,＋,0

的子代數(shù)。證明：任取B的兩個(gè)元素2n1和2n2，n1

I，n2

I。2n1＋2n2=2(n1＋n2)

B

n1＋n2

I所以，加法＋在B上封閉。又0=2×0

B所以

B,＋,0

是

I,＋,0

的子代數(shù)。定義6.3.3設(shè)V1=

A,*

和V2=

B,°

是兩個(gè)代數(shù)系統(tǒng)，其中*和°是二元運(yùn)算。

a1,b1

A×B和

a2,b2

A×B，A×B上的二元運(yùn)算△定義為：

a1,b1

△

a2,b2

=

a1*

a2,b1°b2

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

A×B,△

稱為V1到V2的積代數(shù)或直積，記為V1×V2【例6.11】設(shè)V1=

A,*

和V2=

B,°

是兩個(gè)代數(shù)系統(tǒng)，其中A=

a,b

，A上的二元運(yùn)算*如表6.7所示，B=

x,y,z

，B上的二元運(yùn)算°如表6.8所示。試求V1×V2

表6.7*abaabbba表6.8?xyzxxyzyyyzzzzz解：V1×V2=

A×B,△

，其中

A×B=

a,x

,

a,y

,

a,z

,

b,x

,

b,y

,

b,z

，二元運(yùn)算△如表6.9所示。表6.9△<a,x><a,y><a,z><b,x><b,y><b,z><a,x><a,x><a,y><a,z><b,x><b,y><b,z><a,y><a,y><a,y><a,z><b,y><b,y><b,z><a,z><a,z><a,z><a,z><b,z><b,z><b,z><b,x><b,x><b,y><b,z><a,x><a,y><a,z><b,y><b,y><b,y><b,z><a,y><a,y><a,z><b,z><b,z><b,z><b,z><a,z><a,z><a,z>

定義6.3.4

設(shè)V1=

A,?,°

和V2=

B,?,◎

是兩個(gè)代數(shù)系統(tǒng)，其中?、°、?和◎都是二元運(yùn)算。

a1,b1,

a2,b2

A×B，定義A×B上的二元運(yùn)算△和□為：

a1,b1

△

a2,b2

=

a1*a2,b1?b2

a1,b1□a2,b2=a1°a2,b1◎b2

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

A×B,△,□稱為V1到