離散數(shù)學(xué)教材(與“關(guān)系”相關(guān)共184張)

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

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

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

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

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

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

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

DiscreteMathematicswithCombinatorics

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

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

第二部分集合論

第三部分代數(shù)結(jié)構(gòu)

第四部分圖論

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

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

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

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

{3,1,2}={1,2,3}本書規(guī)定:集合的元素都是集合.6.1集合的基本概念元素(Element)和集合之間的隸屬關(guān)系:“屬于”或“不屬于”.“屬于”關(guān)系記作,“不屬于”記作.例如:A={a,{b,c},d,{mouicm6}}. aA,{b,c}A,dA,{qmg2amy}A, bA,kw8sgmaA. b和sucqaga是A元素的元素.為了體系的嚴(yán)謹(jǐn)性,規(guī)定:對(duì)任何集合A,都有:AA.A={a,{b,c},d,{suaaeyo}}的樹形圖表示.a{b,c}Ad{oauy20k}bc64yiciad6.1集合的基本概念如果B不被A包含,則記作BA.包含的符號(hào)化表示為

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

B.相等的符號(hào)化表示為 A=B

AB∧BA

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

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

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

x}.例如:{x|xR∧x2+1=0}是方程x2+1=0的實(shí)數(shù)解集,因?yàn)樵摲匠虩o實(shí)數(shù)解,所以,其解集是空集.定理6.1空集是一切集合的子集.任給一個(gè)集合A,由子集的定義可知:

Ax(xxA)由于蘊(yùn)涵式(x

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

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

2,2

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

Complement).定義6.7設(shè)A和B為集合,A與B的并集A∪B,交集A∩B,B對(duì)A的相對(duì)補(bǔ)集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的元素構(gòu)成,A∩B由A和B的公共元素構(gòu)成,A-B由屬于A,但不屬于B的元素構(gòu)成.例如: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=若兩個(gè)集合的交集為,則稱這兩個(gè)集合是不相交的.如:B和C是不相交的.

6.2集合的運(yùn)算n個(gè)集合的并和交:無窮多個(gè)集合的并和交:∪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集合的運(yùn)算例如A={a,b,c},B={b,d},則:AB={a,c,d}對(duì)稱差運(yùn)算的另一種定義是 AB=(A∪B)-(B∩A)在給定全集E以后,AE,A的絕對(duì)補(bǔ)集~A定義如下:集合的對(duì)稱差集(Symmetric

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

AB=(A-B)∪(B-A)6.2集合的運(yùn)算EEBEB文氏圖(VennDiagrams)EABA∩B=AA∩B=AEABA-BEABA∪BEABA∩BEA~AAABB(A∩B)-CAC6.2集合的運(yùn)算例6.2對(duì)24名人員掌握外語情況的調(diào)查.其統(tǒng)計(jì)結(jié)果如下:解令A(yù),B,C和D分別表示會(huì)英、法、德、日語的人的集合.設(shè)同時(shí)會(huì)三種語言的有x人,只會(huì)英、法或德語一種語言的分別為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會(huì)英、日、德、法分別為:13,5,10和9人;同時(shí)會(huì)英語和日語的有2人;會(huì)英、德和法語中任兩種語言的都是4人.已知會(huì)日語的人既不懂法語也不懂德語,分別求只會(huì)一種語言(英、德、法、日)的人數(shù)和會(huì)三種語言的人數(shù).6.2集合的運(yùn)算41BAC例6.3求1到1000之間(包含1和1000在內(nèi)),既不能被5和6,也不能被8整除的數(shù)有多少個(gè).解設(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集合的運(yùn)算定理6.2(包含排斥原理)設(shè)S為有窮集,P1,P2,…,Pm是m個(gè)性質(zhì).S中的任何元素x或者具有性質(zhì)Pi,或者不具有性質(zhì)Pi(i=1..m),兩種情況必居其一.

令A(yù)i表示S中具有性質(zhì)Pi的元素構(gòu)成的子集,則S中不具有性質(zhì)P1,P2,…,Pm的元素?cái)?shù)為:6.2集合的運(yùn)算推論S中至少具有一條性質(zhì)的元素?cái)?shù)為根據(jù)包含排斥原理,例6.3中所求的元素?cái)?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以上定義的并和交運(yùn)算稱為初級(jí)并和初級(jí)交.下面考慮推廣的并和交運(yùn)算,即廣義并和廣義交.6.2集合的運(yùn)算定義6.10設(shè)A為集合,A的元素的元素構(gòu)成的集合稱為A的廣義并,記為∪A.符號(hào)化表示為:

