第四章二元关系和函数

第4章二元关系和函数4.2关系的运算4.1集合的笛卡儿积与二元关系4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数4.1集合的笛卡儿积与二元关系一.集合的笛卡儿积1.定义:设a,b为集合,则a和b的笛卡儿积为

a×b={<x,y>|x∈a∧y∈b}

其中<x,y>叫做有序对或序偶;例如:a={a,b},b={0,1,2},则

a×b={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}b×a={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}说明:①如果a中有m个元素,b中有n个元素,则a×b和b×a中都有m*n个元素;②若<x,y>∈a×b,则有x∈a且y∈b

若<x,y>a×b,则有xa或yb2.性质:①φ×b=a×φ=φ②若a≠b且a≠φ,b≠φ,则a×b≠b×a③若a≠φ,b≠φ,c≠φ,则(a×b)×c≠a×(b×c)④a×(b∪c)=(a×b)∪(a×c)(b∪c)×a=(b×a)∪(c×a)a×(b∩c)=(a×b)∩(a×c)(b∩c)×a=(b×a)∩(c×a)证明:<x,y>∈a×(b∪c)⇔x∈a∧y∈b∪c⇔x∈a∧(y∈b∨y∈c)⇔(x∈a∧y∈b)∨(x∈a∧y∈c)⇔<x,y>∈a×b∨<x,y>∈a×c⇔<x,y>∈(a×b)∪(a×c)所以,a×(b∪c)=(a×b)∪(a×c)例4.1设a={1,2},求p(a)×a解:p(a)×a={φ,{1},{2},{1,2}}×{1,2}={<φ,1>,<φ,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>};例4.2设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)解:(1)成立:<x,y>∈(a∩b)×(c∩d)⇔x∈a∩b∧y∈c∩d⇔(x∈a∧x∈b)∧(y∈c∧y∈d)⇔(x∈a∧y∈c)∧(x∈b∧y∈d)

⇔<x,y>∈a×c∧<x,y>∈b×d⇔<x,y>∈(a×c)∩(b×d)(2)不成立:若a=d=φ,b=c={1}

则(a∪b)×(c∪d)=b×c={<1,1>}

而(a×c)∪(b×d)=(φ×c)∪(φ×d)=φ∪φ=φ(3)不成立:若a=b={1},c={2},d=φ

则(a-b)×(c-d)=φ×c=φ

而(a×c)-(b×d)={<1,2>}-φ={<1,2>}(4)不成立:若a=b={1},c={2},d=φ

则(a⊕b)×(c⊕d)=φ×{2}=φ

而(a×c)⊕(b×d)={<1,2>}⊕φ={<1,2>}例4.3设a,b,c,d为任意集合,判断以下命题的真假.(1)若a⊆c且b⊆d,则a×b⊆c×d(2)若a×b⊆c×d,则a⊆c且b⊆d解:(1)为真:∀<x,y>∈a×b⇒x∈a∧y∈b⇒x∈c∧y∈d

⇒<x,y>∈c×d(2)为假:若a=c=d=φ,b={1};

则a×b⊆c×d但b

d

3.n个(n≥2)集合的笛卡儿积

a1×a2×…×an={<x1,x2,…,xn>|x1∈a1,x2∈a2,…,xn∈an}

当a1=a2=…=an=a时,an={<x1,x2,…,xn>|xi∈a,i=1,2,…n}二.二元关系1.定义:若r={<x,y>|x,y∈a};

则r为a的二元关系,记作xry,否则xry

注)若|a|=n,则|a×a|=n2,|p(a×a)|=

所以a上有不同的二元关系,其中有3种特殊关系:

空关系,全域关系ea和恒等关系ia.

全域关系ea={＜x,y>|x∈a∧y∈a}=a×a

恒等关系ia={＜x,x>|x∈a}例如：Ａ＝｛０，１，２｝则

