離散數(shù)學(xué)課件老師畫重點(diǎn)版ch7

主要內(nèi)容有序?qū)εc笛卡兒積二元關(guān)系的定義與表示法關(guān)系的運(yùn)算關(guān)系的性質(zhì)等價(jià)關(guān)系與劃分偏序關(guān)系第七章二元關(guān)系17.1有序?qū)εc笛卡兒積定義7.1由兩個(gè)元素x和y，按照一定的順序組成的二元組稱為有序?qū)Γ涀?lt;x,y>.有序?qū)π再|(zhì):(1)有序性<x,y><y,x>（當(dāng)xy時(shí)）(2)<x,y>與<u,v>相等的充分必要條件是<x,y>=<u,v>

x=uy=v.2笛卡兒積定義7.2設(shè)A,B為集合，A與B的笛卡兒積記作AB，且

AB={<x,y>|xAyB}.例1

A={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={},B=P(A)A={<,>,<{},>}P(A)B=

3笛卡兒積的性質(zhì)(1)不適合交換律

AB

BA(AB,A,B)(2)不適合結(jié)合律(AB)C

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

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

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

(5)若|A|=m,|B|=n,則|AB|=mn

4性質(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).5實(shí)例例2(1)證明A=B,C=D

AC=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=,則AC=BD但是A

B.67.2二元關(guān)系定義7.3如果一個(gè)集合滿足以下條件之一：(1)集合非空,且它的元素都是有序?qū)?2)集合是空集則稱該集合為一個(gè)二元關(guān)系,簡稱為關(guān)系，記作R.如果<x,y>∈R,可記作xRy；如果<x,y>R,則記作x

y實(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,a

c等.7A到B的關(guān)系與A上的關(guān)系定義7.4設(shè)A,B為集合,A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系,當(dāng)A=B時(shí)則叫做A上的二元關(guān)系.例3

A={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的子集有個(gè).所以A上有個(gè)不同的二元關(guān)系.例如|A|=3,則A上有=512個(gè)不同的二元關(guān)系.8A上重要關(guān)系的實(shí)例定義7.5設(shè)A為集合,(1)是A上的關(guān)系，稱為空關(guān)系(2)

全域關(guān)系

EA={<x,y>|x∈A∧y∈A}=A×A恒等關(guān)系IA

={<x,x>|x∈A}小于等于關(guān)系LA

={<x,y>|x,y∈A∧x≤y},A為實(shí)數(shù)子集

整除關(guān)系DB={<x,y>|x,y∈B∧x整除y},A為非0整數(shù)子集

包含關(guān)系R={<x,y>|x,y∈A∧xy},A是集合族.9實(shí)例例如,A={1,2},則EA

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

={<1,1>,<2,2>}例如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}>}

