第1講集合與映射的有關(guān)概念掌握以下主要內(nèi)容:1.集合、子集、冪集、n元組和笛卡爾積.2.映射的定義及性質(zhì).3.逆映射.4.復(fù)合映射.《離散數(shù)學(xué)》

(Discrete

Mathematics)《離散數(shù)學(xué)》(第二版),鄧輝文編著清華大學(xué)出版社,2010ISBN

978-7-302-13711-5

《離散數(shù)學(xué)習(xí)題解答》(第二版),鄧輝文編著,清華大學(xué)出版社,2010ISBN

978-7-302-13712-2

離散數(shù)學(xué)研究的對(duì)象:離散量及其之間的關(guān)系.離散量與連續(xù)量及其之間的轉(zhuǎn)換.現(xiàn)今計(jì)算機(jī)的處理對(duì)象是非常特殊的離散量:0和1.學(xué)習(xí)離散數(shù)學(xué)的目的:1.培養(yǎng)各種能力.2.為后繼專業(yè)課程的學(xué)習(xí)作知識(shí)上的準(zhǔn)備.離散數(shù)學(xué)的基本內(nèi)容:1.集合與關(guān)系Chapter

1集合、映射與運(yùn)算Chapter

2關(guān)系2.數(shù)理邏輯Chapter

3命題邏輯Chapter

4謂詞邏輯3.代數(shù)結(jié)構(gòu)(Chapter

5

)4.圖論Chapter

6圖論Chapter

7幾類特殊的圖5.組合計(jì)數(shù)(Chapter

8)學(xué)習(xí)離散數(shù)學(xué)的方法:1.聽視頻講座.2.看網(wǎng)絡(luò)課件.3.作業(yè).4.網(wǎng)絡(luò)課件中的12套模擬試題.參考文獻(xiàn):

耿素云屈婉玲,離散數(shù)學(xué)(修訂版),高等教育出版社,2004.

Kenneth

H.

Rosen,

Discrete

Mathematics

and

ItsApplications

(Fourth

Edition),

McGraw-HillCompanies,

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

1

Sets,

Mappings

andOperations集合是現(xiàn)代數(shù)學(xué)的最基本概念(?).

映射又稱為函數(shù),它是現(xiàn)代數(shù)學(xué)的基本概念,可以借助于集合下定義.運(yùn)算本質(zhì)上是映射,但其研究有其特殊性.

集合、映射、運(yùn)算及關(guān)系(Chapter

2)是貫穿于本書的一條主線.1.1集合的有關(guān)概念1.集合

集合(用處?)已滲透到自然科學(xué)以及社會(huì)科學(xué)的各個(gè)研究領(lǐng)域,在信息的表示及處理中,可以借助于集合去實(shí)現(xiàn)數(shù)據(jù)的刪節(jié)、插入、排序以及描述數(shù)據(jù)間的關(guān)系.

在一定范圍內(nèi),集合(set)是其具有某種特定性質(zhì)的對(duì)象匯集成的一個(gè)整體,其中的每一個(gè)對(duì)象都稱為該集合的元素(element).這里所指范圍是全集U(見圖1-1).(避免悖論!)

在數(shù)學(xué)中常用{

}表示整體.

若x是集合A中元素,則記x A,

否則x

A.

常見的數(shù)的集合用正+黑體字母表示:N是自然數(shù)集合,包括數(shù)0；Z是整數(shù)集合；Q是有理數(shù)集合；R是實(shí)數(shù)集合；C是復(fù)數(shù)集合.表示集合的常用方法:(1)列舉法:{0,2,4,6,8},N

={0,1,2,3,(2)描述法:{x|x滿足的條件}.(3)遞歸法自然數(shù)集合N可遞歸定義,在后面章節(jié)定義命題公式及謂詞公式時(shí)還會(huì)用此法.有限集合A的元素個(gè)數(shù)|A|.Remarks1.集合中的元素可以是集合,例如A

={a,{a,b},

b,

c}.2.集合之間的元素原則上是沒(méi)有次序的,如A={a,{a,b},b,c}就是{a,b,c

,{a,b}};3.集合中的元素原則上不重復(fù),如{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個(gè)元素(?)x1,x2,…,xn按一定順序排列就得到一個(gè)n元(有序)組.在數(shù)據(jù)結(jié)構(gòu)中就是一個(gè)線性表.n

=

2:

(x,

y).n

=

3:

(x,

y,

z)顯然,一般說(shuō)來(lái)(x,y)(y,

x).注意區(qū)別(a,b,c),((a,b),c),(a,(b,c))

n維向量是n元組,長(zhǎng)度為n的線性表是n元組,抽象數(shù)據(jù)結(jié)構(gòu)Data_Structure=(D,S)本身是一個(gè)2元組.2元組常稱為有序?qū)蛐蚺?5.笛卡兒積例1-4(P4)設(shè)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可推廣到更多個(gè)集合的笛卡兒積的情形:1.2

映射的有關(guān)概念1.映射的定義

映射=函數(shù)(高數(shù)中?),它也是現(xiàn)代數(shù)學(xué)中的基本概念,要求我們?cè)诟鲗W(xué)科中都要會(huì)使用映射的觀點(diǎn).函數(shù)在信息科學(xué)中得到了充分的應(yīng)用,大家熟悉的C語(yǔ)言是一種函數(shù)型語(yǔ)言.DefAB函數(shù)的表示:(1)解析式(2)圖形(3)表格(數(shù)值計(jì)算中出現(xiàn)較多)函數(shù)符號(hào)的選取.注意區(qū)別函數(shù)f與函數(shù)表達(dá)式f(x).映射的兩個(gè)特點(diǎn):(1)全函數(shù);(2)唯一性.B上A:例1-5Theorem

1-6注意B上A的記號(hào)與該結(jié)論的關(guān)系.x1x2x3y1y2■Xf(X)Yf-1(Y)n元函數(shù)(n

1):n

=0:C語(yǔ)言中的無(wú)參函數(shù)?2.映射的性質(zhì)(1)單射(2)滿射是Z到N的滿射,但不是Z到例如,Z的滿射(?).(3)雙射雙射又稱為一一對(duì)應(yīng):既單又滿.例1-8例1-9(P8)例1-10

Def

1-11有限集合A上自身的雙射稱為A上的置換(permutation).A

={1,2,3,4}上的所有置換有多少個(gè)?4!1231233.逆映射

設(shè)f:

A

B,

將對(duì)應(yīng)關(guān)系f逆轉(zhuǎn)(改變方向),

一般來(lái)說(shuō),

不能得到B到A的映射:

Def

1-12設(shè)f:A

B,若將對(duì)應(yīng)關(guān)系f逆轉(zhuǎn)后能得出一個(gè)得到B到A的映射,則稱該映射為

f的逆映射,記為f-1.abc123

Theorem

1-7f

的逆映射存在的充要條件是f是雙射.對(duì)于y

=sin

x,當(dāng)時(shí),有反函數(shù),常記為當(dāng)時(shí),y

=sin

x仍有反函數(shù),但不能記為arcsin.

顯然,

當(dāng) 時(shí),

無(wú)反函數(shù).4.復(fù)合映射設(shè)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)任