集合映射與運算使用教材書名：離散數學（第三版）“十一五”國家規劃教材主編：鄧輝文出版社：清華大學出版社講授：第1章_第6章第2頁,共76頁，2024年2月25日，星期天參考書目1、邵學才.離散數學（第二版）.清華大學出版社.(應用型規劃教材)2、周忠榮.離散數學及其應用.清華大學出版社.3、王禮萍.離散數學簡明教程.清華大學出版社.(高職教材)4、耿素云,屈婉玲.離散數學（修訂版）.高等教育出版社.(十五規劃教材，北京大學)第3頁,共76頁，2024年2月25日，星期天考核方式期末成績=平時成績+期末試卷成績平時成績20分平時成績=出勤+小測驗+作業出勤=10

小測驗=5

作業=5（獨立、自主）期末試卷成績80分。第4頁,共76頁，2024年2月25日，星期天研究對象

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

離散數學是研究計算機科學的基本數學工具和最合適的理論手段；是計算機類專業的重要課程。第5頁,共76頁，2024年2月25日，星期天學習目的

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

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

2、培養學生抽象思維能力和嚴密的邏輯推理能力。第6頁,共76頁，2024年2月25日，星期天基本內容（1）一、集合與關系：是離散數學研究的重點內容

1、Chapter1集合、映射與運算：集合是現代數學的最基本概念，映射是現代數學的基本概念，是本書的重點。

2、Chapter2關系：是刻畫聯系的數學模型。二、數理邏輯：研究思維形式及思維規律尤其是推理的學科。

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

2、Chapter4謂詞邏輯：研究原子命題的內部形式結構及其邏輯關系。第7頁,共76頁，2024年2月25日，星期天基本內容（2）三、代數結構：研究有一般元素組成的集合上的運算，以及運算滿足一些給定的數學結構的性質。

1、Chapter5(1)代數結構：計算機系統本身就是一種代數結構。

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

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

1、Chapter6圖論：主要研究數據結構中圖的相關性質。

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

集合（set）:是指具有某種特定性質的對象匯集成的一個整體。元素（element）：集合中的每一個對象稱為集合的元素。通常用大寫字母表示集合，用小寫字母表示集合中的元素。在數學中常用{}表示整體.在討論集合時，為避免出現某些悖論，應指定討論范圍，這個范圍也是一個集合，稱為全集或論域，記作U。文氏圖用矩形框表示。A第11頁,共76頁，2024年2月25日，星期天隸屬關系集合與集合中元素的關系——隸屬關系給定一個集合A，（1）若x是集合A中的元素，記作x

A，讀作x屬于A；（2）若x不是集合A中的元素，則記作x

A，讀作x不屬于A。說明：

讀作屬于；

讀作不屬于例:A={a,b,c,d}，則有b

A，e

A．第12頁,共76頁，2024年2月25日，星期天特殊集合表示幾類特殊集合的表示：N自然數集合,包括數0；Z整數集合；Q有理數集合；R實數集合；C復數集合.第13頁,共76頁，2024年2月25日，星期天集合的表示⑴列舉法就是把集合中的所有元素一一列舉出來，或列出足夠多的元素以反映出集合中成員的特征，元素之間用逗號分開，并用花括號括起來。如：A={a1，a2，……，an}B={0，2，4，6，……，2n，……}。第14頁,共76頁，2024年2月25日，星期天集合的表示⑵描述法是指把集合中的元素所滿足的條件或具有的性質描述出來，即將條件或性質用文字或符號在花括號內豎線后面表示出來。一般形式為：

A={x|x滿足的條件或具有的性質}如：A={x|x–1=0，x

R}B={x|x是英文字母，x元音}第15頁,共76頁，2024年2月25日，星期天集合的表示⑶遞歸法是指通過計算規則定義集合中的元素。首先給出該集合的初始元素；然后給出由集合中已知元素構造其他元素的方法；最后強調有限次使用前面的步驟得到的元素是集合中僅有的元素。如：設a0=1,a1=1,an+1=an+an-1,A={a0,a1,a2,……}={ak

k

0}。第16頁,共76頁，2024年2月25日，星期天集合的表示⑷巴科斯范式(BNF)表示法

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

首先畫一個大矩形表示全集，然后在矩形內畫一些圓，用圓的內部表示集合，集合之間的相互關系和有關的運算可以用文氏圖給予形象的描述。第17頁,共76頁，2024年2月25日，星期天集合的特性⑴確定性確定性是指一旦給定了集合A，對于任意元素a，我們就可以準確地判定a是否在A中。如：A={x|x是自然數，且x<100}則必有30

A，101