∪A={x|z(zA∧xz)}根據(jù)廣義并的定義不難得到:若A={A1,A2,…,An},則 ∪A=A1∪A2∪…∪An類似地可以定義集合的廣義交.例6.4設(shè) 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集合的運(yùn)算例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設(shè)A為非空集合,A的所有元素的公共元素所構(gòu)成的集合稱為A的廣義交,記為∩A.符號(hào)化表示為 ∩A={x|z(zA

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

=;空集不可進(jìn)行廣義交,因?yàn)椤刹皇羌?

在集合論中是沒有意義的;若A={A1,A2,…,An},則∩A=A1∩A2∩…∩An.6.2集合的運(yùn)算稱廣義并,廣義交,冪集,絕對(duì)補(bǔ)運(yùn)算為一類運(yùn)算,并,交,相對(duì)補(bǔ)和對(duì)稱差運(yùn)算為二類運(yùn)算.下面的集合公式都是合理的公式:∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)一類運(yùn)算優(yōu)先于二類運(yùn)算一類運(yùn)算之間由右向左順序進(jìn)行二類運(yùn)算之間右括號(hào)決定先后順序6.2集合的運(yùn)算例6.5設(shè)A={{a},{a,b}},計(jì)算∪∪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集合的運(yùn)算冪等率–IdempotentLawsA∪A=A (6.1)A∩A=A (6.2)結(jié)合律–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)證對(duì)任意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.證對(duì)任意x,xA∩E

xA∧xE

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

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

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

就是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假設(shè)已知等式6.1-6.14,試證等式6.15:

A∪(A∩B)=A.6.3集合恒等式還有一些關(guān)于集合運(yùn)算性質(zhì)的重要結(jié)果.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.證對(duì)于任意的x, xA-B xA∧xB xA∧x~B xA∩~B所以,A-B=A∩~B.等式6.27把相對(duì)補(bǔ)運(yùn)算轉(zhuǎn)換成交運(yù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對(duì)于任意的x,xAxA∨xBxA∪BxB(因?yàn)锳∪B=B)所以,AB.

2).證ABA∩B=A

顯然有A∩BA,下面證:AA∩B.對(duì)于任意的x,xAxA∧xAxA∧xB(因?yàn)锳B)xA∩B由集合相等的定義有:A∩B=A.

3).證:A∩B=AA-B=A-B=A∩~B=(A∩B)∩~B(因?yàn)锳∩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)解因?yàn)锳∪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是關(guān)于對(duì)稱差運(yùn)算的算律;前四條可通過對(duì)稱差的定義加以證明;最后一條叫做消去律.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集合恒等式第七章二元關(guān)系7.1有序?qū)εc笛卡兒積7.2二元關(guān)系7.3關(guān)系的運(yùn)算7.4關(guān)系的性質(zhì)7.5關(guān)系的閉包7.6等價(jià)關(guān)系與劃分7.7偏序關(guān)系有序?qū)?lt;x,y>具有以下性質(zhì):當(dāng)x

y時(shí),<x,y>

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

