第一章集合論基礎(chǔ)

1、離離 散散 數(shù)數(shù) 學(xué)學(xué)常 州 大 學(xué)任課教師： 朱虹第一篇第一篇 緒緒 言言v離散數(shù)學(xué)的特征和性質(zhì)v此課程的主要學(xué)習(xí)內(nèi)容v此課程的主要學(xué)習(xí)方法第一篇第一篇 緒緒 言言v離散數(shù)學(xué)（又稱組合數(shù)學(xué)）是數(shù)學(xué)的一個(gè)分支，它以離散量作為其主要研究對(duì)象，是研究離散對(duì)象的結(jié)構(gòu)以及它們之間相互關(guān)系的科學(xué)。由于計(jì)算機(jī)不論硬件還是軟件都屬于離散結(jié)構(gòu)，所以計(jì)算機(jī)所應(yīng)用的數(shù)學(xué)必是離散數(shù)學(xué)。v正如馬克思所說的：“一門科學(xué)，只有當(dāng)它能夠運(yùn)用數(shù)學(xué)時(shí)，才算真正發(fā)展了?！庇?jì)算機(jī)正是在離散數(shù)學(xué)中圖靈機(jī)理論的指導(dǎo)下誕生的。第一篇第一篇 緒緒 言言v離散數(shù)學(xué)在企業(yè)管理、交通規(guī)劃、戰(zhàn)爭指揮、金融分析等領(lǐng)域中有很重要的應(yīng)用，例如： 在美國

2、有家公司以組合數(shù)學(xué)命名，用組合數(shù)學(xué)的方法來提高企業(yè)管理的效益。 德國一位著名的組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用。第一篇第一篇 緒緒 言言v離散數(shù)學(xué)在日常生活中的應(yīng)用：v世界地圖著色v裝箱子時(shí)，如何使得箱子盡量裝滿v航空調(diào)度和航班的設(shè)定v中國郵遞員問題v用不同形狀的地磚鋪地，能否鋪滿v船夫要把一只狼、一只羊和一棵白菜運(yùn)過河，其中狼要吃羊，羊要吃白菜，而船每趟只能運(yùn)其中一個(gè)。第一篇第一篇 緒緒 言言v離散數(shù)學(xué)課程是 計(jì)算機(jī)系核心課程 信息類專業(yè)必修課 其它類專業(yè)的重要選修課程v離散數(shù)學(xué)也是后續(xù)課的基礎(chǔ) 第一篇第一篇 緒緒 言言v離散數(shù)學(xué)課程的學(xué)習(xí)可以培養(yǎng)學(xué)生抽象的

3、思維、邏輯推理能力和創(chuàng)新能力。v讓學(xué)生見識(shí)一些重要的數(shù)學(xué)思想、數(shù)學(xué)方 法以及用數(shù)學(xué)解決實(shí)際問題的著名事例。 培養(yǎng)邏輯思維的能力和分析問題解決問題的能力。第一篇第一篇 緒緒 言言v離散數(shù)學(xué)的主要學(xué)習(xí)內(nèi)容： 1. 集合論 2. 代數(shù)系統(tǒng) 3. 圖論 4. 數(shù)理邏輯 *5. 組合數(shù)學(xué) *6. 形式語言與自動(dòng)機(jī)第一篇第一篇 緒緒 言言v特點(diǎn)：內(nèi)容較雜，概念多，定理多，比較抽象，學(xué)習(xí)有一定的難度。v學(xué)習(xí)方法： 1.準(zhǔn)確掌握每個(gè)概念(包括內(nèi)涵及外延)。 2.要有刻苦鉆研的精神,不斷總結(jié)經(jīng)驗(yàn)。 3.在理解內(nèi)容的基礎(chǔ)上，要多做練習(xí)題，從而再進(jìn)一步加深理解所學(xué)內(nèi)容。 4.注意培養(yǎng)分析問題和解決問題的能力參考書目