A⑵互異性互異性是指集合中的元素之間是彼此不同的，即集合中不允許出現重復的元素。如：集合A={a,b,c,c,b,d}應為A={a,b,c,d}第18頁,共76頁，2024年2月25日，星期天集合的特性⑶無序性無序性是指集合中的元素之間沒有次序關系。在不特別說明情況下，我們所討論的集合都不是多重集。如：

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

與A={a,b,c,{a,b}}相同⑷抽象性抽象性是指集合中元素是抽象的，甚至可以是集合。如：A={a,{a,b},b,c}；第19頁,共76頁，2024年2月25日，星期天相關概念有限集由有限個元素a1,…,an組成的集合稱為有限集。基數（或勢）若集合A是有限集，則集合A中的元素個數稱為集合A的基數（或勢），通常記作|A|。無限集無限集是指由無限個元素組成的集合。空集不含有任何元素的集合是空集。記

或{}。第20頁,共76頁，2024年2月25日，星期天1.1.2子集子集——集合間的包含關系

給定兩個集合A和B，若A中的任意元素都屬于B，則稱A是B的子集，或稱A包含在B，或稱B包含A，通常記作A

B，或B

A。（若任意a

A，必有a

B，則A

B）若A不是B的子集，則集合A中至少有一個元素不屬于B。第21頁,共76頁，2024年2月25日，星期天子集定理1-1對于任意的集合A，有

A。1-2設A、B、C是任意的集合，則有⑴自反性：AA.（任意集合是其子集）⑵反對稱性：AB,BAA=B.⑶傳遞性：AB,BCAC.1-3A=B的充要條件是AB且BA第22頁,共76頁，2024年2月25日，星期天真子集若A

B，且A

B，則稱A是B的真子集，通常記作A

B。（若A是B的真子集，則B中至少有一個元素不屬于A）注意區別：與的不同問題：由AB,BC可否得出AC?解：不成立,如A={a,b},B={a,b,c},C={a,{a,b,c}}.第23頁,共76頁，2024年2月25日，星期天1.1.3冪集設X是一個集合，由X的所有子集作為元素構成的集合稱為X的冪集，記以P(X)或2X。定理

設A是一個有限集且|A|=n，則|P(A)|=2n第24頁,共76頁，2024年2月25日，星期天冪集示例X={a,b}P(X)={,{a},{b},{a,b}}.P({})={,{}}.習題1.1(7)第25頁,共76頁，2024年2月25日，星期天1.1.4n元組將n個元素x1,x2,…,xn按一定順序排列就得到一個n元(有序)組.記為：n=2n=3一般說來(x,y)

(y,x).第26頁,共76頁，2024年2月25日，星期天序偶2元組常稱為有序對或序偶.注意區別(a,b,c),((a,b),c),(a,(b,c))的不同.第27頁,共76頁，2024年2月25日，星期天1.1.5笛卡兒積設A1，A2，…，An是集合，稱集合為A1，A2，…，An的笛卡兒積（直積，叉積）第28頁,共76頁，2024年2月25日，星期天笛卡兒積定理

A=B=例：設A={a,b},B={1,2},C={

},求A

B,B

A,A

B

C,B

C.解：A

B={(a,1),(b,1),(a,2),(b,2)}.BA={(1,a),(1,b),(2,a),(2,b)}.

A

B

C={(a,1,),(b,1,),(a,2,),(b,2,)}.B

C={(1,),(2,)}第29頁,共76頁，2024年2月25日，星期天1.2映射的有關概念映射就是函數，研究的是任意兩個集合之間的一種對應關系。映射是現代數學中的基本概念。函數在信息科學中得到了充分的應用。與集合一樣，映射貫穿本書的所有內容，深刻理解映射的有關內容，對于其他內容的學習是至關重要的。第30頁,共76頁，2024年2月25日，星期天1.2.1映射的定義任意給定兩個集合A和B，若存在對應法則f

，使得對于任意x

A，均存在唯一的y

B與它對應，則稱f是集合A到B的一個映射，或稱A到B的一個函數，記為f:A

B。AB第31頁,共76頁，2024年2月25日，星期天映射的兩個特點假定f:A

B,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).第32頁,共76頁，2024年2月25日，星期天映射的表示（1）解析表達式（2）圖示（3）表格法函數符號的選取:f,g,…,F,G,…,

,

,…,sin,exp,main,add,average,…第33頁,共76頁，2024年2月25日，星期天BA

（讀作B上A）定義對于集合A和B，用BA表示A到B的所有映射組成的集合，即定理：對于集合A和B，若|A|=m，|B|=n，則|BA|=nm。教材P7例題1-5第34頁,共76頁，2024年2月25日，星期天1.2.2映射的性質1、單射假設f:A

B,如果對任意x1,x2

A,由f(x1)=f(x2)可推出x1=x2,則稱f是A到B的單射,或稱f是A到B的一對一映射。例：設f:N→N，f(x)=2x,則f是N到N的單射，試證明之。第35頁,共76頁，2024年2月25日，星期天1.2.2映射的性質2、滿射假設f:A

