關(guān)系及其運(yùn)算課件

關(guān)系及其運(yùn)算離散數(shù)學(xué)－集合論南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系1感謝你的觀看2019年8月23關(guān)系及其運(yùn)算離散數(shù)學(xué)－集合論1感謝你的觀看2019年8月23回顧集合的基本概念集合及其描述集合相等、子集關(guān)系冪集、笛卡爾乘積集合運(yùn)算交并補(bǔ)、廣義交、廣義并集合恒等式集合相關(guān)命題的證明方式2感謝你的觀看2019年8月23回顧集合的基本概念2感謝你的觀看2019年8月23提要關(guān)系的定義關(guān)系的表示關(guān)系的運(yùn)算0-1矩陣運(yùn)算關(guān)系的性質(zhì)3感謝你的觀看2019年8月23提要關(guān)系的定義3感謝你的觀看2019年8月23有序?qū)Γ∣rderedpair）(a,b)是集合{{a},{a,b}}的簡寫次序的體現(xiàn)(x,y)=(u,v)iffx=u且

y=v若{{x},{x,y}}={{u},{u,v}}，則{x}={u}或{x}={u,v},因此x=u。假設(shè)yv(1)若x=y,左邊={{x}},而vx,右邊{{x}};(2)若xy,則必有{x,y}={u,v},但y既非u,又非v,矛盾。4感謝你的觀看2019年8月23有序?qū)Γ∣rderedpair）(a,b)是集合{{a}笛卡爾乘積（CartesianProduct）對任意集合A,B

笛卡爾積AB={(a,b)|aA,bB}例：{1,2,3}{a,b}={(1,a),(3,a),(3,a),(1,b),(2,b),(3,b)}若A，B是有限集合，|AB|=|A||B|5感謝你的觀看2019年8月23笛卡爾乘積（CartesianProduct）對任意集合A例題A={1,2},

(A)×A=?|A|=m,|B|=n,|A×B|=?6感謝你的觀看2019年8月23例題A={1,2},(A)×A=?6感謝你的觀看201（二元）關(guān)系的定義若A,B是集合,從A到B的一個(gè)關(guān)系是AB的一個(gè)子集.集合,可以是空集集合的元素是有序?qū)﹃P(guān)系意味著什么？兩類對象之間建立起來的聯(lián)系！7感謝你的觀看2019年8月23（二元）關(guān)系的定義若A,B是集合,從A到B的一個(gè)關(guān)系是A從A到B的二元關(guān)系笛卡爾乘積的子集“從A到B的關(guān)系”R；RAB若A=B：稱為“集合A上的（二元）關(guān)系”例子常用的數(shù)學(xué)關(guān)系：不大于、整除、集合包含等網(wǎng)頁鏈接、文章引用、相互認(rèn)識8感謝你的觀看2019年8月23從A到B的二元關(guān)系笛卡爾乘積的子集8感謝你的觀看2019年8特殊的二元關(guān)系集合A上的空關(guān)系:空關(guān)系即空集全域關(guān)系

EA:EA={(x,y)

|x,yA}恒等關(guān)系

IA:IA

={(x,x)

|xA}9感謝你的觀看2019年8月23特殊的二元關(guān)系集合A上的空關(guān)系:空關(guān)系即空集9感謝你的函數(shù)是一種特殊的關(guān)系函數(shù)f:ABR={(x,f(x))

|xA}是一個(gè)從A到B的一個(gè)關(guān)系10感謝你的觀看2019年8月23函數(shù)是一種特殊的關(guān)系函數(shù)f:AB10感謝你的觀看2關(guān)系的表示假設(shè)A={a,b,c,d},B={α,β,γ}//假設(shè)為有限集合集合表示:R1={(a,β),(b,α),(c,α),(c,γ)}0-1矩陣有向圖abcdadcbAB11感謝你的觀看2019年8月23關(guān)系的表示假設(shè)A={a,b,c,d},B={α,β,γ}二元關(guān)系和有向圖關(guān)系RABA和B是集合有序?qū)?x,y)R若A=B,R中存在序列：(x1,x2),(x2,x3),…,(xn-1,xn)有向圖(VD

,ED)頂點(diǎn)集VD=AB有向邊集ED從x到y(tǒng)有一條邊圖D中存在從x1到xn

的長度為n-1的通路12感謝你的觀看2019年8月23二元關(guān)系和有向圖關(guān)系RAB有向圖(VD,ED)關(guān)系的運(yùn)算（1）關(guān)系是集合,所有的集合運(yùn)算對關(guān)系均適用例子:自然數(shù)集合上:“<”“=”等同于“”自然數(shù)集合上:“”“”等同于“=”自然數(shù)集合上:“<”“>”等同于13感謝你的觀看2019年8月23關(guān)系的運(yùn)算（1）關(guān)系是集合,所有的集合運(yùn)算對關(guān)系均適用13關(guān)系的運(yùn)算（2）與定義域和值域有關(guān)的運(yùn)算domR={x|y(x,y)R}ranR={y|x(x,y)R}fldR=domRranRR

A={(x,y)|xA

xRy}

RR[A]={y|x(xA

(x,y)R)}=ran(RA)ranR例：A={1,2,3,4,5},B={1,3,5,6},A上關(guān)系R：

R={(1,2),(1,4),(2,3),(3,5),(5,2)},

求RB、R[B]、R(1)和R(2)14感謝你的觀看2019年8月23關(guān)系的運(yùn)算（2）與定義域和值域有關(guān)的運(yùn)算14感謝你的觀看20關(guān)系的運(yùn)算（3）逆運(yùn)算R-1={(x,y)|(y,x)R}注意:如果R是從A到B的關(guān)系,則R-1是從B到A的。(R-1)-1=R例子：(R1R2)-1=R1-1R2-1

(x,y)(R1R2)-1

(y,x)(R1R2)(y,x)R1

或(y,x)R2

(x,y)R1-1

或(x,y)R2-115感謝你的觀看2019年8月23關(guān)系的運(yùn)算（3）逆運(yùn)算15感謝你的觀看2019年8月23關(guān)系的運(yùn)算（4）關(guān)系的復(fù)合（合成,Composition）設(shè)

