离散数学代数系统.PPT

1、计算机科学学院计算机科学学院 刘芳刘芳2021-12-51第三部分 代数结构引言引言代数系统代数系统群与环群与环格与布尔代数格与布尔代数计算机科学学院计算机科学学院 刘芳刘芳2021-12-52引言引言数学的三大核心领域数学的三大核心领域代数学：数学中研究数的部分代数学：数学中研究数的部分几何学：数学中研究形的部分几何学：数学中研究形的部分分析学：沟通形与数且涉及极限运算的部分分析学：沟通形与数且涉及极限运算的部分总体来说：总体来说：数学的三大类数学构成了整个数学的数学的三大类数学构成了整个数学的本体与核心本体与核心。在这一核心的周围，由于数学通过数与形这两个概念，与在这一核心的周围，由于数学

2、通过数与形这两个概念，与其它科学互相渗透，而出现了许多其它科学互相渗透，而出现了许多边缘学科边缘学科和和交叉学科交叉学科。现在已经拥有现在已经拥有100多个主要分支学科。多个主要分支学科。计算机科学学院计算机科学学院 刘芳刘芳2021-12-53引言引言代数学代数学代数学是建立在集合论基础上以代数运算为研究代数学是建立在集合论基础上以代数运算为研究对象的学科。对象的学科。其范畴包括：其范畴包括：算术、初等代数、高等代数、数论、抽象代数算术、初等代数、高等代数、数论、抽象代数代数学发展的代数学发展的4个阶段个阶段: 1文字叙述阶段文字叙述阶段2简化文字阶段简化文字阶段3符号代数阶段符号代数阶段4

3、结构代数阶段结构代数阶段一门科学的历史是那门科学中最宝一门科学的历史是那门科学中最宝贵的一部分，因为科学只能给我们贵的一部分，因为科学只能给我们知识，而历史却能给我们智慧。知识，而历史却能给我们智慧。计算机科学学院计算机科学学院 刘芳刘芳2021-12-541 文字叙述阶段文字叙述阶段文字叙述阶段文字叙述阶段尚未形成任何简化的符号表达法；尚未形成任何简化的符号表达法；代数运算法则都是采用通常的语言叙述方式来表达；代数运算法则都是采用通常的语言叙述方式来表达；代数推理也都采用直观的方法。代数推理也都采用直观的方法。古代中国古代中国: 算筹法算筹法算筹计数算筹计数筹算开方法筹算开方法（九章算术九章

4、算术 ）计算机科学学院计算机科学学院 刘芳刘芳2021-12-551 文字叙述阶段文字叙述阶段而古希腊则借助于几何图形的变换方法而古希腊则借助于几何图形的变换方法 最典型的代表是毕达哥拉斯最典型的代表是毕达哥拉斯(Pythagoras公元前公元前585497)几何数论几何数论方法。方法。1+3+5+(2n-1)=n2不要认为简单的几何图形变换只能产生简单的代数不要认为简单的几何图形变换只能产生简单的代数结论，恰当地利用几何图形的变换有时也会产生结论，恰当地利用几何图形的变换有时也会产生重重要的代数结论要的代数结论 计算机科学学院计算机科学学院 刘芳刘芳2021-12-562 2 简化文字阶段简

5、化文字阶段简化文字阶段简化文字阶段古希腊数学后期，数学家古希腊数学后期，数学家丢番图丢番图（Diophantus,公元公元250年）年）才开始把通常的语言叙述作简化，利用简化的文字符号代才开始把通常的语言叙述作简化，利用简化的文字符号代替一些相对固定的代数表达式。替一些相对固定的代数表达式。算术算术使用简化文字符号使用简化文字符号12345678910： 平方 ： （希腊文幂希腊文幂”字为字为dumamis(YNMIS) ）立方 ： (立方的希腊文为立方的希腊文为kubos(KYBOS) )计算机科学学院计算机科学学院 刘芳刘芳2021-12-573 符号代数阶段符号代数阶段符号代数阶段符号代

6、数阶段用字母表示数，这一过程使代数学达到了现在我们看到的用字母表示数，这一过程使代数学达到了现在我们看到的这种符号演算形式。这种符号演算形式。代数学不再停留在具体的数字计算，有了真正意义的数学代数学不再停留在具体的数字计算，有了真正意义的数学公式、运算法则，并由此进化为现代数学符号系统、现代公式、运算法则，并由此进化为现代数学符号系统、现代数学公理系统。数学公理系统。代表数学家代表数学家德国数学家德国数学家 M.Stiefel(1486-1567) 1553综合算术综合算术; 用用 1 0进制小数表示实数进制小数表示实数 法国数学家法国数学家 F.Viete(1540-1603) 是第一个系统

