蘇XI友無密碼課件第5章代數(shù)系統(tǒng)的一般性質(zhì).ppt

1、Chap.5 代數(shù)系統(tǒng)的一般性質(zhì),代數(shù)系統(tǒng)又稱近世代數(shù)、抽象代數(shù). 19世紀(jì)的數(shù)學(xué)家認(rèn)識(shí)到, 對(duì)許多不相“聯(lián)系”的代數(shù)抽出它們的共同的內(nèi)容進(jìn)行綜合研究, 可以發(fā)現(xiàn)它們具有統(tǒng)一的形式, 即: (1)它們都是由一些元素或?qū)ο蠼M成的集合; (2)服從一種或幾種運(yùn)算; (3)這些運(yùn)算的特性僅僅由某些抽象的性質(zhì)決定; (4)運(yùn)算的結(jié)果是該集的元素. 因此, 所謂代數(shù)系統(tǒng)就是由集合和定義其上的一個(gè)或多個(gè)運(yùn)算所組成的系統(tǒng), 簡稱為代數(shù).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,1,Chap.5 代數(shù)系統(tǒng)的一般性質(zhì),代數(shù)系統(tǒng)是一種數(shù)學(xué)結(jié)構(gòu), 它由集合、關(guān)系、運(yùn)算、公理、定義、定理和算法所組成. 它是應(yīng)用抽象的方法, 研

2、究我們將要處理的數(shù)學(xué)對(duì)象集合上的關(guān)系或運(yùn)算(運(yùn)算也是一種關(guān)系). 事物間的關(guān)系就是事物的結(jié)構(gòu), 所以代數(shù)系統(tǒng)又稱為代數(shù)結(jié)構(gòu).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,2,Chap.5 代數(shù)系統(tǒng)的一般性質(zhì),近世代數(shù)的應(yīng)用十分廣泛, 它不僅是數(shù)學(xué)專業(yè)的一些分支, 如數(shù)論、范疇論等的基礎(chǔ), 也是其它專業(yè), 如原子物理、系統(tǒng)工程等所必需. 在計(jì)算機(jī)和信息科學(xué)中, 近世代數(shù)是重要的數(shù)學(xué)工具. 如: 描述機(jī)器可計(jì)算的函數(shù)、研究算術(shù)計(jì)算的復(fù)雜性、刻畫抽象的數(shù)據(jù)結(jié)構(gòu)、作為程序設(shè)計(jì)語言的語義學(xué)基礎(chǔ)、邏輯電路設(shè)計(jì)和編碼理論等, 都需要代數(shù)知識(shí). 因此, 代數(shù)的概念和基本方法, 已成為這一領(lǐng)域中科技人員必須掌握的基本工具.,

3、北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,3,Chap.5 代數(shù)系統(tǒng)的一般性質(zhì),1二元運(yùn)算及其性質(zhì) 2代數(shù)系統(tǒng)及其子代數(shù) 3代數(shù)系統(tǒng)的同態(tài)與同構(gòu),北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,4,1 二元運(yùn)算及其性質(zhì),一、二元運(yùn)算的定義 在給出一般的代數(shù)運(yùn)算定義之前, 先看下面兩例： Exp.1 設(shè)Z是整數(shù)集合, 考慮Z中的普通加法運(yùn)算+, 則對(duì)于Z中的任意兩個(gè)數(shù)a和b, 根據(jù)數(shù)的加法運(yùn)算法則, 可得Z中唯一一個(gè)整數(shù)c作為a+b的結(jié)果. 通常記作c=a+b. Exp.2 設(shè)Mn(R)是全體n階實(shí)數(shù)矩陣的集合, 考慮Mn(R)中的普通的矩陣乘法, 則A,BMn(R),根據(jù)乘法運(yùn)算法則, 可得Mn(R)中唯一一個(gè)n階實(shí)矩陣C

