discretemathematics-西南大学网络教育学院

第1讲集合与映射的有关概念掌握以下主要内容:1.集合、子集、幂集、n元组和笛卡尔积.2.映射的定义及性质.3.逆映射.4.复合映射.《离散数学》

(Discrete

Mathematics)《离散数学》(第二版),邓辉文编著清华大学出版社,2010ISBN

978-7-302-13711-5

《离散数学习题解答》(第二版),邓辉文编著,清华大学出版社,2010ISBN

978-7-302-13712-2

离散数学研究的对象:离散量及其之间的关系.离散量与连续量及其之间的转换.现今计算机的处理对象是非常特殊的离散量:0和1.学习离散数学的目的:1.培养各种能力.2.为后继专业课程的学习作知识上的准备.离散数学的基本内容:1.集合与关系Chapter

1集合、映射与运算Chapter

2关系2.数理逻辑Chapter

3命题逻辑Chapter

4谓词逻辑3.代数结构(Chapter

5

)4.图论Chapter

6图论Chapter

7几类特殊的图5.组合计数(Chapter

8)学习离散数学的方法:1.听视频讲座.2.看网络课件.3.作业.4.网络课件中的12套模拟试题.参考文献:

耿素云屈婉玲,离散数学(修订版),高等教育出版社,2004.

Kenneth

H.

Rosen,

Discrete

Mathematics

and

ItsApplications

(Fourth

Edition),

McGraw-HillCompanies,

Inc.1998.(有中译本,2002)Chapter

1

Sets,

Mappings

andOperations集合是现代数学的最基本概念(?).

映射又称为函数,它是现代数学的基本概念,可以借助于集合下定义.运算本质上是映射,但其研究有其特殊性.

集合、映射、运算及关系(Chapter

2)是贯穿于本书的一条主线.1.1集合的有关概念1.集合

集合(用处?)已渗透到自然科学以及社会科学的各个研究领域,在信息的表示及处理中,可以借助于集合去实现数据的删节、插入、排序以及描述数据间的关系.

在一定范围内,集合(set)是其具有某种特定性质的对象汇集成的一个整体,其中的每一个对象都称为该集合的元素(element).这里所指范围是全集U(见图1-1).(避免悖论!)

在数学中常用{

}表示整体.

若x是集合A中元素,则记x A,

否则x

A.

常见的数的集合用正+黑体字母表示:N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合.表示集合的常用方法:(1)列举法:{0,2,4,6,8},N

={0,1,2,3,(2)描述法:{x|x满足的条件}.(3)递归法自然数集合N可递归定义,在后面章节定义命题公式及谓词公式时还会用此法.有限集合A的元素个数|A|.Remarks1.集合中的元素可以是集合,例如A

={a,{a,b},

b,

c}.2.集合之间的元素原则上是没有次序的,如A={a,{a,b},b,c}就是{a,b,c

,{a,b}};3.集合中的元素原则上不重复,如{a,{a,b},b,b,c}还是集合A.不含有任意元素的集合称为空集,

记为

或{

}.是任意集合的子集.2.子集A

B,特别地A

=

B.Theorem

1-2(P3)(1)

AA.(2)

AB,

BAA

=

B.(3)

AB,

BCA

C.Theorem

1-3

A

=

B

A

B

且

B

A.Theorem

1-4Proof由乘法原理证明?4.n元组

Def

1-4将n个元素(?)x1,x2,…,xn按一定顺序排列就得到一个n元(有序)组.在数据结构中就是一个线性表.n

=

2:

(x,

y).n

=

3:

(x,

y,

z)显然,一般说来(x,y)(y,

x).注意区别(a,b,c),((a,b),c),(a,(b,c))

n维向量是n元组,长度为n的线性表是n元组,抽象数据结构Data_Structure=(D,S)本身是一个2元组.2元组常称为有序对或序偶.5.笛卡儿积例1-4(P4)设A

={a,b},B

={1,2},C

={ },

求A

B,

B

A,

B

C,

C

A

B.SolutionB

C

=

{(1, ),

(2,

)}C

A

B

=

{( ,

a,

1),

( ,

b,

1),

( ,

a,

2),

(2)}.A

=

A=

.RemarkP5,

10?TheoremHint可推广到更多个集合的笛卡儿积的情形:1.2

映射的有关概念1.映射的定义

映射=函数(高数中?),它也是现代数学中的基本概念,要求我们在各学科中都要会使用映射的观点.函数在信息科学中得到了充分的应用,大家熟悉的C语言是一种函数型语言.DefAB函数的表示:(1)解析式(2)图形(3)表格(数值计算中出现较多)函数符号的选取.注意区别函数f与函数表达式f(x).映射的两个特点:(1)全函数;(2)唯一性.B上A:例1-5Theorem

1-6注意B上A的记号与该结论的关系.x1x2x3y1y2■Xf(X)Yf-1(Y)n元函数(n

1):n

=0:C语言中的无参函数?2.映射的性质(1)单射(2)满射是Z到N的满射,但不是Z到例如,Z的满射(?).(3)双射双射又称为一一对应:既单又满.例1-8例1-9(P8)例1-10

Def

1-11有限集合A上自身的双射称为A上的置换(permutation).A

={1,2,3,4}上的所有置换有多少个?4!1231233.逆映射

设f:

A

B,

将对应关系f逆转(改变方向),

一般来说,

不能得到B到A的映射:

Def

1-12设f:A

B,若将对应关系f逆转后能得出一个得到B到A的映射,则称该映射为

f的逆映射,记为f-1.abc123

Theorem

1-7f

的逆映射存在的充要条件是f是双射.对于y

=sin

x,当时,有反函数,常记为当时,y

=sin

x仍有反函数,但不能记为arcsin.

显然,

当 时,

无反函数.4.复合映射设f:

A

B,

g:

B

C:例1-12abc123例1-13(P9)

f:

R

R,

f(x)

=

x2,g:

RR,g(x)=x

+2,求f◦g和g◦f.Solution

x

R:(f◦g)(x)

=

g(f(x))

=

g(x2)

=

x2

+

2.(g◦f)(x)

=

f(g(x))

=

f(x+2)

=

(x+2)2.Remark

f◦g

g◦f.Theorem

1-9Theorem

1-10(1)若f和g是单射,则f◦g是单射.(2)若f和g是满射,则f◦g是满射.(3)若f和g是双射,则f◦g是双射.

Proof

(2)任意z

C,

由于g是满射,

存在yB,

使得z

=

g(y).

又由于f是满射,

存在x

A,使得y

=

f(x).

于是z

=

g(y)

=

g(f(x))

=

(f◦g)(x).

故f◦g是满射(see

below).Theorem

1-11(1)若f◦g是单射,则f是单射,g不一定.(2)若f◦g是满射,则g是满射,f

不一定.(3)若f◦g是双射,则f是单射且g是满射.Proof

(1)任