笛卡爾積與二元關(guān)系42 關(guān)系的運(yùn)算

1第2章二元關(guān)系為了研究離散對象之間的聯(lián)系,本章引入關(guān)系的概念本章討論的二元關(guān)系(簡稱關(guān)系)仍然是一種集合.它的元素是由有序?qū)M成.22.1有序?qū)εc笛卡兒積

有序?qū)Φ芽▋悍e及其性質(zhì)二元關(guān)系的定義二元關(guān)系的表示3有序?qū)Χx

由兩個元素x和y，按照一定的順序組成的二元組稱為有序?qū)?，記?lt;x,y>.x叫有序?qū)Φ牡谝辉?y叫有序?qū)Φ牡诙貙?shí)例：點(diǎn)的直角坐標(biāo)(3,4)有序?qū)π再|(zhì)

有序性

<x,y><y,x>（當(dāng)xy時）

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

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

4=2,x+5=y

y=2,x=3

4有序?qū)?lt;x,y>和集合{x,y}的區(qū)別:有序?qū)?lt;x,y>中x和y是有順序的,xy時,<x,y><y,x>

如:<3,6><6,3>而集合中{x,y},x,y是無序的,xy時,{x,y}={y,x}

如:{3,6}={6,3}

5有序?qū)Φ母拍羁梢詳U(kuò)展成有序n元組定義一個有序n(n3)元組<x1,x2,…,xn>是一個有序?qū)?，其中第一個元素是一個有序n-1元組，即

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

當(dāng)n=1時,<x>形式上可以看成有序1元組.實(shí)例

n維向量是有序

n元組.6笛卡兒積:一種新的集合運(yùn)算定義設(shè)A,B為集合，用A中的元素為第一元素,B中的元素為第二元素,構(gòu)成有序?qū)?所有這樣的有序?qū)M成的集合叫做A與B的笛卡兒積記作AB，即AB={<x,y>|xA且yB}例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={<,>,<{},>}

*如果A中有m個元素,B中有n個元素,則AB

有mn個元素.7例4.18笛卡兒積的性質(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中有一個為空集，則AB就是空集.

A=B=

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

則|AB|=mn

9分配律的證明證明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).10例題解(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.11二元關(guān)系什么是關(guān)系:

在涉及離散對象的很多問題中,往往需要研究這些對象之間的某種關(guān)系.

日常生活中父子關(guān)系,兄弟關(guān)系等,

都可以抽象成集合中元素之間的關(guān)系.

為簡單起見,我們僅討論兩個集合上的二元關(guān)系.12二元關(guān)系的定義定義如果一個集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個二元關(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，S不是二元關(guān)系根據(jù)上面的記法，可以寫1R2,aRb,ac等.關(guān)系也是一種集合,只是關(guān)系中的元素為有序?qū)?13從A到B的關(guān)系與A上的關(guān)系例4A={0,1},B={1,2,3},求A×B,A×AA×B={<0,1>,<0,2>,<0,3>,<1,1>,<1,2>,<1,3>}A×A={<0,0>,<0,1>,<1,0>,<1,1>}定義設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,A=B時則叫做A上的二元關(guān)系.14從A到B的關(guān)系與A上的關(guān)系定義設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,A=B時則叫做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同時也是A上的二元關(guān)系.計(jì)數(shù)|A|=n,|A×A|=n2,A×A的子集有個.所以A上有個不同的二元關(guān)系.例如|A|=3,則A上有=512個不同的二元關(guān)系.

其中只有少數(shù)的二元關(guān)系是我們需要關(guān)注的.15問題：下列說法有何區(qū)別？設(shè)A,B為集合,

從A到B的二元關(guān)系,A上的二元關(guān)系16A上三種特殊關(guān)系設(shè)A為任意集合，是A上的關(guān)系，稱為空關(guān)系EA,IA分別稱為A上的全域關(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>}

17A上其他特殊關(guān)系小于等于關(guān)系LA,整除關(guān)系DA,包含關(guān)系R定義：小于等于關(guān)系

LA={<x,y>|x,y∈A∧x≤y},AR，R為實(shí)數(shù)集合整除關(guān)系DB={<x,y>|x,y∈B∧x整除y},BZ*,Z*為非0整數(shù)集例如A={1,2,3}則

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

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}.18包含關(guān)系:R={<x,y>|x,y∈A∧xy},A是集合族例:A=P(B)={,{a},,{a,b}},則A上的包含關(guān)系是R={<,>,<,{a}>,<,>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<,>,<,{a,b}>,<{a,b},{a,b}>}

