离散数学(第30讲).ppt

文档介绍：冯伟森
Email:******@scu.
2011年11月24日星期四5时3分2秒
离散数学
计算机学院
2018/6/13
计算机学院
2
主要内容
二元运算
代数系统
特异元
半群与含幺半群
2018/6/13
计算机学院
3
代数系统
代数系统又称为代数结构,群、环、域、格和布尔代数是典型的代数系统。代数系统理论对于可计算模型研究、抽象数据结构、形式语言理论、程序设计语言语义分析等许多方面产生的影响是深远的。
代数系统理论提供了对各种表面上不同的实际问题高度抽象的途径,使人们更能把握住事物的本质,进行形式化的研究,又反过来指导实践的深入。
2018/6/13
计算机学院
4
二元运算
:设S是一个非空集合,映射(或函数)f :Sn→S称为S上的n元代数运算,简称n元运算(n-ary Operation)。当n=1时,称为一元运算;当n=2时,称为二元运算。
一般采用符号“·”表示二元运算符。
2018/6/13
计算机学院
5
运算的性质
:设“·”是一个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,则称“·”是幂等的。
2018/6/13
计算机学院
6
设“*”、“·”是集合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,∪,∩〉,〈,,〉
2018/6/13
计算机学院
7
设S是一个非空集合,f1,f2,…, fm分别是定义在S上的运算,称集合S和f1,f2,…, fm所组成的系统称为一个代数系统,简称代数,记为<S,f1,f2,…,fm >。
常见的代数系统有
同一个集合与不同的运算构成不同的代数系统
2018/6/13
计算机学院
8
特异元
设“*”是集合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是(代数系统)的一个幂等元。
2018/6/13
计算机学院
9
设“*”是集合S上的二元运算,〈S,*〉是一个代数系统,e是〈S,*〉的幺元,若对aS,bS,使得:a*b=b*a=e,则称b是a的逆元,a也称为可逆的,记为b=a-1(同样,a也为b的逆元,b也称为可逆的,记为b-1 );
注意:在一个代数系统中,并不是每个元都是可
逆的。
2018/6/13
计算机学院
10
特异元的性质
设〈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
因此,逆元也是唯一的。