B，如果對任意y

B,均存在x

A，使得y=f(x)，則稱f是A到B的滿射，或稱f是A到B的映上(onto)的映射。例：設f:Z→N,f(x)=|x|,則f是Z到N的滿射。第36頁,共76頁，2024年2月25日，星期天1.2.2映射的性質3、雙射假設f:A

B，f既是單射又是滿射，則稱f是A到B的雙射,或稱f是A到B的一一對應。例：試建立一個Z到N的一一對應。

2xx≥0f(x)=2|x|-1x<0習題1.2(2)第37頁,共76頁，2024年2月25日，星期天置換的定義設A是有限集合,A到A的雙射稱為A上的置換例如：寫出A={1，2，3}上的所有置換。(個數：n!)第38頁,共76頁，2024年2月25日，星期天1.2.3逆映射定義：設f:A

B,若將對應關系f逆轉后能得出一個B到A的映射,則稱該映射為f的逆映射,記為f-1.定理：設f:AB

，則f的逆映射存在的充要條件是f是雙射.第39頁,共76頁，2024年2月25日，星期天1.2.4復合映射定理

設f:A

B,g:B

C，對于任意x

A，令h(x)=g(f(x))則h是集合A到集合C的映射。xy=f(x)z=g(y)=g(f(x))第40頁,共76頁，2024年2月25日，星期天1.2.4復合映射定義：設f:A

B,g:B

C,對于任意x

A,h(x)=g(f(x))則稱h為f和g的復合映射或復合函數，記為f?g重點：(f?g)(x)=g(f(x))abc123

第41頁,共76頁，2024年2月25日，星期天復合映射例題注意：要保證復合映射有意義，必須f(A)dom(g)例2：設R到R有兩個映射f和g，定義如下：f(x)=x2,g(x)=x+2，分別計算復合映射f?g和g?f注意：一般來說，即使復合映射均有意義，也不能保證f?g=g?f成立

第42頁,共76頁，2024年2月25日，星期天恒等映射設A是集合，令f:A

A,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

第43頁,共76頁，2024年2月25日，星期天復合映射性質【定理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)第44頁,共76頁，2024年2月25日，星期天1.3運算的定義及性質運算是由已知對象得出新對象的一種方法。運算是討論對象之間有何聯系的一種方法。運算本質上是映射，但運算更側重于研究運算滿足的一些運算性質。

第45頁,共76頁，2024年2月25日，星期天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是運算結果，由定義知道：運算結果一定是唯一的。第46頁,共76頁，2024年2月25日，星期天運算的特征1、封閉運算：若對于x1,x2,…,xn

A，有f(x1,x2,…,xn)=y

A，則稱f為A上的n元封閉運算(closedoperation)，或稱為A上的n元代數運算。習題1.3(1)(2)2、運算符號的選取：常用符號和定義符號3、運算符號的位置：前面、中間和后面4、運算表：方便直觀第47頁,共76頁，2024年2月25日，星期天運算的例題例1（絕對值運算）f:ZN,f(x)=|x|.（一元運算）

例2(模運算)f:ZN,f(x)=x(modk),例3（模m加法運算和模m乘法運算）例4（最大公因數gcd和最小公倍數lcm）第48頁,共76頁，2024年2月25日，星期天1.3.2運算的性質1、對合性【定義】設*是A上的1元代數運算，若對于x

A，均有

*(*x)=x

則稱*具有對合性，或稱*滿足對合律〖例1-20〗實數集上的取反數運算“—”具有對合性，而其上的絕對值運算||不具有對合性。矩陣的逆運算及轉置運算具有對合性，因為(A-1)-1=A并且(AT)T=A第49頁,共76頁，2024年2月25日，星期天1.3.2運算的性質2、冪等性【定義】設*是A上的2元代數運算，若對于x

A，有x*x=x

則稱x為關于*運算的冪等元；若對于任意的x

A，x均為冪等元，則稱*具有冪等性，或稱*滿足冪等率。*

123123

132232313例1：設A={1,2,3}，A上的*運算見表，指出A中的冪等元，并判斷是否滿足冪等率？例2：正整數集合N+上gcd和lcm是否冪等率？例3：實數集合R上乘法是否滿足冪等率？第50頁,共76頁，2024年2月25日，星期天1.3.2運算的性質3、交換性【定義】設*是A上的2元代數運算，若對于任意x,y

A，均有

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

Q，x1*x2=x1x2。證明*不具有交換性。例3：說明復合映射是否具有交換性。第51頁,共76頁，2024年2月25日，星期天1.3.2運算的性質4、結合性【定義】設*是A上的2元代數運算，若對于任意的x,y,z

A

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