4、作為A乘B的結(jié)果. 記作C=AB.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,5,1 二元運(yùn)算及其性質(zhì),Def.1 設(shè)S是一個(gè)非空集合, S2=SS到S的一個(gè)映射(或函數(shù))f:S2S稱為S上的一個(gè)二元代數(shù)運(yùn)算, 簡稱二元運(yùn)算. S到S的映射f:SS稱為集合S上的一元代數(shù)運(yùn)算, 簡稱一元運(yùn)算. 我們可以將一元運(yùn)算、二遠(yuǎn)運(yùn)算的概念推廣到一般的n元運(yùn)算.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,6,1 二元運(yùn)算及其性質(zhì),Def.2 設(shè)S是一個(gè)非空集合, Sn到S的一個(gè)映射(或函數(shù))f:SnS稱為S上的一個(gè)n元代數(shù)運(yùn)算, 簡稱n元運(yùn)算. n稱為運(yùn)算的階或秩, f稱為運(yùn)算符. f為S上的n元運(yùn)算應(yīng)滿足以下兩個(gè)條件: (1)x

5、1,x2,xnS, f(x1,x2,xn)都要有定義,即f是全函數(shù); (2)x1,x2,xnS, 運(yùn)算結(jié)果f(x1,x2,xn)是唯一的, 且都是集合S中的元素, 即S對(duì)于運(yùn)算f是封閉的.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,7,1 二元運(yùn)算及其性質(zhì),Def.3 設(shè)S是一個(gè)非空集合, Sn到S的一個(gè)映射(或函數(shù))f:SnS, 若f(Sn)S, 則稱映射f關(guān)于集合S是封閉的(closed)或稱S對(duì)f是封閉的. n元運(yùn)算的一個(gè)重要特性就是運(yùn)算的封閉性, 即只要f是集合S上的n元運(yùn)算, 則f關(guān)于S是封閉的; 反之, 只要f是關(guān)于S封閉的函數(shù), 則f是S上的n元運(yùn)算. 從本質(zhì)上講, 集合S上的n元運(yùn)算就是從

6、Sn到S的一個(gè)特定函數(shù). 因此, 看一個(gè)函數(shù)是否為n元運(yùn)算只需看它是否是封閉的即可.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,8,1 二元運(yùn)算及其性質(zhì),Exp.3 (1),是N上的二元運(yùn)算, 但,不是. (2),都是Z和R上的二元運(yùn)算, 但不是. (3),都是非零實(shí)數(shù)集R*上的二元運(yùn)算, 而,不是. 因?yàn)閮蓚€(gè)非零實(shí)數(shù)相加或相減可能為0. (4)設(shè)A為任意集合, 則,為P(A)上的二元運(yùn)算. 是P(A)上的一元運(yùn)算. (5), 為命題公式集合上的二元運(yùn)算, 而是該集合上的一元運(yùn)算. (6)矩陣加法和乘法為Mn(R)上的二元運(yùn)算, 但不是全體實(shí)矩陣集合上的二元運(yùn)算. (7)函數(shù)的復(fù)合運(yùn)算為AA上的二元運(yùn)算.

7、 設(shè)B是A上的所有雙射函數(shù)的集合, 則函數(shù)的逆運(yùn)算是B上的一元運(yùn)算.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,9,1 二元運(yùn)算及其性質(zhì),為了與一般的函數(shù)相區(qū)別, 通常用、等表示運(yùn)算的符號(hào), 稱為算符. 設(shè)f:SSS是S上的二元運(yùn)算, 對(duì)任意的 x,yS, 如果x與y的運(yùn)算結(jié)果是z, 即 f(x,y)=z, 利用算符可簡記為 xy=z. 有時(shí)為了方便起見, 在不致引起混淆的情況下, 可將算符省略, 直接記為 xy=z, 讀作“x乘y”.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,10,1 二元運(yùn)算及其性質(zhì),Exp.4 設(shè)R為實(shí)數(shù)集合, 定義R上的二元運(yùn)算: x,yR, 有xy=x. 計(jì)算34, (-5)0.2, 01

8、/2. 解. 34=3, (-5)0.2=-5, 01/2=0. 對(duì)于有限集合上的一元和二元運(yùn)算除了可使用函數(shù)f的表達(dá)式給出以外, 還可以使用運(yùn)算表給出.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,11,1 二元運(yùn)算及其性質(zhì),Exp.5 設(shè)A=1,2, 給出P(A)上的運(yùn)算和的運(yùn)算表. 其中全集為A. 解.P(A)=,1,2,1,2. 和的運(yùn)算表為:,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,12,1 二元運(yùn)算及其性質(zhì),Exp.6 設(shè)S=1,2,3,4, 定義S上的二元運(yùn)算如下: xy=(xy)mod5,x,yS. 求的運(yùn)算表. 解. 運(yùn)算表如下:,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,13,1 二元運(yùn)算及其性質(zhì),二、二元運(yùn)

