離散數(shù)學教材(與“關系”相關共184張)

離散數(shù)學電子與通信工程系韋寶典耿素云屈婉玲DiscreteMathematics信息科學與技術學院計算機科學系吳向軍，黃劍《離散數(shù)學》(修訂版)

耿素云、屈婉玲,高等教育出版社,2004年教材《離散數(shù)學》

王兵山、王長英、周賢林、何自強編,國防科技大學出版社,1985年《離散數(shù)學》

檀鳳琴、何自強編著,科學出版社,1999年《離散數(shù)學》

孫吉貴、楊鳳杰、歐陽丹彤和李占山,高等教育出版社,2002年《離散數(shù)學》

左孝凌、李為鑒、劉永才編,上?？萍嘉墨I出版社,2002年DiscreteMathematicalStructures(FourthEdition)

BernardKolman,RobertC.B.&SharonC.R.高等教育出版社,2001年

DiscreteMathematicswithCombinatorics

JamesA.Anderson清華大學出版社,2004年DiscreteMathematics(FifthEdition)

KennethA.Ross,CharlesR.B.Wright清華大學出版社,2003年教學參考書…根據(jù)作者的教學經(jīng)驗,本教材要在160學時內(nèi)完成全部教學內(nèi)容.如果采用120學時的教學計劃,可略去第9章,第12章,第18章和第11章的部分內(nèi)容.軟件學院的教學計劃是一個學期講解《離散數(shù)學》,有:18周4學時/周,共72學時.如果遇到節(jié)假日,可能還會減少2學時,習題課還需用掉10左右學時,用于講課的時間可能在60學時左右.所以,計劃講解第二部分和第四部分的主要內(nèi)容.前言教材目錄第一部分數(shù)理邏輯

第二部分集合論

第三部分代數(shù)結構

第四部分圖論

附錄—部分中英文對照第一章命題邏輯基本概念第二章命題邏輯等值演算第三章命題邏輯的推理理論第四章一階邏輯基本概念第五章一階邏輯等值演算與推理第一部分數(shù)理邏輯有事可以隨時離開教室；請將手機調(diào)為震動；如果鈴聲真的響了，請不要在課上接電話；如果實在想接，goto1上課要求第六章集合代數(shù)第七章二元關系第八章函數(shù)第九章集合的基數(shù)第二部分集合論6.1集合的基本概念6.2集合的運算6.3集合恒等式第六章集合代數(shù)6.1集合的基本概念方程x2-1=0的實數(shù)解集合,1和-1是該集合的元素;26個英文字母的集合,a,b,…,z是該集合的元素;坐標平面上所有點的集合;

<0,0>,<0,1>,<1,1>是該集合的元素;常用的集合名稱:N:自然數(shù)集合(本課程中認為0也是自然數(shù))Z:整數(shù)集合 Q:有理數(shù)集合R:實數(shù)集合 C:復數(shù)集合集合(Set)是一些個體匯集在一起所組成整體.通常把整體中的個體稱為集合的元素或成員.例如:集合有三種表示方法:列元素法、謂詞表示法和圖示法.列元素法:列出集合中的所有元素,各元素之間用逗號隔開,并把它們用花括號括起來.例如A={a,b,c,…,z}Z={0,±1,±2,…}謂詞表示法:用謂詞來概括集合中元素的屬性.例如:B={x|x

R且x2-1=0}集合B表示方程x2-1=0的實數(shù)解集.許多集合可用兩種方法來表示,如:B={-1,1}.有些集合不能用列元素法表示,如:實數(shù)集合,不能列舉出所有集合中的所有元素.圖示法:用一個圓來表示,圓中的點表示集合中的元素.6.1集合的基本概念集合的元素是彼此不同的.若同一個元素在集合中多次出現(xiàn),則只認為其是一個元素;

如:{1,1,2,2,3}={1,2,3}集合的元素是無序的,如:

{3,1,2}={1,2,3}本書規(guī)定:集合的元素都是集合.6.1集合的基本概念元素(Element)和集合之間的隸屬關系:“屬于”或“不屬于”.“屬于”關系記作,“不屬于”記作.例如:A={a,{b,c},d,{yvx6un0}}. aA,{b,c}A,dA,{kuegq2e}A, bA,8bgppe6A. b和dutba0t是A元素的元素.為了體系的嚴謹性,規(guī)定:對任何集合A,都有:AA.A={a,{b,c},d,{goul5cn}}的樹形圖表示.a{b,c}Ad{v0726my}bc2yq5l62d6.1集合的基本概念如果B不被A包含,則記作BA.包含的符號化表示為

BAx(xBxA)例如:NZQRC,但,ZN.顯然,對任何集合A,都有:AA.包含關系表示集合之間的關系;隸屬關系表示元素和集合之間的關系,但也可表示某些集合之間關系.如: {a}{a,{a}},{a}{a,{a}}定義6.1設A和B為集合,若B中的每個元素都是A的元素,則稱B是A的子集合,簡稱子集(Subset),也可稱B被A包含,或A包含B,記作BA.AB6.1集合的基本概念：等值的：蘊涵式定義6.2設A和B為集合,如果AB且BA,則稱A與B相等,記作:A=B.若A與B不相等,則記作:A

B.相等的符號化表示為 A=B