類似的還可以定義：大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等.10關(guān)系的表示1.關(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.2.關(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到B的關(guān)系或A上的關(guān)系（A,B為有窮集）關(guān)系圖適合表示有窮集A上的關(guān)系11實(shí)例例4A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關(guān)系矩陣MR和關(guān)系圖GR如下：127.3關(guān)系的運(yùn)算關(guān)系的基本運(yùn)算定義7.6關(guān)系的定義域、值域與域分別定義為domR={x|y(<x,y>R)}ranR={y|x(<x,y>R)}fldR=domR

ranR例5

R={<1,2>,<1,3>,<2,4>,<4,3>},則domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}13關(guān)系運(yùn)算(逆與合成)定義7.7關(guān)系的逆運(yùn)算R1={<y,x>|<x,y>R}定義7.8關(guān)系的合成運(yùn)算RS={<x,z>|

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

R={<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>}

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

SR={<1,2>,<1,4>,<3,2>,<3,3>}14合成的圖示法利用圖示（不是關(guān)系圖）方法求合成

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

SR={<1,2>,<1,4>,<3,2>,<3,3>}15關(guān)系運(yùn)算(限制與像)定義7.9設(shè)R為二元關(guān)系,A是集合(1)R在A上的限制記作R?A,其中

R?A={<x,y>|xRy∧x∈A}(2)A在R下的像記作R[A],其中

R[A]=ran(R?A)說明：R在A上的限制R?A是R的子關(guān)系，即R?ARA在R下的像R[A]是ranR

的子集，即R[A]ranR

16實(shí)例例7設(shè)R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},則

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

R?=

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

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

R[]=

R[{3}]={2}17關(guān)系運(yùn)算的性質(zhì)定理7.1設(shè)F是任意的關(guān)系,則(1)(F1)1=F(2)domF1=ranF,ranF1=domF證(1)任取<x,y>,由逆的定義有<x,y>∈(F1)1

<y,x>∈F1

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

y(<x,y>∈F1)

y(<y,x>∈F)

x∈ranF

所以有domF1=ranF.同理可證ranF1=domF.18定理7.2設(shè)F,G,H是任意的關(guān)系,則(1)(FG)H=F(GH)(2)(FG)1=G1F1關(guān)系運(yùn)算的性質(zhì)證(1)任取<x,y>,<x,y>(FG)H

t(<x,t>∈FG∧<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>∈GH)

<x,y>∈F(GH)所以(FG)H=F(GH)19證明(2)任取<x,y>,

<x,y>∈(FG)1

<y,x>∈FG

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

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

<x,y>∈G1F1

所以(F

G)1=G1F1

20關(guān)系運(yùn)算的性質(zhì)定理7.3設(shè)R為A上的關(guān)系,則

RIA=IAR=R證任取<x,y>

<x,y>∈RIA

t(<x,t>∈R∧<t,y>∈IA)

t(<x,t>∈R∧t=y∧y∈A)<x,y>∈R21關(guān)系運(yùn)算的性質(zhì)定理7.4

(1)F(GH)=FG∪FH(2)(G∪H)F=GF∪HF(3)F(G∩H)

FG∩FH(4)(G∩H)F

GF∩HF只證(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>∈FG∧<x,y>∈FH

<x,y>∈FG∩FH所以有F(G∩H)=FG∩FH22推廣定理7.4的結(jié)論可以推廣到有限多個(gè)關(guān)系R(R1∪R2∪…∪Rn)=RR1∪RR2∪…∪RRn

(R1∪R2∪…∪Rn)R=R1R∪R2R∪…∪RnR

R(R1∩R2∩…∩Rn)

RR1∩RR2∩…∩RRn

(R1∩R2∩…∩Rn)R

R1R∩R2R∩…∩RnR

23關(guān)系運(yùn)算的性質(zhì)定理7.5設(shè)F為關(guān)系,A,B為集合,則(1)F?(A∪B)=F?A∪F?B(2)F[A∪B]=F[A]∪F[B](3)F?(A∩B)=F?A∩F?B(4)F[A∩B]

F[A]∩F[B]

24證明證只證(1)和(4).(1)任取<x,y>

<x,y>∈F?(A∪B)<x,y>∈F∧x∈A∪B<x,y>∈F∧(x∈A∨x∈B)(<x,y>∈F∧x∈A)∨(<x,y>∈F∧x∈B)<x,y>∈F?A∨<x,y>∈F?B<x,y>∈F?A∪F?B所以有F?(A∪B)=F?A∪F?B.25證明(4)任取y,y∈F[A∩B]

x(<x,y>∈F∧x∈A∩B)

x(<x,y>∈F∧x∈A∧x∈B)

x((<x,y>∈F∧x∈A)∧(<x,y>∈F∧x∈B))

x(<x,y>∈F∧x∈A)∧x(<x,y>∈F∧x∈B)

y∈F[A]∧y∈F[B]

y∈F[A]∩F[B]

所以有F[A∩B]=F[A]∩F[B].26關(guān)系的冪運(yùn)算定義7.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為：(1)R0={<x,x>|x∈A}=IA(2)

Rn+1=RnR注意：對于A上的任何關(guān)系R1和R2都有R10=R20=IA

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

例8設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關(guān)系圖表示.解R與R2的關(guān)系矩陣分別是：冪的求法28R3和R4的矩陣是：因此M4=M2,即R4=R2.因此可以得到

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

R0的關(guān)系矩陣是冪的求法29關(guān)系圖R0,R1,R2,R3,…的關(guān)系圖如下圖所示.

R0R1R2=R4=…R3=R5=…30冪運(yùn)算的性質(zhì)定理7.6設(shè)A為n元集,R是A上的關(guān)系,則存在自然數(shù)s和t,使得Rs=Rt.31定理7.7設(shè)R是A上的關(guān)系,m,n∈N,則(1)RmRn=Rm+n(2)(Rm)n=Rmn

冪運(yùn)算的性質(zhì)證用歸納法(1)對于任意給定的m∈N,施歸納于n.若n=0,則有

RmR0=RmIA=Rm=Rm+0

假設(shè)RmRn=Rm+n,則有

RmRn+1

=Rm(RnR)=(RmRn)R=Rm+n+1,所以對一切m,n∈N有RmRn=Rm+n.32證明(2)對于任意給定的m∈N,施歸納于n.若n=0,則有(Rm)0=IA=R0

=Rm×0

假設(shè)(Rm)n=Rmn,則有(Rm)n+1

=(Rm)nRm=(Rmn)Rn=Rmn+m=Rm(n+1)所以對一切m,n∈N有(Rm)n=Rmn.

337.4關(guān)系的性質(zhì)定義7.11設(shè)R為A上的關(guān)系,(1)若x(x∈A→<x,x>R),則稱R在A上是自反的.(2)若x(x∈A→<x,x>R),則稱R在A上是反自反的.實(shí)例：自反：全域關(guān)系EA,恒等關(guān)系IA,小于等于關(guān)系LA,整除關(guān)系DA反自反：實(shí)數(shù)集上的小于關(guān)系、冪集上的真包含關(guān)系.

A={1,2,3},R1,R2,R3是A上的關(guān)系,其中R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R2自反，R3反自反，R1既不是自反的也不是反自反的.34對稱性與反對稱性定義7.12設(shè)R為A上的關(guān)系,

(1)若xy(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對稱的關(guān)系.(2)若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對稱關(guān)系.實(shí)例：對稱關(guān)系：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系反對稱關(guān)系：恒等關(guān)系IA和空關(guān)系也是A上的反對稱關(guān)系.設(shè)A＝{1,2,3},R1,R2,R3和R4都是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：不對稱、不反對稱35傳遞性定義7.13設(shè)R為A上的關(guān)系,若

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),則稱R是A上的傳遞關(guān)系.實(shí)例：A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系，小于等于和小于關(guān)系，整除關(guān)系，包含與真包含關(guān)系設(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和R3是A上的傳遞關(guān)系,R2不是A上的傳遞關(guān)系.36關(guān)系性質(zhì)成立的充要條件定理7.9設(shè)R為A上的關(guān)系,則(1)R在A上自反當(dāng)且僅當(dāng)IAR(2)R在A上反自反當(dāng)且僅當(dāng)R∩IA=(3)R在A上對稱當(dāng)且僅當(dāng)R=R1(4)R在A上反對稱當(dāng)且僅當(dāng)R∩R1IA(5)R在A上傳遞當(dāng)且僅當(dāng)RRR

37自反性反自反性對稱性反對稱性傳遞性集合IARR∩IA=R=R1R∩R1IARRR關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1,且i≠j,則rji＝0M2中1位置,M中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)兩點(diǎn)之間有邊,是一對方向相反的邊兩點(diǎn)之間有邊,是一條有向邊點(diǎn)xi到xj有邊,xj到xk有邊,則xi到xk也有邊關(guān)系性質(zhì)的三種等價(jià)條件387.6等價(jià)關(guān)系與劃分

主要內(nèi)容等價(jià)關(guān)系的定義與實(shí)例等價(jià)類及其性質(zhì)商集與集合的劃分等價(jià)關(guān)系與劃分的一一對應(yīng)39等價(jià)關(guān)系的定義與實(shí)例定義7.15設(shè)R為非空集合上的關(guān)系.如果R是自反的、對稱的和傳遞的,則稱R為A上的等價(jià)關(guān)系.設(shè)R是一個(gè)等價(jià)關(guān)系,若<x,y>∈R,稱x等價(jià)于y,記做x～y.實(shí)例設(shè)A={1,2,…,8},如下定義A上的關(guān)系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.不難驗(yàn)證R為A上的等價(jià)關(guān)系,因?yàn)?1)x∈A,有x≡x(mod3)(2)x,y∈A,若x≡y(mod3),則有y≡x(mod3)(3)x,y,z∈A,若x≡y(mod3),y≡z(mod3),則有x≡z(mod3)

