第三章集合與關(guān)系-最終版

集合與關(guān)系的結(jié)構(gòu)圖枚舉法有向圖矩陣等價關(guān)系有向圖等價類商集劃分偏序關(guān)系相容類最大相容類完全覆蓋簡化圖全序哈斯圖計算方法運算性質(zhì)二元關(guān)系概念及表示方法性質(zhì)自反對稱傳遞反對稱反自反相容關(guān)系運算復合求逆閉包重要元素1第3章集合與關(guān)系離散數(shù)學河南工業(yè)大學信息科學與工程學院2第二篇集合論集合論是現(xiàn)代數(shù)學的基礎(chǔ)，幾乎與現(xiàn)代數(shù)學的各個分支都有著密切聯(lián)系，并且滲透到所有科技領(lǐng)域，是不可缺少的數(shù)學工具和表達語言。集合論的起源可以追溯到16世紀末期，為了追尋微積分的堅實基礎(chǔ)，開始時，人們僅進行了有關(guān)數(shù)集的研究。1876～1883年，康托爾(GeorgCantor)發(fā)表了一系列有關(guān)集合論研究的文章，奠定了集合論的深厚基礎(chǔ)。集合論在程序語言、數(shù)據(jù)結(jié)構(gòu)、編譯原理、數(shù)據(jù)庫與知識庫、形式語言和人工智能等領(lǐng)域都得到了廣泛的應用，并且還得到了發(fā)展。康托爾3第四章內(nèi)容（自學）第三章內(nèi)容（重點）第二篇集合論主要包括如下內(nèi)容：集合論初步二元關(guān)系函數(shù)實數(shù)集合與集合的基數(shù)4第三章集合與關(guān)系本章的主要內(nèi)容3-1集合的概念和表示法3-2集合的運算3-3包含排斥原理*3-4序偶和笛卡爾積3-5關(guān)系和表示3-6關(guān)系的性質(zhì)（重點）3-7復合關(guān)系和逆關(guān)系3-8關(guān)系的閉包（重點）3-9集合的劃分和覆蓋3-10等價關(guān)系與等價類（重點）3-11相容關(guān)系3-12序關(guān)系51-2節(jié)的內(nèi)容提要集合間的關(guān)系3特殊集合4集合的概念1集合的概念1集合的表示方法2集合的表示方法2無限集合5集合的運算561-2節(jié)學習要求重點掌握一般掌握11集合的概念及集合間關(guān)系2集合的表示3集合運算及定律4冪集P(A)

21集合的歸納法表示2集合的對稱差運算73-1集合一、集合的概念集合（SET）：即是由一些確定的彼此不同的客體（事物）匯集到一起組成一個整體，稱為集合。討論：客體：泛指一切，可以是具體的、抽象的。元素(element，成員)：

即組成集合的客體，稱之為元素。二、集合的記法通常用帶(不帶)標號的大寫字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用帶（不帶）標號的小寫字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。8固定的符號0,1,2,…自然數(shù)集合N…,-2,-1,0,1,2,…整數(shù)集合

Ip/q,p,q是整數(shù)，且q≠0

有理數(shù)集合

Q

實數(shù)集合

R復數(shù)集合

C9三、集合與元素的關(guān)系客體a與集合A之間的關(guān)系只能是屬于和不屬于之一。a是集合A的元素或a屬于集合A，記為aA，稱a是A的成員，A包含a，a在A中。a不是集合A的元素或a不屬于集合A，記為aA，或者(aA)，稱a不是A的成員，A不包含a，a不在A中。例如，對元素2和自然數(shù)集合N，就有2屬于N，即2N，對元素-2和自然數(shù)集合N，就有-2不屬于N，即-2N。有限集：組成集合的元素個數(shù)是有限的。|A|：有限集合A中元素的個數(shù)。無限集：組成集合的元素個數(shù)是無限的。10四、集合的表示方法集合是由它包含的元素完全確定的，為了表示一個集合，通常有：

枚舉法（列舉法）謂詞表示法（隱式法、敘述法）文氏(Venn)圖-輔助的集合的表示方法111、枚舉法（顯式表示法）就是把集合的元素（全部或部分）寫在花括號的里面，每個元素僅寫一次，不考慮順序，并用”,”分開。例

（1）命題的真假值組成的集合：S={T,F}

（2）A＝{a，e，i，o，u}12在使用中，分兩種情況：（1）當集合中元素個數(shù)有限且較少時，將元素全部寫出。例1：設集合A是由絕對值不超過3的整數(shù)組成。A={-3,-2,-1,0,1,2,3}（2）當集合A元素的個數(shù)無限或有限但個數(shù)較多時，不能或不需要一一列舉出來，只要寫出少數(shù)元素，以顯示出它的規(guī)律。（當規(guī)律不明確，不能用此方法）。例2：設集合B是由自然數(shù)的平方構(gòu)成的集合。B={0,1,4,9,16,…,n2,…}適用場景：一個集合僅含有限個元素。一個集合的元素之間有明顯關(guān)系。132、謂詞表示法（隱式法、敘述法）用謂詞描述集合中元素的屬性，稱為謂詞表示法（敘述法、隱式法）一般表示方法：A＝{x|P(x)}若個體域內(nèi)，客體a使得P(a)為真，則a∈A，否則aA。例如：大于10的整數(shù)的集合：S={x|x∈I∧x>10)}命題的真假值組成的集合：S={F,T}={x|x=F∨x=T}適用場景：一個集合含有很多或無窮多個元素；一個集合的元素之間有容易刻畫的共同特征。其突出優(yōu)點是原則上不要求列出集合中全部元素，而只要給出該集合中元素的特性。P(x)是謂詞公式，x具有的性質(zhì)P代表元素14A3、文氏(Venn)圖-輔助的集合的表示方法文氏(Venn)圖是一種利用平面上的點構(gòu)成的圖形來形象展示集合的一種方法，用一個矩形的內(nèi)部表示全集，其他集合用矩形內(nèi)的園面或一封閉曲線圈成的面積來表示。U15說明：集合中的元素都是不同的，凡是相同的元素，均視為同一個元素；{1,1,2}={1,2}一旦給定了集合A，對于任意客體a，可以準確地判定a是否在A中。