R1AB,R2BC,R1與R2的復(fù)合（合成）,記為R2

?

R1,定義如下：R2

?

R1={(a,c)AC

|bB((a,b)R1(b,c)R2)

}16感謝你的觀看2019年8月23關(guān)系的運(yùn)算（4）關(guān)系的復(fù)合（合成,Composition）復(fù)合關(guān)系的圖示(a,c)R2

?

R1當(dāng)且僅當(dāng)aA,cC,且存在bB，使得(a,b)R1,(b,c)R2abcR1R217感謝你的觀看2019年8月23復(fù)合關(guān)系的圖示(a,c)R2?R1當(dāng)且僅當(dāng)a關(guān)系的復(fù)合運(yùn)算：舉例設(shè)A={a,b,c,d},R1,R2為A上的關(guān)系，其中： R1={(a,a),(a,b),(b,d)} R2={(a,d),(b,c),(b,d),(c,b)}則： R2

?

R1={(a,d),(a,c),(a,d)} R1

?

R2={(c,d)} R12={(a,a),(a,b),(a,d)}18感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算：舉例設(shè)A={a,b,c,d},R1,關(guān)系的復(fù)合運(yùn)算的性質(zhì)（1）結(jié)合律給定R1AB,R2BC,R3CD,則：

(R3

?

R2)?

R1=R3

?

(R2

?

R1)證明左右兩個(gè)集合相等.19感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算的性質(zhì)（1）結(jié)合律19感謝你的觀看2019年8關(guān)系的復(fù)合運(yùn)算的性質(zhì)（2）復(fù)合關(guān)系的逆關(guān)系給定R1AB,R2BC,則：

(R2

?

R1)-1=R1-1

?

R2-1同樣，證明左右兩個(gè)集合相等(x,y)(R2

?

R1)-1

(y,x)R2

?

R1

tB((y,t)R1

(t,x)R2)

tB((t,y)

R1-1(x,t)R2-1)

(x,y)R2-1

?

R1-120感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算的性質(zhì)（2）復(fù)合關(guān)系的逆關(guān)系20感謝你的觀看2關(guān)系的復(fù)合運(yùn)算的性質(zhì)（3）對集合并運(yùn)算滿足分配律給定FAB,GBC,HBC,則：

(GH)

?

F=(G?

F)(H?

F)對集合交運(yùn)算：

(GH)

?

F(G?

F)(H?

F)注意：等號不成立。A={a},B={s,t},C=;F={(a,s),(a,t)},G={(s,b)},H={(t,b)};GH=?,(G?

F)(H?

F)={(a,b)}

21感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算的性質(zhì)（3）對集合并運(yùn)算滿足分配律21感謝你的0-1矩陣運(yùn)算令0-1矩陣M1=[aij],M2=[bij]:C=M1M2:cij=1iff.aij=bij=1C=M1M2:cij=1iff.aij=1或bij=1令rs矩陣M1=[aij]；st矩陣M2=[bij]:C=M1M2:cij=1iff.22感謝你的觀看2019年8月230-1矩陣運(yùn)算令0-1矩陣M1=[aij],M2=[bij關(guān)系運(yùn)算的矩陣法（1）命題23感謝你的觀看2019年8月23關(guān)系運(yùn)算的矩陣法（1）命題23感謝你的觀看2019年8月23證明：24感謝你的觀看2019年8月23證明：24感謝你的觀看2019年8月23關(guān)系的性質(zhì)：自反性reflexivity集合A上的關(guān)系

R

是:自反的reflexive：定義為：對所有的

aA,(a,a)R反自反的irreflexive：定義為：對所有的aA,(a,a)R注意區(qū)分”非”與”反”設(shè)A={1,2,3},RAA{(1,1),(1,3),(2,2),(2,1),(3,3)}是自反的{(1,2),(2,3),(3,1)}是反自反的{(1,2),(2,2),(2,3),(3,1)}既不是自反的，也不是反自反的25感謝你的觀看2019年8月23關(guān)系的性質(zhì)：自反性reflexivity集合A上的關(guān)系R自反性與恒等關(guān)系R

是A

上的自反關(guān)系

IAR,

這里IA是集合A上的恒等關(guān)系,即:IA={(a,a)|aA}直接根據(jù)定義證明：只需證明：對任意(a,b)，若(a,b)IA,則(a,b)R只需證明：對任意的a,若aA,則(a,a)R26感謝你的觀看2019年8月23自反性與恒等關(guān)系R是A上的自反關(guān)系IAR,自反關(guān)系的有向圖和0-1矩陣abcA={a,b,c}27感謝你的觀看2019年8月23自反關(guān)系的有向圖和0-1矩陣abcA={a,b,c}27感謝關(guān)系的性質(zhì)：對稱性

Symmetry集合A上的關(guān)系R是:對稱的symmetric：定義為：若(a,b)R,則(b,a)R反對稱的anti-~：定義為：若(a,b)R

且(b,a)R，則a=b設(shè)A={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)}是對稱的{(1,2),(2,3),(2,2),(3,1)}是反對稱的28感謝你的觀看2019年8月23關(guān)系的性質(zhì)：對稱性Symmetry集合A上的關(guān)系R是:2理解對稱性關(guān)系R滿足對稱性：對任意(a,b)，若

(a,b)R,則

(b,a)R注意：是對稱關(guān)系。反對稱并不是對稱的否定:(令：A={1,2,3},RAA){(1,1),(2,2)}既是對稱的，也是反對稱的是對稱關(guān)系，也是反對稱關(guān)系。29感謝你的觀看2019年8月23理解對稱性關(guān)系R滿足對稱性：對任意(a,b)，若(a,b)對稱性與逆關(guān)系R

是集合A上的對稱關(guān)系

R-1=R

證明一個(gè)集合等式R-1=R

若(a,b)R-1,則(b,a)R,由R的對稱性可知(a,b)R,因此：R-1R;同理可得：RR-1;只需證明：對任意的(a,b)若(a,b)R,則(b,a)R30感謝你的觀看2019年8月23對稱性與逆關(guān)系R是集合A上的對稱關(guān)系R-1=R30對稱關(guān)系的有向圖和0-1矩陣abcA={a,b,c}31感謝你的觀看2019年8月23對稱關(guān)系的有向圖和0-1矩陣abcA={a,b,c}31感謝關(guān)系的性質(zhì)：傳遞性

