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

離散數(shù)學(xué)近世代數(shù)代數(shù)結(jié)構(gòu)第1頁，課件共39頁，創(chuàng)作于2023年2月第四篇代數(shù)系統(tǒng)第2頁，課件共39頁，創(chuàng)作于2023年2月由集合以及集合上的運算組成的數(shù)學(xué)結(jié)構(gòu)稱為代數(shù)結(jié)構(gòu)（也稱為代數(shù)系統(tǒng)）.代數(shù)結(jié)構(gòu)是抽象代數(shù)的一個主要內(nèi)容.研究的中心問題：集合上的抽象運算及運算的性質(zhì)和結(jié)構(gòu)。什么是代數(shù)結(jié)構(gòu)第3頁，課件共39頁，創(chuàng)作于2023年2月研究意義：研究抽象代數(shù)結(jié)構(gòu)的基本特征和基本結(jié)構(gòu)，不僅能深化代數(shù)結(jié)構(gòu)的理論研究，也能擴展其應(yīng)用領(lǐng)域。應(yīng)用：現(xiàn)代數(shù)學(xué)，如拓撲學(xué)、泛函分析，等計算機科學(xué)：如半群自動機、形式語言群糾錯碼的設(shè)計格和布爾代數(shù)計算機硬件設(shè)計、通訊系統(tǒng)設(shè)計其他：代數(shù)方程求解、物理、化學(xué)關(guān)于代數(shù)結(jié)構(gòu)第4頁，課件共39頁，創(chuàng)作于2023年2月主要內(nèi)容第12章代數(shù)結(jié)構(gòu)的概念第13章半群與群第14章環(huán)和域

第15章格與布爾代數(shù)

第5頁，課件共39頁，創(chuàng)作于2023年2月第12章代數(shù)結(jié)構(gòu)的概念

第1節(jié)代數(shù)運算及其性質(zhì)第2節(jié)代數(shù)結(jié)構(gòu)的同態(tài)和同構(gòu)重點：代數(shù)結(jié)構(gòu)的判定與構(gòu)造，代數(shù)結(jié)構(gòu)關(guān)系：同態(tài)、同構(gòu)難點：同態(tài)基本定理第6頁，課件共39頁，創(chuàng)作于2023年2月代數(shù)運算、代數(shù)結(jié)構(gòu)S是非空集合，映射f:SnS稱為S上的n元運算。寫法:f(a,b)=c可改寫為:afb=c例如，在集合R上，對任意兩個數(shù)所進行的普通加法和乘法，都是在集合R上的二元運算。由集合S及S上的封閉運算f1，f2，…，fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記作<S，f1，f2,…，fk>,或（S，f1，f2,…，fk）.第7頁，課件共39頁，創(chuàng)作于2023年2月例1

〈Z;+,＊〉,〈Z;-,＊〉,〈N,-〉,

〈{T,F};┐,∧,∨〉,〈P(A);∪,∩〉是否代數(shù)系統(tǒng)？需要滿足的條件？對于集合A，稱運算f:A

B

是封閉的,如果BA。第8頁，課件共39頁，創(chuàng)作于2023年2月一個代數(shù)系統(tǒng)需要滿足以下三個條件：有一個非空集合S；有一些建立在集合S上的運算；這些運算在S上是封閉的。代數(shù)系統(tǒng)的基本概念第9頁，課件共39頁，創(chuàng)作于2023年2月例在整數(shù)集合I上定義如下： 對任何 其中的+，分別是通常數(shù)的加法和乘法。 那么是一個從I 2

到I的函數(shù)， 易知在集合I上是封閉的，<I，

>是一個代數(shù)系統(tǒng)。第10頁，課件共39頁，創(chuàng)作于2023年2月

如果兩個代數(shù)系統(tǒng)有相同個數(shù)的運算符，每個相對應(yīng)的運算符的元數(shù)是相同的，則稱這兩個代數(shù)系統(tǒng)是同類型的。

定義：兩個代數(shù)系統(tǒng)(U，)與(U，*)，如果滿足下列條件：UU；若aU，bU，則a*b=ab；則稱(U，*)是(U，)的子系統(tǒng)或子代數(shù)。代數(shù)系統(tǒng)的基本概念