集合中的元素是沒有順序的。

{2,1}={1,2}集合的三大特征1、互異性－2、確定性－3、無序性－集合中的元素可以是集合。如S={a,{1,2},p,{q}}16同一個集合可以用不同的表示方法：

例方程x2-1=0的所有實數(shù)解的集合A；謂詞法：A={x|xR∧x2-1=0}或A={x|x是實數(shù)且x2-1=0}枚舉法：A={1，-1}17五、集合與集合的關(guān)系（一）包含關(guān)系（二）相等關(guān)系（三）真包含關(guān)系18“包含關(guān)系”的謂詞表示：

ABBA

(x)(x∈Ax∈B)（一）包含關(guān)系例：設A={ADA,BASIC,PASCAL}，B={BASIC,PASCAL,ADA,C,JAVA}定義：

A包含在B內(nèi)，A包含于B，B包含A設A，B是任意兩個集合，若A的每個元素都是B的元素，則稱A是B的子集(Subset)，也稱A包含在B內(nèi)，B包含A，記作BA或AB，若A不被B所包含，則記作A

B。顯然，對任意集合A，都有AA。AB19（二）相等關(guān)系定義A＝B當且僅當A與B具有相同的元素，否則，AB。即集合A,B中的元素完全相同，稱這樣的兩個集合相等。

{1,2,4}={1,4,2}≠{1,{2,4}}定理3-1.1

設A和B是任意兩個集合，A=BAB且BA。集合相等的謂詞表示：A=B(x)(x∈Ax∈B)20定理3-1.1

A=B

AB且BA。證明：(1)證：若AB且BA，則A=B。(反證法)

已知AB且BA，假設A≠B，則至少有一個元素x，使得x∈A而xB；或者x∈B而xA。如果x∈A而xB，則與AB矛盾。如果x∈B而xA，則與BA矛盾。

所以A=B。(2)證：若A=B

，則AB且BA

。若A=B，則兩個集合有相同的元素，即(x)(x∈Ax∈B)為真，且(x)(x∈Bx∈A)為真，即必有AB且BA。所以，A=B

AB且BA。該定理是證明兩個集合相等的基本思路和依據(jù)。21集合相等的謂詞定義A=BAB∧BA(x)(x∈Ax∈B)∧(x)(x∈Bx∈A)(x)((x∈Ax∈B)∧(x∈Bx∈A))(x)(x∈Ax∈B)A=B(x)(x∈Ax∈B)22（三）真包含關(guān)系定義1.2.2

：A真包含于B設A,B是任意兩個集合，集合A中的每一個元素都屬于B，但集合B中至少有一個元素不屬于A。則稱A是B的真子集(ProperSubset)，記作AB，如果A不是B的真子集，則記作AB?！罢姘P(guān)系”的謂詞表示：ABAB∧A≠BAB(x)(x∈Ax∈B)∧(x)(x

B∧xA)對任意x，如xA，則xB，并且存在xB，但是xA。23自學真包含關(guān)系的謂詞定義：ABAB∧A≠B(x)(x∈Ax∈B)∧

(x)(x∈Ax∈B)(x)(x∈Ax∈B)∧

((x)(x∈Ax∈B)∨

(x)(x∈Bx∈A))((x)(x∈Ax∈B)∧(x)(x∈Ax∈B))

∨

((x)(x∈Ax∈B)∧(x)(x∈Bx∈A))(x)(x∈Ax∈B)∧(x)(x∈B

∧

xA)集合A中的每一個元素都屬于B，但集合B中至少有一個元素不屬于A。24六、幾個特殊集合1、全集2、空集3、冪集251、全集定義

在一個相對固定的范圍內(nèi)，包含此范圍內(nèi)所有客體的集合，稱為全集或論集(UniversalSet)，用U或E表示。

E={x|P(x)∨P(x)}其中：P(x)為任何謂詞。用文氏圖描述如下:U六、幾個特殊集合一般地，根據(jù)討論問題的范圍，選擇對問題討論方便的集合作為全集。在實際應用中，常常把某個適當大的集合看成全集。262、空集定義：不含任何元素的集合叫做空集(EmptySet)，記作Φ?？占梢苑柣癁?/p>

Φ={x|P(x)∧P(x)}={}其中：P(x)為任何謂詞。例

設A={x|(x∈R)∧(x2<0)}，試列舉A中的所有元素。解：A=Φ。Φ與{Φ}:Φ是不含任何元素的集合，{Φ}是含一個元素Φ的集合。

{Φ}={{}}，|Φ|=0，|{Φ}|=1，Φ∈{Φ}定理3-1.2（1）空集是一切集合的子集；（2）空集是絕對唯一的。27反證法（1）空集是一切集合的子集；ΦA(chǔ)證明：因為(x)(x∈Φx∈A)為永真式，所以ΦA(chǔ)。（2）空集是絕對唯一的。分析：對“唯一性”的證明通常采用反證法。即假設“不唯一”，得出矛盾，從而說明結(jié)論正確。證明：（反證法）假設空集不唯一，即存在Φ1和Φ2兩個空集，且Φ1≠Φ2，因為是Φ1空集，則由性質(zhì)1得Φ1

Φ2

。因為是Φ2空集，則由性質(zhì)1得Φ2

Φ1

。所以Φ1=Φ2

。與假設矛盾，所以空集是唯一的。定理3-1.2的證明Φ{Φ}283、冪集

