離散數(shù)學(xué)第五版第四章(耿素云、屈婉玲、張立昂編著)

第四章

二元關(guān)系和函數(shù)4.1迪卡爾乘積與二元關(guān)系4.2二元運算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系4.6函數(shù)的定義與性質(zhì)4.7函數(shù)的復(fù)合與反函數(shù)4.1迪卡爾乘積與二元關(guān)系定義4.1一、有序?qū)τ蓛蓚€元素x和y（允許x=y）按一定的順序排列成的二元組叫做一個有序?qū)蛐蚺?，記?lt;x,y>，其中x是它的第一元素，y是它的第二元素。有序?qū)π再|(zhì)當(dāng)x

y時，<x,y>

<y,x><x,y>=<u,v>的充分必要條件是x=u且y=v

集合中的元素具有無序性，但是有序?qū)χ械脑厥怯行虻摹?.1迪卡爾乘積與二元關(guān)系例1：已知<x+2,4>=<5,2x+y>求x和y解得：x=3，y=-2根據(jù)有序?qū)Φ男再|(zhì)得：x+2=52x+y=4有序n元組一個有序n元組(n>=3)是一個有序?qū)Γ渲械谝粋€元素是一個有序n-1元組，一個有序n元組記作<x1,x2,……,xn>，即<x1,x2,……,xn>=<<x1,x2,……xn-1>,xn>例如：空間直角坐標(biāo)系中點的坐標(biāo)<1,-1,3>、<2,4.5,0>等有序

3元組。n維空間中點的坐標(biāo)或n維向量都是有序n元組。4.1迪卡爾乘積與二元關(guān)系定義4.3二、迪卡爾乘積設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)ΑＫ羞@樣的有序?qū)M成的集合叫做A和B的迪卡爾乘積，記作A×B。符號化表示為：

A×B={<x,y>|xAyB}4.1迪卡爾乘積與二元關(guān)系迪卡爾乘積的性質(zhì)如果|A|=m,|B|=n，則|A×B|=mn對任意集合A，根據(jù)定義有：A×=，×A=一般地說，迪卡爾乘積運算不滿足交換律，即：