transitivity集合A上的關(guān)系R是傳遞的transitive:若(a,b)R,(b,c)R,則(a,c)R設(shè)A={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)}傳遞的{(1,2),(2,3),(3,1)}是非傳遞的{(1,3)}?

?32感謝你的觀看2019年8月23關(guān)系的性質(zhì)：傳遞性transitivity集合A上的關(guān)系傳遞性與關(guān)系的乘冪關(guān)系的復(fù)合(乘)運(yùn)算滿足結(jié)合律，可以用

Rn表示

R?R?…?R

(n是正整數(shù))命題：(a,b)Rn

當(dāng)且僅當(dāng)：存在t1,t2,…,tn-1A,滿足：(a,t1),(t1,t2),…,(tn-2,tn-1),(tn-1,b)R。對n>=1用數(shù)學(xué)歸納法：n=1,trivial.奠基n=2,直接由關(guān)系復(fù)合的定義可得；歸納基于：Rn=Rn-1?R集合A上的關(guān)系R是傳遞關(guān)系

R2R必要性：任取(a,b)R2,根據(jù)上述命題以及R的傳遞性可得(a,b)R充分性：若(a,b)R,(b,c)R,則(a,c)R2,由R2R可得：(a,c)R，則

R是傳遞關(guān)系33感謝你的觀看2019年8月23傳遞性與關(guān)系的乘冪關(guān)系的復(fù)合(乘)運(yùn)算滿足結(jié)合律，可以用傳遞關(guān)系的有向圖和0-1矩陣abcA={a,b,c}34感謝你的觀看2019年8月23傳遞關(guān)系的有向圖和0-1矩陣abcA={a,b,c}34感謝一些常用關(guān)系的性質(zhì)35感謝你的觀看2019年8月23一些常用關(guān)系的性質(zhì)35感謝你的觀看2019年8月23關(guān)系運(yùn)算與性質(zhì)的保持36感謝你的觀看2019年8月23關(guān)系運(yùn)算與性質(zhì)的保持36感謝你的觀看2019年8月23下列關(guān)系是否自反的、對稱的、反對稱的或可傳遞的？關(guān)系S為：r1≤|r2|(r1,r2∈R)時(shí)解：s是自反的，因?yàn)閷θ我獾膔∈R，有r≤|r|。s不是對稱的，如-1≤|3|，但3>|-1|。s不是反對稱的，如-3≤|2|，2≤|-3|，但-3≠2。s不是可傳遞的，100≤|-101|，-101≤|2|，但100>|2|習(xí)題舉例一37感謝你的觀看2019年8月23下列關(guān)系是否自反的、對稱的、反對稱的或可傳遞的？關(guān)系S為：r38感謝你的觀看2019年8月2338感謝你的觀看2019年8月2339感謝你的觀看2019年8月2339感謝你的觀看2019年8月2340感謝你的觀看2019年8月2340感謝你的觀看2019年8月2341感謝你的觀看2019年8月2341感謝你的觀看2019年8月23小結(jié)關(guān)系：笛卡爾積的子集關(guān)系的運(yùn)算集合運(yùn)算；復(fù)合運(yùn)算；逆0-1矩陣運(yùn)算關(guān)系的性質(zhì)reflexivity,ir-~;symmetry,anti-~;transitivity圖特征；矩陣特征42感謝你的觀看2019年8月23小結(jié)關(guān)系：笛卡爾積的子集42感謝你的觀看2019年8月23作業(yè)教材內(nèi)容：[Rosen]2.1.3、8.1節(jié)8.3節(jié)課后習(xí)題：見課程主頁43感謝你的觀看2019年8月23作業(yè)教材內(nèi)容：[Rosen]2.1.3、8.1節(jié)8.3函數(shù)及其運(yùn)算離散數(shù)學(xué)－集合論南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系44感謝你的觀看2019年8月23函數(shù)及其運(yùn)算離散數(shù)學(xué)－集合論44感謝你的觀看2019年8月2回顧關(guān)系：笛卡爾積的子集關(guān)系的運(yùn)算集合運(yùn)算；復(fù)合運(yùn)算；逆0-1矩陣運(yùn)算關(guān)系的性質(zhì)reflexivity,ir-~;symmetry,anti-~;transitivity圖特征；矩陣特征45感謝你的觀看2019年8月23回顧關(guān)系：笛卡爾積的子集45感謝你的觀看2019年8月23提要函數(shù)的定義子集的像單射與滿射反函數(shù)函數(shù)的復(fù)合函數(shù)加法與乘法46感謝你的觀看2019年8月23提要函數(shù)的定義46感謝你的觀看2019年8月23函數(shù)(function)的定義設(shè)A和B為非空集合，從集合A到B的函數(shù)

f是對元素的一種指派，對A的每個(gè)元素恰好指派B的一個(gè)元素。記作

f:AB。Welldefined(良定義)f:AB：函數(shù)的型構(gòu)f的定義域（domain）是A，f的伴域（codomain）是B如果

f為A中元素a指派的B中元素為b，就寫成f(a)=b。此時(shí)，稱b是a的像，而a是b的一個(gè)原像。A中元素的像構(gòu)成的集合稱為f的值域range（f的像image）。函數(shù)也稱為映射(mapping)或變換(transformation)47感謝你的觀看2019年8月23函數(shù)(function)的定義設(shè)A和B為非空集合，從函數(shù)的集合定義48感謝你的觀看2019年8月23函數(shù)的集合定義48感謝你的觀看2019年8月23函數(shù)的集合定義（續(xù)）49感謝你的觀看2019年8月23函數(shù)的集合定義（續(xù)）49感謝你的觀看2019年8月23函數(shù)舉例下取整函數(shù)x:R→Z函數(shù)

f的圖像:{(a,b)|aAf(a)=b}JavaProgramint

floor(floatreal){…}xyfloor:float

→int

50感謝你的觀看2019年8月23函數(shù)舉例下取整函數(shù)x:R→Z函數(shù)f的圖像:函數(shù)舉例某課程成績ProgramCourseGrade

