離散代數(shù)運算

主要內(nèi)容：代數(shù)運算定義性質(zhì)特殊元1§7.1代數(shù)運算與代數(shù)系統(tǒng)

1.代數(shù)運算定義(1)定義：設(shè)A為非空集合，nI+,f:An→A稱為A上的n元運算，n稱為運算的階。例1：R上的加法+、乘法

運算是R上的二元運算。例2：冪集

(U)上,集合的補是

(U)上的一元運算，交、并是二元運算。例3：字符串的連接運算是字符串集合上的二元運算。

Σ–字母集合，Σ*–由Σ中的字母構(gòu)成的字符串集合，o–字符串的連接運算,o:(Σ*)2→Σ*

例4：設(shè)A={深色，淺色}*深色淺色深色淺色深色深色深色淺色*：A2→A*是A上的二元運算。封閉性性質(zhì)?單位元?零元?逆元?可約?判別2封閉性設(shè)o是A上的n元運算，SA且S，如果a1,…,anS,均有o(a1,…,an)S,則稱S關(guān)于運算o是封閉的。定理7.1.1:設(shè)o是A上的n元運算，C是

(A)的非空子集，若SC,S關(guān)于運算o是封閉的，則∩C關(guān)于運算o也是封閉的。證明：設(shè)a1,…,an

∩C，則SC,有a1,…,anS,

∵S關(guān)于運算o是封閉的,∴o(a1,…,an)S,∴o(a1,…,an)∩C,

故∩C關(guān)于運算o也是封閉的?！?.1代數(shù)運算與代數(shù)系統(tǒng)

2.代數(shù)運算的性質(zhì)(1)3設(shè)*,o是集合A上的二元運算交換律：

a,bA,有a*b=b*a結(jié)合律：

a,b,cA,有(a*b)*c=a*(b*c)常用an表示a*a*…*a,并稱為a的n次冪，n為a的指數(shù)。定理7.1.3若*是集合A上的可結(jié)合的二元運算，則

aA，m,nI,有am*an=am+n;(am)n=amn分配律：*對o既是左可分配，又是右可分配；*對o左可分配:

a,b,cA,有a*(boc)=(a*b)o(a*c)*對o右可分配：

a,b,cA,有(aob)*c=(a*c)o(b*c).分析例1-4§7.1代數(shù)運算與代數(shù)系統(tǒng)

2.代數(shù)運算的性質(zhì)(2)4單位元（幺元）定義：設(shè)*是A上的二元運算，0+a=aa+0=a0+a=a+0=a

①若

elA,使得aA,有el*a=a,則稱el為關(guān)于*的左單位元.②若

erA,使得aA,有a*er=a,則稱er為關(guān)于*的右單位元.③若

eA,使得aA,有e*a=a*e=a,則稱e為關(guān)于*的單位元.例1中：§7.1代數(shù)運算與代數(shù)系統(tǒng)

3.與二元運算相關(guān)的特殊元(1)R關(guān)于+:左單位元、右單位元、單位元均為0。R關(guān)于

:左單位元、右單位元、單位元均為1。例2中：(U)關(guān)于

:左單位元、右單位元、單位元均為

。

(U)關(guān)于

:左單位元、右單位元、單位元均為U。例3中：Σ*關(guān)于o:左單位元、右單位元、單位元均為空串

。例4中：A關(guān)于*:左單位元、右單位元、單位元均為“淺色”。5例5：N上定義*：

a,bN,a*b=bN關(guān)于*的左單位元

右單位元單位元§7.1代數(shù)運算與代數(shù)系統(tǒng)

3.與二元運算相關(guān)的特殊元(2)：每個元素都是左單位元；：無；：無定理7.1.4設(shè)*是A上的二元運算，el和er分別是關(guān)于*的左右單位元，則el=er，且它是關(guān)于*的唯一單位元。證明：el*er=erel=令e=er=el,則e是關(guān)于*的單位元，設(shè)e’也是關(guān)于*的單位元，則e’=e*e’=e,所以，e是關(guān)于*的唯一單位元零元?可約?6R關(guān)于+:左零元、右零元、零元均無。R關(guān)于

