元關(guān)系和函數(shù)離散數(shù)學(xué)離散數(shù)學(xué)(第四版)清華出版社

第四章二元關(guān)系和函數(shù)笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性質(zhì)1234567關(guān)系的閉包等價(jià)關(guān)系和偏序關(guān)系函數(shù)的定義和性質(zhì)函數(shù)的復(fù)合和反函數(shù)第四章二元關(guān)系和函數(shù)笛卡爾積與二元關(guān)系關(guān)系的運(yùn)算關(guān)系的性

設(shè)n為一正整數(shù)，由n個(gè)元素x1,x2,…,xn按一定順序排列成的一個(gè)序列<x1,x2,…,xn>稱為有序n元組。(Theorderedn-tuple<x1,x2,…,xn>istheorderedcollectionthathasx1asitsfirstelement,x2asitssecondelement,…,andxnasitsnthelement.)DEFINITION1.笛卡爾積與二元關(guān)系1二元關(guān)系和函數(shù)2設(shè)n為一正整數(shù)，由n個(gè)元素x1,x2,…,xn按一定

設(shè)A,B為集合，用A中元素為第一元素，B中元素為第二元素，構(gòu)成有序?qū)?，所有這樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記做A×B.(LetAandBbesets.TheCartesianproductofAandB,denotedbyA×B,isthesetofallorderedpairs<x,y>wherex∈Aandy∈B.Hence,A×B={<x,y>∣x∈A∧y∈B}.)DEFINITION2.笛卡爾積與二元關(guān)系3設(shè)A,B為集合，用A中元素為第一元素，B中元素為第二

設(shè)集合A={1,2}，B={a,b,c}，求A與B的笛卡爾積。A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}.EXAMPLE1

若A中有m個(gè)元素，B中有n個(gè)元素，則A×B中有mn個(gè)元素。笛卡爾積與二元關(guān)系4設(shè)集合A={1,2}，B={a,b,c設(shè)集合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>}.EXAMPLE2笛卡爾積與二元關(guān)系5設(shè)集合A={1,2}，求P(A)×A.P(A)×A=

設(shè)A1,A2,…,An是集合(n

2)，它們的n階笛卡爾積記作A1×A2×…×An，其中，A1×A2×…×An={<x1,x2,…,xn>∣xi∈Ai,i=1,2,…,n}.(TheCartesianproductofthesetsA1,A2,…,An,denotedbyA1×A2×…×An,isthesetoforderedn-tuples<x1,x2,…,xn>,wherexibelongstoAifori=1,2,…,n.)DEFINITION3.笛卡爾積與二元關(guān)系6設(shè)A1,A2,…,An是集合(n2)，它

設(shè)集合A={0,1},B={1,2},C={0,1,2}，求A,B和C的笛卡爾積A×B×C。A×B×C={<0,1,0>,<0,1,1>,<0,1,2>,<0,2,0>,<0,2,1>,<0,2,2>,<1,1,0>,<1,1,1>,<1,1,2>,<1,2,0>,<1,2,1>,<1,2,2>}.EXAMPLE3笛卡爾積與二元關(guān)系7設(shè)集合A={0,1},B={1,2},C={笛卡爾積運(yùn)算的性質(zhì)：1、若A,B中有一個(gè)空集，則它們的笛卡爾積是空集，即：?×B=A×?=?.2、當(dāng)A

B且A,B都不是空集時(shí)，有A×B

B×A.3、當(dāng)A,B,C都不是空集時(shí)，有(A×B)×CA×(B×C).笛卡爾積與二元關(guān)系8笛卡爾積運(yùn)算的性質(zhì)：笛卡爾積與二元關(guān)系8笛卡爾積運(yùn)算的性質(zhì)：4、笛卡爾積運(yùn)算對∪或∩運(yù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).笛卡爾積與二元關(guān)系9笛卡爾積運(yùn)算的性質(zhì)：笛卡爾積與二元關(guān)系9證明等式：(B∪C)×A=(B×A)∪(C×A).證明：對于任意的<x,y>,<x,y>

(B∪C)×AxB∪CyA(x

BxC)

yA(xByA)(xC

yA)<x,y>

B×A<x,y>

C×A

<x,y>(B×A)∪(C×A)

(B∪C)×A=(B×A)∪(C×A)笛卡爾積與二元關(guān)系10證明等式：(B∪C)×A=(B×A)∪(C×A).證明：對注意：二元關(guān)系是指滿足某規(guī)律的有序?qū)Φ娜w。二元關(guān)系——按照某種規(guī)定，定義了一個(gè)有序?qū)?lt;x,y>的集合R，其中x∈A，y∈B，稱R為從Ａ到B的二元關(guān)系。DEFINITION4.當(dāng)A=B時(shí)，R是A到A的二元關(guān)系，稱為A上的二元關(guān)系。DEFINITION5.

對于二元關(guān)系R，若<x,y>∈R，則記作xRy，若<x,y>∈R，則記作xRy。例：R={<x,y>|x/y,x,y∈N}是自然數(shù)集Ｎ上的二元關(guān)系。笛卡爾積與二元關(guān)系11注意：二元關(guān)系是指滿足某規(guī)律的有序?qū)Φ娜w。二元關(guān)系——按照例如：

A={張三，李四，王五，趙六}B={100米，跳高，鉛球，足球，跨欄}窮舉法表示：