7、使用字母表示数的人，韦达在代数方程、三角学等许多方面都是第一个系统使用字母表示数的人，韦达在代数方程、三角学等许多方面都作了杰出的贡献。作了杰出的贡献。计算机科学学院计算机科学学院 刘芳刘芳2021-12-584结构代数阶段结构代数阶段结构代数（结构代数（抽象代数、近世代数抽象代数、近世代数）代数学的研究对象不再是个别的数字运算，而是代数学的研究对象不再是个别的数字运算，而是抽象抽象的运算系统的运算系统(如群、环、域如群、环、域 等等)的代数结构。的代数结构。事实上事实上不管是连续的还是离散的不管是连续的还是离散的数学结构数学结构，常常是对，常常是对研究对象研究对象（自然数（自然数,实数实数,

8、多项式多项式,矩阵矩阵,命题命题,集合集合,图等）图等）定义种种定义种种运算运算（加（加,减减,乘乘;与与,或或,非；交非；交,补等）补等）然后讨论这些对象及运算的有关然后讨论这些对象及运算的有关性质性质。计算机科学学院计算机科学学院 刘芳刘芳2021-12-594结构代数阶段结构代数阶段代数系统代数系统由集合和集合中的一个或多个运算所组成的系统（即数学由集合和集合中的一个或多个运算所组成的系统（即数学结构），称为结构），称为代数系统代数系统，又称，又称代数结构或抽象代数代数结构或抽象代数，它是，它是用代数的方法构造出来的数学模型。用代数的方法构造出来的数学模型。代数系统的应用代数系统的应用自

9、动机理论自动机理论编码理论编码理论 形式语义学形式语义学密码学密码学等等计算机科学学院计算机科学学院 刘芳刘芳2021-12-510第9章 代数系统9.1 二元运算及性质二元运算及性质9.2 代数系统代数系统计算机科学学院计算机科学学院 刘芳刘芳2021-12-5119 .1 二元运算及其性质 9.1.1 运算的定义运算的定义9.1.2 运算的表示方法运算的表示方法9.1.3 二元运算的主要性质二元运算的主要性质9.1.4 二元运算的特殊元素二元运算的特殊元素小结小结计算机科学学院计算机科学学院 刘芳刘芳2021-12-5129.1.1 运算的定义运算的定义定义定义9.2 (P166 )设设S

10、是一个集合，函数是一个集合，函数f:SS称为称为S上的一个一元上的一个一元运算，简称为运算，简称为一元运算一元运算。例如：例如： Z, Q 和和 R上求相反数的运算上求相反数的运算 非零有理数集非零有理数集Q*，非零实数集，非零实数集 R*上求倒数运算上求倒数运算 复数集合复数集合C上求共轭复数的运算上求共轭复数的运算 幂集幂集P(S)上上, 全集为全集为S，求绝对补运算，求绝对补运算 在在 Mn(R) (n2)上求转置矩阵上求转置矩阵计算机科学学院计算机科学学院 刘芳刘芳2021-12-5139.1.1 运算的定义运算的定义定义定义9.1 (P165 )设设S是一个集合，函数是一个集合，函数

11、f:SSS称为称为S上的一个二上的一个二元运算，简称为元运算，简称为二元运算二元运算。问题：问题：如何验证一个运算是否为如何验证一个运算是否为S上的二元运算？上的二元运算？S中任意两个元素可以进行这种运算，且结果唯一。中任意两个元素可以进行这种运算，且结果唯一。S中任何两个元素的运算结果都属于中任何两个元素的运算结果都属于S，即即S对该运算是对该运算是封闭封闭的的 。计算机科学学院计算机科学学院 刘芳刘芳2021-12-5149.1.1 运算的定义运算的定义例例9.1 (P165 )N 上的上的、Z 上的上的 、 R*上的上的、Mn(R)上的矩阵加法和乘法上的矩阵加法和乘法P(S)上的上的、

12、一般地：一般地：函数函数f:SnS称为称为S上的一个上的一个n元运算元运算。计算机科学学院计算机科学学院 刘芳刘芳2021-12-5159.1.2 运算的表示方法运算的表示方法 1.函数解析式函数解析式f(x1,x2,xn)2.算符算符 用用 * 等符号表示等符号表示n元运算，称为算符。元运算，称为算符。几种形式，如：几种形式，如：前缀形式前缀形式: (x1,x2,xn)中缀形式中缀形式: x1x2xn后缀形式后缀形式: (x1,x2,xn) 计算机科学学院计算机科学学院 刘芳刘芳2021-12-5169.1.2 运算的表示方法运算的表示方法3.运算表运算表设设S=a1,a2,an，S上的上的

