第2篇集合論第三章集合的基本概念和運算第四章關系第五章函數第三章集合論3.1集合的基本概念3.2集合的基本運算3.3集合中元素的計數3.4笛卡爾乘積集合論簡介康托(GeorgCantor，1845-1918)是集合論的創(chuàng)始人，為數學引入了集合和無限兩個新事物。集合論是數學中許多分支的基礎，是整個大廈的基礎，是許多計算機科學理論不可或缺的工具。從歷史上來看，1900年之前的數學幾乎沒有集合論的容身之地。當時的學術論文，文摘雜志上，集合論都被作為哲學的一部分。本章將討論集合的基本概念，表示法；粗略地介紹集合的公理化系統(tǒng)；集合的劃分與覆蓋；集合的運算及運算性質。集合不僅可以用來表示數及其運算，更可以用于非數值信息的表示和處理，如數據的刪除、排序、插入、數據間的關系描述。集合論是數學中許多分支的基礎，是整個大廈的基礎，是許多計算機科學理論不可或缺的工具。本章將討論集合的基本概念，表示法；集合的運算及運算性質。3.1集合的基本概念康托關于集合的描述：集合是一些確定的、不同的事物的總體，這些事物人們可以意識到，并且能判斷一個給定的事物是否屬于這個總體。集合是由某些相互區(qū)別的事物匯集在一起組成的整體。例3.1.1以下都是一些集合的例子

(1)所有偶數構成一個集合。

(2)所有在20世紀80年代出生的人構成一個集合。

(3)亞洲的國家的全體構成一個集合。

(4)方程x2-1=0的全體實數解集合。

(5)26個英文字母的集合。

(6)計算機內存的全體單元的集合集合通常用大寫英文字母表示。元素通常用小寫字母表示。a是集合A的元素，記作aA，否則記為aA。符號代表的集合N(N+)自然數(正整數)集Z(Z+,Z-)整數(正整數,負整數)集Q(Q+,Q-)有理數(正有理數,負有理數)集R(R+,R-)實數(正實數,負實數)集C復數集一個集合的元素有如下特點：

(1)互異性；(2)無序性；(3)確定性表示一個集合的常用方法有2種：列舉法：把一個集合中的所有或者部分元素列舉在花括號當中，元素之間用逗號隔開，如：{0,1,…,100}描述法（謂詞表示法）：用一個謂詞公式P(x)表示x具有性質P，用{x|P(x)}表示所有具有性質P的事物組成的集合

{x||x-2|≤1,x是實數},{x|x是自然數,x≤100}

{x|x5+x4+x3+x+1=0}例3.1.2A={a,{b,c},d,iomiwma}，請表示出該集合元素間的關系集合間的關系：=,,,≠。定義3.1.1

設A,B是兩個集合，如果B的每個元素都是A的元素，則稱B是A的一個子集，記作BA，讀作‘B包含于A’或‘B是A的子集’.

BA(x)(xB→xA)定義3.1.2

設A、B為集合，如果AB且BA則稱A與B相等，即A=B

A=BAB∧BA如果A與B不相等，記做A≠B.

由定義可知，兩個集合相等的充分必要條件是它們具有相同的元素.定義3.1.3

若B是A的子集，且A中至少有一個元素不在B中，則稱B是A的真子集，記作BA，讀作‘A真包含B’或‘B被真包含在A中’.

BABA∧B≠A定義3.1.4

不含任何元素的集合叫做空集，記做?.

?={x|P(x)∧﹁P(x)}

?={x|x≠x}定理3.1.1

空集是一切集合的子集推論

?是唯一的。注意：{?}≠?，因為{?}并不是空集，它包括一個元素?，但是?{?}，且?{?}。這里可以看到，集合{?}是以一個集合作為其元素的，實際上，集合的元素可以是任何事物，包括集合。再如{a,{a}}，{?,{?}}都是包含集合作為元素的集合的例子。由定義可知，對任意集合A，都有?A。稱?和A為A的平凡子集。只要A不是空集，就有?A.對任何集合S，都有SS等價定義A=B(x)(xA?xB)(AB∧BA)

AB(x)﹁(xA?xB)

AB(x)(xA→xB)

AB(AB∧AB)定理

AA,

(AB∧BA)A=B

(AB∧BC)AC含有n個元素的集合簡稱為n元集，它的含有m個(m≤n)元素的子集稱為它的m元子集。例3.1.4A={a,b,c}，求A的全部子集一般地，對n元集合A，它的m(0≤m≤n)元子集有個，不同的子集總數有定義3.1.5

設A為集合，把A的全體子集構成的集合叫做A的冪集，記做ρ(A)，可符號化表示為

ρ(A)={x|x

A}

定義3.1.6

在一個具體的問題中，如果所涉及的集合都是某個集合的子集，則稱這個集合為全集，記做U。例試求出集合A={p,q},B={1,2,3},C={?},D=?的冪集。

解：P(A)={?,{p},{q},{p,q}}