40模3等價(jià)關(guān)系的關(guān)系圖等價(jià)關(guān)系的實(shí)例41等價(jià)類定義定義7.16設(shè)R為非空集合A上的等價(jià)關(guān)系,x∈A，令[x]R

={y|y∈A∧xRy}稱[x]R為x關(guān)于R的等價(jià)類,簡稱為x的等價(jià)類,簡記為[x]或?qū)嵗鼳={1,2,…,8}上模3等價(jià)關(guān)系的等價(jià)類：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}42等價(jià)類的性質(zhì)定理7.14設(shè)R是非空集合A上的等價(jià)關(guān)系,則(1)xA,[x]是A的非空子集(2)x,yA,如果xRy,則[x]=[y](3)x,yA,如果x

y,則[x]與[y]不交(4)∪{[x]|xA}=A43商集與劃分定義7.17設(shè)R為非空集合A上的等價(jià)關(guān)系,以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集,記做A/R,

A/R={[x]R|x∈A}實(shí)例設(shè)A={1,2,…,8}，A關(guān)于模3等價(jià)關(guān)系R的商集為

A/R={{1,4,7},{2,5,8},{3,6}}A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：

A/IA

={{1},{2},…,{8}}，A/EA

={{1,2,…,8}}定義7.18設(shè)A為非空集合,若A的子集族π(π

P(A))滿足:(1)

