離散數(shù)學(xué)關(guān)系.ppt

《離散數(shù)學(xué)關(guān)系.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章關(guān)系1.在現(xiàn)實(shí)生活中,集合與集合之間還存在著某種聯(lián)系，如同學(xué)關(guān)系、朋友關(guān)系等。這些關(guān)系正是各門學(xué)科所要研究的主要內(nèi)容。離散數(shù)學(xué)從集合出發(fā)，主要研究集合之間的關(guān)系。本章內(nèi)容主要研究二元關(guān)系。2.本章主要內(nèi)容：關(guān)系的基本概念關(guān)系的表示方法關(guān)系的運(yùn)算關(guān)系的性質(zhì)關(guān)系的閉包等價(jià)關(guān)系與劃分偏序關(guān)系3.2.1關(guān)系的基本概念為了討論關(guān)系，首先引入有序?qū)偷芽▋悍e兩個(gè)概念。由兩個(gè)元素a,b組成的集合{a,b}中，a和b是沒有次序的。有時(shí)需要考慮有次序的兩個(gè)元素，所以需要由兩個(gè)元素組成新的東西，并且兩個(gè)元素是有次序的。定義2.1兩個(gè)元素a,b有次序地放在一起，稱為一個(gè)有序?qū)蛐蚺?，記?/p>

2、(a,b)。在有序?qū)?a,b)中，a稱為第一元素，b稱為第二元素。且(a1,b1)=(a2,b2)當(dāng)且僅當(dāng)a1=a2且b1=b2。4.定義2.2設(shè)A,B是兩個(gè)集合，集合{(x,y)

3、x∈A且y∈B}稱為A和B的笛卡兒積，也稱卡氏積，記為A×B。用屬于關(guān)系來表示就是：(x,y)∈A×B當(dāng)且僅當(dāng)x∈A且y∈B和(x,y)?A×B當(dāng)且僅當(dāng)x?A或y?B。其中A稱為第一集合，B稱為第二集合。5.例2.1設(shè)A={1,2,3},B={a,b}，求A×B。由笛卡兒積的定義可知有A×?=?×A=?。又由有序?qū)Φ男再|(zhì)可知，一般沒有A×B≠B×A。A×B也是一個(gè)集合，所以可以和另一集合C作笛

4、卡兒積(A×B)×C，類似地有A×(B×C)。但是，一般沒有(A×B)×C=A×(B×C)，且A×B中的元素既不是A中的元素，也不是B中的元素。6.定理2.1如果B1?A1，B2?A2，則B1×B2?A1×A2。7.證明對?(x,y)∈B1×B2，有x∈B1且y∈B2，又因?yàn)锽1?A1，B2?A2，則x∈A1且y∈A2，所以(x,y)∈A1×A2，即B1×B2?A1×A2。8.定理2.2A,B,C是任意集合，則：(1)A×(B∪C)=(A×B)∪(A×C)，(B∪C)×A=(B×A)∪(C×A)。(2)A×(B∩C)=(A×B)∩(A×C)，(B∩C)×A=(B×A)∩(

5、C×A)。(3)A×(B-C)=(A×B)-(A×C)，(B-C)×A=(B×A)-(C×A)。9.證明(1)對?(x,y)∈A×(B∪C)，有x∈A且y∈B∪C，因此x∈A且(y∈B或y∈C)，當(dāng)y∈B時(shí)，由x∈A和y∈B得(x,y)∈A×B，當(dāng)y∈C時(shí)，由x∈A和y∈C得(x,y)∈A×C，所以(x,y)∈(A×B)∪(A×C)，即A×(B∪C)?(A×B)∪(A×C)。因?yàn)锳?A，B?B∪C和C?B∪C得A×B?A×(B∪C)和A×C?A×(B∪C)，因此(A×B)∪(A×C)?A×(B∪C)。因此A×(B∪C)=(A×B)∪(A×C)成立。同理可證(B∪C)×A=

6、(B×A)∪(C×A)。10.(2)對?(x,y)∈(A×B)∩(A×C)，有(x,y)∈A×B且(x,y)∈A×C，所以（x∈A且y∈B）且（x∈A且y∈C）。由y∈B且y∈C得y∈B∩C，由x∈A且y∈B∩C得(x,y)∈A×(B∩C)。因此(A×B)∩(A×C)A×(B∩C)。因?yàn)锳?A，B∩C?B和B∩C?C，所以有A×(B∩C)?A×B和A×(B∩C)?A×C成立，因此A×(B∩C)?(A×B)∩(A×C)。因此A×(B∩C)=(A×B)∩(A×C)。同理可證(B∩C)×A=(B×A)∩(C×A)。11.(3)對?(x,y)∈A×(B-C)，有x∈A且y∈B-

7、C，所以x∈A且y∈B且y?C。由x∈A且y∈B得(x,y)∈A×B，由y?C得(x,y)?A×C，所以(x,y)∈(A×B)-(A×C)。因此A×(B-C)?(A×B)-(A×C)。對(x,y)∈(A×B)-(A×C)，有(x,y)∈A×B且(x,y)?A×C，由(x,y)∈A×B得x∈A且y∈B，由x∈A和(x,y)?A×C得y?C，所以x∈A且y∈B且y?C。由y∈B且y?C得y∈B-C，所以(x,y)∈A×(B-C)。因此(A×B)-(A×C)?A×(B-C)。因此A×(B-C)=(A×B)-(A×C)。同理可證(B-C)×A=(B×A)-(C×A)。12.定義

8、2.3任給n≥2，n個(gè)元素a1，…,an有次序地放在一起，稱為一個(gè)n元有序組，記為(a1，…，an)。為了體現(xiàn)n元有序組的次序，規(guī)定(a1，…，an)=(b1,，…，bn)當(dāng)且僅當(dāng)任給1≤i≤n，都有ai=bi。n元有序組可以組成集合，特別地有n個(gè)集合的卡氏積。13.定義2.4任給n≥2，A1，…，An是n個(gè)集合，集合{(x1,?,xn)

9、任給1≤i≤n，都有xi∈Ai}稱為A1，…，An的卡氏積，記為A1×…×An。任給1≤i≤n，Ai稱為這個(gè)卡氏積的第i個(gè)集合。14.定義2.5如果一個(gè)集合滿足以下條件之一：（1）集合非空，