《离散数学 代数系统引入优秀课件.ppt》由会员分享，可在线阅读，更多相关《离散数学 代数系统引入优秀课件.ppt（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学 代数系统引入1第1页，本讲稿共15页algebraic system代数代数也叫代数结构，是指定义有若干运算的集合n例如整数集合，在其上定义了加法、乘法就构成了一个代数系统。代数学的历史悠久。但是从上世纪初以来，代数学的研究对象和研究方法发生了重大变革，形成了抽象代数学，这一变化可以追溯到伽罗瓦(Galois)提出群的概念。人们发现许多不同对象上的运算可以有共同的性质不同对象上的运算可以有共同的性质，这些发现将代数学研究引导到更高的层次 抽象代数系统抽象代数系统研究。2第2页，本讲稿共15页抽象代数：n不关心代数系数的具体集合是什么n也不关心集合的运算如何定义n只根据假设这些运算的某
2、些规则（如结合律，分配律等）来讨论系统应具有的性质，使所得结论具有普遍意义。3第3页，本讲稿共15页algebraic system抽象代数学不同于以代数方程求根和根的分布情况为研究中心的古典代数学古典代数学。在抽象代数系统中，对象是抽象的而不是具体的，对象上的运算也是抽象的，其含义由一组给定公理规定。抽象代数系统在计算机科学研究中始终占有重要的地位和作用：毫无疑问，没有抽象代数结构研究和数理逻辑研究的先行发展，图灵就不可能在1936年提出图灵机这样的代数结构作为计算的模型，从而第一次精确地定义了计算的概念和证明了计算机在理论上的存在性。4第4页，本讲稿共15页algebraic system
3、在上世纪4050年代，格和布尔代数成为计算机硬件设计以及通信系统设计中的重要工具，半群理论在形式语言与自动机的研究中发挥重要的作用。上世纪70年代在数据库研究中，人们发现关系代数理论能够作为数据库的理论模型。代数的概念与方法是研究计算机科学和工程的重要数学工具。众所周知，在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构。我们这里所要研究的是一类特殊的数学结构由集合上定义若干个运算而组由集合上定义若干个运算而组成的系统成的系统。我们通常称它为代数系统代数系统。它在计算机科学中有着广泛的应用。5第5页，本讲稿共15页一、运算本章将从一般代数系统的引入出发，研究一些特殊的代
4、数系统，而这些代数系统中的运算具有某些性质，从而确定了这些代数系统的数学结构。考察一个非空集合上运算的概念 n（1）将有理数集合Q上的每一个数 a 的映射成它的整数部分an （2）将Q上的每一个数a 映射成它的相反数-a以上两个映射可以称为集合Q上的一元运算一元运算 n（3）在集合Q上，对任意两个数所进行的普通加法和乘法都是集合Q上的二元运算二元运算（也可以看作是将Q中的每两个数映射成一个数）6第6页，本讲稿共15页一、运算n（4）对集合Q上的任意三个数x，x2，x3，代数式x12+x22+x32和x1+x2+x3分别给出了Q上的两个三元运算三元运算（分别将Q中三个数映射成Q中的一个数）上述这
5、些例子有一个共同的特征，那就是其运算的结果都是在原来的集合中，我们称那些具有这种特征的运算是封闭的，简称闭运算闭运算。相反地，没有这种特征的运算就是不封闭的不封闭的。很容易举出不封闭运算的例子：设N是自然数集，Z是整数集，普通的减法是N-N到Z的运算*因因为为两两个个自自然然数数相相减减可可以以不不是是自自然然数数，所所以以减减法法运运算算不不是是自然数集自然数集N上的闭运算。上的闭运算。7第7页，本讲稿共15页一、运算又如：一架自动货机，能接受一角硬币和二角五分硬币，又如：一架自动货机，能接受一角硬币和二角五分硬币，而所对应的商品是桔子水（瓶）、可口可乐（瓶）和冰淇而所对应的商品是桔子水（瓶
6、）、可口可乐（瓶）和冰淇淋（杯）。当人们投入上述硬币的任何两枚时，自动售货淋（杯）。当人们投入上述硬币的任何两枚时，自动售货机将按下表所示的供应相应的商品。表格左上角的记号机将按下表所示的供应相应的商品。表格左上角的记号*可可理解为一个二元运算符。理解为一个二元运算符。*一角硬币一角硬币 二角伍分硬币二角伍分硬币一角硬币二解伍分硬币桔子水 可口可乐可口可乐 冰淇淋二元运算*是在集合一角硬币，二角伍分硬币上的不封闭运算。8第8页，本讲稿共15页一、运算定义定义5-1.1 5-1.1 对于集合A，一个从An到B的映射，称为 集合A上的n元运算元运算。如果 BA，则称该n元运算在A上封闭封闭。如 A
7、AB称为集A上的一个二元运算，若BS,，称该运运算是封闭的算是封闭的。例1：R上求一个数的相反数是一元运算，非0实数集上求倒数为一元运算，空间上点(x,y,z)投影到x轴为三元运算。例2：判定下列在给定集上的二元运算的封闭性：1）自然数集N上乘法，除法。2）整数集Z上的加法，减法，乘法，除法。3）非零实数集上加法，减法，乘法，除法。4）S为任意集，S的幂集P（S）上，运算。*通常用通常用，*，等表示二元运算等表示二元运算 9第9页，本讲稿共15页二代数系统二代数系统 定义定义5-1.25-1.2 一个非空集合A连同若干个定义在该集合上的运算 f1，f2，f k 所组成的系统称为一个代数系统代数
8、系统，记作。例如：（1）正整数集I及定义在该集合上的普通加法“”组成一个代数系统I，（2）有限集S上幂集及其上运算，组成代数系统 .10第10页，本讲稿共15页二代数系统二代数系统 定义定义5-1.25-1.2 代数结构代数结构是由以下三个部分组成的数学结构：是由以下三个部分组成的数学结构：（1）非空集合）非空集合S，称为代数结构的，称为代数结构的载体载体。（2）载体）载体S上的若干上的若干运算运算。（3）一组刻划载体上各）一组刻划载体上各运算所满足性质运算所满足性质的公理。的公理。*代数结构常用一个多元序组代数结构常用一个多元序组来表示，其来表示，其中中 S是是载体载体，、为各种为各种运算运
9、算。有时为了强调。有时为了强调S有某有某些元素地位特殊，也可将它们列入这种多元序组的末尾。些元素地位特殊，也可将它们列入这种多元序组的末尾。虽然代数系统具有不同的形式，但它们之间可能有一些共共同的运算规律同的运算规律。11第11页，本讲稿共15页二代数系统二代数系统 例如，考察代数系统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页由前例可看出，虽然集合不同，运算不同，但是它们是一些具有共同运算规律的运算，研究 就相当于研究，在这样的代数系统中，集合和运算仅仅是一些符号集合和运算仅仅是一些符号，可以用一组公理来规定这些集合和运算，这样的代数系统称为抽象代数系统抽象代数系统。13第13页，本讲稿共15页本课小结运算运算代数系统代数系统14第14页，本讲稿共15页作业课后复习15第15页，本讲稿共15页