1、離散數(shù)學(xué)(I),主講教師: 馮莎莎 助課教師: 林 海 吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 智能決策與自動(dòng)推理教研室,馮莎莎 林 海 教研室電話: 5166478,學(xué)習(xí)這門(mén)課的目的: 1. 知識(shí)本身 2. 數(shù)學(xué)訓(xùn)練 學(xué)習(xí)這門(mén)課的方法: 1. 認(rèn)真理解概念 2. 認(rèn)真讀書(shū)中的內(nèi)容 3. 做題,基本內(nèi)容,第一章 集合論基礎(chǔ)（集合論） 第二章 命題邏輯 第三章 謂詞邏輯 第四章 圖與網(wǎng)絡(luò) （圖論） 第五章 數(shù)論基礎(chǔ) （數(shù)論） 第六章第八章 （抽象代數(shù)）,（數(shù)理邏輯）,第一章 集合論基礎(chǔ),1.1 集合的基本概念 1.2 關(guān) 系 1.3 映 射,康托爾（G.Cantor,18451918 )，德國(guó)數(shù)學(xué)家。,他

2、創(chuàng)立了集合論作為實(shí)數(shù)理論，以至整個(gè)微積分理論體系的基礎(chǔ)。,1845年3月3日，喬治康托生于俄國(guó)的一個(gè)丹麥猶太血統(tǒng)的家庭。 1856年康托和他的父母一起遷到德國(guó)的法蘭克福。像許多優(yōu)秀的數(shù)學(xué)家一樣，他在中學(xué)階段就表現(xiàn)出一種對(duì)數(shù)學(xué)的特殊敏感，并不時(shí)得出令人驚奇的結(jié)論。 他的父親力促他學(xué)工，因而康托在1863年帶著這個(gè)目地進(jìn)入了柏林大學(xué)。這時(shí)柏林大學(xué)正在形成一個(gè)數(shù)學(xué)教學(xué)與研究的中心?？低泻茉缇拖蛲@所由魏爾斯特拉斯占據(jù)著的世界數(shù)學(xué)中心之一。所以在柏林大學(xué)，康托受了魏爾斯特拉斯的影響而轉(zhuǎn)到純粹的數(shù)學(xué)。 他在1869年取得在哈勒大學(xué)任教的資格，不久后就升為副教授，并在1879年被升為正教授。 1874年康

3、托在克列勒的數(shù)學(xué)雜志上發(fā)表了關(guān)于無(wú)窮集合理論的第一篇革命性文章。數(shù)學(xué)史上一般認(rèn)為這篇文章的發(fā)表標(biāo)志著集合論的誕生。,克羅內(nèi)克（L.Kronecker，18231891），是康托爾的老師，他用各種用得上的尖刻語(yǔ)言，粗暴地、連續(xù)不斷地攻擊康托爾達(dá)十年之久。他甚至在柏林大學(xué)的學(xué)生面前公開(kāi)攻擊康托爾。橫加阻撓康托爾在柏林得到一個(gè)薪金較高、聲望更大的教授職位。使得康托爾想在柏林得到職位而改善其地位的任何努力都遭到挫折。 法國(guó)數(shù)學(xué)家龐加萊（H.Poincare，18541912）：我個(gè)人，而且還不只我一人，認(rèn)為重要之點(diǎn)在于，切勿引進(jìn)一些不能用有限個(gè)文字去完全定義好的東西。集合論是一個(gè)有趣的“病理學(xué)的情形”

4、，后一代將把（Cantor）集合論當(dāng)作一種疾病，而人們已經(jīng)從中恢復(fù)過(guò)來(lái)了。,德國(guó)數(shù)學(xué)家魏爾（C.H.HermannWeyl，18851955）認(rèn)為，康托爾關(guān)于基數(shù)的等級(jí)觀點(diǎn)是霧上之霧。 菲利克斯.克萊因（F.Klein，18491925）不贊成集合論的思想。 數(shù)學(xué)家HA施瓦茲，康托爾的好友，由于反對(duì)集合論而同康托爾斷交。 . 從1884年春天起，康托爾患了嚴(yán)重的憂郁癥，極度沮喪，神態(tài)不安，精神病時(shí)時(shí)發(fā)作，不得不經(jīng)常住到精神病院的療養(yǎng)所去。變得很自卑，甚至懷疑自己的工作是否可靠。他請(qǐng)求哈勒大學(xué)當(dāng)局把他的數(shù)學(xué)教授職位改為哲學(xué)教授職位。健康狀況逐漸惡化，1918年，他在哈勒大學(xué)附屬精神病院去世。,康