grade(StudentNamesname，CourseNamecname){…}Function：Grade:StudentName×CourseName→CourseGrade

函數(shù)原型函數(shù)型構(gòu)(signature)51感謝你的觀看2019年8月23函數(shù)舉例某課程成績ProgramFunction：函數(shù)原型函函數(shù)舉例設(shè)A為非空集合，A上的

恒等函數(shù)A:AA定義為A(x)=x，xA設(shè)U為非空集合，對任意的AU,特征函數(shù)A:U{0,1}定義為：A(x)=1，xAA(x)=0，xU-A52感謝你的觀看2019年8月23函數(shù)舉例設(shè)A為非空集合，A上的恒等函數(shù)A:AA定義為5函數(shù)的集合53感謝你的觀看2019年8月23函數(shù)的集合53感謝你的觀看2019年8月23函數(shù)(function)的相等函數(shù)相等f=gifdom(f)=dom(g)codom(f)=codom(g)x(xdom(f)→f(x)=g(x))54感謝你的觀看2019年8月23函數(shù)(function)的相等函數(shù)相等f=gif54感謝函數(shù)的相等55感謝你的觀看2019年8月23函數(shù)的相等55感謝你的觀看2019年8月23子集在函數(shù)下的像設(shè)

f是從集合A到B的函數(shù)，S是A的一個(gè)子集。

S

在

f下的像，記為f(S)，定義如下：f(S)={t|sS(t=f(s))}備注：f(A)即為

f的值域。56感謝你的觀看2019年8月23子集在函數(shù)下的像設(shè)f是從集合A到B的函數(shù)，S是A的一個(gè)Bf(S):TASfS的像和逆像S的像:Tabcb的逆像T的逆像是什么？57感謝你的觀看2019年8月23Bf(S):TASfS的像和逆像S的像:Tabcb的逆像T的并集的像設(shè)函數(shù)

f:AB，且X，Y是A的子集，則

f(XY)=f(X)f(Y)證明:f(XY)

f(X)f(Y)

對任意的t，若tf(XY),則存在sXY,滿足f(s)=t;假設(shè)sX,則tf(X),假設(shè)sY,則tf(Y),tf(X)f(Y)f(X)f(Y)f(XY)

對任意的t，若tf(X)f(Y)

情況1：tf(X),則存在sXXY,滿足f(s)=t,tf(XY)

情況2：tf(Y),同樣可得tf(XY)

tf(XY)58感謝你的觀看2019年8月23并集的像設(shè)函數(shù)f:AB，且X，Y是A的子集，則

f交集的像設(shè)函數(shù)

f:AB，且X，Y是A的子集，則f(XY)

f(X)f(Y)ABXYa1a2cf在f(X)f(Y)中，但不在f(XY)中59感謝你的觀看2019年8月23交集的像設(shè)函數(shù)f:AB，且X，Y是A的子集，則ABX函數(shù)性質(zhì):AB是單射（一對一的）injection,injectivefunction,one-to-onefunctionx1,x2A,若x1x2，則(x1)(x2)//等價(jià)的說法：x1,x2A,若(x1)=(x2)，則x1=x2//另一種等價(jià)的說法？:AB是滿射（映上的）surjection,surjectivefunction,ontofunctionyB,xA,使得(x)=y//等價(jià)的說法：f(A)=B:AB是雙射（一一對應(yīng)）bijection,bijectivefunction,one-to-onecorrespondence滿射+單射60感謝你的觀看2019年8月23函數(shù)性質(zhì):AB是單射（一對一的）60感謝你的觀看2019函數(shù)性質(zhì)的證明判斷:RRRR,(<x,y>)=<x+y,x-y>的性質(zhì)單射？令(<x1,y1>)=(<x2,y2>)x1+y1=x2+y2且x1-y1=x2-y2,易見：

x1=x2且y1=y2<x1,y1>=<x2,y2>滿射？任取<a,b>R×R，總存在<(a+b)/2,(a-b)/2>,使得(<(a+b)/2,(a-b)/2>)=<a,b>61感謝你的觀看2019年8月23函數(shù)性質(zhì)的證明判斷:RRRR,(<x,y>)=函數(shù)性質(zhì)的證明設(shè)A有限集合，f是從A到A的函數(shù)。f是單射當(dāng)且僅當(dāng)

f是滿射。62感謝你的觀看2019年8月23函數(shù)性質(zhì)的證明設(shè)A有限集合，f是從A到A的函數(shù)。f是單射反函數(shù)設(shè)f是從A到B的一一對應(yīng)，f的反函數(shù)是從B到A的函數(shù)，它指派給B中元素b的是A中滿足f(a)=b的（唯一的）a。f的反函數(shù)記作f-1。f(a)=b當(dāng)且僅當(dāng)f-1(b)=a任何函數(shù)都有反函數(shù)嗎？例子:RRRR,(<x,y>)=<x+y,x-y>f-1:RRRR,-1(<x,y>)=<?,?>63感謝你的觀看2019年8月23反函數(shù)設(shè)f是從A到B的一一對應(yīng)，f的反函數(shù)是從B到A的函函數(shù)的復(fù)合設(shè)g是從A到B的函數(shù)，f是從B到C的函數(shù)，f和g的復(fù)合用f

g表示，定義為：(f

g)(x)=f(g(x))，xAaAg(a)BCf(g(a))gff

g64感謝你的觀看2019年8月23函數(shù)的復(fù)合設(shè)g是從A到B的函數(shù)，f是從B到C的函數(shù)，f和g復(fù)合運(yùn)算的性質(zhì)函數(shù)的復(fù)合滿足結(jié)合律(f

g)

h=f(gh)滿射的復(fù)合是滿射單射的復(fù)合是單射

雙射的復(fù)合是雙射

設(shè)f是從A到B的雙射

f-1

f=Af

f-1=B65感謝你的觀看2019年8月23復(fù)合運(yùn)算的性質(zhì)函數(shù)的復(fù)合滿足結(jié)合律65感謝你的觀看2019年復(fù)合運(yùn)算66感謝你的觀看2019年8月23復(fù)合運(yùn)算66感謝你的觀看2019年8月23復(fù)合運(yùn)算67感謝你的觀看2019年8月23復(fù)合運(yùn)算67感謝你的觀看2019年8月23但是…若f

