二元關(guān)系和函數(shù)課件

二元關(guān)系和函數(shù)說(shuō)起關(guān)系這個(gè)詞，對(duì)我們并不陌生，世界上存在著各種各樣的關(guān)系，人與人之間的“同志”關(guān)系；“同學(xué)”關(guān)系；“朋友”關(guān)系；“師生”關(guān)系；“上下級(jí)”關(guān)系；“父子”關(guān)系；兩個(gè)數(shù)之間有“大于”關(guān)系；“等于”關(guān)系和“小于”關(guān)系；兩個(gè)變量之間有一定的“函數(shù)”關(guān)系；計(jì)算機(jī)內(nèi)兩電路間有導(dǎo)線(xiàn)“連接”關(guān)系；程序間有“調(diào)用”關(guān)系等等。所以對(duì)關(guān)系進(jìn)行深刻的研究，對(duì)數(shù)學(xué)與計(jì)算機(jī)科學(xué)都有很大的用處。在這一章我們要研究集合內(nèi)元素間的關(guān)系以及集合之間元素之間的關(guān)系，這就是“關(guān)系”與“函數(shù)”。它們是很重要的基本數(shù)學(xué)概念，在數(shù)學(xué)領(lǐng)域中均有很大的作用，并且對(duì)研究計(jì)算機(jī)科學(xué)中的許多問(wèn)題如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)、情報(bào)檢索、算法分析、計(jì)算理論等都是很好的數(shù)學(xué)工具。

關(guān)系的引入

例4.0設(shè)一旅館有n個(gè)房間，每個(gè)房間可住兩個(gè)旅客，所以一共可住2n個(gè)旅客，在旅館內(nèi)，旅客與房間有一定關(guān)系，用R

表示“某旅客住在某房間”這種關(guān)系。設(shè)n=3表示旅館共有3個(gè)房間,分別記以1,2,3可住6個(gè)旅客分別記以a,b,c,d,e,f,這些旅客住的房間如右下圖所示123abcdef滿(mǎn)足R的所有關(guān)系可看成是一個(gè)有序偶的集合，這個(gè)集合可叫RR={<a,1>,<b,1>,<c,2>,<d,2>,<e,3>,<f,3>}

若令

A={a,b,c,d,e,f}B={1,2,3}則例中關(guān)系的每一元素均屬于A×B亦即R是A×B的子集，并稱(chēng)此關(guān)系為從A到B的關(guān)系R?！?.1集合的笛卡爾積與二元關(guān)系定義4.1由兩個(gè)元素x,y（允許x=y）按一定順序排列成的二元組叫做一個(gè)有序?qū)蛐蚺迹涀?lt;x,y>,其中x是它的第一元素，y是它的第二元素。有序?qū)?lt;x,y>具有以下性質(zhì)：(1)當(dāng)x≠y時(shí)，<x,y>≠<y,x>(2)<x,y>=<w,v>

x=w∧y=v例4.1：已知<x+3,y-2>=<y+7,3y-x>，求x和y。解：由有序?qū)ο嗟鹊某湟獥l件得

x+3=y+7y-2=3y-x

解得x=6,y=2§4.1集合的笛卡爾積與二元關(guān)系定義4.2一個(gè)有序n元組(n≥3)是一個(gè)有序?qū)Γ渲械谝粋€(gè)元素是一個(gè)有序n-1元組，一個(gè)有序n元組記作<x1,x2,…,xn>,即<x1,x2,…,xn>=<

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

例如：空間直角坐標(biāo)系中點(diǎn)的坐標(biāo)<1,-1,3>,<2,4.5,0>等都是有序3元組。n維空間中點(diǎn)的坐標(biāo)或n維向量都是有序n元組。形式上也可以把<x>看成有序1元組。定義4.3

設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)?。所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積，記作A×B。笛卡兒積的符號(hào)化表示為：

A×B={<x,y>|x∈A∧y∈B}例如：若A={1,2},B={a,b,c},則A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}B×A={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}易知：若|A|=m,(即集合A的元素的個(gè)數(shù)),|B|=n,則|A×B|=|B×A|=mn§4.1集合的笛卡爾積與二元關(guān)系由前面的定義可知：有序?qū)褪怯许樞虻臄?shù)組，如<x,y>，x,y的位置是確定的，不能隨意放置。

注意：有序?qū)?lt;a，b>

<b,a>，以a,b為元素的集合{a,b}={b,a}；有序?qū)?a,a)有意義，而集合{a,a}不成立，因?yàn)樗皇菃卧丶希瑧?yīng)記作{a}。

笛卡兒積是一種集合合成的方法，把集合A，B合成集合A×B，規(guī)定

A×B＝{<x,y>

x

A,y

B}由于有序?qū)?lt;x,y>中x,y的位置是確定的，因此A×B的記法也是確定的，不能寫(xiě)成B×A。

笛卡兒積也可以多個(gè)集合合成

A1×A2×…×An。

笛卡兒積的運(yùn)算性質(zhì)。笛卡兒積的性質(zhì)：1、對(duì)任意集合A，根據(jù)定義有

A×φ=φ×A=φ2、一般來(lái)說(shuō)，笛卡兒積不滿(mǎn)足交換律，即