A×BB×A(當(dāng)ABAB時)迪卡爾乘積運算不滿足結(jié)合律，即： （A×B）×CA×（B×C）（當(dāng)ABC）4.1迪卡爾乘積與二元關(guān)系迪卡爾乘積運算對并和交運算滿足分配律，即：(1)A×（BC）=(A×B)(A×C）證明：對于任意的<x,y> <x,y>A×（BC）

xAyBC xA(yByC) (xAyB)(xAyC) <x,y>A×B<x,y>A×C <x,y>(A×B)(A×C)4.1迪卡爾乘積與二元關(guān)系迪卡爾乘積運算對并和交運算滿足分配律，即：(2)（BC）×A=(B×A)(C×A）證明：對于任意的<x,y> <x,y>（BC）×A xBCyA (xBxC)yA (xByA)(xCyA) <x,y>B×A<x,y>C×A <x,y>(B×A)(C×A)4.1迪卡爾乘積與二元關(guān)系迪卡爾乘積運算對并和交運算滿足分配律，即：(3)A×（BC）=(A×B)(A×C）證明：對于任意的<x,y> <x,y>A×（BC）

xAyBC xA(yByC) (xAyB)(xAyC) <x,y>A×B<x,y>A×C <x,y>(A×B)(A×C)4.1迪卡爾乘積與二元關(guān)系迪卡爾乘積運算對并和交運算滿足分配律，即：(4)（BC）×A=(B×A)(C×A）證明：對于任意的<x,y> <x,y>（BC）×A xBCyA (xBxC)yA (xByA)(xCyA) <x,y>B×A<x,y>C×A <x,y>(B×A)(C×A)4.1迪卡爾乘積與二元關(guān)系A(chǔ)CBDA×BC×D證明：對于任意的<x,y> <x,y>A×B xAyB xCyD xC×D

所以：A×BC×D4.1迪卡爾乘積與二元關(guān)系n階迪卡爾乘積（定義4.4）設(shè)A1，A2，……，An是集合(n>=2)，它們的n階迪卡爾乘積記作A1×A2×……×An，其中：

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

……xnAn}4.1迪卡爾乘積與二元關(guān)系例2：設(shè)A={1,2}，求P(A)×A解：P(A)={,{1},{2},{1,2}}P(A)×A={<,1>,<,2>, <{1},1>,<{1},2>, <{2},1>,<{2},2>, <{1,2},1>,<{1,2},2>}4.1迪卡爾乘積與二元關(guān)系例3：設(shè)A,B,C,D為任意集合，判斷以下等式是否成立？（1）(AB)×(CD)=(A×C)(B×D)證明：對于任意的<x,y> <x,y>(AB)×(CD) xAByCD xAxByCyD (xAyC)(xByD) <x,y>A×C<x,y>B×D <x,y>(A×C)(B×D)4.1迪卡爾乘積與二元關(guān)系（2）(AB)×(CD)=(A×C)(B×D)證明：設(shè)A=、B={1}、C={2}、D={3}

(AB)×(CD)={<1,2>、<1,3>}

(A×C)(B×D)={<2,1>、<2,3>}

所以：等式不成立（3）(A-B)×(C-D)=(A×C)-(B×D)證明：設(shè)A={1}、B={1}、C={2}、D={3}

(A-B)×(C-D)=

(A×C)-(B×D)={<1,2>}

所以：等式不成立4.1迪卡爾乘積與二元關(guān)系（4）(AB)×(CD)=(A×C)(B×D)證明：設(shè)A={1}、B={1}、C={2}、D={3}

(AB)×(CD)=

(A×C)(B×D)={<1,2>,<1,3>}

所以：等式不成立4.1迪卡爾乘積與二元關(guān)系例4：設(shè)A,B,C,D為任意集合，判斷真假。（1）A×B=A×CB=C證明：若A=，B={1}，C={2}

則A×B=A×C=，而BC。 所以：命題真假不定4.1迪卡爾乘積與二元關(guān)系（2）A-(B×C)=(A×B)-(A×C)證明：若A={0}，B={1}，C={2}

則A-(B×C)={0}

(A×B)-(A×C)={<0,1>}

所以：命題真假不定4.1迪卡爾乘積與二元關(guān)系（3）A=BC=D

(A×C)=(B×D)證明：對任意<x,y> <x,y>A×C xAyC xByD x<B×D>

所以：命題真值為14.1迪卡爾乘積與二元關(guān)系（4）存在集合A，使得A

A×A證明：令A(yù)= 則A×A=

所以：A

A×A

該命題真值為14.1迪卡爾乘積與二元關(guān)系定義4.5三、二元關(guān)系如果一個集合滿足以下條件之一：集合非空，且它的元素都是有序?qū)鲜强占瘎t稱這樣的集合為二元關(guān)系，記作R。二元關(guān)系也可以簡稱為關(guān)系。對于二元關(guān)系R，如果<x,y>R，可記作xRy。例：R1={<1,2>,<a,b>}，R2={<1,2>,a,b}

則R1為二元關(guān)系；R2不是二元關(guān)系，僅僅是一個集合。4.1迪卡爾乘積與二元關(guān)系集合上元素的關(guān)系（定義4.6）三、二元關(guān)系設(shè)A，B為集合，A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系，特別當(dāng)A=B是則叫做A上的二元關(guān)系。例：A={0,1}、B={1,2,3}，那么R1={<0,2>}，R2=A×B，R3=

，R4={<0,1>}等都是

A到B的二元關(guān)系。R3和R4是A上的二元關(guān)系。

集合A上的二元關(guān)系的數(shù)目依賴于A中的元素數(shù)：設(shè)|A|=n，則|A×A|=。A×A的子集有個。每個子集代表一個A上的二元關(guān)系，所以A上的二元關(guān)系數(shù)目為：。4.1迪卡爾乘積與二元關(guān)系全域關(guān)系與恒等關(guān)系例：A={0,1}A上的全域關(guān)系為：{<0,0>,<0,1>,<1,0>,<1,1>}.A上的恒等關(guān)系為：{<0,0>,<1,1>}.對于任意集合A，定義：

EA={<x,y>|xAyA}=A×A IA={<x,x>|xA} LA={<x,y>|x,yAx<=y},這里A

R

DA={<x,y>|x,yAx整除y},這里A

4.1迪卡爾乘積與二元關(guān)系例：A={4,0.5,-1},B={1,2,3,6}，則LA={<-1,-1>,<0.5,0.5>,<4,4>,<-1,0.5>,<-1,4>,<0.5,4>}LB={<1,1>,<2,2>,<3,3>,<6,6>,<2,1>,<3,1><6,1>,<6,2>,<6,3>}4.1迪卡爾乘積與二元關(guān)系例5：設(shè)A={a,b}，R是P(A)上的包含關(guān)系，R={<x,y>|x,yP(A)xy}解：P(A)={,{a},,{a,b}}

R={<,>,<,{a}>,<,>,<,{a,b}>, <{a},{a}>,<{a},{a,b}>,<,>, <,{a,b}>,<{a,b},{a,b}>}4.1迪卡爾乘積與二元關(guān)系關(guān)系的表示方法集合表達(dá)式：例6：設(shè)A={1,2,3,4}，下面各式定義的R都是A上的 關(guān)系，試用列元素法表示R R1={<x,y>|x是y的倍數(shù)} R2={<x,y>|(x-y)(x-y)A} R3={<x,y>|x/y是素數(shù)} R4={<x,y>|x

y}4.1迪卡爾乘積與二元關(guān)系關(guān)系的表示方法關(guān)系矩陣：設(shè)A={x1,x2,……,xn}，R是A上的關(guān)系，令則是R的關(guān)系矩陣，記作MR。4.1迪卡爾乘積與二元關(guān)系關(guān)系的表示方法關(guān)系圖：設(shè)A={x1,x2,……,xn}，R是A上的關(guān)系，令圖G=<V,E>，其中頂點集合V=A，邊集為E。對于

xi，xjV，滿足

<xi,xj>ExiRxj稱圖G為R的關(guān)系圖，記作GR。第四章

二元關(guān)系和函數(shù)4.1迪卡爾乘積與二元關(guān)系4.2二元運算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系4.6函數(shù)的定義與性質(zhì)4.7函數(shù)的復(fù)合與反函數(shù)4.2關(guān)系的運算關(guān)系的定義域、值域、域（定義4.8）一、關(guān)系的基本運算設(shè)R是二元關(guān)系。R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義 域，記作domR，形式化表示為：

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

ranR={y|x(<x,y>R)}4.2關(guān)系的運算R的定義域和值域的并集稱為R的域，記作fldR，形式化 表示為：

fldR=domR

ranR例1：設(shè)R={<1,2>,<1,3>,<2,4>,<4,3>}，則domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}4.2關(guān)系的運算例2：下列關(guān)系都是整數(shù)集Z上的關(guān)系，分別求出它們的 定義域和值域。(1)R1={<x,y>|x,yZx<=y}(2)R2={<x,y>|x,yZx*x+y*y=1}(3)R3={<x,y>|x,yZy=2x}(4)R4={<x,y>|x,yZ|x|=|y|=3}4.2關(guān)系的運算關(guān)系的逆運算（定義4.9）設(shè)R為二元關(guān)系，R的逆關(guān)系，簡稱R的逆，記作，其中關(guān)系的合成運算（定義4.9）設(shè)F，G為二元關(guān)系，F(xiàn)和G的合成記作F

G，其中

F

G={<x,y>|z(xGzzFy)}4.2關(guān)系的運算例3：設(shè)F={<3,3>,<6,2>}，G={<2,3>}，則FG={<2,3>}={<3,3>,<2,6>}GF={<6,3>}例4：設(shè)F={<x,y>|x,yNy=x*x}，

G={<x,y>|x,yNy=x+1}， 求4.2關(guān)系的運算限制與像（定義4.9）設(shè)F為二元關(guān)系，A是集合F在A上的限制記作FA，其中

FA={<x,y>|xFy

xA}A在F上的象記作F[A]，其中

F[A]=ran(FA)F在A上的限制FA是F的子關(guān)系，而A在F下的像F[A]是ranF的子集。4.2關(guān)系的運算例5：設(shè)R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}則R[{1}]={2,3}R{1}={<1,2>,<1,3>}R