ea={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>}ia={<0,0>,<1,1>,<2,2>}小于等于关系:la={<x,y>|x,y∈a∧x≤y}整除关系:db={<x,y>|x,y∈b

∧x|y}例如:a={4,0.5,-1},b={1,2,3,6}则la={<-1,-1>,<-1,0.5>,<-1,4>,<0.5,0.5>,<0.5,4>,<4,4>}db={<1,1>,<1,2>,<1,3>,<1,6>,<2,2>,<2,6>,<3,3>,<3,6>,<6,6>}例:4.4设a={a,b},r是p(a)上的包含关系

r={<x,y>|x,y∈p(a)∧x⊆y}

则有p(a)={φ,{a},{b},a}r={<φ,φ>,<φ,{a}>,<φ,{b}>,<φ,a>,<{a},{a}>,<{a},a>,<{b},{b}>,<{b},a>,<a,a>}2.二元关系的矩阵表示法和图表示法设a={1,2,3,4},r={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}关系矩阵关系图4.2关系的运算一.关系的定义域.值域和域定义域：domr={x|∃y(<x,y>∈r)}值域：ranr={y|∃x(<x,y>∈r)}域：fldr=domr∪ranr例4.5下列关系都是整数集z上的关系,分别求他们的定义域和值域(1)r1={<x,y>|x,y∈z∧x≤y}(2)r2={<x,y>|x,y∈z∧x2+y2=1}(3)r3={<x,y>|x,y∈z∧y=2x}(4)r4={<x,y>|x,y∈z∧|x|=|y|=3}解:(1)domr1=ranr1=z(2)r2={<0,1>,<0,-1>,<1,0>,<-1,0>}

domr2=ranr2={0,-1,1}(3)domr3=z,ranr3={2x|x∈z}(4)domr4=ranr4={-3,3}图示二.关系运算f的逆:f-1={<y,x>|xfy}f与g的合成:fog={<x,y>|∃z(xgz

∧zfy)}f在a上的限制:f↑a={<x,y>|xfy

∧x∈a}a在f下的像:f[a]=ran(f↑a)例4.6设f,g是n上的关系,其定义为

f={<x,y>|x,y∈n∧y=x2}g={<x,y>|x,y∈n∧y=x+1}

求g-1,fog,gof,f↑{1,2},f[{1,2}]

解:g-1={<x,y>|x,y∈n∧y=x-1}(org-1={<y,x>|x,y∈n∧x=y-1})g-1={<1,0>,<2,1>,<3,2>,…,<x,x-1>,…}

fog={<x,y>|x,y∈n∧y=(x+1)2}

gof={<x,y>|x,y∈n∧y=x2+1}f↑{1,2}={<1,1>,<2,4>}f[{1,2}]=ran(f↑{1,2})={1,4}例4.7设f={<a,{a}>,<{a},{a,{a}}>}

求fof,f↑{a},f[{a}]

解:fof={<a,{a,{a}}>}

f↾{a}={<a,{a}>}f[{a}]=ran(f↑{a})={{a}}

三.关系运算的性质定理1:设f,g,h是任意的关系,则有

(1)(f-1)-1=f(2)domf-1=ranf,ranf-1=domf(3)(fog)oh=fo(goh)(4)(fog)-1=g-1of-1证明:(4)<x,y>∈(fog)-1⇔<y,x>∈fog

⇔∃z(<y,z>∈g∧<z,x>∈f)

⇔∃z(<z,y>∈g-1

∧<x,z>∈f-1)

⇔∃z(<x,z>∈f-1

∧<z,y>∈g-1)

⇔<x,y>∈g-1of-1

所以(fog)-1=g-1of-1定理2:设f,g,h为任意的关系,则有

(1)fo(g∪h)=fog∪foh(2)fo(g∩h)⊆fog∩foh(3)(g∪h)of=gof∪hof

(4)(g∩h)of⊆gof∩hof证明:(1)<x,y>∈fo(g∪h)

⇔∃z(<x,z>∈g∪h∧<z,y>∈f)

⇔∃z((<x,z>∈g∨<x,z>∈h)∧<z,y>∈f)

