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

1、1,第五章 代数结构,5-1 代数系统引入 授课人：李朔 Email:,2,algebraic system,代数也叫代数结构，是指定义有若干运算的集合 例如整数集合，在其上定义了加法、乘法就构成了一个代数系统。 代数学的历史悠久。但是从上世纪初以来，代数学的研究对象和研究方法发生了重大变革，形成了抽象代数学，这一变化可以追溯到伽罗瓦(Galois)提出群的概念。 人们发现许多不同对象上的运算可以有共同的性质，这些发现将代数学研究引导到更高的层次 抽象代数系统研究。,3,抽象代数： 不关心代数系数的具体集合是什么 也不关心集合的运算如何定义 只根据假设这些运算的某些规则（如结合律，分配律等）来

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

3、计中的重要工具，半群理论在形式语言与自动机的研究中发挥重要的作用。 上世纪70年代在数据库研究中，人们发现关系代数理论能够作为数据库的理论模型。 代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构。 我们这里所要研究的是一类特殊的数学结构由集合上定义若干个运算而组成的系统。我们通常称它为代数系统。它在计算机科学中有着广泛的应用。,6,一、运算,本章将从一般代数系统的引入出发，研究一些特殊的代数系统，而这些代数系统中的运算具有某些性质，从而确定了这些代数系统的数学结构。 考察一个非空集合上运算的概念 （1）将

4、有理数集合Q上的每一个数 a 的映射成它的整数部分a （2）将Q上的每一个数a 映射成它的相反数-a 以上两个映射可以称为集合Q上的一元运算 （3）在集合Q上，对任意两个数所进行的普通加法和乘法都是集合Q上的二元运算 （也可以看作是将Q中的每两个数映射成一个数 ）,7,一、运算,（4）对集合Q上的任意三个数x，x2 ，x3 ，代数式x12+x22+x32和x1+x2+x3分别给出了Q上的两个三元运算 （分别将Q中三个数映射成Q中的一个数 ） 上述这些例子有一个共同的特征，那就是其运算的结果都是在原来的集合中，我们称那些具有这种特征的运算是封闭的，简称闭运算。 相反地，没有这种特征的运算就是不封

5、闭的。很容易举出不封闭运算的例子 ： 设N是自然数集，Z是整数集，普通的减法是N-N到Z的运算 *因为两个自然数相减可以不是自然数，所以减法运算不是自然数集N上的闭运算。,8,一、运算,又如：一架自动货机，能接受一角硬币和二角五分硬币，而所对应的商品是桔子水（瓶）、可口可乐（瓶）和冰淇淋（杯）。当人们投入上述硬币的任何两枚时，自动售货机将按下表所示的供应相应的商品。表格左上角的记号*可理解为一个二元运算符。,二元运算*是在集合一角硬币，二角伍分硬币上的不封闭运算。,9,一、运算,定义5-1.1 对于集合A，一个从An到B的映射，称为 集合A上的n元运算。如果 BA，则称该n元运算在A上封闭。

6、如 AAB称为集A上的一个二元运算，若BS,，称该运算是封闭的。 例1：R上求一个数的相反数是一元运算，非0实数集上求倒数为一元运算，空间上点(x, y, z)投影到x轴为三元运算。 例2：判定下列在给定集上的二元运算的封闭性： 1）自然数集N上乘法，除法。 2）整数集Z上的加法，减法，乘法，除法。 3）非零实数集上加法，减法，乘法，除法。 4）S为任意集，S的幂集P（S）上， ，运算。 *通常用，*，等表示二元运算,10,二代数系统,定义5-1.2 一个非空集合A连同若干个定义在该集合上的运算 f1，f2，f k 所组成的系统称为一个代数系统，记作 。 例如： （1）正整数集I及定义在该集合

7、上的普通加法“”组成一个代数系统I， （2）有限集S上幂集及其上运算， 组成代数系统 .,11,二代数系统,定义5-1.2 代数结构是由以下三个部分组成的数学结构： （1）非空集合S，称为代数结构的载体。 （2）载体S上的若干运算。 （3）一组刻划载体上各运算所满足性质的公理。 *代数结构常用一个多元序组来表示，其中 S是载体，、为各种运算。有时为了强调S有某些元素地位特殊，也可将它们列入这种多元序组的末尾。 虽然代数系统具有不同的形式，但它们之间可能有一些共同的运算规律。,12,二代数系统,例如，考察代数系统I，+。很明显，在这个代数系统中，关于加法运算，具有以下三个运算规律，即对于任意的x，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，+有类似的运算性质。,13,由前例可看出，虽然集合不同，运算