引例：求集合的子集及子集的個數(shù)例A子集子集個數(shù)ΦΦ1{a}Φ,{a}2{a,b}Φ,{a},,{a,b}4{a,b,c}Φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}8一般來說，對于n個元素的集合A，它的不同的子集總數(shù)有：＝(1+1)n＝2n所以，n元集共有2n個子集。Cn2＋……Cn0Cn1Cnn＋＋＋29一般來說，對于n個元素的集合A，它的不同的子集總數(shù)有

Cn2＋……Cn0Cn1Cnn＋＋＋Cn2＋…Cn0Cn1Cnn＋＋＋xn-1yxn-2y2xnynCn2＋……Cn0Cn1Cnn＋＋＋而(x+y)n=令x=y=1時得

2n=所以不同子集總數(shù)有2n30冪集定義：冪集(powerset)給定集合A，由A的所有子集為元素組成的集合稱為A的冪集(powerset)，記為ρ(A)

。冪集的符號化表示為ρ(A)＝{x|xA}例如：計算下列冪集:(1)ρ(Φ)；(2)ρ({a});(3)ρ({Φ})。解：(1)ρ(Φ)={Φ}；(2)ρ({a})={Φ,{a}}(3)ρ({Φ})={Φ,{Φ}}；定理3-1.3若有限集合Ａ有n個元素，則其冪集ρ(A)共有2n個元素。|A|=n,|ρ(A)|=2n31子集Bijk編碼Ａ＝{a,b,c}

ijk是二進制數(shù)，

Bi

jk

A,i=1，a∈Bijk；i=0，aBijk；j=1，b∈Bijk；j=0，bBijk；k=1，c∈Bijk；k=0，cBijk

。例：Ａ＝{a,b,c}則B000B001B010B011B100B101B110B111Φ{c}{b,c}{a}{a,c}{a,b}{a,b,c}B0

B1B2B3B4B5B6B7故：ρ(A)={Φ,{c},,{b,c},{a},{a,c},{a,b},{a,b,c}}例：Ａ＝{a,{b,c,d}}

B0=B00=Φ，B1=

B01={{b,c,d}}，B2=B10={a}，

B3=B11={a,{b,c,d}}故：ρ(A)={Φ,{{b,c,d}},{a},{a,{b,c,d}}}利用子集Ba1a2a3…an的下標編碼求集合A的冪集，a1a2a3…an為二進制編碼，n為集合A的元素個數(shù)。32設A={Φ}，B=ρ(ρ(A))ρ(A)={Φ,{Φ}}在求ρ(ρ(A))時，實際上是將{Φ,{Φ}}中的元素分別看成Φ=a,{Φ}=b,于是{Φ,{Φ}}={a,b}B=ρ(ρ(A))=ρ({a,b})={B0,

B1,B2,B3}={B00,

B01,B10,B11}={Φ,,{a},{a,b}}然后再將a,b代回即可B=ρ(ρ(A))=ρ({Φ,{Φ}})={Φ,{{Φ}},{Φ},{Φ,{Φ}}}以后熟悉后就可以直接寫出。練習

P86(7)333-2集合的運算一、定義

設A、B是兩個集合，={x|x∈A∨x∈B}x∈A∪B

x∈A∨x∈B

={x|xA

∧

xB}x∈A∩B

x∈A∧x∈B

={x|x∈A∧x

B}x∈A-B

x∈A∧xB

={x|x∈E∧x

A}={x|x

A}

x∈~A

xA

(x∈A)

={x|((xA)∧(xB))∨((xB)∧(xA))}AB=(A-B)∪(B-A)AB=(A∪B)-(A∩B)EAB差集EAB交集補集EA并集EAB(1)并集A∪B(2)交集A∩B(3)差集A-B(4)補集~A(5)對稱差集AB34例：A={4,{1,2},{3}},B={{3},{1,2,3},4,{1,2},{1}}則：A∩B={4,{1,2},{3}}=AA∪B={4,{1,2},{3},{1,2,3},{1}}=BA-B=ΦB-A={{1,2,3},{1}}35二、集合的運算律等冪律:A∪A=A；A∩A=A；交換律:A∪B=B∪A;A∩B=B∩A結(jié)合律:A∪(B∪C)=(A∪B)∪C；A∩(B∩C)=(A∩B)∩C；恒等律:A∪Φ=A； A∩E=A；零律:A∪E=E； A∩Φ=Φ；分配律:A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)吸收律:A∩(A∪B)=A; A∪(A∩B)=A；

集合的運算律是指集合的交、并、補、差等運算的主要性質(zhì)，也稱為集合的基本定律。36定理否定律：

~~A=A；德摩根定律：~(A∩B)=~A∪~B~(A∪B)=~A∩~B矛盾律：

A∩~A＝Φ；排中律：

A∪~A＝E。其他：

A-A=Φ；A-B=A-(A∩B)；

A-B=A∩~B;(A-B)-C=A-(B∪C)；A∪(B-A)=A∪B；EAB37三、證明集合相等的四種方法方法一：命題演算法（邏輯等價式和推理規(guī)則）方法二：等式代入法(假設交換律、分配律、同一律、零律已經(jīng)成立)方法三：證明出：AB且BA，則A=B。方法四：反證法38三、證明集合相等的四種方法方法一：命題演算法（邏輯等價式和推理規(guī)則）例：證明A∪(A∩B)=A

（吸收律）證任取x,

x(A

∪(A∩

B))

xA∨x(A∩

B)

xA∨

(xA∧xB)

xA

因此得A∪(AB)=A。方法二：等式代入法(假設交換律、分配律、同一律、零律已經(jīng)成立)例證明吸收律A∪(A∩

B)=(A∩

E)∪(A∩

B)=A∩(E∪

B)=A∩

E=A39集合等式的證明方法三：證明出：AB且BA，則A=B

依據(jù)：定理3-1.1