⇔∃z((<x,z>∈g∧<z,y>∈f)∨(<x,z>∈h∧<z,y>∈f))⇔∃z(<x,z>∈g∧<z,y>∈f)∨∃z(<x,z>∈h∧<z,y>∈f)⇔<x,y>∈fog

∨<x,y>∈foh⇔<x,y>∈fog∪foh所以fo(g∪h)=fog∪foh(2)<x,y>∈fo(g∩h)⇒∃z(<x,z>∈g∩h∧<z,y>∈f)

⇒∃z(<x,z>∈g

∧<z,y>∈f)⇒<x,y>∈fog所以fo(g∩h)⊆fog

同理可证fo(g∩h)⊆foh故fo(g∩h)⊆fog∩foh四.关系运算的幂设r为a上的关系,n为自然数,则r的n次幂规定如下:(1)r0={<x,x>|x∈a}(r0=ia是a上的恒等关系)(2)rn=rn-1or,n≥1例4.8设a={a,b,c,d},r={<a,b>,<b,a>,<b,c>,<c,d>}求r0,r1,r2,r3,r4和r5解:关系运算:r0={<a,a>,<b,b>,<c,c>,<d,d>}r1={<a,b>,<b,a>,<b,c>,<c,d>}r2=r1or1={<a,a>,<a,c>,<b,b>,<b,d>}r3=r2or1={<a,b>,<a,d>,<b,a>,<b,c>}

r4=r3or1={<a,a>,<a,c>,<b,b>,<b,d>}

r5=r4or1={<a,b>,<a,d>,<b,a>,<b,c>}关系图法={<a,a>,<b,b>,<c,c>,<d,d>}r1={<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}={<a,b>,<a,d>,<b,a>,<b,c>}关系矩阵r0={<a,a>,<b,b>,<c,c>,<d,d>}r1={<a,b>,<b,a>,<b,c>,<c,d>}r2=r1or1={<a,a>,<a,c>,<b,b>,<b,d>}r3=r2or1={<a,b>,<a,d>,<b,a>,<b,c>}

定理3:设r为a上的关系,m,n是自然数,则下面的等式成立:(1)rm◌rn=rm+n(2)(rm)n=rmn4.3关系的性质一.关系的定义和性质:设r是a上的关系,则有例如:设a={1,2,3}令

r1={<1,1>,<2,2>,<3,3>,<1,2>}r2={<2,3>,<3,2>}r3={<1,1>,<2,2>}r4={<1,2>,<2,1>,<3,3>}r5={<1,2>,<1,3>}r6={<1,1>}r7={<1,2>,<2,1>,<1,3>}

则r1是自反的,反对称的;r2是反自反的,对称的;r3既是对称的,又是反对称的;r4是对称的;r5是反自反的,反对称的;r6既是对称的，又是反对称的;r7是反自反的.例4.9试判断图中的关系性质解:(1)是对称的

(2)是反自反的,反对称的;(3)是自反的,反对称的;二.关系运算的性质设r1，r2为a上的对称关系,可证r1∩r2也是a上的对称关系.证明:<x,y>∈r1∩r2⇔<x,y>∈r1∧<x,y>∈r2

⇔<y,x>∈r1∧<y,x>∈r2⇔<y,x>∈r1∩r2设r1,r2为a上反对称关系,但r1∪r2不一定是a上的反对称关系例如:a={x1,x2},r1={<x1,x2>},r2={<x2,x1>};r1∪r2={<x1,x2>,<x2,x1>}4.4关系的闭包定义:设r是非空集合a上的关系,r的自反闭包(对称闭包或传递闭包)是a上的r’,且r’满足以下条件:(1)r’是自反的(对称的或传递的)(2)r⊆r’(3)对a上的任何包含r的自反关系(对称或传递关系)r”

都有r’⊆r”一般:将r的自反闭包,记作r(r);对称闭包,记作s(r);传递闭包,记作t(r);定理:设r为非空集合a上的关系,则有

