離散數(shù)學集合概念表示法

離散數(shù)學集合概念表示法第1頁，共56頁，2023年，2月20日，星期一集合論十九世紀下半葉，康托爾創(chuàng)立了著名的集合論，在集合論剛產生時，曾遭到許多人的猛烈攻擊。但不久這一開創(chuàng)性成果就為廣大數(shù)學家所接受了，并且獲得廣泛而高度的贊譽。數(shù)學家們發(fā)現(xiàn)，從自然數(shù)與康托爾集合論出發(fā)可建立起整個數(shù)學大廈。因而集合論成為現(xiàn)代數(shù)學的基石。第2頁，共56頁，2023年，2月20日，星期一集合論“一切數(shù)學成果可建立在集合論基礎上”這一發(fā)現(xiàn)使數(shù)學家們?yōu)橹兆怼?900年，國際數(shù)學家大會上，法國著名數(shù)學家龐加萊就曾興高采烈地宣稱：“………借助集合論概念，我們可以建造整個數(shù)學大廈……今天，我們可以說絕對的嚴格性已經達到了……”可是，好景不長。1903年，一個震驚數(shù)學界的消息傳出：集合論是有漏洞的！這就是英國數(shù)學家羅素提出的著名的羅素悖論。

第3頁，共56頁，2023年，2月20日，星期一理發(fā)師悖論（羅素悖論）20世紀英國著名哲學家、數(shù)學家羅素提出一個著名的悖論——“理發(fā)師難題”，其內容如下：

西班牙的塞維利亞有一個理發(fā)師，這位理發(fā)師有一條極為特殊的規(guī)定：他只給那些“不給自己刮胡子”的人刮胡子。第4頁，共56頁，2023年，2月20日，星期一羅素悖論羅素構造了一個集合S：S由一切不是自身元素的集合所組成。羅素問：S是否屬于S呢？如果S屬于S，根據S的定義，S就不屬于S；反之，如果S不屬于S，同樣根據定義，S就屬于S。無論如何都是矛盾的。G.弗雷格在收到羅素介紹這一悖論的信后傷心地說：“一個科學家所遇到的最不合心意的事莫過于是在他的工作即將結束時，其基礎崩潰了。羅素先生的一封信正好把我置于這個境地?！笨梢哉f，這一悖論就象在平靜的數(shù)學水面上投下了一塊巨石，而它所引起的巨大反響則導致了第三次數(shù)學危機。第5頁，共56頁，2023年，2月20日，星期一危機產生后，數(shù)學家紛紛提出自己的解決方案：人們希望能夠通過對康托爾的集合論進行改造，通過對集合定義加以限制來排除悖論，這就需要建立新的原則。“這些原則必須足夠狹窄，以保證排除一切矛盾；另一方面又必須充分廣闊，使康托爾集合論中一切有價值的內容得以保存下來。”1908年，策梅羅在這一原則基礎上提出第一個公理化集合論體系，后來經其他數(shù)學家改進，稱為ZF系統(tǒng)。這一公理化集合系統(tǒng)很大程度上彌補了康托爾樸素集合論的缺陷。公理化集合系統(tǒng)的建立，成功排除了集合論中出現(xiàn)的悖論，從而比較圓滿地解決了第三次數(shù)學危機。第6頁，共56頁，2023年，2月20日，星期一集合論第3章集合和關系第4章函數(shù)第7頁，共56頁，2023年，2月20日，星期一第三章集合與關系

本章主要講授集合論的基本知識，包括集合運算、包含排斥原理、笛卡爾積、關系及其性質、關系的運算、特殊關系(包括等價關系、相容關系、序關系)等。 重點是集合的運算、關系及其表示、關系的性質、關系的閉包、等價關系、偏序關系。難點是關系的性質、等價關系、偏序關系的證明。第8頁，共56頁，2023年，2月20日，星期一3-1集合的概念和表示法第9頁，共56頁，2023年，2月20日，星期一

組成集合的對象稱為集合的成員（member）或元素（element）。

集合是一些確定的、作為整體識別的、互相區(qū)別的對象的總體。一、集合的基本概念

一般用大寫字母表示集合，用小寫字母表示元素。例如A表示一個集合，a表示元素，如果a是A的元素，記為：aA，讀作“a屬于A”、“a是A的元素”、“a是A的成員”、“a在A之中”、“A包含a”。如果a不是A的元素，記為：aA

