离散数学-5-1 代数系统引入

离散数学2012

第五章 代数结构5-1 代数系统引入 授课人：李朔 Email:chn.nj.ls@http://doc.guandang.net

离散数学2012

algebraic system代数也叫代数结构，是指定义有若干运算的集合 代数 例如整数集合，在其上定义了加法、乘法就构成了一 个代数系统。 代数学的历史悠久。但是从上世纪初以来，代数学的研究 对象和研究方法发生了重大变革，形成了抽象代数学，这 一变化可以追溯到伽罗瓦(Galois)提出群的概念。 人们发现许多不同对象上的运算可以有共同的性质 不同对象上的运算可以有共同的性质，这些 不同对象上的运算可以有共同的性质 抽象代数系统研 发现将代数学研究引导到更高的层次─ 抽象代数系统 究。

离散数学2012

抽象代数： 不关心代数系数的具体集合是什么 也不关心集合的运算如何定义 只根据假设这些运算的某些规则(如结合律， 分配律等)来讨论系统应具有的性质，使所得 结论具有普遍意义。

离散数学2012

algebraic system抽象代数学不同于以代数方程求根和根的分布情况为研究 中心的古典代数学 古典代数学。 古典代数学 在抽象代数系统中，对象是抽象的而不是具体的，对象上 的运算也是抽象的，其含义由一组给定公理规定。 抽象代数系统在计算机科学研究中始终占有重要的地位和 作用： 毫无疑问，没有抽象代数结构研究和数理逻辑研究的先行 发展，图灵就不可能在1936年提出图灵机这样的代数结构 作为计算的模型，从而第一次精确地定义了计算的概念和 证明了计算机在理论上的存在性。4

离散数学2012

algebraic system在上世纪40-50年代，格和布尔代数成为计算机硬件设计以及通信系 统设计中的重要工具，半群理论在形式语言与自动机的研究中发挥重 要的作用。 上世纪70年代在数据库研究中，人们发现关系代数理论能够作为数据 库的理论模型。 代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周 知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就 要用到某种数学结构。 我们这里所要研究的是一类特殊的数学结构--由集合上定义若干个 由集合上定义若干个 运算而组成的系统。我们通常称它为代数系统 代数系统。它在计算机科学中有 运算而组成的系统 代数系统 着广泛的应用。

离散数学2012

一、运算本章将从一般代数系统的引入出发，研究一些特殊的代数 系统，而这些代数系统中的运算具有某些性质，从而确定了 这些代数系统的数学结构。 考察一个非空集合上运算的概念 (1)将有理数集合Q上的每一个数 a 的映射成它的整数部 分[a] (2)将Q上的每一个数a 映射成它的相反数-a 以上两个映射可以称为集合Q上的一元运算 (3)在集合Q上，对任意两个数所

进行的普通加法和乘法 都是集合Q上的二元运算 (也可以看作是将Q中的每两个数 二元运算 映射成一个数 )

离散数学2012

一、运算(4)对集合Q上的任意三个数x1,x2 ,x3 ,代数式 x12+x22+x32和x1+x2+x3分别给出了Q上的两个三元运算 (分 三元运算 别将Q中三个数映射成Q中的一个数 ) 上述这些例子有一个共同的特征，那就是其运算的结果都 是在原来的集合中，我们称那些具有这种特征的运算是封闭 的，简称闭运算 闭运算。 闭运算 相反地，没有这种特征的运算就是不封闭的 不封闭的。很容易举出 不封闭的 不封闭运算的例子 ： 设N是自然数集，Z是整数集，普通的减法是N-N到Z的运算 *因为两个自然数相减可以不是自然数 ， 所以 减法运算不是 因为两个自然数相减可以不是自然数， 因为两个自然数相减可以不是自然数 所以减法运算不是 自然数集N上的闭运算 上的闭运算。 自然数集 上的闭运算。

离散数学2012