R={<張三，鉛球>，<張三，足球>，<李四，100米>，

<李四，跳高>，<王五，跨欄>，<趙六，100米>}是運(yùn)動會的報(bào)名表。二元關(guān)系的表示：因?yàn)槎P(guān)系本身也是集合，也可用窮舉法，描述法來表示，還可用表格、圖示、矩陣法表示。DEFINITION6.笛卡爾積與二元關(guān)系12例如：二元關(guān)系的表示：因?yàn)槎P(guān)系本身也是集合，也可用窮舉

用字母數(shù)字來代替這些元素

A＝{a，b，c，d}

B＝{1，2，3，4，5}表格表示法：用表格表示一目了然笛卡爾積與二元關(guān)系13用字母數(shù)字來代替這些元素表格表示法：用表格表示一目了然笛卡圖示法：關(guān)系圖，直觀笛卡爾積與二元關(guān)系14圖示法：關(guān)系圖，直觀笛卡爾積與二元關(guān)系14相關(guān)矩陣法表示：把A,B集合內(nèi)元素排好序12345笛卡爾積與二元關(guān)系15相關(guān)矩陣法表示：把A,B集合內(nèi)元素排好序123二元關(guān)系是笛卡爾A×B的子集。若R=A×B，則相關(guān)矩陣元素全為1。笛卡爾積與二元關(guān)系16二元關(guān)系是笛卡爾A×B的子集。笛卡爾積與二元關(guān)系16注：（1）若R＝A×B，稱此二元關(guān)系為全域關(guān)系；（2）設(shè)A＝｛x1，x2，…，xn｝

R＝｛<xi，xj>｜xi，xj∈A｝若R＝｛<xi，xi>｜xi∈A｝稱R為恒等關(guān)系，用IA表示，是單位矩陣。笛卡爾積與二元關(guān)系17注：（1）若R＝A×B，稱此二元關(guān)系為全域關(guān)系；笛卡爾積與二關(guān)系R的定義域domR，值域ranR和域fldR分別是：

domR={x|y(<x,y>∈R)}.ranR={y|x(<x,y>∈R)}.fldR=domR∪ranR.當(dāng)定義域與值域交換得

R-1={<x,y>|yRx}，稱為R的逆關(guān)系。DEFINITION7.二元關(guān)系和函數(shù)關(guān)系的運(yùn)算218關(guān)系R的定義域domR，值域ranR和域fldR分別是：DE

二元關(guān)系是集合，集合存在并、交、差、非和對稱差的運(yùn)算，故二元關(guān)系也存在這樣的運(yùn)算。設(shè)R1和R2是A到B的二元關(guān)系，則：（1）R1∪R2＝{<x,y>｜<x,y>∈R1∨<x,y>∈R2}（2）R1∩R2＝{<x,y>｜<x,y>∈R1∧<x,y>∈R2}（3）R1-R2＝{<x,y>｜<x,y>∈R1∧<x,y>

R2}

（5）R1

R2＝{<x,y>｜<x,y>∈R1∪R2∧<x,y>

R1∩R2}關(guān)系的運(yùn)算∧19二元關(guān)系是集合，集合存在并、交、差、非和對稱差的運(yùn)算，故例1：A＝{1，2，3，4}，I為整數(shù)集，解：R與S都是A上的二元關(guān)系