9、算的性質(zhì)及特殊元素 對(duì)于給定的集合S, S上可以存在許多二元運(yùn)算.但是, 其中只有一小部分具有良好性質(zhì)的才有實(shí)際意義. 下面定義二元運(yùn)算的一些重要的性質(zhì). Def.4 設(shè)是集合S上的二元運(yùn)算, 如果對(duì)于任意的x,yS都有 xy=yx, 則稱運(yùn)算在S上是可交換的(Commutative), 也稱滿足交換律(Commutative Law). 例如, R:,滿足交換律, 但R:是不可交換的. Mn(R):滿足交換律, 但Mn(R):不滿足交換律.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,14,1 二元運(yùn)算及其性質(zhì),Def.5 設(shè)是集合S上的二元運(yùn)算, 如果對(duì)于任意的x,y,zS都有 (xy)z=x(yz),

10、 則稱運(yùn)算在S上是可結(jié)合的(Associative), 也稱滿足結(jié)合律(Associative Law). 例如, R:,滿足結(jié)合律, 但R:和R:不滿足結(jié)合律; Mn(R):,滿足結(jié)合律. P(S):,滿足結(jié)合律, 但P(S):不滿足結(jié)合律. G:,滿足結(jié)合律, 但G:不滿足結(jié)合律.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,15,1 二元運(yùn)算及其性質(zhì),若運(yùn)算在集合S上是可結(jié)合的, 則 (xy)z=x(yz)=xyz. 用歸納法可以證明:若二元運(yùn)算在集合S上是可結(jié)合的, 則對(duì)任意n個(gè)元素x1,x2,xnS, 運(yùn)算也是可結(jié)合的, 此時(shí)可省略括號(hào), 記為 x1x2xn. 又若x1=x2=xn=x, 則x1x

11、2xn=xn, 稱為元素x的n次冪(Power). 易證: m,nN和xS, 有 xmxn=xm+n, (xm)n=xmn.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,16,1 二元運(yùn)算及其性質(zhì),Def.6 設(shè)和是集合S上的兩個(gè)二元運(yùn)算, 如果對(duì)于任意的x,y,zS都有 x(yz)=(xy)(xz), (1) (yz)x=(yx)(zx), (2) 則稱運(yùn)算對(duì)是可分配的(Distributive), 也稱對(duì)滿足分配律(Distributive Law).若上述兩式分別只有(1)或(2)式成立, 這時(shí)我們分別稱對(duì)是左可分配的(Left Distributive)或右可分配的(Right Distributi

12、ve). 例如, R:對(duì)滿足分配律, 但對(duì)不滿足分配律. Mn(R):對(duì)滿足分配律, 但對(duì)不滿足分配律. P(S):和相互可分配, G:和也是相互可分配.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,17,1 二元運(yùn)算及其性質(zhì),Def.7 設(shè)和是集合S上的兩個(gè)可交換的二元運(yùn)算, 如果對(duì)任意的x,yS都有 x(xy)=x, x(xy)=x, 則稱和滿足吸收律(Absorption Law). 例如, P(S):和滿足吸收律. G:和也滿足吸收律. 應(yīng)該指出, 對(duì)于一些運(yùn)算律的驗(yàn)證, 通常是非常困難的, 一般只能對(duì)于具體對(duì)象進(jìn)行驗(yàn)證.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,18,1 二元運(yùn)算及其性質(zhì),下面考慮二元運(yùn)算的

13、特殊元素. Def.8 設(shè)是集合S上的二元運(yùn)算. (1)如果存在元素eS, 使得對(duì)任意xS都有ex=x, 則稱e是S中關(guān)于運(yùn)算的一個(gè)左幺元(Left Identity Element)或左單位元(Left Unit Element); (2)如果存在元素erS, 使得對(duì)任意xS都有xer=x,則稱er是S中關(guān)于運(yùn)算的一個(gè)右幺元(Right Identity Element)或右單位元(Right Unit Element); (3)如果存在元素eS, 使得對(duì)任意xS都有ex=xe=x, 則稱e是S中關(guān)于運(yùn)算的一個(gè)幺元(Identity Element)或單位元(Unit Element).,北

