第十章 代数系统.ppt

第三部分代数结构
代数结构也叫做抽象代数,主要研究抽象的代数系统。抽象的代数系统也是一种数学模型,可以用它表示实际世界中的离散结构。
例如在形式语言中常将有穷字符表记为∑,由∑上的有限个字符(包括0个字符)可以构成一个字符串,称为∑上的字。∑上的全体字符串构成集合∑*。设α,β是∑*上的两个字,将β连接在α后面得到∑*上的字αβ。如果将这种连接看作∑*上的一种运算,那么这种运算不可交换,但是可结合。集合∑*关于连接运算就构成了一个代数系统,它恰好是抽象代数系统--半群的一个实例。
抽象代数在计算机中有着广泛的应用,例如自动机理论、编码理论、形式语义学、代数规范、密码学等等都要用到抽象代数的知识。代数结构的主要研究对象就是各种典型的抽象代数系统。
二元运算及其性质
一、二元运算与一元运算的定义
设S为集合,函数f:S×S→S称为S上的二元 运算,简称为二元运算。
例如f:N×N→N,f(<x,y>)=x+y就是自然数集合N上 的二元运算,即普通的加法运算。
普通的减法不是自然数集合N上的二元运算,
因为两个自然数相减可能得到负数,而负数不是自然数。这时也称N对减法运算不封闭。
例如实数集合R上不可以定义除法运算,因为0∈R,而0不能做除数。但在R*=R-{0}上就可以定义除法运算了,因为 x,y∈R*,都有x/y∈R*。
验证一个运算是否为集合S上的二元运算主要考虑两点:
(1) S中任何两个元素都可以进行这种运算,且运算的结 果是唯一的。
(2) S中任何两个元素的运算结果都属于S,即S对该运 算是封闭的。
设S为集合,函数f:S→S称为S上的一个一元
运算,简称为一元运算。
(6) 在n(n≥2)阶实矩阵的集合Mn(R)上,求一个矩阵的转置矩阵是Mn(R)上的一元运算。
(1) 求一个数的相反数是Z,Q和R上的一元运算。
(2) 求一个数的倒数是Q*,R*上的一元运算。
(3) 求一个复数的共轭复数是复数集合C上的一元运算。
(4) 在P(S)上,如果规定全集为S,则求集合的绝对补运算~是P(S)上的一元运算。
(5) 设S为集合,令A为S上所有双射函数的集合,A  SS,则求一个双射函数的反函数为A上的一元运算。
同样可以用算符来标记,若f(x)=y,则记为(x)=y,或x=y
如:相反数-x,求绝对补集~A
解析公式就是使用算符和表达式给出参与运算的元
素和运算结果之间的映射规则。
表示二元或一元运算的方法有两种:解析公式和运算表。
对于有穷集上的一元和二元运算,可以用有穷表给出。
。其中a1,a2,…,an是S中的元素,   为算符。
ai
ai
a1
a2
…
an
a1
a2
…an

a1 a2 … an
a1
a2
…
an
a1a1 a1a2 … a1an
a2a1 a2a2 … a2an
………
ana1 ana2 … anan


例3:给出对应的运算表:
1) 设A={1,2,1/2},对xA,规定x=1/x
2) 设A={1,2,3,4},对x,yA,规定xy=max(x,y)
ai
ai
1
2
1/2
1
½
2

1 2 3 4
1
2
3
4
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4