R={<1,1>,<2,2>,<3,3>,<4,4>,<1,3>,<3,1>,<2,4>,<4,2>}S={<4,1>}關(guān)系的運(yùn)算20例1：A＝{1，2，3，4}，I為整數(shù)集，解：R與S都是A上R∪S={<1,1>,<2,2>,<3,3>,<4,4>,<1,3>,<3,1>,<2,4>,<4,2>,<4,1>}R∩S=?關(guān)系的運(yùn)算21R∪S={<1,1>,<2,2>,<3,3>,<4,4>,<例2：

R是父子關(guān)系，則R２=R?R是祖孫關(guān)系。設(shè)F,G為任意的關(guān)系，A為集合，F(xiàn)與G的復(fù)合關(guān)系（合成）記作F?G，F(xiàn)?G={<x,y>|z(xGz∧zFy)}DEFINITION8.關(guān)系的運(yùn)算22例2：設(shè)F,G為任意的關(guān)系，A為集合，F(xiàn)與G的復(fù)合關(guān)系（合則：R1={<b1,c3>,<b1,c4>,<b2,c2>,<b2,c3>,<b2,c4>,<b3,c1>,<b3,c2>,<b4,c2>,<b4,c4>}是各專業(yè)本學(xué)期必修課的二元關(guān)系。關(guān)系的運(yùn)算23則：R1={<b1,c3>,<b1,c4>,<b2,c2>,R3=R1?R2={<a1,c1>,<a1,c2>,<a1,c3>,<a1,c4>,<a2,c2>,<a2,c3>,<a2,c4>,<a3,c1>,<a3,c2>,<a3,c4>,<a4,c2>,<a4,c3>,<a4,c4>}是選雙學(xué)位學(xué)生本學(xué)期必修課的二元關(guān)系。R2={<a1,b1>,<a1,b3>,<a2,ｂ2>,<a2,b4>,<a3,b3>，

<a3,b4>,<a4,b1>,<a4,b4>}是學(xué)生選雙學(xué)位專業(yè)的二元關(guān)系。關(guān)系的運(yùn)算24R3=R1?R2R2={<a1,b1>,<a1,b3>普通的矩陣乘法：二元關(guān)系的復(fù)合的布爾型矩陣乘法：關(guān)系的運(yùn)算25普通的矩陣乘法：二元關(guān)系的復(fù)合的布爾型矩陣乘法：關(guān)系的運(yùn)算2

在行處標(biāo)上姓名，列處標(biāo)上課程，就知誰該必修哪些課了。關(guān)系的運(yùn)算26在行處標(biāo)上姓名，列處標(biāo)上課程，就知誰該必修哪些課了。關(guān)系設(shè)R為A上的二元關(guān)系，n為自然數(shù)，則R的n次冪規(guī)定如下：(1)R0={<x,x>｜x∈A}；(2)Rn=Rn-1?R,n1.DEFINITION8.關(guān)系的運(yùn)算27設(shè)R為A上的二元關(guān)系，n為自然數(shù)，則R的n次冪規(guī)定如下：DE例4：

R={<0,0>,<0,3>,<2,3>,<3,2>,<2,1>,<2,0>}是集合{0,1,2,3}上的二元關(guān)系，R的關(guān)系圖如下：關(guān)系的運(yùn)算28例4：關(guān)系的運(yùn)算28R2={<0,0>,<0,2>,<0,3>,<2,0>,<2,2>,<2,3>,<3,0>,<3,1>,<3,3>}關(guān)系的運(yùn)算29R2={<0,0>,<0,2>,<0,3>,<2,0>,<2Rn的關(guān)系圖的構(gòu)造：可由R的關(guān)系圖來構(gòu)造，從R的每個(gè)結(jié)點(diǎn)xi出發(fā)，數(shù)n條邊。若通過數(shù)n條邊能到達(dá)結(jié)點(diǎn)xj，則有<xi,xj>∈Rn。關(guān)系圖中從xi出發(fā)到xj的邊是存在的。這樣處理容易出錯(cuò)，用相關(guān)矩陣的布爾型乘法來做，簡單，又不容易錯(cuò)，還適宜于計(jì)算機(jī)處理。關(guān)系的運(yùn)算30Rn的關(guān)系圖的構(gòu)造：關(guān)系的運(yùn)算30關(guān)系的運(yùn)算31關(guān)系的運(yùn)算31定理：設(shè)F,G,H是任意的二元關(guān)系，則：

(F-1)-1=F；(2)domF-1=ranF,ranF-1=domF；(3)(F?G)?H=F?(G?H)；(4)(F?G)-1=G-1

?F-1；(5)F?(G∪H)=(F?G)∪(F?H)；(6)F?(G∩H)

(F?G)∩(F?H)；(7)(G∪H)?F=(G?F)∪(H?F)；(8)(G∩H)?F

(G?F)∩(H?F).關(guān)系的運(yùn)算32定理：設(shè)F,G,H是任意的二元關(guān)系，則：關(guān)系的運(yùn)算32證明：(4)任取<x,y>，<x,y>

(F?G)-1<y,x>

F?Gz(<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-1

?F-1

(F?G)-1

=G-1

?F-1關(guān)系的運(yùn)算33證明：(4)任取<x,y>，關(guān)系的運(yùn)算33證明：(7)任取<x,y>，<x,y>

(G∪H)?Fz(<x,z>F

<z,y>G∪H)z(<x,z>F

(<z,y>G<z,y>H)z((<x,z>F<z,y>G)(<x,z>F<z,y>H))<x,y>

G?F<x,y>H?F<x,y>(G?F)∪(H?F)

(G∪H)?F=(G?F)∪(H?F)關(guān)系的運(yùn)算34證明：(7)任取<x,y>，關(guān)系的運(yùn)算34設(shè)R是A上的二元關(guān)系，R=(rij)n*n(1)自反性：對

x∈A，<x,x>∈R，則R稱為自反的二元關(guān)系。顯然，rii=1(i=1,2,…,n)

反自反性：對

x∈A，<x,x>

R，則R稱為反自反的二元關(guān)系。即rii=0(i=1,2,…,n)注：

自反和反自反性互斥，但不互補(bǔ)。如：rii中既有0又有1，則R既不是自反的也不是反自反的。二元關(guān)系和函數(shù)關(guān)系的性質(zhì)335設(shè)R是A上的二元關(guān)系，R=(rij)n*n注：二元關(guān)系和函數(shù)(2)對稱性：若x≠y,<x,y>∈R,必有<y,x>∈R，稱R為對稱的二元關(guān)系。即R的相關(guān)矩陣為對稱陣，rij=rji.

反對稱性：若x≠y，<x,y>∈R,則<y,x>

R，稱R為反對稱的二元關(guān)系。注：(1)R的相關(guān)矩陣是反對稱的，即：rij∧rji=0(i≠j)(2)若rij=1，則rji=0；但rij=0時(shí)，不要求rji=1，即rij=rji=0是允許的。(3)對稱性與反對稱性既不互斥，又不互補(bǔ)。關(guān)系的性質(zhì)36(2)對稱性：反對稱性：注：關(guān)系的性質(zhì)36關(guān)系的性質(zhì)37關(guān)系的性質(zhì)37注：若rij，rjk中有一個(gè)不是１，則?(rij∧rjk)=1，

rik就可以任意。

即：若<x,y>,<y,z>中有一個(gè)不屬于R，則討論<x,z>是否屬于R，無意義。也就是說，沒有傳遞的條件，也不需傳遞的結(jié)果。如：A={a,b,c,d｝，R={<a,b>,<c,d>}(3)傳遞性：若<x,y>，<y,z>∈R，則<x,z>∈R，稱R為傳遞的二元關(guān)系。即：?(rij∧rjk)∨rik=1關(guān)系的性質(zhì)38注：若rij，rjk中有一個(gè)不是１，即：若<x,y>,<二元關(guān)系的性質(zhì)對應(yīng)于關(guān)系圖，有：(1)自反性：每個(gè)頂點(diǎn)都有環(huán)；(2)反自反性：每個(gè)頂點(diǎn)都沒有環(huán)；(3)對稱性：任意兩個(gè)頂點(diǎn)間或沒有邊，或有兩條方向相反的邊；(4)反對稱性：任意兩個(gè)頂點(diǎn)間至多只有一條有向邊；(5)傳遞性：若xi到xj有邊，xj到xk有邊，則xi到xk必有邊。關(guān)系的性質(zhì)39二元關(guān)系的性質(zhì)對應(yīng)于關(guān)系圖，有：關(guān)系的性質(zhì)39錯(cuò)誤結(jié)論：由對稱性與傳遞性可推出自反性。理由：若<x,y>∈R，由對稱性，有<y,x>∈R，由傳遞性，有<x,x>∈R。如：若R的相關(guān)矩陣是全0矩陣，是對稱的，傳遞的，反自反的，但不是自反的。錯(cuò)誤原因：不是

x，

y，使<x,y>∈R。關(guān)系的性質(zhì)40錯(cuò)誤結(jié)論：由對稱性與傳遞性可推出自反性。如：錯(cuò)誤原因：不是例１：R1={<x,y>｜x≤y，x,y∈N}

自反的，rii=1；不是對稱的，<1,2>∈R1，而<2,1>

R1；反對稱的，傳遞的。注：將≤改為＜，則無自反性，且是反自反的。例2：R2={<x,y>｜x|y，x,y∈N}

自反的，不是對稱的，反對稱的，傳遞的。例3：R3={<S1,S2>｜S1

S2，S1,S2∈P(S)}其中P(S)是S的冪集。自反的，不是對稱的，反對稱的，傳遞的。注：若改為，則無自反性。關(guān)系的性質(zhì)41例１：R1={<x,y>｜x≤y，x,y∈N}例2：R2=例4：R4={<x,y>｜x+y=偶數(shù)，x,y∈N}

自反的，對稱的，傳遞的。因?yàn)?，若x+y=偶數(shù)，y+z=偶數(shù)，則：0＜x+z=(x+y)+(y+z)-2y=偶數(shù)與偶數(shù)之差=偶數(shù)。例5：R5={<x，y>｜x與y互為素?cái)?shù)，x,y∈N}

對稱的，但不是自反的，也無傳遞性。（1）素?cái)?shù)：素?cái)?shù)是一個(gè)比1大，其因子只有1和它本身，沒有其它數(shù)可以整除它的數(shù)。素?cái)?shù)是無限的。例如：2，3，5，7……。（2）兩個(gè)數(shù)互為素?cái)?shù)：指的是它們除了1之外沒有共同的因子。也可以說這兩個(gè)數(shù)的最大公因子是1。例如，4和9，13和27等。關(guān)系的性質(zhì)42例4：R4={<x,y>｜x+y=偶數(shù)，x,y∈N}例5：R[定理1]：設(shè)R是A上的二元關(guān)系，則R∪IA一定是自反的，而且是包含R，具有自反性的最小關(guān)系。（其中IA是A上的恒等關(guān)系）。[定義1]：稱R∪IA是R的自反閉包，記為r(R)。證明：對