A=B，當且僅當AB且BA。例如：（P91定理3-2.5的證明方法）方法四：反證法假設不等，推出矛盾。40分析：(x)(x∈A∩Bx∈A)(x)(x∈Ax∈B)證明：A∩B=A，(x)(x∈A∩Bx∈A)(x)((x∈A∩B

x∈A)∧(x∈Ax∈A∩B))(x)((xA∩B∨x∈A)∧(xA∨x∈A∩B))(x)(((x∈A∧x∈B)∨x∈A)∧(xA∨(x∈A∧x∈B))(x)(((xA∨xB)∨x∈A)∧

(xA∨(x∈A∧x∈B)))(x)(T∧(T∧(

xA∨x∈B)))(x)(

xA∨x∈B)(x)(x∈Ax∈B)AB證明P90定理3-2.3：A∩B=A

AB41四、證明AB的四種方法：方法一：A和B是用枚舉方式定義的：依次檢查A的每個元素是否在B中出現(xiàn)。方法二：通過集合運算判斷AB：即A∪B=B,A∩B=A,AB=三個等式中有一個為真，則AB。方法三：通過文氏圖判斷集合的包含（注意這里是判斷，而不是證明）方法四：A和B是謂詞定義的，且A和B中元素的性質(zhì)分別為P和Q：（即：A={x|P(x)}B={x|Q(x)}利用的定義證明（按定義證明法）。42按定義證明的方法若定義中有“若…則…”來描述的，則在證明時應采用離散數(shù)學中特有的按定義證明方法即證明時，首先敘述定義的前半部分“若…”，將這部分的內(nèi)容稱為“附加的已知條件”，此時利用該“附加的已知條件”和題目本身所給的已知條件證明出定義的后半部分“則…”，這部分的內(nèi)容稱為定義中的結(jié)論。這種證明問題的方法在于：證明時不能單純利用題目所給的已知條件，而應同時利用定義中的“已知”，推出的并非整個定義，而是定義中的結(jié)論。這與一般的證明思路：已知→中間結(jié)果→結(jié)論是完全不同的。本章的證明大部分都采用按定義證明方法。利用的定義證明：AB定義：AB(x)(x∈Ax∈B)證明：假設(x)(x∈A)，利用題目中的已知條件和已有的定理和公理去推出即(x)(x

∈B)，從而證明AB。注意：若已知AB，則可以設(x)(x∈A)(x)(x

∈B)

43六、證明集合不等的方法證AB：

方法一：舉例或畫文氏圖示意。方法二：轉(zhuǎn)化為證明邏輯判斷式不等價。A≠B(x)(xA且xB)∨(x)(xB且xA)方法三：反證法，假設A=B，推出矛盾。五、判斷客體a是否是集合A元素的基本方法：把a作為一個整體，檢查它在A中是否出現(xiàn)。44七、證明集合A是空集的方法方法一： 其邏輯判斷條件是永假。

Φ={x|P(x)∧P(x)}方法二： 用反證法：設aA，引出矛盾的結(jié)果。 45自學求證(A-B)-C=(A-C)-(B-C)證明：任取x，

x∈(A-C)-(B-C)x∈(A-C)∧x(B-C)(x∈A∧xC)∧(x∈B∧xC)(x∈A∧xC)∧

(xB∨x∈C)(x∈A∧xC∧xB)∨(x∈A∧xC∧x∈C)x∈A∧xC∧xBx∈A∧xB∧xC(x∈A∧xB)∧xCx∈A-B∧xCx∈(A-B)-C所以(A-B)-C=(A-C)-(B-C)46自學A-(B∩C)=(A-B)∪(A-C)A-(B∪C)=(A-B)∩(A-C)證明：任取x∈A-(B∪C)x∈A∧x(B∪C)x∈A∧(x∈B∨x∈C)x∈A∧(xB∧xC)(x∈A∧xB)∧(x∈A∧xC)x∈A-B∧x∈A-Cx∈(A-B)∩(A-C)所以A-(B∪C)=(A-B)∩(A-C))A∩(B-C)=(A∩B)-(A∩C)但∪對-

是不可分配的，如A∪(A-B)=A，而(A∪A)-(A∪B)=Φ注意:這不是分配律47自學證明：AB~B~A證明：AB(x)(x∈Ax∈B)

(x)(xBxA)x(x∈~Bx∈~A)

~B~A∴AB~B~A證明：德摩根定律(1)~(A∩B)=~A∪~B(2)~(A∪B)=~A∩~B證明:(1)：任取x∈~(A∩B)x∈~(A∩B)

xA∩B(x∈A∧x∈B)(xA)∨(xB)(x∈~A)∨(x∈~B)x∈(~A∪~B)

