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

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

y=v若{{x},{x,y}}={{u},{u,v}}，則{x}={u}或{x}={u,v},因此x=u。假設(shè)y

v(1)若x=y,左邊={{x}},而vx,右邊{{x}};(2)若x

y,則必有{x,y}={u,v},但y既非u,又非v,矛盾。4笛卡爾乘積（CartesianProduct）對(duì)任意集合A,B

笛卡爾積A

B={(a,b)|a

A,b

B}例：{1,2,3}{a,b}={(1,a),(3,a),(3,a),(1,b),(2,b),(3,b)}若A，B是有限集合，|A

B|=|A||B|5例題A={1,2},

(A)×A=?|A|=m,|B|=n,|A×B|=?6（二元）關(guān)系的定義若A,B是集合,從A到B的一個(gè)關(guān)系是A

B的一個(gè)子集.集合,可以是空集集合的元素是有序?qū)﹃P(guān)系意味著什么？?jī)深悓?duì)象之間建立起來的聯(lián)系！7從A到B的二元關(guān)系笛卡爾乘積的子集“從A到B的關(guān)系”R；R

A

B若A=B：稱為“集合A上的（二元）關(guān)系”例子常用的數(shù)學(xué)關(guān)系：不大于、整除、集合包含等網(wǎng)頁鏈接、文章引用、相互認(rèn)識(shí)8特殊的二元關(guān)系集合A上的空關(guān)系

:空關(guān)系即空集全域關(guān)系

EA:EA={(x,y)

|x,y

A}恒等關(guān)系

IA:IA

={(x,x)

|x

A}9函數(shù)是一種特殊的關(guān)系函數(shù)f:A

BR={(x,f(x))

|x

A}是一個(gè)從A到B的一個(gè)關(guān)系10關(guān)系的表示假設(shè)A={a,b,c,d},B={α,β,γ}//假設(shè)為有限集合集合表示:R1={(a,β),(b,α),(c,α),(c,γ)}0-1矩陣有向圖abcd

adcb

AB11二元關(guān)系和有向圖關(guān)系R

A

BA和B是集合有序?qū)?x,y)R若A=B,R中存在序列：(x1,x2),(x2,x3),…,(xn-1,xn)有向圖(VD

,ED)頂點(diǎn)集VD=A

B有向邊集ED從x到y(tǒng)有一條邊圖D中存在從x1到xn

的長(zhǎng)度為n-1的通路12關(guān)系的運(yùn)算（1）關(guān)系是集合,所有的集合運(yùn)算對(duì)關(guān)系均適用例子:自然數(shù)集合上:“<”“=”等同于“”自然數(shù)集合上:“”“”等同于“=”自然數(shù)集合上:“<”“>”等同于

13關(guān)系的運(yùn)算（2）與定義域和值域有關(guān)的運(yùn)算domR={x|

y(x,y)

R}ranR={y|

x(x,y)

R}fldR=domR

ranRR

A={(x,y)|x

A

xRy}

RR[A]={y|

x(x

A

(x,y)

R)}=ran(R

A)

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)},

求R

