第1章集合、映射与运算2015

离散数学(DiscreteMathematics)祁伟电话Q:826105276使用教材书名：离散数学（第三版）“十一五”国家规划教材主编：邓辉文出版社：清华大学出版社讲授：第1章_第6章参考书目1、邵学才.离散数学（第二版）.清华大学出版社.(应用型规划教材)2、周忠荣.离散数学及其应用.清华大学出版社.3、王礼萍.离散数学简明教程.清华大学出版社.(高职教材)4、耿素云,屈婉玲.离散数学（修订版）.高等教育出版社.(十五规划教材，北京大学)考核方式期末成绩=平时成绩+期末试卷成绩平时成绩20分平时成绩=出勤+小测验+作业出勤=10

小测验=5

作业=5（独立、自主）期末试卷成绩80分。研究对象

离散数学是研究离散量的结构及其相互之间关系的一门学科，它与当今计算机所处理的对象相一致。

离散数学是研究计算机科学的基本数学工具和最合适的理论手段；是计算机类专业的重要课程。学习目的

离散数学是计算机及相关专业的一门核心课程，不是一门纯数学课程，而是计算机学科的专业基础课程。

1、为后继课程提供必要的数学基础

2、培养学生抽象思维能力和严密的逻辑推理能力。基本内容（1）一、集合与关系：是离散数学研究的重点内容

1、Chapter1集合、映射与运算：集合是现代数学的最基本概念，映射是现代数学的基本概念，是本书的重点。

2、Chapter2关系：是刻画联系的数学模型。二、数理逻辑：研究思维形式及思维规律尤其是推理的学科。

1、Chapter3命题逻辑：研究的主要对象是命题。

2、Chapter4谓词逻辑：研究原子命题的内部形式结构及其逻辑关系。基本内容（2）三、代数结构：研究有一般元素组成的集合上的运算，以及运算满足一些给定的数学结构的性质。

1、Chapter5(1)代数结构：计算机系统本身就是一种代数结构。

2、Chapter5(2)群、环和域：在形式语言与自动机理论学科中发挥作用。

3、Chapter5(3)格与布尔代数：在自动推理和逻辑电路设计的分析和优化等问题中得到应用。四、图论：广泛应用与解决现实问题。

1、Chapter6图论：主要研究数据结构中图的相关性质。

2、Chapter7几类特殊的图：介绍生活和研究中实际的图论的问题。第1章集合、映射与运算1.1集合的有关概念1.2映射的有关概念1.3运算的定义及性质1.4集合的运算1.5集合的划分与覆盖第1章集合、映射与运算集合是现代数学的最基本概念.映射又称为函数,它是现代数学的基本概念,可以借助于集合下定义.运算本质上是映射,但有其特殊性.(关系也是集合)集合、映射、运算及关系是贯穿于本书的一条主线.1.1.1集合

集合（set）:是指具有某种特定性质的对象汇集成的一个整体。元素（element）：集合中的每一个对象称为集合的元素。通常用大写字母表示集合，用小写字母表示集合中的元素。在数学中常用{}表示整体.在讨论集合时，为避免出现某些悖论，应指定讨论范围，这个范围也是一个集合，称为全集或论域，记作U。文氏图用矩形框表示。A隶属关系集合与集合中元素的关系——隶属关系给定一个集合A，（1）若x是集合A中的元素，记作xA，读作x属于A；（2）若x不是集合A中的元素，则记作xA，读作x不属于A。说明：读作属于；读作不属于例:A={a,b,c,d}，则有bA，eA．特殊集合表示几类特殊集合的表示：N自然数集合,包括数0；Z整数集合；Q有理数集合；R实数集合；C复数集合.集合的表示⑴列举法就是把集合中的所有元素一一列举出来，或列出足够多的元素以反映出集合中成员的特征，元素之间用逗号分开，并用花括号括起来。如：A={a1，a2，……，an}B={0，2，4，6，……，2n，……}。集合的表示⑵描述法是指把集合中的元素所满足的条件或具有的性质描述出来，即将条件或性质用文字或符号在花括号内竖线后面表示出来。一般形式为：