(1)r(r)=r∪r0(2)s(r)=r∪r-1(3)t(r)=r∪r2∪r3∪…例4.10设a={a,b,c,d},r={<a,b>,<b,a>,<b,c>,<c,d>}

求r和r(r),s(r),t(r)关系运算,关系图和关系矩阵解:关系运算:r(r)=r∪r0={<a,b>,<b,a>,<b,c>,<c,d>}

∪(<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}s(r)=r∪r-1={<a,b>,<b,a>,<b,c>,<c,d>}∪{<c,b>,<d,c>}r2=ror={<a,a>,<a,c>,<b,b>,<b,d>}r3=r2or={<a,b>,<a,d>,<b,a>,<b,c>}r4=r3or={<a,a>,<a,c>,<b,b>,<b,d>}r5=r3;t(r)=r∪r2∪r3={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<a,c>,<b,b>,<b,d>,<a,d>}关系图关系矩阵mr=m+e;ms=m+m’;mt=m+m2+m3+…4.5等价关系和偏序关系一.等价关系1.等价关系定义:设r为非空集合a上的关系,如果r是自反的,对称的和传递的,则r为a上的等价关系.对∀x,y∈a,若<x,y>∈r,则记作x～y例4.11a={1,2,…,8},r={<x,y>|x,y∈a∧x≡y(mod3)}

其中x≡y(mod3)

是x-y可以被3整除.解:r1={<1,1>,<4,4>,<7,7>,<1,4>,<4,1>,<1,7>,<7,1>,<4,7>,<7,4>}r2={<2,2>,<5,5>,<8,8>,<2,5>,<5,2>,<2,8>,<8,2>,<5,8>,<8,5>}

r3={<3,3>,<6,6>,<3,6>,<6,3>}

r=r1∪r2∪r32.等价类定义:设r是非空集合a上的等价关系,对∀x∈a,令[x]r={y|y∈a∧

xry}则称[x]r为x关于r的等价类,简称为x的等价类,简记为[x].例如:例4.11有[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}定理(等价类的性质):设r是非空集合a上的等价关系,

对∀x,y∈a,则有(1)[x]≠φ,且[x]⊆a(2)若xry,则[x]=[y](3)若xry,则[x]∩[y]=φ(4)∪[x]=a例如:例4.11{1,4,7}∪{2,5,8}∪{3,6}={1,2,…,8}3.商集定义:设r为非空集合a上的等价关系,以r的不交的等价类为元素的集合叫做a在r下的商集,记作a/r.即a/r={[x]r|x∈a}如:例4.11中,a在r下的商集为a/r={{1,4,7},{2,5,8},{3,6}}4.划分定义:设a是非空集合,如果存在一个a的子集族π(π⊆p(a))

满足以下条件(1)φπ(2)π中任意两个元素不交,(3)π中所有元素的并集等于a,

则称π为a的一个划分,且称π中的元素为划分块.例4.14考虑集合a={a,b,c,d}的下列子集族

(1){{a},{b,c},{d}}(2){{a,b,c,d}}(3){{a,b},{c},{a,d}}(4){φ,{a,b},{c,d}}(5){{a},{b,c}}则有(1)(2)都是a的划分,(3)(4)(5)不是a的划分.注)所有等价类的集合,即商集a/r,就是a的一个划分,称为由r所诱导的划分.例4.15设a={1,2,3},求出a上所有的等价关系解:a的所有划分

π1={{1,2,3}}π2={{1},{2,3}}π3={{2},{1,3}}π4={{3},{1,2}}π5={{1},{2},{3}}对应划分πi的等价关系为ri

(i=1,2,3,4,5);ia={<1,1>,<2,2>,<3,3>}r1=ia∪{<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}r2=ia∪{<2,3>,<3,2>}r3=ia∪{<1,3>,<3,1>}r4=ia∪{<1,2>,<2,1>}r5=ia二.偏序关系1.偏序关系:设r为非空集合a上的关系,