=

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

]=

R[{2,3}]={2,4}4.2關(guān)系的運算關(guān)系的運算的順序關(guān)系運算中的逆運算優(yōu)先于其他運算；所有的關(guān)系運算都優(yōu)先于集合運算；沒有規(guī)定優(yōu)先權(quán)的運算以括號決定運算順序。4.2關(guān)系的運算定理4.1二、關(guān)系基本運算的性質(zhì)設(shè)F,G,H是任意的關(guān)系，則=Fdom=ranF,ran=domF(F

G)

H=F(GH)(F

G)=GF4.2關(guān)系的運算定理設(shè)R為A上的關(guān)系，則RIA=IAR=R定理4.2F(GH)=FGFH(GH)F=GFHFF(GH)FGFH(GH)FGFHF4.2關(guān)系的運算定義4.10三、關(guān)系的n次冪設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：={<x,x>|xA}=IA

注：(1)

。

(2)。4.2關(guān)系的運算例6：設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}

求=IA={<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}={<a,b>,<a,d>,<b,a>,<b,c>}={<a,a>,<a,c>,<b,b>,<b,d>}={<a,b>,<a,d>,<b,a>,<b,c>}4.2關(guān)系的運算定理4.3設(shè)R為A上的關(guān)系，m,nN，則

第四章