A×B≠B×A（當(dāng)A≠BB≠φ、A≠φ時(shí)）3、笛卡兒積不滿(mǎn)足結(jié)合律，即(A×B)×C≠A×(B×C)（當(dāng)A≠φ∧B≠φ∧C≠φ時(shí)）4、笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿(mǎn)足分配律，即

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)§4.1集合的笛卡爾積與二元關(guān)系例4.2證明：(B∩C)×A=(B×A)∩(C×A)對(duì)于<x,y><x,y>∈(B∩C)×A

x∈(B∩C)∧y∈A

x∈B∧x∈

C∧y∈A

x∈B∧x∈C

∧y∈A∧y∈A

(x∈B∧y∈A)∧(x∈C∧y∈A)

<x,y>∈B×A∧<x,y>∈C×A

<x,y>∈(B×A)∩(C×A)∴(B∩C)×A=(B×A)∩(C×A)§4.1集合的笛卡爾積與二元關(guān)系例4.3：設(shè)A，C，B，D為任意集合，判斷以下命題是否為真，并說(shuō)明理由。(1)A×B=A×C=>B=

C(2)A-(B×C)=(A-B)×(A-C)(3)存在集合A,使得A

A×A.解：(1)不一定為真。反例A=φ,B、C為任意不相等的非空集合。(2)不一定為真。反例A={1},B={2},C={3}.(3)為真。當(dāng)A=φ時(shí)成立。定義4.4

設(shè)A1,A2,…,An,是集合(n≥2),它們的n階笛卡兒積記作A1×A2×…×An

，其中

A1×A2×…×An={<x1,x2,…,xn

>

|x1

A1∧x2

A2∧…∧xn

An

}

當(dāng)A1=A2=…=An=A時(shí),將起n階笛卡兒積記作An例如，A={a,b},則

A3=A×A×A={a,b}×{a,b}×{a,b}

={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}§4.1集合的笛卡爾積與二元關(guān)系例4.6設(shè)集合A={a,b},B={1,2,3},C=j3h3vyb,求A×B×C，B×A。解先計(jì)算A×B＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>} A×B×C＝

{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}×znvygb4＝{<a,1,d>,<a,2,d>,<a,3,d>,<b,1,d>,<b,2,d>,<b,3,d>}

B×A＝{<1,a>,<2,a>,<3,a>,<1,b>,<2,b>,<3,b>}

例4.7設(shè)集合A＝{1,2},求A×P(A)。解P(A)={

,{1},{2},{1,2}} A×P(A)＝{1,2}×{

,{1},}{2},{1,2} ={<1,

>,<2,

>,<1,{1}>,<2,{1}>,<1,{2}>,<2,{2}>,<1,{1,2}>,<2,{1,2}>}定義4.5

如果一個(gè)集合符合以下條件之一：(1)集合非空，且它的元素都是有序?qū)?2)集合是空集則稱(chēng)該集合為一個(gè)二元關(guān)系，記作R，簡(jiǎn)稱(chēng)為關(guān)系。對(duì)于二元關(guān)系R，若<x,y>∈R,可記作xRy;如果<x,y>R,則記作xRy。例：R1={<1,2>,<a,b>},R2={5,6,7}aR1b,1R12,5R16§4.1集合的笛卡爾積與二元關(guān)系二元關(guān)系是兩種客體之間的聯(lián)系，例如某學(xué)生學(xué)習(xí)語(yǔ)文、數(shù)學(xué)、外語(yǔ)，表示為

A＝{語(yǔ)文,數(shù)學(xué),外語(yǔ)}功課的成績(jī)分四個(gè)等級(jí)，記作B＝{A，B，C，D}于是該生成績(jī)的全部可能為A×BA×B＝{<語(yǔ)文,A>,<語(yǔ)文,B>,<語(yǔ)文,C>,<語(yǔ)文,D>,<數(shù)學(xué),A>,<數(shù)學(xué),B>,<數(shù)學(xué),C>,<數(shù)學(xué),D>,<外語(yǔ),A>,<外語(yǔ),B>,<外語(yǔ),C>,<外語(yǔ),D>}而該生的實(shí)際成績(jī)

P＝{<語(yǔ)文,B>,<數(shù)學(xué),A>,<外語(yǔ),D>}可以看出P是A×B的一個(gè)子集，它表示了功課與其成績(jī)的一種關(guān)系。由此可見(jiàn)：兩個(gè)集合之間的二元關(guān)系，實(shí)際上就是兩個(gè)元素之間的某種相關(guān)性。定義4.6設(shè)A，B為集合，A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)則叫做A上的二元關(guān)系。例4.7：若A={a,b}，B={2,5,8}，則

A×B={<a,2>,<a,5>,<a,8>,<b,2>,<b,5><b,8>}令R1={<a,2>,<a,8>,<b,2>},R2={<a,5>,<b,2><b,5>},R3={<a,2>}因?yàn)镽1

A×B，R2

A×B，R3

A×B，所以R1，R2和R5均是由A到B的二元關(guān)系因?yàn)橹挥懻摱P(guān)系，所以今后無(wú)特別聲明，術(shù)語(yǔ)“關(guān)系”皆指二元關(guān)系？又例：若A={a,b}，B={2,5,8}，則