5、托爾的主要研究成果,由于康托爾所創(chuàng)立的樸素集合論產(chǎn)生了悖論，促進(jìn)了集合論公理化的工作。 具有代表性的工作有兩個(gè)： 由德國(guó)數(shù)學(xué)家策梅洛(E.Zermelo)于1908年首先建立，后來(lái)由以色列數(shù)學(xué)家弗蘭克爾(A.A.Fraenkel)，挪威數(shù)學(xué)家斯科倫(T.Skolem)與馮諾依曼(von Neumann)等人于20世紀(jì)20年代加以改進(jìn)的ZF公理集合論系統(tǒng)，加入選擇公理的系統(tǒng)成為ZFC。 von Neumann-Bernays-Gdel公理系統(tǒng)，簡(jiǎn)稱NBG系統(tǒng)。 教材主要介紹康托爾的樸素集合論的工作。,1.1 集合的基本概念,定義 “所要討論的一類對(duì)象的整體” “具有同一性質(zhì)單元的集體” “把人們

6、直觀的或想象的一些確定的、可區(qū)分的對(duì)象匯總在一起成一整體，便是一個(gè)集合” 通常，用大寫(xiě)的英文字母A, B, C,表示集合；,1、二十六個(gè)英文字母構(gòu)成一個(gè)集合； 2、所有的自然數(shù)構(gòu)成一個(gè)集合； 3、這間教室中的所有座椅構(gòu)成一個(gè)集合； 4、平面上的所有點(diǎn)構(gòu)成一個(gè)集合。,例如:,集合的元素,組成一個(gè)集合的那些對(duì)象或單元稱為這個(gè)集合的元素。 通常，用小寫(xiě)的英文字母a, b, c,表示集合中的元素 。,設(shè)A是一個(gè)集合，a是集合A中的元素，記為aA，讀作a屬于A；若a不是集合A中的元素，則記為aA，讀作a不屬于A。 例如：若A是正偶數(shù)集合，則2A，8A，36A；而 3A，9A，17A,屬于,有限個(gè)元素a1

7、,，an構(gòu)成的集合，稱為有窮集或有限集，記為a1,，an； 包含無(wú)限個(gè)元素的集合，稱為無(wú)窮集或無(wú)限集。 例：所有英文字母組成的集合是有窮集，整數(shù)集合是無(wú)窮集。,有窮集 、無(wú)窮集,不含任何元素的集合，稱為空集，記為，有時(shí)也用來(lái)表示。 只有一個(gè)元素a構(gòu)成的集合記為a.,空集,設(shè)A是有窮集合， A中元素的個(gè)數(shù)稱為A的元素?cái)?shù)，記為A。 例如，設(shè)A是所有英文字母組成的集合，則A=26。特別， | |=0,集合的元素?cái)?shù)（基數(shù)）,列舉法；將集合中的元素一一列舉，或列出足夠多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1, 4, 9, 16, 25, 36。 描述法 ；通過(guò)描述集合中元素

8、的共同特征來(lái)表示集合，即S=x | x具有性質(zhì)p 例如： V= x | x是元音字母， B= n | n=a2 , a是自然數(shù),集合的表示法,確定性 互異性 無(wú)序性 多樣性,集合的特征,任何一個(gè)對(duì)象，或者是這個(gè)集合的元素，或者不是，二者必居其一； 例如：A=x|x是自然數(shù)，且x100 B=x|x是年輕人 C=x|x是禿子,確定性,集合中任何兩個(gè)元素都是不同的，即集合中不允許出現(xiàn)重復(fù)的元素。 例如： 集合A=a,b,c,c,b,d，實(shí)際上，應(yīng)該是A=a,b,c,d,互異性,集合與其中的元素的順序無(wú)關(guān) 例如： a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a 表示同一個(gè)集合。,無(wú)序性,