AB∧BA

x(xAxB)∧x(xBxA)定義6.3設A和B為集合,如果BA且B

A,則稱B是A的真子集(ProperSubset),記作BA.若B不是A的真子集,則記為:BA.真子集的符號化表示為:BABA∧B

A例如:NZQRC,但,NN.6.1集合的基本概念定義6.4不含任何元素的集合叫做空集,記作:.空集可以符號化表示為:={x|x

x}.例如:{x|xR∧x2+1=0}是方程x2+1=0的實數(shù)解集,因為該方程無實數(shù)解,所以,其解集是空集.定理6.1空集是一切集合的子集.任給一個集合A,由子集的定義可知:

Ax(xxA)由于蘊涵式(x

xA)的前件為假而使其成為真命題,所以,

A.6.1集合的基本概念證假設:存在空集1和2.由定理6.1可知:1

2,2

1.由集合相等的定義可知:1=2.推論空集是惟一的.證例6.1A={1,2,3},將A的子集分類:假設有一個含有n個元素的集合A,若集合A1是其子集且|A1|=m,則稱子集A1為集合A的m元子集.對任給一個n元集合A,如何求出它的全部子集?0元子集,即空集,只有一個:;1元子集,即單元集:{1},{2},{3};2元子集:{1,2},{1,3},{2,3};3元子集:{1,2,3}.由上面的例子,我們不難歸納出:對n元集合A,有:0元子集有Cn0個1元子集有Cn1個…m元子集有Cnm個…n元子集有Cnn個子集總數(shù)為Cn0+Cn1+…+Cnn=2n個定義集合A中元素的個數(shù)n為集合的勢(Cardinality),記為|A|.6.1集合的基本概念全集是有相對性的,不同的問題有不同的全集,即使是同一個問題也可以取不同的全集.例如:在研究平面上直線的相互關系時,可把整個平面上所有點的集合看作全集,也可把整個空間上所有點的集合看作全集.一般地說,全集取得小一些,問題的描述和處理會簡單些.冪集的符號化表示為:P(A)={x|xA}.對于集合A={1,2,3},有:P(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.不難看出,若A是n元集,則P(A)有2n個元素.定義6.6在某具體問題中,若所涉及的集合都是某個集合的子集,則稱該集合為全集(UniversalSet),記作E.定義6.5設A為集合,把A的全體子集構成的集合叫做A的冪集(PowerSet),記作P(A),PA,2A.6.1集合的基本概念集合的基本運算有并(Union),交(Intersection)和相對補(Relative

Complement).定義6.7設A和B為集合,A與B的并集A∪B,交集A∩B,B對A的相對補集A-B分別定義如下:A∪B={x|x

A∨x

B}A∩B={x|x

A∧x

B}A-B={x|x

A∧xB}由定義可知:A∪B是由A或B的元素構成,A∩B由A和B的公共元素構成,A-B由屬于A,但不屬于B的元素構成.例如:A={a,b,c},B={a},C={b,d},則: A∪B={a,b,c} A∩B={a}A-B={b,c} B-A=,B∩C=若兩個集合的交集為,則稱這兩個集合是不相交的.如:B和C是不相交的.

6.2集合的運算n個集合的并和交:無窮多個集合的并和交:∪i=1..∞Ai=A1∪A2∪…∩i=1..∞Ai=A1∩A2∩…∪i=1..nAi=A1∪A2∪…∪An={x|xA1∨…∨xAn)∩i=1..nAi=A1∩A2∩…∩An={x|xA1∧…∧xAn)6.2集合的運算例如A={a,b,c},B={b,d},則:AB={a,c,d}對稱差運算的另一種定義是 AB=(A∪B)-(B∩A)在給定全集E以后,AE,A的絕對補集~A定義如下:集合的對稱差集(Symmetric

Difference)和絕對補集(AbsoluteComplement).定義6.9~A=E–A={x|xE∧xA}因為E是全集,xE是真命題,所以,~A可以定義為~A={x|xA}.例如:E={a,b,c,d},A={a,b,c},則, ~A=9b3auwy.定義6.8設A和B為集合,A與B的對稱差集AB定義為:

AB=(A-B)∪(B-A)6.2集合的運算EEBEB文氏圖(VennDiagrams)EABA∩B=AA∩B=AEABA-BEABA∪BEABA∩BEA~AAABB(A∩B)-CAC6.2集合的運算例6.2對24名人員掌握外語情況的調(diào)查.其統(tǒng)計結果如下:解令A,B,C和D分別表示會英、法、德、日語的人的集合.設同時會三種語言的有x人,只會英、法或德語一種語言的分別為y1,y2和y3.畫出的圖如右圖.列出下面方程組:y1+2(4-x)+x+2=13y2+2(4-x)+x=9y3+2(4-x)+x=10y1+y2+y3+3(4-x)+x=19解得:x=1,y1=4,y2=3,y3=3.y224-xy1x4-x4-xy35-2DACB會英、日、德、法分別為:13,5,10和9人;同時會英語和日語的有2人;會英、德和法語中任兩種語言的都是4人.已知會日語的人既不懂法語也不懂德語,分別求只會一種語言(英、德、法、日)的人數(shù)和會三種語言的人數(shù).6.2集合的運算41BAC例6.3求1到1000之間(包含1和1000在內(nèi)),既不能被5和6,也不能被8整除的數(shù)有多少個.解設S={x|xZ∧1

x

1000}A={x|xS∧x可被5整除}B={x|xS∧x可被6整除}C={x|xS∧x可被8整除}|A|=int(1000/5)=200|B|=int(1000/6)=166|C|=int(1000/8)=125|A∩B|=int(1000/lcm(5,6))=33|A∩C|=int(1000/lcm(5,8))=25|B∩C|=int(1000/lcm(6,8))=41|A∩B∩C|=int(1000/lcm(5,6,8))=81000-(200+100+33+67)=600171502581333320016612516733672510059+A∩B∩C6.2集合的運算定理6.2(包含排斥原理)設S為有窮集,P1,P2,…,Pm是m個性質(zhì).S中的任何元素x或者具有性質(zhì)Pi,或者不具有性質(zhì)Pi(i=1..m),兩種情況必居其一.

令Ai表示S中具有性質(zhì)Pi的元素構成的子集,則S中不具有性質(zhì)P1,P2,…,Pm的元素數(shù)為:6.2集合的運算推論S中至少具有一條性質(zhì)的元素數(shù)為根據(jù)包含排斥原理,例6.3中所求的元素數(shù)為:|A∩B∩C|=|S|-(|A|+|B|+|C|) +(|A∩B|+|A∩C|+|B∩C|)-|A∩B∩C| =1000-(200+166+125)+(33+25+41)-8=600以上定義的并和交運算稱為初級并和初級交.下面考慮推廣的并和交運算,即廣義并和廣義交.6.2集合的運算定義6.10設A為集合,A的元素的元素構成的集合稱為A的廣義并,記為∪A.符號化表示為:

∪A={x|z(zA∧xz)}根據(jù)廣義并的定義不難得到:若A={A1,A2,…,An},則 ∪A=A1∪A2∪…∪An類似地可以定義集合的廣義交.例6.4設 A={{a,b,c},{a,c,d},{a,e,f}} B={{a}} C={a,{c,d}}則 ∪A={a,b,c,d,e,f} ∪B={a} ∪C=a∪{c,d} ∪=6.2集合的運算例6.4: A={{a,b,c},{a,c,d},{a,e,f}} B={{a}}C={a,{c,d}}有: ∩A={a},∩B={a},∩C=a∩{c,d}定義6.11設A為非空集合,A的所有元素的公共元素所構成的集合稱為A的廣義交,記為∩A.符號化表示為 ∩A={x|z(zA

xz)}定義6.11中,特別強調(diào)A是非空集合;對于空集可以進行廣義并,即:∪

=;空集不可進行廣義交,因為∩不是集合;

在集合論中是沒有意義的;若A={A1,A2,…,An},則∩A=A1∩A2∩…∩An.6.2集合的運算稱廣義并,廣義交,冪集,絕對補運算為一類運算,并,交,相對補和對稱差運算為二類運算.下面的集合公式都是合理的公式:∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)一類運算優(yōu)先于二類運算一類運算之間由右向左順序進行二類運算之間右括號決定先后順序6.2集合的運算例6.5設A={{a},{a,b}},計算∪∪A,∩∩A和∩∪A∪(∪∪A-∪∩A).解 ∪A={a,b} ∩A={a} ∪∪A=a∪b ∩∩A=a ∩∪A=a∩b ∪∩A=a ∩∪A∪(∪∪A-∪∩A) =(a∩b)∪((a∪b)-a) =(a∩b)∪(b-a) =b所以∪∪A=a∪b,∩∩A=a, ∩∪A∪(∪∪A-∪∩A)=b.6.2集合的運算冪等率–IdempotentLawsA∪A=A (6.1)A∩A=A (6.2)結合律–AssociativeLaws(A∪B)∪C=A∪(B∪C) (6.3)(A∩B)∩C=A∩(B∩C) (6.4)交換律–CommutativeLawsA∪B=B∪A (6.5)A∩B=B∩A (6.6)分配律–DistributiveLawsA∪(B∩C)=(A∪B)∩(A∪C) (6.7)A∩(B∪C)=(A∩B)∪(A∩C) (6.8)6.3集合恒等式同一率–IdentityLaws