B×A={<2,a>,<2,b>,<5,a>,<5,b>,<8,a><8,b>}令R4={<2,a>,<2,b>},R5={<5,a>,<8,a><8,b>},因?yàn)镽4B×A，R5B×A，所以R4和R5均是由B到A的關(guān)系又B×B={<2,2>,<2,5>,<2,8>,<5,2>,<5,5>,<5,8>,<8,2>,<8,5>,<8,8>}

令R6={<2,2>,<5,2>,<8,2>},R7={<8,5>,<5,2><2,8>,<2,5>}因?yàn)镽6B×B，R7B×B，所以R6和R7均是集合B上的關(guān)系。若集合|A|=n,則集合A上的二元關(guān)系有多少個(gè)？答曰：|A|=n，則|A×A|=n2,A×A的任一個(gè)子集就是A上的二元關(guān)系，即P(A)=2n個(gè)。２例4.8

A={1,2}則A×A有2n個(gè)不同的二元關(guān)系A(chǔ)×A={1,2}×{1,2}={<1

1>,<1,2>,<2,1>,<2,2>}A×A的任一個(gè)子集就是A×A的冪集，即P(A)P(A)={

,{<1,1>},{<1,2>},{<2,1>},{<2,2>}

{<1,1>,<1,2>},{<1,1>,<2,1>},{<1,1>,<2,2>}

{<1,2>,<1,1>},{<1,2>,<2,1>},{<1,2>,<2,2>}

{<2,2>,<1,1>},{<2,2>,<1,2>},{<2,2>,<2,1>}

{<1,1>,<1,2>,<2,1>},

{<1,1>,<1,2>,<2,2>},

{<1,1>,<2,1>,<2,2>},{<1,2>,<2,1>,<2,2>}

{<1,1>,<1,2>,<2,1>,<2,2>}}

集合中的元素不分順序２若集合A={a,b,c}

則A的冪集，P(A)為P(A)={

,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}

（注{a,a}={a}{b,b}={c,c}={c}）三類(lèi)特殊的關(guān)系

對(duì)于任何集合A，空集φ

是A×A的子集，叫做A上的空關(guān)系定義EA={<x,y>|x∈A∧y∈A}=A×A為全域關(guān)系定義IA={<x,x>|x∈A}為恒等關(guān)系例：若A={1,2}，則

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

IA={<1,1>,<2,2>}除上述三類(lèi)特殊的關(guān)系外，還有一些常用的關(guān)系，如：

LA={<x,y>|x,y∈A∧x≤y}(A

R)為實(shí)數(shù)集上的小于等于關(guān)系。

DA={<x,y>|x,y∈A∧x整除y}(A

Z*)為非正整數(shù)集上的整除關(guān)系。

R

={<x,y>|x,y∈A∧x

y}(A是集合族)為集合上的包含關(guān)系。類(lèi)似地還可以定義大于等于關(guān)系、大于關(guān)系、小于關(guān)系、真包含關(guān)系等。§4.1集合的笛卡爾積與二元關(guān)系例4.9：設(shè)A={1,2,3,4}，請(qǐng)表示下列關(guān)系。(1)R={<x,y>|x是y的倍數(shù)}(2)R={<x,y>|(x-y)2∈A}(3)R={<x,y>|x除y是素?cái)?shù)}(4)R={<x,y>|x≠y}§4.1集合的笛卡爾積與二元關(guān)系解(1)DA={<1,1>,<2,2>,<3,3>,<4,4>,<2,1>,<3,1>,<4,1>,<4,2>}(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}(3)DA={<1,2>,<1,3>,<2,4>}(4)R={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}|A|=n,|B|=m,A,B中的元素已按一定的次序排列若A={x1,x2,…,xn},B={y1,y2,…,ym}且R

A

B,若

1若xiRyjrij=(i=1,2,…,nj=1,2,…,m)0若xiRyj則稱(chēng)矩陣M(R)=(rij)n

m為R的關(guān)系矩陣。有窮集合上的二元關(guān)系的三種表示方法：集合表示法（前已使用）

關(guān)系矩陣法關(guān)系圖關(guān)系矩陣是表示關(guān)系的另一種有效的方法，其優(yōu)點(diǎn)是可以利用矩陣作為研究關(guān)系的手段，而且這樣做便于計(jì)算機(jī)進(jìn)行處理。設(shè)R：AB，A和B都是有限集，且

設(shè)A，B為集合，A×B的任何子集Ri

A×B則稱(chēng)Ri所定義的二元關(guān)系叫做從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)則叫做A上的二元關(guān)系則r11r12…r1n(rij)=r21r22…r2n

…rn1rn2…rnn是R的關(guān)系矩陣，記作MR。關(guān)系矩陣法若A={x1,x2,…,xn},B={y1,y2,…,yn

}則R的關(guān)系矩陣是一個(gè)n行n列矩陣M(R)=(rij)nn

,

其中元素rij

為：1若xiRyjrij=(i,j=1,2,…,n)0若xiRyj

0111MR=001100010000例4.10A={1,2,3,4}R為A上的小于關(guān)系，則R為：R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}R的關(guān)系矩陣為：12341234例4.11設(shè)集合A＝{2,3,4},B={8,9,12,14}.R是由A到B的二元關(guān)系，定義：

