离散数学代数系统.ppt

1、2020/7/31,1,第三部分 代数结构,引言 代数系统 群与环 格与布尔代数,2020/7/31,2,引言,数学的三大核心领域 代数学：数学中研究数的部分 几何学：数学中研究形的部分 分析学：沟通形与数且涉及极限运算的部分 总体来说： 数学的三大类数学构成了整个数学的本体与核心。 在这一核心的周围，由于数学通过数与形这两个概念，与其它科学互相渗透，而出现了许多边缘学科和交叉学科。 现在已经拥有100多个主要分支学科。,2020/7/31,3,引言,代数学 代数学是建立在集合论基础上以代数运算为研究对象的学科。 其范畴包括： 算术、初等代数、高等代数、数论、抽象代数 代数学发展的4个阶段:

2、1文字叙述阶段2简化文字阶段 3符号代数阶段4结构代数阶段,一门科学的历史是那门科学中最宝贵的一部分，因为科学只能给我们知识，而历史却能给我们智慧。,2020/7/31,4,1 文字叙述阶段,文字叙述阶段 尚未形成任何简化的符号表达法； 代数运算法则都是采用通常的语言叙述方式来表达； 代数推理也都采用直观的方法。 古代中国: 算筹法 算筹计数 筹算开方法（九章算术 ）,2020/7/31,5,1 文字叙述阶段,而古希腊则借助于几何图形的变换方法 最典型的代表是毕达哥拉斯(Pythagoras公元前585497)几何数论方法。 1+3+5+(2n-1)=n2,不要认为简单的几何图形变换只能产生简

3、单的代数结论，恰当地利用几何图形的变换有时也会产生重要的代数结论,2020/7/31,6,2 简化文字阶段,简化文字阶段 古希腊数学后期，数学家丢番图（Diophantus,公元250年）才开始把通常的语言叙述作简化，利用简化的文字符号代替一些相对固定的代数表达式。 算术使用简化文字符号 12345678910： 平方 ： （希腊文幂”字为dumamis(YNMIS) ） 立方 ： (立方的希腊文为kubos(KYBOS) ),2020/7/31,7,3 符号代数阶段,符号代数阶段 用字母表示数，这一过程使代数学达到了现在我们看到的这种符号演算形式。 代数学不再停留在具体的数字计算，有了真正意

4、义的数学公式、运算法则，并由此进化为现代数学符号系统、现代数学公理系统。 代表数学家 德国数学家 M.Stiefel(1486-1567) 1553综合算术; 用 1 0进制小数表示实数 法国数学家 F.Viete(1540-1603) 是第一个系统使用字母表示数的人，韦达在代数方程、三角学等许多方面都作了杰出的贡献。,2020/7/31,8,4结构代数阶段,结构代数（抽象代数、近世代数） 代数学的研究对象不再是个别的数字运算，而是抽象的运算系统(如群、环、域 等)的代数结构。 事实上 不管是连续的还是离散的数学结构，常常是对 研究对象（自然数,实数,多项式,矩阵,命题,集合,图等） 定义种种

5、运算（加,减,乘;与,或,非；交,补等） 然后讨论这些对象及运算的有关性质。,2020/7/31,9,4结构代数阶段,代数系统 由集合和集合中的一个或多个运算所组成的系统（即数学结构），称为代数系统，又称代数结构或抽象代数，它是用代数的方法构造出来的数学模型。 代数系统的应用 自动机理论 编码理论 形式语义学 密码学 等,2020/7/31,10,第9章 代数系统,9.1 二元运算及性质 9.2 代数系统,2020/7/31,11,9 .1 二元运算及其性质,9.1.1 运算的定义 9.1.2 运算的表示方法 9.1.3 二元运算的主要性质 9.1.4 二元运算的特殊元素 小结,2020/7/

6、31,12,9.1.1 运算的定义,定义9.2 (P166 ) 设S是一个集合，函数f:SS称为S上的一个一元运算，简称为一元运算。 例如： Z, Q 和 R上求相反数的运算 非零有理数集Q*，非零实数集 R*上求倒数运算 复数集合C上求共轭复数的运算 幂集P(S)上, 全集为S，求绝对补运算 在 Mn(R) (n2)上求转置矩阵,2020/7/31,13,9.1.1 运算的定义,定义9.1 (P165 ) 设S是一个集合，函数f:SSS称为S上的一个二元运算，简称为二元运算。 问题： 如何验证一个运算是否为S上的二元运算？ S中任意两个元素可以进行这种运算，且结果唯一。 S中任何两个元素的运