9、集合中的元素可以是任意的對(duì)象，相互獨(dú)立，不要求一定要具備明顯的共同特征。 例如：A=a,a,a,b,a, 1B=1,a,*,-3,a,b,x|x是汽車,地球,多樣性,康托爾的樸素集合論,外延原理 任意兩個(gè)集合相等，當(dāng)且僅當(dāng)?shù)乃鼈冎械母鱾€(gè)元素都是相同的。 概括原理 任給一個(gè)性質(zhì)，都有一個(gè)滿足該性質(zhì)的對(duì)象所組成的集合。 選擇原理 每個(gè)集合都有一個(gè)選擇函數(shù)。,設(shè)集合S=A|A是集合，且AA 若SS，則S是集合S的元素，則根據(jù)S的定義，有S S，與假設(shè)矛盾； 若SS，則S是不以自身為元素的集合，則根據(jù)S的定義，有SS，與假設(shè)矛盾；,羅素悖論(Russells paradox),當(dāng)兩個(gè)集合A和B的元素完

10、全一樣，即A，B實(shí)際上是同一個(gè)集合時(shí)，則稱集合A，B相等，記以A=B。 例：設(shè)A=x|x是偶數(shù)，且0x10，B=2,4,6,8，則A=B。,【定義1】集合相等,設(shè)A，B是兩個(gè)集合，若A的元素都是B的元素，則稱A是B的子集，也稱B包含A，或A包含于B，記以A B，或B A 。 若AB，且AB，則稱A是B的真子集(proper subset)，也稱B真包含A，或A真包含于B，記以AB，或B A 。,【定義2】子集(subset),設(shè)A=2,4,6,8 ，B= x|x是正偶數(shù)， C=x|x是整數(shù),則有A B，B C，AC,并且A B，B C，A C 。,例：,當(dāng)我們所討論的集合都是某一集合的子 集時(shí)

11、，這個(gè)集合就稱為全集，記作E。全 集是相對(duì)的。,對(duì)任意集合A, 有A A。 空集是任意集合的子集，且空集是唯一的。 對(duì)于任意兩個(gè)集合A、B，A=B當(dāng)且僅當(dāng)AB且BA。,重要結(jié)論,是否存在集合A和B, 使得AB 且A B ？若存在，請(qǐng)舉一例。,討論,文氏圖(Venn Diagram)用矩形中的點(diǎn)表示全集，用矩形中的圓周或其它形狀的封閉的曲線內(nèi)部的點(diǎn)表示E的子集，用陰影部分表示所關(guān)心的子集。 例如：集合V=a,e,i,o,u ，用文氏圖表示如下:,E,V,a,u,設(shè)A 是集合，A的所有子集為元素做成的集合稱為A的冪集，記以(A)或 2A。 (A)=S|S A 例： A=a,b,c ，則 (A)=

12、,a,b,c,a,b,a,c,b,c,a,b,c,【定義3】?jī)缂?power set),|()| = () = () = () = , ,若A為有窮集，|A|=n，則|2A | = x(A)當(dāng)且僅當(dāng)xA。 設(shè)A、B是兩個(gè)集合，AB當(dāng)且僅當(dāng)(A)(B)；,冪集的性質(zhì),證明：集合A和B，AB(A)(B),證明：（充分性）任意取x A，x(A),又(A)(B)，故x(B)，則xB， AB成立。 （必要性）任意取x (A)，即x A，又AB，則x B，那么x (B)，(A)(B)成立。,設(shè)C是一個(gè)集合。若C的元素都是集合，則稱C為集合族。 若集合族C可表示為C=SddD，則稱D為集合族C的標(biāo)志（索引）

13、集。,【定義4】集合族、標(biāo)志集,顯然，2A是一個(gè)集合族。 設(shè)A1, A2, A3, 是集合的序列，且兩兩之間互不相同，則集合A1, A2, A3, 是一個(gè)集合族，可表示為Ai| iN，其中,N是自然數(shù)集合，是該集合的標(biāo)志集合。,設(shè)A，B是兩個(gè)集合。所有屬于A或者屬于B的元素做成的集合，稱為A和B的并集，記以AB。即AB=x|xA或xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。,【定義5】集合的并集(Union),并集的文氏圖,A,B,AB,設(shè)A，B是兩個(gè)集合。由屬于A又屬于B的元素組成的集合，稱為A和B的交集，記以AB。即AB=x|xA且xB 例如，令