g是滿射，能推出f和g是滿射嗎？f一定是滿射，

g不一定是滿射。

若f

g是單射，能推出f和g是單射嗎？g一定是單射，f不一定是單射。

68感謝你的觀看2019年8月23但是…若fg是滿射，能推出f和g是滿射嗎？68感謝你gfABC69感謝你的觀看2019年8月23gfABC69感謝你的觀看2019年8月23gfABC70感謝你的觀看2019年8月23gfABC70感謝你的觀看2019年8月23函數(shù)的加法、乘法設(shè)f和g是從A到R的函數(shù)，那么f+g和fg也是從A到R的函數(shù)，其定義為(f+g)(x)=f(x)+

g(x)，xAfg(x)=f(x)g(x)，xA71感謝你的觀看2019年8月23函數(shù)的加法、乘法設(shè)f和g是從A到R的函數(shù)，那么f+g和遞增（遞減）函數(shù)設(shè)f的定義域和伴域都是實(shí)數(shù)(或其子集)，f是遞增的xy(xyf(x)f(y))f是嚴(yán)格遞增的xy(xyf(x)f(y))72感謝你的觀看2019年8月23遞增（遞減）函數(shù)設(shè)f的定義域和伴域都是實(shí)數(shù)(或其子集)，72練習(xí)73感謝你的觀看2019年8月23練習(xí)73感謝你的觀看2019年8月23練習(xí)74感謝你的觀看2019年8月23練習(xí)74感謝你的觀看2019年8月23一個(gè)有趣的例子自然數(shù)1,2,3,…,n2+1的任何一種排列中，必然含一個(gè)長度不小于n+1的嚴(yán)格遞增鏈或嚴(yán)格遞減鏈。7,4,3,5,2,1,9,8,6,10//////10,3,2,6,4,7,5,9,1,8在所給的序列中，以k開始的嚴(yán)格遞增序列長度為I(k),以k開始的嚴(yán)格遞減序列長度為D(k)。f:

k(I(k),D(k)),k{1,2,…,n2+1}f(7)=(3,5),f(4)=(4,4),f(3)=(4,3),f(5)=(3,3),f(2)=(3,2),f(1)=(3,1)f(9)=(2,3),f(8)=(2,2),f(6)=(2,1),f(10)=(1,1)f是單射：對于k1k2，如果k1排在k2前面，則I(k1)I(k2)，如果k2排在k1前面，則D(k2)D(k1)。反證法：給定任一種排列，假設(shè)嚴(yán)格遞增與遞減序列最大長度均不大于n：f的值域最多有n2個(gè)元素f不可能是單射75感謝你的觀看2019年8月23一個(gè)有趣的例子自然數(shù)1,2,3,…,n2+1的任何一種排列中作業(yè)教材[2.3]見課程主頁76感謝你的觀看2019年8月23作業(yè)教材[2.3]76感謝你的觀看2019年8月23關(guān)系及其運(yùn)算離散數(shù)學(xué)－集合論南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系77感謝你的觀看2019年8月23關(guān)系及其運(yùn)算離散數(shù)學(xué)－集合論1感謝你的觀看2019年8月23回顧集合的基本概念集合及其描述集合相等、子集關(guān)系冪集、笛卡爾乘積集合運(yùn)算交并補(bǔ)、廣義交、廣義并集合恒等式集合相關(guān)命題的證明方式78感謝你的觀看2019年8月23回顧集合的基本概念2感謝你的觀看2019年8月23提要關(guān)系的定義關(guān)系的表示關(guān)系的運(yùn)算0-1矩陣運(yùn)算關(guān)系的性質(zhì)79感謝你的觀看2019年8月23提要關(guān)系的定義3感謝你的觀看2019年8月23有序?qū)Γ∣rderedpair）(a,b)是集合{{a},{a,b}}的簡寫次序的體現(xiàn)(x,y)=(u,v)iffx=u且

y=v若{{x},{x,y}}={{u},{u,v}}，則{x}={u}或{x}={u,v},因此x=u。假設(shè)yv(1)若x=y,左邊={{x}},而vx,右邊{{x}};(2)若xy,則必有{x,y}={u,v},但y既非u,又非v,矛盾。80感謝你的觀看2019年8月23有序?qū)Γ∣rderedpair）(a,b)是集合{{a}笛卡爾乘積（CartesianProduct）對任意集合A,B

笛卡爾積AB={(a,b)|aA,bB}例：{1,2,3}{a,b}={(1,a),(3,a),(3,a),(1,b),(2,b),(3,b)}若A，B是有限集合，|AB|=|A||B|81感謝你的觀看2019年8月23笛卡爾乘積（CartesianProduct）對任意集合A例題A={1,2},

(A)×A=?|A|=m,|B|=n,|A×B|=?82感謝你的觀看2019年8月23例題A={1,2},(A)×A=?6感謝你的觀看201（二元）關(guān)系的定義若A,B是集合,從A到B的一個(gè)關(guān)系是AB的一個(gè)子集.集合,可以是空集集合的元素是有序?qū)﹃P(guān)系意味著什么？兩類對象之間建立起來的聯(lián)系！83感謝你的觀看2019年8月23（二元）關(guān)系的定義若A,B是集合,從A到B的一個(gè)關(guān)系是A從A到B的二元關(guān)系笛卡爾乘積的子集“從A到B的關(guān)系”R；RAB若A=B：稱為“集合A上的（二元）關(guān)系”例子常用的數(shù)學(xué)關(guān)系：不大于、整除、集合包含等網(wǎng)頁鏈接、文章引用、相互認(rèn)識84感謝你的觀看2019年8月23從A到B的二元關(guān)系笛卡爾乘積的子集8感謝你的觀看2019年8特殊的二元關(guān)系集合A上的空關(guān)系:空關(guān)系即空集全域關(guān)系

EA:EA={(x,y)

|x,yA}恒等關(guān)系

IA:IA