14、京林業(yè)大學(xué)信息學(xué)院 蘇喜友,19,1 二元運(yùn)算及其性質(zhì),例如, N,Z,R:的幺元是0, 的幺元是1. Mn(R):的幺元是0n,的幺元是In. P(S):和的幺元是, 的幺元是S. G:幺元的是0, 的幺元是1. 對(duì)于給定的集合及該集合上的二元運(yùn)算, 有的運(yùn)算存在幺元, 有的運(yùn)算不存在幺元. 例如, R:就不存在幺元.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,20,1 二元運(yùn)算及其性質(zhì),Def.9 設(shè)是集合S上的二元運(yùn)算. (1)如果存在元素S, 使得對(duì)任意xS都有x=, 則稱是S中關(guān)于運(yùn)算的一個(gè)左零元(Left Zero Element); (2)如果存在元素rS, 使得對(duì)任意xS都有xr=r, 則

15、稱r是S中關(guān)于運(yùn)算的一個(gè)右零元(Right Zero Element); (3)如果存在元素S, 使得對(duì)任意xS都有x=x=, 則稱是S中關(guān)于運(yùn)算的一個(gè)零元(Zero Element).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,21,1 二元運(yùn)算及其性質(zhì),例如, N,Z,R:的零元是0, 而沒有零元. Mn(R):的零元是0n, 而沒有零元. P(S):的零元是S, 的零元是. G:的零元是1, 的零元是0. 顯然, 有的二元運(yùn)算存在零元, 有的二元運(yùn)算不存在零元.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,22,1 二元運(yùn)算及其性質(zhì),Def.10 設(shè)是集合S上的二元運(yùn)算, e是S中關(guān)于的幺元, 元素xS, 若存在

16、一元素yS使得 (1)yx=e, 則稱x是左可逆的(Left Invertible),并稱y是x的一個(gè)左逆元(Left Inverse Element),記為x; (2)xy=e, 則稱x是右可逆的(Right Invertible),并稱y是x的一個(gè)右逆元(Right Inverse Element),記為xr ; (3)xy=yx=e, 則稱x是可逆的(Invertible),并稱y是x的一個(gè)逆元(Inverse Element),記為x-1. 由定義, 顯然, x與x-1互為逆元.,-1,-1,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,23,1 二元運(yùn)算及其性質(zhì),例如, N:的幺元e=0, 0-1=

17、0, 其它自然數(shù)都無逆元; 的幺元e=1, 1-1=1, 其它自然數(shù)都無逆元. Z:的幺元e=0, xZ, x-1=-x; 的幺元e=1, 1-1=1, (-1)-1=-1, 其它整 數(shù)都無逆元. R:的幺元e=0, xR, x-1=-x; 的幺元e=1, 0無逆元, xR, x0, x-1=1/x. R*:無幺元, 從而每個(gè)非零實(shí)數(shù)都無逆元; 的幺元e=1, xR*, x-1=1/x.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,24,1 二元運(yùn)算及其性質(zhì),Mn(R): 的幺元e=0n, MMn(R), M-1=-M; 的幺元e=In, MMn(R), 當(dāng)|M|0, M的逆元為M-1. P(S):的幺元e

18、=S, S-1=S, 其它元素都不存在逆元; 的幺元e=,-1=, 其它元素都不存在逆元. 對(duì)于給定集合上的二元運(yùn)算, 逆元和幺元、零元不同. 如果幺元或零元存在, 則幺元或零元一定是唯一的. 而逆元是與集合中的某個(gè)元素有關(guān), 有的元素有逆元,有的元素?zé)o逆元, 不同的元素對(duì)應(yīng)著不同的逆元, 而且一個(gè)元素的逆元也可能不唯一.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,25,1 二元運(yùn)算及其性質(zhì),Exp.7 設(shè)A=a,b,c,d, 在A上定義二元運(yùn)算如右表, 求A中關(guān)于運(yùn)算的幺元及每個(gè)元素的逆元. 解. 由表易知: a是幺元, 因此a-1=a.,b的左逆元為c,d, 右逆元為c, 所以b-1=c. c的左逆元

