離散數(shù)學(xué)-近世代數(shù)-代數(shù)結(jié)構(gòu).ppt

1、離散數(shù)學(xué) Discrete Mathematics,School of Mathematics and Computing Science,第四篇 代數(shù)系統(tǒng),由集合以及集合上的運(yùn)算組成的數(shù)學(xué)結(jié)構(gòu) 稱為代數(shù)結(jié)構(gòu)（也稱為代數(shù)系統(tǒng)）. 代數(shù)結(jié)構(gòu)是抽象代數(shù)的一個(gè)主要內(nèi)容. 研究的中心問(wèn)題： 集合上的抽象運(yùn)算及運(yùn)算的性質(zhì)和結(jié)構(gòu)。,什么是代數(shù)結(jié)構(gòu),研究意義：研究抽象代數(shù)結(jié)構(gòu)的基本特征和基本結(jié)構(gòu)，不僅能深化代數(shù)結(jié)構(gòu)的理論研究，也能擴(kuò)展其應(yīng)用領(lǐng)域。 應(yīng)用： 現(xiàn)代數(shù)學(xué)，如拓?fù)鋵W(xué)、泛函分析，等 計(jì)算機(jī)科學(xué)：如 半群自動(dòng)機(jī)、形式語(yǔ)言 群糾錯(cuò)碼的設(shè)計(jì) 格和布爾代數(shù)計(jì)算機(jī)硬件設(shè)計(jì)、通訊系統(tǒng)設(shè)計(jì) 其他：代數(shù)方程求解、物理

2、、化學(xué),關(guān)于代數(shù)結(jié)構(gòu),主要內(nèi)容,第12章 代數(shù)結(jié)構(gòu)的概念 第13章 半群與群 第14章 環(huán)和域 第15章 格與布爾代數(shù),第12章 代數(shù)結(jié)構(gòu)的概念 第1節(jié) 代數(shù)運(yùn)算及其性質(zhì) 第2節(jié) 代數(shù)結(jié)構(gòu)的同態(tài)和同構(gòu) 重點(diǎn)： 代數(shù)結(jié)構(gòu)的判定與構(gòu)造，代數(shù)結(jié)構(gòu)關(guān)系：同態(tài)、同構(gòu) 難點(diǎn)： 同態(tài)基本定理,代數(shù)運(yùn)算、代數(shù)結(jié)構(gòu),S是非空集合，映射 f: SnS稱為S上的n元運(yùn)算。 寫(xiě)法: f(a,b)=c可改寫(xiě)為: a f b=c 例如，在集合R上，對(duì)任意兩個(gè)數(shù)所進(jìn)行的普通加法和乘法，都是在集合R上的二元運(yùn)算。,由集合S及S上的封閉運(yùn)算f1，f2，fk所組成的系統(tǒng)就稱為一個(gè)代數(shù)系統(tǒng)，記作, 或（S，f1，f2 ,，fk）.

3、,例1Z; +, Z; -, ,N, - , T,F; , P(A); , 是否代數(shù)系統(tǒng)？ 需要滿足的條件？,對(duì)于集合A，稱運(yùn)算f: A B 是封閉的, 如果BA。,一個(gè)代數(shù)系統(tǒng)需要滿足以下三個(gè)條件： 有一個(gè)非空集合S； 有一些建立在集合S上的運(yùn)算； 這些運(yùn)算在S上是封閉的。,代數(shù)系統(tǒng)的基本概念,例,在整數(shù)集合 I 上定義 如下： 對(duì)任何 其中的+， 分別是通常數(shù)的加法和乘法。 那么 是一個(gè)從 I2 到 I 的函數(shù)， 易知 在集合 I 上是封閉的， 是 一個(gè)代數(shù)系統(tǒng)。,如果兩個(gè)代數(shù)系統(tǒng)有相同個(gè)數(shù)的運(yùn)算符，每個(gè)相對(duì)應(yīng)的運(yùn)算符的元數(shù)是相同的，則稱這兩個(gè)代數(shù)系統(tǒng)是同類型的。 定義：兩個(gè)代數(shù)系統(tǒng)(U，

4、)與(U，*) ，如果滿足下列條件： U U； 若a U，bU，則a*b =a b；則稱(U，*)是(U，)的子系統(tǒng)或子代數(shù) 。,代數(shù)系統(tǒng)的基本概念,設(shè)有代數(shù)系統(tǒng)(S，*)，對(duì)a，b，cS，如果有 (a*b)*c= a*(b*c), 則稱此代數(shù)系統(tǒng)的運(yùn)算滿足結(jié)合律。 例：設(shè)A是一個(gè)非空集合， 是A上的二元運(yùn)算，對(duì)于任意a，bA，有ab=b，證明：是滿足結(jié)合律的。 證： 對(duì)于任意的a，b ，c A， (a b)c= b c= c 而a(bc)=a c= c， (ab)c= a(bc) 是滿足結(jié)合律的.,代數(shù)運(yùn)算及其性質(zhì),交換律 設(shè)有代數(shù)系統(tǒng)(S，*)，如果對(duì)于a，b S，有a*b = b*a，則

