二元關(guān)系與函數(shù)第一頁，共三十三頁，編輯于2023年，星期六14.1集合的笛卡兒積和二元關(guān)系

有序?qū)Φ芽▋悍e及其性質(zhì)二元關(guān)系的定義二元關(guān)系的表示第二頁，共三十三頁，編輯于2023年，星期六2有序?qū)Χx

由兩個(gè)元素x和y，按照一定的順序組成的二元組稱為有序?qū)Γ涀?lt;x,y>實(shí)例：平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)<3,4>有序?qū)π再|(zhì)

1）有序性<x,y><y,x>（當(dāng)xy時(shí)）

2）<x,y>與<u,v>相等的充分必要條件是

<x,y>=<u,v>x=uy=v例1<2,x+5>=<3y4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

第三頁，共三十三頁，編輯于2023年，星期六3有序n元組定義一個(gè)有序n(n3)元組<x1,x2,…,xn>是一個(gè)有序?qū)?，其中第一個(gè)元素是一個(gè)有序n-1元組，即

<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

實(shí)例：空間直角坐標(biāo)系中的坐標(biāo)

<3，5，－6>n維向量是有序

n元組.當(dāng)n=1時(shí),<x>形式上可以看成有序1元組.第四頁，共三十三頁，編輯于2023年，星期六4笛卡兒積定義設(shè)A,B為集合，用A中元素為第一個(gè)元素，B中元素為第二個(gè)元素，構(gòu)成有序?qū)?所有這樣的有序?qū)M成的集合叫做

A與B的笛卡兒積

記作AB，即AB={<x,y>|xAyB}例2A={1,2,3},B={a,b,c}

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}

A={},P(A)A={<,>,<{},>}第五頁，共三十三頁，編輯于2023年，星期六5笛卡兒積的性質(zhì)不適合交換律

ABBA(AB,A,B)不適合結(jié)合律

(AB)CA(BC)(A,B)對于并或交運(yùn)算滿足分配律

A(BC)=(AB)(AC)(BC)A=(BA)(CA)

A(BC)=(AB)(AC)(BC)A=(BA)(CA)若A或B中有一個(gè)為空集，則AB就是空集.

A=B=

若|A|=m,|B|=n,

則|AB|=mn

第六頁，共三十三頁，編輯于2023年，星期六6性質(zhì)的證明證明A(BC)=(AB)(AC)證任取<x,y><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).第七頁，共三十三頁，編輯于2023年，星期六7例題解(1)任取<x,y><x,y>AC

xAyC

xByD<x,y>BD

例3(1)證明A=BC=DAC=BD

(2)AC=BD是否推出A=B

C=D?為什么？(2)不一定.反例如下：

A={1}，B={2},C=D=,則AC=BD但是AB.第八頁，共三十三頁，編輯于2023年，星期六8例4(1)證明A

BC

DAC

BD

(2)AC

BD是否推出A

B

C

D解(1)任取<x,y><x,y>AC

xAyC

xByD<x,y>BD

(2)不一定.反例如下：

A={1}，B={2},C=D=第九頁，共三十三頁，編輯于2023年，星期六9二元關(guān)系：集合中兩個(gè)元素之間的某種關(guān)系例1甲、乙、丙3個(gè)人進(jìn)行乒乓球比賽，任何兩個(gè)人之間都要比賽一場。假設(shè)比賽結(jié)果是乙勝甲，甲勝丙，乙勝丙。比賽結(jié)果可表示為：{<乙,甲>，<甲,丙>，<乙,丙>}，其中<x,y>表示x勝y，它表示了集合{甲,乙,丙}中元素之間的一種勝負(fù)關(guān)系.例2有A、B、C3個(gè)人和四項(xiàng)工作G1、G2、G3、G4，已知A可以從事工作G1和G4，B可以從事工作G3，C可以從事工作G1和G2.

那么，人和工作之間的對應(yīng)關(guān)系可以記作

R＝

{<A,G1>,<A,G4>,<B,G3>,<C,G1>,<C,G2}它表示了集合{A,B,C}到工作{G1,G2,G3,G4}之間的關(guān)系第十頁，共三十三頁，編輯于2023年，星期六10二元關(guān)系的定義定義如果一個(gè)集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個(gè)二元關(guān)系,簡稱為關(guān)系，記作R.如<x,y>∈R,可記作xRy；如果<x,y>R,則記作xy實(shí)例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元關(guān)系,當(dāng)a,b不是有序?qū)r(shí)，S不是二元關(guān)系根據(jù)上面的記法，可以寫1R2,aRb,ac等.第十一頁，共三十三頁，編輯于2023年，星期六11從A到B的關(guān)系與A上的關(guān)系定義設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)則叫做A上的二元關(guān)系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是從A到B的二元關(guān)系,R3和R4同時(shí)也是A上的二元關(guān)系.計(jì)數(shù)|A|=n,|A×A|=n2,A×A的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,則A上有=512個(gè)不同的二元關(guān)系.第十二頁，共三十三頁，編輯于2023年，星期六12A上重要關(guān)系的實(shí)例設(shè)A為任意集合，是A上的關(guān)系，稱為空關(guān)系EA,IA分別稱為全域關(guān)系與恒等關(guān)系，定義如下：EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},則

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

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

第十三頁，共三十三頁，編輯于2023年，星期六13A上重要關(guān)系的實(shí)例（續(xù)）小于等于關(guān)系LA,整除關(guān)系DA,包含關(guān)系R定義：

LA={<x,y>|x,y∈A∧x≤y},AR，R為實(shí)數(shù)集合

DB={<x,y>|x,y∈B∧x整除y},BZ*,Z*為非0整數(shù)集