4、參考書目v離散數(shù)學(xué)及其應(yīng)用，機(jī)械工業(yè)出版社，Kenneth H.Rosen著，袁崇義等譯v離散數(shù)學(xué)，上海科學(xué)技術(shù)文獻(xiàn)出版社，左孝凌等著v離散數(shù)學(xué)，高等教育出版社，屈婉玲等編v這方面的參考書目很多，請(qǐng)大家自己選擇第二篇第二篇 集合論集合論v主要包括如下內(nèi)容： 集合論初步 二元關(guān)系 函數(shù) 有限集和無限集第一章第一章 集合論初步集合論初步v本章主要介紹如下內(nèi)容： 基本概念及集合的表示方法 集合間的關(guān)系 特殊集合 集合的運(yùn)算基本概念基本概念1.集合與元素 集合：是一些確定的對(duì)象(客體)的全體。一般用大寫的英文字母表示。 這里所謂“確定”是指：論域內(nèi)任何對(duì)象，要么屬于這個(gè)集合，要么不屬于這個(gè)集合，是唯一

5、確定的。 元素：集合中的對(duì)象。 ：表示元素與集合的屬于關(guān)系。 例如，N表示自然數(shù)集合，2N， 而1.5不屬于N，寫成 1.5N?；靖拍罨靖拍?. 有限集合與無限集合 這里對(duì)有限集合與無限集合先給出樸素的定義，以后再給出嚴(yán)格的形式定義。 有限集合有限集合：有有限個(gè)元素的集合。 如果A是有限集合，用|A|表示A中元素個(gè)數(shù)。例如，A=1,2,3, 則|A|=3。 無限集合無限集合：有無限個(gè)元素的集合。 對(duì)無限集合的所謂大小的討論，以后再進(jìn)行。基本概念基本概念3.集合的表示方法 列舉法列舉法：將集合中的元素一一列出，寫在大括號(hào)內(nèi)。 例如，N=1,2,3,4, A=a,b,c,d 描述法描述法：用句

6、子描述元素的屬性。 例如，B=x| x是偶數(shù) C=x|x是實(shí)數(shù)且2x5 一般地，A=x|P(x), 其中P(x)是謂詞公式， 如果對(duì)象a使得P(a)為真，則aA，否則aA?；靖拍罨靖拍?. 說明 集合中的元素間次序是無關(guān)緊要的，但是必須是 可以區(qū)分的，即是不同的。例如A=a,b,c，B=c,b,a，C=a,b,c,a，則A、B和C是一樣的。 對(duì)集合中的元素?zé)o任何限制，例如令 A=人，石頭，1，, B=, 本書中常用的幾個(gè)集合符號(hào)的約定： 自然數(shù)集合N= 1,2,3, 整數(shù)集合I，實(shí)數(shù)集合R，有理數(shù)集合Q集合中的元素也可以是集合。例如：2，2特殊集合特殊集合1.全集 E 定義：包含所討論的所

7、有元素的集合，稱之為全集，記作E。 由于討論的問題不同，全集也不同。所以全集不唯一。 例如: 若討論數(shù)，可以把實(shí)數(shù)集看成全集。 若討論人，可以把人類看成全集。 性質(zhì)：對(duì)于任何集合A，都有A在E中。特殊集合特殊集合2.空集 定義：沒有元素的集合，稱之為空集，記作。 性質(zhì)： (1).對(duì)于任何集合A，都有在A中。 (2).空集是唯一的。集合間的關(guān)系集合間的關(guān)系1.包含關(guān)系(子集) (1).定義：A、B是集合，如果A中元素都是B中元素，則稱B包含A，A包含于B，也稱A是B的子集。記作AB。 文氏圖表示如右下圖。 例如，N是自然數(shù)集合， R是實(shí)數(shù)集合，則NR AB集合間的關(guān)系集合間的關(guān)系(2).性質(zhì)：

