離散數(shù)學(xué)集合

離散數(shù)學(xué)集合目錄CONTENCT集合基本概念集合運算冪集與笛卡爾積映射與函數(shù)等價關(guān)系與劃分偏序關(guān)系與格論基礎(chǔ)01集合基本概念集合定義表示方法舉例集合是具有某種特定屬性的事物的總體，是一個抽象的數(shù)學(xué)概念。集合通常用大寫字母表示，如A、B、C等。元素用小寫字母表示，如a、b、c等。集合中的元素可以列舉出來，用花括號{}括起來。如集合A={1,2,3}，表示集合A包含元素1、2、3。集合定義與表示方法屬于關(guān)系如果元素a不在集合A中，則稱a不屬于A，記作a?A。不屬于關(guān)系舉例對于集合A={1,2,3}，有1∈A，4?A。如果元素a在集合A中，則稱a屬于A，記作a∈A。元素與集合關(guān)系集合間關(guān)系及運算性質(zhì)子集關(guān)系如果集合A中的每一個元素都是集合B中的元素，則稱A是B的子集，記作A?B。相等關(guān)系如果集合A和集合B包含相同的元素，則稱A和B相等，記作A=B。并集運算集合A和集合B的并集是由所有屬于A或?qū)儆贐的元素組成的集合，記作A∪B。交集運算集合A和集合B的交集是由所有既屬于A又屬于B的元素組成的集合，記作A∩B。差集運算集合A與集合B的差集是由所有屬于A但不屬于B的元素組成的集合，記作A-B或AB。對稱差集運算集合A與集合B的對稱差集是由所有屬于A但不屬于B，或?qū)儆贐但不屬于A的元素組成的集合，記作A⊕B。02集合運算并集定義對于任意兩個集合A和B，由所有屬于A或?qū)儆贐的元素所組成的集合稱為A和B的并集，記作A∪B。并集性質(zhì)并集運算滿足交換律和結(jié)合律，即A∪B=B∪A，(A∪B)∪C=A∪(B∪C)。并集運算示例若A={1,2,3}，B={3,4,5}，則A∪B={1,2,3,4,5}。并集運算及性質(zhì)030201交集定義對于任意兩個集合A和B，由所有既屬于A又屬于B的元素所組成的集合稱為A和B的交集，記作A∩B。交集性質(zhì)交集運算滿足交換律和結(jié)合律，即A∩B=B∩A，(A∩B)∩C=A∩(B∩C)。交集運算示例若A={1,2,3}，B={3,4,5}，則A∩B={3}。交集運算及性質(zhì)差集性質(zhì)差集運算不滿足交換律，即A-B不一定等于B-A。差集運算滿足結(jié)合律和分配律，即(A-B)-C=A-(B∪C)，(A∪B)-C=(A-C)∪(B-C)。差集運算示例若A={1,2,3}，B={3,4,5}，則A-B={1,2}。差集定義對于任意兩個集合A和B，由所有屬于A但不屬于B的元素所組成的集合稱為A和B的差集，記作A-B或AB。差集運算及性質(zhì)對稱差集定義對于任意兩個集合A和B，由所有屬于A但不屬于B，或?qū)儆贐但不屬于A的元素所組成的集合稱為A和B的對稱差集，記作A⊕B。對稱差集運算滿足交換律和結(jié)合律，即A⊕B=B⊕A，(A⊕B)⊕C=A⊕(B⊕C)。對稱差集運算也可以表示為兩個集合的并集減去它們的交集，即A⊕B=(A∪B)-(A∩B)。若A={1,2,3}，B={3,4,5}，則A⊕B={1,2,4,5}。對稱差集性質(zhì)對稱差集運算示例對稱差集運算及性質(zhì)03冪集與笛卡爾積A是A本身的子集，即A∈P(A)。性質(zhì)定義：設(shè)A為任意集合，把A的所有子集構(gòu)成的集合叫做A的冪集，記作P(A)?？占侨魏渭系淖蛹?，即?∈P(A)。冪集的元素個數(shù)等于原集合元素個數(shù)的2的n次方，即若|A|=n，則|P(A)|=2^n。冪集定義及性質(zhì)0103020405性質(zhì)若A和B均為非空有限集，則|A×B|=|A|×|B|。笛卡爾積滿足結(jié)合律，即(A×B)×C=A×(B×C)。笛卡爾積滿足交換律，即A×B=B×A。定義：設(shè)A和B為任意兩個集合，則所有形如(a,b)的有序?qū)?gòu)成的集合稱為A和B的笛卡爾積，記作A×B。笛卡爾積定義及性質(zhì)冪集應(yīng)用舉例笛卡爾積應(yīng)用舉例冪集和笛卡爾積應(yīng)用舉例在關(guān)系數(shù)據(jù)庫中，一個關(guān)系可以看作是一個二維表，表中的每一行對應(yīng)一個實體，每一列對應(yīng)一個屬性。而冪集則可以用來表示這個二維表中所有可能的屬性組合。在計算機網(wǎng)絡(luò)中，IP地址由網(wǎng)絡(luò)地址和主機地址兩部分組成。若網(wǎng)絡(luò)地址有m種可能，主機地址有n種可能，則整個網(wǎng)絡(luò)中最多可以有m×n個不同的IP地址，這就是笛卡爾積的應(yīng)用。04映射與函數(shù)01020304映射定義有向性單值性滿射、單射與雙射映射概念及性質(zhì)對于集合$X$中的任意一個元素$x$，通過映射$f$，在集合$Y$中有唯一確定的元素與之對應(yīng)。映射是有方向的，從集合$X$到集合$Y$，必須指明方向。設(shè)$X$和$Y$是兩個集合，如果存在一個法則$f$，使得對$X$中的每一個元素$x$，按法則$f$，在$Y$中有唯一確定的元素$y$與之對應(yīng)，則稱$f$為從$X$到$Y$的映射，記作$f:XrightarrowY$。根據(jù)映射的定義和性質(zhì)，可以進一步定義滿射、單射和雙射等概念。0102030405函數(shù)定義：設(shè)數(shù)集$DsubsetR$，則稱映射$f:DrightarrowR$為定義在數(shù)集$D$上的函數(shù)，通常簡記為：$y=f(x),xinD$。函數(shù)性質(zhì)有界性：函數(shù)在定義域內(nèi)有界，即存在一個正數(shù)$M$，使得對于所有$xinD$，都有$|f(x)|leqM$。單調(diào)性：函數(shù)在其定義域內(nèi)單調(diào)增加或減少。周期性：函數(shù)在其定義域內(nèi)具有周期性，即存在一個正數(shù)$T$，使得對于所有$xinD$，都有$f(x+T)=f(x)$。函數(shù)概念及性質(zhì)80%80%100%特殊類型函數(shù)介紹對于所有$xinD$，都有$f(x)=C$（其中C為常數(shù)），則稱函數(shù)為常值函數(shù)。形如$y=x^n(ninR)$的函數(shù)稱為冪函數(shù)。形如$y=a^x(a>0,aneq1)$的函數(shù)稱為指數(shù)函數(shù)。常值函數(shù)冪函數(shù)指數(shù)函數(shù)05等價關(guān)系與劃分自反性對稱性傳遞性等價關(guān)系定義及性質(zhì)如果$xRy$，則必有$yRx$，即關(guān)系$R$在元素間是對稱的。如果$xRy$且$yRz$，則必有$xRz$，即關(guān)系$R$在元素間是可傳遞的。對于任意元素$x$，都有$xRx$，即每個元素與自身具有關(guān)系$R$。010203非空性互斥性完備性劃分概念及性質(zhì)劃分的每個子集（塊）都不是空集。劃分的任意兩個子集（塊）之間沒有交集。劃分的所有子集的并集等于原集合。03等價類與劃分塊對應(yīng)在等價關(guān)系誘導(dǎo)的劃分中，每個劃分塊對應(yīng)于一個等價類，反之亦然。01等價關(guān)系誘導(dǎo)劃分對于集合$A$上的等價關(guān)系$R$，可以按照關(guān)系$R$將集合$A$劃分為互不相交的子集，每個子集內(nèi)的元素彼此等價。02劃分確定等價關(guān)系給定集合$A$的一個劃分，可以定義一個等價關(guān)系$R$，使得同一子集內(nèi)的元素彼此等價，不同子集的元素不等價。等價關(guān)系與劃分之間聯(lián)系06偏序關(guān)系與格論基礎(chǔ)自反性對于任意x∈A，都有xRx；傳遞性對于任意x,y,z∈A，如果xRy且yRz，則xRz。反對稱性對于任意x,y∈A，如果xRy且yRx，則x=y；偏序關(guān)系的定義設(shè)R是集合A上的一個二元關(guān)系，如果R滿足自反性、反對稱性和傳遞性，則稱R是A上的一個偏序關(guān)系。偏序關(guān)系定義及性質(zhì)格論基本概念介紹交換律對于任意a,b∈L，有a∨b=b∨a和a∧b=b∧a；上確界和下確界的存在性對于任意a,b∈L，都存在上確界a∨b和下確界a∧b；格的定義設(shè)(L,≤)是一個偏序集，如果L中任意兩個元素都有上確界和下確界，則稱(L,≤)是一個格。結(jié)合律對于任意a,b,c∈L，有(a∨b)∨c=a∨(b∨c)和(a∧b)∧c=a∧(b∧c)；吸收律對于任意a,b∈L，有a∨(a∧b)=a和a∧(a∨b)=a。010203偏序關(guān)系的應(yīng)用在計算機科學(xué)中，偏序關(guān)系用于描述數(shù)據(jù)結(jié)構(gòu)中的排序和搜索問題；在經(jīng)濟學(xué)中，偏序關(guān)系用于描述消費者偏好和商品排序問題；偏序關(guān)系和格論在實際問題中應(yīng)用在數(shù)學(xué)中，偏序關(guān)系用于研究