19、和右逆元均為b,c, 因此, c-1=b, c-1=c. d的右逆元為b, 但無左逆元, 從而d無逆元.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,26,1 二元運(yùn)算及其性質(zhì),Th.1 設(shè)是集合S上的二元運(yùn)算. (1)若S中存在關(guān)于運(yùn)算的左幺元e和右幺元er,則有 e=er=e, 且e是S中關(guān)于運(yùn)算的唯一幺元; (2)若S中存在關(guān)于運(yùn)算的左零元和右零元r,則有 =r=, 且是S中關(guān)于運(yùn)算的唯一零元; (3)若S中存在關(guān)于運(yùn)算的幺元e, 且可結(jié)合, 元素xS存在左逆元x 和右逆元xr , 則有 x =xr =x , 且x 是x的唯一逆元.,-1,-1,-1,-1,-1,-1,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,2

20、7,1 二元運(yùn)算及其性質(zhì),證.(1)因?yàn)閑和er分別是S中關(guān)于運(yùn)算的左幺元 和右幺元, 則 eer=er, eer=e, 所以, e=er. 令e=er=e, 即e是幺元, 又若e也是S中關(guān)于的 幺元, 則 ee=e, ee=e, 所以, e=e, 即e是唯一的.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,28,1 二元運(yùn)算及其性質(zhì),(2)因?yàn)楹蛂分別是S中關(guān)于運(yùn)算的左零元和 右零元, 則 r=r, r=, 所以, =r. 令=r=, 即是零元, 又若也是S中關(guān)于的 零元, 則 =, =, 所以, =, 即是唯一的.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,29,1 二元運(yùn)算及其性質(zhì),(3)因?yàn)閤 和xr 分別是S

21、中元素x關(guān)于運(yùn)算的左 逆元和右逆元, 則 x x=e, xxr =e, 所以, x =x e=x (xxr )=(x x)xr =exr =xr . 令x =xr =x-1,因此x有逆元x-1.又若y也是x的 逆元, 則 xy=yx=e, 所以, y=ye=y(xx-1)=(yx)x-1=ex-1=x-1. 故, x-1是x的唯一逆元.,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,30,1 二元運(yùn)算及其性質(zhì),推論. 設(shè)集合S上的二元運(yùn)算是可結(jié)合的, 且有幺元e存在, 若元素x,yS的逆元分別為x-1和y-1, 則xy存在逆元

22、, 且(xy)-1=y-1x-1. 證.由逆元定義, 有 xx-1=x-1x=e, yy-1=y-1y=e, 則 (xy)(y-1x-1)=x(yy-1)x-1 =xex-1=xx-1=e, (y-1x-1)(xy)=y-1(x-1x)y =y-1ey=y-1y=e. 所以, (xy)-1=y-1x-1.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,31,1 二元運(yùn)算及其性質(zhì),Def.11 設(shè)是定義在集合S上的二元運(yùn)算, 若元素aS, 使得aa=a, 則稱a是S中關(guān)于的一個(gè)冪等元(Idempotent Element), 簡稱a為冪等元. 若S中每一個(gè)元素都是冪等元, 則稱在S中是冪等的(Idempoten

23、t)或稱滿足冪等律(Idempotent Law). 顯然, 幺元和零元都是冪等的. 例如, P(S):和滿足冪等律. G:和滿足冪等律. R:max(x,y)和min(x,y)滿足冪等律. Z+:無冪等元.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,32,1 二元運(yùn)算及其性質(zhì),Exp.8 實(shí)數(shù)集合R上定義二元運(yùn)算為 xy=x+y-xy,x,yR, 討論運(yùn)算是否可交換、可結(jié)合, 并求幺元、零元、 冪等元和所有可逆元素的逆元. 解.對(duì)x,yR, 有 xy=x+y-xy=y+x-yx=yx, 所以可交換. 對(duì)x,y,zR, 有 (xy)z=(x+y-xy)z=x+y-xy+z-(x+y-xy)z =x+y+z

24、-xy-xz-yz+xyz, x(yz)=x(y+z-yz)=x+y+z-yz-x(y+z-yz) =x+y+z-xy-xz-yz+xyz, 所以, 是可結(jié)合的.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,33,1 二元運(yùn)算及其性質(zhì),假設(shè)有幺元e, 則xR, 應(yīng)有 ex=xe=x. 因是可交換的, 只需考慮xe=x即可. 而 xe=x+e-xe=x, 因此, 要使該式對(duì)xR 成立, 必然有e=0, 故0是R中關(guān)于的幺元. 假設(shè)有零元, 則xR, 應(yīng)有 x=x=. 因是可交換的, 只需考慮x=即可. 而 x=x+-x=, 因此, 要使該式對(duì)xR 成立, 必然有=1, 故1是R中關(guān)于的零元.,北京林業(yè)大學(xué)信息