A∪=A (6.9)A∩E=A (6.10)零率–moreIdentitylaws

A∪E=E (6.11)A∩=

(6.12)排中率–ComplementationlawsA∪~A=E (6.13)A∩~A=

(6.14)6.3集合恒等式吸收率–

AbsorptionlawsA∪(A∩B)=A (6.15)A∩(A∪B)=A (6.16)德摩根律

–

DeMorganlawsA-(B∪C)=(A-B)∩(A-C) (6.17)A-(B∩C)=(A-B)∪(A-C) (6.18)~(B∪C)=~B∩~C (6.19)~(B∩C)=~B∪~C (6.20)~=E (6.21)~E=

(6.22)雙重否定率–

Double

Complementation~(~A)=A (6.23)6.3集合恒等式例6.6證明:A-(B∪C)=(A-B)∩(A-C) (式6.17)證對任意x, x

A-(B∪C)

xA∧xB∪C xA∧┐(xB∨xC) xA∧(┐xB∧┐xC) xA∧xB∧xC (xA∧xB)∧(xA∧xC) xA-B∧xA-C x(A-B)∩(A-C)所以,A-(B∪C)=(A-B)∩(A-C)6.3集合恒等式例6.7證明式6.10,即:A∩E=A.證對任意x,xA∩E