二元關(guān)系和函數(shù)4.1迪卡爾乘積與二元關(guān)系4.2二元運算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系4.6函數(shù)的定義與性質(zhì)4.7函數(shù)的復(fù)合與反函數(shù)4.3關(guān)系的性質(zhì)自反性、反自反性一、關(guān)系的性質(zhì)設(shè)R是A上的關(guān)系，若

x(xA<x,x>R)，則稱R在A上是自反的。若

x(xA<x,x>R)，則稱R在A上是反自反的。A上的全域關(guān)系EA、恒等關(guān)系IA、都是A上的自反關(guān)系。小于等于關(guān)系LA、整除關(guān)系DB分別為A和B上的自反關(guān)系。小于關(guān)系、真包含關(guān)系是給定集合或集合族上的反自反關(guān)系。4.3關(guān)系的性質(zhì)例8：設(shè)A={1,2,3}，R1，R2和R3是A上的關(guān)系，其中

R1={<1,1>,<2,2>} R2={<1,1>,<2,2>,<3,3>} R3={<1,3>}說明R1，R2和R3是否為A上的自反關(guān)系和反自反關(guān)系。R3是A上的反自反關(guān)系，R2是A上的自反關(guān)系。1234.3關(guān)系的性質(zhì)對稱性、反對稱性設(shè)R是A上的關(guān)系，若

xy(x,yA<x,y>R<y,x>R)， 則稱R為A上對稱的關(guān)系。若

xy(x,yA<x,y>R<y,x>Rx=y)， 則稱R為A上反對稱的關(guān)系。A上的全域關(guān)系EA、恒等關(guān)系IA、空關(guān)系都是A上的對稱關(guān)系。恒等關(guān)系IA、空關(guān)系也是A上的反對稱關(guān)系。4.3關(guān)系的性質(zhì)例9：設(shè)A={1,2,3}，R1，R2和R3是A上的關(guān)系，其中

R1={<1,1>,<2,2>} R2={<1,1>,<1,2>,<2,1>} R3={<1,2>,<1,3>} R4={<1,2>,<2,1>,<1,3>}說明R1，R2，R3和R4是否為A上的對稱關(guān)系和反對稱關(guān)系。1231231231234.3關(guān)系的性質(zhì)傳遞性設(shè)R是A上的關(guān)系，若xyz(x,y,zA<x,y>R<y,z>R<x,z>R)，則稱R為A上傳遞的關(guān)系。A上的全域關(guān)系EA、恒等關(guān)系IA、空關(guān)系都是A上的傳遞關(guān)系。小于或等于LA、整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的的傳遞關(guān)系。小于關(guān)系、真包含關(guān)系也是相應(yīng)集合上的的傳遞關(guān)系。4.3關(guān)系的性質(zhì)例10：設(shè)A={1,2,3}，R1，R2和R3是A上的關(guān)系，其中

R1={<1,1>,<2,2>} R2={<1,2>,<2,3>} R3={<1,3>}說明R1，R2，R3和R4是否為A上的傳遞關(guān)系。1231231234.3關(guān)系的性質(zhì)定理二、關(guān)系性質(zhì)的相關(guān)定理設(shè)R是A上的關(guān)系，則R在A上的自反當(dāng)且僅當(dāng)IA