8、(a). 有自反性，對(duì)任何集合A有AA。 (b). 有傳遞性，對(duì)任何集合A、B、C，有AB且 BC ，則AC。 (c). 有反對(duì)稱性，對(duì)任何集合A、B，有AB且 BA ，則A=B。集合間的關(guān)系集合間的關(guān)系2. 相等關(guān)系 定義：A、B是集合，如果它們的元素完全相同，則稱A與B相等。記作A=B。 性質(zhì)： 有自反性，對(duì)任何集合A，有A=A。 有傳遞性，對(duì)任何集合A、B、C，如果有A=B且 B=C ，則A=C。 有對(duì)稱性，對(duì)任何集合A、B，如果有A=B，則B=A。集合間的關(guān)系集合間的關(guān)系3.真包含關(guān)系(真子集) 定義：A、B是集合，如果AB且AB，則稱B真包含A，A真包含于B，也稱A是B的真子集。記作

9、AB。性質(zhì)： 有傳遞性，對(duì)任何集合A、B、C，如果有AB且 BC ，則AC。集合的運(yùn)算集合的運(yùn)算1.1.交運(yùn)算交運(yùn)算 定義：定義：A、B是集合，由既屬于A，也屬于B的元素構(gòu)成的集合 ,稱之為A與B的交集,記作AB。 例如:A=1,2,3 ,B=2,3,4 則 AB=2,3ABAB集合的運(yùn)算集合的運(yùn)算性質(zhì)： 冪等律冪等律 對(duì)任何集合A，有AA=A。 交換律交換律 對(duì)任何集合A、B，有AB=BA。 結(jié)合律結(jié)合律 對(duì)任何集合A、B、C，有 (AB)C=A(BC)。 同一律同一律 對(duì)任何集合A，有AE=A。 零一律零一律 對(duì)任何集合A，有A=。 AB AB=A。集合的運(yùn)算集合的運(yùn)算2.2.并運(yùn)算并運(yùn)算

10、 定義：定義：A、B是集合，由或?qū)儆贏，或?qū)儆贐的元素構(gòu)成的集合 ,稱之為A與B的并集,記作AB。 例如:A=1,2,3 ,B=2,3,4 則AB=1,2,3,4BAAB集合的運(yùn)算集合的運(yùn)算性質(zhì)： 冪等律冪等律 對(duì)任何集合A，有AA=A。 交換律交換律 對(duì)任何集合A,B，有AB=BA。 結(jié)合律結(jié)合律 對(duì)任何集合A,B,C,有(AB)C=A(BC). 同一律同一律 對(duì)任何集合A，有A=A。 零一律零一律 對(duì)任何集合A，有AE =E 。 集合的運(yùn)算集合的運(yùn)算 分配律分配律 對(duì)任何集合A、B、C，有 A(BC) =(AB)(AC)。 A(BC) =(AB)(AC)。 吸收律吸收律 對(duì)任何集合A、B，

11、有 A(AB)=A A(AB) =A。 AB AB=B。集合的運(yùn)算集合的運(yùn)算3.絕對(duì)補(bǔ)集 定義：定義：A是集合,由不屬于A的元素構(gòu)成的集合 ,稱之為A的絕對(duì)補(bǔ)集,記作A。 例如，E=1,2,3,4，A=2,3, 則A=1,4AEA集合的運(yùn)算集合的運(yùn)算性質(zhì)： 設(shè)A、B、C是任意集合，則 E= =E (A)=A AA= AA=E 注：在這里只有A同時(shí)滿足性質(zhì)（4）（5）（稱作A的惟一性）。證明：此時(shí)我們假設(shè)除了A還有B滿足（4）（5），則有B=B =B (AA)=（B A）（B A ）=E (B A)= B A.同理，我們可以得到A= A B.因此B= A.集合的運(yùn)算集合的運(yùn)算 A-B=AB 德摩

