西安交通大学-刘国荣-离散数学 第六章 代数系统[1].ppt

离散数学 西安交通大学 电子与信息工程学院 计算机软件所 刘国荣 离散数学 代数系统在计算机科学中的应用 代数系统是一种数学结构，代数的概念和方法是研究计算机科学的重要数学工具。在利用计算机科学解决实际问题时都离不开数学模型，而构造一个现象或过程的数学模型就需要某种数学结构，而代数结构就是最常用的数学结构之一。如描述机器可计算的函数、研究算法计算的复杂性、刻划抽象数据结构、程序设计语言的语义基础、逻辑电路设计和编码理论等都需要代数知识。代数系统中的群论在计算机安全领域得到广泛关注，比如有名的椭圆曲线算法，半群在形式语言与自动机中都有具体的应用。 另外，计算机科学中的有限自动机理论、开关网络理论、计算机逻辑设计等领域都直接地应用了布尔代数的结论。 离散数学 离散数学 第六章 代数系统 §1.代数系统的基本概念 　　　　 §2.代数系统的同态和同构 　　　　 §3.半群与单子 　　　　 §4.群 §5.环 §6.域 　　　　 §7.同余关系 离散数学 §1.代数系统的基本概念 ?代数系统 ?代数系统的基本性质 ?子代数系统 离散数学 第四章 代数系统 (algebra system) §1.代数系统的基本概念 代数系统有两层含义，一层是代数，一层是系统。代数的实质是运算与比较，运算与比较的概念我们在上二章已经定义过了，比较则牵扯到半序关系；而系统的含义则是集成，即将若干相关联的部分构成一个整体。代数系统就是将一个非空集合以及这个集合上的若干个运算、关系集成在一起成为一个整体。 　这相当于面向对向的程序设计中的捆绑思想。其实代数系统的许多概念都已渗透到计算机科学的各个方面了。 定义1.代数系统　代数结构(algebra structure) 离散数学 一个代数系统(代数结构，简称代数)A是如下的一个有序元组： A=(X,O1 , O2 ,?, Om , R1 , R2 ,?, Rn , c1 , c2 ,?, cl ) 其中: (1)X??是一个任意集合,称为母集或承载子(carrier)； (2)O1 , O2 ,?, Om是X上的m个运算(m?1) ； (3)R1 , R2 ,?, Rn是X上的n个(序)关系(n?0) ； (4)c1 , c2 ,?, cl ?X是X中的l个特殊元素(l?0),称为常项(constants)。 注：?当X是有限集合时，称A为有限代数系统； 　 ?当X是无限集合时，称A为无限代数系统； ?在一个代数系统中运算的集合不能是空的，必须至少有一个X上的运算。代数系统中各个运算的元(阶)数可能是不一样的，即每个运算都有自己的运算元数； ?对于运算我们主要讨论运算的封闭性；另外还要讨论运算的 离散数学 许多性质； ?我们离散数学研究的代数系统主要包含一些运算(以一元、二 元)为主及一些常项。 例1. (1)(I,+), (I, ?) ,(I,+,?)都是代数系统。 这里：I是整数集合：+和?是整数的加法和乘法。 由于两个整数之和仍为整数，且结果唯一，即?a,b，a?I?b?I?a+b?I ，满足封闭性，故+是I上的二元运算。 由于两个整数之积仍为整数，且结果唯一，即?a,b，a?I?b?I?a?b?I ，满足封闭性，故?是I上的二元运算。 由代数系统的定义知(I,+), (I, ?) ,(I,+,?)分别都是代数系统。 (2)(I,+, ?, ?, 0,1)是代数系统。 另外小于等于关系?是I上的二元关系(半序)，0,1?I是I 离散数学 上的两个特殊元素，故(I,+, ?, ?, 0,1)更是一个典型的代数系统。 例2. (?, o)是代数系统。 这里：X={a,b}，设?={f ? f :X?X }，则 ?={f 1 , f 2 , f 3 , f 4 } 。 其中： f 1 (a)=a f 2 (a)=a f 3 (