R。R在A上的反自反當(dāng)且僅當(dāng)RIA=。R在A上的對稱當(dāng)且僅當(dāng)。R在A上的反對稱當(dāng)且僅當(dāng)。R在A上的傳遞當(dāng)且僅當(dāng)。4.3關(guān)系的性質(zhì)例11：設(shè)A是集合，R1和R2是A上的關(guān)系，證明：(1)若R1，R2是自反的和對稱的，則R1R2也是自反的和對稱的。證明：（1）4.3關(guān)系的性質(zhì)例11：設(shè)A是集合，R1和R2是A上的關(guān)系，證明：

(2)若R1和R2是傳遞的，則R1R2也是傳遞的。證明：（2）4.3關(guān)系的性質(zhì)五種性質(zhì)在關(guān)系矩陣和關(guān)系圖中的特點

性質(zhì)表示自反性反自反性對稱性反對稱性傳遞性集合表達(dá)式IA

RR

IA＝

關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij=1，且i

j，則rij=0對M×M中1所在的位置，M中相應(yīng)位置都是1關(guān)系圖每個頂點都是環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊，一定是一對方向相反的邊如果兩個頂點之間有邊，一定是一條有向邊如果頂點xi到xj有邊，xj到xk有邊，則從xi到xk也有邊4.3關(guān)系的性質(zhì)關(guān)系運算與關(guān)系性質(zhì)

原有性質(zhì)運算自反性反自反性對稱性反對稱性傳遞性

R1

R2

R1

R2

R1－R2

第四章

二元關(guān)系和函數(shù)4.1迪卡爾乘積與二元關(guān)系4.2二元運算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系4.6函數(shù)的定義與性質(zhì)4.7函數(shù)的復(fù)合與反函數(shù)4.4關(guān)系的閉包一、關(guān)系閉包的定義設(shè)R是非空集合A上的關(guān)系，R的自反（對稱或傳遞）閉包是A上的關(guān)系R’，使得R’滿足以下條件：

（1）R’是自反的（對稱或傳遞的）

（2）R

R’

（3）對A上的任何包含R的自反（對稱或傳遞）關(guān)系R’’

有R’

R’’

一般將R的自反閉包記作r(R),對稱閉包記作s(R),傳遞閉包記作t(R).4.4關(guān)系的閉包例1：設(shè)A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>}則R關(guān)系圖如下圖，則如何求A上關(guān)系R的閉包？abcd4.4關(guān)系的閉包設(shè)R為非空集合A上的二元關(guān)系，則有二、關(guān)系閉包的求法（關(guān)系運算方法）

；

；

。4.4關(guān)系的閉包例2：設(shè)A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>}則R和r(R),s(R),t(R)的關(guān)系圖如下圖，則如何求A上關(guān)系R的閉包？abcdr(R)={<a,b>,<b,a>,<b,c>,<c,d>}IA={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<c,c>,<d,d>}s(R)={<a,b>,<b,a>,<b,c>,<c,d>}

={<a,b>,<b,a>,<b,c>,<c,d>,<c,b>,<d,c>}t(R)={<a,b>,<b,a>,<b,c>,<c,d>}

={<a,b>,<b,a>,<b,c>,<c,d>,<a,a>,<b,b>,<a,c>,<b,b>, <b,d>,<a,d>}4.4關(guān)系的閉包設(shè)R為非空集合A上的二元關(guān)系，則有三、關(guān)系閉包的求法（矩陣運算方法）Mr=M+E；Ms=M+M’；

。4.4關(guān)系的閉包三、關(guān)系閉包的性質(zhì)（1）R是自反的當(dāng)且僅當(dāng)r(R)=R；R是對稱的當(dāng)且僅當(dāng)s(R)=R;R是傳遞的當(dāng)且僅當(dāng)t(R)=R;設(shè)R是非空集合A上的關(guān)系，則4.4關(guān)系的閉包三、關(guān)系閉包的性質(zhì)（2）r(R1)r(R2)；s(R1)s(R2);t(R1)t(R2);設(shè)R1和R2是非空集合A上的關(guān)系，且R1

R2，則4.4關(guān)系的閉包三、關(guān)系閉包的性質(zhì)(3)

；

；

。設(shè)R是非空集合A上的關(guān)系，則4.4關(guān)系的閉包三、關(guān)系閉包的性質(zhì)(4)r(s(R))=s(r(R))。r(t(R))=t(r(R))。s(t(R))t(s(R))。設(shè)R是非空集合A上的關(guān)系，則第四章

