第1章集合、映射與運算2015

離散數(shù)學(DiscreteMathematics)祁偉電話Q:826105276使用教材書名：離散數(shù)學（第三版）“十一五”國家規(guī)劃教材主編：鄧輝文出版社：清華大學出版社講授：第1章_第6章參考書目1、邵學才.離散數(shù)學（第二版）.清華大學出版社.(應用型規(guī)劃教材)2、周忠榮.離散數(shù)學及其應用.清華大學出版社.3、王禮萍.離散數(shù)學簡明教程.清華大學出版社.(高職教材)4、耿素云,屈婉玲.離散數(shù)學（修訂版）.高等教育出版社.(十五規(guī)劃教材，北京大學)考核方式期末成績=平時成績+期末試卷成績平時成績20分平時成績=出勤+小測驗+作業(yè)出勤=10

小測驗=5

作業(yè)=5（獨立、自主）期末試卷成績80分。研究對象

離散數(shù)學是研究離散量的結(jié)構(gòu)及其相互之間關系的一門學科，它與當今計算機所處理的對象相一致。

離散數(shù)學是研究計算機科學的基本數(shù)學工具和最合適的理論手段；是計算機類專業(yè)的重要課程。學習目的

離散數(shù)學是計算機及相關專業(yè)的一門核心課程，不是一門純數(shù)學課程，而是計算機學科的專業(yè)基礎課程。

1、為后繼課程提供必要的數(shù)學基礎

2、培養(yǎng)學生抽象思維能力和嚴密的邏輯推理能力?；緝?nèi)容（1）一、集合與關系：是離散數(shù)學研究的重點內(nèi)容

1、Chapter1集合、映射與運算：集合是現(xiàn)代數(shù)學的最基本概念，映射是現(xiàn)代數(shù)學的基本概念，是本書的重點。

2、Chapter2關系：是刻畫聯(lián)系的數(shù)學模型。二、數(shù)理邏輯：研究思維形式及思維規(guī)律尤其是推理的學科。

1、Chapter3命題邏輯：研究的主要對象是命題。

2、Chapter4謂詞邏輯：研究原子命題的內(nèi)部形式結(jié)構(gòu)及其邏輯關系?；緝?nèi)容（2）三、代數(shù)結(jié)構(gòu)：研究有一般元素組成的集合上的運算，以及運算滿足一些給定的數(shù)學結(jié)構(gòu)的性質(zhì)。

1、Chapter5(1)代數(shù)結(jié)構(gòu)：計算機系統(tǒng)本身就是一種代數(shù)結(jié)構(gòu)。

2、Chapter5(2)群、環(huán)和域：在形式語言與自動機理論學科中發(fā)揮作用。

3、Chapter5(3)格與布爾代數(shù)：在自動推理和邏輯電路設計的分析和優(yōu)化等問題中得到應用。四、圖論：廣泛應用與解決現(xiàn)實問題。

1、Chapter6圖論：主要研究數(shù)據(jù)結(jié)構(gòu)中圖的相關性質(zhì)。

2、Chapter7幾類特殊的圖：介紹生活和研究中實際的圖論的問題。第1章集合、映射與運算1.1集合的有關概念1.2映射的有關概念1.3運算的定義及性質(zhì)1.4集合的運算1.5集合的劃分與覆蓋第1章集合、映射與運算集合是現(xiàn)代數(shù)學的最基本概念.映射又稱為函數(shù),它是現(xiàn)代數(shù)學的基本概念,可以借助于集合下定義.運算本質(zhì)上是映射,但有其特殊性.(關系也是集合)集合、映射、運算及關系是貫穿于本書的一條主線.1.1.1集合