7、算结果都属于S，即S对该运算是封闭的 。,2020/7/31,14,9.1.1 运算的定义,例9.1 (P165 ) N 上的、 Z 上的 、 R*上的、 Mn(R)上的矩阵加法和乘法 P(S)上的、 一般地： 函数f:SnS称为S上的一个n元运算。,2020/7/31,15,9.1.2 运算的表示方法,1.函数解析式 f(x1,x2,xn) 2.算符 用 * 等符号表示n元运算，称为算符。 几种形式，如： 前缀形式: (x1,x2,xn) 中缀形式: x1x2xn 后缀形式: (x1,x2,xn) ,2020/7/31,16,9.1.2 运算的表示方法,3.运算表 设S=a1,a2,an，S

8、上的一二元运算可以用运算表的形式给出：,2020/7/31,17,9.1.2 运算的表示方法,运算表的实例 例9.4：AP(1,2), , 分别为对称差和绝对补运算的运算表 （注：1,2为全集）,2020/7/31,18,9.1.2 运算的表示方法,例2： Z5 0, 1, 2, 3, 4 , , 分别为模 5 加法与乘法的运算表。,2020/7/31,19,9.1.3 二元运算的性质,定义9.39.5 设 为 S 上的二元运算, 如果对于任意的 x, yS 有x y = y x, 则称运算在 S 上满足交换律. 如果对于任意的 x, y, zS 有 (x y) z = x (y z),则称运

9、算在 S 上满足结合律. 如果对于任意的 xS 有 x x = x, 则称运算在 S 上满足幂等律. (若S中某些x满足x x x,则称x是运算的幂等元)。,2020/7/31,20,9.1.3 二元运算的性质,例:,2020/7/31,21,9.1.3 二元运算的性质,定义9.69.7 设 和 为 S 上两个不同的二元运算 如果对于任意的 x, y, zS 有 (x y) z = (x z) (y z) z (x y) = (z x) (z y) 则称 运算对 运算满足分配律. 如果 和 都可交换, 并且对于任意的 x, yS 有 x (x y) = x x (x y) = x 则称 和 运

10、算满足吸收律.,2020/7/31,22,9.1.3 二元运算的性质,2020/7/31,23,9.1.3 二元运算的性质,定义9.7 设 为集合S上二元运算，如果对于任意元素 x, y, zS, x ，都有 x y = x z y = z, y x = z x y = z 成立，则称 运算满足消去律. 例如： 普通加法和乘法满足消去律 矩阵加法满足消去律 矩阵乘法不满足消去律. 集合的并和交运算也不满足消去律,2020/7/31,24,9.1.4 二元运算的特异元素,1.单位元 定义9.8： 设 为S上的二元运算, 如果存在el（或er）S，使得对任意 xS 都有 el x = x ( 或

11、x er = x )， 则称 el ( 或 er )是 S 中关于 运算的 左 ( 或右 ) 单位元. 若 eS 关于 运算既是左单位元又是右单位元，则称 e 为 S 上关于 运算的单位元（幺元）.,2020/7/31,25,10.1.4 二元运算的特异元素,2.可逆元素及其逆元 定义9.10 令 e 为 S 中关于运算 的单位元. 对于 xS，如果存在yl（或 yr）S 使得 yl x = e（或 x yr = e）， 则称 yl ( 或 yr )是 x 的左逆元 ( 或右逆元 ). 关于 运算，若 yS 既是 x 的左逆元又是 x 的右逆元，则称 y 为 x 的逆元. 如果 x 的逆元存在

12、，就称 x 是可逆的.,2020/7/31,26,9.1.4 二元运算的特异元素,3.零元 定义 9.9 设 为 S 上的二元运算, 如果存在l ( 或r)S，使得对任意 xS 都有 l x =l ( 或 x r =r )， 则称l ( 或r )是 S 中关于 运算的 左 ( 或右) 零元. 若S关于 运算既是左零元又是右零元，则称为 S 上关于运算的零元.,2020/7/31,27,9.1.4 二元运算的特异元素,实例：,2020/7/31,28,9.1.4 二元运算的特异元素,单位元的惟一性,定理9.1：设 为S上的二元运算，el 和 er 分别为 S 中关于运算的左和右单位元，则 el