第11頁，課件共39頁，創(chuàng)作于2023年2月設(shè)有代數(shù)系統(tǒng)(S，*)，對a，b，cS，如果有(a*b)*c=a*(b*c),則稱此代數(shù)系統(tǒng)的運算滿足結(jié)合律。例：設(shè)A是一個非空集合，★是A上的二元運算，對于任意a，bA，有a★b=b，證明：★是滿足結(jié)合律的。證：∵對于任意的a，b，cA，

(a★b)★c=b★c=c

而a★(b★c)=a★c=c， ∴(a★b)★c=a★(b★c) ∴★是滿足結(jié)合律的.代數(shù)運算及其性質(zhì)

第12頁，課件共39頁，創(chuàng)作于2023年2月交換律設(shè)有代數(shù)系統(tǒng)(S，*)，如果對于a，bS，有a*b=b*a，則稱此代數(shù)系統(tǒng)的運算“*”滿足交換律。例：在整合集合I上定義運算： 對任何 其中的+，分別是通常數(shù)的加法和乘法。 可以滿足交換律嗎？第13頁，課件共39頁，創(chuàng)作于2023年2月分配律(左分配，右分配)設(shè)有代數(shù)系統(tǒng)(S，，*)，對a,b,cS，如果有a(b*c)=(ab)*(ac)，則稱“”運算對“*”運算滿足左分配律。若“*”對“”滿足a*(bc)=(a*b)(a*c)，則稱“*”對“”滿足左分配律若有(a*b)c=(a*c)(b*c)，則稱“”對“*”滿足右分配律。若(ab)*c=(a*c)(b*c)，則稱“*”運算對“”運算滿足右分配律。例：代數(shù)系統(tǒng)(N，+，×)。其中+，×分別代表通常數(shù)的加法和乘法。

是否滿足交換律？第14頁，課件共39頁，創(chuàng)作于2023年2月單位元(幺元)一個代數(shù)系統(tǒng)(S，*)，若存在一個元素eU，使得對xS，有：e*x=x*e=x，則稱e為對于運算“*”的單位元,也稱幺元。注意：單位元是跟運算有關(guān)系的，不同的運算可能單位元是不一樣的。第15頁，課件共39頁，創(chuàng)作于2023年2月左單位元或右單位元(左幺元或右幺元)一個代數(shù)系統(tǒng)(S，)，若存在一個元素elS，使得對xS，有：elx=x，則稱el為對于運算“”的左幺元。若存在一個元素erS，使得對xS，有：xer=x，則稱er為對于運算“”的右幺元。第16頁，課件共39頁，創(chuàng)作于2023年2月 例設(shè)代數(shù)系統(tǒng)(N，*)，*的定義為： 對 那么，(N，*)有沒有單位元？左幺元？右幺元？解：對任何因此1是右幺元。但1不是左幺元，因為所以(N，*)沒有左幺元，當(dāng)然也就沒有幺元。第17頁，課件共39頁，創(chuàng)作于2023年2月定理代數(shù)系統(tǒng)(U,)的單位元若存在，則唯一。證：設(shè)e為運算“”的幺元，另有一單位元e，∵e是幺元，∴對xU，有ex=x，取x=e

，則ee=e

①又∵e是幺元，∴對xU，有xe=x，取x=e，則ee=e ②由①②式可得：e=e，即幺元唯一。第18頁，課件共39頁，創(chuàng)作于2023年2月零元代數(shù)系統(tǒng)(S，)，如果存在一個元素θS，使得對xS有：θx=xθ=θ，則稱θ為對于運算“”的零元。若只滿足θx=θ，則θ稱為左零元。若只滿足xθ=θ，則θ稱為右零元。例:

代數(shù)系統(tǒng)(I，×)的零元是什么？在所有n階方陣集合M上的代數(shù)系統(tǒng)(M，×)，零元是什么？在I+上定義一個二元運算取極小“Min”，(I+，Min)的零元是什么？第19頁，課件共39頁，創(chuàng)作于2023年2月性質(zhì)、定理定理一個代數(shù)系統(tǒng)，其零元若存在，則唯一。定理一個代數(shù)系統(tǒng)(S，)，若集合A中元素的個數(shù)大于1，且該代數(shù)系統(tǒng)存在幺元e和零元θ，則θe。證明：用反證法，設(shè)θ=e，則對于任意的xA，必有

x=ex=θx=θ=e，即對于A中所有元素都是相同的，這與A中含有多個元素相矛盾。第20頁，課件共39頁，創(chuàng)作于2023年2月逆元一個存在幺元e的代數(shù)系統(tǒng)(U，)，如果對U中的元素x存在x-1，使得x-1x=xx-1=e，則稱x-1為x的逆元。若xx-1=e，則稱x-1為x的右逆元。若x-1x=e，則稱x-1為x的左逆元。既是左逆元，又是右逆元，則稱x-1為x的一個逆元。第21頁，課件共39頁，創(chuàng)作于2023年2月例子對代數(shù)系統(tǒng)(R，*)，*為二元運算，定義為通常數(shù)的乘法。R為實數(shù)集合。

aR，a0，a的逆元是什么?對代數(shù)系統(tǒng)(I，*)，*為二元運算，定義為通常數(shù)的乘法。I為整數(shù)集合。 哪些元素有逆元？(R{1}，*)，*為二元運算，定義為通常數(shù)的乘法。R{1}為除了1之外的實數(shù)集合。 哪些元素有逆元？第22頁，課件共39頁，創(chuàng)作于2023年2月注意因此，關(guān)于逆元，下述結(jié)論是正確的：當(dāng)幺元存在時，才考慮逆元。逆元是針對具體元素而定的，有些元素可能有逆元，有些元素則可能沒有逆元。如果a和b都有逆元且ab，則a-1

和b-1也不相同。一個元素的逆元必須是代數(shù)系統(tǒng)內(nèi)的元素。設(shè)e幺元，只有當(dāng)aob=e和boa=e同時成立時，b才能是a的逆元，如果只有一個成立，b也不是a的逆元。第23頁，課件共39頁，創(chuàng)作于2023年2月定理：設(shè)代數(shù)系統(tǒng)(U，)，運算“”滿足結(jié)合律，且存在幺元e，那么對任意固定的xU，若x有逆元，則逆元是唯一的。證明：設(shè)x有兩個逆元x1-1和x2-1

，則x1-1xx2-1=x1-1(xx2-1)=x1-1e=x1-1同理x1-1xx2-1=(x1-1x)x2-1=ex2-1=x2-1所以：x1-1=x2-1第24頁，課件共39頁，創(chuàng)作于2023年2月設(shè)*是定義在集合A上的一個二元運算，如果對于任意的xA，都有x*x=x，則稱*運算是等冪的。例:S={1,2,4}，在集合p(S)定義兩個二元運算，∩，∪，分別表示集合的“并”運算和集合的“交”運算，∩，∪是等冪的？解：對于任意的Ap(S)，有A∩A=A；A∪A=A因此運算∩，∪都滿足等冪律。等冪律第25頁，課件共39頁，創(chuàng)作于2023年2月

設(shè)集合S={α，β，γ，δ，ζ}，定義在S上的一個二元運算如下表所示，試指出代數(shù)系統(tǒng)(S，)中各個元素的左、右逆元情況。解：是幺元，是的左逆元，是的右逆元；是、的左逆元，、是右逆元；是的左逆元,是的右逆元；是的左逆元,是的右逆元。例題第26頁，課件共39頁，創(chuàng)作于2023年2月有限集合上運算的性質(zhì)*是封閉的表上每個元素都屬于S。*滿足交換律表中元素關(guān)于主對角線對稱。元素x為左零元x對應(yīng)的行中每個元素都是x。元素x為右零元x對應(yīng)的列中每個元素都是x。元素x為零元x對應(yīng)的行中每個元素都是x且x對應(yīng)的列中每個元素都是x。元素x為左單位元x對應(yīng)的行與表頭的行完全相同。元素x為右單位元x對應(yīng)的列與表頭的列完全相同。元素x為單位元x對應(yīng)的行與表頭的行完全相同且x對應(yīng)的列與表頭的列完全相同。元素x為左逆元x對應(yīng)的行中至少有一個單位元。元素x為右逆元x對應(yīng)的列中至少有一個單位元。元素x與元素y互為逆元x所在行與y所在列交叉位置元素為單位元且x所在列與y所在行交叉位置元素為單位元。*第27頁，課件共39頁，創(chuàng)作于2023年2月代數(shù)結(jié)構(gòu)之間的關(guān)系為什么需要研究代數(shù)結(jié)構(gòu)之間的關(guān)系？