除此以外,還可以構(gòu)成其他關(guān)系:

如:大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.例:P804.419例設(shè)S={1，2，3，4}，下面定義的R都是S上的關(guān)系，分別列出R中的元素（1）R={<x,y>|x,y∈s∧x|y}R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,4>,<3,3>,<4,4>}(2)R={<X,Y>|x,y∈s∧x/y是素?cái)?shù)R=<2,1>,<3,1>,<4,2>}求S上的全域關(guān)系，恒等關(guān)系？20關(guān)系的表示方法三種表示方式：關(guān)系的集合表達(dá)式、關(guān)系矩陣、關(guān)系圖關(guān)系矩陣：若A={x1,x2,…,xn}，R是A上的關(guān)系，R的關(guān)系矩陣是布爾矩陣MR=[rij]nn,其中rij

=1<xi,xj>R.A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系矩陣MR練習(xí)：設(shè)S={1，2，3，4}，R都是S上的關(guān)系，

R={<2,1>,<3,1>,<4,2>}，用關(guān)系矩陣表示R21關(guān)系矩陣表示從A到B的關(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.注意：A,B為有窮集，關(guān)系矩陣適于表示從A到B的關(guān)系或者A上的關(guān)系22用關(guān)系圖表示A上的關(guān)系關(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

的有向邊.注意:以上關(guān)系圖適于表示A上的關(guān)系

A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系圖GR如下：23實(shí)例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系矩陣MR和關(guān)系圖GR如下：24A到B的關(guān)系圖（不是真正意義的關(guān)系圖，主要用于計(jì)算）例:設(shè)A={2,3,4,8},B={1,5,7}A到B上的關(guān)系R={<2,5>,<2,7>,<3,5>,<4,1>,<8,7>}A中的4個元素用4個結(jié)點(diǎn)表示畫左邊,B中的3個元素用3個結(jié)點(diǎn)畫右邊.如關(guān)系中存在有序?qū)?lt;a,b>,就將結(jié)點(diǎn)a和b相連.

如右圖:254.8例題分析例4.26P106X={-4,-3,-2,-1,0,1,2,3,4}R1={<x,y>|x,y∈X∧x<y}

={<-4,-3>,<-4,-2>,….<-4,4>,<-3,-2>…..}R(0)={1,2,3,4}

對于x∈X定義集合

R(x)={y|xRy}

求R(0)=26小結(jié)為了研究離散對象之間的聯(lián)系,本章引入二元關(guān)系的概念.1什么是關(guān)系?關(guān)系也是一種集合,二元關(guān)系中的元素為有序?qū)?這些有序?qū)χ械膬蓚€元素來自兩個不同或相同的集合.

因此,關(guān)系是建立在其他集合之上的集合.

如,A到B上的關(guān)系,反映不同集合中元素與元素之間的關(guān)系

A上的關(guān)系,反映的是同一集合中元素之間的關(guān)系.272A上的關(guān)系數(shù)目為,這個數(shù)目往往是很大的,而我們通常關(guān)注的是其中少量的有特殊含義的關(guān)系.

如EA,IA,整除,小于等于,包含等3關(guān)系的表示方法.1)集合表達(dá)式

2)關(guān)系矩陣

3)關(guān)系圖接下來的課程,我們將學(xué)習(xí)關(guān)系的運(yùn)算,關(guān)系的性質(zhì)等.

28作業(yè)（清華版）29關(guān)系也是集合(其元素為有序?qū)?,因此可對關(guān)系進(jìn)行集合的運(yùn)算,如并∪\交∩\補(bǔ),從而產(chǎn)生其他新的關(guān)系,其運(yùn)算規(guī)則與一般集合一樣地進(jìn)行.7.3關(guān)系的運(yùn)算下面討論關(guān)系的以下運(yùn)算:

求定義域\值域\域\關(guān)系的逆\

關(guān)系的復(fù)合\關(guān)系R在A上的限制\A在R下的像.

以及關(guān)系的冪運(yùn)算30關(guān)系的基本運(yùn)算定義1)定義域domR

:R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合:

domR={x|y(<x,y>R)}2)值域ranR:

R中所有有序?qū)Φ牡诙貥?gòu)成的集合:

ranR={y|x(<x,y>R)}3)R的域fidR: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}31關(guān)系的基本運(yùn)算定義（續(xù)）1)關(guān)系的逆

R的記作R1={<y,x>|<x,y>R}

求關(guān)系的逆就是把其中的有序?qū)︻嵉惯^來.例2R={<1,2>,<2,3>,<1,4>,<2,2>}