14、A=a，b，c，d，B=c，d，e，f，于是AB=c，d。,【定義6】集合的交集(Intersection),交集的文氏圖,A,B,AB,證明：（充分性）任意取x A，由于AB=A，故x AB，即x A并且x B，故AB成立。 （必要性）易見(jiàn)AB A成立，往證A AB 成立。任意取x A，由于AB，故x B，即x AB，即A AB，故 AB=A。,證明：AB 當(dāng)且僅當(dāng)AB=A,證明：AB 當(dāng)且僅當(dāng)AB=B,設(shè)A1，A2，An是n個(gè)集合，A1A2An ，簡(jiǎn)記為 A1A2An ，簡(jiǎn)記為,并集和交集的推廣,對(duì)于有限集A1和A2，有 A1 A2 A1 A2 A1 A2 ,容斥原理(principle

15、of inclusion-exclusion),對(duì)于有限集A1，A2和A3，有 A1 A2 A3 = A1 A2 A3 A1 A2 A1 A3 A2 A3 A1 A2 A3 提示： A1 A2 A3 = (A1 A2) A3,設(shè)A1，A2，An是n個(gè)有窮集合，則,容斥原理(principle of inclusion-exclusion),稱為包含排斥原理，簡(jiǎn)稱容斥原理。,設(shè)A，B是兩個(gè)集合。由屬于集合A而不屬于集合B的所有元素組成的集合，稱為A與B的差集，記以A-B，或AB。即A-B=x|xA且xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是A - B=a，b。,【定義7】集合的差

16、集(Difference),差集的文氏圖,A,B,A-B,E,設(shè)A是一個(gè)集合，全集E與A的差集稱為A的余集或補(bǔ)集，記以A。即A=E-A 例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。 特別，,【定義8】集合的補(bǔ)集(Complement),補(bǔ)集的文氏圖,A,E,設(shè)A，B是兩個(gè)集合。則A與B的環(huán)和(對(duì)稱差),記以AB, 定義為AB=(A-B)(B-A)。 A與B的對(duì)稱差還有一個(gè)等價(jià)的定義，即AB=(AB)-(AB)。 例：令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=a，b， e，f。,【定義9】集合的對(duì)稱差,對(duì)稱差的文氏圖,A,B,AB=(A-B) (B-A),E

17、,設(shè)A，B是兩個(gè)集合，則A與B的環(huán)積定義為 A B = AB,【定義10】集合的環(huán)積,A,B,E,我們將(a1,a2 , ,an)稱為有序n元組，其中，a1是其第一個(gè)元素， a2是其第二個(gè)元素， ，an是其第n個(gè)元素。 兩個(gè)有序n元組(a1,a2 , ,an)和(b1,b2 , ,bn)相等當(dāng)且僅當(dāng)ai=bi , i=1,2,n,【定義11】有序n元組,對(duì)于有序n元組，當(dāng)n=2時(shí)，我們將其稱作有序二元組，也稱作有序?qū)?或序偶。 有序?qū)Φ奶攸c(diǎn)： 若ab,則(a,b)(b,a) 兩個(gè)有序?qū)?a,b)和(c,d)相等當(dāng)且僅當(dāng)a=c，b=d,【定義12】有序?qū)?設(shè)A，B是兩個(gè)集合，所有有序?qū)?x, y

18、)做成的集合(其中xA，yB)，稱為A，B的直乘積(笛卡兒積)，記以AB。 AB=(x，y)xA且yB。,【定義13】笛卡兒積(Cartesian product),設(shè)A1,A2 , ,An是n個(gè)集合，由所有有序n元組(a1,a2,an)做成的集合(其中aiAi，i=1,2, ,n)，稱為A1,A2,An的直乘積(笛卡兒積)，記以A1A2 An。 A1A2 An=(a1,a2 , ,an) aiAi，i=1,2, ,n 。,【定義14】笛卡兒積的推廣,設(shè)A=1,2，B=a,b,c,則AB=(1,a), (1,b),(1,c),(2,a),(2,b),(2,c)； BA =(a,1), (a,2),(b,1),(b,2),(c,1),(c,2)；,例如：,1. |AB|=A B； 2. 對(duì)任意集合A，有A = ， A= ； 3. 直乘積運(yùn)算不滿足交換律，即ABBA； 4. 直乘積運(yùn)算不滿足結(jié)