例1：驗證整數集合Z上的加法運算和減法運算是否滿足結合率。53145534314421213343142254321154321*例2：判定集合A={1,2,3,4,5}見表，是否滿足交換率和結合率？例3：判定映射的復合運算是否滿足結合率？第52頁,共76頁，2024年2月25日，星期天1.3.2運算的性質5、單位元素【定義】設*是A上的2元代數運算，若存在e

A

，對于任意的x

A

，下列條件均成立：

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

例1：驗證整數集合Z關于加法運算+的單位元素為0，而Z關于乘法運算的單位元素為1，Z關于減法運算沒有單位元素。定理：若A關于*運算有單位元素，則單位元素是唯一的。第53頁,共76頁，2024年2月25日，星期天1.3.2運算的性質6、零元素【定義】設*是A上的2元代數運算，若存在θ

A

，對于任意的x

A

，下列條件均成立：

θ*x=θx*θ=θ則稱為集合A關于*運算的零元素。例1：驗證整數集合Z關于加法運算+和減法運算-均沒有零元素。Z關于乘法運算的零元素為0。第54頁,共76頁，2024年2月25日，星期天1.3.2運算的性質7、逆元素【定義1-21】設*是A上的2元代數運算且有單位元素e，若對于x

A，存在y

A，下列條件均成立：

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

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

2、一個雙射的映射的復合運算的逆元是其逆映射。單位元素是恒等映射。第55頁,共76頁，2024年2月25日，星期天1.3.2運算的性質例1：分別考察：實數集合R中各元素關于加法運算和乘法運算的逆元素。例2：設A={a,b,c},關于*運算的運算表。分析逆元。

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

A

，只要x≠θ

，則下列條件均成立：

x*y=x*z→y=zy*x=z*x→y=z則稱*具有消去性，或稱*滿足消去律。例：驗證整數集合Z上的加法運算+和乘法運算均滿足消去律。第57頁,共76頁，2024年2月25日，星期天1.3.2運算的性質9、分配性【定義1-23】設*和?是A上的2元代數運算，若對于任意x,y,z

A，下列條件均成立：x*(y?z)=(x*y)?(x*z)(y?z)*x=(y*x)?(z*x)則稱*運算對?運算具有分配性，或稱滿足分配律。注意：當*運算滿足交換性時，條件之一成立即可。例：實數集合R上的乘法運算對加法運算可分配。第58頁,共76頁，2024年2月25日，星期天1.3.2運算的性質10、吸收性【定義1-24】設*和?是A上的兩個2元代數運算，若對于x,y

A，下列條件均成立：x*(x?y)=x(y?x)*x=x則稱*運算對運算?可吸收。

注意：當*和?運算滿足交換性，以上公式之一成立即可。第59頁,共76頁，2024年2月25日，星期天1.3.2運算的性質11、德·摩根（DeMorgan）律【定義】設·是集合A上的1元代數運算，*和?是A上的兩個2元代數運算，若對于x,y

A

，下列條件均成立：

·(x*y)=(·x)?(·y)·(x?y)=(·x)*(·y)則稱這三種運算滿足DeMorgan律第60頁,共76頁，2024年2月25日，星期天1.4集合的運算1、并運算2、交運算3、補運算4、差運算5、對稱差運算第61頁,共76頁，2024年2月25日，星期天1.4.1并運算【定義】設A和B是兩個任意集合，由所有屬于A或屬于B的元素組成的集合稱為集合A和B的并集，通常記作A∪B。即：A∪B={x|x

A或x

B}陰影部分為A∪BU

BA如：設A={a，b，c，d}，B={b，d，e，f}，求A∪B定理：設A和B是集合，則A∪B是包含集合A和B的最小集合。第62頁,共76頁，2024年2月25日，星期天并運算的性質設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是并運算的零元素)第63頁,共76頁，2024年2月25日，星期天1.4.2交運算【定義】設A和B是兩個任意集合，由所有屬于A又屬于B的元素組成的集合，稱為A和B的交集，通常記作A∩B。即A∩B={x|x

A且x

B}陰影部分為A∩BU

BA如：設A={a，b，c，d}，B={b，d，e，f}，求A∩B定理：設A和B是集合，則A∩B是包含在集合A和B中的最大集合。第64頁,共76頁，2024年2月25日，星期天交運算的性質設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是交運算的單位元素）第65頁,共76頁，2024年2月25日，星期天交和并運算的性質并、交運算的混合性質(吸收律)：

設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)

第66頁,共76頁，2024年2月25日，星期天1.4.3補運算【定義】設U是全集，對于集合A，定義A的補集如下：

={x|x

U，但x

A}注意：一個集合的補集依賴于全集的選取。陰影部分為A的補集UA例：設集合A={a,b,c}分別取全集U={a,b,c,d}和U={a,b,c,{a,b},{b,c