《集合映射与运算课件.ppt》由会员分享，可在线阅读，更多相关《集合映射与运算课件.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、集合映射与运算集合映射与运算第1页，此课件共76页哦使用教材使用教材书 名：离散数学（第三版）“十一五”国家规划教材主 编：邓辉文出版社：清华大学出版社讲 授：第1章 _ 第6章第2页，此课件共76页哦参考书目参考书目1 1、邵学才、邵学才.离散数学（第二版）.清清华大学出版社华大学出版社.(.(应用型规划教材应用型规划教材)2 2、周忠荣、周忠荣.离散数学及其应用.清华清华大学出版社大学出版社.3 3、王礼萍、王礼萍.离散数学简明教程.清华清华大学出版社大学出版社.(.(高职教材高职教材)4 4、耿素云、耿素云,屈婉玲屈婉玲.离散数学（修订版）.高等教育出版社高等教育出版社.(.(十五规划教
2、材，十五规划教材，北京大学北京大学)第3页，此课件共76页哦考核方式考核方式期末成绩期末成绩=平时成绩平时成绩+期末试卷成绩期末试卷成绩 平时成绩平时成绩20分分 平时成绩平时成绩=出勤出勤+小测验小测验+作业作业 出勤出勤=10 小测验小测验=5 作业作业=5（独立、自主独立、自主）期末试卷成绩期末试卷成绩80分。分。第4页，此课件共76页哦研究对象研究对象 离散数学是研究离散量的结构及其相离散数学是研究离散量的结构及其相互之间关系的一门学科，它与当今计算机互之间关系的一门学科，它与当今计算机所处理的对象相一致。所处理的对象相一致。离散数学是研究计算机科学的基离散数学是研究计算机科学的基本数
3、学工具和最合适的理论手段；是本数学工具和最合适的理论手段；是计算机类专业的重要课程。计算机类专业的重要课程。第5页，此课件共76页哦学习目的学习目的 离散数学是计算机及相关专业的一门核心课程，不是一门纯数学课程，而是计算机学科的专业基础课程。1、为后继课程提供必要的数学基础 2、培养学生抽象思维能力和严密的逻辑推理能力。第6页，此课件共76页哦基本内容（基本内容（1）一、集合与关系：是离散数学研究的重点内容 1、Chapter 1 集合、映射与运算：集合是现代数学的最基本概念，映射是现代数学的基本概念，是本书的重点。2、Chapter 2 关系：是刻画联系的数学模型。二、数理逻辑：研究思维形式
4、及思维规律尤其是推理的学科。1、Chapter 3 命题逻辑：研究的主要对象是命题。2、Chapter 4 谓词逻辑：研究原子命题的内部形式结构及其逻辑关系。第7页，此课件共76页哦基本内容（基本内容（2）三、代数结构：研究有一般元素组成的集合上的运算，以及运算满足一些给定的数学结构的性质。1、Chapter 5(1)代数结构：计算机系统本身就是一种代数结构。2、Chapter 5(2)群、环和域：在形式语言与自动机理论学科中发挥作用。3、Chapter 5(3)格与布尔代数：在自动推理和逻辑电路设计的分析和优化等问题中得到应用。四、图论：广泛应用与解决现实问题。1、Chapter 6 图论：
5、主要研究数据结构中图的相关性质。2、Chapter 7 几类特殊的图：介绍生活和研究中实际的图论的问题。第8页，此课件共76页哦第第1章章 集合、映射与运算集合、映射与运算1.1集合的有关概念集合的有关概念1.2映射的有关概念映射的有关概念1.3运算的定义及性质运算的定义及性质1.4集合的运算集合的运算1.5集合的划分与覆盖集合的划分与覆盖第9页，此课件共76页哦第第1章章 集合、映射与运算集合、映射与运算集合是现代数学的最基本概念.映射又称为函数,它是现代数学的基本概念,可以借助于集合下定义.运算本质上是映射,但有其特殊性.(关系也是集合)集合、映射、运算及关系是贯穿于本书的一条主线.第10
6、页，此课件共76页哦1.1.1 集合集合 集合（set）:是指具有某种特定性质的对象汇集成的一个整体。元素（element）：集合中的每一个对象称为集合的元素。通常用大写字母表示集合，用小写字母表示集合中的元素。在数学中常用 表示整体.在讨论集合时，为避免出现某些悖论，应指定讨论范围，这个范围也是一个集合，称为全集或论域，记作U。文氏图用矩形框表示。A第11页，此课件共76页哦隶属关系隶属关系集合与集合中元素的关系隶属关系给定一个集合A，（1）若x是集合A中的元素，记作xA，读作x属于A；（2）若x不是集合A中的元素，则记作xA，读作x不属于A。说明：读作属于；读作不属于例:A=a,b,c,d
7、，则有b A，e A第12页，此课件共76页哦特殊集合表示特殊集合表示几类特殊集合的表示：几类特殊集合的表示：nN 自然数集合自然数集合,包括数包括数0；nZ 整数集合；整数集合；nQ 有理数集合；有理数集合；nR 实数集合；实数集合；nC 复数集合复数集合.第13页，此课件共76页哦集合的表示集合的表示 列举法列举法 就是把集合中的所有元素一一列举出来，或列出足够多的元素以反映出集合中成员的特征，元素之间用逗号分开，并用花括号括起来。如：A=a1，a2，an B=0，2，4，6，2n，。第14页，此课件共76页哦集合的表示集合的表示 描述法描述法 是指把集合中的元素所满足的条件或具有的性质描
8、述出来，即将条件或性质用文字或符号在花括号内竖线后面表示出来。一般形式为：A=A=x x|x x 满足的条件或具有的性质满足的条件或具有的性质 如：A=x|x 1=0，xR B=x|x是英文字母，x元音第15页，此课件共76页哦集合的表示集合的表示 递归法递归法 是指通过计算规则定义集合中的元素。首先给出该集合的初始元素；然后给出由集合中已知元素构造其他元素的方法；最后强调有限次使用前面的步骤得到的元素是集合中仅有的元素。如：设a0=1,a1=1,an+1=an+an-1,A=a0,a1,a2,=akk0。第16页，此课件共76页哦集合的表示集合的表示 巴科斯范式巴科斯范式(BNF)表示法表示
9、法 BNF常用来定义高级程序设计语言的标识符或表达式集合。文氏图法文氏图法(John Venn)首先画一个大矩形表示全集，然后在矩形内画一些圆，用圆的内部表示集合，集合之间的相互关系和有关的运算可以用文氏图给予形象的描述。第17页，此课件共76页哦集合的特性集合的特性 确定性确定性 确定性是指一旦给定了集合确定性是指一旦给定了集合A A，对于任意元素，对于任意元素a a，我们就，我们就可以准确地判定可以准确地判定a a是否在是否在A A中。中。如：如：A=A=x x|x x是自然数，且是自然数，且x x100100则必有则必有3030 A A，101101 A A 互异性互异性 互异性是指集合
10、中的元素之间是彼此不同的，即集合中不互异性是指集合中的元素之间是彼此不同的，即集合中不允许出现重复的元素。允许出现重复的元素。如：集合如：集合 A=a,b,c,c,b,d A=a,b,c,c,b,d 应为应为 A=a,b,c,dA=a,b,c,d第18页，此课件共76页哦集合的特性集合的特性 无序性无序性 无序性是指集合中的元素之间没有次序关系。在不特别无序性是指集合中的元素之间没有次序关系。在不特别说明情况下，我们所讨论的集合都不是多重集。说明情况下，我们所讨论的集合都不是多重集。如：如：A=A=a a,a a,b b,b b,c c 与与 A=A=a a,b b,c c,a a,b b 相
11、同相同 抽象性抽象性 抽象性是指集合中元素是抽象的，甚至可以是集合。抽象性是指集合中元素是抽象的，甚至可以是集合。如：如：A=a,a,b,b,c；第19页，此课件共76页哦相关概念相关概念有限集有限集 由有限个元素由有限个元素a1,an组成的集合称为有限集。组成的集合称为有限集。基数（或势）基数（或势）若集合若集合A是有限集，则集合是有限集，则集合A中的元素个数称为集合中的元素个数称为集合A的基的基数（或势），通常记作数（或势），通常记作|A|。无限集无限集 无限集是指由无限个元素组成的集合。无限集是指由无限个元素组成的集合。空集空集 不含有任何元素的集合是空集。记不含有任何元素的集合是空集。
12、记或或。第20页，此课件共76页哦1.1.2 子集子集子集子集集合间的包含关系集合间的包含关系 给定两个集合A和B，若A中的任意元素都属于B，则称A是B的子集，或称A包含在B，或称B包含A，通常记作A B，或BA。（若任意aA，必有aB，则A B）若若A A不是不是B B的子集，则集合的子集，则集合A A中至少有一中至少有一个元素不属于个元素不属于B B。第21页，此课件共76页哦子集定理子集定理1-1 对于任意的集合对于任意的集合A，有，有 A。1-2 设设A、B、C是任意的集合，则有是任意的集合，则有自反性：自反性：A A.（任意集合是其子集）（任意集合是其子集）反对称性：反对称性：A B
13、,B A A=B.传递性：传递性：A B,B C A C.1-3 A=B 的充要条件是的充要条件是A B 且且 B A第22页，此课件共76页哦真子集真子集 若若A A B B，且，且A A B B，则称，则称A A是是B B的真子集，通常记作的真子集，通常记作A A B B。（若。（若A A是是B B的真子集，则的真子集，则B B中至少有一个元素不属于中至少有一个元素不属于A A）注意区别：注意区别：与 的不同问题：由由由由A B,B C C可否得出可否得出A C C?解：不成立解：不成立解：不成立解：不成立,如如A=a a,b,B=a a,b b,c c,C=a a,a a,b b,c.第
14、23页，此课件共76页哦1.1.3 幂集幂集 设设X X是一个集合，由是一个集合，由X X的的所有所有子集作为元素构子集作为元素构成的集合称为成的集合称为X X的幂集，记以的幂集，记以P P(X)(X)或或2 2X X。定理定理 设设A是一个有限集且是一个有限集且|A|=n，则，则|P(A)|=2n第24页，此课件共76页哦幂集示例幂集示例X X=a a,b b P P(X X)=)=,a a,b b,a a,b b.P P()=)=,.习题习题1.1(7)1.1(7)第25页，此课件共76页哦1.1.4 n元组元组 将将n n个元素个元素x x1 1,x x2 2,x xn n按一定顺序排列
15、就得到按一定顺序排列就得到一个一个n n元元(有序有序)组组.记为：记为：n=2n=3一般说来一般说来一般说来一般说来(x x,y)(y y,x).第26页，此课件共76页哦序偶序偶2元组常称为有序对或序偶元组常称为有序对或序偶.注意区别(a,b,c),(a,b),c),(a,(b,c)的不同.第27页，此课件共76页哦1.1.5 笛卡儿积笛卡儿积设设A1，A2，An是集合，称集合是集合，称集合为为A1，A2，An的笛卡儿积（直积，叉积）的笛卡儿积（直积，叉积）第28页，此课件共76页哦笛卡儿积定理笛卡儿积定理 A=B =例：设例：设A=a,b,B=1,2,C=,求求A B,B A,A B C
16、,B C.解：解：A A B=(a a,1),(b b,1),(,1),(a a,2),(b b,2).B A A=(1,=(1,a),(1,b),(2,),(2,a a),(2,b).A A B B C=(=(a,1,1,),(),(b b,1,),(a a,2,2,),(),(b,2,2,).).B C=C=(1,(1,),(2,),(2,)第29页，此课件共76页哦1.2 映射的有关概念映射的有关概念 映射就是函数，研究的是任意两个集映射就是函数，研究的是任意两个集合之间的一种对应关系。合之间的一种对应关系。映射是现代数学中的基本概念。函数映射是现代数学中的基本概念。函数在信息科学中得到
17、了充分的应用。在信息科学中得到了充分的应用。与集合一样，映射贯穿本书的所有内与集合一样，映射贯穿本书的所有内容，深刻理解映射的有关内容，对于其他容，深刻理解映射的有关内容，对于其他内容的学习是至关重要的。内容的学习是至关重要的。第30页，此课件共76页哦1.2.1 映射的定义映射的定义 任意给定两个集合任意给定两个集合A和和B，若存在对应法则，若存在对应法则 f，使得对于使得对于任意任意x A，均存在，均存在唯一唯一的的y B与它对应，与它对应，则称则称 f 是集合是集合A到到B的一个映射，或称的一个映射，或称A到到B的一个的一个函数，记为函数，记为 f:AB。AB第31页，此课件共76页哦映
18、射的两个特点映射的两个特点 假定假定 f:AB,y=f(x),通常把通常把x称为自变量，其取值范围称为称为自变量，其取值范围称为定定义域记为义域记为dom f；将；将y称为因变量，其取值范围称为值域，记为称为因变量，其取值范围称为值域，记为ran f。全函数全函数.映射映射f的定义域是集合的定义域是集合A,记为记为dom f=A；唯一性唯一性唯一性唯一性.对于任意对于任意xA,对应于对应于B中唯一的元素中唯一的元素f(x),x为为f的自变量的自变量(也称为原像也称为原像),f(x)称为称为x在映射在映射f下的像下的像,通常记为通常记为y=f(x).第32页，此课件共76页哦映射的表示映射的表示
19、（1）解析表达式）解析表达式（2）图示）图示（3）表格法）表格法函数符号的选取函数符号的选取:f,g,F,G,sin,exp,main,add,average,第33页，此课件共76页哦B BA A （读作（读作B B上上A A）定义）定义 对于集合对于集合A和和B，用，用BA表示表示A到到B的所有映射组的所有映射组成的集合，即成的集合，即定理：定理：对于集合对于集合A和和B，若，若|A|=m，|B|=n，则，则|BA|=nm。教材教材P7例题例题1-5第34页，此课件共76页哦1.2.2 映射的性质映射的性质1、单射、单射 假设假设f:AB,如果对任意如果对任意x1,x2 A,由由f(x1)
20、=f(x2)可推出可推出x1=x2,则称则称f是是A到到B的单射的单射,或称或称f是是A到到B的的一对一映射。一对一映射。例：设例：设f f:NN:NN，f f(x)=2x,(x)=2x,则则f f是是N N到到N N的单射，试证明之。的单射，试证明之。第35页，此课件共76页哦1.2.2 映射的性质映射的性质2、满射、满射假设假设f:AB，如果对任意，如果对任意y B,均存在均存在x A，使得，使得y=f(x)，则称，则称f是是A到到B的满射，或称的满射，或称f是是A到到B的映上的映上(onto)的映射。的映射。例：例：设设f:ZN,f(x)=|x|,f:ZN,f(x)=|x|,则则f f是
21、是Z Z到到N N的满射。的满射。第36页，此课件共76页哦1.2.2 映射的性质映射的性质3、双射、双射假设假设f:AB，f 既是单射又是满射，则称既是单射又是满射，则称f是是A到到B的双射的双射,或或称称f 是是A到到B的一的一 一对应。一对应。例：试建立一个例：试建立一个Z到到N的一一的一一对应。对应。2x x0f(x)=2|x|-1 x0 习题习题1.2(2)1.2(2)第37页，此课件共76页哦置换的定义置换的定义设设A是有限集合是有限集合,A到到A的双射称为的双射称为A上的置换上的置换例如：写出例如：写出A=1，2，3上的所有置换。上的所有置换。(个数：个数：n!)第38页，此课件
22、共76页哦1.2.3 逆映射逆映射定义：设f:AB,若将对应关系f逆转后能得出一个B到A的映射,则称该映射为f的逆映射,记为f-1.定理：设定理：设f:AB，则，则f的逆映射存在的充的逆映射存在的充要条件是要条件是f是双射是双射.第39页，此课件共76页哦1.2.4 复合映射复合映射定理定理 设设f f:A A B B,g g:B B C C，对于任意，对于任意 x x A A，令，令h h(x x)=)=g g(f f(x x)则则h h是集合是集合A A到集合到集合C C的映射。的映射。xy=f(x)z=g(y)=g(f(x)第40页，此课件共76页哦1.2.4 复合映射复合映射定义：定义
23、：设设f f:A A B B,g g:B B C,C,对于任意对于任意 x x A,A,h h(x x)=)=g g(f f(x x)则称则称h h为为f f和和g g的复合映射或复合函数，的复合映射或复合函数，记为记为f fg g 重点：重点：(f fg g)(x x)=g(f(x)abc123 第41页，此课件共76页哦复合映射例题复合映射例题注意：要保证复合映射有意义，必须注意：要保证复合映射有意义，必须 f f(A A)dom(dom(g g)例例2 2：设设R R到到R R有两个映射有两个映射f f和和g g，定义如下：，定义如下：f(x)=xf(x)=x2 2,g(x),g(x)=
24、x+2=x+2，分别计算复合映射，分别计算复合映射f fg g和和g g g gf f f f注意：一般来说，即使复合映射均有意义，也不能保证注意：一般来说，即使复合映射均有意义，也不能保证注意：一般来说，即使复合映射均有意义，也不能保证注意：一般来说，即使复合映射均有意义，也不能保证f f f f g g g g =g g g g f f f f成立成立成立成立 第42页，此课件共76页哦恒等映射恒等映射 设设A A是集合，令是集合，令f f:A:AA,A,f f(x x)=)=x x，称称f f为集合为集合A A上的恒等映射上的恒等映射(identity(identity function
25、 on A)function on A)，记为，记为IA 显然恒等映射是唯一存在的。显然恒等映射是唯一存在的。【定理定理1-9】若若f:A A B B是双射，则有是双射，则有f f-1=IA，f-1 f=I B.特别地，若特别地，若f:A A A A是双射，则是双射，则f f-1=f-1 f=IA 第43页，此课件共76页哦复合映射性质复合映射性质【定理定理1-10】设设f:A A B B,g:B B C C ，(1)若若 f 和和 g 是单射是单射,则则 f g是单射是单射.(2)若若 f 和和 g 是满射是满射,则则 f g 是满射是满射.(3)若若 f 和和 g 是双射是双射,则则 f
26、g 是双射是双射.【定理定理1-11】设设f:A A B B,g:B B C C ，(1)若若fg是单射是单射,则则f是单射是单射,g不一定不一定.(2)若若fg是满射是满射,则则g是满射是满射,f 不一定不一定.(3)若若fg是双射是双射,则则f是单射且是单射且g是满射是满射.【定定理理1-12】设设f:A A B B,g:B B C C ，h:C C D D，则则(f g)h=f(g h)第44页，此课件共76页哦1.3 运算的定义及性质运算的定义及性质 运算是由已知对象得出新对象的一种运算是由已知对象得出新对象的一种方法。运算是讨论对象之间有何联系的一方法。运算是讨论对象之间有何联系的一
27、种方法。种方法。运算本质上是映射，但运算更侧重于运算本质上是映射，但运算更侧重于研究运算满足的一些运算性质。研究运算满足的一些运算性质。第45页，此课件共76页哦1.3.1 运算的定义运算的定义 设设A1,A2,An和和B是集合，若是集合，若 f:A1 A2 AnB 则称则称f为为A1,A2,An到到B的的n元运算。在不需要强元运算。在不需要强调集合调集合A1,A2,An和和B时，可以简称时，可以简称f为为运算运算，f:AAAB称称f为为A到到B的的n元运算，或称元运算，或称f f为为A上的上的n元运算。元运算。如如y=f(xy=f(x1 1,x,x2 2,x,xn n)中，中，x x1 1,
28、x,x2 2,x,xn n是参加运算的是参加运算的n n个有顺序的对象，个有顺序的对象，f f称为称为n n元运算，元运算，y y是运算结果，由定义知是运算结果，由定义知道：道：运算结果一定是唯一的运算结果一定是唯一的。第46页，此课件共76页哦运算的特征运算的特征1 1、封封闭闭运运算算：若若对对于于x x1 1 ,x x2 2 ,x xn n A A，有有f f(x(x1 1 ,x x2 2 ,x xn n)=y y A A，则则称称f f为为A A上上的的n n元元封封闭闭运运算算(closed(closed operation)operation)，或或称称为为A A上上的的n n元元
29、代数运算。代数运算。习题习题1.3(1)(2)1.3(1)(2)2 2、运算符号的选取运算符号的选取：常用符号和定义符号：常用符号和定义符号3 3、运算符号的位置运算符号的位置：前面、中间和后面：前面、中间和后面4 4、运算表运算表：方便直观：方便直观第47页，此课件共76页哦运算的例题运算的例题例例1（绝对值运算绝对值运算）f:Z N,f(x)=|x|.（一元运算）（一元运算）例例2 (模运算模运算)f:Z N,f(x)=x(mod k),例例3（模（模m加法运算和模加法运算和模m乘法运算）乘法运算）例例4（最大公因数（最大公因数gcd和最小公倍数和最小公倍数lcm）第48页，此课件共76页
30、哦1.3.2 运算的性质运算的性质1、对合性、对合性【定义定义】设设*是是A上的上的1元代数运算，若对于元代数运算，若对于x x A A，均有，均有 *(*x)=x 则称则称*具有对合性，或称具有对合性，或称*满足对合律满足对合律例例1-20实实数数集集上上的的取取反反数数运运算算“”具具有有对对合合性性，而而其其上上的的绝绝对对值值运运算算|不不具具有有对对合合性性。矩矩阵阵的的逆逆运运算算及及转转置置运运算算具具有对合性，因为有对合性，因为(A-1)-1=A并且并且(AT)T=A第49页，此课件共76页哦1.3.2 运算的性质运算的性质2 2、幂等性、幂等性【定定义义】设设 *是是A A上
31、上的的2 2元元代代数数运运算算，若若对对于于x x A A，有有 x*x=xx*x=x 则则称称x x为为关关于于*运运算算的的幂幂等等元元；若若对对于于任任意意的的x x A A，x x均为幂等元，则称均为幂等元，则称*具有幂等性，或称具有幂等性，或称*满足幂等率。满足幂等率。*1 2 3123 1 3 2 2 3 2 3 1 3例例1 1：设：设A=1,2,3A=1,2,3，A A上的上的*运算见表，指出运算见表，指出A A中中的幂等元，并判断是否满足幂等率？的幂等元，并判断是否满足幂等率？例例2 2：正整数集合：正整数集合N N+上上gcdgcd和和lcmlcm是否幂等率？是否幂等率？
32、例例3 3：实数集合：实数集合R R上乘法是否满足幂等率？上乘法是否满足幂等率？第50页，此课件共76页哦1.3.2 运算的性质运算的性质3、交换性、交换性【定定义义】设设*是是A上上的的2元元代代数数运运算算，若若对对于于任任意意x,yx,y A A，均有均有 x*y=y*x则称则称*具有交换性，或称具有交换性，或称*满足交换律。满足交换律。例例1 1：验证整数集合：验证整数集合Z Z上的加法运算和减法运算是否满足交换律上的加法运算和减法运算是否满足交换律例例2 2：设：设*是有理数集合是有理数集合Q Q上的上的2 2元运算，定义如下：任意元运算，定义如下：任意x x1 1,x,x2 2 Q
33、 Q，x x1 1*x*x2 2=x=x1 1x2x2。证明。证明*不具有交换性。不具有交换性。例例3 3：说明复合映射是否具有交换性。：说明复合映射是否具有交换性。第51页，此课件共76页哦1.3.2 运算的性质运算的性质4、结合性、结合性【定定义义】设设*是是A上上的的2元元代代数数运运算算，若若对对于于任任意意的的 x,y,zx,y,z A A，均有，均有 (x*y)*z=x*(y*z)则称则称*具有结合性，或称具有结合性，或称*满足结合律。满足结合律。例例1 1：验证整数集合：验证整数集合Z Z上的加法运算和上的加法运算和减法运算是否满足结合率。减法运算是否满足结合率。53145534
34、314421213343142254321154321*例例2 2：判定集合：判定集合A=1,2,3,4,5A=1,2,3,4,5见表，见表，是否满足交换率和结合率？是否满足交换率和结合率？例例3 3：判定映射的复合运算是否满足：判定映射的复合运算是否满足结合率？结合率？第52页，此课件共76页哦1.3.2 运算的性质运算的性质5、单位元素、单位元素【定定义义】设设*是是A上上的的2元元代代数数运运算算，若若存存在在e e A A，对对于于任意的任意的x x A A，下列条件均成立：，下列条件均成立：e*x=x x*e=x则称则称e为集合为集合A关于关于*运算的单位元素或幺元素。运算的单位元素
35、或幺元素。例例1 1：验证整数集合：验证整数集合Z Z关于加法运算关于加法运算+的单位元素为的单位元素为0 0，而，而Z Z关于乘法运关于乘法运算的单位元素为算的单位元素为1 1，Z Z关于减法运算没有单位元素。关于减法运算没有单位元素。定理：若定理：若A A关于关于*运算有单位元素，则单位元素是唯一的。运算有单位元素，则单位元素是唯一的。第53页，此课件共76页哦1.3.2 运算的性质运算的性质6 6、零元素、零元素【定定义义】设设 *是是A A上上的的2 2元元代代数数运运算算，若若存存在在 A A ，对对于任意的于任意的x x A A ，下列条件均成立：，下列条件均成立：*x=x*=则称
36、为集合则称为集合A A关于关于*运算的零元素。运算的零元素。例例1 1：验证整数集合：验证整数集合Z Z关于加法运算关于加法运算+和减法运算和减法运算-均没有零元素。均没有零元素。Z Z关于乘法运算的零元素为关于乘法运算的零元素为0 0。第54页，此课件共76页哦1.3.2 运算的性质运算的性质7 7、逆元素、逆元素【定定义义1-211-21】设设 *是是A A上上的的2 2元元代代数数运运算算且且有有单单位位元元素素e e，若对于若对于x x A A，存在，存在y y A A，下列条件均成立：下列条件均成立：y*x=e x*y=e则称则称y y为为x x的逆元素。的逆元素。注意：注意：1 1
37、、一一个个方方阵阵关关于于乘乘法法运运算算的的逆逆元元是是其其逆逆矩矩阵阵，单单位位元元素素是单位矩阵；是单位矩阵；2 2、一一个个双双射射的的映映射射的的复复合合运运算算的的逆逆元元是是其其逆逆映映射射。单单位位元素是恒等映射。元素是恒等映射。第55页，此课件共76页哦1.3.2 运算的性质运算的性质例例1 1：分别考察：实数集合：分别考察：实数集合R R中各元素关于加法运算和乘法运中各元素关于加法运算和乘法运算的逆元素。算的逆元素。例例2 2：设：设A=a,b,c,A=a,b,c,关于关于*运算的运算表。分析逆元。运算的运算表。分析逆元。结论：一个元素的逆元不一定存在，存在也不一定唯一。结
38、论：一个元素的逆元不一定存在，存在也不一定唯一。习题习题1.3(8)1.3(8)caccaabbcbaacba*【定理】设【定理】设A A关于关于*运算的单位元素为运算的单位元素为e e且且*运运算满足结合律，若算满足结合律，若x x在在A A中有左逆元中有左逆元y y及右逆及右逆元元z z，则，则y=zy=z。进而，对于一个满足结合律。进而，对于一个满足结合律的运算来说，若一个元素有逆元则其逆元是的运算来说，若一个元素有逆元则其逆元是唯一的。唯一的。第56页，此课件共76页哦1.3.2 运算的性质运算的性质8 8、消去性、消去性【定定义义1-221-22】设设 *是是A A上上的的2 2元元
39、代代数数运运算算，若若A A关关于于*运运算算有有零零元元素素，如如果果对对于于任任意意x,y,zx,y,z A A ，只只要要xx ，则则下下列列条件均成立：条件均成立：x*y=x*z y=zx*y=x*z y=z y*x=z*x y=z y*x=z*x y=z则称则称*具有消去性，或称具有消去性，或称*满足消去律。满足消去律。例：验证整数集合例：验证整数集合Z Z上的加法运算上的加法运算+和乘法运算均满足消和乘法运算均满足消去律。去律。第57页，此课件共76页哦1.3.2 运算的性质运算的性质9 9、分配性、分配性【定定义义1-231-23】设设 *和和 是是A A上上的的2 2元元代代数
40、数运运算算，若若对对于于任任意意x,y,zx,y,z A A ，下列条件均成立：，下列条件均成立：x*(y x*(y z)=(x*y)=(x*y)(x*z)(x*z)(y (y z)*x=(y*x)*x=(y*x)(z*x)(z*x)则称则称*运算对运算对运算具有分配性，或称满足分配律。运算具有分配性，或称满足分配律。注意：当注意：当*运算满足交换性时，条件之一成立即可。运算满足交换性时，条件之一成立即可。例：实数集合例：实数集合R上的乘法运算对加法运算可分配。上的乘法运算对加法运算可分配。第58页，此课件共76页哦1.3.2 运算的性质运算的性质1010、吸收性、吸收性【定定义义1-241-
41、24】设设 *和和是是A A上上的的两两个个2 2元元代代数数运运算算，若若对对于于x,yx,y A A ，下列条件均成立：，下列条件均成立：x*(x x*(x y)=x)=x (y (y x)*x=x)*x=x则称则称*运算对运算运算对运算可吸收。可吸收。注注意意：当当*和和运运算算满满足足交交换换性性，以以上上公公式式之之一一成成立立即即可。可。第59页，此课件共76页哦1.3.2 运算的性质运算的性质1111、德、德摩根（摩根（De MorganDe Morgan）律）律 【定定义义】设设是是集集合合A A上上的的1 1元元代代数数运运算算，*和和是是A A上上的的两两个个2 2元代数运
42、算，若对于元代数运算，若对于x,yx,y A A ，下列条件均成立：，下列条件均成立：(x*y)=(x)(y)(x y)=(x)*(y)则称这三种运算满足则称这三种运算满足De MorganDe Morgan律律 第60页，此课件共76页哦1.4 集合的运算集合的运算1、并运算、并运算2、交运算、交运算3、补运算、补运算4、差运算、差运算5、对称差运算、对称差运算第61页，此课件共76页哦1.4.1 并运算并运算【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A或属于或属于B B的元素组成的集合称为集合的元素组成的集合称为集合A A和和B B的并集，
43、通常记作的并集，通常记作ABAB。即：。即：AB=AB=x x|x x A A或或x x BB阴阴影影部部分分为为ABABU U B BA A如：设如：设 A=a，b，c，d，B=b，d，e，f，求求ABAB定理：设定理：设A A和和B B是集合，则是集合，则ABAB是包含集合是包含集合A A和和B B的最小集合。的最小集合。第62页，此课件共76页哦并运算的性质并运算的性质设设A A，B B，C C是集合，则是集合，则1 1、幂等律：、幂等律：AA=AAA=A2 2、交换律：、交换律：AB=BAAB=BA3 3、结合律：、结合律：(AB)C=A(BC)(AB)C=A(BC)4 4、A=AA=
44、A=A(A(空集空集是并运算的单位元素是并运算的单位元素)5 5、UA=AU=U(UA=AU=U(全集全集U U是并运算的零元素是并运算的零元素)第63页，此课件共76页哦1.4.2 交运算交运算【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A又属于又属于B B的元的元素组成的集合，称为素组成的集合，称为A A和和B B的交集，通常记作的交集，通常记作ABAB。即。即AB=AB=x x|x x A A且且x x BB阴阴影影部部分分为为ABABU U B BA A如：设如：设 A=a，b，c，d，B=b，d，e，f，求求A AB B定理：设定理：设
45、A A和和B B是集合，则是集合，则A AB B是包含在集合是包含在集合A A和和B B中的最大集合。中的最大集合。第64页，此课件共76页哦交运算的性质交运算的性质设设A A，B B，C C是集合，则是集合，则1 1、幂等律：、幂等律：AA=AAA=A2 2、交换律：、交换律：AB=BAAB=BA3 3、结合律：、结合律：(AB)C=A(BC)(AB)C=A(BC)4 4、A=AA=A=（空集（空集是交运算的零元素）是交运算的零元素）5 5、UA=AU=AUA=AU=A（全集（全集U U是交运算的单位元素）是交运算的单位元素）第65页，此课件共76页哦交和并运算的性质交和并运算的性质并、交运
46、算的混合性质并、交运算的混合性质(吸收律吸收律)：设设A A，B B，C C是集合，则是集合，则（1）对对可吸收：可吸收：AA(AB)=A（2）对对可吸收：可吸收：AA(AB)=A（3）对对可分配：可分配：AA(BC)=(AB)(AC)（4）对对可分配：可分配：AA(BC)=(AB)(AC)第66页，此课件共76页哦1.4.3 补运算补运算【定义定义】设设U U是全集，对于集合是全集，对于集合A A，定义，定义A A的补集如下：的补集如下：=x|x=x|x U U，但，但x x A A 注意：一个集合的补集依赖于全集的选取。注意：一个集合的补集依赖于全集的选取。阴阴影影部部分分为为A A的补集
47、的补集U UA A例：设集合例：设集合A=a,b,c分别取全集分别取全集U=a,b,c,d和和U=a,b,c,a,b,b,c,c,求求A的补集。的补集。第67页，此课件共76页哦补运算的性质补运算的性质补运算的性质：补运算的性质：（1）A =U （2）A =De Morgan律律第68页，此课件共76页哦1.4.4 差运算差运算【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A但不属于但不属于B B的元素组成的集合称为的元素组成的集合称为A A和和B B的差集，通常记作的差集，通常记作A-BA-B。即。即A-B=x|xA-B=x|x A A且且x x
48、 BBU UA AB B阴阴影影部部分分为为A-BA-B如：设如：设 A=a，b，c，d，B=b，d，e，f，求求A-BA-B和和B-AB-A第69页，此课件共76页哦差运算的性质差运算的性质（1 1）A-A=A-A=（2 2）A-A-=A=A（3 3）A-U=A-U=定理：对于集合定理：对于集合A,BA,B，有，有A A B=AB B=AB第70页，此课件共76页哦1.4.5 对称差运算对称差运算【定义】设【定义】设A A和和B B是两个任意集合，由所有属于是两个任意集合，由所有属于A A但不属于但不属于B B或者属于或者属于B B但不属于但不属于A A的元素构成的集合称为对称差运的元素构成
49、的集合称为对称差运算也可称为环和运算算也可称为环和运算 ，通常记作，通常记作A A B B。即。即A A B=B=（A-BA-B）（B-AB-A）A A B=B=（A AB B）-（BABA）U UA AB B阴影部分为阴影部分为A A B B如：设如：设 A=a，b，c，d，B=b，d，e，f，求求A A B B第71页，此课件共76页哦对称差的性质对称差的性质（1 1）A A B=B B=B A A（2 2）A A =A=A（3 3）A A A=A=（4 4）（）（A A B B）C=A C=A （B B C C）第72页，此课件共76页哦容斥原理容斥原理（1 1）设）设A A，B B是有
50、限集合，则是有限集合，则|AB|=|A|AB|=|A|B|B|AB|AB|（2 2）设）设A A，B B是有限集合，则是有限集合，则一个班有一个班有5050个学生，在第一次考试中得个学生，在第一次考试中得9595分的有分的有2626人，在第二次考试中得人，在第二次考试中得9595分的有分的有2121人，如果两次考人，如果两次考试中没有得试中没有得9595分的有分的有1717人，那么两次考试都得人，那么两次考试都得9595分分的有多少人？的有多少人？第73页，此课件共76页哦1.5 集合的划分与覆盖集合的划分与覆盖 集合的划分就是集合元素间的一种分集合的划分就是集合元素间的一种分类。在信息科学中