13、一一二元二元运算可以用运运算可以用运算表的形式给出：算表的形式给出：aiaia1a1a2a2anana1a2ana1a1a1a1a2a1ana2a2a1a2a2a2ananana1ana2anan计算机科学学院计算机科学学院 刘芳刘芳2021-12-5179.1.2 运算的表示方法运算的表示方法运算表的实例运算表的实例例例9.4：AP(1,2), , 分别为对称差和绝对补分别为对称差和绝对补运算的运算表运算的运算表 （注：（注：1,2为全集）为全集） 1 2 1,2 x x121,2 1 2 1,2 1 1,2 2 2 1,2 11,2 2 1 1 2 1,21,2 2 1 计算机科学学院计算

14、机科学学院 刘芳刘芳2021-12-5189.1.2 运算的表示方法运算的表示方法例例2： Z5 0, 1, 2, 3, 4 , , 分别为模分别为模 5 加法加法与乘法的运算表。与乘法的运算表。 0 1 2 3 4 0 1 2 3 4012340 1 2 3 41 2 3 4 02 3 4 0 13 4 0 1 24 0 1 2 3 0 1 2 3 4 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 计算机科学学院计算机科学学院 刘芳刘芳2021-12-5199.1.3 二元运算的性质二元运算的性质 定义定义9.39.5设设 为为 S 上的

15、二元运算上的二元运算,如果对于任意的如果对于任意的 x, y S 有有x y = y x, 则称运算则称运算 在在 S 上满足上满足交换律交换律.如果对于任意的如果对于任意的 x, y, z S 有有 (x y) z = x (y z),则则称运算称运算 在在 S 上满足上满足结合律结合律. 如果对于任意的如果对于任意的 x S 有有 x x = x, 则称运算则称运算 在在 S 上满上满足足幂等律幂等律. (若若S中某些中某些x满足满足x x x,则称则称x是运算是运算的的幂幂等元等元)。计算机科学学院计算机科学学院 刘芳刘芳2021-12-5209.1.3 二元运算的性质二元运算的性质例例

16、:集合集合运算运算Z, Q, R普通加法普通加法+普通乘法普通乘法 Mn(R)矩阵加法矩阵加法+矩阵乘法矩阵乘法 P(B)并并 交交 相对补相对补 对称差对称差 交换律交换律结合律结合律幂等律幂等律有有有有无无有有有有无无有有有有无无无无有有无无有有有有有有有有有有有有无无无无无无有有有有无无计算机科学学院计算机科学学院 刘芳刘芳2021-12-5219.1.3 二元运算的性质二元运算的性质定义定义9.69.7设设 和和 为为 S 上两个不同的二元运算上两个不同的二元运算如果对于任意的如果对于任意的 x, y, zS 有有 (x y) z = (x z) (y z) z (x y) = (z

17、x) (z y) 则称则称 运算对运算对 运算满足运算满足分配律分配律. 如果如果 和和 都可交换都可交换, 并且对于任意的并且对于任意的 x, yS 有有 x (x y) = x x (x y) = x 则称则称 和和 运算满足运算满足吸收律吸收律. 计算机科学学院计算机科学学院 刘芳刘芳2021-12-5229.1.3 二元运算的性质二元运算的性质 集合集合 运算运算分配律分配律吸收律吸收律 Z,Q,R普通加法普通加法 + 与乘法与乘法 Mn(R)矩阵加法矩阵加法 + 与乘法与乘法 P(B)并并 与交与交 交交 与对称差与对称差 集合集合 运算运算分配律分配律吸收律吸收律 Z,Q,R普通加

18、法普通加法 + 与乘法与乘法 对对 + 可分配可分配无无+ 对对 不分配不分配 Mn(R)矩阵加法矩阵加法 + 与乘法与乘法 对对 + 可分配可分配无无+ 对对 不分配不分配 P(B)并并 与交与交 对对 可分配可分配有有 对对 可分配可分配交交 与对称差与对称差 对对 可分配可分配无无 对对 不分配不分配计算机科学学院计算机科学学院 刘芳刘芳2021-12-5239.1.3 二元运算的性质二元运算的性质定义定义9.7 设设 为为集合集合S上二元运算，如果对于任意元上二元运算，如果对于任意元素素 x, y, z S, x ，都有都有 x y = x z y = z, y x = z x y =