xA∧xE

xA(因為xE是恒真命題),所以,A∩E=A.以上證明的基本思想是:設P和Q為集合公式,欲證:

P=Q,即證PQ∧QP為真.要證對于任意的x有:

xPxQ和xQxP成立.對于某些恒等式,可將這兩個方向的推理合到一起,

就是xPxQ6.3集合恒等式證A∪(A∩B) =(A∩E)∪(A∩B) (6.10) =A∩(E∪B) (6.8) =A∩(B∪E) (6.5) =A∩E (6.11) =A (6.10)例6.8假設已知等式6.1-6.14,試證等式6.15:

A∪(A∩B)=A.6.3集合恒等式還有一些關于集合運算性質(zhì)的重要結果.A∩B

A,A∩BB (6.24)AA∪B,BA∪B (6.25)A-BA (6.26)A-B=A∩~B (6.27)A∪B=B

AB

A∩B=A

A-B=

(6.28)AB=BA (6.29)(AB)C=A(BC) (6.30)A

=A (6.31)AA= (6.32)AB=ACB=C (6.33)6.3集合恒等式例6.9證明等式6.27,即A-B=A∩~B.證對于任意的x, xA-B xA∧xB xA∧x~B xA∩~B所以,A-B=A∩~B.等式6.27把相對補運算轉(zhuǎn)換成交運算.6.3集合恒等式例6.10證明:(A-B)∪B=A∪B.證 (A-B)∪B =(A∩~B)∪B =(A∪B)∩(~B∪B) =(A∪B)∩E =A∪B6.3集合恒等式例6.11證明命題6.28是真命題:

A∪B=B

AB

A∩B=A

A-B=.證

1).證A∪B=BAB對于任意的x,xAxA∨xBxA∪BxB(因為A∪B=B)所以,AB.

2).證ABA∩B=A

顯然有A∩BA,下面證:AA∩B.對于任意的x,xAxA∧xAxA∧xB(因為AB)xA∩B由集合相等的定義有:A∩B=A.

3).證:A∩B=AA-B=A-B=A∩~B=(A∩B)∩~B(因為A∩B=A) =A∩(B∩~B)=A∩=4).證:A-B=

A∪B=B由例6.10及A-B=,有:A∪B=B∪(A-B)=B∪

=B6.3集合恒等式例6.12化簡((A∪B∪C)∩(A∪B))-((A∪(B-C))∩A)解因為A∪B

A∪B∪C,A

A∪(B-C),由式6.28: ((A∪B∪C)∩(A∪B))-((A∪(B-C))∩A) =(A∪B)-A =B-A式6.29～6.33是關于對稱差運算的算律;前四條可通過對稱差的定義加以證明;最后一條叫做消去律.6.3集合恒等式Why?3種方式說明證已知AB=AC,所以,有: A(AB)=A(AC) (6.30) (AA)B=(AA)C (6.32) B=C (6.29) B=C (6.31)例6.13已知AB=AC,證明:B=C.6.3集合恒等式第七章二元關系7.1有序?qū)εc笛卡兒積7.2二元關系7.3關系的運算7.4關系的性質(zhì)7.5關系的閉包7.6等價關系與劃分7.7偏序關系有序?qū)?lt;x,y>具有以下性質(zhì):當x

y時,<x,y>

<y,x>;<x,y>=<u,v>的充分必要條件是x=u且y=v.這些性質(zhì)是二元集{x,y}所不具備的.例如當x

y時,有:{x,y}={y,x}.原因在于有序?qū)χ械脑厥怯行虻?而集合中的元素是無序的.定義7.1由兩個元素x和y按一定順序排列成的二元組叫做一個有序?qū)蛐蚺?OrderedPair),記作<x,y>,其中x是它的第一元素,y是它的第二元素.7.1有序?qū)εc笛卡兒積例7.1已知<x+2,4>=<5,2x+y>,求x和y.解得:x=3,y=-2.解由有序?qū)ο嗟鹊某湟獥l件有7.1有序?qū)εc笛卡兒積定義7.2設A和B為集合,用A中元素為第一元素,B中元素為第二元素構成有序?qū)?笛卡兒積的符號化表示為:AB={<x,y>|xA,yB}例如,設A={a,b},B={0,1,2},則AB={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}BA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}由排列組合的知識不難證明,如果|A|=m,|B|=n,則|AB|=mn.所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積(CartesianProduct/ProductSet),記作AB.7.1有序?qū)εc笛卡兒積笛卡兒積運算具有以下性質(zhì):1.對任意集合A,根據(jù)定義有A=,A=2.一般地說,笛卡兒積運算不滿足交換律,即AB

BA(當A

B,A

,B

時)3.笛卡兒積運算不滿足結合律,即(AB)C

A(BC)(當A

,B

,C

時)7.1有序?qū)εc笛卡兒積4.笛卡兒積運算對并和交運算滿足分配律,即(1).A(B∪C)=(AB)∪(AC)(2).(B∪C)A=(BA)∪(CA)(3).A(B∩C)=(AB)∩(AC)(4).(B∩C)A=(BA)∩(CA)我們只證明等式(1).證任取<x,y>