∴~(A∩B)=~A∪~B48自學~A=B當且僅當A∪B=E且A∩B=Φ證明：(A∪B=E)∧(A∩B=Φ)(x)(x∈A∪Bx∈E)∧(PT=P)(x)(x∈A∩Bx∈Φ)(PF=P)(x)(x∈A∪BT)∧x(x∈A∩BF)(x)(x∈A∪B∧(x∈A∩B))(x)((x∈A∨x∈B)∧(x∈A∧x∈B))(x)((x∈A∨x∈B)∧(xA∨xB))(x)((xAx∈B)∧(x∈BxA))(x)((x∈~Ax∈B)∧(x∈Bx∈~A))(x)((x∈~Ax∈B)~A=B49設A是有窮集合，其元素個數(shù)為|A|。這節(jié)主要解決集合的計數(shù)問題。例如有AB兩個商店，A店經(jīng)營1000種商品，B店經(jīng)營1200種商品，其中有100種商品兩個商店都經(jīng)營，問兩個商店共經(jīng)營多少種商品？顯然|A∪B|=|A|+|B|-|A∩B|如果有ABC三個有限集合，則|A∪B∪C|=|A∪B|+|C|-|(A∪B)∩C|=|A|+|B|-|A∩B|+|C|-|(A∩C)∪(B∩C)|=|A|+|B|-|A∩B|+|C|-(|A∩C|+|B∩C|-|A∩B∩C|)=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|ABA∩BA∪B*3-3.包含排斥原理ABCU50一般地，有n個有限集合A1,A2,...An,則*3-3.包含排斥原理51令U為全集，E、F、J分別為會英語、法語和日語人的集合。|U|=170|E|=120|F|=80|J|=60|E∩F|=50|E∩J|=25|F∩J|=30|E∩F∩J|=10|E∪F∪J|=|E|+|F|+|J|-|E∩F|-|E∩J|-|F∩J|+|E∩F∩J|=120＋80＋60－50－25－30＋10＝165|U-(E∪F∪J)|=170-165=5即有5人不會這三種語言。例3-3.1某個研究所有170名職工，其中120人會英語，80人會法語，60人會日語，50人會英語和法語，25人會英語和日語，30人會法語和日語，10人會英語、日語和法語。問有多少人不會這三種語言？EFJ10U521.掌握集合的定義、謂詞定義、證明方法。2.掌握三個特殊集合，會求集合的冪集。3.掌握集合的五種運算定義、計算方法、性質(zhì)。*4.會用包含排斥原理解決集合計數(shù)問題.

作業(yè)：第94頁⑶d)⑷⑸b)⑼3.1~3.3小結(jié)533.4序偶與集合的笛卡爾積要求：1、理解概念；2、掌握序偶和笛卡爾積的定義和性質(zhì)。54一、序偶與有序n元組兩個具有固定次序的客體x、y組成序偶，也稱為有序二元組，記作<x,y>；稱x、y分別為序偶<x,y>的第一，第二元素。固定次序是指調(diào)換第一和第二元素位置后，含義不同。注意，第一、二元素未必不同。1.定義：說明<2,3><3,2><1,-2><-2,1><-4,-3>55序偶的性質(zhì)（1）當x≠y時，<x,y>≠<y,x>。

{x,y}={y,x}（2）序偶二個元素可以重復，即<x,x>也是序偶。

無{x,x}（3）序偶中兩個元素可以來自不同的集合。<x,y>：x∈A,y∈B{x,y}∈A（4）序偶與集合的統(tǒng)一：

<x,y>={{x},{x,y}}（5）序偶相等的定義：

(x,y=u,v)(x=u)∧(y=v)由序偶相等的定義有

x+2＝5 2x+y＝4解得x＝3,y＝-2。解答例

已知<x+2,4>＝<5,2x+y>，求x和y。56序偶的推廣：

有序N元組

定義

由N個元素x1,x2,…,xn-1,xn按照一定的次序組成的N元組稱為有序N元組，記為<x1,x2,…,xn-1,xn>。xi叫做該

n元組的第i個分量i=1,…,n。有序N元組與序偶的關(guān)系：<x1,x2,…,xn-1,xn>

=x1,x2,…,xn-1,xn三元組

x1,x2,x3

=x1,x2,x3四元組x1,x2,x3,x4=x1,x2,x3,x4

=<x1,x2>,x3>,x4注意：x1,x2,x3≠

x1,x2,x3x1,x2,x3,x4

≠

x1,x2,x3,x4x1,x2,x3,x4,x5≠

x1,x2,x3,x4,x5例如：a年b月c日d時e分f秒，可用六元組表示<a,b,c,d,e,f>57定義：兩個n元組相等設x1,x2,…,xn與y1,y2,…,yn是兩個n元組，如果xi=yi，i=1,…,n，則稱這兩個n元組相等，記為x1,x2,…,xn=y1,y2,…,yn。用邏輯的方法表示為(x1,x2,…,xn=y1,y2,…,yn)(x1=y1)∧(x2=y2)∧…∧(xn=yn)。

<a,b,c,d><b,a,d,c><a,b,d,c>58二、集合的笛卡爾積

引例

“斗獸棋”虎象獅豹狼鼠貓狗虎象獅豹狼鼠貓狗每個棋子可以看成一個序偶:<紅,象>,<紅,獅>,<紅,虎>,<紅,豹>,<紅,狼>,<紅,狗>,<紅,貓>,<紅,鼠>,<藍,象>,<藍,獅>,<藍,虎>,<藍,豹>,<藍,狼>,<藍,狗>,<藍,貓>,<藍,鼠>可看成是由兩種顏色的集合A和8種動物的集合B做運算得到的。

A={紅,藍}B={象,獅,虎,豹,狼,狗,貓,鼠}斗獸棋可記成集合：}{斗獸棋可記成集合：59補充的定義:A和B的笛卡爾積或直積設A、B是集合，由A的元素為第一元素，B的元素為第二元素組成的所有序偶的集合，稱為A和B的笛卡爾積或直積，記作A×B，即

AB={<x,y>|xA∧yB}<x,y>AB

xA

∧

yB<x,y>AB

xA

∨

yB例如：A表示某大學所有學生的集合，B表示大學開設的所有課程的集合。則A×B可以用來表示該校學生選課的所有可能情況。1、集合的笛卡爾積的定義60AB={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}BA={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}AA={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>}可見A×B≠B×A集合的笛卡爾積運算不滿足交換律。例：A={0,1}，B={a,b}，C={z}(AB)C={<0,a>,<0,b>,<1,a>,<1,b>}×{z}={<0,a,z>,<0,b,z>,<1,a,z>,<1,b,z>}A(BC)={0,1}{<a,z>,<b,z>}={<0,<a,z>>,<0,<b,z>>,<1,<a,z>>,<1,<b,z>>}

(AB)C={<<x,y>,z>|<x,y>AB∧

zC}A(BC)={<x,<y,z>>|xA∧<y,z>BC},可見(AB)CA(BC)。集合的笛卡爾積運算也不滿足結(jié)合律。例：設A={0,1,2}，B={a,b}，求AB，BA，AA。|AB|=6=|BA||AA|=9611)如果A、B都是有限集，且|A|=m,|B|=n，