A={x|x满足的条件或具有的性质}如：A={x|x–1=0，xR}B={x|x是英文字母，x元音}集合的表示⑶递归法是指通过计算规则定义集合中的元素。首先给出该集合的初始元素；然后给出由集合中已知元素构造其他元素的方法；最后强调有限次使用前面的步骤得到的元素是集合中仅有的元素。如：设a0=1,a1=1,an+1=an+an-1,A={a0,a1,a2,……}={akk0}。集合的表示⑷巴科斯范式(BNF)表示法

BNF常用来定义高级程序设计语言的标识符或表达式集合。⑸文氏图法(JohnVenn)

首先画一个大矩形表示全集，然后在矩形内画一些圆，用圆的内部表示集合，集合之间的相互关系和有关的运算可以用文氏图给予形象的描述。集合的特性⑴确定性确定性是指一旦给定了集合A，对于任意元素a，我们就可以准确地判定a是否在A中。如：A={x|x是自然数，且x<100}则必有30A，101A⑵互异性互异性是指集合中的元素之间是彼此不同的，即集合中不允许出现重复的元素。如：集合A={a,b,c,c,b,d}应为A={a,b,c,d}集合的特性⑶无序性无序性是指集合中的元素之间没有次序关系。在不特别说明情况下，我们所讨论的集合都不是多重集。如：

A={a,{a,b},b,c}

与A={a,b,c,{a,b}}相同⑷抽象性抽象性是指集合中元素是抽象的，甚至可以是集合。如：A={a,{a,b},b,c}；相关概念有限集由有限个元素a1,…,an组成的集合称为有限集。基数（或势）若集合A是有限集，则集合A中的元素个数称为集合A的基数（或势），通常记作|A|。无限集无限集是指由无限个元素组成的集合。空集不含有任何元素的集合是空集。记或{}。1.1.2子集子集——集合间的包含关系

给定两个集合A和B，若A中的任意元素都属于B，则称A是B的子集，或称A包含在B，或称B包含A，通常记作AB，或BA。（若任意aA，必有aB，则AB）若A不是B的子集，则集合A中至少有一个元素不属于B。子集定理1-1对于任意的集合A，有A。1-2设A、B、C是任意的集合，则有⑴自反性：AA.（任意集合是其子集）⑵反对称性：AB,BAA=B.⑶传递性：AB,BCAC.1-3A=B的充要条件是AB且BA真子集若AB，且AB，则称A是B的真子集，通常记作AB。（若A是B的真子集，则B中至少有一个元素不属于A）注意区别：与的不同问题：由AB,BC可否得出AC?解：不成立,如A={a,b},B={a,b,c},C={a,{a,b,c}}.1.1.3幂集设X是一个集合，由X的所有子集作为元素构成的集合称为X的幂集，记以P(X)或2X。定理

设A是一个有限集且|A|=n，则|P(A)|=2n幂集示例X={a,b}P(X)={,{a},{b},{a,b}}.P({})={,{}}.习题1.1(7)1.1.4n元组将n个元素x1,x2,…,xn按一定顺序排列就得到一个n元(有序)组.记为：n=2n=3一般说来(x,y)(y,x).序偶2元组常称为有序对或序偶.注意区别(a,b,c),((a,b),c),(a,(b,c))的不同.1.1.5笛卡儿积设A1，A2，…，An是集合，称集合为A1，A2，…，An的笛卡儿积（直积，叉积）笛卡儿积定理A=B=例：设A={a,b},B={1,2},C={},求AB,BA,ABC,BC.解：AB={(a,1),(b,1),(a,2),(b,2)}.BA={(1,a),(1,b),(2,a),(2,b)}.

ABC={(a,1,),(b,1,),(a,2,),(b,2,)}.BC={(1,),(2,)}1.2映射的有关概念映射就是函数，研究的是任意两个集合之间的一种对应关系。映射是现代数学中的基本概念。函数在信息科学中得到了充分的应用。与集合一样，映射贯穿本书的所有内容，深刻理解映射的有关内容，对于其他内容的学习是至关重要的。1.2.1映射的定义任意给定两个集合A和B，若存在对应法则f