<x,y>A(B∪C)

xA∧y(B∪C)

xA∧(yB∨yC) (xA∧yB)∨(xA∧yC) <x,y>AB∨<x,y>AC <x,y>(AB)∪(AC)7.1有序?qū)εc笛卡兒積5.A

C∧BDAB

CD性質(zhì)5的證明和性質(zhì)4類似,也采用命題演算的方法.注意性質(zhì)5的逆命題不成立,可分多種情況來討論.例7.2設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>}7.1有序?qū)εc笛卡兒積例7.3設A,B,C,D為任意集合,判斷以下命題是否為真,并說明理由.1).AB=ACB=C2).A-(BC)=(A-B)(A-C)3).A=B∧C=D

AC=BD4).存在集合A,使得:A

AA解1).不一定為真.當A=,B={1},C={2}時,有:AB=AC=,但,B

C.2).不一定為真.當A=B={1},C={2}時,A-(BC)={1}-{<1,2>}={1}(A-B)(A-C)={2}=3).真.可由等量代入的原理證得.4).真.當A=時,有:A

AA成立.7.1有序?qū)εc笛卡兒積定義7.3若一個集合滿足以下條件之一: (1).集合非空,且它的元素都是有序?qū)?(2).集合是空集 則稱該集合為二元關系(BinaryRelation),記作R,可簡稱為關系.若<x,y>R,可記作:xRy;否則,記作:xRy.例如:R1={<1,2>,<a,b>},R2={<1,2>,a,b},則R1是二元關系,R2不是二元關系.7.2二元關系集合A上二元關系的數(shù)目依賴于A中的元素數(shù).若|A|=n,則,|AA|=n2,AA的子集就有2n2個.因為每一個子集代表一個A上的二元關系,所以,A上有2n2個不同的二元關系.例如:|A|=3,則A上有232=512個不同的二元關系.定義7.4設A和B為集合,AB的任何子集所定義的二元關系叫做從A到B的二元關系.

當A=B時,則稱該關系為A上的二元關系.例如:A={0,1},B={1,2,3},那么, R1={<0,2>} R2=AB R3=

R4={<0,1>}都是從A到B的二元關系,且R3和R4也是A上的二元關系.7.2二元關系對于任何集合A,稱空集為A上的空關系.下面定義A上的全域關系EA(UniversalRelation)和恒等關系IA(IdentityRelation).定義7.5對任意集合A,定義: EA={<x,y>|x,yA}=AA IA={<x,x>|xA}例如,A={1,2},則 EA={<1,1>,<1,2>,<2,1>,<2,2>} IA={<1,1>,<2,2>}7.2二元關系除上面三種特殊關系(空關系,全域關系和恒等關系)之外,還有一些常用的關系,分別說明如下:LA={<x,y>|x,yA,x

y,A

R}DB={<x,y>|x,yB,x整除y,BZ*}R={<x,y>|x,yA,xy,A是集合族}LA叫做A上的小于等于()關系,DB叫做B上的整除關系,其中x是y的因子,R叫做A上的包含關系.例如,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>}類似地,還可以定義大于等于關系,小于關系,大于關系,真包含關系等.7.2二元關系例7.4設A={1,2,3,4},下面各式定義的R都是A上的關系,試用列元素法表示R.(1)R={<x,y>|x是y的倍數(shù)}(2)R={<x,y>|(x-y)2A}(3)R={<x,y>|x/y是素數(shù)}(4)R={<x,y>|x

y}解(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,

<2,3>,<1,2>}(3)R={<2,1>,<3,1>,<4,2>}(4)R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>, <3,2>,<3,4>,<4,1>,<4,2>,<4,3>}7.2二元關系給出一個關系的方法有三種:集合表達式,關系矩陣和關系圖.例7.4中的關系是用集合表達式來給出的,對于有窮集A上的關系還可用其他兩種方式來給出.設A={x1,x2,...,xn

},R是A上的關系.令則,R的關系矩陣MR如下所示.7.2二元關系例如,A={1,2,3,4},

R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},則R的關系矩陣是7.2二元關系t(<t,x>f∧<t,y>f)(f:A→B是雙射)2設F和G為函數(shù),則,F=GFG∧GF.Rs+k=RsRk=RtRk=Rt+k15:

A∪(A∩B)=A.A={a,b,c,d,e,f,g,h}t(<x,t>Rn∧<t,y>R1)4設A={1,2,3,4},下面各式定義的R都是A上的關系,試用列元素法表示R.x“小于或等于”y的含義是:依照這個序,x排在y的前邊或者x就是y.1的推論2可知:fIB:A→B和IAf:A→B.tsr(R)=t(s(r(R)))所以,(FG)-1=G-1F-1.(A-B)(A-C)={2}=函數(shù)值f(x)B,而

像f(A1)B.3若一個集合滿足以下條件之一:<x,y>Rn+1=RnR1<x,y>R∧<x,y>R-1從以上定義可以看出:最小元與極小元是不一樣的.設A={x1,x2,...,xn},R是A上的關系.令:圖G=<V,E>,其中頂點集合V=A,邊集為E.對于x1,x2V,滿足:<x1,x2>E<x1,x2>R,稱圖G為R的關系圖,記作GR.例如,A={1,2,3,4},