R={<a,b>|a整除b}寫(xiě)出R的表達(dá)式和關(guān)系矩陣.解R={<2,8>,<2,12>,<2,14>,<3,9>,<3,12>,<4,8>,<4,12>}89121421011R的關(guān)系矩陣為.MR=3011041010

關(guān)系圖關(guān)系圖是表示關(guān)系的一種直觀形象的方法，設(shè)R：AB，A和B都是有限集，A={x1,x2,…,xn},B={y1,y2,…,ym}關(guān)系R的有序偶<xi,yj

>可用圖中從結(jié)點(diǎn)xi到y(tǒng)j

的有向邊表示，這樣即可將關(guān)系用圖表示之。例4.12設(shè)R:AB，A={x1,x2,x3,x4},B={y1,y2,y3}R={<x1,y2>,<x2,y1>,<x2,y3><x3,y3>}R的關(guān)系如下圖所示x1x2x3x4y1y2y3關(guān)系圖關(guān)系圖是表示關(guān)系的一種直觀形象的方法，設(shè)R：AB，A和B都是有限集，

A={x1,x2,…,xn},B={y1,y2,…,ym}關(guān)系R的有序偶<xi,yj

>可用圖中從結(jié)點(diǎn)xi到y(tǒng)j

的有向邊表示，這樣即可將關(guān)系用圖表示之。例4.13設(shè)R:AA，A={a,b,c,d}R={<a,b>,<a,c>,<b,a>,<b,c>,<c,c>}R的關(guān)系如下圖所示abcd其中c到c的邊稱(chēng)為環(huán)定義4.8設(shè)R是二元關(guān)系(1)R中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱(chēng)為R的定義域，記作domR,形式化表示為：

domR={x|

y(<x,y>∈R)}(2)R中所有的有序?qū)Φ牡诙貥?gòu)成的集合稱(chēng)為R的值域，記作ranR,形式化表示為：

ranR={y|

x(<x,y>∈R)}(3)R的定義域和值域的并集稱(chēng)為R的域，記作fldR,形式化表示為：

fldR=domR∪ranR§4.2關(guān)系的運(yùn)算例4.14下列關(guān)系都是整數(shù)集Z上的關(guān)系，分別求出它們的定義域和值域R1={<x,y>|x,yZ∧x≤y}(2)R2={<x,y>|x,yZ∧x2+y2=1}(3)R3={<x,y>|x,yZ∧y=2x}R4={<x,y>|x,yZ∧|x|=|y|=3}解(1)domR1=ramR1=ZR2={<0,1>,<0,-1>,<1,0>,<-1,0>}

domR2={0,1,-1}ramR2={0,1,-1}(3)domR3=ZramR3={2z|zZ}

即偶數(shù)集(4)domR4={-3,3}ramR4={-3,3}10-1-101domR2ramR2R2…210-1-2……43210-1-2-3-4…domR3=ZramR3R3例4.15設(shè)R1={<1,2>,<2,4>,<3,3>}R2={<1,3>,<2,4>,<4,2>}

求其定義域和值域解題目沒(méi)有告訴我們R1和R2是由什么集合到什么的關(guān)系,這對(duì)于我們解此題是無(wú)關(guān)緊要的,事實(shí)上,不論R1和R2是定義在何種集合上的關(guān)系,據(jù)定義域和值域的定義domR={x|

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

x(<x,y>∈R)}有

domR1={1,2,3}

domR2={1,2,4}

ramR1={2,4,3}ramR2={3,4,2}規(guī)律:集合R1和R2中序偶中的第一個(gè)元素的集合即為其定義域,序偶中的第二個(gè)元素的集合即為其值域.如果此題再加上求R1∪R2及

R1∩R2定義域和值域,則因?yàn)镽1∪R2={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}R1∩R2={<2,4>}

所以domR1∪domR2={1,2,3,4}

ramR1∪

ramR2={2,3,4}定義4.9設(shè)F,G為任意的關(guān)系,A為集合，則(1)F的逆記作F-1,

F-1={<x,y>|yFx}

(2)

F與G的合成記作F

G，其中F

G={<x,y>|

z(xGz∧zFy}

或F

G={<x,y>|

z(xFz∧zGy} p87

(3)F在A上限制記作F『A

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

∧x∈A)}(4)A在F下的象記作F[A]

F[A]=ran(F『A)§4.2關(guān)系的運(yùn)算逆關(guān)系：

設(shè)R是一個(gè)X到Y(jié)的關(guān)系，則Y到X的關(guān)系R-1：

R-1={<y,x>|<x,y>R}

稱(chēng)為R的逆關(guān)系。例4.16

設(shè)X={1,2,3}Y={a,b,c}

且設(shè)R是從X到

Y的關(guān)系R={<1,a>,<2,b>,<3,c>}

則R-1={<a,1>,<b,2>,<c,3>}例4.17

設(shè)X={x1,x2,x3}Y={y1,y2,y3}

且設(shè)R是從X到Y(jié)的關(guān)系R={<x1,y2>,<x2,y3>,<x3,y1>}的逆關(guān)系

R-1={<y2,x1>,<y3,x2>,<y1,x3>}如下圖所示：x1x2x3y1y2y3y1y2y3x1x2x3

RR-1合成關(guān)系（或復(fù)合關(guān)系）

