離散數(shù)學課件老師畫重點版ch7

主要內容有序對與笛卡兒積二元關系的定義與表示法關系的運算關系的性質等價關系與劃分偏序關系第七章二元關系17.1有序對與笛卡兒積定義7.1由兩個元素x和y，按照一定的順序組成的二元組稱為有序對，記作<x,y>.有序對性質:(1)有序性<x,y><y,x>（當xy時）(2)<x,y>與<u,v>相等的充分必要條件是<x,y>=<u,v>

x=uy=v.2笛卡兒積定義7.2設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笛卡兒積的性質(1)不適合交換律

AB

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

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

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

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

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

4性質證明證明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實例例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二元關系定義7.3如果一個集合滿足以下條件之一：(1)集合非空,且它的元素都是有序對(2)集合是空集則稱該集合為一個二元關系,簡稱為關系，記作R.如果<x,y>∈R,可記作xRy；如果<x,y>R,則記作x

y實例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元關系,當a,b不是有序對時，S不是二元關系根據(jù)上面的記法，可以寫1R2,aRb,a

c等.7A到B的關系與A上的關系定義7.4設A,B為集合,A×B的任何子集所定義的二元關系叫做從A到B的二元關系,當A=B時則叫做A上的二元關系.例3

A={0,1},B={1,2,3},那么R1={<0,2>},R2=A×B,R3=,R4={<0,1>}R1,R2,R3,R4是從A到B的二元關系,R3和R4也是A上的二元關系.計數(shù):|A|=n,|A×A|=n2,A×A的子集有個.所以A上有個不同的二元關系.例如|A|=3,則A上有=512個不同的二元關系.8A上重要關系的實例定義7.5設A為集合,(1)是A上的關系，稱為空關系(2)

全域關系

EA={<x,y>|x∈A∧y∈A}=A×A恒等關系IA

={<x,x>|x∈A}小于等于關系LA

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

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

包含關系R={<x,y>|x,y∈A∧xy},A是集合族.9實例例如,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上的包含關系是

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

類似的還可以定義：大于等于關系,小于關系,大于關系,真包含關系等.10關系的表示1.關系矩陣若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B的關系，R的關系矩陣是布爾矩陣MR=[rij

]mn,其中

rij

=1<xi,yj>R.2.關系圖若A={x1,x2,…,xm}，R是從A上的關系，R的關系圖是GR=<A,R>,其中A為結點集，R為邊集.如果<xi,xj>屬于關系R，在圖中就有一條從xi到xj的有向邊.注意：關系矩陣適合表示從A到B的關系或A上的關系（A,B為有窮集）關系圖適合表示有窮集A上的關系11實例例4A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關系矩陣MR和關系圖GR如下：127.3關系的運算關系的基本運算定義7.6關系的定義域、值域與域分別定義為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關系運算(逆與合成)定義7.7關系的逆運算R1={<y,x>|<x,y>R}定義7.8關系的合成運算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合成的圖示法利用圖示（不是關系圖）方法求合成

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

SR={<1,2>,<1,4>,<3,2>,<3,3>}15關系運算(限制與像)定義7.9設R為二元關系,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的子關系，即R?ARA在R下的像R[A]是ranR

的子集，即R[A]ranR

16實例例7設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關系運算的性質定理7.1設F是任意的關系,則(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設F,G,H是任意的關系,則(1)(FG)H=F(GH)(2)(FG)1=G1F1關系運算的性質證(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關系運算的性質定理7.3設R為A上的關系,則

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關系運算的性質定理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的結論可以推廣到有限多個關系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關系運算的性質定理7.5設F為關系,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關系的冪運算定義7.10設R為A上的關系,n為自然數(shù),則R的n次冪定義為：(1)R0={<x,x>|x∈A}=IA(2)

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

對于A上的任何關系R都有R1=R27

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

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

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

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

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

RmR0=RmIA=Rm=Rm+0

假設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

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

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

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

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

(1)若xy(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對稱的關系.(2)若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),則稱R為A上的反對稱關系.實例：對稱關系：A上的全域關系EA,恒等關系IA和空關系反對稱關系：恒等關系IA和空關系也是A上的反對稱關系.設A＝{1,2,3},R1,R2,R3和R4都是A上的關系,其中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設R為A上的關系,若

xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),則稱R是A上的傳遞關系.實例：A上的全域關系EA,恒等關系IA和空關系，小于等于和小于關系，整除關系，包含與真包含關系設A＝{1,2,3},R1,R2,R3是A上的關系,其中R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}R1和R3是A上的傳遞關系,R2不是A上的傳遞關系.36關系性質成立的充要條件定理7.9設R為A上的關系,則(1)R在A上自反當且僅當IAR(2)R在A上反自反當且僅當R∩IA=(3)R在A上對稱當且僅當R=R1(4)R在A上反對稱當且僅當R∩R1IA(5)R在A上傳遞當且僅當RRR

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

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

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.不難驗證R為A上的等價關系,因為(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等價關系的關系圖等價關系的實例41等價類定義定義7.16設R為非空集合A上的等價關系,x∈A，令[x]R

={y|y∈A∧xRy}稱[x]R為x關于R的等價類,簡稱為x的等價類,簡記為[x]或實例A={1,2,…,8}上模3等價關系的等價類：[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}42等價類的性質定理7.14設R是非空集合A上的等價關系,則(1)xA,[x]是A的非空子集(2)x,yA,如果xRy,則[x]=[y](3)x,yA,如果x

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

A/R={[x]R|x∈A}實例設A={1,2,…,8}，A關于模3等價關系R的商集為

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

A/IA

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

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

P(A))滿足:(1)

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

12351232123412331對應EA,5對應IA,2,3和

4分別對應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偏序關系

主要內容偏序關系偏序關系的定義偏序關系的實例偏序集與哈斯圖偏序集中的特殊元素及其性質極大元、極小元、最大元、最小元上界、下界、最小上界、最大下界46定義與實例定義7.19偏序關系：非空集合A上的自反、反對稱和傳遞的關系，記作?.設?為偏序關系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.實例集合A上的恒等關系IA是A上的偏序關系.小于或等于關系,整除關系和包含關系也是相應集合上的偏序關系.47相關概念定義7.20設R為非空集合A上的偏序關系,(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上的偏序關系,(1)x,y∈A,x與y都是可比的，則稱R為全序（或線序）實例：數(shù)集上的小于或等于關系是全序關系,整除關系不是正整數(shù)集合上的全序關系定義7.22

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

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

解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實例51偏序集中的特殊元素

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