如果r是自反的,反对称的和传递的,

则称r为a上的偏序关系,简称偏序,记作≤例如:任何集合a上的恒等关系,集合的幂集p(a)上的包含关系,

实数集上的小于等于关系,正整数集上的整除关系,

都是偏序关系.例:集合a={1,2,3}上的大于等于关系,是a的偏序关系即≤={<3,3>,<3,2>,<3,1>,<2,2>,<2,1>,<1,1>}所以有3≤2.2≤2.3≤1表示<3,2>,<2,2>,<3,1>属于偏序≤;2.偏序集一个集合a与a上的偏序关系r一起叫做偏序集;记作<a,r>.例如:<z,r≤>其中r≤表示通常数小于等于关系,<p(a),r⊆>其中r⊆表示集合的包含关系都是偏序集.3.可比与盖住设<a,≤>为偏序集,∀x,y∈a,如果x≤y或y≤x成立,则称x与y是可比的.如果x＜y(即x≤y∧x≠y),且不存在z∈a,使x<z<y,则称y盖住x.例如:<a,≤>是偏序集,其中a={1,2,3,4,5},≤是整除关系,有1与1,2,3,4,5是可比的,2,3,5盖住1,4盖住2.4不能盖住1。4.全序关系和全序集设<a,≤>为偏序集,若∀x,y∈a,x和y都可比,则称≤为a上的全序关系,且称<a,≤>为全序集.例如:a={1,2,3,4,5}上的小于等于关系是全序关系,

而整除关系不是全序关系.5.哈斯图例4.16画出<{1,2,…,12},r整除>和<p({a,b,c},r⊆>哈斯图.例4.17设偏序集<a,≤>的哈斯图如图所示,

求出集合a的偏序≤.解:a={a,b,c,d,e,f,g,h}≤={<a,c>,<a,d>,<a,e>,<b,c>,<b,d>,<b,e>,<c,e>,<d,e>,<f,g>}∪ia6.最小元与最大元,极小元与极大元定义:设<a,≤>为偏序集,b⊆a(1)若∃y∈b,使∀x(x∈b->y≤x)成立,则称y是b的最小元.(2)若∃y∈b,使∀x(x∈b->x≤y)成立,则称y是b的最大元.(3)若∃y∈b,￢∃x(x∈b∧x<y)成立,则称y是b的极小元.(4)若∃y∈b,￢∃x(x∈b∧y<x)成立,则称y是b的极大元.例4.16(1)有最小元1;无最大元,有极大元7,8,9,10,11,12;(2)有最小元φ;有最大元{a,b,c}例4.17无最小元和最大元,但有极小元a,b,f,h和极大元e,g,h.7.上确界和下确界定义:设<a,≤>为偏序集,b⊆a(1)若∃y∈a,使∀x(x∈b->x≤y)成立,则称y为b的上界.(2)若∃y∈a,使∀x(x∈b->y≤x)成立,则称y为b的下界.(3)令c={y|y为b的上界},则c的最小元为b的最小上界或上确界.(4)令d={y|y为b的下界},则d的最大元为b的最大下界或下确界.例4.16在整除关系的偏序集里,取b={2,3,6},那么b的上界为6和12,上确界为6,b的下界是1,下确界是1;取b=a,则b的上确界为{a,b,c},下确界为φ.例4.17取b={c,d,e},则b的上界和上确界为e,b的下界为a,b,但没有下确界.4.6函数的定义和性质一.函数(映射)定义1:设f为二元关系,若∀x∈domf,

∃唯一的y∈ranf,

使xfy成立,则称f为函数,记作f(x)=y.例如f1={<x1,y1>,<x2,y1>,<x3,y2>}是函数.f2={<x1,y1>,<x1,y2>,<x2,y1>,<x3,y2>}不是函数.定义2:设a,b是集合,如果函数f满足以下条件

(1)domf=a(2)ranf⊆b

则称f是从a到b的函数,记作f:a->b定义3:设a,b为集合,所有从a到b的函数构成集合ba

有ba={f|f:a->b};例如:a={0,1,2},b={a,b}f1={<0,a>,<1,a>,<2,a>}f2={<0,a>,<1,a>,<2,b>}f3={<0,a>,<1,b>,<2,a>}f4={<0,b>,<1,a>,<2,a>}f5={<0,b>,<1,b>,<2,b>}f6={<0,b>,<1,b>,<2,a>}f7={<0,b>,<1,a>,<2,b>}f8={<0,a>,<1,b>,<2,b>}所以,ba={f1,f2,…,f8}注)若|a|=m,|b|=n,则ba=nm定义4:设f:a->b,a’⊆a,则a’在f下的象是