y時(shí),有:{x,y}={y,x}.原因在于有序?qū)χ械脑厥怯行虻?而集合中的元素是無序的.定義7.1由兩個(gè)元素x和y按一定順序排列成的二元組叫做一個(gè)有序?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設(shè)A和B為集合,用A中元素為第一元素,B中元素為第二元素構(gòu)成有序?qū)?笛卡兒積的符號(hào)化表示為:AB={<x,y>|xA,yB}例如,設(shè)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>}由排列組合的知識(shí)不難證明,如果|A|=m,|B|=n,則|AB|=mn.所有這樣的有序?qū)M成的集合叫做A和B的笛卡兒積(CartesianProduct/ProductSet),記作AB.7.1有序?qū)εc笛卡兒積笛卡兒積運(yùn)算具有以下性質(zhì):1.對(duì)任意集合A,根據(jù)定義有A=,A=2.一般地說,笛卡兒積運(yùn)算不滿足交換律,即AB

BA(當(dāng)A

B,A

,B

時(shí))3.笛卡兒積運(yùn)算不滿足結(jié)合律,即(AB)C

A(BC)(當(dāng)A

,B

,C

時(shí))7.1有序?qū)εc笛卡兒積4.笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律,即(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設(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>}7.1有序?qū)εc笛卡兒積例7.3設(shè)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).不一定為真.當(dāng)A=,B={1},C={2}時(shí),有:AB=AC=,但,B

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

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

當(dāng)A=B時(shí),則稱該關(guān)系為A上的二元關(guān)系.例如:A={0,1},B={1,2,3},那么, R1={<0,2>} R2=AB R3=

R4={<0,1>}都是從A到B的二元關(guān)系,且R3和R4也是A上的二元關(guān)系.7.2二元關(guān)系對(duì)于任何集合A,稱空集為A上的空關(guān)系.下面定義A上的全域關(guān)系EA(UniversalRelation)和恒等關(guān)系IA(IdentityRelation).定義7.5對(duì)任意集合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二元關(guān)系除上面三種特殊關(guān)系(空關(guān)系,全域關(guān)系和恒等關(guān)系)之外,還有一些常用的關(guān)系,分別說明如下: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上的小于等于()關(guān)系,DB叫做B上的整除關(guān)系,其中x是y的因子,R叫做A上的包含關(guān)系.例如,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>}類似地,還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等.7.2二元關(guān)系例7.4設(shè)A={1,2,3,4},下面各式定義的R都是A上的關(guān)系,試用列元素法表示R.(1)R={<x,y>|x是y的倍數(shù)}(2)R={<x,y>|(x-y)2A}(3)R={<x,y>|x/y是素?cái)?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二元關(guān)系給出一個(gè)關(guān)系的方法有三種:集合表達(dá)式,關(guān)系矩陣和關(guān)系圖.例7.4中的關(guān)系是用集合表達(dá)式來給出的,對(duì)于有窮集A上的關(guān)系還可用其他兩種方式來給出.設(shè)A={x1,x2,...,xn

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

R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},則R的關(guān)系矩陣是7.2二元關(guān)系t(<t,x>f∧<t,y>f)(f:A→B是雙射)2設(shè)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設(shè)A={1,2,3,4},下面各式定義的R都是A上的關(guān)系,試用列元素法表示R.x“小于或等于”y的含義是:依照這個(gè)序,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若一個(gè)集合滿足以下條件之一:<x,y>Rn+1=RnR1<x,y>R∧<x,y>R-1從以上定義可以看出:最小元與極小元是不一樣的.設(shè)A={x1,x2,...,xn},R是A上的關(guān)系.令:圖G=<V,E>,其中頂點(diǎn)集合V=A,邊集為E.對(duì)于x1,x2V,滿足:<x1,x2>E<x1,x2>R,稱圖G為R的關(guān)系圖,記作GR.例如,A={1,2,3,4},