，讀作“a不屬于A”。第10頁，共56頁，2023年，2月20日，星期一空集和只含有有限多個元素的集合稱為有限集（finitesets），否則稱為無限集（infinitesets）。有限集合中元素的個數(shù)稱為集合的基數(shù)（cardinality）。集合A的基數(shù)表示為A。集合的分類第11頁，共56頁，2023年，2月20日，星期一二、集合的三種表示方式：（l）列舉法將集合的元素列舉出來。

（2）描述法

利用一項規(guī)則（一個謂詞公式），描述集合中的元素的共同性質，以便決定某一物體是否屬于該集合。（3）歸納法用遞歸方法定義集合。第12頁，共56頁，2023年，2月20日，星期一1、列舉法：將集合的元素列舉出來例：A={a，b，c，d}，A1={1，3，5，7，9，……}使用列舉法，須列出足夠多的元素以反映集合中成員的特征。如：B={2，4，8，……}若x=2n，則

B={2，4，8，16，32，……}若x=2+n(n-1)，則

B={2，4，8，14，22，……}2、描述法：A={x|P(x)}或A={x：P(x)}例：C={x|1x5，xR}，

D={(x，y)|x2+y21，x，yR}F={x|x是中國的一個省}第13頁，共56頁，2023年，2月20日，星期一說明：1、描述法中C={x|1x5，xR}與C={y|1y5，xR}表示同一個集合。2、集合中元素是無序的。{a，b，c}，{b，c，a}，{c，a，b}表示同一個集合。3、集合中的元素可能也是集合，例：A={1，2，{1}，{1，2，3}}，1A，{1}A。第14頁，共56頁，2023年，2月20日，星期一三、集合的關系1.相等關系相等(外延性公理)：兩個集合是相等的，當且僅當它們有相同的成員。兩個集合A和B相等，記作A=B，兩個集合不相等，記作AB。{0，1}={x|x(x2-2x+1)=0，x

I}{0，1}{1，2}第15頁，共56頁，2023年，2月20日，星期一

抽象原理

對任意謂詞公式P(x)，均存在集合S，使得

S={xP(x)}

兩個集合A和

B相等當且僅當它們具有相同的元素。即對任意集合A、B,

A=Bx(xAxB)

外延公理

概括公理

對任意個體域，任一謂詞公式都確定一個以該域中的對象為元素的集合。即對給定個體域U，對任意謂詞公式P(x)，存在集合S，使得

S＝{xxU∧P(x)}第16頁，共56頁，2023年，2月20日，星期一2.包含關系（子集）定義3-1.1

設A、B是任意兩個集合，如果A的每一個元素都是B的元素，則稱集合A是集合B的子集合（或子集，subsets），或稱A包含在B內，記為AB；或稱B包含A，記為BA

。

即

AB

x(xAxB)

設A，B，C為任意集合，根據定義，顯然有：

包含關系具有自反性：AA

包含關系具有傳遞性：若AB且BC，則AC。第17頁，共56頁，2023年，2月20日，星期一

注：可能AB或BA

，也可能兩者均不成立，不是兩者必居其一。

例：A={1，2，3}，B={1，2}，C={1，3}，

D={3}，F(xiàn)={1，4}，則BA，CA，DC，F(xiàn)A

第18頁，共56頁，2023年，2月20日，星期一第19頁，共56頁，2023年，2月20日，星期一第20頁，共56頁，2023年，2月20日，星期一n元集、m元子集含有n個元素的集合稱為n元集。它的含有m個元素的子集稱為它的m元子集。第21頁，共56頁，2023年，2月20日，星期一四、特殊的集合1、空集定義3-1.3：不含任何元素的集合稱為空集，記作。={x|p(x)p(x)}例如：X={x|x2+1=0，xR}是空集。注意：{}，{}定理3-1.2：對于任意一個集合A，A。證明：反證法，假設存在一個集合A，使得A為假。則存在x且xA，這與空集的定義矛盾，所以A，空集是任意集合的子集。推論：空集是唯一的。證明：設1，2是兩個空集，則12，21，得1=2，所以空集是唯一的。第22頁，共56頁，2023年，2月20日，星期一2、全集定義3-1.4：在一定范圍內，如果所有集合均是某一集合的子集，則稱該集合為全集。記作E。