在研究代數(shù)結(jié)構(gòu)的過程中，所關(guān)心的常常是代數(shù)結(jié)過中運算所滿足的性質(zhì)，不關(guān)心具體的運算，而對于遵循相同運算規(guī)律的系統(tǒng)只需要研究其中一個就可以了解其它的系統(tǒng).

考察下列代數(shù):I,;Q,+;R+,min;P(S),∩;P(S),∪

此5個代數(shù)都有相同的構(gòu)成成分:同樣個數(shù)的運算且對應(yīng)運算元數(shù)相(1個二元運算);滿足同樣的Y運算律(交換律,結(jié)合律);存在單位元。稱具有這些性質(zhì)的代數(shù)是同一類(代數(shù)結(jié)構(gòu)的類)第28頁，課件共39頁，創(chuàng)作于2023年2月設(shè)(U，)和(V，*)是兩個同類型的代數(shù)系統(tǒng),與*都是二元運算,如果存在映射f：UV，使得對x1，x2

U,有f(x1x2)=f(x1)*f(x2)，稱f是一個從(U，)到(V，*)的同態(tài)映射，或說(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)第29頁，課件共39頁，創(chuàng)作于2023年2月例解：作映射f：IA，abcaabcbbabcacb是偶數(shù)是奇數(shù)1.設(shè)集合A={a，b，c}，在A上定義運算。如下表，那么，V1=(I，+)，V1=(A，o)，其中I是正整數(shù)集合，+運算是普通的加法。V1和V1是否同態(tài)？2.構(gòu)造<R+,*>與<R,+>之間的同態(tài)映射.(課堂練習(xí))第30頁，課件共39頁，創(chuàng)作于2023年2月例解：作雙射f：A1A2，f(1)=b,f(2)=d,f(3)=c,f(4)=aabcdabbbdbaadbccbcadaacd*123414124242343143341211設(shè)代數(shù)系統(tǒng)V1=(A1，*)，V2=(A2，o)，其中A1={1，2，3，4}，A2={a，b，c，d}，*和o的運算分別如下表，V1和V2是否同構(gòu)？第31頁，課件共39頁，創(chuàng)作于2023年2月例代數(shù)結(jié)構(gòu)〈R+;*〉,〈R;+〉同構(gòu)嗎？

第32頁，課件共39頁，創(chuàng)作于2023年2月證明：<R+,*>與<R,+>同構(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(a*b)=ln（a*b）=lna+lnb=f(a)+f(b)綜上，<R+,*>同構(gòu)于<R,+>第33頁，課件共39頁，創(chuàng)作于2023年2月定理設(shè)代數(shù)系統(tǒng)和其中*,o,*’,o’,都是二元運算，是V1到V2的滿同態(tài)映射，則(1)如果*是可交換的，則*’也是可交換的；(2)如果*是可結(jié)合的，則*’也是可結(jié)合的；(3)如果*對o是可分配的,則*’對o’也是可分配的；(4)若e是*的單位元，則(e)是*’的單位元;(5)若是*的零元，則()是*’的零元;(6)若a關(guān)于運算*可逆，且逆元為b,則(a)關(guān)于運算*’也可逆，逆元為(b)。第34頁，課件共39頁，創(chuàng)作于2023年2月性質(zhì)保持1.對于同構(gòu)：保持結(jié)合律、交換律、分配律；單位元、逆元、零元相應(yīng)存在