25、學(xué)院 蘇喜友,34,1 二元運(yùn)算及其性質(zhì),假設(shè)xR是關(guān)于的冪等元, 則xx=x, 即 x+x-x2=x, 由此得方程 x2-x=0. 解之得 x=0, x=1. 即0和1是冪等元. 假設(shè)xR有逆元y, 則xy=yx=0, 因可交換, 只需考慮xy=0即可. 而 xy=x+y-xy=0, 由此得 y=x/x-1. 所以, R中每個(gè)不是零元1的元素都有逆元, x-1=x/x-1(x1).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,35,1 二元運(yùn)算及其性質(zhì),Def.12 設(shè)是集合S上的二元運(yùn)算, 元素aS, 使得對(duì)任意的x,yS都有 (1)若ax=ay, 則x=y, (2)若xa=ya, 則x=y, 則稱a在

26、集合S中關(guān)于是可消去的(Cancellative)或 稱a是可消去元(Cancellative Element), 僅滿足(1) 的元素稱為左可消去元(Left Cancellative Element), 僅滿足(2)的元素稱為右可消去元(Right Cancellative Element). 若S中所有元素都是可消去 元, 則稱在S上是可消去的或稱滿足消去律 (Cancellative Law).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,36,1 二元運(yùn)算及其性質(zhì),例如, Z:,滿足消去律. R:,滿足消去律. Z,R:滿足消去律, 但不滿足消去律, 只有0不是可消去元. P(S):不滿足消去律,

27、 S是可消去元; 也不滿足消去律, 是可消去元. Note1 零元不是可消去元; Note2 幺元都是可消去元.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,37,1 二元運(yùn)算及其性質(zhì),Th.2 設(shè)集合S上的二元運(yùn)算是可結(jié)合的. (1)若元素aS是左可逆的, 則a是左可消去的; (2)若元素aS是右可逆的, 則a是右可消去的; (3)若元素aS是可逆的, 則a是可消去的. 證.(1)設(shè)a的左逆元為a , 則a a=e. 對(duì)x,yS, 若 ax=ay, 則 a (ax)=a (ay), 因可結(jié)合, (a a)x=(a a)y, 即 ex=ey, 所以 x=y. (2)與(1)類似可證, (3)由(1)(2)直

28、接可得.,-1,-1,-1,-1,-1,-1,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,38,1 二元運(yùn)算及其性質(zhì),Note Th.2的逆定理是不成立的, 即若一個(gè)元素是左(右)可消去的, 但不一定是左(右)可逆的. 例如, Z+中每個(gè)元素關(guān)于運(yùn)算都是可消去的, 但每個(gè)元素關(guān)于運(yùn)算都不存在逆元,因?yàn)閆+關(guān)于運(yùn)算不存在幺元.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,39,2 代數(shù)系統(tǒng)及其子代數(shù),Def.1 非空集合S和S上的m個(gè)運(yùn)算1,2,m(其中i為ni元運(yùn)算, i=1,2,m)所組成的系統(tǒng)稱為 一個(gè)代數(shù)系統(tǒng)(Algebraic System), 簡稱為代數(shù)(Algebra), 記為S,1,2,m. 當(dāng)S是有限集

29、合時(shí), 該代數(shù)系統(tǒng)稱為有限代數(shù)系統(tǒng), 否則稱為 無限代數(shù)系統(tǒng). 有限代數(shù)系統(tǒng)中集合的元素?cái)?shù) 稱為該有限代數(shù)系統(tǒng)的階.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,40,2 代數(shù)系統(tǒng)及其子代數(shù),例如, N,Z,R,都是代數(shù)系統(tǒng). Mn(R),是代數(shù)系統(tǒng). P(S),是代數(shù)系統(tǒng), 稱為集合代數(shù). G,是代數(shù)系統(tǒng), 稱為命題代數(shù). 在某些代數(shù)系統(tǒng)中對(duì)于給定的二元運(yùn)算存在幺元或零元, 并且它們對(duì)該系統(tǒng)的性質(zhì)起著重要作用, 稱之為該系統(tǒng)的特異元素或代數(shù)常數(shù). 為了強(qiáng)調(diào)這些特異元素的存在, 有時(shí)把它們列到有關(guān)的代數(shù)系統(tǒng)的表達(dá)式中. 例如, P(S),S, G,0,1.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,41,2 代數(shù)系統(tǒng)及