R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},則R的關(guān)系圖GR如下圖所示.7.2二元關(guān)系(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域(Range),記作ranR.其形式化表示為:

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

FG={<x,y>|t(<x,t>G∧<t,y>F)}7.3關(guān)系的運(yùn)算定義7.9設(shè)R為二元關(guān)系,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的子關(guān)系,A在R下的像R[A]是ranR的子集.RR|AAR[A]7.3關(guān)系的運(yùn)算例7.7設(shè)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關(guān)系的運(yùn)算下面討論關(guān)系基本運(yùn)算的性質(zhì).定理7.1設(shè)F是任意的關(guān)系,則 (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關(guān)系的運(yùn)算定理7.2設(shè)F,G和H是任意關(guān)系,則 (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關(guān)系的運(yùn)算定理7.2設(shè)F,G和H是任意關(guān)系,則 (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關(guān)系的運(yùn)算定理7.3設(shè)R為A上的關(guān)系,則,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關(guān)系的運(yùn)算定理7.4設(shè)F、G和H為任意關(guān)系,則:

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

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

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

(4).(G∩H)FGF∩HF證只證結(jié)論(3)7.3關(guān)系的運(yùn)算<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ù)學(xué)歸納法不難證得:定理7.4的結(jié)論,對(duì)于n個(gè)關(guā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關(guān)系的運(yùn)算定理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]證只證(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關(guān)系的運(yùn)算定理7.5設(shè)F為關(guān)系,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關(guān)系的運(yùn)算定義7.10設(shè)R為A上的關(guān)系,n為自然數(shù),則R的n次冪定義為: (1).R0={<x,x>|xA}=IA (2).Rn+1=Rn

R也就是說,A上任何關(guān)系的0次冪都相等,都等于A上的恒等關(guān)系IA.此外,對(duì)A的任何關(guān)系R都有R1=R,因?yàn)?R1=R0

R=IA

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

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

—

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

1)Rm

Rn=Rm+n

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

R0=Rm

IA=Rm=Rm+01.2).假設(shè):Rm

Rn=Rm+n,則有:

Rm

Rn+1=Rm

(Rn

R)=(Rm

Rn)

R=Rm+n

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

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

(Rm)n+1=(Rm)n

Rm=Rm*n

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

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

Rk=Rt

Rk=Rt+k

2).對(duì)k進(jìn)行歸納.2.1).若k=0,則有:Rs+0p+i=Rs+i2.2).假設(shè):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).對(duì)kN,有:Rs+k=Rt+k2).對(duì)k,iN,有:Rs+kp+i=Rs+i,其中p=t-s3).令S={R0,R1,...,Rt-1},則qN,有:RqS7.3關(guān)系的運(yùn)算3).令S={R0,R1,...,Rt-1},則對(duì)于任意的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關(guān)系的運(yùn)算由上面定理可知:有窮集A上的關(guān)系R的冪序列R0,R1,R1,R2,...是一個(gè)周期性變化的序列.利用該周期性可將R的高次冪化簡為R的低次冪.例7.9設(shè)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的右復(fù)合運(yùn)算下有下述變化規(guī)律:abab...defdef...對(duì)于a和b,它們的變化周期是2;對(duì)于d,e,f,它們的變化周期是3,因此,一定有:Rm=Rm+6,其中6是2和3的最小公倍數(shù).所以,取:m=0,n=6,即可滿足本題要求.7.3關(guān)系的運(yùn)算(1)若x(xA

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

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

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

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

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

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

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

IA (5).R在A上是傳遞的,當(dāng)且僅當(dāng)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關(guān)系的性質(zhì)定理7.9設(shè)R為A上的關(guān)系,則

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

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

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

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

<x,x>R

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

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

(3.1)必要性假設(shè):R在A上是對(duì)稱的.任取<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上是對(duì)稱的.7.4關(guān)系的性質(zhì)定理7.9設(shè)R為A上的關(guān)系,則

(4).R在A上是反對(duì)稱的,當(dāng)且僅當(dāng)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上是反對(duì)稱的.7.4關(guān)系的性質(zhì)定理7