二元關(guān)系和函數(shù)4.1迪卡爾乘積與二元關(guān)系4.2二元運算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系4.6函數(shù)的定義與性質(zhì)4.7函數(shù)的復(fù)合與反函數(shù)4.5等價關(guān)系與偏序關(guān)系一、等價關(guān)系的定義設(shè)R為非空集合A上的關(guān)系，如果R是自反的、對稱的、傳遞的，則稱R為A上的等價關(guān)系。對任何x,yA，如果<x,y>等價關(guān)系R，則記作xy。4.5等價關(guān)系與偏序關(guān)系例4：A={1,2,3,,8},R={<x,y>|x,yAxy(mod3)},其中xy(mod3)的含義就是x-y可以被3整除。求證：R是否為等價關(guān)系？58247163對任何正整數(shù)n可以定義整數(shù)集合Z上模n的等價關(guān)系：

R={<x,y>|x,yZxy(modn)}4.5等價關(guān)系與偏序關(guān)系例5:在一群人的集合上，年齡相等的關(guān)系、朋友關(guān)系。動物是按種屬分類的，“具有相同種屬”的關(guān)系。集合上的恒等關(guān)系。在同一平面上，三角形之間的相似關(guān)系。在同一平面上，直線間的平行關(guān)系。4.5等價關(guān)系與偏序關(guān)系二、等價類的定義設(shè)R是非空集合A上的等價關(guān)系，對任意的x

A，令

[x]R={y|yAxRy},則稱[x]R為x關(guān)于R的等價類，簡稱為x的等價類，簡記為[x]。集合A={1,2,3,,8},R={<x,y>|x,yAxy(mod3)}中的等價類有：[1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6}4.5等價關(guān)系與偏序關(guān)系三、等價關(guān)系、等價類的性質(zhì)[x]

，且[x]A;若xRy，則[x]=[y];若<x，y>R，則[x][y]=;

;4.5等價關(guān)系與偏序關(guān)系四、商集的定義設(shè)R是非空集合A上的等價關(guān)系，以R的不交的等價類為元素的集合叫做A在R下的商集，記作A/R，即

A/R={[x]R|xA}。集合A={1,2,3,,8},R={<x,y>|x,yAxy(mod3)}，則A在R下的商集是：

A/R=｛{1,4,7}，{2,5,8}，{3,6}}4.5等價關(guān)系與偏序關(guān)系例6:非空集合A上的全域關(guān)系EA是A上的等價關(guān)系，對任意xA

有[x]=,商集A/EA=非空集合A上的恒等關(guān)系IA是A上的等價關(guān)系，對任意xA

有[x]=,商集A/EA=。4.5等價關(guān)系與偏序關(guān)系五、劃分的定義設(shè)A是非空集合，如果存在一個A的子集族

(P(A))滿足以下條件：

，

中任意兩個元素不交，

中所有元素的并集等于A，則稱為A的一個劃分，且稱中的元素為劃分塊。4.5等價關(guān)系與偏序關(guān)系例7:考慮集合A={a,b,c,d}的下列子集族，哪些是A的劃分{{a},{b,c},ewnvo0z}{{a,b,c,d}}{{a,b},{c},{a,d}}{,{a,b},{c,d}}{{a},{b,c}}集合A上的等價關(guān)系與集合A的劃分是一一對應(yīng)的。4.5等價關(guān)系與偏序關(guān)系例8:設(shè)A={1,2,3}，求出A上所有的等價關(guān)系。231R1231R2231R3231R4231R5R1={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}=EAR2={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}R3={<1,1>,<2,2>,<3,3>,<1,3>,<3,1>}R4={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}R5={<1,1>,<2,2>,<3,3>}=IA4.5等價關(guān)系與偏序關(guān)系五、偏序關(guān)系的定義設(shè)R為非空集合A上的關(guān)系，如果R是自反的、反對稱的和傳遞的，則稱R為A上的偏序關(guān)系，簡稱偏序，記作。例如：集合A={1,2,3},R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>},則關(guān)系R是偏序關(guān)系。 整數(shù)集合上的小于等于關(guān)系為偏序關(guān)系； 集合冪集上的子集關(guān)系為偏序關(guān)系。4.5等價關(guān)系與偏序關(guān)系六、可比和蓋住的定義設(shè)<A,>為偏序集，對于任意x,yA，如果xy或者yx成立則稱x與y是可比的，如果x<y(即xyxy)，且不存在z