5、稱此代數(shù)系統(tǒng)的運(yùn)算“ * ”滿足交換律。 例：在整合集合 I 上定義運(yùn)算 ： 對(duì)任何 其中的 +， 分別是通常數(shù)的加法和乘法。 可以滿足交換律嗎？,分配律(左分配，右分配) 設(shè)有代數(shù)系統(tǒng)(S，*)，對(duì)a,b,cS，如果有 a(b*c)=(ab)*(ac)，則稱 “”運(yùn)算對(duì)“*”運(yùn)算滿足左分配律。 若“*”對(duì)“”滿足a*(bc)=(a*b)(a*c)，則稱 “*”對(duì) “”滿足左分配律 若有(a* b)c=(a* c)(b* c)，則稱“” 對(duì)“*” 滿足右分配律。 若(ab)*c=(a* c)(b* c)，則稱“*”運(yùn)算對(duì)“”運(yùn)算滿足右分配律。 例：代數(shù)系統(tǒng)(N，+，)。其中+，分別代表通常數(shù)的

6、加法和乘法。 是否滿足交換律？,單位元( 幺元),一個(gè)代數(shù)系統(tǒng)(S，*)， 若存在一個(gè)元素eU，使得對(duì) xS，有：e * x =x * e = x，則稱 e 為對(duì)于運(yùn)算“ * ”的單位元,也稱幺元 。 注意： 單位元是跟運(yùn)算有關(guān)系的，不同的運(yùn)算可能單位元是不一樣的。,左單位元或右單位元(左幺元或右幺元) 一個(gè)代數(shù)系統(tǒng)(S，)， 若存在一個(gè)元素elS，使得對(duì)xS，有：elx =x，則稱 el 為對(duì)于運(yùn)算“ ”的左幺元 。 若存在一個(gè)元素erS，使得對(duì)xS，有：x er=x，則稱 er為對(duì)于運(yùn)算“ ”的右幺元 。,例 設(shè)代數(shù)系統(tǒng)(N，*)，* 的定義為： 對(duì) 那么，(N，*)有沒(méi)有單位元？左幺元？

7、右幺元？ 解：對(duì)任何 因此 1 是右幺元。 但 1 不是左幺元，因?yàn)?所以(N，*)沒(méi)有左幺元，當(dāng)然也就沒(méi)有幺元。,定理,代數(shù)系統(tǒng)(U,)的單位元若存在，則唯一。 證：設(shè) e 為運(yùn)算“ ”的幺元，另有一單位元 e， e是幺元，對(duì)xU，有ex =x，取x= e ，則e e = e 又 e是幺元，對(duì)xU，有x e =x，取x=e，則e e =e 由 式可得： e =e，即幺元唯一。,零元,代數(shù)系統(tǒng)(S，)，如果存在一個(gè)元素S，使得對(duì)xS有：x =x=，則稱為對(duì)于運(yùn)算“ ” 的零元。 若只滿足x =，則稱為左零元。 若只滿足 x=，則稱為右零元。 例: 代數(shù)系統(tǒng)(I，)的零元是什么？ 在所有n階方陣

8、集合M上的代數(shù)系統(tǒng)(M，)，零元是什么？ 在I+上定義一個(gè)二元運(yùn)算取極小“Min”，( I+，Min)的零元是什么？,性質(zhì)、定理,定理 一個(gè)代數(shù)系統(tǒng)，其零元若存在，則唯一。 定理 一個(gè)代數(shù)系統(tǒng)(S，)，若集合 A 中元素的個(gè)數(shù)大于1，且該代數(shù)系統(tǒng)存在幺元 e 和零元，則e。 證明：用反證法，設(shè)=e，則對(duì)于任意的xA，必有 x = ex = x = e， 即對(duì)于A中所有元素都是相同的，這與A中含有多個(gè)元素相矛盾。,逆元,一個(gè)存在幺元 e 的代數(shù)系統(tǒng)(U，)，如果對(duì) U 中的 元素 x 存在 x-1，使得 x-1 x = x x-1 = e， 則稱x-1為x的逆元。 若 x x-1 = e，則稱