B、R[B]、R(1)和R(2)14關(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例子：(R1

R2)-1=R1-1

R2-1

(x,y)

(R1

R2)-1

(y,x)

(R1

R2)

(y,x)

R1

或(y,x)

R2

(x,y)

R1-1

或(x,y)

R2-115關(guān)系的運(yùn)算（4）關(guān)系的復(fù)合（合成,Composition）設(shè)

R1

A

B,R2

B

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

?

R1,定義如下：R2

?

R1={(a,c)

A

C

|

b

B((a,b)

R1

(b,c)

R2)

}16復(fù)合關(guān)系的圖示(a,c)

R2

?

R1當(dāng)且僅當(dāng)a

A,c

C,且存在b

B，使得(a,b)

R1,(b,c)

R2abcR1R217關(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關(guān)系的復(fù)合運(yùn)算的性質(zhì)（1）結(jié)合律給定R1

A

B,R2

B

C,R3

C

D,則：

(R3

?

R2)?

R1=R3

?

(R2

?

R1)證明左右兩個(gè)集合相等.19關(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關(guān)系的復(fù)合運(yùn)算的性質(zhì)（3）對(duì)集合并運(yùn)算滿足分配律給定FAB,GBC,HBC,則：

(G

H)

?

F=(G?

F)

(H?

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

(G

H)

?

F

(G?

F)

(H?

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

H=?,(G?

F)

(H?

F)={(a,b)}

210-1矩陣運(yùn)算令0-1矩陣M1=[aij],M2=[bij]:C=M1

M2:cij=1iff.aij=bij=1C=M1

M2:cij=1iff.aij=1或bij=1令r

s矩陣M1=[aij]；s

t矩陣M2=[bij]:C=M1M2:cij=1iff.22關(guān)系運(yùn)算的矩陣法（1）命題23證明：24關(guān)系的性質(zhì)：自反性reflexivity集合A上的關(guān)系

R

是:自反的reflexive：定義為：對(duì)所有的

a

A,(a,a)R反自反的irreflexive：定義為：對(duì)所有的a

A,(a,a)R注意區(qū)分”非”與”反”設(shè)A={1,2,3},R

A

A{(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自反性與恒等關(guān)系R

是A

上的自反關(guān)系

IA

R,

這里IA是集合A上的恒等關(guān)系,即:IA={(a,a)|a

A}直接根據(jù)定義證明：只需證明：對(duì)任意(a,b)，若(a,b)

IA,則(a,b)

R只需證明：對(duì)任意的a,若a

A,則(a,a)

R26自反關(guān)系的有向圖和0-1矩陣abcA={a,b,c}27關(guān)系的性質(zhì)：對(duì)稱性

Symmetry集合A上的關(guān)系R是:對(duì)稱的symmetric：定義為：若(a,b)

R,則(b,a)R反對(duì)稱的anti-~：定義為：若(a,b)

R

且(b,a)R，則a=b設(shè)A={1,2,3},R

A

A{(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)}是對(duì)稱的{(1,2),(2,3),(2,2),(3,1)}是反對(duì)稱的28理解對(duì)稱性關(guān)系R滿足對(duì)稱性：對(duì)任意(a,b)，若

(a,b)

R,則

(b,a)R注意：

是對(duì)稱關(guān)系。反對(duì)稱并不是對(duì)稱的否定:(令：A={1,2,3},R

A

A){(1,1),(2,2)}既是對(duì)稱的，也是反對(duì)稱的

是對(duì)稱關(guān)系，也是反對(duì)稱關(guān)系。29對(duì)稱性與逆關(guān)系R

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

R-1=R

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

若(a,b)R-1,則(b,a)R,由R的對(duì)稱性可知(a,b)R,因此：R-1

R;同理可得：R

R-1;只需證明：對(duì)任意的(a,b)若(a,b)

R,則(b,a)

R30對(duì)稱關(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},R

A

A{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)}傳遞的{(1,2),(2,3),(3,1)}是非傳遞的{(1,3)}?

?32傳遞性與關(guān)系的乘冪關(guān)系的復(fù)合(乘)運(yùn)算滿足結(jié)合律，可以用

Rn表示

R?R?…?R

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

當(dāng)且僅當(dāng)：存在t1,t2,…,tn-1

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

R2

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

R可得：(a,c)R，則

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

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

f:A

B。Welldefined(良定義)f:A

B：函數(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函數(shù)的集合定義48函數(shù)的集合定義（續(xù)）49函數(shù)舉例下取整函數(shù)

x

:R→Z函數(shù)

f的圖像:{(a,b)|a

A

f(a)=b}JavaProgramint

floor(floatreal){…}xyfloor:float

→int

50函數(shù)舉例某課程成績(jī)ProgramCourseGrade

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

函數(shù)原型函數(shù)型構(gòu)(signature)51函數(shù)舉例設(shè)A為非空集合，A上的

恒等函數(shù)

A:A

A定義為

A(x)=x，x

A設(shè)U為非空集合，對(duì)任意的A

U,特征函數(shù)

A:U

{0,1}定義為：

A(x)=1，x

A

A(x)=0，x

U-A52函數(shù)的集合53函數(shù)(function)的相等函數(shù)相等f=gifdom(f)=dom(g)codom(f)=codom(g)

x(xdom(f)→f(x)=g(x))54函數(shù)的相等55子集在函數(shù)下的像設(shè)

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

S

在

f下的像，記為f(S)，定義如下：f(S)={t|

s

S(t=f(s))}備注：f(A)即為

f的值域。56Bf(S):TASfS的像和逆像S的像:Tabcb的逆像T的逆像是什么？57并集的像設(shè)函數(shù)

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

f(XY)=f(X)

f(Y)證明:f(XY)

f(X)

f(Y)

對(duì)任意的t，若t

f(XY),則存在s

XY,滿足f(s)=t;假設(shè)s

X,則t

f(X),假設(shè)s

Y,則t

f(Y),tf(X)

f(Y)f(X)

f(Y)

f(XY)

對(duì)任意的t，若t

f(X)

f(Y)

情況1：t

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

情況2：t

f(Y),同樣可得tf(XY)

tf(XY)58交集的像設(shè)函數(shù)

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

f(X)

f(Y)ABXYa1a2cf

在f(X)

f(Y)中，但不在f(XY)中59函數(shù)性質(zhì)

:A

B是單射（一對(duì)一的）injection,injectivefunction,one-to-onefunction

x1,x2

A,若x1

x2，則

(x1)

(x2)//等價(jià)的說法：

x1,x2

A,若

(x1)=

(x2)，則x1=x2//另一種等價(jià)的說法？

:A

B是滿射（映上的）surjection,surjectivefunction,ontofunction

y

B,

x

A,使得

(x)=y//等價(jià)的說法：f(A)=B

:A

B是雙射（一一對(duì)應(yīng)）bijection,bijectivefunction,one-to-onecorrespondence滿射+單射60函數(shù)性質(zhì)的證明判斷

:R

R

R

R,

(<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函數(shù)性質(zhì)的證明設(shè)A有限集合，f是從A到A的函數(shù)。f是單射當(dāng)且僅當(dāng)

f是滿射。62反函數(shù)設(shè)f是從A到B的一一對(duì)應(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ù)嗎？例子

:R

R

R

R,

(<x,y>)=<x+y,x-y>f-1:R

R

R

R,

-1(<x,y>)=<?,?>63函數(shù)的復(fù)合設(shè)g是從A到B的函數(shù)，f是從B到C的函數(shù)，f和g的復(fù)合用f

g表示，定義為：(f

g)(x)=f(g(x))，x

AaAg(a)BCf(g(a))gff

g64復(fù)合運(yùn)算的性質(zhì)函數(shù)的復(fù)合滿足結(jié)合律(f

g)

h=f

(g

h)滿射的復(fù)合是滿射