設(shè)R是一個(gè)X到Y(jié)的關(guān)系，S是一個(gè)Y到Z的關(guān)系,則R與S的合成關(guān)系(或復(fù)合關(guān)系):R

S

為：R

S

={<x,y>|

z(xSz∧zRy}

例4.18

設(shè)X={x1,x2,x3},Y={y1,y2,y3},Z={z1,z2,z3}

從X到Z的關(guān)系S={<x1,z1>,<x1,z2>,<x2,z2>}從Z到Y(jié)的關(guān)系R={<z1,y2>,<z2,y3>,<z3,y3>}則X到Z的關(guān)系R

S={<x1,y2>,<x1,y3>,<x2,y3>}XZYXYRSR

S

x1x2x3z1z2z3y1y2y3x1x2x3y1y3y2例4.19：設(shè)A={2,3}

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

則R-1,R

G，G

R，R『A,R『φ,R[A],R[φ]分別是

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

G={<2,2>,<2,3>}G

R={<1,1>,<1,4>,<3,1>}R『A={<x,y>|xRyxA}={

<3,2>}R『φ=φR[A]=ran(R『A)={2}R[φ]=φ注意：逆運(yùn)算的優(yōu)先級(jí)高于其他運(yùn)算，而所有的關(guān)系運(yùn)算都優(yōu)于集合運(yùn)算。例4.20設(shè)有集合A={4,5,8,15},B={3,4,5,9,11}C={1,6,8,13},F是由A到B的關(guān)系,G是由B到C的關(guān)系,分別定義為

F={<a,b>||b-a|=1}G={<b,c>||b-c|=2或|b-c|=4}求合成關(guān)系G

F和F

G

解先求G

F,由題意知F={<4,3>,<4,5>,<5,4>,<8,9>}G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}G

F={<4,1>,<5,6>,<5,8>,<8,13>}

例4.20(續(xù))設(shè)有集合A={4,5,8,15},B={3,4,5,9,11}C={1,6,8,13},F是由A到B的關(guān)系,G是由B到C的關(guān)系,分別定義為

F={<a,b>||b-a|=1}G={<b,c>||b-c|=2或|b-c|=4}求合成關(guān)系G

F和F

G

解再求F

G,由題意知G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}F={<4,3>,<4,5>,<5,4>,<8,9>}F

G={<4,9>}例4.21：設(shè)F={<a,{a}>,<{a},{a,{a}}>}

求F

F，F(xiàn)『{a}，F(xiàn)『[{a}]解因?yàn)镕={<a,{a}>,<{a},{a,{a}}>}

F={<a,{a}>,<{a},{a,{a}}>}

所以F

F={<a,{a,{a}}>}

由公式F『A={<x,y>|xFy

∧x∈A)}有F『{a}={<a,{a}>}

由公式F[A]=ran(F『A)有F『[{a}]=ran(F『{a})=ran{<a,{a}>}={{a}}定義域值域定理4.1

設(shè)F、G、H是任意關(guān)系,則(1)(F-1)-1=F(2)dom(F-1)=ranF,ranF-1=domF

(3)(F

G)

H=F

(G

H)(4)(F

G)-1=G-1

F-1證明:(1)任取<x,y>,由逆的定義有<x,y>∈(F-1)-1

<y,x>∈F-1

<x,y>∈F∴(F-1)-1=F(2)任取x,x∈ranF-1

y(<y,x>∈F-1)

y(<x,y>∈F)

x∈domF∴ranF-1=domF同理可證dom(F-1)=ranF

(3)(F

G)

H=F

(G

H)(4)(F

G)-1=G-1

F-1證明:(3)任取<x,y>,<x,y>∈(F

G)

H

t(<x,t>∈F

G∧<t,y>∈H)

t

s(<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)(4)任取<x,y>,<x,y>∈(F

G)-1

<y,x>∈F

G

t(<y,t>∈F∧

<t,x>∈G)

t(<x,t>∈G-1

∧

<t,y>∈F-1)

<x,y>∈G-1

F-1

定理4.2

設(shè)F、G、H是任意關(guān)系,則(1)F

(G∪H)=F

G∪F

H(2)(G∪H)

F=G

F∪H

F(3)F

(G∩H)

F

G∩F

H(4)(G∩H)

F

G

F∩H

F證明:(1)任取<x,y>,<x,y>∈F

(G∪H)

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

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

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

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

<x,y>∈F

G∨<x,y>∈F

H

<x,y>∈F

G∪F

H證明:(3)任取<x,y>,<x,y>∈F

(G∩H)

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

t(<x,t>∈F∧

<t,y>∈G∧

<t,y>∈H)

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

<x,y>∈F

G∧

<x,y>∈F

H

<x,y>∈F

G∩F

H本定理對(duì)有限個(gè)關(guān)系的并和交都成立。R

(R1∪R2∪…∪Rn)=R

R1∪R

R2∪…∪R

Rn(R1∪R2∪…∪Rn)

R=R1

R∪R2

R∪…∪Rn

RR

(R1∩

R2∩…∩Rn)

R

R1∩R

R2∩…∩R

Rn(R1∩R2∩…∩Rn)

R

R1

R∩R2

R∩…∩Rn

R定義4.10

設(shè)R是A上的關(guān)系,n為自然數(shù)，則R的n次冪規(guī)定如下(1)R0={<x,x>|x∈A}(2)Rn=Rn-1