9、x-1 為 x 的右逆元。 若 x-1 x = e，則稱 x-1 為 x 的左逆元。 既是左逆元，又是右逆元，則稱 x-1 為 x 的一個(gè)逆元。,例子,對(duì)代數(shù)系統(tǒng)(R，*)，* 為二元運(yùn)算，定義為通常數(shù)的乘法。R為實(shí)數(shù)集合。 aR，a 0，a 的逆元是什么? 對(duì)代數(shù)系統(tǒng)(I，*)， * 為二元運(yùn)算，定義為通常數(shù)的乘法。I 為整數(shù)集合。 哪些元素有逆元？ (R1，*)， * 為二元運(yùn)算，定義為通常數(shù)的乘法。 R1為除了 1 之外的實(shí)數(shù)集合。 哪些元素有逆元？,注意,因此，關(guān)于逆元，下述結(jié)論是正確的： 當(dāng)幺元存在時(shí)，才考慮逆元。 逆元是針對(duì)具體元素而定的，有些元素可能有逆元，有些元素則可能沒(méi)有逆元

10、。如果 a 和 b 都有逆元且 a b，則 a-1 和 b-1 也不相同。 一個(gè)元素的逆元必須是代數(shù)系統(tǒng)內(nèi)的元素。 設(shè) e 幺元，只有當(dāng) a b = e 和 b a = e 同時(shí)成立時(shí)，b才能是 a 的逆元，如果只有一個(gè)成立，b 也不是 a 的逆元。,定理：設(shè)代數(shù)系統(tǒng)(U，)，運(yùn)算“ ”滿足結(jié)合律，且 存在幺元 e，那么對(duì)任意固定的 xU，若 x 有逆元，則 逆元是唯一的。 證明： 設(shè) x 有兩個(gè)逆元 x1-1和x2-1 ，則 x1-1 x x2-1 = x1-1 (x x2-1 )=x1-1 e=x1-1 同理 x1-1 x x2-1= (x1-1 x) x2-1 =e x2-1 = x2-

11、1 所以：x1-1 = x2-1,設(shè) * 是定義在集合A上的一個(gè)二元運(yùn)算，如果對(duì)于任意的xA，都有x * x = x，則稱 * 運(yùn)算是等冪的。 例: S=1,2,4，在集合 p(S) 定義兩個(gè)二元運(yùn)算，分別表示集合的“并”運(yùn)算和集合的“交”運(yùn)算，是等冪的？ 解：對(duì)于任意的A p(S) ，有AA=A；AA=A 因此運(yùn)算，都滿足等冪律。,等冪律,設(shè)集合S=， ，定義在S上的一個(gè)二元運(yùn)算如下表所示，試指出代數(shù)系統(tǒng)(S，)中各個(gè)元素的左、右逆元情況。,解：是幺元， 是 的左逆元 ， 是 的右逆元 ； 是 、 的左逆元， 、是 右逆元 ； 是 的左逆元 , 是 的右逆元； 是 的左逆元, 是 的右逆元。

12、,例題,有限集合上運(yùn)算的性質(zhì),*是封閉的表上每個(gè)元素都屬于S。 *滿足交換律表中元素關(guān)于主對(duì)角線對(duì)稱。 元素x為左零元x對(duì)應(yīng)的行中每個(gè)元素都是x。 元素x為右零元x對(duì)應(yīng)的列中每個(gè)元素都是x。 元素x為零元x對(duì)應(yīng)的行中每個(gè)元素都是x且x對(duì)應(yīng)的列中每個(gè)元素都是x。 元素x為左單位元x對(duì)應(yīng)的行與表頭的行完全相同。 元素x為右單位元x對(duì)應(yīng)的列與表頭的列完全相同。 元素x為單位元x對(duì)應(yīng)的行與表頭的行完全相同且x對(duì)應(yīng)的列與表頭的列完全相同。 元素x為左逆元x對(duì)應(yīng)的行中至少有一個(gè)單位元。 元素x為右逆元x對(duì)應(yīng)的列中至少有一個(gè)單位元。 元素x與元素y互為逆元x所在行與y所在列交叉位置元素為單位元且x所在列與y