集合（set）:是指具有某種特定性質(zhì)的對象匯集成的一個整體。元素（element）：集合中的每一個對象稱為集合的元素。通常用大寫字母表示集合，用小寫字母表示集合中的元素。在數(shù)學中常用{}表示整體.在討論集合時，為避免出現(xiàn)某些悖論，應指定討論范圍，這個范圍也是一個集合，稱為全集或論域，記作U。文氏圖用矩形框表示。A隸屬關系集合與集合中元素的關系——隸屬關系給定一個集合A，（1）若x是集合A中的元素，記作xA，讀作x屬于A；（2）若x不是集合A中的元素，則記作xA，讀作x不屬于A。說明：讀作屬于；讀作不屬于例:A={a,b,c,d}，則有bA，eA．特殊集合表示幾類特殊集合的表示：N自然數(shù)集合,包括數(shù)0；Z整數(shù)集合；Q有理數(shù)集合；R實數(shù)集合；C復數(shù)集合.集合的表示⑴列舉法就是把集合中的所有元素一一列舉出來，或列出足夠多的元素以反映出集合中成員的特征，元素之間用逗號分開，并用花括號括起來。如：A={a1，a2，……，an}B={0，2，4，6，……，2n，……}。集合的表示⑵描述法是指把集合中的元素所滿足的條件或具有的性質(zhì)描述出來，即將條件或性質(zhì)用文字或符號在花括號內(nèi)豎線后面表示出來。一般形式為：

A={x|x滿足的條件或具有的性質(zhì)}如：A={x|x–1=0，xR}B={x|x是英文字母，x元音}集合的表示⑶遞歸法是指通過計算規(guī)則定義集合中的元素。首先給出該集合的初始元素；然后給出由集合中已知元素構(gòu)造其他元素的方法；最后強調(diào)有限次使用前面的步驟得到的元素是集合中僅有的元素。如：設a0=1,a1=1,an+1=an+an-1,A={a0,a1,a2,……}={akk0}。集合的表示⑷巴科斯范式(BNF)表示法

BNF常用來定義高級程序設計語言的標識符或表達式集合。⑸文氏圖法(JohnVenn)

首先畫一個大矩形表示全集，然后在矩形內(nèi)畫一些圓，用圓的內(nèi)部表示集合，集合之間的相互關系和有關的運算可以用文氏圖給予形象的描述。集合的特性⑴確定性確定性是指一旦給定了集合A，對于任意元素a，我們就可以準確地判定a是否在A中。如：A={x|x是自然數(shù)，且x<100}則必有30A，101A⑵互異性互異性是指集合中的元素之間是彼此不同的，即集合中不允許出現(xiàn)重復的元素。如：集合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組成的集合稱為有限集?；鶖?shù)（或勢）若集合A是有限集，則集合A中的元素個數(shù)稱為集合A的基數(shù)（或勢），通常記作|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）注意區(qū)別：與的不同問題：由AB,BC可否得出AC?解：不成立,如A={a,b},B={a,b,c},C={a,{a,b,c}}.1.1.3冪集設X是一個集合，由X的所有子集作為元素構(gòu)成的集合稱為X的冪集，記以P(X)或2X。定理

設A是一個有限集且|A|=n，則|P(A)|=2n冪集示例X={a,b}P(X)={,{a},,{a,b}}.P({})={,{}}.習題1.1(7)1.1.4n元組將n個元素x1,x2,…,xn按一定順序排列就得到一個n元(有序)組.記為：n=2n=3一般說來(x,y)(y,x).序偶2元組常稱為有序?qū)蛐蚺?注意區(qū)別(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映射的有關概念映射就是函數(shù)，研究的是任意兩個集合之間的一種對應關系。映射是現(xiàn)代數(shù)學中的基本概念。函數(shù)在信息科學中得到了充分的應用。與集合一樣，映射貫穿本書的所有內(nèi)容，深刻理解映射的有關內(nèi)容，對于其他內(nèi)容的學習是至關重要的。1.2.1映射的定義任意給定兩個集合A和B，若存在對應法則f

，使得對于任意xA，均存在唯一的yB與它對應，則稱f是集合A到B的一個映射，或稱A到B的一個函數(shù)，記為f:AB。AB映射的兩個特點假定f:AB,y=f(x),通常把x稱為自變量，其取值范圍稱為定義域記為domf；將y稱為因變量，其取值范圍稱為值域，記為ranf。⑴全函數(shù).

映射f的定義域是集合A,記為domf=A；⑵唯一性.

對于任意x∈A,對應于B中唯一的元素f(x),x為f的自變量(也稱為原像),f(x)稱為x在映射f下的像,通常記為y=f(x).映射的表示（1）解析表達式（2）圖示（3）表格法函數(shù)符號的選取: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映射的性質(zhì)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映射的性質(zhì)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映射的性質(zhì)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}上的所有置換。(個數(shù)：n!)1.2.3逆映射定義：設f:AB,若將對應關系f逆轉(zhuǎn)后能得出一個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的復合映射或復合函數(shù)，記為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