f(a’)={f(x)|x∈a’}=f[a’]

当a’=a时,称f(a’)=f(a)=ranf是函数的象.例如:f:r->r,如f(x)=exf{-1,0,1}={e-1,e0,e1}={e-1,1,e},即f(r)=r+二.双射定义:设函数f:a->b(1)若ranf=b,则称f是满射,(2)若∀x1,x2∈a且x1≠x2,都有f(x1)≠f(x2),则称f是单射.(3)若f既是满射,又是单射,则称f是双射.例如:函数f:{1,2}->{0},f(1)=f(2)=0是满射.

函数f:n->n,f(x)=2x是单射.

函数f:z->z,f(x)=x+1是双射.例4.18分别确定以下各题中的f是否为从a到b的函数,并对其中的f:a->b指出它是否为单射,满射或双射,说明理由.设a={1,2,3,4,5},b={6,7,8,9,10}(1)f={<1,8>,<3,9>,<4,10>,<2,6>,<5,9>}是函数,不是单射,也不是满射.(2)f={<1,8>,<3,10>,<2,6>,<4,9>}不是函数.(3)f={<1,7>,<2,6>,<4,5>,<1,9>,<5,10>}不是函数.设a,b为实数集(4)f(x)=x2-x是函数由于x2-x=x(x-1)=0,可知x=0和x=1都有f(0)=f(1)=0

所以f不是单射;

由于,当x=1/2,f(x)有最小值-1/4,即ranf=[-1/4,+∞)

所以,f不是满射.(f’(x)=2x-1,f”(x)=2)(5)f(x)=x3是函数,

∀x1,x2∈a且

x1≠x2,则有x13≠x23,所以f是单射;

∀y∈b,都有x3=y,即,所以f是满射,

故f是双射.

不是函数(x<0不成立)(7)不是函数(x=0不成立)设a,b为正整数集,(8)f(x)=x+1是函数,

∀x1,x2∈a且x1≠x2,都有x1+1≠x2+1,所以f是单射;

但由于1∉ranf⊂b(即对y=1,不存在x=0,使f(0)=1),

所以,f不是满射.1x=1(9)f(x)=是函数,x-1x>1

由于f(1)=f(2)=1,所以f不是单射;

∀y∈b,若y=1,则有x=1,其它有y=x-1,即x=y+1,

所以,f是满射.设a,b为正实数集,

是函数,

由于知(x1x2-1)(x1-x2)=0

若x1≠x2,可知x1x2-1=0,故取x1=1/4,x2=4,有f(x1)=f(x2)

所以,f不是单射,

由于,当x=1时,f(x)有最大值1/2;(如取y=1,找不到x>0,

使成立),即ranf⊂b,故f不是满射.例4.19判断以下函数的单射,满射和双射性

(1)f:r×r->r×r,r为实数集,f(<x,y>)=<x+y,x-y>(2)f:n×n->n,n为自然数集(0∈n),f(<x,y>)=|x2-y2|解:(1)∀<x,y>,<u,v>∈r×r,若<x,y>≠<u,v>

只要证明<x+y,x-y>≠<u+v,u-v>,就说明f是单射,

用反证法:假设<x+y,x-y>=<u+v,u-v>

则有x+y=u+v,x-y=u-v,得x=u,y=v,即<x,y>=<u,v