x∈A，<x,x>∈IA

R∪IA，且R

R∪IA。若R’包含R且具有自反性，則IA

R’，R

R’，IA∪R

R’。即IA∪R為最小。[推論1]：當(dāng)且僅當(dāng)R是自反閉包，R具有自反性。證明：

(1)R是自反閉包，R=IA∪R

IA

R；

(2)R具有自反性，IA

R，R∪IA=R.二元關(guān)系和函數(shù)4關(guān)系的閉包43[定理1]：設(shè)R是A上的二元關(guān)系，則R∪IA一定是自反的，而[定理2]：設(shè)R是A上的二元關(guān)系，則R∪R-1是對稱的，包含R的最小關(guān)系。（其中R-1是R的逆關(guān)系）。[定義2]：稱R∪R-1是R的對稱閉包，記為s(R)。

證明：(1)若<x,y>∈R∪R-1，則

<x,y>∈R或<x,y>∈R-1，

<y,x>∈R-1或<y,x>∈R

故<y,x>∈R∪R-1（對稱性）。

(2)若R’為包含R，且對稱的二元關(guān)系，則對

<x,y>∈R∪R-1，

<x,y>∈R

<x,y>∈R’；

<x,y>∈R-1

<y,x>∈R

<y,x>∈R’

又R’具有對稱性，<x,y>∈R’，故R∪R-1

R’。關(guān)系的閉包44[定理2]：設(shè)R是A上的二元關(guān)系，則R∪R-1是對稱的，包含[推論2]：當(dāng)且僅當(dāng)R是對稱閉包時(shí)，R具有對稱性。證明：(1)R具有對稱性，若<x,y>∈R，則<y,x>∈R，又<y,x>∈R-1

即

<y,x>∈R-1，<x,y>∈R

<y,x>∈R

R-1

R