19、 z成立，则称成立，则称 运算满足运算满足消去律消去律. 例如例如：普通加法和乘法满足消去律普通加法和乘法满足消去律矩阵加法满足消去律矩阵加法满足消去律矩阵乘法不满足消去律矩阵乘法不满足消去律. 1. 集合的并和交运算也不满足消去律集合的并和交运算也不满足消去律计算机科学学院计算机科学学院 刘芳刘芳2021-12-5249.1.4 二元运算的特异元素二元运算的特异元素1.单位元单位元定义定义9.8： 设设 为为S上的二元运算上的二元运算, 如果存在如果存在el（或（或er） S，使得，使得对任意对任意 xS 都有都有 el x = x ( 或或 x er = x )，则称则称 el ( 或或

20、er )是是 S 中关于中关于 运算的运算的 左左 ( 或或右右 ) 单位元单位元. 若若 eS 关于关于 运算既是左单位元又是右单位元，运算既是左单位元又是右单位元，则称则称 e 为为 S 上关于上关于 运算的运算的单位元单位元（幺元）幺元）.计算机科学学院计算机科学学院 刘芳刘芳2021-12-52510.1.4 二元运算的特异元素二元运算的特异元素2.2.可逆元素及其逆元可逆元素及其逆元定义定义9.10 令令 e 为为 S 中关于运算中关于运算 的单位元的单位元. 对于对于 xS，如，如果存在果存在yl（或（或 yr）S 使得使得 yl x = e（或（或 x yr = e），），则称则

21、称 yl ( 或或 yr )是是 x 的的左逆元左逆元 ( 或或右逆元右逆元 ). 关于关于 运算，若运算，若 yS 既是既是 x 的左逆元又是的左逆元又是 x 的右逆元，则称的右逆元，则称 y 为为 x 的的逆元逆元. 如果如果 x 的逆元存在，就称的逆元存在，就称 x 是是可逆的可逆的.计算机科学学院计算机科学学院 刘芳刘芳2021-12-5269.1.4 二元运算的特异元素二元运算的特异元素3.3.零元零元定义定义 9.9 设设 为为 S 上的二元运算上的二元运算, 如果存在如果存在l ( 或或r)S，使，使得对任意得对任意 xS 都有都有 l x =l ( 或或 x r =r )，则称

22、则称l ( 或或r )是是 S 中关于中关于 运算的运算的 左左 ( 或或右右) 零元零元. 若若S关于关于 运算既是左零元又是右零元，则称运算既是左零元又是右零元，则称为为 S 上关于上关于 运算的运算的零元零元.计算机科学学院计算机科学学院 刘芳刘芳2021-12-5279.1.4 二元运算的特异元素二元运算的特异元素实例：实例：集合集合运算运算Z,Q,R普通加法普通加法+普通乘法普通乘法 Mn(R)矩阵加法矩阵加法+矩阵乘法矩阵乘法 P(B)并并 交交 对称差对称差 单位元单位元零元零元逆元逆元0无无x 的逆元的逆元 x10 x 的逆元的逆元 x 1(x-1属于给定集合属于给定集合) 无

23、无X 逆元逆元 XE X的逆元的逆元 X 1（X是可逆矩阵）是可逆矩阵）B的逆元为的逆元为BB的逆元为的逆元为B无无X的逆元为的逆元为X计算机科学学院计算机科学学院 刘芳刘芳2021-12-5289.1.4 二元运算的特异元素二元运算的特异元素单位元的惟一性单位元的惟一性定理定理9.1：设设 为为S上的二元运算，上的二元运算，el 和和 er 分别为分别为 S 中关中关于运算的左和右单位元，则于运算的左和右单位元，则 el = er = e 为为 S 上关于上关于 运运算的惟一的单位元算的惟一的单位元. 证：证： el = el er = er el = er , 将这个单位元记作将这个单位元

24、记作 e. 假设假设 e 也是也是 S 中的单位元，则有中的单位元，则有 e = e e = e. 惟一性得证惟一性得证.类似地可以证明关于零元的惟一性定理类似地可以证明关于零元的惟一性定理5.2. 计算机科学学院计算机科学学院 刘芳刘芳2021-12-5299.1.4 二元运算的特异元素二元运算的特异元素逆元的惟一性逆元的惟一性定理定理9.4： 设设 为为 S 上可结合的二元运算上可结合的二元运算, e 为该运算的单位为该运算的单位元元, 对于对于 xS 如果存在左逆元如果存在左逆元 yl 和右逆元和右逆元 yr , 则有则有 yl = yr= y, 且且 y 是是 x 的惟一的逆元的惟一的

