离散数学屈婉玲第十四章.ppt
《离散数学屈婉玲第十四章.ppt》由会员分享,可在线阅读,更多相关《离散数学屈婉玲第十四章.ppt(55页珍藏版)》请在咨信网上搜索。
1、1第五部分第五部分 代数系统简介代数系统简介主要内容主要内容l二元运算及其性质二元运算及其性质 二元运算和一元运算、二元运算性质、特异元素二元运算和一元运算、二元运算性质、特异元素l代数系统的概念代数系统的概念l几个典型的代数系统几个典型的代数系统 半群、独异点、群半群、独异点、群 环与域环与域 格与布尔代数格与布尔代数l代数系统的同构与同态代数系统的同构与同态2第十四章第十四章 代数系统简介代数系统简介主要内容主要内容二元运算及其性质二元运算及其性质l一元和二元运算定义及其实例一元和二元运算定义及其实例l二元运算的性质二元运算的性质代数系统代数系统l代数系统定义及其实例代数系统定义及其实例l
2、子代数子代数l积代数积代数代数系统的同态与同构代数系统的同态与同构314.1代数系统的基本概念代数系统的基本概念定义定义14.1设设S为集合,函数为集合,函数f:S SS 称为称为S上的上的二元运算二元运算,简称为二元运算函数简称为二元运算函数f:SS 称为称为S上的上的一元运算一元运算,简,简称一元运算称一元运算.lS 中任何元素都可以进行运算,且运算的结果惟一中任何元素都可以进行运算,且运算的结果惟一lS 中任何元素的运算结果都属于中任何元素的运算结果都属于S,即,即S 对该运算封闭对该运算封闭例例1(1)自然数集合自然数集合N上的加法和乘法是上的加法和乘法是N上的二元运算,但上的二元运算
3、,但减法和除法不是减法和除法不是(2)整数集合整数集合Z上的加法、减法和乘法都是上的加法、减法和乘法都是Z上的二元运算,上的二元运算,而除法不是求一个数的相反数是而除法不是求一个数的相反数是Z上的一元运算上的一元运算.(3)非零实数集非零实数集R*上的乘法和除法都是上的乘法和除法都是R*上的二元运算,而上的二元运算,而加法和减法不是求倒数是加法和减法不是求倒数是R*上的一元运算上的一元运算.4实例实例(4)设设Mn(R)表示所有表示所有n 阶阶(n2)实矩阵的集合,即实矩阵的集合,即矩阵加法、乘法是矩阵加法、乘法是Mn(R)上的二元运算上的二元运算.转置是一元运算转置是一元运算.(5)S为任意
4、集合,则为任意集合,则、为为P(S)上二元运算上二元运算.运算运算为一元运算为一元运算.(6)SS为为S上的所有函数的集合,则合成运算上的所有函数的集合,则合成运算 为为SS上二元运算上二元运算.求反函数不一定是一元运算求反函数不一定是一元运算.5二元与一元运算的表示二元与一元运算的表示1算符算符可以用可以用,等符号表示二元或一元运算,称为算符等符号表示二元或一元运算,称为算符.对二元运算对二元运算,如果,如果x 与与y 运算得到运算得到z,记做,记做xy=z对一元运算对一元运算,x的运算结果记作的运算结果记作 x.2表示二元或一元运算的方法表示二元或一元运算的方法:解析公式和运算表解析公式和
5、运算表公式表示公式表示例例设设R为实数集合,如下定义为实数集合,如下定义R上的二元运算上的二元运算:x,yR,x y=x.那么那么3 4=3,0.5(3)=0.56运算表:表示有穷集上的一元和二元运算运算表:表示有穷集上的一元和二元运算 运算表运算表 二元运算的运算表二元运算的运算表一元运算的运算表一元运算的运算表7 例例2 设设S=P(a,b),S上的上的 和和 运算运算的运算表如下的运算表如下 运算表的实例运算表的实例8二元运算的性质二元运算的性质定义定义14.2-4设设为为S上的二元运算上的二元运算,(1)若对任意若对任意x,yS 有有xy=yx,则称运算在则称运算在S上满足上满足交换律
6、交换律.(2)若对任意若对任意x,y,zS有有(xy)z=x(yz),则称运算在则称运算在S上满足上满足结结合律合律.(3)若对任意若对任意xS 有有xx=x,则称运算在则称运算在S上满足上满足幂等律幂等律.定义定义14.5-6设设和和 为为S上两个不同的二元运算上两个不同的二元运算,(1)若对任意若对任意x,y,zS有有(x y)z=(xz)(yz),z(x y)=(zx)(zy),则称则称运算对运算对 运算满足运算满足分配律分配律.(2)若若 和和 都可交换都可交换,且对任意且对任意x,yS有有x(x y)=x,x(xy)=x,则称则称和和 运算满足运算满足吸收律吸收律.9实例实例Z,Q,
7、R分别为整数、有理数、实数集;分别为整数、有理数、实数集;Mn(R)为为n阶实阶实矩阵集合矩阵集合,n 2;P(B)为幂集;为幂集;AA为从为从A到到A的函数集,的函数集,|A|2集合集合运算运算交交换换律律结结合律合律幂幂等律等律Z,Q,R普通加法普通加法+普通乘法普通乘法 有有有有有有有有无无无无Mn(R)矩矩阵阵加法加法+矩矩阵阵乘法乘法 有有无无有有有有无无无无P(B)并并 交交 相对补相对补 对称差对称差 有有有有无无有有有有有有无无有有有有有有无无无无AA函数复合函数复合 无无有有无无10集合集合运算运算分配律分配律吸收律吸收律Z,Q,R普通加法普通加法+与乘法与乘法 对对+可分配
8、可分配+对对 不分配不分配无无Mn(R)矩矩阵阵加法加法+与乘法与乘法 对对+可分配可分配+对对 不分配不分配无无P(B)并并 与交与交 对对 可分配可分配 对对 可分配可分配有有交交 与与对对称差称差 对对 可分配可分配无无实例实例Z,Q,R分别为整数、有理数、实数集;分别为整数、有理数、实数集;Mn(R)为为n阶实阶实矩阵集合矩阵集合,n 2;P(B)为幂集;为幂集;AA为从为从A到到A的函数集,的函数集,|A|211特异元素:单位元、零元特异元素:单位元、零元定义定义14.7-9设设为为S上的二元运算上的二元运算,(1)如果存在如果存在el(或或er)S,使得对任意,使得对任意xS 都有
9、都有 elx=x(或或xer=x),则称则称el(或或er)是是S中关于中关于运算的运算的左左(或或右右)单位元单位元.若若eS关于关于运算既是左单位元又是右单位元,则称运算既是左单位元又是右单位元,则称e为为S上上关于关于运算的运算的单位元单位元.单位元也叫做单位元也叫做幺元幺元.(2)如果存在如果存在 l(或或 r)S,使得对任意,使得对任意xS 都有都有 l x=l(或或x r=r),则称则称 l(或或 r)是是S 中关于中关于运算的运算的左左(或或右右)零元零元.若若 S 关于关于运算既是左零元又是右零元,则称运算既是左零元又是右零元,则称 为为S上关上关于运算于运算的的零元零元.12
10、可逆元素和逆元可逆元素和逆元(3)设设为为S上的二元运算上的二元运算,令令e为为S中关于运算中关于运算 的单位元的单位元.对于对于xS,如果存在,如果存在yl(或或yr)S使得使得 ylx=e(或(或xyr=e)则称则称yl(或或yr)是是x的的左逆元左逆元(或(或右逆元右逆元).关于关于运算,若运算,若yS 既是既是x 的左逆元又是的左逆元又是x 的右逆元,则称的右逆元,则称y为为x的的逆元逆元.如果如果x 的逆元存在,就称的逆元存在,就称x 是是可逆的可逆的.可以证明:可以证明:l对于给定二元运算,单位元或零元如果存在,则是唯一的对于给定二元运算,单位元或零元如果存在,则是唯一的.l对于可
11、结合的二元运算,给定元素若存在逆元,则是唯一对于可结合的二元运算,给定元素若存在逆元,则是唯一的逆元的逆元13实例实例集合集合运算运算单位元单位元零元零元逆元逆元Z,Q,R普通加法普通加法+普通乘法普通乘法 01无无0 x逆元逆元 xx逆元逆元x 1(x 1 给定集合给定集合)Mn(R)矩矩阵阵加法加法+矩矩阵阵乘法乘法 n阶全阶全0矩阵矩阵n阶单位矩阵阶单位矩阵无无n阶全阶全0矩阵矩阵X逆元逆元 XX的逆元的逆元X 1(X可逆)可逆)P(B)并并 交交 对称差对称差 BB无无的逆元为的逆元为B的逆元为的逆元为BX的逆元为的逆元为X消去律消去律定定义义14.10设设 为为S上的二元运算,如果上
12、的二元运算,如果对对于任意的于任意的x,y,z S满满足以下条件:足以下条件:(1)若若x y=x z且且x,则则y=z;(2)若若y x=z x且且x,则则y=z;称称运算运算满满足足消去律消去律,其中,其中(1)为为左消去律左消去律,(2)为为右消去律右消去律l注意被消去的注意被消去的x 不能是运算的零元不能是运算的零元 整数集合上的加法和乘法整数集合上的加法和乘法满满足消去律足消去律P(S)上的并和交一般不上的并和交一般不满满足消去律足消去律.对对称差运算称差运算 满满足消去律足消去律,A,B,C P(S),都有,都有 A B=A CB=C B A=C AB=C1415代数系统代数系统定
13、义定义14.11非空集合非空集合S和和S上上k个一元或二元运算个一元或二元运算f1,f2,fk组组成的系统称为成的系统称为代数系统代数系统,简称代数,记做简称代数,记做.实例:实例:(1),是代数系统,是代数系统,+和和分别表示普通分别表示普通加法和乘法加法和乘法.(2)是代数系统,和是代数系统,和分别表示分别表示n 阶阶(n2)实矩实矩阵的加法和乘法阵的加法和乘法.(3)是代数系统,是代数系统,Zn0,1,n-1,和和 分别表示分别表示模模n的加法和乘法,对于的加法和乘法,对于x,yZn,x y=(xy)modn,x y=(xy)modn(4)是代数系统,是代数系统,和和 为并和交,为并和交
14、,为绝对补为绝对补16代数系统的成分与表示代数系统的成分与表示构成代数系统的成分:构成代数系统的成分:l集合(也叫载体,规定了参与运算的元素)集合(也叫载体,规定了参与运算的元素)l运算(这里只讨论有限个二元和一元运算)运算(这里只讨论有限个二元和一元运算)l代数常数(通常是与运算相关的特异元素:如单位元等)代数常数(通常是与运算相关的特异元素:如单位元等)研究代数系统时,如果把运算具有它的特异元素也作为系统研究代数系统时,如果把运算具有它的特异元素也作为系统的性质之一,那么这些特异元素可以作为系统的成分,叫做的性质之一,那么这些特异元素可以作为系统的成分,叫做代数常数代数常数.例如:代数系统
15、例如:代数系统:集合:集合Z,运算运算+,代数常数代数常数0代数系统代数系统:集合:集合P(S),运算运算和和,无代数常数,无代数常数17代数系统的表示代数系统的表示(1)列出所有的成分:集合、运算、代数常数(如果存在)列出所有的成分:集合、运算、代数常数(如果存在)如如,(2)列出集合和运算,在规定系统性质时不涉及具有单位元列出集合和运算,在规定系统性质时不涉及具有单位元的性质(无代数常数)的性质(无代数常数)如如,(3)用集合名称简单标记代数系统用集合名称简单标记代数系统在前面已经对代数系统作了说明的前提下使用在前面已经对代数系统作了说明的前提下使用如代数系统如代数系统Z,P(B)18同类
16、型与同种代数系统同类型与同种代数系统定义定义14.12(1)如果两个代数系统中运算的个数相同,对应运算的元数相如果两个代数系统中运算的个数相同,对应运算的元数相同,且代数常数的个数也相同,则称它们是同,且代数常数的个数也相同,则称它们是同类型的同类型的代数代数系统系统.(2)如果两个同类型的代数系统规定的运算性质也相同,则称如果两个同类型的代数系统规定的运算性质也相同,则称为为同种的同种的代数系统代数系统.例如例如V1=,V2=,为为n 阶全阶全0矩阵,矩阵,E为为n 阶单位矩阵阶单位矩阵,V3=lV1,V2,V3是同类型的代数系统,它们都含有是同类型的代数系统,它们都含有2个二元运算个二元运
17、算,2个代数常数个代数常数.lV1,V2是同种的代数系统,是同种的代数系统,V1,V2与与V3不是同种的代数系统不是同种的代数系统19V1V2V3+可交可交换换、可、可结结合合可交可交换换、可、可结结合合+满足消去律满足消去律满足消去律满足消去律对对+可分配可分配+对对不可分配不可分配+与与没有吸收律没有吸收律+可交可交换换、可、可结结合合可交可交换换、可、可结结合合+满足消去律满足消去律不满足消去律不满足消去律对对+可分配可分配+对对不可分配不可分配+与与没有吸收律没有吸收律可交可交换换、可、可结结合合可交换、可结合可交换、可结合不满足消去律不满足消去律不满足消去律不满足消去律对对可分配可分
18、配对对可分配可分配与与满足吸收律满足吸收律运算性质比较运算性质比较2014.2几个典型的代数系统几个典型的代数系统主要内容主要内容l半群、独异点与群半群、独异点与群l环与域环与域l格与布尔代数格与布尔代数21半群、独异点与群的定义半群、独异点与群的定义定义定义14.13(1)设设V=是代数系统,是代数系统,为二元运算,如果为二元运算,如果 运算是可运算是可结合的,则称结合的,则称V为为半群半群.(2)设设V=是半群,若是半群,若eS是关于是关于 运算的单位元,则称运算的单位元,则称V 是是含幺半群含幺半群,也叫做,也叫做独异点独异点.有时也将独异点有时也将独异点V 记作记作V=.(3)设设V=
19、是独异点,是独异点,e S关于关于 运算的单位元,若运算的单位元,若 a S,a 1 S,则称,则称V是是群群.通常将群记作通常将群记作G.22实例实例例例1(1),都是半群,都是半群,+是普通加是普通加法法.这些半群中除这些半群中除外都是独异点外都是独异点(2)设设n是大于是大于1的正整数,的正整数,和和都是半都是半群,也都是独异点,其中群,也都是独异点,其中+和和分别表示矩阵加法和矩阵分别表示矩阵加法和矩阵乘法乘法(3)为半群,也是独异点,其中为半群,也是独异点,其中 为集合对称差运算为集合对称差运算(4)为半群,也是独异点,其中为半群,也是独异点,其中Zn=0,1,n 1,为模为模n加法
20、加法(5)为半群,也是独异点,其中为半群,也是独异点,其中为函数的复合运算为函数的复合运算(6)为半群,其中为半群,其中R*为非零实数集合,为非零实数集合,运算定义如运算定义如下:下:x,y R*,xy=y半群:半群:上的上的字代数和语言字代数和语言例例2设设 是有是有穷穷字母表,字母表,k N,定,定义义下述集合:下述集合:k=a1a2ak|ai 是是 上所有上所有长长度度为为k的串的集合的串的集合.当当k=0时时,0=,表示空表示空串串.令令表示表示 上所有有限上所有有限长长度的串的集合,度的串的集合,+=*则则表示表示 上所有上所有长长度至少度至少为为1的有限串的集合的有限串的集合.在在
21、*上可以定上可以定义义串的串的连连接运算,接运算,1,2 *,1=a1a2am,2=b1b2bn有有 1 2=a1a2amb1b2bn显显然然*关于关于连连接运算构成一个独异点接运算构成一个独异点,称称为为 上的字代数上的字代数.上上的的语语言言L就是就是*的一个子集的一个子集.23群码群码例例3某二某二进进制制码码的的码码字字x=x1x2x7由由7位构成,位构成,其中其中x1,x2,x3和和x4为为数据位数据位,x5,x6和和x7为为校校验验位,且位,且满满足:足:x5=x1 x2 x3 x6=x1 x2 x4x7=x1 x3 x4这这里的里的 是模是模2加法加法.设设G为为所有所有码码字构
22、成的集合,在字构成的集合,在G上定上定义义二元运算如下:二元运算如下:x,y G,x y=z1z2.z7,zi=xi yi,i=1,2,7.那么那么构成群构成群.这样这样的的码码称称为为群群码码2425群的相关概念及子群群的相关概念及子群有限群有限群:若群:若群G是有是有穷穷集,集,则则称称G是有限群,否是有限群,否则则称称为为无限群无限群群群G的的阶阶:群:群G含有的元素数,有限群含有的元素数,有限群G的的阶记阶记作作|G|.交交换换群群或或阿阿贝贝尔尔(Abel)群群:群中运算可交:群中运算可交换换实实例:例:和和是无限群,是无限群,是是n阶阶群群上述所有的群都是交上述所有的群都是交换换群
23、,但群,但n阶阶(n 2)实实可逆矩可逆矩阵阵的集合的集合(是(是Mn(R)的真子集)关于矩的真子集)关于矩阵阵乘法构成的群是非交乘法构成的群是非交换换群群子群子群:群:群G的非空子集的非空子集H关于群的运算构成群,称关于群的运算构成群,称为为G的子群的子群.实实例:例:H=nZ=nk|k Z,n为给为给定自然数,是定自然数,是的子群的子群.当当n=0和和1时时,子群分子群分别别是是0和和Z,称,称为为平凡子群平凡子群;2Z由能被由能被2整除的全体整数构成,也是子群整除的全体整数构成,也是子群.群的直积群的直积定定义义14.14设设G1=和和G2=是群,是群,和和 分分别为别为它它们们的二元运
24、算,在集合的二元运算,在集合A B上定上定义义新的二元运算新的二元运算,,A B,有,有=称称G=为为G1与与G2的的直直积积,记记作作G1 G2.例例4G1,G2分分别为别为模模2加和模加和模3加群,它加群,它们们的直的直积积运算运算26 27环与域环与域 定义定义10.15设设是代数系统,是代数系统,+和和是二元运算是二元运算.如果满足如果满足以下条件以下条件:(1)构成交换群构成交换群(2)构成半群构成半群(3)运算关于运算关于+运算适合分配律运算适合分配律则称则称是一个是一个环环.通常称通常称+运算为环中的运算为环中的加法加法,运算为环中的运算为环中的乘法乘法.定义定义14.16设设是
25、环,若是环,若(1)环中乘法环中乘法可交换;可交换;(2)R中至少含有两个元素中至少含有两个元素.且且 aR 0,都有,都有a1R;则称则称R是是域域.l0指加法单位元,指加法单位元,a1指指a的乘法逆元的乘法逆元28环与域的实例环与域的实例例例5(1)整数集、有理数集、实数集和复数集关于普通的加法和整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环,分别称为乘法构成环,分别称为整数环整数环Z,有理数环有理数环Q,实数环实数环R 和和复数环复数环C.Q、R和和C也称为有理数域、也称为有理数域、实数域实数域、复数复数域域.(2)n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)关于矩阵的加
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 屈婉玲 第十四
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。