π(2)xy(x,yπ∧x≠y→x∩y=)(3)∪π=A則稱π是A的一個(gè)劃分,稱π中的元素為A的劃分塊.44例11給出A＝{1,2,3}上所有的等價(jià)關(guān)系實(shí)例1231

12351232123412331對應(yīng)EA,5對應(yīng)IA,2,3和

4分別對應(yīng)R2,R3和R4.

R2={<2,3>,<3,2>}∪IA

R3={<1,3>,<3,1>}∪IA

R4={<1,2>,<2,1>}∪IA解先做出A的劃分,從左到右分別記作1,2,3,4,5.457.7偏序關(guān)系

主要內(nèi)容偏序關(guān)系偏序關(guān)系的定義偏序關(guān)系的實(shí)例偏序集與哈斯圖偏序集中的特殊元素及其性質(zhì)極大元、極小元、最大元、最小元上界、下界、最小上界、最大下界46定義與實(shí)例定義7.19偏序關(guān)系：非空集合A上的自反、反對稱和傳遞的關(guān)系，記作?.設(shè)?為偏序關(guān)系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.實(shí)例集合A上的恒等關(guān)系IA是A上的偏序關(guān)系.小于或等于關(guān)系,整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系.47相關(guān)概念定義7.20設(shè)R為非空集合A上的偏序關(guān)系,(1)x,y∈A,x與y可比

x?y∨y?x(2)任取元素x和y,可能有下述幾種情況發(fā)生：

x?y(或y?x),x＝y(tǒng),x與y不是可比的定義7.21

R為非空集合A上的偏序關(guān)系,(1)x,y∈A,x與y都是可比的，則稱R為全序（或線序）實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系,整除關(guān)系不是正整數(shù)集合上的全序關(guān)系定義7.22

x,y∈A,如果x?y且不存在z∈A使得x?z?y,則稱y覆蓋x.例如{1,2,4,6}集合上整除關(guān)系,2覆蓋1,4和6覆蓋2,4不覆蓋1.48偏序集與哈斯圖定義7.23集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.實(shí)例:<Z,≤>,<P(A),R>哈斯圖:利用偏序關(guān)系的自反、反對稱、傳遞性進(jìn)行簡化的關(guān)系圖特點(diǎn)：(1)每個(gè)結(jié)點(diǎn)沒有環(huán) (2)兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前(3)具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊49實(shí)例例12偏序集<{1,2,3,4,5,6,7,8,9},R整除>和<P({a,b,c}),R>的哈斯圖.

50例13已知偏序集<A,R>的哈斯圖如下圖所示,試求出集合A和關(guān)系R的表達(dá)式.

解A={a,b,c,d,e,f,g,h}R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA實(shí)例51偏序集中的特殊元素

定義7.24設(shè)<A,?>為偏序集,BA,y∈B(1)若x(x∈B→y?x)成立,則稱y為B的最小元(2)若x(x∈B→x?y)成立,則稱y為B的最大元(3)若