={(x,x)

|xA}85感謝你的觀看2019年8月23特殊的二元關(guān)系集合A上的空關(guān)系:空關(guān)系即空集9感謝你的函數(shù)是一種特殊的關(guān)系函數(shù)f:ABR={(x,f(x))

|xA}是一個(gè)從A到B的一個(gè)關(guān)系86感謝你的觀看2019年8月23函數(shù)是一種特殊的關(guān)系函數(shù)f:AB10感謝你的觀看2關(guān)系的表示假設(shè)A={a,b,c,d},B={α,β,γ}//假設(shè)為有限集合集合表示:R1={(a,β),(b,α),(c,α),(c,γ)}0-1矩陣有向圖abcdadcbAB87感謝你的觀看2019年8月23關(guān)系的表示假設(shè)A={a,b,c,d},B={α,β,γ}二元關(guān)系和有向圖關(guān)系RABA和B是集合有序?qū)?x,y)R若A=B,R中存在序列：(x1,x2),(x2,x3),…,(xn-1,xn)有向圖(VD

,ED)頂點(diǎn)集VD=AB有向邊集ED從x到y(tǒng)有一條邊圖D中存在從x1到xn

的長度為n-1的通路88感謝你的觀看2019年8月23二元關(guān)系和有向圖關(guān)系RAB有向圖(VD,ED)關(guān)系的運(yùn)算（1）關(guān)系是集合,所有的集合運(yùn)算對關(guān)系均適用例子:自然數(shù)集合上:“<”“=”等同于“”自然數(shù)集合上:“”“”等同于“=”自然數(shù)集合上:“<”“>”等同于89感謝你的觀看2019年8月23關(guān)系的運(yùn)算（1）關(guān)系是集合,所有的集合運(yùn)算對關(guān)系均適用13關(guān)系的運(yùn)算（2）與定義域和值域有關(guān)的運(yùn)算domR={x|y(x,y)R}ranR={y|x(x,y)R}fldR=domRranRR

A={(x,y)|xA

xRy}

RR[A]={y|x(xA

(x,y)R)}=ran(RA)ranR例：A={1,2,3,4,5},B={1,3,5,6},A上關(guān)系R：

R={(1,2),(1,4),(2,3),(3,5),(5,2)},

求RB、R[B]、R(1)和R(2)90感謝你的觀看2019年8月23關(guān)系的運(yùn)算（2）與定義域和值域有關(guān)的運(yùn)算14感謝你的觀看20關(guān)系的運(yùn)算（3）逆運(yùn)算R-1={(x,y)|(y,x)R}注意:如果R是從A到B的關(guān)系,則R-1是從B到A的。(R-1)-1=R例子：(R1R2)-1=R1-1R2-1

(x,y)(R1R2)-1

(y,x)(R1R2)(y,x)R1

或(y,x)R2

(x,y)R1-1

或(x,y)R2-191感謝你的觀看2019年8月23關(guān)系的運(yùn)算（3）逆運(yùn)算15感謝你的觀看2019年8月23關(guān)系的運(yùn)算（4）關(guān)系的復(fù)合（合成,Composition）設(shè)

R1AB,R2BC,R1與R2的復(fù)合（合成）,記為R2

?

R1,定義如下：R2

?

R1={(a,c)AC

|bB((a,b)R1(b,c)R2)

}92感謝你的觀看2019年8月23關(guān)系的運(yùn)算（4）關(guān)系的復(fù)合（合成,Composition）復(fù)合關(guān)系的圖示(a,c)R2

?

R1當(dāng)且僅當(dāng)aA,cC,且存在bB，使得(a,b)R1,(b,c)R2abcR1R293感謝你的觀看2019年8月23復(fù)合關(guān)系的圖示(a,c)R2?R1當(dāng)且僅當(dāng)a關(guān)系的復(fù)合運(yùn)算：舉例設(shè)A={a,b,c,d},R1,R2為A上的關(guān)系，其中： R1={(a,a),(a,b),(b,d)} R2={(a,d),(b,c),(b,d),(c,b)}則： R2

?

R1={(a,d),(a,c),(a,d)} R1

?

R2={(c,d)} R12={(a,a),(a,b),(a,d)}94感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算：舉例設(shè)A={a,b,c,d},R1,關(guān)系的復(fù)合運(yùn)算的性質(zhì)（1）結(jié)合律給定R1AB,R2BC,R3CD,則：

(R3

?

R2)?

R1=R3

?

(R2

?

R1)證明左右兩個(gè)集合相等.95感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算的性質(zhì)（1）結(jié)合律19感謝你的觀看2019年8關(guān)系的復(fù)合運(yùn)算的性質(zhì)（2）復(fù)合關(guān)系的逆關(guān)系給定R1AB,R2BC,則：

(R2

?

R1)-1=R1-1

?

R2-1同樣，證明左右兩個(gè)集合相等(x,y)(R2

?

R1)-1

(y,x)R2

?

R1

tB((y,t)R1

(t,x)R2)

tB((t,y)

R1-1(x,t)R2-1)

(x,y)R2-1

?

R1-196感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算的性質(zhì)（2）復(fù)合關(guān)系的逆關(guān)系20感謝你的觀看2關(guān)系的復(fù)合運(yùn)算的性質(zhì)（3）對集合并運(yùn)算滿足分配律給定FAB,GBC,HBC,則：

(GH)

?

F=(G?

F)(H?

F)對集合交運(yùn)算：

(GH)

?

F(G?

F)(H?

F)注意：等號不成立。A={a},B={s,t},C=;F={(a,s),(a,t)},G={(s,b)},H={(t,b)};GH=?,(G?

F)(H?

F)={(a,b)}