30、其子代數(shù),在P(S),S和G,0,1這兩個(gè)代數(shù)系統(tǒng)中, 雖然它們具有不同的運(yùn)算對(duì)象和運(yùn)算符, 但它們具有相同的形式, 即都是由一個(gè)集合和兩個(gè)定義在該集合上的二元運(yùn)算及一個(gè)一元運(yùn)算所組成, 且具有相同數(shù)目的代數(shù)常數(shù), 這樣的代數(shù)系統(tǒng)我們稱之為同類型的代數(shù)系統(tǒng). Def.2 設(shè)S1,1,2,m,a1,a2,ak和S2,1,m,b1,b2,bk是兩個(gè)代數(shù)系統(tǒng), 若 i和i都是ni元運(yùn)算(i=1,2,m), 則稱這兩個(gè)代數(shù)系統(tǒng)是同類型的.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,42,2 代數(shù)系統(tǒng)及其子代數(shù),具有一個(gè)非空集合和一個(gè)定義在該集合上的二元運(yùn)算構(gòu)成的代數(shù)系統(tǒng)通常稱為二元代數(shù)(Binary Algebr

31、a). Def.3 設(shè)V=S,1,2,m是代數(shù)系統(tǒng), BS且B,如果B對(duì)運(yùn)算1,2,m都是封閉的, 且B和S含有相同的代數(shù)常數(shù), 則稱V=B,1,2,m是 V的子代數(shù)系統(tǒng)(Subalgebraic System), 簡稱為 子代數(shù)(Subalgebra).若BS, 則稱V是V的真子 代數(shù)(Proper Subalgebra). 有時(shí), 為方便起見, 也常說B是V的子代數(shù).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,43,2 代數(shù)系統(tǒng)及其子代數(shù),例如,N,是Z,的子代數(shù),N,和Z,都是R,的子代數(shù), 且都是真子代數(shù). N,0是Z,0的子代數(shù), N,0和 Z,0都是R,0的子代數(shù), 且也都是真子代數(shù). R,是

32、R,的子代數(shù), 但不是R,0的子代數(shù), 因?yàn)镽,沒有代數(shù)常數(shù)0.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,44,2 代數(shù)系統(tǒng)及其子代數(shù),由子代數(shù)的定義不難看出, V的子代數(shù)V與V本身不僅具有相同的代數(shù)運(yùn)算, 并且這些運(yùn)算也具有相同的性質(zhì), 它們是同類型的代數(shù)系統(tǒng). 任何代數(shù)系統(tǒng)其子代數(shù)一定存在, 因?yàn)樗旧砭褪撬淖哟鷶?shù), 但真子代數(shù)不一定存在. 代數(shù)系統(tǒng)V的最大子代數(shù)就是V本身. 設(shè)B表示代數(shù)系統(tǒng)V中所有代數(shù)常數(shù)組成的集合, 且B對(duì)V中所有運(yùn)算都是封閉的, 那么B就構(gòu)成了V的最小子代數(shù). V的最小與最大子代數(shù)稱為V的平凡子代數(shù).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,45,2 代數(shù)系統(tǒng)及其子代數(shù),Exp.1

33、設(shè)V=Z,0,令 nZ=nz|zZ, n為自然數(shù), 則nZ是V的子代數(shù). 證.nz1,nz2nZ, 則 nz1nz2=n(z1z2)nZ, 即nZ對(duì)運(yùn)算是封閉的, 并且0=n0nZ也是 nZ,的幺元. 所以, nZ,0是V的子代數(shù). 當(dāng)n=1時(shí), nZ就是V本身, 是V的最大子代數(shù); 當(dāng)n=0時(shí), 0Z=0, 是V的最小子代數(shù), 而其它 的子代數(shù)都是V的非平凡的真子代數(shù).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,46,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),同態(tài)與同構(gòu)是研究兩個(gè)代數(shù)系統(tǒng)之間關(guān)系的有力工具. 在討論代數(shù)系統(tǒng)時(shí), 我們常常會(huì)發(fā)現(xiàn)有些代數(shù)系統(tǒng)在結(jié)構(gòu)上有某些相似的地方. Exp.1設(shè)A=a,b,是P(A)上的

