离散数学 代数系统引入

离散数学代数系统引入1第1页，课件共15页，创作于2023年2月algebraicsystem代数也叫代数结构，是指定义有若干运算的集合例如整数集合，在其上定义了加法、乘法就构成了一个代数系统。代数学的历史悠久。但是从上世纪初以来，代数学的研究对象和研究方法发生了重大变革，形成了抽象代数学，这一变化可以追溯到伽罗瓦(Galois)提出群的概念。人们发现许多不同对象上的运算可以有共同的性质，这些发现将代数学研究引导到更高的层次─抽象代数系统研究。2第2页，课件共15页，创作于2023年2月抽象代数：不关心代数系数的具体集合是什么也不关心集合的运算如何定义只根据假设这些运算的某些规则（如结合律，分配律等）来讨论系统应具有的性质，使所得结论具有普遍意义。3第3页，课件共15页，创作于2023年2月algebraicsystem抽象代数学不同于以代数方程求根和根的分布情况为研究中心的古典代数学。在抽象代数系统中，对象是抽象的而不是具体的，对象上的运算也是抽象的，其含义由一组给定公理规定。抽象代数系统在计算机科学研究中始终占有重要的地位和作用：毫无疑问，没有抽象代数结构研究和数理逻辑研究的先行发展，图灵就不可能在1936年提出图灵机这样的代数结构作为计算的模型，从而第一次精确地定义了计算的概念和证明了计算机在理论上的存在性。4第4页，课件共15页，创作于2023年2月algebraicsystem在上世纪40－50年代，格和布尔代数成为计算机硬件设计以及通信系统设计中的重要工具，半群理论在形式语言与自动机的研究中发挥重要的作用。上世纪70年代在数据库研究中，人们发现关系代数理论能够作为数据库的理论模型。代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构。我们这里所要研究的是一类特殊的数学结构－－由集合上定义若干个运算而组成的系统。我们通常称它为代数系统。它在计算机科学中有着广泛的应用。5第5页，课件共15页，创作于2023年2月一、运算本章将从一般代数系统的引入出发，研究一些特殊的代数系统，而这些代数系统中的运算具有某些性质，从而确定了这些代数系统的数学结构。考察一个非空集合上运算的概念（1）将有理数集合Q上的每一个数a的映射成它的整数部分［a］（2）将Q上的每一个数a映射成它的相反数-a以上两个映射可以称为集合Q上的一元运算

（3）在集合Q上，对任意两个数所进行的普通加法和乘法都是集合Q上的二元运算（也可以看作是将Q中的每两个数映射成一个数）6第6页，课件共15页，创作于2023年2月一、运算（4）对集合Q上的任意三个数x１，x2，x3

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

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

*一角硬币

二角伍分硬币一角硬币二解伍分硬币桔子水可口可乐可口可乐冰淇淋二元运算*是在集合{一角硬币，二角伍分硬币}上的不封闭运算。8第8页，课件共15页，创作于2023年2月一、运算定义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第9页，课件共15页，创作于2023年2月二．代数系统

定义5-1.2

一个非空集合A连同若干个定义在该集合上的运算

f1，f2，…，fk

所组成的系统称为一个代数系统，记作<A，f1，f2，…，fk>。例如：（1）正整数集I＋及定义在该集合上的普通加法“＋”组成一个代数系统＜I＋，＋＞（2）有限集S上幂集及其上运算

，

，

组成代数系统

<P(S),

，

，

>.10第10页，课件共15页，创作于2023年2月二．代数系统

定义5-1.2’

代数结构是由以下三个部分组成的数学结构：（1）非空集合S，称为代数结构的载体。（2）载体S上的若干运算。（3）一组刻划载体上各运算所满足性质的公理。*代数结构常用一个多元序组<S，

，

，…>来表示，其中S是载体，

、

、…为各种运算。有时为了强调S有某些元素地位特殊，也可将它们列入这种多元序组的末尾。虽然代数系统具有不同的形式，但它们之间可能有一些共同的运算规律。11第11页，课件共15页，创作于2023年2月二．代数系统

例如，考察代数系统＜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，+＞有类似的运算性质。12第12页，课件共15页，创作于2023年2月由前例可看出，虽然集合不同，运算不同，但是它们是一些具有共同运算规律的运算，研究<I，+>就相当于研究<P(S)，∪>，<P(S)