离散数学(3讲).pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn 2011年11月24日星期四5时3分2秒 * 计算机学院 * 主要内容 二元运算 代数系统 特异元 半群与含幺半群 * 计算机学院 * 代数系统 代数系统又称为代数结构，群、环、域、格和布尔代数是典型的代数系统。代数系统理论对于可计算模型研究、抽象数据结构、形式语言理论、程序设计语言语义分析等许多方面产生的影响是深远的。 代数系统理论提供了对各种表面上不同的实际问题高度抽象的途径，使人们更能把握住事物的本质，进行形式化的研究，又反过来指导实践的深入。 * 计算机学院 * 二元运算 定义14.1：设S是一个非空集合，映射（或函数）f ：Sn→S称为S上的n元代数运算，简称n元运算(n-ary Operation)。当n＝1时，称为一元运算；当n＝2时，称为二元运算。 一般采用符号“·”表示二元运算符。 * 计算机学院 * 运算的性质 定义14.2：设“·”是一个S上的二元代数运算，如果 对任意的a, b∈S，都有a·b∈S，则称“·”在S上是封闭的； 对任意的a, b∈S，都有a·b＝b·a 则称“·”在S上是可交换的，或称满足交换律； 对任意的a, b，c∈S，都有 (a·b)·c＝a·(b·c) 则称“·”在S上是可结合的，或称满足结合律； 对任意的a∈S，满足a·a＝a，则称“·”是幂等的。 * 计算机学院 * 定义14.3 设“*”、“·”是集合S上的两个二元运算，对?a,b,c?S， 若 a·(b*c)=(a·b)*(a·c)且 (b*c)·a=(b·a)*(c·a)，则称“·”对“*”在S上满足分配律。 设“*”、“·”是可换运算，若a·(a*b)=a及 a*(a·b)=a，则称运算“*”与“·” 满足吸收律。 问题:在我们已经 学过的知识里面， 这样的集合和运算 存不存在呢? 〈2A，∪，∩〉，〈?，?，?〉 * 计算机学院 * 定义14.4 设S是一个非空集合，f1,f2,…, fm分别是定义在S上的运算，称集合S和f1,f2,…, fm所组成的系统称为一个代数系统，简称代数，记为S，f1,f2,…,fm 。 常见的代数系统有 同一个集合与不同的运算构成不同的代数系统 * 计算机学院 * 特异元 定义14.5 设“*”是集合S上的二元运算，〈S,*〉是一个代数系统， 1）若?e?S，使得对?a?S，都有：a*e=e*a=a， 则称e为(代数系统）的单位元或幺元； 2）若?θ?S,使得对?a?S,都有： a*θ=θ*a=θ，则称θ为(代数系统）的零元； （注意：在任意一个代数系统中，并不是都有零元存在）。 3）若元素a∈S，满足a*a＝a，则称a是(代数系统）的一个幂等元。 * 计算机学院 * 定义14.6 设“*”是集合S上的二元运算,〈S,*〉是一个代数系统，e是〈S,*〉的幺元，若对a?S，?b?S，使得：a*b=b*a=e，则称b是a的逆元，a也称为可逆的，记为b=a-1（同样，a也为b的逆元，b也称为可逆的，记为b-1 ）； 注意：在一个代数系统中，并不是每个元都是可 逆的。 * 计算机学院 * 特异元的性质 定理14.1 设〈S,*〉是一个代数系统：1）若〈S,*〉存在幺元，则该幺元唯一； 2）若〈S,*〉存在零元，则该零元唯一； 3）若“*”满足结合律且e是〈S,*〉的幺元(即幺元存在)，则对?a?S，若a存在逆元,则该逆元唯一。 证明：1）（反证法）设〈S,*〉含有幺元e1，e2，根据定义e1=e1*e2=e2，因此，幺元是唯一的。 3）设e是〈 S,*〉的幺元，元素a有两个逆元a1，a2，则 a1=a1*e= a1*（a*a2）= (a1*a)*a2=e*a2=a2 因此，逆元也是唯一的。 * 计算机学院 * 半群与含幺半群 广群、半群与含么半群是最简单的代数系统之一，它在时序线路、形式语言理论、自动机理论中均有很广泛的应用。 一般地，我们把只含一个二元运算的代数系统S,*称为二元代数。 * 计算机学院 * 定义14.7　设S，*是一个二元代数系统： 当“*”是封闭的，称S，*为广群； 如果S，*是广群，且“*”是可结合的运算，则称S，*为半群； S，*是半群，且存在幺元e，则称此半群S，*是含幺半群，常记为S，*，e； 如果S，*是含幺半群，且每个元素都有逆元，则称S，*为群。（闭、结、逆、幺） 群?含幺半群?半群?广群 * 计算机学院 * 例14.1 设n＝｛0,1,2,…,n-1｝，定义n上的运算+n如下：?x,y∈n，x