离散数学代数结构部分.ppt

《离散数学代数结构部分.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三部分代数结构第五章代数系统代数结构又称为代数系统，简称代数，是抽象代数的主要研究对象。代数系统的种类很多，它们在计算机科学的自动机理论、编码理论、形式语言、时序线路、开关线路计数问题以及计算机网络纠错码的纠错能力判断、密码学、计算机理论科学等方面有着非常广泛的应用。本部分主要内容二元运算及其性质。二元运算中的特殊元素幺元，零元，逆元。代数系统的定义及其性质。定义5.1设为集合，函数称为上的二元运算，简称为二元运算。5.1节二元运算及其性质在整数集合上，对任意两个整数所进行的普通加法和乘法，都是集合上的

2、二元运算。如何判断一个运算是否为集合上的二元运算唯一性集合S中任意的两个元素都能进行这种运算，并且结果要是唯一的。封闭性集合S中任意的两个元素运算的结果都是属于S的，就是说S对该运算是封闭的例5.1设A＝{x

3、x＝，n∈N}，问在集合A上通常的乘法运算是否封闭，对加法运算呢?解：对于任意的所以乘法运算是封闭的。而对于加法运算是不封闭的,因为至少有定义5.2设*是定义在集合A上的二元运算，如果对于任意的x,y∈A，都有x*y＝y*x，则称该二元运算*是可交换的。例5.2设Q是有理数集合，*是Q上的二元运算，

4、对任意的a，b∈Q，a*b＝a+b-a·b，问运算*是否可交换。解：因为a*b＝a+b-a·b＝b+a-b·a＝b*a，所以运算*是可交换的。定义5.1设为集合，函数称为上的二元运算，简称为二元运算。5.1节二元运算及其性质在整数集合上，对任意两个整数所进行的普通加法和乘法，都是集合上的二元运算。定义5.2设*是定义在集合A上的二元运算，如果对于任意的x,y∈A，都有x*y＝y*x，则称该二元运算*是可交换的。例5.2设Q是有理数集合，*是Q上的二元运算，对任意的a，b∈Q，a*b＝a+b-a·b，问运算

5、*是否可交换。解：因为a*b＝a+b-a·b＝b+a-b·a＝b*a，所以运算*是可交换的。定义5.3设*是定义在集合A上的二元运算，如果对于任意的x，y，z∈A，都有(x*y)*z＝x*(y*z)，则称该二元运算*是可结合的，或者说运算*在A上适合结合律。例5.3设A=Z,“+”是整数中的加法：则“+”在Z中适合结合律。“。”是整数中的减法：则特取而运算“。”不满足结合律定义5.4设*是定义在集合A上的一个二元运算，如果对于任意的x∈A，都有x*x＝x，则称运算*是等幂的。例5.4设P(S)是集合S的幂

6、集，在P(S)上定义的两个二元运算，集合的“并”运算∪和集合的“交”运算∩，验证∪，∩是等幂的。解：对于任意的A∈P(S)，有A∪A＝A和A∩A＝A，因此运算∪和∩都满足等幂律。定义5.5设。和*是S上的两个二元运算，如果对任意的有例5.5在实数集R上，对于普通的乘法和加法有即乘法对加法是可分配的。定义5.6设。和*是定义在集合A上的两个可交换二元运算，如果对于任意的x，y∈A，都有则称。运算和*满足吸收律例5.6设集合N为自然数全体，在N上定义两个二元运算*和★，对于任意x，y∈N，有x*y＝max(x

7、，y)，x★y＝min(x，y)，验证运算*和★满足吸收律。解：对于任意a，b∈Na*(a★b)＝max(a，min(a，b))＝aa★(a*b)＝min(a，max(a，b))＝a因此，*和★满足吸收律。定义5.7设*是S上的二元运算，5.2节二元运算中的特殊元素1.幺元在自然数集N上加法的幺元是0，乘法的幺元是1.对于给定的集合和运算有的存在幺元，有的不存在幺元。定理5.1设*是S上的二元运算，如果S中存在关于运算*的）幺元，则必是唯一的。所以幺元是唯一的。定理5.2设*是S上的二元运算，如果S中既存

8、在关于运算*的左幺元，又存在关于运算的右幺元则S中必存在关于运算*的幺元e并且定义5.8设*是S上的二元运算，2.零元在自然数集N上普通乘法的零元是0，而加法没有零元。定理5.3设*是S上的二元运算，如果S中存在（关于运算*的）零元，则必是唯一的。所以零元是唯一的。定理5.4设*是S上的二元运算，如果S中既存在关于运算*的左零元又存在关于运算*的右零元定义5.9设*是S上的二元运算，2.逆元例5.8整数集Z上关于加法的幺元是0，对任意的整数m，它关于加法的逆元是-m,因为定理5.5设*是S上可结合的二元运

9、算，e为幺元,如果S中元素x存在（关于运算*）的逆元，则必是惟一的。所以对于可结合的二元运算，逆元是惟一的。定理5.6设*是S上可结合的二元运算，e为幺元,如果S中元素x既存在关于运算*的左逆元，又存在关于运算*的右逆元，则S中必存在x关于运算*的逆元并且解：*运算适合交换律、结合律和消去律，不适合幂等律。单位元是a，没有零元，且运算适合交换律、结合律和幂等律，不适合消去律。单位元是a，零元是b.只有a有逆元，运算不适合交换律