P(B)={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

P(C)={?,{?}}

P(D)={?}

集合論的公理化簡介子集公理：對于任給集合A和性質P，存在集合B，使得B中元素恰為A中滿足P的那些元素。外延公理：兩集合A和B相等，當且僅當它們有相同的元素?？占恚翰话魏卧氐募鲜谴嬖诘?。冪集公理：對任何集合A，存在唯一集合B，B恰以A中所有子集為元素。(稱B為A的冪集)基礎公理：對任何集合A，只要A非空，就存在xA，使得x和A沒有任何相同元素。練習判斷下列表達式是否成立：

x{x},{x}{x},{x}{x},

x{{x}},{x}{{x}},{x}{{x}},

?{x},

?{x},

是否存在集合A,B滿足AB且AB下列集合是否為某集合的冪集？

(1)?;(2){a,?};(3){?,{a}};(4){?,{a},{?,a}}3.2集合的基本運算3.2.1集合的運算3.2.2集合運算算律3.2.1集合的運算定義3.3.1

設A,B是集合，A與B的并集A∪B，交集A∩B，B對A的相對補集A-B分別定義如下：

A∪B={x|xA∨xB}

A∩B={x|xA∧xB}

A－B={x|xA∧xB}

注：定義中的或是指可兼或。若A和B是集合，且A∩B=，則稱A和B是不相交的。n個集合的并集和交集定義3.2.2

設A是集合，集合A相對于全集U的補集U–A稱為A的絕對補集，簡稱為A的補集，記為～A。

～A=U–A={x|xU∧xA}定義3.2.3

設A和B是集合，則A與B的對稱差為A⊕B

A⊕B=(A－B)∪(B－A)

A⊕B=(A∪B)－(A∩B)例3.2.1A={0,1,2}，B={2,3}，計算A⊕B冪等律、結合律、交換律、分配律同一律、零律、排中律、矛盾律、吸收律德·摩根律、雙重否定律集合之間的交、并、差運算也有對偶原理：

設集合A和B分別是由一些集合只進行交、并、差的運算而得來的，將A和B中的交、并分別換為并、交，空集與全集分別換為全集與空集，所得集合分別為A’,B’。如果A=B,那么A’=B’。恒等式證明的基本思想：欲證P=Q，即證PQ∧QP；或證xPxQ3.2.2集合運算律定理

任給集合A，B，C和D，則

①若AB，則A∪B=B，A∩B=A

②若AB和CD，則A∪CB∪D，

A∩CB∩D

③AA∪B，A∩BA

④A-=A，A-BA自然語言敘述法：A=BAB且BA，以及AB對任何xA，都有xB邏輯公式等價演算法恒等代換法例

設A,B是集合，證明(A-B)∪B=A∪B例

設A,B,C是集合，證明A-(B∪C)=(A-B)∩(A-C)例

設集合A與B滿足條件A∩B=?,A∪B=U，證明A=~B.例

證明A∩(B∪C)=(A∩B)∪(A∩C)。提示：A=B(x)(xA?xB)(AB∧BA)證明：對任意x，有

x∈A∩(B∪C)

(x∈A)∧(x∈B∪C)

(x∈A)∧(x∈B∨x∈C)

((x∈A)∧(x∈B))∨((x∈A)∧(x∈C))

(x∈A∩B)∨(x∈A∩C)

x∈(A∩B)∪(A∩C)作業(yè)：P753.(4)(5)(6)4.(2)(3)(4)(6)5.(1)(2)3.3集合中元素的計數3.3.1容斥原理3.3.2容斥原理實例3.3.1容斥原理集合A含有n個元素，可以說集合A的基數是n，

記作cardA=n，或|A|=n定義3.3.1

設A為集合，若存在自然數n，使得cardA=|A|=n，則稱A為有窮集，否則就稱A為無窮集。例3.3.1

有100名程序員，其中47名熟悉C語言，35名熟悉C++語言，23名熟悉這兩種語言。問有多少人對這兩種語言都不熟悉？常用方法：

文氏圖、容斥原理文氏圖法：

(1)根據已知條件畫文氏圖：每條性質決定一個集合，并且任意兩個集合一般都是相交的。

(2)將集合的基數分別填入表示集合的區(qū)域內：通常是從幾個集合的交集填起，接著根據計算的結果將數字逐步填入其他空白區(qū)域內，直到所有區(qū)域內都填好為止。例3.3.2

求在1~1000之間不能被5或6，也不能被8整除的數的個數。設S是有窮集，P1和P2分別表示兩種性質，對于S中的任何一個元素x，只能處于以下4種情況之一：

(1)只具有性質P1；(2)只具有性質P2；

(3)同時具有兩種性質；(4)兩種性質都沒有。容斥原理：設A1和A2分別表示S中具有性質P1和P2的元素的集合，則

|~A1∩~A2|=|S|-(|A1|+|A2|)+|A1∩A2|推論：|A1∪A2|=(|A1|+|A2|)-|A1∩A2|3.3.2容斥原理實例例3.3.3

某學院選課情況如下：260人選C語言，208人選編譯原理，160人選人工智能，76人選C語言和編譯原理，48人選C語言和人工智能，62人選編譯原理和人工智能，全部3門課均選的有30人，3門課均沒選的有150人

(1)該學院共有多少人？

(2)有多少學生選C語言和編譯原理，但不選人工智能？

(3)有多少學生選C語言和人工智能，但不選編譯原理？

(4)有多少學生選人工智能和編譯原理，但不選C語言？

(5)有多少學生選C語言，而不選其他兩門課？

(6)有多少學生選編譯原理，而不選其他兩門課？

(7)有多少學生選人工智能，而不選其他兩門課？例3.3.4

某班學生150人，數學考試成績90以上的有80人，語文考試成績90以上的有75人，兩門課程均在90以上的有50人，問

(1)只有一門課程在90以上的學生有多少人？

(2)兩門課程均不在90以上的學生有多少人？3.4笛卡爾乘積3.4.1有序對3.4.2笛卡爾積3.4.3n階笛卡爾積3.4.1有序對定義3.4.1設x和y是兩個元素(允許x和y相等)，由x和y按一定順序排列而成的二元組<x,y>稱為一個序偶，或稱為有序對。x和y稱為序偶<x,y>的坐標，或分量。序偶有以下特點：

(1)當x≠y時，<x,y>≠<y,x>

(2)兩個序偶相等，即<x,y>=<u,v>的充要條件是x=u且y=v例3.4.1證明<x,y>=<u,v>的充要條件是x=u且y=v定義3.4.2

n元有序組定義為<a1,a2,…,an>=<<a1,…,an-1>,an>，ai稱為第i個分量，i=1,2,…,n。3.4.2笛卡爾積定義3.4.3

設A，B是集合，稱集合{<x,y>|xA且yB}是A和B的笛卡兒積，記為A×B。

A×B={<x,y>|xA∧yB}若<x,y>A×B，則xA且yB；

若<x,y>A×B，則xA或yB|A|=m，|B|=n時，|A×B|=m×n例設A={1,2},B={3,4},C={5}，則

A×B={<1,3>,<1,4>,<2,3>,<2,4>}

B×A={<3,1>,<3,2>,<4,1>,<4,2>}求笛卡爾積得運算有如下性質：(1)A=?或B=?時，A×B=B×A=?(2)A≠B且A,B都非空時，A×B≠B×A

(3)A,B,C都非空時，(A×B)×C≠A×(B×C)(4)設符號?是集合的交，并，差，或對稱差運算符，A,B,C是任意集合，則：

A×(B?C)=(A×B)?(A×C)

(B?C)×A=(B×A)?(C×A)例3.4.2

設A={1,2},求ρ(A)×A例3.4.3

設A,B,C,D為任意集合，判斷下列等式是否成立

(1)(A∩B)×(C∩D)=(A×C)∩(B×D)

(2)(A∪B)×(C∪D)=(A×C)∪(B×D)

(3)(A－B)×(C－D)=(A×C)－(B×D)

(4)(A⊕B)×(C⊕D)=(A×C)⊕(B×D)例3.4.4

設A,B是集合，則A×B=?當且僅當A=?或B=?例3.4.5

設A,B,C,D是非空集合，則A×CB×D當且僅當AC且BD。例3.4.6

設A,B是集合，則A×B=B×A當且僅當A=B3.4.3n階笛卡爾積定義3.4.4

設A1,A2,…,An是集合(n≥2)，它們的n階笛卡爾積記做A1×A2×…×An={<x1,x2,…,xn>|x1A1∧x2A2∧…∧xnAn}

當A1=A2=…=An=A時，可將它們的笛卡爾積簡記為An定理3.4.1

設A1,A2,…,An(n是正整數)是有限集，則|A1×A2×…×An|=|A1|×|A2|×…×|An|第四章關系關系簡介4.1關系的概念4.2關系的表示與性質4.3關系的運算4.4關系的閉包運算4.5相容關系與覆蓋4.6等價關系與劃分4.7偏序關系關系簡介第3章討論了集合及集合的運算。本章研究集合內元素間的關系。關系一般是指個體間的相互聯系，它不僅是重要的數學概念，而且在計算機科學中也有著廣泛的應用，如數據結構、數據庫、情報檢索、算法分析等都有很多應用。關系中最基本的是設計兩個個體之間的聯系，即二元關系，這也是本章的學習重點。4.1關系的概念(1)定義4.1.1

設A,B是任意兩個集合，RA×B，則稱R是從A到B的一個二元關系。

當A=B時，即RA×A，稱R是A上的一個二元關系。從定義可以看出，A到B的二元關系也是序偶的集合。

若<a,b>∈R，則稱a與b有關系R，記做aRb。

若<a,b>R，則稱a與b沒有關系R。例如，設A={a,b,c,d}，B={0,1}，則R={<a,0>,<b,0>,<c,1>}就是一個從A到B的二元關系。4.1關系的概念(2)定義4.1.2

設A,B是任意兩個集合，R是從A到B上的二元關系，若R=?，則稱R為空關系。若R=A×B，則稱R為全關系。IA={<a,a>|a∈A}，稱為A上的恒等關系。

全關系EA=A×A={<a,b>|a∈A∧b∈A}。例如，設A={0,1,2}，則IA={<0,0>,<1,1>,<2,2>}4.1關系的概念(3)例4.1.1

設B={1,2,3,6}，求B上的整除關系。例4.1.2

設A={1,2,3,4}，定義A上的關系R如下，試用列元素法表示出R。

(1)R={<x,y>|x是y的倍數}

(2)R={<x,y>|(x-y)2∈A}

(3)R={<x,y>|x/y是素數}

(4)R={<x,y>|x≠y}4.1關系的概念(4)定義4.1.3

設A,B是任意兩個集合，R是從A到B的二元關系，則稱集合{a|a∈A,b∈B使<a,b>∈R}為R的定義域，記為dom(R)或D(R)。稱集合{b|b∈B,a∈A使<a,b>∈R}為R的值域，記為ran(R)或R(R)。

R的定義域和值域一起稱為R的域，記做FLDR，即FLDR=dom(R)∪ran(R)。4.1關系的概念(5)例4.1.3

設A={1,2,3,5},B={1,2,4}，在A×B上定義的關系R={<1,2>,<1,4>,<2,4>,<3,4>}。求R的dom(R)，ran(R)和FLDR。定理4.1.1若R和S是從集合A到B上的兩個二元關系，則R和S的并、交、補、差也是A到B上的二元關系。函數：特殊的關系函數f:A→B，可描述為{<a,f(a)>|a∈A}每個從A到B的函數都對應著一個從A到B的關系，然而一個從A到B的關系未必是一個從A到B的函數。定義

設A≠?，B≠?，f是從A到B的關系，如果：

(1)domf=A；

(2)對任意<a,b>，<c,d>∈f，當a=c時必有b=d。

則稱f是從A到B的一個函數。

4.2關系的表示與性質4.2.1關系的矩陣表示4.2.2關系的圖形表示法4.2.3關系的性質設X={a,b,c}，Y={0,1,2,3}，R={<a,1>,<b,2>,<c,0>}。設兩個有限集合X={x1,…,xm}，Y={y1,…,yn}，且R是從X到Y的二元關系。如果有

<xi,yj>R<xi,yj>R

則稱矩陣MR=(rij)為R的關系矩陣。例4.2.1

設集合X={1,2,3,4}和X中二元關系R={<x,y>|(x,y∈X)∧(x>y)}，試求出R的關系矩陣。4.2.1關系的矩陣表示4.2.2關系的圖形表示法用點(實心圓)表示元素，有向邊(有向環(huán))表示序偶。設X={x1,x2,x3,x4}和Y={y1,y2}，R={<x1,y1>,<x2,y1>,<x3,y2>}，畫出R的關系圖。例4.2.2

設A={1,2,3,4,5}，在A上的二元關系R={<1,5>,<1,4>,<2,3>,<3,1>,<3,4>,<4,4>}，畫出R的關系圖。4.2.3關系的性質(1)定義4.2.1

設R是集合A上的二元關系，如果對任意一個a∈A，都有aRa，即<a,a>∈R，則稱R是自反的。

在自反關系中，每個元素都和自己有關系。如：，≤，直線的平行，IA，EA4.2.3關系的性質(2)定義4.2.2

設R是集合A上的二元關系，如果對任何

a∈A，都有<a,a>R，則稱R是反自反的。

在反自反關系中，每個元素都和自己沒有關系。如，，<。注意：自反關系和反自反關系沒有必然聯系。一個關系不是自反的，不一定就是反自反的。反之，也不一定成立。4.2.3關系的性質(3)定義4.2.3

設R是集合A上的二元關系，如果對任意的a,b∈A，當aRb時，就有bRa成立，則稱R是對稱的。

如：=，三角形的相似定義4.2.4

設R是集合A上的二元關系，如果對任意的a,b∈A，當aRb且bRa時，必有a=b，則稱R是反對稱的。

如：，≤4.2.3關系的性質(4)注意：存在即是對稱又是反對稱的二元關系，如恒等關系。換句話說，R是集合A上的關系，如果當a,b∈A，且a≠b時，<a,b>∈R和<b,a>∈R中至少有一個不成立，則稱R是反對稱的。4.2.3關系的性質(5)定義4.2.5

設R是集合A上的二元關系。如果對任意的a,b,c∈A，當aRb且bRc時，有aRc，則稱R是傳遞的。一個關系R可以既不是自反的，也不是反自反的；可以既是對稱的，又是反對稱的。下表列出了關系可能具有的性質，以及分別說明怎樣利用關系的集合表達式，關系矩陣和關系圖做判斷。判別性質集合表達式關系矩陣關系圖自反IARrii=1，i=1,…,n每個頂點處有環(huán)反自反IA∩R=?

rii=0，i=1,…,n每個頂點處無環(huán)對稱R=R-1rij=rji任何兩個不相同頂點之間要么無邊，要么有2條方向相反的邊反對稱R∩R-1

IArij和rji不能同時為1任何兩個不相同頂點之間要么無邊，要么只有1條邊傳遞————若有ai到aj的邊和aj到ak的邊，則有ai到ak的邊4.2.3關系的性質(6)例下列關系都是集合{1,2,3,4}上的關系，分別判斷它們的性質。

R1={<1,1>,<1,2>,<2,1>,<2,2>,<3,4>,<4,4>}

R2={<1,1>,<1,2>,<2,1>}

R3={<2,1>,<3,1>,<3,2>,<4,1>,<4,2>,<4,3>}

R4={<1,1>,<1,2>,<2,2>,<2,3>,<3,3>,<4,4>}Review關系、關系圖、關系矩陣矩陣表示、關系圖表示、關系與函數自反性、反自反性、對稱性、反對稱性及其判斷。作業(yè)：習題P1003.(2)67.(1)(3)104.3關系的運算4.3.1關系的逆運算4.3.2關系的合成運算4.3.1關系的逆運算(1)定義4.3.1

設R是從集合X到Y的二元關系，將R中每一對序偶的元素順序互換，所得到的新的集合成為R的逆關系，記為R-1。即R-1={<y,x>|對x∈X和y∈Y,有xRy}。

dom(R-1)=ran(R)，ran(R-1)=dom(R)。

由定義可知，R-1的關系圖可以通過將R的關系圖中的所有有向弧變向得到。R-1的關系矩陣可以通過將R的關系矩陣轉置得到。例4.3.1

設X={1,2,3,4}，Y={a,b,c}，R={<1,a>,<2,b>,<4,c>}，求R-1。4.3.1關系的逆運算(2)定理4.3.1

設R和S都是從集合X到Y的二元關系，則下列各式成立：

(1)(R-1)-1=R

(2)(R∪S)-1=R-1∪S-1

(3)(R∩S)-1=R-1∩S-1

(4)(~R)-1=~(R-1)，這里~R表示(X×Y)-R

(5)(R-S)-1=R-1-S-1

(6)若RS，則R-1S-14.3.1關系的逆運算(3)定理4.3.2

設R是集合A上的二元關系，則

(1)R是自反的，當且僅當IA

R。

(2)R是反自反的，當且僅當IA∩R=?。

(3)R是對稱的等價于R=R-1。

(4)R是反對稱的等價于R∩R-1=IA。4.3.2關系的合成運算(1)定義4.3.2

設R是從集合X到Y的關系，S是從Y到Z的關系，稱從X到Z的關系{<x,z>|對x∈X和z∈Z,y∈Y,使xRy且ySz}為R和S的合成關系，記為R?S。當ran(R)∩dom(S)=?，R?S=?。例4.3.2

設X={1,2,3,4}，Y={2,3,4}，Z={1,2,3}，R是從集合X到Y的關系，S是從Y到Z的關系，定義如下：

R={<x,y>|(x∈X)∧(y∈Y)∧(x+y=6)}

S={<y,z>|(y∈Y)∧(z∈Z)∧(y-z=1)}

試求出R與S的合成關系R?S，并畫出其關系圖。4.3.2關系的合成運算(2)設R是從集合X={x1,…,xm}到集合Y={y1,…,yn}的關系，S是從集合Y={y1,…,yn}到集合Z={z1,…,zl}的關系，則MR是一個m×n的矩陣，MS是一個n×l的矩陣。定義MR?S=MR?MS，它是個m×l的矩陣。

設MR=(aij)m×n，MS=(bij)n×l，MR?S=(cij)m×l，且

cij=∨kn(aik∧bkj),

i=1,…,m，j=1,…,l?！藕汀牡倪\算規(guī)則分別同布爾加和布爾乘。4.3.2關系的合成運算(3)例4.3.3

設X={a,b,c,d,e}中有如下關系：

R={<a,b>,<b,d>,<c,e>}

S={<b,c>,<c,d>,<d,e>,<e,a>}

試求出合成關系R?S的關系矩陣MR?S設R是從集合X到Y的關系，IX是X上的恒等關系，IY是Y上的恒等關系，則有IX?R=R?IY=R。定理4.3.3

設X,Y,Z和W都是集合。R是從X到Y的關系，S是從Y到Z的關系，T是從Z到W的關系。于是有(R?S)?T=R?(S?T)。4.3.2關系的合成運算(4)一般來說，關系的合成運算不滿足交換律。定義4.3.3

設R是集合X中的二元關系，n∈N，于是R的n次冪Rn定義為：

(1)R0=IX

(2)Rn+1=Rn?R定理4.3.4

設R是集合X中的二元關系，m,n∈N，則有

(1)Rm?Rn=Rn?Rm=Rm+n

(2)(Rm)n=Rmn4.3.2關系的合成運算(5)例4.3.4

設集合設X={a,b,c}，且X中的關系定義如下：

R1={<a,b>,<a,c>,<c,b>}

R2={<a,b>,<b,c>,<c,a>}

R3={<a,b>,<b,c>,<c,c>}

R4={<a,b>,<b,a>,<c,c>}

試求出這些關系的各次冪。4.3.2關系的合成運算(6)定理4.3.5

設A為含有n個元素的集合，R是A上的二元關系，則必存在s和t，使得

Rs=Rt，0≤s＜t≤2n2定理4.3.6設R是集合A上的二元關系，則R在A上是傳遞的，當且僅當R?RR。4.3.2關系的合成運算(7)函數是一種特殊的關系。需要注意以下兩點：

(1)任何關系都有逆關系。函數作為一種關系也有逆關系，但其逆關系不一定是函數。也即，函數不一定有逆函數。

(2)函數的復合運算與關系的合成運算的順序不一樣。關系的合成運算是從左到右進行的；而函數的復合運算是從右到左進行的，這是為了與人們通常寫函數的習慣一致。合成運算對于并運算滿足分配律4.3.2關系的合成運算(8)定理設R和S都是集合A={a1,…,an}上的二元關系，關系矩陣分別是MR=(rij)和MS=(sij)，則

(1)R∩S的關系矩陣MR∩S=MR∧MS=(rij∧sij)，其中運算∧的定義為：rij∧sij=min(rij,sij).

(2)R∪S的關系矩陣MR∪S=MR∨MS=(rij∨sij)，其中運算∨的定義為：rij∨sij=max(rij,sij).

(3)R-1的關系矩陣MR-1=MRT，即MR的轉置.

(4)R?S的關系矩陣MR?S=MR·MS，其中的”·”為布爾乘，或稱邏輯乘，也即0·0=0，1·0=0·1=0，1·1=1.作業(yè)：習題15.給定集合X={1,2,3,4}，且X中的關系R={<1,1>,<1,2>,<1,4>,<2,1>,<2,2>,<3,3>,<4,1>,<4,4>}，試作出R的關系矩陣和關系圖，并判別R所具有的性質。18.給定集合X={0,1,2,3}，x,y∈X，且X中有關系：

R1={<x,y>|y=x+1或y=x/2}

R2={<x,y>|x=y+2}

求出下列合成關系：

(1)R1?R2(2)R2?R1(3)R1?R2?R1(4)R12(5)R234.4關系的閉包運算關系的閉包是對關系的一種擴充，即，通過添加序偶以使得關系具有原本沒有的某種性質。

自反閉包（對稱閉包、傳遞閉包）就是包含R的具有自反性（對稱性、傳遞性）的最小集合。4.4關系的閉包運算(1)定義4.4.1

設R和R’是集合A上的兩個關系，稱R’是R的自反閉包，如果：

(1)R’是自反的；

(2)RR’；

(3)若R’’也是A上的自反關系，且RR’’，則R’R’’。定義4.4.2

設R和R’是A上的兩個關系，稱R’是R的對稱閉包，如果：

(1)R’是對稱的；

(2)RR’；

(3)若R’’也是A上的對稱關系，且RR’’，則R’R’’。4.4關系的閉包運算(2)定義4.4.3

設R和R’是集合A上的關系，稱R’是R的傳遞閉包，如果：

(1)R’是傳遞的；

(2)RR’；

(3)若R’’是A上的傳遞的關系且RR’’，則R’R’’。自反閉包r(R)是包含R且具有自反性的最小關系，

對稱閉包s(R)是包含R且具有對稱性的最小關系，

傳遞閉包t(R)是包含R且具有傳遞性的最小關系。4.4關系的閉包運算(3)定理4.4.1

設R是集合A上的二元關系，則

(1)r(R)=R∪IA

(2)s(R)=R∪R-1

(3)t(R)=R∪R2∪…。

若|A|=n，則t(R)=R∪R2∪…∪Rn例4.4.1設X={a,b,c,d,e,f}，X上的關系R={<a,b>,<b,c>,<c,a>,<d,f>,<f,c>}，求r(R),s(R)和t(R)并畫出其關系圖。例4.4.2設A={a,b,c}，A上的關系R={<a,b>,<b,c>,<c,a>}，求t(R)。4.4關系的閉包運算(4)定理設R是有限集合A上的關系，|A|=n，MR是R的關系矩陣，則：

(1)Mr(R)=MR∨E，E為n階單位矩陣；

(2)Ms(R)=MR∨MRT；

(3)

Mt(R)=MR∨MR2∨…∨MRn

=MR∨(MR)2∨…∨(MR)nWarshall算法：只對關系矩陣作行初等變換。對第i列，若bji=1，則把第i行加到第j行，作為新的第j行。4.4關系的閉包運算(5)定理4.4.2

設R是集合A上的二元關系，則

(1)R是自反的，當且僅當R=r(R)

(2)R是對稱的，當且僅當R=s(R)

(3)R是傳遞的，當且僅當R=t(R)定理4.4.3

設R是集合A上的二元關系，則

(1)R是自反的，則s(R)和t(R)也是自反的。

(2)R是對稱的，則r(R)和t(R)也是對稱的。

(3)R是傳遞的，則r(R)也是傳遞的。

(s(R)未必是傳遞的)例設A={1,2}，R={<1,1>,<1,2>}4.4關系的閉包運算(6)定理4.4.4

設R1和R2是集合A上的二元關系，且R1R2，則

(1)r(R1)r(R2)

(2)s(R1)s(R2)

(3)t(R1)t(R2)定理4.4.5

設R是集合A上的二元關系，則

(1)rs(R)=

sr(R)

(2)rt(R)=

tr(R)

(3)st(R)ts(R)例設X={1,2,3}，R={<1,1>,<2,1>}作業(yè)：習題P101151719.(2)222324.(1)25.(2)4.5相容關系與覆蓋(1)定義4.5.1

設R是集合A上的二元關系，如果R是自反的，對稱的，則稱R是相容關系。例4.5.1

設A={cat,teacher,cold,desk,knife,by}，在A上定義關系R如下

R={<x,y>|x,y∈A且x和y有相同的字母}

試畫出R的關系圖和關系矩陣，并說明R是相容的。4.5相容關系與覆蓋(2)相容關系是自反的和對稱的，因此其關系圖可以簡化：將每個頂點處的環(huán)省略，兩個頂點之間若有2條方向相反的邊，則只保留1條，并省略箭頭。相容關系的關系矩陣的簡化：因為其對稱性，關系矩陣是對稱矩陣；由于其自反性，主對角線元素全是1，所以可只列出矩陣中主對角線以下的下三角矩陣。4.5相容關系與覆蓋(3)定義4.5.2給定非空集合A，設有集合S={S1,S2,…,Sm}，其中，SiA且Si≠?，i=1,2,…,m，且S1∪S2∪…∪Sm=A，則稱集合S為A的覆蓋。定理4.5.1給定集合A上的一個覆蓋S={S1,S2,…,Sm}，由它確定的關系

R=(S1×S1)∪(S2×S2)∪…∪(Sm×Sm)

是相容關系。注意：不同的覆蓋可以構造出相同的相容關系。4.5相容關系與覆蓋(4)定義4.5.3

設R是集合A上的相容關系，若有A的子集C，使得對任何x,y∈C，都有xRy，則稱C是由相容關系R產生的相容類，簡稱相容類。并且在A-C中，如果沒有任何一個元素與C中的所有元素都有R關系，則稱C是由相容關系R產生的最大相容類。

由R所產生的所有最大相容類所構成的集合，稱為集合集合A的完全覆蓋。定理

設R是有限集合A上的相容關系，C是一個相容類，則存在一個最大相容類C’，使CC’。相容關系的完全覆蓋的求法關系圖法：R是集合A上的一個相容關系，R的簡化關系圖中每個最大完全多邊形的所有頂點的集合就是一個最大相容類。所謂完全多邊形，指的是一個多邊形，它的任何2個不相同頂點之間恰有1條邊。最大完全多邊形，是指在完全多邊形中再任意加一個頂點，就不再是完全多邊形。關系矩陣法：

(1)若對應于某個元素xj的行和列上的值均為零，則它單獨構成一個最大相容類，于是刪去該元素對應的行和列。

(2)對簡化了的矩陣從最后一列開始向左掃描，直到遇到一個至少包含一個非零元素的列。列出這一列中各非零元素所對應的元素對的集合。

(3)繼續(xù)向左掃描，直到遇到至少包含一個非零元素的列，同樣列出這一列中各非零元素所對應的元素對的集合。若后列出的集合中，有某個元素與前面的集合中各元素都有關系R，則將該元素加入到前面的集合中。若后列出的集合中，某個元素只與前面的集合中部分元素有關系R，則也將這些有關系的元素組成新的集合。最后，刪除已作為其他元素的子集的集合。

(4)重復步驟(3)，直到掃描完所有的列。最后得到的各集合(包括單個元素所構成的集合)的全體就是完全覆蓋。4.6等價關系與劃分(1)定義4.6.1R是集合A上的二元關系，如果R是自反的，對稱的和傳遞的，則稱R是等價關系。

等價關系一定是相容關系，反之不一定。例4.6.1“模k同余”：對a,bI,a≡b(modk)等價于k|(b-a)。I上的“模k同余”關系是個等價關系。定義4.6.2

設R是集合A上的等價系，a∈A，稱{x|x∈A,xRa}是以a為代表元的一個等價類，記為[a]R，簡記為[a]。例4.6.2

求出例4.6.1中當k=3時各元素的等價類。一個等價類中的所有元素互相等價。定理4.6.1

設R是集合A上的等價關系，則：

(1)對任何a∈A，[a]≠?；

(2)對任何a,b∈A，若aRb，則[a]=[b]或者[a]∩[b]=?；

(3)。

指的是取遍A中每個元素為代

表元的等價類的并集.4.6等價關系與劃分(2)4.6等價關系與劃分(3)定義4.6.3

設R是集合A上的等價關系。由A中各元素生成的關于R的等價類的集合{[x]R|x∈A}，稱為A關于R的商集。記為A/R。定義4.6.4給定非空集合A，設有集合S={S1,S2,…,Sm}，其中，SiA且Si≠?，i=1,2,…,m，且Si∩Sj=?(i≠j)，以及S1∪S2∪…∪Sm=A，則稱集合S為A的劃分。定理4.6.2

設R是非空集合A上的等價關系，則A關于R的商集是A的一個劃分，該劃分稱為A的等價劃分。(這個劃分是唯一的)4.6等價關系與劃分(4)定理4.6.3

設S={S1,…,Sn}是非空集合A的一個劃分，令Ri=Si×Si,i=1,…,n。則R=R1∪R2∪…∪Rn是A上的等價關系，R產生的等價劃分就是S。例4.6.3A={a,b,c,d,e,f}，A的一個劃分S={{a,b},{c,d},{e,f}}，求S確定的等價關系R。集合A上的劃分和等價關系是一一對應的。作業(yè)：習題P103272831324.7偏序關系(1)集合上元素的次序關系：

偏序關系、擬序關系、全序關系、良序關系定義4.7.1

設R是集合A上的二元關系，如果R是自反的、反對稱的、傳遞的，則稱R是偏序關系，簡記為“≤”。A和≤一起稱為偏序集，記為<A,≤>。例4.7.1

在實數集R上，證明大于等于關系“≥”是偏序關系。例4.7.2

設集合A={2,3,6,8,12,24,36}，R是集合A上的整除關系，試證明R是集合A上的偏序關系，并畫出R的關系圖。4.7偏序關系(2)偏序關系關系圖的簡化：省略環(huán)，省略傳遞邊(沒有三角形)，省略箭頭(方向朝上，沒有水平線)定義4.7.2

設<A,≤>是一個偏序集。x,y∈A，若x≤y且x≠y，且不存在z∈A滿足x≤z,z≤y，則稱y蓋住x。簡化后的偏序關系的關系圖稱為哈斯圖。例

A={1,2,3,4}，偏序<P(A),>。{1,2}蓋住{1}。但{1,2,3}不蓋住{1}，因為有{1,3}∈P(A)。4.7偏序關系(3)哈斯圖的構造方法：

(1)用頂點表示集合A中的元素，頂點的位置按照元素在偏序中的次序由底向上排列；

(2)若元素b蓋住a，則將b畫在a的上層，并在a,b之間用一條線段相連；

(3)若a,b直接沒有關系，b,a之間也沒有關系，則把a,b畫在同一層上。

注：若a≤b且a≠b，但b不蓋住a，則a,b之間不能有連線。4.7偏序關系(4)例4.7.3設集合A={2,3,6,12,24,36}，R是集合A上的整除關系，試畫出”≤”的哈斯圖。例4.7.4A={a,b,c}，畫出偏序<P(A),>的哈斯圖。定義4.7.3

設R是集合A上的二元關系，如果R是反自反的、傳遞的，則稱R是擬序關系，簡記為“＜”。A和＜一起稱為擬序集，記為<A,＜>。注：擬序集必是反對稱的。

實數集上的小于關系，集合的冪集上的真包含關系。4.7偏序關系(5)定義4.7.4

設<A,≤>是一個偏序集，對于任意的x,y∈A，如果x≤y或y≤x，則稱x和y是可比的。如果x≤y和y≤x都不滿足，則稱x和y是不可比的。定義4.7.5

設“≤”是A上的一個二元關系，若對于任何的x,y∈A，x和y都是可比的，則稱≤是A上的一個線序或全序關系，將<A,≤>稱為全序集。例

設A={a,b,c}，在A上有關系R={<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<a,c>}，則R是全序關系。例4.7.5

畫出集合A={3,9,27,54}上的整除關系的哈斯圖，并說明是否為全序關系。4.7偏序關系(6)全序關系的哈斯圖是一條鏈。定義4.7.6

設<A,≤>是一個偏序集，集合B是A的子集。若b∈B，且不存在任何元素x∈B，使得b≤x且b≠x，則稱b是集合B的一個極大元。同理，b∈B，且不存在任何元素x∈B，使得x≤b且b≠x，則稱b是集合B的一個極小元。例4.7.6

設A={2,3,5,7,14,15,21}，其偏序關系為R={<2,2>,<3,3>,<5,5>,<7,7>,<14,14>,<15,15>,<21,21>,<2,14>,<3,15>,<3,21>,<5,15>,<7,14>,<7,21>}，求B={2,3,7,14,21}的極大元和極小元。4.7偏序關系(7)定義4.7.7

設<A,≤>是一個偏序集，B是A的一個子集。如果存在b∈B，使得對任何元素x∈B，都有x≤b，則稱b是<B,≤>的最大元。同理，如果存在b∈B，使得對任何x∈B都有b≤x，則稱b是<B,≤>的最小元。例4.7.7

在例4.7.2的哈斯圖中，設B={2,6,8,12}，求其極大元，極小元，最大元，最小元。定理4.7.1設<A,≤>是一個偏序集，B是A的一個子集。若B有最大元或最小元，則必是唯一的。

4.7偏序關系(8)最大元，最小元，極大元，極小元：(1)偏序集不一定有最大元或最小元，若有則必唯一；且最大元定是極大元，最小元定是極小元。(2)偏序集定有極大元和極小元，但可能不唯一。(3)哈斯圖中向上路徑的每一個終點都是一個極大元；極大元不可能向上到達任何其他元素，任何其他元素不可能向上達到極小元。(4)任何其他元素都可以向上達到最大元，最小元可以向上達到任何其他元素。4.7偏序關系(9)定義4.7.8

設<A,≤>是一個偏序集，BA,若有a∈A，使得對任何x∈B，都有x≤a，稱a是B的一個上界。同理，若有a∈A，使得對任何x∈B，都有a≤x，稱a是B的一個下界。定義4.7.9

設<A,≤>是一個偏序集，BA。若存在B的某個上界a，使得對于B的任何上界x，滿足a≤x，則稱a是B的最小上界(上確界)，記做LUBB。同理，若存在B的某個下界a，使得對B的任何下界x，都有x≤a，則稱a是B的最大下界(下確界)

，記做GLBB。4.7偏序關系(10)例4.7.8

在例4.7.4中，設B={{b,c},,{c},?}，求B的上界和下界。例4.7.9

偏序集<A,R>的關系圖如圖所示，試求出其極大元，極小元，最大元，最小元。試求出子集{b,c,d},{b,d,e},{a,b,c}的上界、下界、最小上界和最大下界。abcde4.7偏序關系(11)定理4.7.2設<A,≤>是一個偏序集，BA，若B有最大下界或最小上界未必存在，則必唯一。定義4.7.10設<A,≤>是一個偏序集，若A的任一非空子集都有最小元，則稱<A,≤>為良序集。

如自然數集對于“小于等于”關系是良序集。定理4.7.3每一個有限全序集，一定是良序集。定理4.7.4每一個良序集，一定是全序集。4.7偏序關系(12)偏序集的一個子集，其上界和下界未必存在，若存在也未必唯一；若存在，則可能存在于子集內部，也可能不在子集內，而在整個偏序集中。有上界、下界，則必有最小上界、最大下界。Review偏序，可比，蓋住哈斯圖，極大元，極小元，最大元，最小元上界，下界，最大下界，最小上界，格作業(yè)：習題36.試畫出下列集合中的“整除”關系的哈斯圖。

(1){1,2,3,4,6,8,12,24}38.針對下列各個偏序集的哈斯圖，分別寫出各偏序關系的集合表達式。39.分別找出下列各偏序集<A,≤>的極大元、極小元、最大元和最小元。

(2)A={a,b,c,d,e},R≤={<c,d>}∪IA40.設集合A={1,2,…,12}，≤為整除關系，B={2,3,4}。在偏序集A中求B的上界、下界、最小上界和最大下界。第五章函數函數簡介5.1函數的基本概念和性質5.2函數的復合與反函數函數簡介函數是一種具有特殊性質的二元關系。用計算機的術語來說，函數是輸入和輸出之間的一種對應。換言之，對每一個輸入，函數相應產生一個輸出。再如，將編譯程序看作是一個函數，每輸入一個源程序，便得到一個機器語言程序，它是源程序的輸出值。從變量之間的對應關系定義一個函數：設有兩個變量x和y，如果在x的變化過程中，y隨之發(fā)生相應的變化，則稱y是x的函數。5.1函數的基本概念和性質5.1.1函數的定義5.1.2

函數的性質5.1.1函數的定義(1)定義5.1.1

設F為二元關系，若對任意的x∈dom(F)都存在唯一的y∈ran(F)，使得xFy成立，則稱F為函數。例5.1.1

判斷下列關系是否為函數。

(1)F1={<x1,y1>,<x2,y1>,<x3,y2>}

(2)F2={<x1,y1>,<x1,y2>,<x2,y1>,<x3,y2>}函數一般用大寫或小寫英文字母表示。如果<x,y>∈F，則記作F(x)=y，并稱x為自變量，y為與自變量x對應的F的函數值。函數也有全域、定義域、值域的概念，其定義與關系相同。5.1.1函數的定義(2)函數是集合，所以函數f和g相等就是它們的集合表達式相等，即f=gfg∧gf。也就是，dom(f)=dom(g)，且對任意的xdom(f)=dom(g)，有f(x)=g(x)。定義5.1.2

設A和B是兩個非空集合，如果函數f滿足以下條件：(1)dom(f)=A，(2)ran(f)=B，則稱f是從A到B的一個函數，記為f:A→B。定義5.1.3

設A、B為集合，所有從A到B的函數構成集合BA，讀作“B上A”。即BA，={f|f:A→B}。5.1.1函數的定義(3)例5.1.2

設A={0,1,2}，B={a,b}，求BA。一般來說，如果|A|=m，|B|=n，其中m,n不全為0，則|BA|=nm。函數也常稱為映射，用y=f(x)表示在函數f的作用下，稱x的象是y，或者y的原象是x。定義5.1.4

設X和Y為任意集合，f:X→Y，X‘X，Y’Y，則

(1)X’在f下的象f(X’)定義為：

f(X’)={y|(x)(xX’∧y=f(x))}，f(X)記為f的值域；

(2)Y’在f下的原象f-1(Y’)定義為：

f-1(Y’)={x|xX∧f(x)Y’}

顯然，f(X’)Y，f-1(Y’)X5.1.1函數的定義(4)例5.1.3設A={a,b,c,d,e}，B={1,2,3,4}，φ:A→B。φ={<a,1>,<b,2>,<c,1>,<d,1>,<e,3>}。求φ({a,b,c}),φ(A),φ-1({1}),φ-1({1,2,3})例5.1.4設f:N→N，當x為奇數，f(x)=(x-1)/2，否則，f(x)=x/2。求f({0,1}),f(N),f-1({0}),f(?),f-1(?)設f:X→Y，X非空。定義RX×X為

x1,x2X,x1Rx2當且僅當f(x1)=f(x2)

則R是X上的等價關系(稱之為由f誘導的等價關系)，并且由關系R確定的劃分為：

{f-1({y})|yY∧f-1({y})≠?}5.1.1函數的定義(5)令g:X→X/R，g(x)=[x]R

稱g是由f誘導的規(guī)范映射?？梢妼o定的一個函數均可得到一個規(guī)范映射。例5.1.5設X={a,b,c,d}，Y={0,1,2,3,4}，f:X→Y，且f(a)=f(c)=1,f(b)=0,f(d)=3，求f誘導的等價關系和規(guī)范映射。例5.1.6設X和Y為任意集合，f:X→Y，AX，BY，證明：(1)f(A∪B)=f(A)∪f(B)；

(2)f(A∩B)f(A)∩f(B)例

設f={<a,1>,<b,2>,<c,1>}，驗證上例(2)的逆。5.1.2

函數的性質(1)定義5.1.5

設函數f:A→B,

(1)如果對任何x1,x2∈A,x1≠x2

f(x1)≠f(x2)，則稱f是單射的。

(2)如果ran(f)=B，則稱f是滿射的。

(3)如果f既是單射又是滿射，則稱f是雙射的(或一一對應的)。定理5.1.1

設f:A→B，且A和B是有限集，

(1)若f是滿射，則|B|≤|A|

(2)若f是單射，則|A|≤|B|

(3)若f是雙射，則|A|=|B|鴿巢原理：m只鴿子飛進n個鴿巢，若m>n，則至少有兩只鴿子飛進同一鴿巢。定義5.1.6(1)設f:A→B，若存在y∈B使得對所有的x∈A都有f(x)=y，則稱f:A→B是常函數。

(2)A上的恒等關系IA就是A上的恒等函數，對于所有的x∈A都有IA(x)=x。

(3)設f:R→R，對于任意的x1,x2∈R，如果x1<x2則有f(x1)≤f(x2)，就稱f是單調遞增的。如果x1<x2則有f(x1)<f(x2)，就稱f是嚴格單調遞增的。類似的，也可以定義單調遞減和嚴格單調遞減的函數。它們統(tǒng)稱為單調函數。(4)設A為集合，對于任何的A’A，A’的特征函數χA’:A→{0,1}定義為：當a∈A’時，χA’(a)=1；當a∈A-A’時，χA’(a)=0。

(5)設R是A上的等價關系，定義一個從A到A/R的函數g:A→A/R且g(a)=[a]，它把A中的元素a映射到a的等價類[a]。稱g是從A到商集A/R的自然映射。集合的特征函數所描述的集合是由那些特征函數值為1的元素所組成的。給定χA，則可得到集合{x|χA(x)=1}。因此集合與特征函數之間存在一一對應關系。定理5.1.2

設A,B是全集U的兩個子集，則對于任意的xU：

(1)χA(x)=1A=U

(2)χA(x)=0A=?

(3)χA(x)≤χB(x)AB

(4)χA(x)=χB(x)A=B

(5)χ~A(x)=1-χA(x)

(6)χA∩B(x)=χA(x)χB(x)

(7)χA∪B(x)=χA(x)+χB(x)-χA(x)χB(x)

(8)χA-B(x)=χA(x)(1-χB(x))

(9)(χA(x))2=

χA(x)特征函數的運算可用來表示集合的運算。例5.1.10

利用特征函數證明A∩(B∪C)=(A∪B)∩(A∪C).5.2