一、运算又如：一架自动货机，能接受一角硬币和二角五分硬币， 又如：一架自动货机，能接受一角硬币和二角五分硬币， 而所对应的商品是桔子水( )、可口可乐 可口可乐( 而所对应的商品是桔子水(瓶)、可口可乐(瓶)和冰淇 )。当人们投入上述硬币的任何两枚时 当人们投入上述硬币的任何两枚时， 淋(杯)。当人们投入上述硬币的任何两枚时，自动售货 机将按下表所示的供应相应的商品。表格左上角的记号*可 机将按下表所示的供应相应的商品。表格左上角的记号 可 理解为一个二元运算符。 理解为一个二元运算符。

*一角硬币

一角硬币 桔子水

二角伍分硬币 可口可乐

二解伍分硬币

可口可乐

冰淇淋

二元运算*是在集合{一角硬币，二角伍分硬币}上的不封 闭运算。8

离散数学2012

一、运算定义5 定义5-1.1 对于集合A,一个从An到B的映射，称为 集合 A上的n元运算 元运算。如果 B A,则称该n元运算在A上封闭 封闭。 元运算 封闭 如 A×A→B称为集A上的一个二元运算，若B S,,称该运算 运算 是封闭的。 是封闭的 例1:R上求一个数的相反数是一元运算，非0实数集上求倒 数为一元运算，空间上点(x, y, z)投影到x轴为三元运算。 例2:判定下列在给定集上的二元运算的封闭性： 1)自然数集N上乘法，除法。 2)整数集Z上的加法，减法，乘法，除法。 3)非零实数集上加法，减法，乘法，除法。 4)S为任意集，S的幂集P(S)上∩,∪, ,⊕运算。 *通常用о,*, , 等表示二元运算 通常用о 通常用 ，9

离散数学2012

二.代数系统定义5 定义5-1.2 一个非空集合A连同若干个定义在该集合上的 代数系统，记 运算 f1,f2,…,f k 所组成的系统称为一个代数系统 代数系

统 作<A, f1,f2,…,f k > 。 例如： (1)正整数集I+及定义在该集合上的普通加法“+”组成 一个代数系统<I+,+> (2)有限集S上幂集及其上运算∪,∩,～ 组成代数系统 <P(S), ∪,∩,～ >.

离散数学2012

二.代数系统定义5 1.2’ 代数结构是由以下三个部分组成的数学结构 是由以下三个部分组成的数学结构： 定义5-1.2’ 代数结构是由以下三个部分组成的数学结构： 载体。 (1)非空集合 ，称为代数结构的载体。 )非空集合S,称为代数结构的载体 上的若干运算 (2)载体 上的若干运算。 )载体S上的若干运算。 运算所满足性质的公理 (3)一组刻划载体上各运算所满足性质的公理。 )一组刻划载体上各运算所满足性质的公理。 *代数结构常用一个多元序组 ， , ,… >来表示，其 代数结构常用一个多元序组<S, 来表示， 代数结构常用一个多元序组 来表示 为各种运算 中 S是载体， 、 、…为各种运算。有时为了强调 有某 是载体， 为各种运算。有时为了强调S有某 些元素地位特殊，也可将它们列入这种多元序组的末尾。 些元素地位特殊，也可将它们列入这种多元序组的末尾。 虽然代数系统具有不同的形式，但它们之间可能有一些共 共 同的运算规律。 同的运算规律11

离散数学2012

二.代数系统例如，考察代数系统<I,+>。很明显，在这个代数系统 中，关于加法运算，具有以下三个运算规律，即对于任意 的x,y,z∈I,有： (1) x+y ∈ I (2) x+y=y+x (封闭性 封闭性) 封闭性 (交换律 交换律) 交换律 (结合律 结合律) 结合律

(3) (x+y)+z=x+(y+z)

又如，设S是集合，P(S)是S的幂集，则代数系统 <P(S),∪>和<P(S),∩>中的∪、∩都适合 交换律，结合律，即他们与<I,+>有类似的运算性质。

离散数学2012

由前例可看出，虽然集合不同，运算不同，但是它们是一 些具有共同运算规 …… 此处隐藏：2057字，全部文档内容请下载后查看。喜欢就下载吧 ……