，使得对于任意xA，均存在唯一的yB与它对应，则称f是集合A到B的一个映射，或称A到B的一个函数，记为f:AB。AB映射的两个特点假定f:AB,y=f(x),通常把x称为自变量，其取值范围称为定义域记为domf；将y称为因变量，其取值范围称为值域，记为ranf。⑴全函数.

映射f的定义域是集合A,记为domf=A；⑵唯一性.

对于任意x∈A,对应于B中唯一的元素f(x),x为f的自变量(也称为原像),f(x)称为x在映射f下的像,通常记为y=f(x).映射的表示（1）解析表达式（2）图示（3）表格法函数符号的选取:f,g,…,F,G,…,,,…,sin,exp,main,add,average,…BA

（读作B上A）定义对于集合A和B，用BA表示A到B的所有映射组成的集合，即定理：对于集合A和B，若|A|=m，|B|=n，则|BA|=nm。教材P7例题1-51.2.2映射的性质1、单射假设f:AB,如果对任意x1,x2A,由f(x1)=f(x2)可推出x1=x2,则称f是A到B的单射,或称f是A到B的一对一映射。例：设f:N→N，f(x)=2x,则f是N到N的单射，试证明之。1.2.2映射的性质2、满射假设f:AB，如果对任意yB,均存在xA，使得y=f(x)，则称f是A到B的满射，或称f是A到B的映上(onto)的映射。例：设f:Z→N,f(x)=|x|,则f是Z到N的满射。1.2.2映射的性质3、双射假设f:AB，f既是单射又是满射，则称f是A到B的双射,或称f是A到B的一一对应。例：试建立一个Z到N的一一对应。2xx≥0f(x)=2|x|-1x<0习题1.2(2)置换的定义设A是有限集合,A到A的双射称为A上的置换例如：写出A={1，2，3}上的所有置换。(个数：n!)1.2.3逆映射定义：设f:AB,若将对应关系f逆转后能得出一个B到A的映射,则称该映射为f的逆映射,记为f-1.定理：设f:AB

，则f的逆映射存在的充要条件是f是双射.1.2.4复合映射定理

设f:A

B,g:B

C，对于任意xA，令h(x)=g(f(x))则h是集合A到集合C的映射。xy=f(x)z=g(y)=g(f(x))1.2.4复合映射定义：设f:A

B,g:B

C,对于任意xA,h(x)=g(f(x))则称h为f和g的复合映射或复合函数，记为f◦g重点：(f◦g)(x)=g(f(x))abc123复合映射例题注意：要保证复合映射有意义，必须f(A)dom(g)例2：设R到R有两个映射f和g，定义如下：f(x)=x2,g(x)=x+2，分别计算复合映射f◦g和g◦f注意：一般来说，即使复合映射均有意义，也不能保证f◦g=g◦f成立

恒等映射设A是集合，令f:AA,f(x)=x，称f为集合A上的恒等映射(identityfunctiononA)，记为IA

显然恒等映射是唯一存在的。【定理1-9】若f:A

B是双射，则有f

◦

f-1=IA，f-1

◦

f

=IB.特别地，若f:A

A是双射，则f

◦

f-1=f-1

◦

f

=IA

复合映射性质【定理1-10】设f:A

B,g:B

C

，(1)若f和g是单射,则f◦

g是单射.(2)若f和g是满射,则f◦

g是满射.(3)若f和g是双射,则f◦

g是双射.【定理1-11】设f:A

B,g:B

C

，(1)若f◦g是单射,则f是单射,g不一定.(2)若f◦g是满射,则g是满射,f不一定.(3)若f◦g是双射,则f是单射且g是满射.【定理1-12】设f:A

B,g:B

C

，h:C

D，则(f◦

g)◦h=f◦(g◦h)1.3运算的定义及性质运算是由已知对象得出新对象的一种方法。运算是讨论对象之间有何联系的一种方法。运算本质上是映射，但运算更侧重于研究运算满足的一些运算性质。

1.3.1运算的定义设A1,A2,……,An和B是集合，若

f:A1×A2×……×An→B