:左零元、右零元、零元均為0?！?.1代數(shù)運算與代數(shù)系統(tǒng)

3.與二元運算相關(guān)的特殊元(3)零元：定義：設(shè)*是A上的二元運算，

①若

zlA,使得aA,有zl*a=zl,則稱zl為關(guān)于*的左零元.②若

zrA,使得aA,有a*zr=zr,則稱zr為關(guān)于*的右零元.③若

zA,使得aA,有z*a=a*z=z,則稱z為關(guān)于*的零元.例1中:例2中:(U)關(guān)于

:左零元、右零元、零元均為U。

(U)關(guān)于

:左零元、右零元、零元均為

。例3中:Σ*關(guān)于o:無左零元、右零元和零元。例4中：A關(guān)于*:左零元、右零元、零元均為“深色”例5中：N關(guān)于*:每個元素都是右零元、無左零元和零元。定理7.1.5若關(guān)于*的左右零元都存在，則他們相等，是唯一零元。7逆元：定義：設(shè)*是A上的二元運算，e是關(guān)于*的單位元，aA

①若

alA,使得al*a=e,則稱al為a關(guān)于*的左逆元.②若

arA,使得a*ar=e,則稱ar為a關(guān)于*的右逆元.③若

a’A,使得a’*a=a*a’=e,則稱a’為a關(guān)于*的逆元.例1中：§7.1代數(shù)運算與代數(shù)系統(tǒng)

3.與二元運算相關(guān)的特殊元(4)關(guān)于+:aR的左逆元、右逆元和逆元均為-a。關(guān)于

:aRa0,a的左逆元、右逆元和逆元均為1/a。例2中：關(guān)于

:(A)中，的左逆元、右逆元和逆元均為

。關(guān)于

:(A)中，U左逆元、右逆元和逆元均為U。例3中：關(guān)于o:Σ*中，空串的左逆元、右逆元和逆元均為

。例4中：關(guān)于*:A中，淺色的左逆元、右逆元和逆元均為淺色。8定理7.1.6設(shè)*是A上的可結(jié)合的二元運算，e是關(guān)于*的單位元，

al,ar分別為a關(guān)于*的左右逆元，則al=ar且它是a關(guān)于*的唯一逆元?！?.1代數(shù)運算與代數(shù)系統(tǒng)

3.與二元運算相關(guān)的特殊元(5)冪等元：定義：設(shè)*是A上二元運算，aA，若a*a=a,則稱a是關(guān)于*的冪等元?？杉s元：定義：設(shè)*是A上二元運算，aA，

①x,yA,a*x=a*yx=y,則稱a關(guān)于*左可約；②x,yA,x*a=y*a

x=y,則稱a關(guān)于*右可約；③若a關(guān)于*既左可約又右可約，則稱a關(guān)于*可約；

④若aA都是可約的，則稱*滿足消去律。分析例1-4

9例1中：關(guān)于+:aR均為左可約，右可約，也是可約的；關(guān)于

:aRa0均為左可約，右可約，也是可約的；

+滿足消去律。例2中：關(guān)于：是可約的；關(guān)于：U可約。例3中：關(guān)于o:*均可約。例4中：關(guān)于*:淺色可約。例5中：關(guān)于*:iN均左可約。定理7.1.7設(shè)*為A上的可結(jié)合的二元運算，aA，若a關(guān)于*可逆，則a關(guān)于*可約。*此定理的逆不成立。例6：N中的乘法運算.§7.1代數(shù)運算與代數(shù)系統(tǒng)

3.與二元運算相關(guān)的特殊元(6)10定理7.1.7:設(shè)*為A上的可結(jié)合的二元運算，aA，

若a關(guān)于*可逆，則a關(guān)于*可約。證明：

x,yA，如果a*x=a*y,∵a關(guān)于*可逆,=e*x由a*x=a*y，又有a-1*(a*x)=a-1*(a*y)

=(a-1*a)*y=e*y=y

=x

∴x=y故a關(guān)于*左可約。∴有a-1,使a-1*a=a*a-1=e;∴a-1*(a*x)=(a-1*a)*x

同理可證a關(guān)于*右可約。分析例4的運算表