R∪R-1＝R；(2)R是對稱閉包時(shí)，R＝R∪R-1

R具有對稱性。關(guān)系的閉包45[推論2]：當(dāng)且僅當(dāng)R是對稱閉包時(shí)，R具有對稱性。關(guān)系的閉包[定理3]：傳遞閉包t(R)＝R∪R2∪R3∪…例6：設(shè)A={1,2,3}，R={<1,1>,<1,2>,<2,3>}，求t(R)

。關(guān)系的閉包46[定理3]：傳遞閉包t(R)＝R∪R2∪R3∪…例6：關(guān)系的[定義1]等價(jià)關(guān)系：

A上的二元關(guān)系R，如果R是

(1)自反的

(2)對稱的

(3)傳遞的稱R為等價(jià)關(guān)系。若<x，y>∈R，稱x與y等價(jià)，記作x～y。二元關(guān)系和函數(shù)5等價(jià)關(guān)系和偏序關(guān)系47[定義1]等價(jià)關(guān)系：二元關(guān)系和函數(shù)5等價(jià)關(guān)系和偏序[定義2]

等價(jià)類：把Ａ中的等價(jià)元素歸為一類，稱為等價(jià)類。注：等價(jià)關(guān)系R把Ａ的元素分為若干類，各類之間沒有公共元素。確定的R是對集合Ａ進(jìn)行的劃分。[定義3]集合的劃分：把集合A分為若干子集A1,A2,…,滿足：

(1)當(dāng)i≠j時(shí)，Ai∩Aj＝

(2)

x∈A，

i，使x∈Ai(i＝１，２，…)，則集合

={A1，A2，…，An，…}稱為Ａ的一個(gè)劃分。等價(jià)關(guān)系和偏序關(guān)系48[定義2]等價(jià)類：把Ａ中的等價(jià)元素歸為一類，稱為等價(jià)類。[[定理1]：

A在等價(jià)關(guān)系R下的等價(jià)類正是A的一種劃分，A的任一種劃分，也必有A上的一個(gè)等價(jià)關(guān)系R與之對應(yīng)。注：

P(A)（A的冪集）；當(dāng)且僅當(dāng)A=，=P(A)={}；

A非空時(shí)，P(A).等價(jià)關(guān)系和偏序關(guān)系49[定理1]：注：等價(jià)關(guān)系和偏序關(guān)系49證明：

R是等價(jià)關(guān)系，

x∈A，由R的自反性，<x,x>∈R，即x與x屬于同一等價(jià)類，即

i，x∈Ai.

若i≠j，Ai≠Aj，而Ai∩Aj≠

。則

z∈Ai∩Aj，z∈Ai，且z∈Aj,

對x∈Ai，x～z，z∈Aj

對

y∈Aj，y～z，即z～y(對稱性)

由Ｒ傳遞性，x～y.

由x，y的任意性，故Ai＝Aj

與Ai和Aj為不同的等價(jià)類矛盾。故Ai∩Aj=

所以，R完成了等價(jià)類的劃分。等價(jià)關(guān)系和偏序關(guān)系50證明：等價(jià)關(guān)系和偏序關(guān)系50

若A已進(jìn)行了劃分，則構(gòu)造二元關(guān)系R。(1)

x∈A，使<x，x>∈R.(2)分別對每一等價(jià)類內(nèi)所有兩個(gè)不同元素x，y，<x，y>∈R，使<y，x>∈R.

顯然，R是自反的，對稱的，而且也是傳遞的，因?yàn)槿?lt;x，y>∈R，<y，z>∈R，則x，y，z均在同一等價(jià)類內(nèi)，故<x，z>∈R。等價(jià)關(guān)系和偏序關(guān)系51若A已進(jìn)行了劃分，則構(gòu)造二元關(guān)系R。等價(jià)關(guān)系和例1：

A＝｛52張撲克｝

R1＝｛<x，y>｜x與y同花，x，y是撲克｝

R2＝｛<x，y>｜x與y同點(diǎn)，x，y是撲克｝則：R1把Ａ分為四類同花類，

R2把Ａ分為13類同點(diǎn)類。例2：

A＝｛0，1，2，3，4，5｝

R＝｛<0，0>，<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，1>，<2，3>，<3，1>，<3，2>，<4，4>，<4，5>，<5，4>，<5，5>｝等價(jià)關(guān)系和偏序關(guān)系52例1：例2：等價(jià)關(guān)系和偏序關(guān)系52R是等價(jià)關(guān)系，但不直觀，用關(guān)系圖表示。三個(gè)不連通的圖等價(jià)關(guān)系和偏序關(guān)系二元關(guān)系R是自反的，對稱的，傳遞的，且把Ａ分成了三個(gè)等價(jià)類，｛0｝，｛1，2，3｝，｛4，5｝53R是等價(jià)關(guān)系，但不直觀，用關(guān)系圖表示。三個(gè)不連通的圖等價(jià)關(guān)系[定義]商集的元素個(gè)數(shù)（即A在R下的等價(jià)類個(gè)數(shù)）稱為R的秩。[定義]商集：等價(jià)關(guān)系R將A分成若干等價(jià)類，每個(gè)類選個(gè)代表組成新的集合稱為A關(guān)于R的商集，表示為A/R。例：在上例中

A/R＝｛［0］，［1］，［4］｝等價(jià)關(guān)系和偏序關(guān)系54[定義]商集的元素個(gè)數(shù)（即A在R下的等價(jià)類個(gè)數(shù)）稱為R的秩例3：