復合映射性質(zhì)【定理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運算的定義及性質(zhì)運算是由已知對象得出新對象的一種方法。運算是討論對象之間有何聯(lián)系的一種方法。運算本質(zhì)上是映射，但運算更側(cè)重于研究運算滿足的一些運算性質(zhì)。

1.3.1運算的定義設A1,A2,……,An和B是集合，若

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

則稱f為A1,A2,……,An到B的n元運算。在不需要強調(diào)集合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是運算結(jié)果，由定義知道：運算結(jié)果一定是唯一的。運算的特征1、封閉運算：若對于x1,x2,…,xnA，有f(x1,x2,…,xn)=yA，則稱f為A上的n元封閉運算(closedoperation)，或稱為A上的n元代數(shù)運算。習題1.3(1)(2)2、運算符號的選?。撼Ｓ梅柡投x符號3、運算符號的位置：前面、中間和后面4、運算表：方便直觀運算的例題例1（絕對值運算）f:ZN,f(x)=|x|.（一元運算）

例2(模運算)f:ZN,f(x)=x(modk),例3（模m加法運算和模m乘法運算）例4（最大公因數(shù)gcd和最小公倍數(shù)lcm）1.3.2運算的性質(zhì)1、對合性【定義】設*是A上的1元代數(shù)運算，若對于xA，均有

*(*x)=x

則稱*具有對合性，或稱*滿足對合律〖例1-20〗實數(shù)集上的取反數(shù)運算“—”具有對合性，而其上的絕對值運算||不具有對合性。矩陣的逆運算及轉(zhuǎn)置運算具有對合性，因為(A-1)-1=A并且(AT)T=A1.3.2運算的性質(zhì)2、冪等性【定義】設*是A上的2元代數(shù)運算，若對于xA，有x*x=x

則稱x為關于*運算的冪等元；若對于任意的xA，x均為冪等元，則稱*具有冪等性，或稱*滿足冪等率。例1：設A={1,2,3}，A上的*運算見表，指出A中的冪等元，并判斷是否滿足冪等率？例2：正整數(shù)集合N+上gcd和lcm是否冪等率？例3：實數(shù)集合R上乘法是否滿足冪等率？1.3.2運算的性質(zhì)3、交換性【定義】設*是A上的2元代數(shù)運算，若對于任意x,yA，均有

x*y=y*x則稱*具有交換性，或稱*滿足交換律。例1：驗證整數(shù)集合Z上的加法運算和減法運算是否滿足交換律例2：設*是有理數(shù)集合Q上的2元運算，定義如下：任意x1,x2

Q，x1*x2=x1x2。證明*不具有交換性。例3：說明復合映射是否具有交換性。1.3.2運算的性質(zhì)4、結(jié)合性【定義】設*是A上的2元代數(shù)運算，若對于任意的x,y,zA

，均有(x*y)*z=x*(y*z)則稱*具有結(jié)合性，或稱*滿足結(jié)合律。

例1：驗證整數(shù)集合Z上的加法運算和減法運算是否滿足結(jié)合率。53145534314421213343142254321154321*例2：判定集合A={1,2,3,4,5}見表，是否滿足交換率和結(jié)合率？例3：判定映射的復合運算是否滿足結(jié)合率？1.3.2運算的性質(zhì)5、單位元素【定義】設*是A上的2元代數(shù)運算，若存在eA

，對于任意的xA

，下列條件均成立：

e*x=xx*e=x則稱e為集合A關于*運算的單位元素或幺元素。