Rn≥1

由定義可以知道R0就是A上的恒等關(guān)系IA，不難證明下面的等式

R

R0=R=R0

R由這個(gè)等式立即可以得到R1=R0

R=R例4.22設(shè)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

=R0

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>}R2

=R

R

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

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3

=R2

R

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

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}R4

=R3

R

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

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R5

=R4

R

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

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}定理4.3

設(shè)R是A上的關(guān)系,m,n為自然數(shù)，則下面的等式成立(1)Rm

Rn=Rm+n

(2)(Rm)n=Rmn證明：(1)任給m，對(duì)n作歸納法。

n=0時(shí)，Rm

?R0=Rm

=Rm+0。

假設(shè)Rm

?Rn=Rm+n，那么Rm?Rn+1=Rm?(Rn?R1)=(Rm?Rn)?R1=Rm+n?R1=Rm+n+1=Rm+(n+1)

。(2)任給m，對(duì)n作歸納法。

n=0時(shí)，(Rm)0=R0=Rm

0。

假設(shè)(Rm)n=Rmn。

那么(Rm)n+1=(Rm)n

?

Rm

=Rmn

?Rm=Rmn+m=Rm(n+1)

011001101110M

2

=MM=10001000=0110011001101110000000000000111001101110M

3

=M2M=01101000=1110111001101110000000000000例4.23：設(shè)A={1,2,3,4},R是A上二元關(guān)系，關(guān)系矩陣為0110M

=100001100000解：R，R2,R3

的關(guān)系矩陣分別為：求R3。(M為R的關(guān)系矩陣)設(shè)R是A上的關(guān)系，R的性質(zhì)主要有以下5種(1)若

x(x∈A<x,x>∈R),則稱(chēng)R在A上是自反的。也就是說(shuō)，對(duì)R

A

A，若A中每個(gè)x，都有xRx，則稱(chēng)R是自反的，即

A上關(guān)系R是自反的

x(x

A

xRx)該定義表明了，在自反的關(guān)系R中，除其他有序?qū)ν?，必須包括有全部由每個(gè)x

A所組成的元素相同的有序?qū)纾涸O(shè)A={1,2,3},R

是A上的關(guān)系，

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

則R

是自反的§4.3關(guān)系的性質(zhì)設(shè)R是A上的關(guān)系，R的性質(zhì)主要有以下5種(2)若

x(x∈A<x,x>∈R),則稱(chēng)R在A上是反自反的也就是說(shuō)，對(duì)R

A

A，若A中每個(gè)x，有xRx，則稱(chēng)R是反自反的，即A上關(guān)系R是反自反的

x(x

A

xRx)該定義表明了，一個(gè)反自反的關(guān)系R中，不應(yīng)包括有任何相同元素的有序?qū)?。例如：設(shè)A={1,2,3}，R

是A上的關(guān)系，

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

R是反自反的

§4.3關(guān)系的性質(zhì)應(yīng)該指出，任何一個(gè)不是自反的關(guān)系，未必是反自反的；反之，任何一個(gè)不是反自反的關(guān)系，未必是自反的。這就是說(shuō)，存在既不是自反的也不是反自反的二元關(guān)系。例如：設(shè)A={1,2,3},R

是A上的關(guān)系，R={<1,1>,<2,2>}缺少{<3,3>}則R是既不是自反的，也不是反自反的§4.3關(guān)系的性質(zhì)(3)若

xy(x,y∈A∧<x,y>∈R<y,x>∈R),則稱(chēng)R在A上是對(duì)稱(chēng)的。也就是說(shuō),對(duì)R

A

A,對(duì)A中每個(gè)x和y,若xRy,則yRx,稱(chēng)R是對(duì)稱(chēng)的,即A上關(guān)系R是對(duì)稱(chēng)的(x)(

y)(x,y

A

xRy→yRx)該定義表明了，在表示對(duì)稱(chēng)的關(guān)系R的有序?qū)现?，若有有序?qū)?lt;x,y>，則必定還會(huì)有有序?qū)?lt;y,x>。例如：設(shè)A={1,2,3},R是A上的關(guān)系，

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

則R

是對(duì)稱(chēng)的(4)若

xy(x,y∈A∧<x,y>∈R∧x≠y<y,x>R),

則稱(chēng)R在A上是反對(duì)稱(chēng)的。(隱含x=y<y,x>∈R)也就是說(shuō),對(duì)R

A

A，對(duì)A中每個(gè)x和y，若xRy且yRx，則x=y，稱(chēng)R是反對(duì)稱(chēng)的，即A上關(guān)系R是反對(duì)稱(chēng)的

(

x)(

y)(x,y

A

xRy

yRx→x=y)該定義表明了，在表示反對(duì)稱(chēng)關(guān)系R的有序?qū)现?，若存在有序?qū)?lt;x,y>和<y,x>，則必定是x=y?；蛘哒f(shuō)，在R中若有有序?qū)?lt;x,y>，則除非x=y，否則必定不會(huì)出現(xiàn)<y,x>。例如：設(shè)A={1,2,3},R={<1,2>,<1,3>}

是A上的關(guān)系，則R是反對(duì)稱(chēng)的