R＝｛<x，y>｜x≡y（mod３），x，y∈Z｝是整數(shù)集合Z上模3同余的二元關(guān)系，證明R是等價(jià)關(guān)系。證明：(1)x≡x(mod3).自反性(2)若x≡y(mod3)，則y≡x(mod3).對稱性(3)若x≡y(mod3)，y≡z(mod3)，則x≡z(mod3).滿足傳遞性。故R是等價(jià)關(guān)系。商集：Z／R＝｛［0］，［1］，［2］｝其中，［0］＝｛…，-6，-3，0，3，6，…｝［1］＝｛…，-5，-2，1，4，7，…｝［2］＝｛…，-4，-1，2，5，8，…｝等價(jià)關(guān)系和偏序關(guān)系55例3：等價(jià)關(guān)系和偏序關(guān)系55[定義]

偏序關(guān)系：Ｒ是Ａ上的二元關(guān)系，如果Ｒ滿足：

(1)自反的

(2)反對稱的

(3)傳遞的則稱Ｒ是Ａ上偏序關(guān)系，簡稱偏序。記作≤。等價(jià)關(guān)系和偏序關(guān)系56[定義]偏序關(guān)系：等價(jià)關(guān)系和偏序關(guān)系56例：Ａ＝｛１，２，３，４，５，６，７，８，９｝Ｂ＝｛ａ，ｂ，ｃ｝Ｒ1＝｛<x，y>｜x≤y，x，y∈Ａ｝Ｒ2＝｛<x，y>｜x|y，x，y∈Ａ｝Ｒ3＝｛<s1，s2>｜s1

