《離散數(shù)學(xué)]》PPT課件.ppt

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

1、集合論由于集合論的語言適合于描述和研究離散對象及其關(guān)系，所以也是計(jì)算機(jī)科學(xué)與工程的理論基礎(chǔ)，在程序設(shè)計(jì)、關(guān)系數(shù)據(jù)庫、排隊(duì)論、開關(guān)理論，形式語言和自動(dòng)機(jī)理論等學(xué)科領(lǐng)域中都有重要的應(yīng)用。本篇主要介紹：集合、二元關(guān)系和函數(shù)，以及集合的基數(shù)問題。集合論第三章集合與關(guān)系§1集合的概念和表示法§2集合的運(yùn)算§4序偶與笛卡爾積§5關(guān)系及其表示§6關(guān)系的性質(zhì)§7復(fù)合關(guān)系和逆關(guān)系§8關(guān)系的閉包運(yùn)算§9集合的劃分和覆蓋§10等價(jià)關(guān)系與等價(jià)類§11相容關(guān)系§12序關(guān)系§1集合的概念和表示法1、集合與元素（1）集合：就是把人們直觀

2、的或想象中的某些確定的能夠區(qū)分的對象匯合在一起組成的一個(gè)整體。討論：①一些不同的確定的對象之全體。例：1000以內(nèi)的素?cái)?shù)的集合；這個(gè)班里高個(gè)子學(xué)生的集合；（不是集合）②元素（成員）：組成集合的各個(gè)對象。③符號：用大寫英文字母表示集合，用小寫英文字母或其它符號表示元素。集合：A，B….元素：a，b….§1集合的概念和表示法④元素與集合間的關(guān)系：若a是集合S中的元素，則可寫成a?S；若b不是集S合中的元素，則可寫成b?S。⑤集合S的基數(shù)(勢)：S中的元素個(gè)數(shù)。用

3、S

4、表示。⑥有限集合：集合的基數(shù)（元素）是有限的

5、。無限集合：集合的基數(shù)（元素）是無限的?！?集合的概念和表示法⑦本書中常用集合符:Im(m≥1)有限個(gè)正整數(shù)的集合{1,2,3……m}Nm(m≥0)有限個(gè)自然數(shù)的集合{0,1,2……m}以上是有限集合,下面是無限集合：N自然數(shù)集合{0,1,2……}I+正整數(shù)集合{1,2,3……}I整數(shù)集合{……-1,0,1,2……}P素?cái)?shù)集合{大于1的正整數(shù)，只能被1和自己整除}Q有理數(shù)集合{i/j.i、j均為整數(shù)且j≠0}R實(shí)數(shù)集合{有理數(shù)、無理數(shù)}C復(fù)數(shù)集合{a+bi，a、b可為實(shí)數(shù)}§1集合的概念和表示法(2)集合的

6、表示方法:(a)枚舉法(列舉法)把集合的元素列于花括號內(nèi)。例：命題的真假值組成的集合：S={T,F}自然數(shù)0,1,2,3,4五個(gè)元素的集合：P={0,1,2,3,4}(b)謂詞公式描述法所有集合均可用謂詞公式來表示：S={x

7、p(x)}§1集合的概念和表示法例：大于10的整數(shù)的集合：S1={x

8、x?I∧x>10}偶整數(shù)集合：S2={x

9、?y(y?I∧x=2y)}有限個(gè)元素集合：S3={1,2,3,4,5}={x

10、x?I∧(1≤x≤5)}S4={F,T}={x

11、x=T∨x=F}S5={1,4}={x

12、(x2-

13、5x+4=0)}(c)同一集合可以用多種不同的形式表示。(d)集合也可作為某一集合的元素。例：S={a,{1,2},p,{q}}§1集合的概念和表示法(3)三個(gè)特殊集合：空集、全集合、集合族《定義》如果一個(gè)集合包含了所要討論的每一個(gè)集合，則稱該集合為全集合，簡稱全集，用E表示。E={x

14、p(x)∨?p(x)}p(x)為任何謂詞公式《定義》不擁有任何元素的集合稱為空集（或稱零集），用?表示?={x

15、p(x)∧?p(x)}={}注意：?≠{?}前者是空集，是沒有元素的集合；后者是以?作為元素的集合。§1集合的概

16、念和表示法《定義》集合中的元素均為集合，稱這樣的集合為集合族。例A={{a}，，{c、d}}2、集合之間的關(guān)系《公理》給定二個(gè)集合A和B，當(dāng)且僅當(dāng)A和B具有同樣的元素（成員），則A和B才是相等的，記作A=B并規(guī)定：（A=B）??x(x?A?x?B)例：{a,b,c}={b,a,a,c,c}§1集合的概念和表示法例：{a,b,c}={b,c,a}例：設(shè)P={{1,2},4}，Q={1,2,4}，則P?Q《定義》設(shè)A、B是任意二個(gè)集合，如果集合A的每一個(gè)元素都是B的一個(gè)元素，則稱A是B的子集，或者說A包含

17、于B，或者說B包含A，記作A?B，或者B?A。并規(guī)定：A?B?B?A??x(x?A→x?B)§1集合的概念和表示法例：A1={1,2,3}A2={0}A3={1,2,3,0}B={1,2,3,0}則A1、A2、A3均為B的子集合，并記為A1?B，A2?B，A3?B《定義》設(shè)A、B是任意二個(gè)集合，若A?B且A≠B，則稱A是B的真子集，記作A?B（A真包含于B）并規(guī)定：A?B?（A?B∧A≠B）§1集合的概念和表示法注意：區(qū)分“?”和“?”的關(guān)系：“?”關(guān)系是指集合和該集合中元素之間的關(guān)系。例：S={a,

18、,c}則a?S，?S，c?S而“?”關(guān)系是指二個(gè)集合之間的關(guān)系。例：S1={a,b}S2={a,b,1,2}則S1?S2若A不包含于B，則也可表示成A?B《定理》設(shè)E是全集，A是一個(gè)集合，則一定有A?E?！?集合的概念和表示法《定理》設(shè)A、B是任意二個(gè)集合，當(dāng)且僅當(dāng)A?B和B?A才有A=B。證明：(ⅰ)充分性：（A=B）?（A?B∧B?A）(A=B)??x(x?A→x?B∧x?B→x?A)??x(x?A→x