13、= er = e 为 S 上关于 运算的惟一的单位元. 证： el = el er = er el = er , 将这个单位元记作 e. 假设 e 也是 S 中的单位元，则有 e = e e = e. 惟一性得证. 类似地可以证明关于零元的惟一性定理5.2.,2020/7/31,29,9.1.4 二元运算的特异元素,逆元的惟一性,定理9.4： 设 为 S 上可结合的二元运算, e 为该运算的单位元, 对于 xS 如果存在左逆元 yl 和右逆元 yr , 则有 yl = yr= y, 且 y 是 x 的惟一的逆元. 证明：由 yl x = e 和 x yr = e 得 yl = yl e = y

14、l (x yr) = (yl x) yr = e yr = yr 令 yl = yr = y, 则 y 是 x 的逆元. 假若 yS 也是 x 的逆元, 则 y= y e = y (x y) = (y x) y = e y = y 所以 y 是 x 惟一的逆元. 说明：对于可结合的二元运算，可逆元素 x 只有惟一的逆元， 记作 x-1.,2020/7/31,30,9.1.4 二元运算的特异元素,零元的惟一性,定理9.2：设 为S上的二元运算，l 和r 分别为 S 中关于运算的左和右零元，则 l = r = 为 S 上关于 运算的惟一的单位元. 证： l = l r = r l = r , 将这

15、个单位元记作 . 假设 也是 S 中的单位元，则有 = = . 惟一性得证.,2020/7/31,31,例题分析,例： 设 运算为 Q 上的二元运算， x, yQ, x y = x+y+2xy, (1) 判断 运算是否满足交换律和结合律，并说明理由. (2) 求出 运算的单位元、零元和所有可逆元素的逆元.,解 (1) 运算可交换. 任取x, yQ, x y = x+y+2xy = y+x+2yx = y x, 运算可结合，任取x, y, zQ, (x y) z = (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x

16、 + (y+z+2yz) + 2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz,2020/7/31,32,例题分析,(2) 设 运算的单位元和零元分别为 e 和 ，则对于任意 x 有 x e = x 成立，即 x+e+2xe = x e = 0 由于 运算可交换，所以 0 是幺元.,对于任意 x 有 x = 成立，即 x+2x = x+2x =0 = 1/2 1/2为零元.,(3)给定 x，设 x 的逆元为 y, 则有 x y = 0 成立，即 x+y+2xy = 0 则:y=-x/(2x+1) (x = 1/2)是 x 的逆元( x 1/2),2020/7/31,33,

17、9.1.4二元运算的特异元素,例9.6 例9.7,2020/7/31,34,9.1.4 二元运算的特异元素,一般地， 根据二元运算表判断特异元素的方法 若某元素所在的行和列的元素排列都与表头一致，则该元素是单位元。 若某元素所在的行和列的所有元素都是这个元素本身，则该元素是零元。 为求x的逆元，检查x所在的行，找出单位元e所在的列。 如果这个列的表头元素为y，那么xy=e。 接着检查yx是否也是e。如果满足要求，则y是x的逆元；否则x没有逆元。,2020/7/31,35,9.1.4 二元运算的特异元素,练习:,2020/7/31,36,本节知识要点,函数 f：SSS 和 f：SS 分别定义了S

18、上的二元和一元运算。 使用算符表示二元和一元运算有两种表示法：解析公式与运算表。 二元运算的算律（交换律、结合律、幂等律、分配律和吸收律）及其判别方法。 二元运算的单位元、零元和逆元的定义及其唯一性。,2020/7/31,37,9.2 代数系统,9.2.1 代数系统 9.2.2 代数系统的子代数 9.2.3 代数系统的积代数,2020/7/31,38,9.2.1代数系统,定义9.12 非空集合S和S上k个运算f1,f2,fk组成的系统称为一个代数系统，简称代数，记做。 例如: ，都是代数系统。 是代数系统 是代数系统 也是代数系统,2020/7/31,39,9.2.1代数系统,带有代数常数的代数系统 Z，0 Z，0，1 定义9.13 同类型的代数系统,2020/7/31,40,9.2.2代数系统的子代数,定义9.14 设V是代数系统，B