离散数学(第二版)第5章代数系统的基本概念

定理5.1.1 设*是S中的二元运算且er与el分别是对于*的 右幺元和左幺元，则er=el=e， 使对任意元素x∈S有 x*e=e*x=x， 称元素e为关于运算*的幺元(identity elements)且 唯一。
第五章 代数系统的基本概念
证明 因为er和el分别是*的右幺元和左幺元，故有 el*er=el，el*er=er，所以er=el。 令其为e，有
(b a)*(b b)=a*b=b (a a)*(a b)=a*a=a (b a)*(b a)=a*a=a (b b)*(b b)=b*b=a (a a)*(a a)=a*a=a (a b)*(a b)=a*a=a
第五章 代数系统的基本概念
(3) b*(a b)=b*a=b
(b*a) (b*b)=b a=a
第五章 代数系统的基本概念
表5.1.1
表5.1.2
第五章 代数系统的基本概念
事实上，对于表5.1.1，通过观察我们可看出其运算为 (〈x，y 〉)=x·y(mod 3)
其中，“·”是普通乘法。 而对于表5.1.2，此时的“*”运算应是在集合{0，1}上 的∧(逻辑合取运算符)。 下面介绍二元运算的性质。
【例5.1.3】加法、 乘法运算是自然数集上的二元运算，
减法和除法便不是。但是减法是有理数集、 实数集上的二
元运算，除法却仍不是。加法、 乘法满足结合律、 交换律，
乘法对加法、 减法满足分配律，减法不满足这些定律。乘
+”运算满足分配律(对“-”也满足)。但加
法“+”
第五章 代数系统的基本概念
【例5.1.4】设A是集合，在A的幂集P(A)上的二元运算 并∪、 交∩满足交换律、 结合律、 吸收律、 幂等律且彼此 满足分配律。
第五章 代数系统的基本概念
第五章 代数系统的基本概念
第五章 代数系统的基本概念
(2) A为集合，P(A)为其幂集。f: P(A)×P(A)→P(A)。 f可 以是∩、 ∪、 -、
(3) A={0，1}。f: A×A→A。f可以是∧、 ∨、 →、 (4) AA={f|f: A→A}。“。(复合)”是AA上的二元运算。 当A是有穷集合时，运算可以用运算表给出。如A={0， 1，2，3，4，5}，二元运算“。”的定义见表5.1.1。
第五章 代数系统的基本概念
定义5.1.2 设*
S上的二元运算。
(1) x y z(x，y，z∈S→x*(y*z)=(x*y)*z)，则称“*” 运算满足结合律。
(2) x y(x，y∈S→x*y=y*x)，则称“*”运算满足 交换律。
(3) 则称“* z∈S→(y
x y z(x，y，z∈S→x*(y z)=(x*y) (x*z))，
第五章 代数系统的基本概念
一般地，二元运算用算符 。，* ‘，·，Δ，◇等等表示， 并将其写于两个元素之间，如Z×Z→Z的加法：
F(〈2，3〉)=+(〈2，3〉)=2+3=5 注意到Ran f A，即运算结果是A中的元素，这称为运 算的封闭性。另外，运算是函数，要具备函数所具有的对每 一个自变元有唯一的像的特性。
故*
又由a*(a b)=a*a=a 及上面(1)、 (2)、 (3)
*
满足吸收律。
*不满足幂等律。
下面我们来定义与集合A中的二元运算有关的集合A中
的特异元素。
第五章 代数系统的基本概念
定义5.1.3 设*是集合S中的一种二元运算，如果存在 er∈S(el∈S)且对任意元素x∈S 均有x*er=x(el*x=x)，则称元素 er(el)为S中关于运算*的右幺元(左幺元)或右单位元(左单位 元)。
(2) 左、 右幺元，幺元，左、 右零元，零元都是依赖于
运算的。例如，在代数结构〈 N，+，·〉中，0关于数加 +
是幺元，关于数乘·是零元； 1关于·是幺元，关于+则既非幺
元又非零元。又如在P(A)
∪的幺元，是关于∩
的零元； A是关于∪的零元，又是关于∩的幺元。
第五章 代数系统的基本概念
(3) 今后，在不致造成混淆时，特殊元素是关于什么运
定理5.1.2 设*是S中的二元运算且θr 与θl分别是对于* 的右零元和左零元，则θr=θl=θ， 使对任意元素x∈S有 x*θ=θ*x=θ， 称元素θ是S中关于运算*的零元(zero)且唯一。
第五章 代数系统的基本概念
证明 因为θr 和θl分别是*的右零元和左零元，故有 θl*θr=θl，θl*θr=θr，所以θr=θl。 令其为θ，有
显然对于二元运算*，若*是可交换的，则任何左(右)可 逆的元素均可逆。
第五章 代数系统的基本概念
定理5.1.3 设*是集合S中的一个可结合的二元运算，且 S中对于*有e为幺元，若x∈S是可逆的，则其左、 右逆元相 等，记作x-1，称为元素x对运算*的逆元(inverse elements)且 是唯一的。(x的逆元通常记为x-1; 但当运算被称为“加法运 算”(记为+)时， x的逆元可记为-x。)
我们注意到，关于同一运算可能同时有幺元和零元，甚 至可能有这样的元素，它关于同一运算既是左(右)幺元，又 是右(左)零元，例如表5.1.5第一行(不计表头)改为三个a时， 那么*运算有左零元a和右幺元a。
第五章 代数系统的基本概念
我们强调以下几点：
(1) 左、 右幺元，幺元，左、 右零元，零元都是常元。
x*θ=θ*x=θ
设另有一零元为右零元θ′，那么
θ=θ*θ′=θ′
故θ对S中的*运算是唯一的零元。
证毕
同样，需强调零元是针对于哪个运算的。
第五章 代数系统的基本概念
【例5.1.7】在实数集R中，对加法“+”运算，没有零元；
在实数集R中，对乘法“×”运算，0是零元；
对于全集E的子集的并“∪”运算，E是零元；
x*e=e*x=x 设另有一幺元为右幺元e′，那么
e=e*e′=e′ 故e对*是唯一的幺元。
证毕
显然，对于可交换的二元运算来说，左幺元即为右幺元，
反之亦然。因此对于可交换的二元运算，左(右)幺元即幺元。
另外，我们必须强调是对哪一个运算而言的幺元。
第五章 代数系统的基本概念
【例5.1.6】在实数集R中，对加法“+”运算，0是幺元；
第五章 代数系统的基本概念
证明 设xr 和xl分别是x对*运算的右逆元和左逆元，故 有
xl*x=x*xr=e 由于*可结合，于是
xl=xl*e=xl*(x*xr)=(xl*x)*xr=e*xr=xr
故xl=xr。
假设
x11
，x
1 2
均是x对*的逆元，则
x11 = x11 *e=x11 *(x* x11 )=
在实数集R中，对乘法“×”运算，1是幺元；
对于全集E的子集的并“∪
对于全集E的子集的交“∩”运算，E是幺元; 在命题集合中，对于析取“∨”运算，矛盾式是幺元；
在命题集合中，对于合取“∧”运算，重言式是幺元；
在AA={f|f:A→A}
IA是幺元。
第五章 代数系统的基本概念
定义5.1.4 设*是集合S中的一种二元运算，如果存在 θr∈S(θl∈S)且对任意元素x∈S均有x*θr=θr(θl*x= θl)，则称元素θr(θl)是S中关于运算*的右零元(左零元)。
对于全集E的子集的交“∩
;
在命题集合中，对于析取“∨”运算，重言式是零元； 在命题集合中，对于合取“∧”运算，矛盾式是零元。
【例5.1.8】设S＝｛a，b，c｝， S上*运算由运算表(如
表5.1.5所示)确定，那么b是右零元， a是幺元。
第五章 代数系统的基本概念
表 5.1.5
第五章 代数系统的基本概念
元。
定理5.1.5 设*是S上的二元运算，e为幺元，θ为零元，
并且|S|≥2，那么θ无左(右)逆元。
证明 首先证 θ≠e，否则θ=e，则S中另有元素a，a不是
幺元和零元，从而 θ＝θ*a＝e*a＝a
与a不是零元矛盾，故θ≠e得证。
第五章 代数系统的基本概念
再用反证法证θ无左(右)逆元，即可设θ有左(右)逆元x， 那么
第五章 代数系统的基本概念
(4) 在P(A)中，对于∪
B(B≠ )均无逆元； 对于∩运算，其幺元为A，每个元素
B(B≠A)均无逆元。
(5) 在集合AA(其中 AA ＝｛f|f： A→A｝)
合成运算，恒等函数IA为幺元，从而A中所有双射函数都有 逆元，所有单射函数都有左逆元， 所有满射函数都有右逆
如，在〈P(A)，∪，∩〉
P(A)的加法幺元、 乘法
零元， 称A为P(A)的乘法幺元、 加法零元。
第五章 代数系统的基本概念
定义5.1.5 设*是集合S中的一种二元运算，且S中对于* 有e为幺元，x，y为S中元素。若x*y＝e，那么称x为y的左逆 元，y为x的右逆元，若x对于*运算既有左逆元又有右逆元， 则称x是左、 右可逆的。若x左右均可逆，称x可逆。
(
x11
*x)*
x
2
1
=e*
x
21=x Nhomakorabea2
1
由 x11 x21 ，故唯一性成立。 由逆元定义知，若x-1存在，则x-1*x=x*x-1=e。
证毕
第五章 代数系统的基本概念
定理5.1.4 设*是集合S中的一个可结合的二元运算，且 e为S中对于*的幺元，x有逆元x-1，则(x-1)-1=x。
证明 (x-1)-1=(x-1)-1*e=(x-1)-1*(x-1*x) =((x-1)-1*x-1)*x=e*x=x。 证毕
算的不再一一指出，但当有两个或两个以上的运算时仍将对
此作出申明。这时，常常出现这样的情况，一个运算与数加
的性质接近，另一个运算与数乘的性质接近，为了简明、