={<2,1>,<3,2>,<4,1>,<2,2>}2)關(guān)系R和S的復(fù)合運(yùn)算(左復(fù)合）

R°S={<x,y>|

z(<x,z>S<z,y>R)}<x,y>∈R°S,表示在某”中間變量”z,使x通過S變到z,z再通過R變到y(tǒng).322)關(guān)系R和S的復(fù)合運(yùn)算

R·S={<x,y>|

z(<x,z>S<z,y>R)}<x,y>∈R°S,表示在某”中間變量”z,使x通過S變到z,z再通過R變到y(tǒng).x------>z------->ySR33關(guān)系的復(fù)合運(yùn)算的兩種定義左復(fù)合（本教材采用）：

R·S={<x,y>|

z(<x,z>S<z,y>R)}

右復(fù)合：

R·S={<x,y>|

z(<x,z>R<z,y>S)}兩種定義都是合理的，性質(zhì)一樣，但結(jié)果不同34利用關(guān)系圖求關(guān)系的復(fù)合:

利用R和S的關(guān)系圖求關(guān)系的復(fù)合:

R·S

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

S·R

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

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}SRRS35例:設(shè)F是由A={1,2,3,4}到B={2,3,4}的關(guān)系

G是由B到C={3,5,6}的關(guān)系.分別定義為F={<a,b>|a+b=6}={<2,4>,<3,3>,<4,2>}G={<b,c>|b整除c}={<2,6>,<3,6>,<3,3>}求復(fù)合關(guān)系F·G36限制與像關(guān)系F在A上的限制

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

xA}含義:表示F對A中元素的作用----第一元素xA對應(yīng)的有序?qū)?例1:R={<1,2>,<2,3>,<1,4>,<2,2>}A={1},

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

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

R?=A在F下的像:即F在A上的限制的值域

F[A]=ran(F?A)實(shí)例

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

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

求A在F下的像的步驟,應(yīng)1)先求出F在A上的限制,2)再求出其值域.注意：F?AF,F[A]ranF

37例4.6:R在A上的限制，A在R下的像設(shè)F,G是N上的關(guān)系，定義

F={(x,y>|x,y∈N∧y=x*x}G={<x,y>|x,y∈N∧y=x+1}

求：G的逆，F(xiàn)?{1,2}，F(xiàn)[{1,2}]38例4.6(復(fù)合運(yùn)算）設(shè)F,G是N上的關(guān)系，定義

F={(x,y>|x,y∈N∧y=x*x}G={<x,y>|x,y∈N∧y=x+1}

求：F·G,

x------>z------->yGFx+1=zy=z*z

F·G=y=z*z=(x+1)(x+1)39關(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.40定理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>∈F°G∧<t,y>∈H)t(s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)

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

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

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

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

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

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

<y,x>∈F°G

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

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

<x,y>∈G1°F1

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

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

42A上關(guān)系的冪運(yùn)算設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：

(1)R0={<x,x>|x∈A}=IA,即為A上的恒等關(guān)系

(2)Rn+1=Rn°R

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

R10=R20=IA

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

R1=R43冪的求法1-圖解法(主要考慮n>=2時)例:設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}求={<a,a>,<b,b>,<c,c>,<d,d>}=R可按下圖解法求得:={<a,a>,<a,c>,<b,b>,<b,d>}44冪的求法2-關(guān)系矩陣相乘法1)首先求出R的關(guān)系矩陣M2)的關(guān)系矩陣M2=M*M3)R3的關(guān)系矩陣M3=M2*M4)R4的關(guān)系矩陣M4=M3*M…5)矩陣乘法時,第i行第j列的元素滿足:rij=ri1*r1j+ri2r2j+ri3*r3j+ri4*r4j相加采用的是邏輯加:1+1=1,1+0=0+1=1,0+0=0例3:設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},解R與R2的關(guān)系矩陣分別為r11=0*0+1*1+0*0+0*0=145同理，R0=IA,R3和R4的矩陣分別是：在本例中,如果對n>5繼續(xù)求冪,就會發(fā)現(xiàn)M4=M2,即R4=R2.因此可以得到

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

冪的求法（續(xù)）可以證明,對于有窮集A和A上的關(guān)系R,R的不同次冪只有有限個.冪序列是一個周期性變化的序列,就象正玄函數(shù)一樣,利用它的周期性可以將R的高次冪化簡成R的低次冪.

注:不同的A和R,周期是不同的.46R0,R1,R2,R3,…的關(guān)系圖如下圖所示冪的求法3-關(guān)系圖法以求為例