則|AB|=m?n.證明：由笛卡爾積的定義及排列組合中的乘法原理，直接推得此定理。

2)AΦ=ΦB=Φ3)對∪和∩滿足分配律。

設A,B,C是任意集合，則

①A(B∪C)=(AB)∪(AC)；②A(B∩C)=(AB)∩(AC)；③(A∪B)C=(AC)∪(BC)；④(A∩B)C=(AC)∩(BC)4)若C,則AB(ACBC)(CACB)。5)設A,B,C,D為非空集合，則ABCDAC∧BD。（兩個笛卡爾積具有包含關(guān)系，則相應的分量也具有包含關(guān)系）2、集合的笛卡爾積的性質(zhì)622、集合的笛卡爾積的性質(zhì)（續(xù)）求證：①A(B∪C)=(AB)∪(AC)分析：<x,y>A(B∪C)??<x,y>(AB)∪(AC)

證明：任取<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)

所以A(B∪C)=(AB)∪(AC)其余可以類似證明。A(B∪C)

<x,y>A(B∪C)

(AB)∪(AC)

<x,y>(AB)∪(AC)A={a},B={1,2},C={2,3}A(B∪C)={a}{1,2,3}={<a,1>,<a,2>,<a,3>}AB={a}{1,2}={<a,1>,<a,2>}AC={a}{2,3}={<a,2>,<a,3>}(AB)∪(AC)={<a,1>,<a,2>,<a,3>}A(B∪C)=(AB)∪(AC)

63即AB(ACBC)類似可以證明AB(CACB)。4)若C,則AB(ACBC)(CACB).證明:證AB(ACBC)①證：ABACBC

設AB,任取<x,y>ACxA

∧

yC

(由AB)

xB

∧

yC<x,y>BC即<x,y>BC

所以,ACBC。2、集合的笛卡爾積的性質(zhì)（續(xù)）②證：(ACBC)

AB若C,任取yC,任取xA

xA

∧

yC<x,y>AC(由ACBC)

<x,y>BCxB

∧

yCxB

所以,AB。<x,y>AB

xA

∧

yBAB(x)(x∈A

x∈B)64

5)設A,B,C,D為非空集合，則ABCDAC∧BD。證明:①證：由ABCDAC∧BD。任取xA，任取yB，

xA∧

yB<x,y>A×B(由ABCD)<x,y>C×DxC∧

yD

即xC∧

yD

所以,AC∧BD.②證：由AC∧BDABCD。任取<x,y>A×B

<x,y>A×B

xA∧

yB(由AC，BD)

xC∧

yD<x,y>C×D即<x,y>C×D所以,ABCD

因此，ABCDAC∧BD。2、集合的笛卡爾積的性質(zhì)（續(xù)）65注意：兩集合的笛卡爾積仍是一個集合，故對于有限集合可進行多次笛卡爾積運算。A×B×C=(A×B)×C

A×B×C×D=(A×B×C)×D=((A×B)×C)×DA1×A2×…

×An=(A1×A2×…×An-1)×An={<x1,x2,…,xn>|x1∈A1,x2∈A2,…,xn∈An}A×A=A2,A×A×A=A3,A×A×…×A=An

66例：令A1={x|x是學號}A2={x|x是姓名}A3={男,女}

A4={x|x是出生日期}A5={x|x是班級}

A6={x|x是籍貫}

則A1A2A3A4A5A6中一個元素：<001，王強，男，1981-02-16，計2001-1，河南>是學生檔案數(shù)據(jù)庫的一條信息，所以學生的檔案就是A1A2A3A4A5A6的一個子集。3、集合的笛卡爾積的應用作業(yè)第105頁⑵673.5關(guān)系及其表示法關(guān)系是一個非常普遍的概念，如數(shù)值的大于關(guān)系、整除關(guān)系，人類的父子關(guān)系、師生關(guān)系、同學關(guān)系等。要求：1、理解定義關(guān)系定義域（前域）、值域2、掌握關(guān)系的表示方法3、熟記特殊的關(guān)系4、會計算關(guān)系的集合運算681.關(guān)系的定義

空集或任一序偶的集合，都稱為一個二元關(guān)系。

設A、B是集合，若RA×B，則稱R是一個從A到B的二元關(guān)系。

若RA×A，則稱R是A上的二元關(guān)系。二元關(guān)系簡稱為關(guān)系。<x,y>R可記作xRy

；一、基本概念設R1＝{<1,2>,<a,b>}，R2＝{<1,2>,a,b}。則R1是二元關(guān)系，R2不是二元關(guān)系，只是一個集合。舉例關(guān)系是以序偶為元素的集合。<x,y>R可記作xRy定義1：定義2：<x,y>R,xRy，表示x和y具有關(guān)系R。<x,y>R，表示x和y不具有關(guān)系R。69注意：關(guān)系集合滿足以下條件之一：(1)集合非空，且它的元素都是序偶；(2)集合是空集，即空集也可稱作關(guān)系。序偶是講究次序的，關(guān)系也是有序的。即<x,y>∈R未必有<y,x>∈R，x與y有關(guān)系R，未必y與x有關(guān)系R。例：甲與乙有父子關(guān)系，則乙與甲肯定沒有父子關(guān)系。由于任何A×B的子集都是一個二元關(guān)系，而A×B共有2|A|╳|B|個不同的子集。因此，從A到B不同的關(guān)系共