例1：驗證整數(shù)集合Z關于加法運算+的單位元素為0，而Z關于乘法運算的單位元素為1，Z關于減法運算沒有單位元素。定理：若A關于*運算有單位元素，則單位元素是唯一的。1.3.2運算的性質(zhì)6、零元素【定義】設*是A上的2元代數(shù)運算，若存在θA

，對于任意的xA

，下列條件均成立：

θ*x=θx*θ=θ則稱為集合A關于*運算的零元素。例1：驗證整數(shù)集合Z關于加法運算+和減法運算-均沒有零元素。Z關于乘法運算的零元素為0。1.3.2運算的性質(zhì)7、逆元素【定義1-21】設*是A上的2元代數(shù)運算且有單位元素e，若對于xA，存在yA，下列條件均成立：

y*x=ex*y=e則稱y為x的逆元素。注意：

1、一個方陣關于乘法運算的逆元是其逆矩陣，單位元素是單位矩陣；

2、一個雙射的映射的復合運算的逆元是其逆映射。單位元素是恒等映射。1.3.2運算的性質(zhì)例1：分別考察：實數(shù)集合R中各元素關于加法運算和乘法運算的逆元素。例2：設A={a,b,c},關于*運算的運算表。分析逆元。

結(jié)論：一個元素的逆元不一定存在，存在也不一定唯一。習題1.3(8)caccaabbcbaacba*【定理】設A關于*運算的單位元素為e且*運算滿足結(jié)合律，若x在A中有左逆元y及右逆元z，則y=z。進而，對于一個滿足結(jié)合律的運算來說，若一個元素有逆元則其逆元是唯一的。1.3.2運算的性質(zhì)8、消去性【定義1-22】設*是A上的2元代數(shù)運算，若A關于*運算有零元素，如果對于任意x,y,zA

，只要x≠θ

，則下列條件均成立：

x*y=x*z→y=zy*x=z*x→y=z則稱*具有消去性，或稱*滿足消去律。例：驗證整數(shù)集合Z上的加法運算+和乘法運算均滿足消去律。1.3.2運算的性質(zhì)9、分配性【定義1-23】設*和

?是A上的2元代數(shù)運算，若對于任意x,y,zA，下列條件均成立：x*(y?z)=(x*y)?(x*z)(y?z)*x=(y*x)?(z*x)則稱*運算對?運算具有分配性，或稱滿足分配律。注意：當*運算滿足交換性時，條件之一成立即可。例：實數(shù)集合R上的乘法運算對加法運算可分配。1.3.2運算的性質(zhì)10、吸收性【定義1-24】設*和?是A上的兩個2元代數(shù)運算，若對于x,yA，下列條件均成立：x*(x?y)=x(y?x)*x=x則稱*運算對運算?可吸收。

注意：當*和?運算滿足交換性，以上公式之一成立即可。1.3.2運算的性質(zhì)11、德·摩根（DeMorgan）律【定義】設·是集合A上的1元代數(shù)運算，*和?是A上的兩個2元代數(shù)運算，若對于x,yA

，下列條件均成立：

·(x*y)=(·x)?(·y)·(x?y)=(·x)*(·y)則稱這三種運算滿足DeMorgan律1.4集合的運算1、并運算2、交運算3、補運算4、差運算5、對稱差運算1.4.1并運算【定義】設A和B是兩個任意集合，由所有屬于A或?qū)儆贐的元素組成的集合稱為集合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的最小集合。并運算的性質(zhì)設A，B，C是集合，則1、冪等律：A∪A=A2、交換律：A∪B=B∪A3、結(jié)合律：(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中的最大集合。交運算的性質(zhì)設A，B，C是集合，則1、冪等律：A∩A=A2、交換律：A∩B=B∩A3、結(jié)合律：(A∩B)∩C=A∩(B∩C)4、∩A=A∩=（空集是交運算的零元素）5、U∩A=A∩U=A（全集U是交運算的單位元素）交和并運算的性質(zhì)并、交運算的混合性質(zhì)(吸收律)：

設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的補集。補運算的性質(zhì)補運算的性質(zhì)：

（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差運算的性質(zhì)（1）A-A=（2）A-=A（3）A-U=定理：對于集合A,B，有A–B