E={x|p(x)p(x)}3、冪集定義3-1.5：給定集合A，由A的所有子集為元素組成的集合稱為A的冪集，記作(A)或2A。(A)={u|uA}例：設A={1，2，3}，寫出A的冪集(A)。解：(A)={，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}}第23頁，共56頁，2023年，2月20日，星期一

一般地如果|A|=n，則：A的0元子集有Cn0=1個，即空集，1元子集有Cn1個，2元子集有Cn2個，…，n-1元子集有Cnn-1個，n元子集有Cnn個。所以A的子集個數(shù)為：Cn0+Cn1+Cn2+…+Cnn=2n。有：定理3-1.3：如果有限集A有n個元素，其冪集(A)有2n個元素。第24頁，共56頁，2023年，2月20日，星期一例：A={a,}，判斷下列結論是否正確。（1）A，（2）A，（3）{}A（4）{}A，（5）aA，（6）aA，（7）{a}A，（8）{a}A，結論（1）、（2）、（3）、（5）、（8）正確。第25頁，共56頁，2023年，2月20日，星期一上次課集合的概念集合的表示集合的關系特殊的集合：空集、全集、冪集第26頁，共56頁，2023年，2月20日，星期一3-2集合的運算及其性質第27頁，共56頁，2023年，2月20日，星期一一、集合的運算1、交定義3-2.1：設任意兩個集合A和B，由A和B的所有共同元素組成的集合，稱為A和B的交集，記為AB。

AB={x|xAxB}文氏圖第28頁，共56頁，2023年，2月20日，星期一例1：A={0，2，4，6，8，10，12}，B={1，2，3，4，5，6}，AB={2，4，6}例2：設A是平面上所有矩形的集合，B是平面上所有菱形的集合，AB是所有正方形的集合。例3：設A是所有能被K整除的整數(shù)的集合，B是所有能被L整除的整數(shù)的集合，AB是所有能被K與L最小公倍數(shù)整除的整數(shù)的集合。舉例第29頁，共56頁，2023年，2月20日，星期一性質：a)AA=Ab)A=c)AE=Ad)AB=BAe)(AB)C=A(BC)f)ABA，ABB第30頁，共56頁，2023年，2月20日，星期一第31頁，共56頁，2023年，2月20日，星期一例題4：設AB，求證ACBC。證明：對任一個xAC，則xA且xC，因為有AB，若xA，則xB，所以xB且xC，故xBC。因此ACBC。舉例第32頁，共56頁，2023年，2月20日，星期一第33頁，共56頁，2023年，2月20日，星期一2、并集定義3-2.2：設任意兩個集合A和B，所有屬于A或屬于B的元素組成的集合，稱為A和B的并集，記作AB。

AB={x|x

Ax

B}文氏圖第34頁，共56頁，2023年，2月20日，星期一例1：A={1，2，3，4}，B={2，4，5}，AB={1，2，3，4，5}例2：設A是奇數(shù)集合，B是偶數(shù)集合，AB是整數(shù)集合，AB=。舉例第35頁，共56頁，2023年，2月20日，星期一性質：a)AA=Ab)AE=Ec)A=Ad)AB=BAe)(AB)C=A(BC)f)AAB，BAB第36頁，共56頁，2023年，2月20日，星期一例題3：設AB，CD，求證ACBD。證明：對任一xAC，則xA或xC，（1）若xA，則xB，故xBD；（2）若xC，則xD，故xBD。因此ACBD。舉例第37頁，共56頁，2023年，2月20日，星期一定理3-2.1設A，B，C為三個集合，則下列分配律成立。a)A(BC)=(AB)(AC)b)A(BC)=(AB)(AC)證明：a)設S=A(BC)，T=(AB)(AC)，若xS，則xA且xBC，即xA且xB或xA且xC，xAB或xAC即xT，所以ST。反之，若xT，則xAB或xAC，xA且xB或xA且xC，即xA且xBC，于是xS，所以TS。因此，S=T。b)證明完全與a)類似。第38頁，共56頁，2023年，2月20日，星期一定理3-2.2設A，B為任意兩個集合，則下列吸收律成立。a)A(AB)=Ab)A(AB)=A證明：a)A(AB)=(AE)(AB)=A(EB)=AE=Ab)A(AB)=(AA)(AB)=A(AB)=A第39頁，共56頁，2023年，2月20日，星期一定理3-2.3AB，當且僅當AB=B或AB=A。證明：若AB，對任意xA必有xB，（1）對任意xAB，則xA或xB，即xB，所以ABB。（2）又BAB，因此得到AB=B。反之，若AB=B，因為AAB，所以AB。同理可證得AB=A第40頁，共56頁，2023年，2月20日，星期一3、差集、補集定義3-2.3：設A、B是任意兩個集合，所有屬于A而不屬于B的元素組成的集合稱為B對A的補集，或相對補，(或A和B差集)記作A-B。