13、所在行交叉位置元素為單位元。,*,代數(shù)結(jié)構(gòu)之間的關(guān)系,為什么需要研究代數(shù)結(jié)構(gòu)之間的關(guān)系？ 在研究代數(shù)結(jié)構(gòu)的過(guò)程中，所關(guān)心的常常是代數(shù)結(jié)過(guò)中運(yùn)算所滿足的性質(zhì)，不關(guān)心具體的運(yùn)算，而對(duì)于遵循相同運(yùn)算規(guī)律的系統(tǒng)只需要研究其中一個(gè)就可以了解其它的系統(tǒng). 考察下列代數(shù): I, ; Q, +; R+, min; P(S), ; P(S), 此5個(gè)代數(shù)都有相同的構(gòu)成成分:同樣個(gè)數(shù)的運(yùn)算 且對(duì)應(yīng)運(yùn)算元數(shù)相(1個(gè)二元運(yùn)算); 滿足同樣的 Y運(yùn)算律(交換律,結(jié)合律);存在單位元。 稱具有這些性質(zhì)的代數(shù)是同一類(代數(shù)結(jié)構(gòu)的類),設(shè)(U，)和(V，*)是兩個(gè)同類型的代數(shù)系統(tǒng), 與 * 都是二元運(yùn)算,如果存在映射f：UV

14、，使得對(duì)x1，x2 U,有f(x1x2)= f(x1)*f(x2)，稱f是一個(gè)從(U，)到(V，*) 的同態(tài)映射，或說(shuō)(U，)與(V，*)是同態(tài)的。 若f是滿射，則稱f是(U，)到(V，*)的滿同態(tài)映射， (U，)與(V，*)是滿同態(tài)。 若f是單射，則稱f是(U，)到(V，*)的單同態(tài)映射， (U，)與(V，*)是單同態(tài)。 若f是雙射，則稱f是(U，)到(V，*)的同構(gòu)映射， (U，)與(V，*)是同構(gòu)的。,同態(tài)與同構(gòu),例,解：作映射 f ：IA，,1. 設(shè)集合A=a，b，c，在A上定義運(yùn)算。如下表，那么， V1=(I，+)， V1=(A，)，其中 I 是正整數(shù)集合，+ 運(yùn)算是普通的加法。V1

15、 和V1是否同態(tài)？,2. 構(gòu)造與之間的同態(tài)映射.(課堂練習(xí)),例,解： 作雙射 f：A1A2，f(1)=b, f(2)=d, f(3)=c, f(4)=a,設(shè)代數(shù)系統(tǒng)V1=(A1，*)，V2=(A2，)， 其中A1=1，2，3，4， A2=a，b，c，d， * 和 的運(yùn)算分別如下表，V1 和 V2 是否同構(gòu)？,例,代數(shù)結(jié)構(gòu)R+; *,R;+同構(gòu)嗎？,證明：與同構(gòu),下面證明二者之間存在雙射關(guān)系且滿足同態(tài)方程。 i)建立雙射關(guān)系： 令f:R+R, f(x)=lnx 顯然，f是單射 yR, x=ey 使y=lney =lnx=f(x) f 是滿射 f是從R+到R的雙射 ii)f 滿足同態(tài)方程： f(

16、a*b)= ln（a*b）=lna+ lnb = f(a) + f(b) 綜上，同構(gòu)于,定理,設(shè)代數(shù)系統(tǒng) 和 其中*, ,*, ,都是二元運(yùn)算，是V1到V2的滿同態(tài)映射，則 (1)如果*是可交換的，則*也是可交換的； (2)如果*是可結(jié)合的，則*也是可結(jié)合的； (3)如果*對(duì)是可分配的,則* 對(duì)也是可分配的； (4) 若e是*的單位元，則(e)是*的單位元; (5)若是*的零元，則()是*的零元; (6)若a關(guān)于運(yùn)算*可逆，且逆元為b,則(a)關(guān)于運(yùn)算*也可逆，逆元為(b)。,性質(zhì)保持 1. 對(duì)于同構(gòu)： 保持結(jié)合律、交換律、分配律；單位元、逆元、零元相應(yīng)存在. 2. 對(duì)于同態(tài) 單向保持性質(zhì),可以證明, 代數(shù)系統(tǒng)間的同構(gòu)關(guān)系是等價(jià)關(guān)系。 自反： 構(gòu)造映射f：U U, 滿足 f(x)=x 對(duì)稱: f是U到V的同構(gòu)映射，則f-1是V到U的同構(gòu)映射。 (U，)，(V，*)，(W，)，如果f是U到V同構(gòu)映射，g是V到W的同構(gòu)映射，則可證 gof 是U到W的 同構(gòu)映射。,代數(shù)系統(tǒng)間同構(gòu)關(guān)系是等價(jià)關(guān)系,同態(tài)核,f是一個(gè)從(U，)到(V，*) 的同態(tài)映射,e是(V，*)的單位元。定義集合 K(f)=x xS且f(x)e為同態(tài)核，記為K(f)。 定理 設(shè)f為代數(shù)