R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},則R的關系圖GR如下圖所示.7.2二元關系(2)R中所有有序?qū)Φ牡诙貥嫵傻募戏Q為R的值域(Range),記作ranR.其形式化表示為:

ranR={y|x(<x,y>R)}關系的基本運算有:定義域,值域,域,逆關系,右復合(左復合),限制和像等七種.定義7.6設R是二元關系R中所有有序?qū)Φ牡谝辉貥嫵傻募戏Q為R的定義域(Domain),記作domR.其形式化表示為: domR={x|y(<x,y>R)}(3)R的定義域和值域的并集稱為R的域(Field),記作fldR.其形式化表示為: fldR=domR∪ranRRXYdomRranRfldR7.3關系的運算例7.5設R={<1,2>,<1,3>,<2,4>,<4,3>},則 domR={1,2,4} ranR={2,3,4} fldR={1,2,3,4}定義7.7設R為二元關系,把R的逆關系(ConverseRelation)簡稱R的逆,記作R-1,其中 R-1={<x,y>|<y,x>R}定義7.8設F和G為二元關系,G對F的右復合FG(Composition)定義為: FG={<x,y>|t(<x,t>F∧<t,y>G)}例7.6設F={<3,3>,<6,2>},G={<2,3>},則 F-1={<3,3>,<2,6>} FG={<6,3>} GF={<2,3>}定義7.8’設F和G為二元關系,G對F的左復合FG定義為:

FG={<x,y>|t(<x,t>G∧<t,y>F)}7.3關系的運算定義7.9設R為二元關系,A是集合(1)R在A上的限制(Under),記作R|A,其中 R|A={<x,y>|<x,y>R,xA}(2)A在R下的像(Image),記作R[A],其中 R[A]=ran(R|A)不難看出:R在A上的限制R|A是R的子關系,A在R下的像R[A]是ranR的子集.RR|AAR[A]7.3關系的運算例7.7設R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}123423則, R|{2,3}={<2,2>,<2,4>,<3,2>} R|{1}={<1,2>,<1,3>} R|= R[{1}]={2,3} R[{3}]={2} R[]=7.3關系的運算下面討論關系基本運算的性質(zhì).定理7.1設F是任意的關系,則 (1).(F-1)-1=F (2).domF-1=ranF,ranF-1=domF證(1).任取<x,y>,由逆的定義可知: <x,y>(F-1)-1

<y,x>F-1

<x,y>F所以,有:(F-1)-1=F.(2).任取x,xdomF-1

y(<x,y>F-1)

y(<y,x>F)

xranF所以,有:domF-1=ranF.同理可證:ranF-1=domF.7.3關系的運算定理7.2設F,G和H是任意關系,則 (1).(FG)H=F(GH) (2).(FG)-1=G-1F-1證(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) st(<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)7.3關系的運算定理7.2設F,G和H是任意關系,則 (2).(FG)-1=G-1F-1證(2).任取<x,y>, <x,y>(FG)-1 <y,x>FG t(<y,t>F∧<t,x>G) t(<t,y>F-1∧<x,t>G-1)

t(<x,t>G-1∧<t,y>F-1) <x,y>G-1F-1所以,(FG)-1=G-1F-1.7.3關系的運算定理7.3設R為A上的關系,則,R

IA=IA

R=R.證任取<x,y>, <x,y>RIA t(<x,t>R∧<t,y>IA) t(<x,t>R∧t=y) <x,y>R <x,y>R <x,y>R∧yA <x,y>R∧<y,y>IA y(<x,y>R∧<y,y>IA) <x,y>RIA綜合上述可得:RIA=R.同理可證:IA

R=R.7.3關系的運算定理7.4設F、G和H為任意關系,則:

(1).F(G∪H)=FG∪FH

(2).(G∪H)F=GF∪HF

(3).F(G∩H)FG∩FH

(4).(G∩H)FGF∩HF證只證結論(3)7.3關系的運算<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∩FH2(<1,2>F∧<2,4>G∧<2,4>H)2(<1,2>F∧<2,4>G)∧2(<1,2>F∧<2,4>H)<1,4>FG∧<1,4>FH<1,4>(FG∩FH)2(<1,2>F∧<2,4>G)∧3(<1,3>F∧<3,4>H)2(<1,2>F∧<2,4>G∧<2,4>H)F={<1,2>,<1,3>}G={<2,4>}H={<3,4>}G∩H=F(G∩H)=FG={<1,4>}FH={<1,4>}(FG)∩(FH)={<1,4>}由數(shù)學歸納法不難證得:定理7.4的結論,對于n個關系的并和交也是成立的,即有: (1).R(R1∪R2∪…∪Rn)=RR1∪RR2∪…∪RRn (2).(R1∪R2∪…∪Rn)R=R1R∪R2R∪…∪RnR (3).F(R1∩R2∩…∩Rn)RR1∩RR2∩…∩RRn (4).(R1∩R2∩…∩Rn)RRR1∩R2R∩…∩RnR7.3關系的運算定理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]證只證(1)和(4).(1).任取<x,y>, <x,y>

