離散數學近世代數代數結構

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

第15章格與布爾代數

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

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

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

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

B

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

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

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

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

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

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

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

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

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

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

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

x=ex=θx=θ=e，即對于A中所有元素都是相同的，這與A中含有多個元素相矛盾。第20頁，課件共39頁，創(chuàng)作于2023年2月逆元一個存在幺元e的代數系統(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月例子對代數系統(tǒng)(R，*)，*為二元運算，定義為通常數的乘法。R為實數集合。

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

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

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

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

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

此5個代數都有相同的構成成分:同樣個數的運算且對應運算元數相(1個二元運算);滿足同樣的Y運算律(交換律,結合律);存在單位元。稱具有這些性質的代數是同一類(代數結構的類)第28頁，課件共39頁，創(chuàng)作于2023年2月設(U，)和(V，*)是兩個同類型的代數系統(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，*)的同構映射，(U，)與(V，*)是同構的。同態(tài)與同構第29頁，課件共39頁，創(chuàng)作于2023年2月例解：作映射f：IA，abcaabcbbabcacb是偶數是奇數1.設集合A={a，b，c}，在A上定義運算。如下表，那么，V1=(I，+)，V1=(A，o)，其中I是正整數集合，+運算是普通的加法。V1和V1是否同態(tài)？2.構造<R+,*>與<R,+>之間的同態(tài)映射.(課堂練習)第30頁，課件共39頁，創(chuàng)作于2023年2月例解：作雙射f：A1A2，f(1)=b,f(2)=d,f(3)=c,f(4)=aabcdabbbdbaadbccbcadaacd*123414124242343143341211設代數系統(tǒng)V1=(A1，*)，V2=(A2，o)，其中A1={1，2，3，4}，A2={a，b，c，d}，*和o的運算分別如下表，V1和V2是否同構？第31頁，課件共39頁，創(chuàng)作于2023年2月例代數結構〈R+;*〉,〈R;+〉同構嗎？

第32頁，課件共39頁，創(chuàng)作于2023年2月證明：<R+,*>與<R,+>同構下面證明二者之間存在雙射關系且滿足同態(tài)方程。i)建立雙射關系：令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+,*>同構于<R,+>第33頁，課件共39頁，創(chuàng)作于2023年2月定理設代數系統(tǒng)和其中*,o,*’,o’,都是二元運算，是V1到V2的滿同態(tài)映射，則(1)如果*是可交換的，則*’也是可交換的；(2)如果*是可結合的，則*’也是可結合的；(3)如果*對o是可分配的,則*’對o’也是可分配的；(4)若e是*的單位元，則(e)是*’的單位元;(5)若是*的零元，則()是*’的零元;(6)若a關于運算*可逆，且逆元為b,則(a)關于運算*’也可逆，逆元為(b)。第34頁，課件共39頁，創(chuàng)作于2023年2月性質保持1.對于同構：保持結合律、交換律、分配律；單位元、逆元、零元相應存在