则称f为A1,A2,……,An到B的n元运算。在不需要强调集合A1,A2,……,An和B时，可以简称f为运算，f:A×A×……×A→B称f为A到B的n元运算，或称f为A上的n元运算。如y=f(x1,x2,…,xn)中，x1,x2,…,xn是参加运算的n个有顺序的对象，f称为n元运算，y是运算结果，由定义知道：运算结果一定是唯一的。运算的特征1、封闭运算：若对于x1,x2,…,xnA，有f(x1,x2,…,xn)=yA，则称f为A上的n元封闭运算(closedoperation)，或称为A上的n元代数运算。习题1.3(1)(2)2、运算符号的选取：常用符号和定义符号3、运算符号的位置：前面、中间和后面4、运算表：方便直观运算的例题例1（绝对值运算）f:ZN,f(x)=|x|.（一元运算）

例2(模运算)f:ZN,f(x)=x(modk),例3（模m加法运算和模m乘法运算）例4（最大公因数gcd和最小公倍数lcm）1.3.2运算的性质1、对合性【定义】设*是A上的1元代数运算，若对于xA，均有

*(*x)=x

则称*具有对合性，或称*满足对合律〖例1-20〗实数集上的取反数运算“—”具有对合性，而其上的绝对值运算||不具有对合性。矩阵的逆运算及转置运算具有对合性，因为(A-1)-1=A并且(AT)T=A1.3.2运算的性质2、幂等性【定义】设*是A上的2元代数运算，若对于xA，有x*x=x

则称x为关于*运算的幂等元；若对于任意的xA，x均为幂等元，则称*具有幂等性，或称*满足幂等率。例1：设A={1,2,3}，A上的*运算见表，指出A中的幂等元，并判断是否满足幂等率？例2：正整数集合N+上gcd和lcm是否幂等率？例3：实数集合R上乘法是否满足幂等率？1.3.2运算的性质3、交换性【定义】设*是A上的2元代数运算，若对于任意x,yA，均有

x*y=y*x则称*具有交换性，或称*满足交换律。例1：验证整数集合Z上的加法运算和减法运算是否满足交换律例2：设*是有理数集合Q上的2元运算，定义如下：任意x1,x2

Q，x1*x2=x1x2。证明*不具有交换性。例3：说明复合映射是否具有交换性。1.3.2运算的性质4、结合性【定义】设*是A上的2元代数运算，若对于任意的x,y,zA

，均有(x*y)*z=x*(y*z)则称*具有结合性，或称*满足结合律。

例1：验证整数集合Z上的加法运算和减法运算是否满足结合率。53145534314421213343142254321154321*例2：判定集合A={1,2,3,4,5}见表，是否满足交换率和结合率？例3：判定映射的复合运算是否满足结合率？1.3.2运算的性质5、单位元素【定义】设*是A上的2元代数运算，若存在eA

，对于任意的xA

，下列条件均成立：

e*x=xx*e=x则称e为集合A关于*运算的单位元素或幺元素。

例1：验证整数集合Z关于加法运算+的单位元素为0，而Z关于乘法运算的单位元素为1，Z关于减法运算没有单位元素。定理：若A关于*运算有单位元素，则单位元素是唯一的。1.3.2运算的性质6、零元素【定义】设*是A上的2元代数运算，若存在θA

，对于任意的xA

，下列条件均成立：

θ*x=θx*θ=θ则称为集合A关于*运算的零元素。例1：验证整数集合Z关于加法运算+和减法运算-均没有零元素。Z关于乘法运算的零元素为0。1.3.2运算的性质7、逆元素【定义1-21】设*是A上的2元代数运算且有单位元素e，若对于xA，存在yA，下列条件均成立：

y*x=ex*y=e则称y为x的逆元素。注意：

1、一个方阵关于乘法运算的逆元是其逆矩阵，单位元素是单位矩阵；

2、一个双射的映射的复合运算的逆元是其逆映射。单位元素是恒等映射。1.3.2运算的性质例1：分别考察：实数集合R中各元素关于加法运算和乘法运算的逆元素。例2：设A={a,b,c},关于*运算的运算表。分析逆元。

结论：一个元素的逆元不一定存在，存在也不一定唯一。习题1.3(8)caccaabbcbaacba*【定理】设A关于*运算的单位元素为e且*运算满足结合律，若x在A中有左逆元y及右逆元z，则y=z。进而，对于一个满足结合律的运算来说，若一个元素有逆元则其逆元是唯一的。1.3.2运算的性质8、消去性【定义1-22】设*是A上的2元代数运算，若A关于*运算有零元素，如果对于任意x,y,zA