25、逆元. 证明：证明：由由 yl x = e 和和 x yr = e 得得 yl = yl e = yl (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. 计算机科学学院计算机科学学院 刘芳刘芳2021-12-5309

26、.1.4 二元运算的特异元素二元运算的特异元素零元的惟一性零元的惟一性定理定理9.2：设设 为为S上的二元运算，上的二元运算，l 和和r 分别为分别为 S 中中关于运算的左和右零元，则关于运算的左和右零元，则 l = r = 为为 S 上关于上关于 运算的惟一的单位元运算的惟一的单位元. 证：证： l = l r = r l = r , 将这个单位元记作将这个单位元记作 . 假设假设 也是也是 S 中的单位元，则有中的单位元，则有 = = . 惟一性得证惟一性得证. 计算机科学学院计算机科学学院 刘芳刘芳2021-12-531例题分析例题分析例：例： 设设 运算为运算为 Q 上的二元运算，上的

27、二元运算， x, y Q, x y = x+y+2xy, (1) 判断判断 运算是否满足交换律和结合律，并说明理由运算是否满足交换律和结合律，并说明理由. (2) 求出求出 运算的单位元、零元和所有可逆元素的逆元运算的单位元、零元和所有可逆元素的逆元.解解 (1) 运算可交换运算可交换. 任取任取x, y Q, x y = x+y+2xy = y+x+2yx = y x, 运算可结合，任取运算可结合，任取x, y, z Q, (x y) z = (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x + (y+z+2y

28、z) + 2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz计算机科学学院计算机科学学院 刘芳刘芳2021-12-532例题分析例题分析(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

29、 成立，即成立，即 x+y+2xy = 0 则则:y=-x/(2x+1) (x = 1/2)是是 x 的逆元的逆元( x 1/2)计算机科学学院计算机科学学院 刘芳刘芳2021-12-5339.1.4二元运算的特异元素二元运算的特异元素例例9.6例例9.7*abcaabcbbcaccababcaabcbbbbccbc.abcaabcbabccabc计算机科学学院计算机科学学院 刘芳刘芳2021-12-5349.1.4 二元运算的特异元素二元运算的特异元素一般地，一般地，根据二元运算表判断特异元素的方法根据二元运算表判断特异元素的方法若某元素所在的行和列的元素排列都与表头一致，则该若某元素所在的

30、行和列的元素排列都与表头一致，则该元素是元素是单位元单位元。若某元素所在的行和列的所有元素都是这个元素本身，若某元素所在的行和列的所有元素都是这个元素本身，则该元素是则该元素是零元零元。为求为求x的的逆元逆元，检查，检查x所在的行，找出单位元所在的行，找出单位元e所在的列。所在的列。 如果这个列的表头元素为如果这个列的表头元素为y，那么那么xy=e。 接着检查接着检查yx是否也是是否也是e。如果满足要求，则如果满足要求，则y是是x的逆的逆元；否则元；否则x没有逆元。没有逆元。 计算机科学学院计算机科学学院 刘芳刘芳2021-12-5359.1.4 二元运算的特异元素二元运算的特异元素练习练习:

31、*01234000000101234202413303142404321计算机科学学院计算机科学学院 刘芳刘芳2021-12-536本节知识要点本节知识要点函数函数 f：SSS 和和 f：SS 分别定义了分别定义了S上的二元上的二元和一元运算。和一元运算。 使用算符表示二元和一元运算有两种表示法：解析使用算符表示二元和一元运算有两种表示法：解析公式与运算表。公式与运算表。 二元运算的算律（交换律、结合律、幂等律、分配二元运算的算律（交换律、结合律、幂等律、分配律和吸收律）及其判别方法。律和吸收律）及其判别方法。 二元运算的单位元、零元和逆元的定义及其唯一性。二元运算的单位元、零元和逆元的定义及

32、其唯一性。计算机科学学院计算机科学学院 刘芳刘芳2021-12-5379.2 代数系统9.2.1 代数系统代数系统9.2.2 代数系统的子代数代数系统的子代数9.2.3 代数系统的积代数代数系统的积代数计算机科学学院计算机科学学院 刘芳刘芳2021-12-538 9.2.1代数系统代数系统定义定义9.12 非空集合非空集合S S和和S S上上k k个运算个运算f1,f2,fk组成的系统称为一组成的系统称为一个代数系统，简称代数，记做个代数系统，简称代数，记做。 例如例如:，都是代数系统。都是代数系统。是代数系统是代数系统是代数系统是代数系统也是代数系统也是代数系统计算机科学学院计算机科学学院 刘芳刘芳2021-12-539 9.2.1代数系统代数系统带有代数常数的代数系统带有代数常数的代数系统Z，0Z，0，1 定义定义9.13同类型的代数系统同类型的代数系统计算机科学学院计算机科学学院 刘芳刘