12、根定律（De Morgans Law）： (AB)=AB (AB)=AB集合的運(yùn)算集合的運(yùn)算4.4.差運(yùn)算差運(yùn)算- (- (相對(duì)補(bǔ)集相對(duì)補(bǔ)集) ) 定義：定義：A、B是集合，由屬于A，而不屬于B的元素構(gòu)成的集合 ,稱之為A與B的差集,或B對(duì)A的相對(duì)補(bǔ)集，記作A-B。 從圖中可以知道A-B=AB例如:A=1,2,3,B=2,3,4 則A-B=1ABA-B集合的運(yùn)算集合的運(yùn)算性質(zhì)：設(shè)A、B、C是任意集合，則 A-=A -A= A-A= A-BA AB A-B= (A-B)-C=(A-C)-(B-C) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) A(B-C)=(AB)-(

13、AC) 但對(duì)- 是不可分配的，如A(A-B)=A，而(AA)-(AB)=集合的運(yùn)算集合的運(yùn)算v補(bǔ)集與差集的關(guān)系：v A=E-A ，A(B)=A-B，AA=， AA=E v利用以上性質(zhì)我們可以得到著名的德.摩根定律（De Morgans Law): v (A B)= A Bv (A B)= A Bv我們簡單地證明一下第一個(gè)式子：v只需證： (A B) (A B)=E 和 (A B) (A B)=集合的運(yùn)算集合的運(yùn)算顯然： (A B) (A B) =(A B) (A) (A B) (B) =E E=E及： (A B) (A B) =(A B) (A） (A B) (B) = (B-A) (A-B)

14、 = 其中，我們用到了 B (A)=B-A 和 A(B)=A-B 由補(bǔ)集的惟一性，得 (A B)=(A B) 同理可得 (A B)=(A B)集合的運(yùn)算集合的運(yùn)算v(6)(A-B)-C=(A-C)-(B-C)v證明:v（6）(A-B)-C=(A-B) C=(A B) Cv同時(shí)(A-C)-(B-C)=(A C) (B C)v = (A C) B Cv = (A C) B (A C) Cv = (A C) B v = (A C) B v = =(A B) C 集合的運(yùn)算集合的運(yùn)算5.對(duì)稱差 定義：定義：A、B是集合,由屬于A而不屬于B，或者屬于B而不屬于A的元素構(gòu)成的集合,稱之為A與B的對(duì)稱差,記

15、作AB。由右圖可以看出：AB= AB- AB=(A-B) (B-A) 例如：A=1,2,3， B=2,3,4 則AB=1,4ABABE集合的運(yùn)算集合的運(yùn)算性質(zhì)： 交換律交換律 對(duì)任何集合A、B，有AB=BA。 結(jié)合律結(jié)合律 對(duì)任何集合A、B、C，有 (AB)C=A(BC)。 同一律同一律 對(duì)任何集合A，有A=A。 對(duì)任何集合A，有AA=。 對(duì)可分配 A(BC)=(AB)(AC)集合的運(yùn)算集合的運(yùn)算6. 集合的冪集定義: A是集合，由A的所有子集構(gòu)成的集合，稱之為A的冪集。記作P(A)或2A。P(A)=B| BA例如: A A的冪集P(A) a ,a a,b ,a,b,a,b集合的運(yùn)算集合的運(yùn)算性質(zhì)： (1).給定有限集合A，如果|A|=n, 則|P(A)|=2n。 例如：a,b,c 則 P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c 238C33C32C31C30|P(A)|集合的運(yùn)算集合的運(yùn)算7. 笛卡爾乘積 先給出n元有序組的定義 定義：n個(gè)（n1）按一定次序排列的客體a1 , a2 , ，an 組成一個(gè)有序序列，稱為n元有序組，記為（ a1 , a2 , ，an ）。 例如我國當(dāng)前使用的身份證號(hào)碼是由一個(gè)七元有序組組成（省、市、區(qū)、出生年