R={<x,y>|x,y∈A∧xy},A是集合族.類似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.第十四頁，共三十三頁，編輯于2023年，星期六14實(shí)例例如A={1,2,3},B={a,b},則

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

A=P(B)={,{a},,{a,b}},則A上的包含關(guān)系是R={<,>,<,{a}>,<,>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<,>,<,{a,b}>,<{a,b},{a,b}>}

第十五頁，共三十三頁，編輯于2023年，星期六15關(guān)系的表示表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖關(guān)系矩陣：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR=[rij]mn,其中rij

=1<xi,yj>R.關(guān)系圖：若A={x1,x2,…,xm}，R是從A上的關(guān)系，R的關(guān)系圖是GR=<A,R>,其中A為結(jié)點(diǎn)集，R為邊集.如果<xi,xj>屬于關(guān)系R，在圖中就有一條從xi

到xj的有向邊.注意：A,B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系，關(guān)系圖適于表示A上的關(guān)系第十六頁，共三十三頁，編輯于2023年，星期六16實(shí)例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系矩陣MR和關(guān)系圖GR如下：第十七頁，共三十三頁，編輯于2023年，星期六17基本運(yùn)算定義定義域、值域、域逆、合成、限制、像基本運(yùn)算的性質(zhì)冪運(yùn)算定義求法性質(zhì)4.2關(guān)系的運(yùn)算第十八頁，共三十三頁，編輯于2023年，星期六18關(guān)系的基本運(yùn)算定義定義域、值域

和域

domR={x|y(<x,y>R)}ranR={y|x(<x,y>R)}fldR=domR

ranR例1R={<1,2>,<1,3>,<2,4>,<4,3>},則domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}第十九頁，共三十三頁，編輯于2023年，星期六19關(guān)系的基本運(yùn)算定義（續(xù)）逆與合成

R1={<y,x>|<x,y>R}

R°S=|<x,y>|

z(<x,z>S<z,y>R)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

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

R°S={<1,2>,<1,4>,<3,2>,<3,3>}S°R={<1,3>,<2,2>,<2,3>}第二十頁，共三十三頁，編輯于2023年，星期六20合成運(yùn)算的圖示方法

利用圖示（不是關(guān)系圖）方法求合成

R°S={<1,2>,<1,4>,<3,2>,<3,3>}

S°R={<1,3>,<2,2>,<2,3>}第二十一頁，共三十三頁，編輯于2023年，星期六21限制與像定義

F在A上的限制

F?A={<x,y>|xFy

xA}A在F下的像

F[A]=ran(F?A)實(shí)例R={<1,2>,<2,3>,<1,4>,<2,2>}

R?{1}={<1,2>,<1,4>}

R[{1}]={2,4}

R?=

R[{1,2}]={2,3,4}注意：F?AF,F[A]ranF

第二十二頁，共三十三頁，編輯于2023年，星期六22關(guān)系基本運(yùn)算的性質(zhì)定理1設(shè)F是任意的關(guān)系,則(1)(F1)1=F(2)domF1=ranF,ranF1=domF證(1)任取<x,y>,由逆的定義有<x,y>∈(F

1)1<y,x>∈F1<x,y>∈F所以有(F1)1=F(2)任取x,x∈domF1y(<x,y>∈F1)y(<y,x>∈F)

x∈ranF

所以有domF1=ranF.同理可證ranF1=domF.第二十三頁，共三十三頁，編輯于2023年，星期六23定理2設(shè)F,G,H是任意的關(guān)系,則

(1)(F°G)°H=F°(G°H)(2)(F°G)1=G1°F1證(1)任取<x,y>,<x,y>(F°G)°Ht(<x,t>∈H∧<t,y>∈F°G)t(<x,t>∈H∧s(<t,s>∈G)∧<s,y>∈F))

ts(<x,t>∈H∧<t,s>∈G∧<s,y>∈F)

s(<s,y>∈F∧t(<x,t>∈H∧<t,s>∈G))

s(<s,y>∈F∧<x,s>∈G°H)

<x,y>∈F°(G°H)

所以(F°G)°H=F°(G°H)關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）

第二十四頁，共三十三頁，編輯于2023年，星期六24

(2)任取<x,y>,<x,y>∈(F°G)1

<y,x>∈F°G

t(<y,t>∈G∧(t,x)∈F)

t(<x,t>∈F1∧(t,y)∈G1)

<x,y>∈G1°F1

所以(F°G)1=G1°F1

關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）

第二十五頁，共三十三頁，編輯于2023年，星期六25關(guān)系基本運(yùn)算的性質(zhì)（續(xù)）

設(shè)F、G、H為任意的二元關(guān)系，則有：F°(G

H)

=F°G

F°H(G

H)

°F=G°F

H°F(合成運(yùn)算對運(yùn)算滿足分配律）3.F°(G

H)

F°G

F°H4.(G

H)

°F

G°F

H°F(合成運(yùn)算對

運(yùn)算分配后是包含關(guān)系）第二十六頁，共三十三頁，編輯于2023年，星期六26A上關(guān)系的冪運(yùn)算設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：

(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn°R

注意：對于A上的任何關(guān)系R1和R2都有

R10=R20=IA

對于A上的任何關(guān)系R都有

R1=R第二十七頁，共三十三頁，編輯于2023年，星期六27冪的求法(1)對于集合表示的關(guān)系R，計(jì)算Rn就是n個(gè)R左復(fù)合.(2)矩陣表示就是n個(gè)矩陣相乘,其中相加采用邏輯加.例3設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.

解R與R2的關(guān)系矩陣分別為第二十八頁，共三十三頁，編輯于2023年，星期六28同理，R0=IA,R3和R4的矩陣分別是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…

對于有窮集A，A上關(guān)系R的不同冪只有有限個(gè)。冪的求法（續(xù)）第二十九頁，共三十三頁，