判斷一個(gè)關(guān)系是否反對(duì)稱(chēng),通俗地講就是對(duì)于所有的a,b∈A,若a≠b,則序偶<a,b>,<b,a>至多只有一個(gè)出現(xiàn)在關(guān)系R中。如R={<1,2>,<1,1>,<3,1>}

有些關(guān)系既是對(duì)稱(chēng)的又是反對(duì)稱(chēng)的還有的關(guān)系既不是對(duì)稱(chēng)的又不是反對(duì)稱(chēng)的，例如：設(shè)A={1,2,3},R6,R7是A上的關(guān)系，

R6={<1,1>}R7={<1,2>,<2,1>,<1,3>}則R6是對(duì)稱(chēng)的，也是反對(duì)稱(chēng)的R7既不是對(duì)稱(chēng)的又不是反對(duì)稱(chēng)的再如，A={a,c,b>,中R={<a,b>,<a,c>,<c,a>}

既不是對(duì)稱(chēng)的又不是反對(duì)稱(chēng)的。例4.24設(shè)A={1,2,3,4,5},A上的關(guān)系R為

R={<a,b>|a-b是偶數(shù)}①用列舉法表示R

②R是否自反、對(duì)稱(chēng)、反對(duì)稱(chēng)？解:①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3><5,5>}

②∵對(duì)任意a∈A,a-a=0是偶數(shù)∴R是自反關(guān)系又∵對(duì)任意a,b∈A,若a-b是偶數(shù),則b-a也是偶數(shù)∴R是對(duì)稱(chēng)關(guān)系。

∵當(dāng)a≠b時(shí)，有<a,b>和<b,a>

同時(shí)出現(xiàn)在

R中,例如<1,3>,<3,1>,<2,4>,<4,2>,<3,5>,<5,3>

∴R不是反對(duì)稱(chēng)關(guān)系。(5)

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R<x,z>∈R)

則稱(chēng)R在A上是傳遞的關(guān)系。也就是說(shuō),對(duì)R

A

A，對(duì)于A中每個(gè)x,y,z，若xRy且yRz，則xRz，稱(chēng)R是傳遞的，即A上關(guān)系R是傳遞的

(

x)(

y)(

z)(x,y,z

A

xRy

yRz→xRz)該定義表明了，在表示可傳遞關(guān)系R的有序?qū)现?，若有有序?qū)?lt;x,y>和<y,z>，則必有有序?qū)?lt;x,z>。(5)

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R<x,z>∈R)

則稱(chēng)R在A上是傳遞的關(guān)系。例4.25設(shè)A={1,2,3,4,5},A上的關(guān)系R為

R={<a,b>|a-b是偶數(shù)}①用列舉法表示R

②R是否是可傳遞的？解:①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3><5,5>}

②對(duì)于任意的a,b,c∈A

若a-b=2m,b-c=2n,則a-c=(a-b)+(b-c)=2(m+n)

也是偶數(shù)。因此A是可傳遞的。

∵<a,b>∈R∧<b,c>∈R<a,c>∈R例4.26設(shè)A={1,2,3,4,5,6,7,8,9,10}R是A上的關(guān)系，

R={<x,y>|x,y∈A∧x+y=10}

說(shuō)明R具有哪些性質(zhì)。解：

R={<1,9>,<2,8>,<3,7>,<4,6>,<5,5>

,<9,1>,<8,2>,<7,3>,<6,4>}易知R既不是自反也不是反自反的

R是對(duì)稱(chēng)的

R不是反對(duì)稱(chēng)的

R不是傳遞的?！?.3關(guān)系的性質(zhì)P1P3P4P2這個(gè)關(guān)系如右圖所示。我們知道，調(diào)用關(guān)系是傳遞的，如P1能調(diào)用P2，P2能調(diào)用P4，則P1亦能調(diào)用P4。我們希望在R的基礎(chǔ)上建立一個(gè)滿(mǎn)足傳遞性的新關(guān)系，譬如說(shuō)，下面的關(guān)系R′即是這樣一個(gè)關(guān)系§4.4關(guān)系的閉包什么叫一個(gè)關(guān)系上的閉包呢？設(shè)有四個(gè)程序所組成的集合P={P1,P2,P3,P4}上的“調(diào)用”關(guān)系R：R={<P1,P2>,<P2,P4>,<P1,P3>,<P3,P4>}R′={<P1,P2>,<P2,P4>,<P1,P3>,<P3,P4>,<P1,P4>}當(dāng)然滿(mǎn)足這個(gè)條件的關(guān)系不僅僅R′一個(gè)，如下面的關(guān)系R″亦是R″={<P1,P2>,<P2,P4>,<P1,P3>,<P3,P4>,<P1,P4>,<P2,P2>}我們選用滿(mǎn)足這個(gè)條件的最小者，在這個(gè)例子中即為R′。這個(gè)R′我們就叫做R上的傳遞閉包。R′是一個(gè)新關(guān)系，它是在集合P上的一個(gè)新的調(diào)用關(guān)系顯然有R

R'R'

R''

選用滿(mǎn)足這個(gè)條件的最小者R',這個(gè)新關(guān)系叫做R上的傳遞閉包，它是在集合P上的一個(gè)新的調(diào)用關(guān)系。

