离散数学课件 代数系统2.ppt

第六章代数系统(抽象代数)就专业知识而言，计算机学科中要培养学生三个能力：
理论抽象设计
理论：就是计算机科学中各种理论课。
抽象：要把实际问题抽象成数学模型(数学系统)。
设计：系统设计、程序设计。
确定数学模型，需要了解有哪些代数结构(系统)。
另外，抽象代数可以培养学生的抽象逻辑思维能力。
本章所讨论的理论，在计算机的编译理论、程序理论、
语义理论、编码理论、计算理论、逻辑设计理论、数据
库理论等都有应用。
本章主要讨论：代数结构(系统)的概念，运算的性质、
代数结构(系统)的同构、半群、独异点、群、环、域等。6-1代数结构(系统)的概念1.定义：设X是个集合，f:XnY是个映射，则称f是X上
的n元运算。(Xn=X×X×...×X--n个X的笛卡尔积)，

如果YX，则称运算f在X上是封闭的。
f:XY是个一元运算。前面的-、~是一元运算。f:X2Y是个二元运算。+×÷∧∨∪∩是二元运算。
思考题：下面说法是否正确？
减法－是N上封闭的二元运算。
除法÷是整数I上的二元运算。
除法÷是实数R上的二元运算。
我们主要讨论二元运算。
通常用、、、、、、+等表示抽象的二
元运算。如果用“”表示二元运算f时，
通常将f(<x,y>)=z写成xy=z。2.二元运算的运算表
有时用一个表来表示二元
运算的运算规律。
例如令E={a,b}，P(E)上的
∩运算表如图所示。

再如令X={S,R,A,L}其中
S表示开始时的位置；
R表示“向右转”；
A表示“向后转”；
L表示“向左转”；
“”表示转动的复合运算；
其运算表如图所示。
从运算表除了可以看清运算的规律外，可以很容易地看
出运算的性质。二.代数系统的概念6-2二元运算的性质

从运算表看交换性：是以主对角线为对称的表。
三.幂等元、幂等性
设是X上的二元运算，如果有a∈X，aa=a，则称a是
幂等元。如果对任何x∈X,都有xx=x，则称有幂等性.
从运算表看幂等元、幂等性：看主对角线的元素与上表头(或左表头)元素相同。
请看上述∩的运算表
∩有幂等性。四.幺元(单位元、恒等元)
设是X上的二元运算，如果有eL∈X，使得对任何x∈X，
有eLx=x，则称eL是相对的左幺元。如果有eR∈X，使
得对任何x∈X，有xeR=x，则称eR是相对的右幺元。
如果eL=eR=e，对任何x∈X，有ex=xe=x,称e是相对
的幺元。
对加法+，幺元是0，
对乘法×，幺元是1，
对并运算∪，幺元是Φ，
对交运算∩，幺元是全集E，
从运算表中找幺元（如表所示）
从运算表找左幺元eL：eL所在行的各元素均与上表头元
素相同。如S行，所以S是eL。
从运算表找右幺元eR：eR所在列的各元素均与左表头元
素相同。如S列，所以S是eR。定理6-2.1.设是X上的二元运算，如果有左幺元eL∈X，也有右幺元eR∈X，则eL=eR=e，且幺元e是唯一的。
证明：因为eL是左幺元，又eR∈X，所以eLeR=eR
因为eR是右幺元，又eL∈X，所以eLeR=eL
于是eL=eR=e。
下面证明幺元的唯一性。
假设有两个幺元e1、e2，
因为e1是幺元，又e2∈X，所以e1e2=e2
因为e2是幺元，又e1∈X，所以e1e2=e1
则e1=e2=e。所以幺元是唯一的。

思考题.减法运算是否有幺元？五.零元
设是X上的二元运算，如果有θL∈X，使得对任何
x∈X，有θLx=θL，则称θL是相对的左零元。如果
有θR∈X，使得对任何x∈X，有xθR=θR，则称θR
是相对的右零元。如果θL=θR=θ，对任何x∈X，有
θx=xθ=θ,称θ是相对的零元。
例如：对乘法×，零元是0，
对并运算∪，零元是全集E，
对交运算∩，零元是Φ，

从运算表找零元
左零元θL：θL所在行的各元素均与左表头元素相同。
如Φ行，所以Φ是θL。
右零元θR：θR所在列的各元素均与上表头元素相同。
如Φ列，所以Φ是θR。
所以θ=Φ定理6-2.2.设是X上的二元运算，如果有左零元θL∈X，也有右零元θR∈X，则θL=θR=θ,且零元θ是唯一的。
证明的方法与前定理类似，从略。
定理6-2.3.设<X,>是代数系统，且|X|>1。如果该代数系统中存在幺元e和零元θ,则θ≠e.
证明：用反证法。假设θ=e，那么对任意xX,
必有x=ex=θx=θ=e
于是,X中所有元素都是相同的，这与|X|>1矛盾。
所以θ≠e。六.可结合性
设是X上的二元运算，如果对任何x,y,z∈X，有
(xy)z=x(yz)，则称是可结合的。
例：数值的加法、乘法，集合的交、并、对称差，
关系的复合、函数的复合，命题的合取、析取等。
若是可结合的运