s2，s1，s2∈P(Ｂ)｝記號：Ｒ={<x，y>|x≤Ｒy,x，y∈Ａ｝，其中≤R可為≤，|，。

等價(jià)關(guān)系和偏序關(guān)系57例：記號：等價(jià)關(guān)系和偏序關(guān)系57注：（1）用矩陣表示偏序關(guān)系，不能明顯看到二元關(guān)系的特征。（2）用簡化的關(guān)系圖表示較適合。

簡化的關(guān)系圖：

(1)自反性：每個(gè)頂點(diǎn)都有自回路，省去。

(2)反對稱性：兩個(gè)頂點(diǎn)間只可能有一個(gè)箭頭從左→右，或從下→上的方向，從小到大安置頂點(diǎn)，可省略箭頭。

(3)傳遞性：由于有<x，y>，<y，z>∈R，則<x，z>∈R，故只畫<x，y>，<y，z>對應(yīng)的邊，省略邊<x，z>。等價(jià)關(guān)系和偏序關(guān)系58注：簡化的關(guān)系圖：等價(jià)關(guān)系和偏序關(guān)系58[定義]：Hasse圖

設(shè)≤是A上的一個(gè)偏序關(guān)系，如果x≤y，則將x畫在y下面，且不

z，使x≤z，z≤y，則x，y間用直線連接。并符合簡化的關(guān)系圖的繪制，稱這樣得到的關(guān)系圖為Hasse圖。上例中偏序關(guān)系的Hasse圖如下：等價(jià)關(guān)系和偏序關(guān)系59[定義]：Hasse圖上例中偏序關(guān)系的Hasse圖如下：等價(jià)R1等價(jià)關(guān)系和偏序關(guān)系60R1等價(jià)關(guān)系和偏序關(guān)系60等價(jià)關(guān)系和偏序關(guān)系61等價(jià)關(guān)系和偏序關(guān)系61等價(jià)關(guān)系和偏序關(guān)系62等價(jià)關(guān)系和偏序關(guān)系62[定義]

全序：Ａ上偏序關(guān)系Ｒ，如果

x，y∈Ａ，都有x≤y，或y≤x，則稱Ｒ為Ａ上的全序關(guān)系。注：

(1)全序的含義：Ａ中每兩個(gè)元素均能比大小，即任何兩個(gè)元素都相關(guān)。

(2)偏序則是部分有序。

(3)上例中，Ｒ1是全序，Ｒ2，Ｒ3都是偏序。如：Ｒ2中，｛１，２，６｝，｛１，２，４，８｝，｛１，３，９｝都排成了序，但２與３，５與７，７與９…，在整除的意義上來說無法排出大小來。等價(jià)關(guān)系和偏序關(guān)系63[定義]全序：注：等價(jià)關(guān)系和偏序關(guān)系63[定義]

偏序集：集合Ａ及Ａ上的一個(gè)偏序關(guān)系Ｒ組成的二元組<Ａ，Ｒ>，稱為偏序集，記為<Ａ，≤Ｒ>或<Ａ，≤>。注：同一集合上的兩個(gè)不同的偏序關(guān)系，所構(gòu)成的是兩個(gè)偏序集，如：Ｒ1和Ｒ2都定義在Ａ＝｛１，２，３，４，５，６，７，８，９｝上，但<Ａ，Ｒ1>與<Ａ，Ｒ2>顯然不是一樣的偏序集。等價(jià)關(guān)系和偏序關(guān)系64[定義]偏序集：注：等價(jià)關(guān)系和偏序關(guān)系64[定義]

全序集：偏序集<Ａ，≤Ｒ>中的偏序關(guān)系≤Ｒ是Ａ上的全序，則此<Ａ，≤Ｒ>稱為全序集。<Ａ，Ｒ1>是全序集。顯然，全序集是偏序集的特例。又如：（－∞，＋∞）實(shí)數(shù)全體，在≤下是全序集；<Ｎ，≤>當(dāng)然也是全序集。等價(jià)關(guān)系和偏序關(guān)系65[定義]全序集：<Ａ，Ｒ1>是全序集。顯然[定義]

極大元與極小元：設(shè)<A，≤>是偏序集，B

A，若y∈B，且在B中找不到一個(gè)元素x（x≠y），使y≤x(x≤y)，則稱y為B中的極大元（極小元）。例：<Ｎ，|>是偏序集，

B＝｛２，３，４，５，６，７，８，９｝則B中極大元：８，６，９，５，７極小元：２，３，５，７注：極大元，極小元并不要求唯一，且同一元素，可以既是極大元，又是極小元，如５，７。等價(jià)關(guān)系和偏序關(guān)系66[定義]極大元與極小元：例：<Ｎ，|>是偏序集，等價(jià)關(guān)系注：極大元，極小元必須是子集B中的元素。[定義]

最大元與最小元：設(shè)<A，≤>是偏序集，B

A，若y∈B，

x∈B，x≤y(y≤x)，則稱y為B的最大元（最小元）。例：在上例中，Hasse圖如下所示：等價(jià)關(guān)系和偏序關(guān)系67注：[定義]最大元與最小元：例：在上例中，Hasse圖如下結(jié)論：子集B中是不存在最大元（最小元）的。等價(jià)關(guān)系和偏序關(guān)系68結(jié)論：等價(jià)關(guān)系和偏序關(guān)系68例：A＝｛ａ，ｂ，ｃ｝,

Ｒ3＝｛<s1，s2>｜s1

s2，s1，s2∈P(A)｝，<P(A)，

>是偏序集。設(shè)B＝｛

，｛ａ｝，｛ｂ｝，｛ｃ｝，｛ａ，ｂ｝，｛ａ，ｃ｝，｛ｂ，ｃ｝｝其Hasse圖如下所示：等價(jià)關(guān)系和偏序關(guān)系69例：A＝｛ａ，ｂ，ｃ｝,等價(jià)關(guān)系和偏序關(guān)系69結(jié)論：

B存在最小元

，沒有最大元。注：最大元（最小元）本身應(yīng)屬于子集B，且與B中任一元素都有關(guān)系。等價(jià)關(guān)系和偏序關(guān)系70結(jié)論：等價(jià)關(guān)系和偏序關(guān)系70[定義]

上界與下界：設(shè)<A，≤>是偏序集，B

A，若y∈A，對

x∈B，x≤y(y≤x)稱y為B的上界（下界）。注：

(1)上例中，B無最大元，但存在B的上界｛ａ，ｂ，ｃ｝。

(2)

為B的最小元，也是B的下界。

(3)最大（小）元是B的一個(gè)上（下）界。

(4)上（下）界可以不唯一，也可以不存在。等價(jià)關(guān)系和偏序關(guān)系71[定義]上界與下界：注：等價(jià)關(guān)系和偏序關(guān)系71[定義]

上確界與下確界：設(shè)<A，≤>是偏序集，B

A，若y是B的一個(gè)上界（下界），而對于任意的B的上界（下界）x，都有y≤x（x≤y），則稱y是B的上確界（下確界）。注：上確界：最小上界下確界：最大下界如果存在上（下）確界，則上（下）確界一定是唯一的。等價(jià)關(guān)系和偏序關(guān)系72[定義]上確界與下確界：注：上確界：最小上界等價(jià)關(guān)系和偏序例：

<P(A)，

>中取B’={

，{ｂ}，{ｃ}}，則{ｂ，ｃ}與{ａ，ｂ，ｃ}是B’的上界，{ｂ，ｃ}是B’的上確界。注：存在上（下）界，并不一定存在上（下）確界。等價(jià)關(guān)系和偏序關(guān)系73例：注：等價(jià)關(guān)系和偏序關(guān)系73結(jié)論：(1)ｄ，ｅ是Ａ的上界。

(2)ｄ與ｅ無法比大小，不存在上確界。

(3)Ａ的下界不存在，不存在下確界。例：ｐ＝｛ａ，ｂ，ｃ，ｄ，ｅ｝Ａ＝｛ａ，ｂ，ｃ｝，<ｐ，≤>等價(jià)關(guān)系和偏序關(guān)系74結(jié)論：(1)ｄ，ｅ是Ａ的上界。例：ｐ＝｛ａ，ｂ，ｃ，ｄ，ｅ｝

設(shè)F為二元關(guān)系，若

xdomF都存在唯一的yranF使xFy成立，則稱F為函數(shù)。

設(shè)A,B為集合，若f為函數(shù)，且domf=A，ranfB，則稱f為從A到B的函數(shù)，記作f:A→B.DEFINITION1.二元關(guān)系和函數(shù)6函數(shù)的定義和性質(zhì)75設(shè)F為二元關(guān)系，若xdomF都存在唯一的y

IffisafunctionfromAtoB,wesaythatAisthedomainoffandBisthecodomainoff.Iff(x)=y,wesaythatyistheimageofxandxisapre-imageofy.TherangeoffisthesetofallimagesofelementsofA.Also,iffisafunctionfromAtoB,wesaythatfmapsAtoB.A：定義域/domainoff,x:y的原象/pre-image,B：陪域/codomainoff,y:x的象/image,f(A)：值域/rangeoff.DEFINITION2.函數(shù)的定義和性質(zhì)76Iffisafunctionfrom

設(shè)f:A

B,A’

A,則A’在f下的象是F(A’)={f(x)|x

A’}.當(dāng)A’=A時(shí)，稱f(A’)=f(A)=ranf是函數(shù)的象。(LetfbeafunctionfromthesetAtothesetBandletA’beasubsetofA.TheimageofA’isthesubsetofBthatconsistsoftheimagesoftheelementsofA’.)A的子集A’的象DEFINITION3.函數(shù)的定義和性質(zhì)77設(shè)f:AB,A’A,則A’在f下的象是

設(shè)A,B為集合，所有從A到B的函數(shù)構(gòu)成集合BA，讀做“B上A”，即BA

={f|f:A→B}.

一般的，若|A|=m,|B|=n,m,n不全是0，則|BA|=nm。DEFINITION4.

如，A={0,1,2},B={a,b}，BA={f1,f2,f3,f4,f5,f6,f7,f8}.函數(shù)的定義和性質(zhì)78設(shè)A,B為集合，所有從A到B的函數(shù)構(gòu)成集合BA，

設(shè)函數(shù)f:A

B，若ranf=B，則稱f是滿射的（或映上的）。(AfunctionffromAtoBiscalledonto,orsurjective,ifandonlyifforeveryelementy∈Bthereisanelementx∈Awithf(x)=y.Afunctionfiscalledasurjection(滿函數(shù))ifitisonto.)映上的，滿函數(shù)，滿射DEFINITION5.函數(shù)的定義和性質(zhì)79設(shè)函數(shù)f:AB，若ranf=B，則稱f是

設(shè)函數(shù)f:A

B，其中A={a,b,c,d},B={1,2,3}，f(a)=3,f(b)=2,f(c)=1,

f(d)=3.問：f是滿射的嗎？EXAMPLE1·······abcd123f函數(shù)的定義和性質(zhì)80設(shè)函數(shù)f:AB，其中A={a,b,c,d}

設(shè)函數(shù)f:A

B，若對于任何的x1,x2A,x1x2,都有f(x1)f(x2)，則稱f是單射的（或一對一的）。(Afunctionfissaidtobeone-to-one,orinjective,ifandonlyiff(x1)=f(x2)impliesthatx1=x2forallx1andx2inthedomainoff.Afunctionissaidtobeaninjection(單函數(shù))ifitisone-to-one.)一對一，單函數(shù)，單射DEFINITION6.函數(shù)的定義和性質(zhì)81設(shè)函數(shù)f:AB，若對于任何的x1,x2A

設(shè)函數(shù)f:A

B，其中A={a,b,c,d},B={1,2,3,4,5}，f(a)=4,f(b)=5,f(c)=1,f(d)=3.問：f是單射的嗎？EXAMPLE2·····

·

·

·

·abcd12345f函數(shù)的定義和性質(zhì)82設(shè)函數(shù)f:AB，其中A={a,b,c,d}

設(shè)函數(shù)f:A

B，若f既是滿射的，又是單射的，則稱f是雙射的（或一一對應(yīng)的）。(Thefunctionfisaone-onecorrespondence,orabijection,ifitisbothone-to-oneandonto.)一一對應(yīng)，雙射DEFINITION7.函數(shù)的定義和性質(zhì)83設(shè)函數(shù)f:AB，若f既是滿射的，又是單射的，則

設(shè)f:R

R，對于任意的x1,x2R，若x1<x2，則有f(x1)≤f(x2)，就稱f為單調(diào)遞增的。若x1<x2，則有f(x1)<f(x2)，就稱f為嚴(yán)格單調(diào)遞增的。類似的也可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù)。它們統(tǒng)稱為單調(diào)函數(shù)。(Afunctionfwhosedomainandcodomainaresubsetsofthesetofrealnumbersiscalledstrictlyincreasingiff(x)<f(y)wheneverx<yandxandyareinthedomainoff.Similarly,fiscalledstrictlydecreasingiff(x)>f(y)wheneverx<yandxandyareinthedomainoff.)DEFINITION8.函數(shù)的定義和性質(zhì)84設(shè)f:RR，對于任意的x1,x2R，若x1<DEFINITION9.

設(shè)f:A

B，若存在yB使得對所有的xA都有f(x)=y，則稱f:A

B是常函數(shù)。設(shè)A為集合，對于任意的A’A，A’的特征函數(shù)

A’:A{0,1}定義為A’(a)=

設(shè)R是A上的等價(jià)關(guān)系，定義一個(gè)從A到A/R的函數(shù)g:AA/R且g(a)=[a]，它把A中的元素a映射到a的等價(jià)類[a]，稱g是從A到商集A/R的自然映射。aA’0aA-A’函數(shù)的定義和性質(zhì)85DEFINITION9.設(shè)f:AB，若存在EXAMPLE31.設(shè)A={a,b,c},A’={a}，則有函數(shù)

A’

:A

{0,1}，

A’

(a)=1,

A’

(b)=0,

A’

(c)=0.2.設(shè)A={1,2,3},R={<1,2>,<2,1>}∪IA，則有函數(shù)g:AA/R，g(1)=g(2)={1,2},g(3)={3}.函數(shù)的定義和性質(zhì)86EXAMPLE31.設(shè)A={a,b,

設(shè)函數(shù)g:A

B,f:BC，則復(fù)合函數(shù)

f

?