對(duì)于關(guān)系的自反性、對(duì)稱(chēng)性、傳遞性均可建立閉包。定義4.11設(shè)R是非空集合A上的關(guān)系，R的自反(對(duì)稱(chēng)或傳遞)閉包是A上的關(guān)系R′,使得R′滿(mǎn)足以下條件:(1)R′是自反(對(duì)稱(chēng)或傳遞)的(2)RR′

(3)對(duì)A上的任何包含R的自反(對(duì)稱(chēng)或傳遞)關(guān)系R″有R′R″

一般將R的自反閉包記作r(R),對(duì)稱(chēng)閉包記作s(R)，傳遞閉包記作t(R)。§4.4關(guān)系的閉包定理4.4

設(shè)R是非空集合A上的關(guān)系，則有(1)r(R)=R∪R0(2)s(R)=R∪R-1(3)t(R)=R∪R2∪R3∪…

此定理提供了一種集合表示形式下關(guān)系閉包的求解方法§4.4關(guān)系的閉包例4.27設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},則r(R)=R∪R0={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,c>,<d,d>,<b,b>,<a,a>}s(R)=R∪R-1={<a,b>,<b,a>,<b,c>,

<c,d>,<d,b>}

∪{<b,a>,<a,b>,<c,b>,

<d,c>,<b,d>}={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,b>,<d,c>,<b,d>}t(R)=R∪R2∪R3∪…(甚不方便)當(dāng)關(guān)系用關(guān)系矩陣表示時(shí)，相應(yīng)閉包求法為：

(1)Mr=M+E(2)Ms=M+M′(3)Mt=M+M2+M3+…其中M為R的關(guān)系矩陣，E是單位矩陣，M`是M的轉(zhuǎn)置矩陣.§4.4關(guān)系的閉包010010001100Mr=M+E=1010+0100=1110000100100011010000010101010001000100Ms=M+M′=1010+1001=10110001010001010100001001101111Mt=M+M2+M3+…=111111111111例4.28

設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},則§4.4關(guān)系的閉包E表示同階單位陣；M'表示M的轉(zhuǎn)置矩陣

abcdabcd請(qǐng)編程實(shí)現(xiàn)Warshall算法:一種求Mt的算法：(矩陣+轉(zhuǎn)置矩陣)設(shè)R為n元集上的關(guān)系，M是R的關(guān)系矩陣，則(1)置新矩陣N=M;(2)置I=1;(3)對(duì)j(1≤j≤n),若N的第j行第i列處為1，則對(duì)k=1,2,…,n做如下計(jì)算：將N的第j行k列處元素與第i行k列處元素進(jìn)行邏輯加，然后將結(jié)果放到第j行k列處，即

N[j,k]=N[j,k]+N[i,k];(4)i=i+1;(5)若i≤n,go(3),否則停止。最終得到的矩陣N就是Mt。作業(yè)：請(qǐng)用C語(yǔ)言編寫(xiě)相應(yīng)的程序段。#defineN3main(){inta[N][N]={{1,0,0},{0,1,0},{0,1,1}};

inti,j,k,s;

for(I=0;I<N;i++)for(j=0;j<N;j++)if(a[j][I])

for(k=0;k<N;k++) {a[j][k]+=a[I][k];if(a[j][k]>1)a[j][k]=1;}}當(dāng)關(guān)系用關(guān)系圖表示時(shí)，相應(yīng)閉包求法為:設(shè)R,r(R),s(R),t(R)的關(guān)系圖分別為G,Gr,Gs,Gt,則Gr,Gs,Gt與G的頂點(diǎn)集相等,除了G的邊以外依據(jù)下列方法添加新的邊:(1)考察G的每個(gè)頂點(diǎn),如果沒(méi)有環(huán)就加上一個(gè)環(huán),最終得到的是Gr。(2)考察G的每一條邊，如果有一條xi到xj的單向邊，i≠j，則在G中加一條xj到xi的反方向邊，最終得到Gs

。(3)考察G的每個(gè)頂點(diǎn)xi,找出從xi出發(fā)的所有2步,3步,…,n步長(zhǎng)的路徑(n為G中的頂點(diǎn)數(shù)).設(shè)路徑的終點(diǎn)為xj1,xj2,…,xjk，如果沒(méi)有從xi到xjl

(i=1,2,…,k)的邊，就加上這條邊，最終得到Gt。例題參見(jiàn)P93例4.10§4.5等價(jià)關(guān)系和偏序關(guān)系定義4.12

設(shè)R是非空集合A上的關(guān)系。若R是自反的、對(duì)稱(chēng)的和傳遞的,則稱(chēng)R是A上的等價(jià)關(guān)系如果R是一個(gè)等價(jià)關(guān)系，若<x,y>∈R,稱(chēng)x等價(jià)于y,記作x~y。

等價(jià)關(guān)系=自反性+對(duì)稱(chēng)性+傳遞性也就是說(shuō),若<a,b>

R,或aRb,稱(chēng)a等價(jià)b,記a

b

由于R是對(duì)稱(chēng)的，a等價(jià)b即b等價(jià)a，反之亦然，a與b彼此等價(jià)。.例4.29

設(shè)有一個(gè)整數(shù)集Z

上的關(guān)系R：R={<x,y>|x-y可被3整除}

求證這個(gè)關(guān)系是等價(jià)關(guān)系