F|(A∪B) <x,y>F∧xA∪B <x,y>F∧(xA∨xB) (<x,y>F∧xA)∨(<x,y>F∧xB) (<x,y>F|A)∨(<x,y>F|B) <x,y>(F|A∪F|B)所以,F|(A∪B)=F|A∪F|B.7.3關系的運算定理7.5設F為關系,A和B為集合,則

(4).F[A∩B]F[A]∩F[B](4).任取y, y

F[A∩B] x(<x,y>F∧xA∩B) x(<x,y>F∧xA∧xB) x(<x,y>F∧xA∧<x,y>F∧xB)

x(<x,y>F∧xA)∧x(<x,y>F∧xB) yF[A]∧yF[B] yF[A]∩F[B]所以,F[A∩B]F[A]∩F[B].7.3關系的運算定義7.10設R為A上的關系,n為自然數(shù),則R的n次冪定義為: (1).R0={<x,x>|xA}=IA (2).Rn+1=Rn

R也就是說,A上任何關系的0次冪都相等,都等于A上的恒等關系IA.此外,對A的任何關系R都有R1=R,因為 R1=R0

R=IA

R=R由以上定義可知:對于A上的任何關系R1和R2都有 R10=R20=IA7.3關系的運算給定A上的關系R和自然數(shù)n,如何計算Rn呢?若n是0或1,結果是很簡單的;下面考慮“n≥2”的情況.R是用集合表達式給出的,可以通過n-1次右復合計算得到Rn;R是用關系矩陣MR給出的,則Rn的關系矩陣是MRn,即n個矩陣MR之積.它與普遍矩陣乘法不同的是其相加是邏輯加,即: 1+1=1,1+0=0+1=1,0+0=0R是用關系圖G給出的,可直接由圖G得到Rn的關系圖G’:G’的頂點集與G相同;G的每個頂點xi,如果在G中從xi出發(fā)經(jīng)過n條邊到達頂點xj,則在G’中加一條從xi到xj的邊.當把所有這樣的邊都找到完時,所得到圖就是G’.7.3關系的運算例7.8設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,

<c,d>},求R的各次冪,分別用矩陣和關系圖來表示.解R的關系矩陣為7.3關系的運算abcdabcd因此,M4=M2,即R4=R2.由此可得: R2=R4=R6=... R3=R5=R7=...7.3關系的運算關系R0,即:IA的關系矩陣是至此,R各次冪的關系矩陣都得到了.用關系圖的方法得到R0,R1,R2,R3,…,的關系圖如下圖所示.7.3關系的運算定理7.6設A為n元集合,R是A上的關系,則存在自然數(shù)s和t,使得:Rs=Rt.證R為A上的關系,對任何自然數(shù)k,Rk都是AA的子集,又知|AA|=n2,|P(AA)|=2n2,即:AA共有2n2個不同的子集.當列出R的各次冪R0,R1,R2,R3,…,R2n2,…時,必存在自然數(shù)s和t,使得:Rs=Rt.(鴿籠原理

—

Pigeon-HolePrinciple)定理7.6說明:有窮集上只有有窮多個不同的二元關系.當t足夠大時,Rt必與前面某個Rs(s<t)相等.如例7.8中的R4=R2.7.3關系的運算定理7.7設R為A上的關系,m,nN,則

1)Rm

Rn=Rm+n

2)(Rm)n=Rmn證用歸納法1)對于任意給定的mN,對n進行歸納.1.1).若n=0,則有:Rm

R0=Rm

IA=Rm=Rm+01.2).假設:Rm

Rn=Rm+n,則有:

Rm

Rn+1=Rm

(Rn

R)=(Rm

Rn)

R=Rm+n

R=Rm+n+1所以,對一切m,nN,有:Rm

Rn=Rm+n.2)對于任意給定的mN,對n進行歸納.若n=0,則有:(Rm)0=IA=R0=Rm*0假設:(Rm)n=Rm*n,則有:

(Rm)n+1=(Rm)n

Rm=Rm*n

Rm=Rm*n+m=Rm(n+1)所以,對一切m,nN,有:(Rm)n=Rmn.7.3關系的運算定理7.8設R為A上的關系,若存在自然數(shù)s,t(s<t),使得:

Rs=Rt,則證1).Rs+k=Rs

Rk=Rt

Rk=Rt+k

2).對k進行歸納.2.1).若k=0,則有:Rs+0p+i=Rs+i2.2).假設:Rs+kp+i=Rs+i,其中p=t-s,則有: Rs+(k+1)p+i=Rs+pk+p+i=Rs+pk+i

Rp

=Rs+i

Rp=Rs+p+i=Rs+t-s+i=Rt+i=Rs+i由歸納法命題得證.1).對kN,有:Rs+k=Rt+k2).對k,iN,有:Rs+kp+i=Rs+i,其中p=t-s3).令S={R0,R1,...,Rt-1},則qN,有:RqS7.3關系的運算3).令S={R0,R1,...,Rt-1},則對于任意的qN,有:RqS證3).任取qN,3.1).若q<t,顯然有:RqS;3.2).若q≥t,則存在自然數(shù)k和i,使得:q=s+kp+i,其中:0

i

p-1.于是有:Rq=Rs+kp+i=Rs+i又 s+i