34、二元運(yùn)算,P(A),是一個(gè)代數(shù)系統(tǒng). 設(shè)B2=00,01,10,11為所有兩位二進(jìn)制數(shù)的集合, 位或是B2上的二元運(yùn)算, 則B2,是一個(gè)代數(shù)系統(tǒng). 它們的運(yùn)算表為:,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,47,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),兩個(gè)運(yùn)算的運(yùn)算表結(jié)構(gòu)非常相似. 兩個(gè)代數(shù)系統(tǒng)除了集合的元素和運(yùn)算符不同外, 它們的數(shù)學(xué)結(jié)構(gòu)完全一樣. :P(A)B2. ()=00, (a)=01, (b)=10, (a,b)=11. 稱這兩個(gè)代數(shù)系統(tǒng)是同構(gòu)的.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,48,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),我們只對(duì)具有一個(gè)二元運(yùn)算的代數(shù)系統(tǒng)給出同態(tài)映射的定義. Def.1 設(shè)V1=S1, V2=S2,

35、是兩個(gè)二元代數(shù)系統(tǒng). 如果存在映射(函數(shù)):S1S2, 滿足對(duì)x,yS1, 有 (xy)=(x)(y), 則稱是V1到V2的同態(tài)映射, 簡稱同態(tài). 稱上式為同態(tài)式. 稱(S1),是V1在下的同態(tài)像.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,49,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),如果同態(tài)映射分別是滿射、單射、雙射時(shí),則分別稱是滿同態(tài)、單同態(tài)、同構(gòu). 如果是V1到V2的滿同態(tài), 記作V1V2; 如果是V1到V2的同構(gòu), 記作V1 V2. 當(dāng)V1=S1,=S2,=V2時(shí), 則稱同態(tài)映射為V1=S1,上的自同態(tài)映射, 簡稱自同態(tài). 當(dāng)分別是滿射、單射、雙射時(shí), 則分別稱是滿自同態(tài)、單自同態(tài)、自同構(gòu).,北京林業(yè)大學(xué)信息

36、學(xué)院 蘇喜友,50,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),Exp.2(1)R, R+,. 令:RR+,xR,(x)=ex, 則x,yR, 有 (xy)=ex+y=exey=(x)(y), 所以是R,到R+,的同態(tài)映射. x,yR, 若xy, 則exey, 即(x)(y), 所以是單射的. yR+, 有x=lnyR, 使得 (x)=(lny)=elny=y, 所以是滿射的. 因此, 是雙射的, 故是R,到R+,的同 構(gòu), 即R, R+,.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,51,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),(2)對(duì)于R,和R, 存在從R,到R,的同態(tài). 令:RR,xR,(x)=ex, 則x,yR, 有 (xy)=

37、ex+y=exey=(x)(y), 所以是R,到R,的同態(tài). x,yR, 若xy, 則exey, 即(x)(y), 所以是R,到R,的單同態(tài). 但對(duì)于任一負(fù)數(shù)y, 在R中不存在x, 使得x=lny, 即不存在xR, 使得(x)=y, 故不是滿同態(tài).,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,52,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),Exp.3 Z,Zn, 其中, Zn=0,1,n-1,為數(shù)的加法, 為模n加法, 即x,yZn, 有 xy=(xy)modn. 令: ZZn,xZ,(x)=(x)modn, 則x,yZ, 有 (xy)=(xy)modn =(x)modn(y)modn)modn, 所以,(xy)=(x)(

38、y)modn =(x)(y). 從而是Z,到Zn,的同態(tài)映射.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,53,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),又xZn, 有xZ, 使得(x)=(x)modn=x, 所以是滿射的. 但存在0,nZ, 使得 (0)=(n)=0Zn, 所以不是單射的. 綜上, 是Z,到Zn,的滿同態(tài), 即 Z,Zn,.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,54,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu),Exp.4 設(shè)Z, 給定aZ, 令a:ZZ,a(x)=ax,xZ. 對(duì)x,yZ, 有 a(xy)=a(xy)=axay=a(x)a(y), 所以, 是Z,上的自同態(tài). 當(dāng)a=0時(shí), 對(duì)xZ, 有0(x)=0, 即0將Z中 所有元素映射到Z,上的幺元0, 稱0為零同 態(tài), 同態(tài)像為0,.,北京林業(yè)大學(xué)信息學(xué)院 蘇喜友,55,3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)