97感謝你的觀看2019年8月23關(guān)系的復(fù)合運(yùn)算的性質(zhì)（3）對集合并運(yùn)算滿足分配律21感謝你的0-1矩陣運(yùn)算令0-1矩陣M1=[aij],M2=[bij]:C=M1M2:cij=1iff.aij=bij=1C=M1M2:cij=1iff.aij=1或bij=1令rs矩陣M1=[aij]；st矩陣M2=[bij]:C=M1M2:cij=1iff.98感謝你的觀看2019年8月230-1矩陣運(yùn)算令0-1矩陣M1=[aij],M2=[bij關(guān)系運(yùn)算的矩陣法（1）命題99感謝你的觀看2019年8月23關(guān)系運(yùn)算的矩陣法（1）命題23感謝你的觀看2019年8月23證明：100感謝你的觀看2019年8月23證明：24感謝你的觀看2019年8月23關(guān)系的性質(zhì)：自反性reflexivity集合A上的關(guān)系

R

是:自反的reflexive：定義為：對所有的

aA,(a,a)R反自反的irreflexive：定義為：對所有的aA,(a,a)R注意區(qū)分”非”與”反”設(shè)A={1,2,3},RAA{(1,1),(1,3),(2,2),(2,1),(3,3)}是自反的{(1,2),(2,3),(3,1)}是反自反的{(1,2),(2,2),(2,3),(3,1)}既不是自反的，也不是反自反的101感謝你的觀看2019年8月23關(guān)系的性質(zhì)：自反性reflexivity集合A上的關(guān)系R自反性與恒等關(guān)系R

是A

上的自反關(guān)系

IAR,

這里IA是集合A上的恒等關(guān)系,即:IA={(a,a)|aA}直接根據(jù)定義證明：只需證明：對任意(a,b)，若(a,b)IA,則(a,b)R只需證明：對任意的a,若aA,則(a,a)R102感謝你的觀看2019年8月23自反性與恒等關(guān)系R是A上的自反關(guān)系IAR,自反關(guān)系的有向圖和0-1矩陣abcA={a,b,c}103感謝你的觀看2019年8月23自反關(guān)系的有向圖和0-1矩陣abcA={a,b,c}27感謝關(guān)系的性質(zhì)：對稱性

Symmetry集合A上的關(guān)系R是:對稱的symmetric：定義為：若(a,b)R,則(b,a)R反對稱的anti-~：定義為：若(a,b)R

且(b,a)R，則a=b設(shè)A={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)}是對稱的{(1,2),(2,3),(2,2),(3,1)}是反對稱的104感謝你的觀看2019年8月23關(guān)系的性質(zhì)：對稱性Symmetry集合A上的關(guān)系R是:2理解對稱性關(guān)系R滿足對稱性：對任意(a,b)，若

(a,b)R,則

(b,a)R注意：是對稱關(guān)系。反對稱并不是對稱的否定:(令：A={1,2,3},RAA){(1,1),(2,2)}既是對稱的，也是反對稱的是對稱關(guān)系，也是反對稱關(guān)系。105感謝你的觀看2019年8月23理解對稱性關(guān)系R滿足對稱性：對任意(a,b)，若(a,b)對稱性與逆關(guān)系R

是集合A上的對稱關(guān)系

R-1=R

證明一個(gè)集合等式R-1=R

若(a,b)R-1,則(b,a)R,由R的對稱性可知(a,b)R,因此：R-1R;同理可得：RR-1;只需證明：對任意的(a,b)若(a,b)R,則(b,a)R106感謝你的觀看2019年8月23對稱性與逆關(guān)系R是集合A上的對稱關(guān)系R-1=R30對稱關(guān)系的有向圖和0-1矩陣abcA={a,b,c}107感謝你的觀看2019年8月23對稱關(guān)系的有向圖和0-1矩陣abcA={a,b,c}31感謝關(guān)系的性質(zhì)：傳遞性

transitivity集合A上的關(guān)系R是傳遞的transitive:若(a,b)R,(b,c)R,則(a,c)R設(shè)A={1,2,3},RAA{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)}傳遞的{(1,2),(2,3),(3,1)}是非傳遞的{(1,3)}?

?108感謝你的觀看2019年8月23關(guān)系的性質(zhì)：傳遞性transitivity集合A上的關(guān)系傳遞性與關(guān)系的乘冪關(guān)系的復(fù)合(乘)運(yùn)算滿足結(jié)合律，可以用

Rn表示

R?R?…?R

(n是正整數(shù))命題：(a,b)Rn

當(dāng)且僅當(dāng)：存在t1,t2,…,tn-1A,滿足：(a,t1),(t1,t2),…,(tn-2,tn-1),(tn-1,b)R。對n>=1用數(shù)學(xué)歸納法：n=1,trivial.奠基n=2,直接由關(guān)系復(fù)合的定義可得；歸納基于：Rn=Rn-1?R集合A上的關(guān)系R是傳遞關(guān)系

R2R必要性：任取(a,b)R2,根據(jù)上述命題以及R的傳遞性可得(a,b)R充分性：若(a,b)R,(b,c)R,則(a,c)R2,由R2R可得：(a,c)R，則

R是傳遞關(guān)系109感謝你的觀看2019年8月23傳遞性與關(guān)系的乘冪關(guān)系的復(fù)合(乘)運(yùn)算滿足結(jié)合律，可以用傳遞關(guān)系的有向圖和0-1矩陣abcA={a,b,c}110感謝你的觀看2019年8月23傳遞關(guān)系的有向圖和0-1矩陣abcA={a,b,c}34感謝一些常用關(guān)系的性質(zhì)111感謝你的觀看2019年8月23一些常用關(guān)系的性質(zhì)35感謝你的觀看2019年8月23關(guān)系運(yùn)算與性質(zhì)的保持112感謝你的觀看2019年8月23關(guān)系運(yùn)算與性質(zhì)的保持36感謝你的觀看2019年8月23下列關(guān)系是否自反的、對稱的、反對稱的或可傳遞的？關(guān)系S為：r1≤|r2|(r1,r2∈R)時(shí)解：s是自反的，因?yàn)閷θ我獾膔∈R，有r≤|r|。s不是對稱的，如-1≤|3|，但3>|-1|。s不是反對稱的，如-3≤|2|，2≤|-3|，但-3≠2。s不是可傳遞的，100≤|-101|，-101≤|2|，但100>|2|習(xí)題舉例一113感謝你的觀看2019年8月23下列關(guān)系是否自反的、對稱的、反對稱的或可傳遞的？關(guān)系S為：r114感謝你的觀看2019年8月2338感謝你的觀看2019年8月23115感謝你的觀看2019年8月2339感謝你的觀看2019年8月23116感謝你的觀看2019年8月2340感謝你的觀看2019年8月23117感謝你的觀看2019年8月2341感謝你的觀看2019年8月23小結(jié)關(guān)系：笛卡爾積的子集關(guān)系的運(yùn)算集合運(yùn)算；復(fù)合運(yùn)算；逆0-1矩陣運(yùn)算關(guān)系的性質(zhì)reflexivity,ir-~;symmetry,anti-~;transitivity圖特征；矩陣特征118感謝你的觀看2019年8月23小結(jié)關(guān)系：笛卡爾積的子集42感謝你的觀看2019年8月23作業(yè)教材內(nèi)容：[Rosen]2.1.3、8.1節(jié)8.3節(jié)課后習(xí)題：見課程主頁119感謝你的觀看2019年8月23作業(yè)教材內(nèi)容：[Rosen]2.1.3、8.1節(jié)8.3函數(shù)及其運(yùn)算離散數(shù)學(xué)－集合論南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系120感謝你的觀看2019年8月23函數(shù)及其運(yùn)算離散數(shù)學(xué)－集合論44感謝你的觀看2019年8月2回顧關(guān)系：笛卡爾積的子集關(guān)系的運(yùn)算集合運(yùn)算；復(fù)合運(yùn)算；逆0-1矩陣運(yùn)算關(guān)系的性質(zhì)reflexivity,ir-~;symmetry,anti-~;transitivity圖特征；矩陣特征121感謝你的觀看2019年8月23回顧關(guān)系：笛卡爾積的子集45感謝你的觀看2019年8月23提要函數(shù)的定義子集的像單射與滿射反函數(shù)函數(shù)的復(fù)合函數(shù)加法與乘法122感謝你的觀看2019年8月23提要函數(shù)的定義46感謝你的觀看2019年8月23函數(shù)(function)的定義設(shè)A和B為非空集合，從集合A到B的函數(shù)