s+p-1=s+t-s-1=t-1顯然,RqS.7.3關系的運算由上面定理可知:有窮集A上的關系R的冪序列R0,R1,R1,R2,...是一個周期性變化的序列.利用該周期性可將R的高次冪化簡為R的低次冪.例7.9設A={a,b,c,d,e,f},R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>},求出最小的自然數(shù)m和n(m<n),使得:Rm=Rn.解由R的定義可以看出A中的元素可分成兩組,即:{a,b}和{d,e,f}.它們在R的右復合運算下有下述變化規(guī)律:abab...defdef...對于a和b,它們的變化周期是2;對于d,e,f,它們的變化周期是3,因此,一定有:Rm=Rm+6,其中6是2和3的最小公倍數(shù).所以,取:m=0,n=6,即可滿足本題要求.7.3關系的運算(1)若x(xA

<x,x>R),則稱R在A上是自反的;(2)若x(xA<x,x>R),則稱R在A上是反自反的.關系的性質(zhì)主要有:自反性(Reflexive),對稱性(Symmetric)和傳遞性(Transitive)

.除此之外,還有:反自反性(Anti-Reflexive)和反對稱性(Anti-Symmetric)

.定義7.11設R為A上的關系,A上的全域關系EA和恒等關系IA都是A上的自反關系小于等于關系LA,整除關系DB分別是A和B上的自反關系包含關系是給定集合簇A上的自反關系小于關系和真包含關系都是給定集合或集合簇上的反自反關系7.4關系的性質(zhì)例7.10設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>}說明R1,R2和R3是否為A上自反關系和反自反的關系.解 R1既不是自反的,也不是反自反的; R2是自反的; R3是反自反的;7.4關系的性質(zhì)定義7.12設R為A上的關系,(2)稱R在A上是反對稱的關系,若關系R滿足條件: xy(x,yA∧<x,y>R∧<y,x>Rx=y)(1)稱R在A上是對稱的關系,若關系R滿足條件: xy(x,yA∧<x,y>R

<y,x>R)A上的全域關系EA,恒等關系IA和空關系都是A上對稱的關系恒等關系IA和空關系都是A上反對稱的關系全域關系EA一般不是A上的反對稱關系,除非A為單元集或空集7.4關系的性質(zhì)例7.11設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是否為A上對稱和反對稱的關系.R1既是對稱的也是反對稱的R2是對稱的但不是反對稱的R3是反對稱的但不是對稱的R4既不是對稱的也不是反對稱的7.4關系的性質(zhì)例7.12設A={1,2,3},R1,R2和R3是A上的關系, R1={<1,1>,<2,2>} R2={<1,2>,<2,3>} R3={<1,3>}說明R1,R2和R3是否為A上的傳遞關系.解R1和R3是A上的傳遞關系,R2不是A上的傳遞關系.定義7.13設R為A上的關系,若

xyz(x,y,zA∧xRy∧yRz<x,z>R)

稱R為A上傳遞的關系.A上的全域關系EA,恒等關系IA和空關系都是A上的傳遞關系小于等于關系,整除關系,包含關系,小于關系和真包含關系是相應集合上的傳遞關系7.4關系的性質(zhì)下面給出關系五種性質(zhì)成立的充分必要條件.定理7.9設R為A上的關系,則 (1).R在A上是自反的,當且僅當IA

R (2).R在A上是反自反的,當且僅當R∩IA= (3).R在A上是對稱的,當且僅當R=R-1 (4).R在A上是反對稱的,當且僅當R∩R-1

IA (5).R在A上是傳遞的,當且僅當RRR證(1.1)必要性 <x,x>IA

xA由R在A上自反的可知:xA,都有:<x,x>R.所以,一定有:<x,x>IA

<x,x>R,即:IA

R.

(1.2)充分性任取x,有:xA<x,x>IA

<x,x>R.因此,R在A上是自反的.7.4關系的性質(zhì)定理7.9設R為A上的關系,則

(2).R在A上是反自反的,當且僅當R∩IA=證

(2.1)必要性(用反證法)假設R∩IA

,那么一定存在<x,y>R∩IA.由于IA是A上的恒等關系,從而推出xA且<x,x>R.這與R在A上是反自反的相矛盾.

(2.2)充分性任取x,則有: xA<x,x>IA

<x,x>R

(由于R∩IA=)從而證明了R在A上是反自反的.7.4關系的性質(zhì)定理7.9設R為A上的關系,則

(3).R在A上是對稱的,當且僅當R=R-1證

(3.1)必要性假設:R在A上是對稱的.任取<x,y>,有: <x,y>R

<y,x>R

<x,y>R-1所以,R=R-1.

(3.2)充分性任取<x,y>,由“R=R-1”可得: <x,y>R<y,x>R-1

<y,x>R所以,R在A上是對稱的.7.4關系的性質(zhì)定理7.9設R為A上的關系,則

(4).R在A上是反對稱的,當且僅當R∩R-1

IA證

(4.1)必要性任取<x,y>,有: <x,y>

R∩R-1 <x,y>R∧<x,y>R-1 <x,y>R∧<y,x>R x=y <x,y>IA

(4.2)

充分性任取<x,y>,有:

<x,y>

R∧<y,x>R <x,y>R∧<x,y>R-1

<x,y>R∩R-1 <x,y>IA x=y從而證明了R是A上是反對稱的.7.4關系的性質(zhì)定理7