有2|A|╳|B|個。1.2.3.70例3-5.1①A={0,1}，B={x,y,z}，則R1={<0,x>，<1,z>}，R2=A×B，R3=等都是從A到B的二元關(guān)系；R4={<0,0>}和R3同時也是A上的二元關(guān)系。②A為整數(shù)集合，則R={<x,y>|x能整除y(即x|y),x,yA}為A上的整除關(guān)系。如：<1,3>,<2,8>,<4,80>,<7,84>等等。③父子關(guān)系：{<x,y>|x人類，y人類，且x是y的父親(y是x的兒子)}71④有王、張、李、趙是某校的老師，該校有三門課程：程序設計、離散數(shù)學和英語，已知王可以教程序設計和離散數(shù)學，張可以教程序設計和英語，李可以教離散數(shù)學，趙可以教英語，若記A={王,張,李,趙}，B={程序設計,離散數(shù)學,英語}。那么這些老師與課程之間的對應關(guān)系就可以用由A到B的一個關(guān)系R中的序偶來表示。R={<王,程序設計>,<王,離散數(shù)學>,<張,程序設計>,<張,英語>,<李,離散數(shù)學>,<趙,英語>}

722.三個特殊關(guān)系（1）空關(guān)系Φ：

因為ΦA(chǔ)×B，(或ΦA(chǔ)×A)，所以Φ也是一個從A

到B(或A上)的關(guān)系，稱為空關(guān)系。（2）完全關(guān)系(全域關(guān)系)E：即含有A×B(或A×A)全部序偶的關(guān)系，A×B(或A×A)本身也是一個從A到B(或A上)的關(guān)系，稱為完全關(guān)系。（3）A上的恒等關(guān)系IA：

IAA×A,且IA={<x,x>|x∈A}稱為A上的恒等關(guān)系。A={1,2,3},則空關(guān)系=ΦEA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}IA={<1,1>,<2,2>,<3,3>}。舉例73其他常見的關(guān)系小于或等于關(guān)系：

LA={<x,y>|x,y∈A∧x≤y}，其中AR。整除關(guān)系：

DA={<x,y>|x,y∈A∧x整除y}，其中AZ*Z*是非零整數(shù)集包含關(guān)系：R＝{<x,y>|x,y∈A∧xy},其中A是集合族。設A={1,2,3}，B＝{a,b},則(1)LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}(2)令C=ρ(B)={,{a},,{a,b}}，則C上的包含關(guān)系是

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

<{a},{a}>,<{a},{a,b}>,<,>,

<,{a,b}>,<{a,b},{a,b}>}舉例74二、關(guān)系的表示方法1.枚舉法即將關(guān)系中所有序偶一一列舉出，寫在大括號內(nèi)。如R

={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}。2.謂詞公式法即用謂詞公式表示序偶的第一元素與第二元素間的關(guān)系。如“<”={<x,y>|x∈N∧y∈N∧x<y}3.有向圖法4.關(guān)系矩陣法

753.有向圖法表示二元關(guān)系R的圖叫做R的關(guān)系圖。⑴從A到B的二元關(guān)系R的關(guān)系圖。⑵A上的二元關(guān)系R的關(guān)系圖。76

ABR:⑴A到B二元關(guān)系R的關(guān)系圖

設A={a1,a2,…,am}，B={b1,b2,…,bn}，R是A到B二元關(guān)系，R的關(guān)系圖的繪制方法如下：

4。3。2。1。。c。b。a①畫出m個小圓圈（實心或空心）表示A的元素，再畫出n個小圓圈表示B的元素。這些小圓圈叫做關(guān)系圖的結(jié)點。②關(guān)系中的序偶ai,bj

，畫一條從ai到bj的有方向(帶箭頭)的線。這些有方向的線叫關(guān)系圖的邊。

(注意ai是始點，bj是終點，次序不能顛倒)。例3-5.3：設A={1,2,3,4},B={a,b,c}，RA×B，R={<1,a>,<1,c>,<2,b>,<3,c>}，

R的關(guān)系圖如下：77

⑵A上的二元關(guān)系R的關(guān)系圖設A={a1,a2,…,am}，R是A上的二元關(guān)系，其關(guān)系圖的繪制方法如下：①畫出m個小圓圈表示A的元素。②若ai,ajR，則從ai到aj畫一根有方向(帶箭頭)的線。③若<ai,ai>R，則從ai到ai畫一條有向環(huán)(自回路)。例：設函數(shù)集合P={P1,P2,P3,P4,P5}，考慮它們之間的調(diào)用關(guān)系R：P1調(diào)用P2；P2調(diào)用P4；P3調(diào)用P1；P4調(diào)用P5；P5調(diào)用P2；