，只要x≠θ

，则下列条件均成立：

x*y=x*z→y=zy*x=z*x→y=z则称*具有消去性，或称*满足消去律。例：验证整数集合Z上的加法运算+和乘法运算均满足消去律。1.3.2运算的性质9、分配性【定义1-23】设*和

◦是A上的2元代数运算，若对于任意x,y,zA，下列条件均成立：x*(y◦z)=(x*y)◦(x*z)(y◦z)*x=(y*x)◦(z*x)则称*运算对◦运算具有分配性，或称满足分配律。注意：当*运算满足交换性时，条件之一成立即可。例：实数集合R上的乘法运算对加法运算可分配。1.3.2运算的性质10、吸收性【定义1-24】设*和◦是A上的两个2元代数运算，若对于x,yA，下列条件均成立：x*(x◦y)=x(y◦x)*x=x则称*运算对运算◦可吸收。

注意：当*和◦运算满足交换性，以上公式之一成立即可。1.3.2运算的性质11、德·摩根（DeMorgan）律【定义】设·是集合A上的1元代数运算，*和◦是A上的两个2元代数运算，若对于x,yA

，下列条件均成立：

·(x*y)=(·x)◦(·y)·(x◦y)=(·x)*(·y)则称这三种运算满足DeMorgan律1.4集合的运算1、并运算2、交运算3、补运算4、差运算5、对称差运算1.4.1并运算【定义】设A和B是两个任意集合，由所有属于A或属于B的元素组成的集合称为集合A和B的并集，通常记作A∪B。即：A∪B={x|xA或xB}阴影部分为A∪BUBA如：设A={a，b，c，d}，B={b，d，e，f}，求A∪B定理：设A和B是集合，则A∪B是包含集合A和B的最小集合。并运算的性质设A，B，C是集合，则1、幂等律：A∪A=A2、交换律：A∪B=B∪A3、结合律：(A∪B)∪C=A∪(B∪C)4、∪A=A∪=A(空集是并运算的单位元素)5、U∪A=A∪U=U(全集U是并运算的零元素)1.4.2交运算【定义】设A和B是两个任意集合，由所有属于A又属于B的元素组成的集合，称为A和B的交集，通常记作A∩B。即A∩B={x|xA且xB}阴影部分为A∩BUBA如：设A={a，b，c，d}，B={b，d，e，f}，求A∩B定理：设A和B是集合，则A∩B是包含在集合A和B中的最大集合。交运算的性质设A，B，C是集合，则1、幂等律：A∩A=A2、交换律：A∩B=B∩A3、结合律：(A∩B)∩C=A∩(B∩C)4、∩A=A∩=（空集是交运算的零元素）5、U∩A=A∩U=A（全集U是交运算的单位元素）交和并运算的性质并、交运算的混合性质(吸收律)：

设A，B，C是集合，则（1）∩对∪可吸收：A∩(A∪B)=A

（2）∪对∩可吸收：A∪(A∩B)=A

（3）∩对∪可分配：A∩(B∪C)=(A∩B)∪(A∩C)

（4）∪对∩可分配：A∪(B∩C)=(A∪B)∩(A∪C)

1.4.3补运算【定义】设U是全集，对于集合A，定义A的补集如下：

={x|xU，但xA}注意：一个集合的补集依赖于全集的选取。阴影部分为A的补集UA例：设集合A={a,b,c}分别取全集U={a,b,c,d}和U={a,b,c,{a,b},{b,c},{{c}}},求A的补集。补运算的性质补运算的性质：

（1）A∪=U

（2）A∩=DeMorgan律1.4.4差运算【定义】设A和B是两个任意集合，由所有属于A但不属于B的元素组成的集合称为A和B的差集，通常记作A-B。即A-B={x|xA且xB}UAB阴影部分为A-B如：设A={a，b，c，d}，B={b，d，e，f}，求A-B和B-A差运算的性质（1）A-A=（2）A-=A（3）A-U=定理：对于集合A,B，有A–B