A使得x<z<y，則稱y蓋住x。例如：集合A={1,2,3,4,5},是整除關(guān)系。那么，對于任意xA都有1x，所以1和1，2，3，4，5都是可比的。但2和3不可比。又1<2，且2<4所以4不能蓋住1。4.5等價關(guān)系與偏序關(guān)系七、全序關(guān)系的定義設(shè)<A,>為偏序集，對于任意x,yA，x和y都可比，則稱為A上的全序關(guān)系，且稱<A,>為全序集。例如：集合A={1,2,3,4,5}上的小于等于關(guān)系為全序關(guān)系，而整除關(guān)系不是全序關(guān)系。4.5等價關(guān)系與偏序關(guān)系八、最小元、最大元、極小元和極大元設(shè)<A，>為偏序集，BA.若

y

B，使得x(xB

yx)成立，則稱y為B的最小元。

若

yB，使得

x(xB

xy)成立，則稱y為B的最大元。

若

yB，使得

x(xB

xy)成立，則稱y為B的極小元。

若

yB，使得

x(x

Byx)成立，則稱y為B的極大元。

4.5等價關(guān)系與偏序關(guān)系例9:設(shè)偏序集<A,

>，求A的極小元，最小元，極大元，最大元abcghdef4.5等價關(guān)系與偏序關(guān)系九、上界、下界、上確界和下確界設(shè)<A，>為偏序集，BA.若

yA，使得

x(xB

xy)成立，則稱y為B的上界。

若

yA，使得

x(xB

yx)成立，則稱y為B的下界。

若C={y|y為B的上界}，則稱C的最小元為B的最小上界或上確界。

若D={y|y為B的下界}，則稱D的最大元為B的最大下界或下確界。

第四章

二元關(guān)系和函數(shù)4.1迪卡爾乘積與二元關(guān)系4.2二元運算4.3關(guān)系的性質(zhì)4.4關(guān)系的閉包4.5等價關(guān)系和偏序關(guān)系4.6函數(shù)的定義與性質(zhì)4.7函數(shù)的復(fù)合與反函數(shù)4.6函數(shù)的定義與性質(zhì)一、函數(shù)的定義（定義4.22）設(shè)F為二元關(guān)系，若對任意的xdomF都存在唯一的yranF使得xFy成立，則稱F為函數(shù)。

例1：設(shè)

F1=｛<x1,y1>,<x2,y1>,<x3,y2>｝

F2={<x1,y1>,<x1,y2>}

判斷他們是否為函數(shù)。4.6函數(shù)的定義與性質(zhì)二、集合A到B的函數(shù)（定義4.23）設(shè)A，B為集合，如果函數(shù)f滿足以下條件（1）domf=A（2）ranfB則稱f是從A到B的函數(shù)，記作f:A->B。

例如：

f:N->N，f(x)=2x g:N->N，g(x)=24.6函數(shù)的定義與性質(zhì)三、集合A到B的函數(shù)（定義4.24）所有從A到B的函數(shù)的集合記作BA，讀作“B上A”。符號化表示為BA＝｛f|f:A->B｝4.6函數(shù)的定義與性質(zhì)f0={<1,a,>,<2,a>,<3,a>}例2：設(shè)A={1,2,3},B={a,b},求={f0,f1,……,f7}，其中：f1={<1,a,>,<2,a>,<3,b>}f2={<1,a,>,<2,b>,<3,a>}f3={<1,a,>,<2,b>,<3,b>}f4={<1,b,>,<2,a>,<3,a>}f5={<1,b,>,<2,a>,<3,b>}f6={<1,b,>,<2,b>,<3,a>}f7={<1,b,>,<2,b>,<3,b>}根據(jù)排列組合得知：

|A|=m,|B|=n |BA|=nm4.6函數(shù)的定義與性質(zhì)設(shè)函數(shù)f:A

B，A’A，四、函數(shù)的像（定義4.25）

令f(A’)={f(x)|x

A’}，稱f(A’)為A’在f下的像。 特別地，當(dāng)A’=A時稱f(A’)=f(A)=ranf為函數(shù)的像。xA,f(x)與f(A)的區(qū)別？4.6函數(shù)的定義與性質(zhì)例3：設(shè)f：N

N，且 令A(yù)={0,1},