則R={<P1,P2>,<P2,P4>,<P2,P2>,<P3,P1>,<P4,P5>,<P5,P2>

R的關(guān)系圖為：P1P2P3P4P578有限集合之間的關(guān)系也可以用矩陣來表示，這種表示法便于用計算機來處理關(guān)系。設A={a1,a2,,am}，B={b1,b2,,bn}是個有限集，RA×B，定義R的關(guān)系矩陣是m×n

階矩陣

MR=(rij)m×n，其中A={a1,a2,,am}是個有限集，RA×A，定義R的關(guān)系矩陣是m×m階矩陣MR=(rij)m×m，其中1若<ai,bj>∈R0若<ai,bj>∈R(1≤i≤m,1≤j≤n)4.矩陣表示法rij=1若<ai,bj>∈R0若<ai,bj>∈R(1≤i,j≤m)rij=79A={a,b,c}，B={1,2,3,4},R1A×BR1={<a,1>,<c,1>,<b,2>,<a,3>,<c,4>}A={1,2,3,4}，R2A×AR2={<1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}

1010010010013×41234注意MR1=MR2=abc

1001001010014×4123412341100在寫關(guān)系矩陣時，首先應對集合A和B中的元素進行排序，不同的排序會得到不同的關(guān)系矩陣。當集合以枚舉法表示時，如果沒有對集合的元素排序，則默認枚舉的次序為元素的排序。80A={1,2,3}上的Φ、完全關(guān)系及IA的關(guān)系圖及矩陣如下：MIA=1000100013×30000000003×3MΦ=1111111113×3MA×A=1。。2。3Φ。1。2。3A×A。1。2。3IA特殊關(guān)系的表示81例3-5.4(1)設A={1,2,3,4}，B={2,4,6}，R表示A與B的整除關(guān)系，寫出關(guān)系R的四種表示法。解：由題意得枚舉法：謂詞公式法：對應的關(guān)系圖為：關(guān)系矩陣為：1234246

1114×3246MR=1234

111

001

010R={<1,2>,<1,4>,<1,6>,<2,2>,<2,4>,<2,6>,<3,6>,<4,4>}；R={<x,y>|x能整除y，x∈A,y∈B}。82由于關(guān)系就是集合，所以集合的∩、∪、~和-運算對關(guān)系也適用。定理3-5.1

設R和S是從集合X到集合Y的兩個關(guān)系，則R∩S，R∪S，~R，R-S仍是從X到Y(jié)的關(guān)系。證明：因為RXY，SXY，所以R∩SXY，R∪SXY；~R=XY-RXY，同理：~SXYR-S=R∩~SXY。故R∩S，R∪S，~R，R-S是從X到Y(jié)的關(guān)系。三、關(guān)系的集合運算

83A是學生集合，R是A上的同鄉(xiāng)關(guān)系，S是A上的同姓關(guān)系，則R∪S：或同鄉(xiāng)或同姓關(guān)系R∩S：既同鄉(xiāng)又同姓關(guān)系R-S：同鄉(xiāng)而不同姓關(guān)系~R：不是同鄉(xiāng)關(guān)系,這里~R=(A×A)-R例3-5.284作業(yè)第109頁⑵、⑸c)d)853.6關(guān)系的性質(zhì)本節(jié)將研究關(guān)系的一些性質(zhì)，它們在關(guān)系的研究中起著重要的作用。這是本章最重要的一節(jié)。本節(jié)中所討論的關(guān)系都是集合A上的關(guān)系。本節(jié)要點：五個性質(zhì)：自反性、反自反性--自己和自己的關(guān)系對稱性、反對稱性–兩個元素之間的關(guān)系傳遞性--三個元素之間的關(guān)系相關(guān)證明86定義：設R是集合A上的關(guān)系，若對于任意x∈A都有<x,x>∈R(xRx)，則稱R是A中的自反關(guān)系。即R是A中自反的(x)(xA<x,x>∈R)該定義表明在自反關(guān)系R中，除其他序偶外，必須包括有全部由每個x∈A所組成的相同元素的序偶。一、自反性非（不是）自反的(x)(xA∧<x,x>R)例如：設X={a,b,c},R1={<a,a>,<b,b>,<c,c>,<a,b>}R2={<a,a>,<b,b>,<a,b>}

例如：相等關(guān)系(=)，小于等于關(guān)系()，包含關(guān)系()等是自反關(guān)系。是自反關(guān)系。不是自反關(guān)系。87定義：設R是集合A上的關(guān)系，若對于任意x∈A都有<x,x>∈R(xRx)，則稱R是A中的自反關(guān)系。即R是A中自反的(x)(xA<x,x>∈R)從關(guān)系矩陣看自反性：從關(guān)系有向圖看自反性：1？？？1？？？1具有自反性的關(guān)系的關(guān)系矩陣和關(guān)系圖的特點。1。2。3主對角線都為1。每個結(jié)點都有環(huán)。88定義：設R是集合A上的關(guān)系，若對于任意的x∈A都有<x,x>R

，則稱R為A中的反自反關(guān)系。即R是A中反自反的(x)(xA<x,x>R)該定義表明了，一個反自反的關(guān)系不應包括有任何相同元素的序偶。二、反自反性非（不是）反自反的(x)(xA∧<x,x>R)例如：設X={a,b,c},R1={<a,b>,<b,c>}

R2=={<a,a>,<a,b>,<b,c>}

不相等關(guān)系()，小于關(guān)系()，真包含關(guān)系()，父子關(guān)系是反自反關(guān)系。是反自反關(guān)系。不是反自反關(guān)系89定義：設R是集合A上的關(guān)系，若對于任意的x∈A都有<x,x>R

，則稱R為A中的反自反關(guān)系。即R是A中反自反的(x)(xA<x,x>R)從關(guān)系矩陣看反自反性：從關(guān)系有向圖看反自反性：0？？？0？？？0具有反自反性的關(guān)系的關(guān)系矩陣和關(guān)系圖的特點1。。2。3主對角線都為0。每個結(jié)點都無環(huán)。90R1、R3、R4是自反的，R2、R5、R8均是反自反關(guān)系。注意：任何一個不是自反的關(guān)系，未必是反自反的，任何一個不是反自反的關(guān)系，未必是自反的，如R6、R7非自反，也非反自反。存在既不是自反的也不是反自反的關(guān)系。例1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。1。2。。3333R2R1R3R4R5R6R7R8自反

反自反反自反反自反

自反

自反

非自反非反自反非自反非反自反91定義：R是集合A上的關(guān)系，若對任何x,y∈A，若有<x,y>R，必有<y,x>R

，則稱R為A中的對稱關(guān)系。

R是A上對稱的(x)(y)((xA∧yA∧<x,y>R)

<y,x>R)在有對稱性的關(guān)系中，若有序偶<x,y>，必有序偶<y,x>。例如：設集合A={1,2,3}有下列關(guān)系：1）R1={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}2）R2={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}三、對稱性非（不是）對稱的(x)(y)(xA∧yA∧<x,y>R∧

<y,x>

R)例如：相等關(guān)系(=)，不相等關(guān)系()，朋友關(guān)系，同學關(guān)系，同鄉(xiāng)關(guān)系等是對稱關(guān)系。是對稱關(guān)系不是對稱關(guān)系92定義：R是集合A上的關(guān)系，若對任何x,y∈A，若有<x,y>R，必有<y,x>