A-B={x|xA∧xB}文氏圖第41頁，共56頁，2023年，2月20日，星期一定義3-2.4：設E為全集，任一集合A關于E的補，稱為A的絕對補，記作A。A=E-A={x|xE∧xA}文氏圖第42頁，共56頁，2023年，2月20日，星期一性質：a)(A)=Ab)E=c)=Ed)AA=Ee)AA=第43頁，共56頁，2023年，2月20日，星期一定理3-2.4設A，B為任意兩個集合，則下列關系式成立。a)(AB)=ABb)(AB)=AB定理3-2.5設A，B為任意兩個集合，則下列關系式成立。a)A-B=ABb)A-B=A-(AB)定理3-2.6設A，B，C為三個集合，則A(B-C)=(AB)-(AC)定理3-2.7設A，B為任意兩個集合，若AB，則a)BAb)(B-A)A=B第44頁，共56頁，2023年，2月20日，星期一4、對稱差定義3-2.5：設A、B是任意兩個集合，集合A和B的對稱差，其元素或屬于A，或屬于B，但不能既屬于A又屬于B，記作AB。

AB=(A-B)(B-A)文氏圖第45頁，共56頁，2023年，2月20日，星期一性質：a)AB=BAb)A=Ac)AA=d)AB=(AB)(AB)e)(AB)C=A(BC)第46頁，共56頁，2023年，2月20日，星期一3-3包含排斥原理(容斥原理)第47頁，共56頁，2023年，2月20日，星期一包含排斥原理1、定理3-3.1：設A1，A2為有限集合，其元素個數(shù)分別為|A1|，|A2|，則|A1A2|=|A1|+|A2|-|A1A2|，此定理被稱作包含排斥原理。證明：a)當A1A2=，則|A1A2|=|A1|+|A2|b)若A1A2，則|A1|=|A1～A2|+|A1A2|，|A2|=|～A1A2|+|A1A2|所以|A1|+|A2|=|A1～A2|+|A1A2|+|～A1A2|+|A1A2|=|A1～A2|+|～A1A2|+2|A1A2|而|A1～A2|+|～A1A2|+|A1A2|=|A1A2|故|A1A2|=|A1|+|A2|-|A1A2|第48頁，共56頁，2023年，2月20日，星期一解：設A為從1到500的整數(shù)中，能被3除盡的數(shù)的集合。

B為從1到500的整數(shù)中，能被5除盡的數(shù)的集合。則A=[500/3]=166（[x]表示不超過x的最大整數(shù)）B=[500/5]=100AB=[500/（3*5）]=33由包含排斥原理：AB=A+B-AB=166+100-33=233即從1到500的整數(shù)中，能被3或5除盡的數(shù)有233個。

例1：求從1到500的整數(shù)中，能被3或5除盡的數(shù)的個數(shù)。第49頁，共56頁，2023年，2月20日，星期一解：設職員和學生的集合分別是A和B。由已知條件A=10，B=12，AB=5，有AB=A+B-AB=10+12-5=17，則(AB)=E-AB=20-17=3。有3名青年既不是職員又不是學生。例2：在20名青年中有10名是公司職員，12名是學生，其中5名既是職員又是學生，問有幾名既不是職員，又不是學生。第50頁，共56頁，2023年，2月20日，星期一例題3假設在10名青年中有5名是工人，7名是學生，其中兼具工人和學生雙重身份的青年有3名，問有幾名既不是工人又不是學生。解：設工人的集合為W，學生的集合為S。則根據題設有|E|=10，W=5，S=7，WS=3，則WS=W+S-WS=5+7-3=9，則(AB)=E-AB=10-9=1。有1名既不是工人又不是學生。第51頁，共56頁，2023年，2月20日，星期一2、三個集合的包含排斥原理：對于三個集合A1，A2和A3，其元素個數(shù)分別為|A1|，|A2|，|A3|，則|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|第52頁，共56頁，2023年，2月20日，星期一例題