f是對元素的一種指派，對A的每個(gè)元素恰好指派B的一個(gè)元素。記作

f:AB。Welldefined(良定義)f:AB：函數(shù)的型構(gòu)f的定義域（domain）是A，f的伴域（codomain）是B如果

f為A中元素a指派的B中元素為b，就寫成f(a)=b。此時(shí)，稱b是a的像，而a是b的一個(gè)原像。A中元素的像構(gòu)成的集合稱為f的值域range（f的像image）。函數(shù)也稱為映射(mapping)或變換(transformation)123感謝你的觀看2019年8月23函數(shù)(function)的定義設(shè)A和B為非空集合，從函數(shù)的集合定義124感謝你的觀看2019年8月23函數(shù)的集合定義48感謝你的觀看2019年8月23函數(shù)的集合定義（續(xù)）125感謝你的觀看2019年8月23函數(shù)的集合定義（續(xù)）49感謝你的觀看2019年8月23函數(shù)舉例下取整函數(shù)x:R→Z函數(shù)

f的圖像:{(a,b)|aAf(a)=b}JavaProgramint

floor(floatreal){…}xyfloor:float

→int

126感謝你的觀看2019年8月23函數(shù)舉例下取整函數(shù)x:R→Z函數(shù)f的圖像:函數(shù)舉例某課程成績ProgramCourseGrade

grade(StudentNamesname，CourseNamecname){…}Function：Grade:StudentName×CourseName→CourseGrade

函數(shù)原型函數(shù)型構(gòu)(signature)127感謝你的觀看2019年8月23函數(shù)舉例某課程成績ProgramFunction：函數(shù)原型函函數(shù)舉例設(shè)A為非空集合，A上的

恒等函數(shù)A:AA定義為A(x)=x，xA設(shè)U為非空集合，對任意的AU,特征函數(shù)A:U{0,1}定義為：A(x)=1，xAA(x)=0，xU-A128感謝你的觀看2019年8月23函數(shù)舉例設(shè)A為非空集合，A上的恒等函數(shù)A:AA定義為5函數(shù)的集合129感謝你的觀看2019年8月23函數(shù)的集合53感謝你的觀看2019年8月23函數(shù)(function)的相等函數(shù)相等f=gifdom(f)=dom(g)codom(f)=codom(g)x(xdom(f)→f(x)=g(x))130感謝你的觀看2019年8月23函數(shù)(function)的相等函數(shù)相等f=gif54感謝函數(shù)的相等131感謝你的觀看2019年8月23函數(shù)的相等55感謝你的觀看2019年8月23子集在函數(shù)下的像設(shè)

f是從集合A到B的函數(shù)，S是A的一個(gè)子集。

S

在

f下的像，記為f(S)，定義如下：f(S)={t|sS(t=f(s))}備注：f(A)即為

f的值域。132感謝你的觀看2019年8月23子集在函數(shù)下的像設(shè)f是從集合A到B的函數(shù)，S是A的一個(gè)Bf(S):TASfS的像和逆像S的像:Tabcb的逆像T的逆像是什么？133感謝你的觀看2019年8月23Bf(S):TASfS的像和逆像S的像:Tabcb的逆像T的并集的像設(shè)函數(shù)

f:AB，且X，Y是A的子集，則

f(XY)=f(X)f(Y)證明:f(XY)

f(X)f(Y)

對任意的t，若tf(XY),則存在sXY,滿足f(s)=t;假設(shè)sX,則tf(X),假設(shè)sY,則tf(Y),tf(X)f(Y)f(X)f(Y)f(XY)

對任意的t，若tf(X)f(Y)

情況1：tf(X),則存在sXXY,滿足f(s)=t,tf(XY)

情況2：tf(Y),同樣可得tf(XY)

tf(XY)134感謝你的觀看2019年8月23并集的像設(shè)函數(shù)f:AB，且X，Y是A的子集，則

f交集的像設(shè)函數(shù)

f:AB，且X，Y是A的子集，則f(XY)

f(X)f(Y)ABXYa1a2cf在f(X)f(Y)中，但不在f(XY)中135感謝你的觀看2019年8月23交集的像設(shè)函數(shù)f:AB，且X，Y是A的子集，則ABX函數(shù)性質(zhì):AB是單射（一對一的）injection,injectivefunction,one-to-onefunctionx1,x2A,若x1x2，則(x1)(x2)//等價(jià)的說法：x1,x2A,若(x1)=(x2)，則x1=x2//另一種等價(jià)的說法？:AB是滿射（映上