1、離散數學,數學與信息科學學院,第一部分 數理邏輯 第二部分 集合論 第三部分 圖論 第四部分 抽象代數,離散數學,第一部分 數理邏輯,數理邏輯是用數學方法研究推理中前提和 結論之間的形式關系的學科。,推理是由一個或幾個判斷推出一個新判斷的思維形式。,數學方法是指建立一套表意符號體系，對具體 事物進行抽象的形式研究的方法。,第一章 命題邏輯 第二章 一階謂詞邏輯,第一部分 數理邏輯,1.1 命題和命題聯結詞 1.2 命題公式及其賦值 1.3 等值演算與聯結詞完備集 1.4 析取范式與合取范式 1.5 推理的形式結構 1.6 自然推理系統P,第一章 命題邏輯,1. 命題：能判斷真假的陳述句。,包含

2、兩層意思：,（1）必須是陳述句。,（2）能夠確定（分辨）其真值。,1.1 命題和命題聯結詞,1.1 命題和命題聯結詞,2. 命題的真值：判斷結果,注意：此處不糾纏具體命題的真假問題，只是將其作為數學概念來處理。,真值：真用T或1表示，假用F或0表示。,3.命題和真值的符號化,1.1 命題和命題聯結詞,1.1 命題和命題聯結詞,原子命題：不能被分解為更簡單的陳述句 復合命題：原子命題通過聯結詞聯結而成,例：2是有理數是不對的；2是偶素數；2或4是素數；如果2是素數，則3也 是素數；2是素數當且僅當3也是素數。,p：2是有理數，q：2是偶數，r：2是素數，s：3是素數，t：4是素數。,1.1 命題

3、和命題聯結詞,4、命題聯結詞,1.1 命題和命題聯結詞,王化不但成績好而且品德好。,pq：,1.1 命題和命題聯結詞,1.1 命題和命題聯結詞,開關壞了或燈泡壞了。,pq：,例：1.張曉婧愛唱歌或愛聽音樂。 2.張曉婧是內蒙人或是陜西人。 3.張曉婧只能挑選202或203房間。,1.1 命題和命題聯結詞,注意：當排斥或兩邊的情況實際根本不可能同時發生的時候，排斥或也 可抽象為。但為了方便起見一般不這樣抽象。,有位父親對兒子說：“如果我 去書店，就一定給你買電腦 報“。問：在什么情況下， 父親算失信呢？,1.1 命題和命題聯結詞,注意：“只要p，就q，因為p，所以q”，“p僅當q”， 只有q，才

4、p“，”除非q才p“，”除非q，否則非p“都可 抽象為pq。 p，q可以沒有任何內在聯系。,例：1.如果336，那么雪是白的。 2.除非我能工作完成了，我才去看電影。 3.只要天下雨，我就回家。 4.我回家僅當天下雨。,pq的邏輯關系為q是p的必要條件或p是q的充分條件。,1.1 命題和命題聯結詞,1.1 命題和命題聯結詞,p q的邏輯關系為p與q互為充要條件,例：1.3是有理數當且僅當加拿大位于亞洲。 2.兩圓的面積相等，則他們的半徑相等， 反之亦然。,1.1 命題和命題聯結詞,例：今天第一節課上離散數學或數據結構。,例：p：北京比天津人口多 q：224 r：烏鴉是黑色的,1.1 命題和命題

5、聯結詞,5、語句形式化,1.1 命題和命題聯結詞,例：2是有理數是不對的；2是偶素數；2或4是素數；如果2是素數，則3也 是素數；2是素數當且僅當3也是素數。,p：2是有理數，q：2是偶數，r：2是素數，s：3是素數，t：4是素數。,p不對；q且r；r或t；如果r，則s；r當且僅當s。,1.1 命題和命題聯結詞,命題常元：表示具體確定內容的命題。 命題變元：表示不確定具體內容的命題。,1.2 命題公式及其賦值,1.2 命題公式及其賦值,同時約定：（1）最外層的括號可以省去。 （2）不影響運算次序的括號也可以省去。,1.2 命題公式及其賦值,1.2 命題公式及其賦值,1.2 命題公式及其賦值,1

6、.2 命題公式及其賦值,1.2 命題公式及其賦值,1.3 命題公式的等值式,基本等值式（A，B，C為任意命題公式）,1.3 命題公式的等值式,1.3 命題公式的等值式,因A，B，C可以代入任意的命題公式，故以上等值式稱為等值式模式。,由已知的等值式推演出另外一些等值式的過程為等值演算。,1.3 命題公式的等值式,等值演算的應用： 1.驗證等值式 2.判定公式的類型 3.解決工作生活中的判斷問題,1.3 命題公式的等值式,甲、已、丙3人根據口音對王教授是哪人進行了判斷： 甲說：王教授不是蘇州人，是上海人 已說：王教授不是上海人，是蘇州人 丙說：王教授既不是上海人，也不是杭州人 結果3人中有一人全

7、對，一人對一半，一人全錯。問王教授是哪人？,聯結詞的完備集,n個命題變元可以形成22n個不同的真值函數,對于每個真值函數，都可以找到許多與之等值的命題公式， 而每個命題公式對應唯一的與之等值的真值函數。,定義.設S是一個聯結詞集合，如果任何n（n1）元真值 函數都可以由僅含S中的聯結詞構成的公式表示，則 稱S是聯結詞完備集。,聯結詞的完備集,1.4 析取范式與合取范式,定義：命題變元及其否定統稱為文字。 僅由有限個文字構成的析取式稱為簡單（質）析取式。 僅由有限個文字構成的合取式稱為簡單（質）合取式。,注意：單個文字既是簡單析取式又是簡單合取式。,討論：設A為含n個文字的簡單析取式 若A中同時

8、含pi和pi，則？,若A為永真式，則？,若A為永真式，則A中必同時含有pi和pi，反之亦然。,同理有，若A為簡單合取式， A為永假式的充要條件是A中同時含有pi和pi。,定理1. 一個簡單析取式是重言式當且僅當它同時含有某 個命題變元及其他的否定。 一個簡單合取式是矛盾式當且僅當它同時含有某 個命題變元及其他的否定。,1.4 析取范式與合取范式,定義：由有限個簡單合取式構成的析取式稱為析取范式。 由有限個簡單析取式構成的合取式稱為合取范式。 析取范式與合取范式稱為范式。,注意：單個文字、簡單析取式、簡單合取式都既是析取范 式又是合取范式。,1.4 析取范式與合取范式,定理2. 一個析取范式是矛

9、盾式當且僅當它的每個簡單合 取式為矛盾式。 一個合取范式是重言式當且僅當它的每個簡單析 取式為重言式。,定理3.任一命題公式都存在與之等值的析取范式和合取范式。,范式的求法：消去公式中的蘊涵、等價和異或聯結詞 使用雙重否定律和德摩根律，將公式中出現 的否定 詞移到命題變元之前。 利用分配律、結合律將公式化為合（析）取 范式。,范式形式不唯一。,1.4 析取范式與合取范式,定義：在含有n個命題變元的簡單合（析）取式中，若每個 命題變元和 它的否定式不同時出現，而二者之一必 出現且僅出現一次，且第 i個命題變元或它的否定是 出現在從左算起的第i位上（字典序），稱這樣的簡 單合（析）取式為極小（大）

10、項。,性質：n個變元可以形成2n個極小（大）項； 每個極小（大）項有且僅有一個成真（假）賦值； 每組賦值下僅有一個極小（大）項為真（假）； 所有極小（大）項的析（合）取為真（假）；,1.4 析取范式與合取范式,將極小項的成真賦值對應的二進制數轉化為十進制數為i， 將對應的極小項記為mi。 將極大項的成假賦值對應的二進制數轉化為十進制數為i， 將對應的極大項記為Mi。,定義：設由n個命題變元構成的析（合）取范式中所有的簡 單合（析）取式都是極小（大）項，則稱該析取范 式為主析（合）取范式。,1.4 析取范式與合取范式,定理.任何命題公式都存在與之等值的主析取范式和主合取范 式，并且是唯一的。,1

11、.4 析取范式與合取范式,公式法：求析取范式 用同一律補進未出現的命題變元 消去永假或重復出現的變元和極小項 將極小項按下標從小到大排列,真值表法：列出公式及各極小項的真值表，將每組賦值下 公式及極小項真值都為真的極小項進行析取。,主析取范式的求法：,1.公式法 2.真值表法,1.4 析取范式與合取范式,應用：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極小項的編碼的二進制數 成假賦值為合取范式中所含極大項的編碼的二進制數,由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的極小項 2求出與1中求出的極小項下標相同的極大項 3做2中極大項之合取,1.4 析取范式與合取范式,3

12、.判斷兩公式是否等值 若A，B共含有n個命題變元，按n個命題變元求出A與B的 主析取范式A、B，若AB，則AB.,2.判斷公式的類型 設A含有n個命題變元 A為重言式當且僅當A的主析取范式含全部2n個極小項； A為矛盾式當且僅當A的主析取范式不含任何極小項，此 時記為0； A為可滿足式當且僅當A的主析取范式中至少含一個極小項。,例：要在A，B，C中挑選2名出國進修，選派時滿足下列條件： 若A去，則C同去 若B去，則C不能去 若C不去，則A或B可以去 問有幾種選派方案，分別是什么？,4.解決實際問題,1.4 析取范式與合取范式,1.5推理的形式結構,注意： 推理正確實際是排除前提真結論假的情況

13、推理是否正確與前提的排列順序無關 推理正確并不能保證B一定為真,1.5推理的形式結構,推理的形式結構,1.5推理的形式結構,例：若下午溫度超過30度，則王曉燕必去游泳。若她去游 泳，她就不會去看電影。所以若王曉燕沒去看電影， 下午溫度必超過了30度。,p：溫度超過30度 q：王曉燕去游泳 r：王曉燕去看電影,1.5推理的形式結構,1.5推理的形式結構,注意： 以上都是蘊含式模式 若某推理的形式結構與某定律一致，則推理正確 成立的等值式可產生兩條定律 推理定律可產生相應的推理規則,1.5推理的形式結構,1.6自然推理系統P,定義.一個形式系統I由以下4部分組成： 非空的字母表，記作A(I) A(

14、I)中符號構成的合式公式集，記作E(I) E(I)中特殊的公式組成的公理集，記作Ax(I) 推理規則集，記作R(I),任給的前提，應用規則得到結論（可能真）,任給的公理，應用規則得到結論（永真）,1.6自然推理系統P,1.6自然推理系統P,例：若小王是理科生，則他的數學成績一定很好。如果 小王不是理科生，他一定是文科生。小王的數學成績 不好。所以小王是文科生。,p：小王是理科生 q：小王是文科生 r：小王的數學成績很好,1.6自然推理系統P,例：如果小張和小王去看電影，則小李也去看電影。小趙 不去看電影或小張去看電影。小王去看電影。所以， 當小趙去看電影時，小李也去。,p：小張去看電影 q：小

15、王去看電影 r：小李去看電影 s：小趙去看電影,1.6自然推理系統P,2.歸謬法 將結論的否定作為前提引入，能推出矛盾來，則推理正確,例：如果馬會飛或羊不吃草，則母雞就會是飛鳥。如果母 雞是飛鳥，那么烤熟的鴨子還會跑。烤熟的鴨子不會 跑。所以羊吃草。,p：馬會飛 q：羊吃草 r：母雞是飛鳥 s：烤熟的鴨子會跑,1.6自然推理系統P,所有的人總是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,p: q: r:,第二章 謂詞邏輯,第二章 謂詞邏輯,2.1一階邏輯命題符號化 2.2一階邏輯公式及解釋 2.3一階邏輯等值式與置換規則 2.4一階邏輯前束范式 2.5一階邏輯的推理理論,2.1一階邏輯命

16、題符號化,1.個體詞,所研究對象中可以獨立存在的具體的或抽象的客體（事物）,表示具體的或特定的客體,表示抽象或泛指的客體,個體變項的取值范圍稱為個體域，用D表示,宇宙間一切事物組成的稱為全總個體域,2.謂詞,用來刻劃個體詞性質及個體詞之間相互關系的詞,2是有理數 x是無理數 小王與小李同歲 x與y具有關系L,是有理數 是無理數 與同歲 與具有關系L,F： G： H： L：,2.1一階邏輯命題符號化,3.量詞：個體詞之間的數量關系,（1）全稱量詞 “一切的”，“所有的”，“每一個”，“任意的”，“凡”，“都” 記作,4.符號化,確定個體域 確定個體詞、量詞和謂詞 確定聯結詞,2.1一階邏輯命題符

17、號化,例：所有的人都是要死的。 有的人用左手寫字。,注意： 全稱量詞的特性謂詞必須作為蘊涵式的前件引入 存在量詞的特性謂詞必須作為合取式的合取項引入 同一命題，不同的個體域符號化的形式可能不同 未指明個體域即為全總個體域,2.1一階邏輯命題符號化,例：在美國留學的學生未必都是亞洲人。 有的兔子比所有的烏龜跑的快。 對任意的整數x，都存在整數y使得xy10。,注意： 多個量詞出現時，順序一般不能隨便換 有些命題符號化形式不唯一,2.1一階邏輯命題符號化,2.2一階邏輯公式及解釋,2.2一階邏輯公式及解釋,合式公式也稱謂詞公式，簡稱公式,2.2一階邏輯公式及解釋,2.2一階邏輯公式及解釋,2.2一

18、階邏輯公式及解釋,2.2一階邏輯公式及解釋,定理.閉式在任何解釋下都變成命題。,2.2一階邏輯公式及解釋,2.2一階邏輯公式及解釋,定理.重言式的代換實例都是永真式，矛盾式的代換 實例都是矛盾式。,2.2一階邏輯公式及解釋,2.3一階邏輯等值式與置換規則,第一組 命題邏輯中等值式模式的代換實例都是一階邏 輯的等值式模式,第二組 一階邏輯中特殊的等值式,2.3一階邏輯等值式與置換規則,D=N，F(x)：x是奇數 G(x)：x是偶數,2.3一階邏輯等值式與置換規則,2.3一階邏輯等值式與置換規則,2.3一階邏輯等值式與置換規則,2.4一階邏輯前束范式,為了方便使用謂詞公式進行定理證明和邏輯推理，需

19、要 把謂詞公式變換為便于使用的規范形式，就是范式。,定理1：任一謂詞公式都可以化成為與之等值的前束范式。,2.4一階邏輯前束范式,2.4一階邏輯前束范式,2.5一階邏輯的推理理論,在一階邏輯中，稱永真的蘊涵式為推理定律。若一個推理 的形式結構正是某條推理定律，則該推理顯然是正確的。,第一組 命題邏輯推理定律的代換實例,第二組 由基本等值式生成的推理定律,第三組 以下重要定律,第四組 消去量詞和引入量詞的推理規則,1、全稱量詞消去規則（UI）,2.5一階邏輯的推理理論,UI規則成立的條件： （1）取代x的y應為任意不在A(x)中約束出現的個體變項； （2）用y取代A(x)中自由出現的x時，必須將

20、所有的自由出現x都取代； （3）自由變元y也可替換為個體域中任意的個體常元c，c為任意不在A(x)中出現過的個體常項。,2.5一階邏輯的推理理論,含義：如果個體域的所有個體都具有性質A，則個體域中 的任一個個體都具有性質A。,2、存在量詞消去規則（EI）,含義：如果個體域存在有性質A的個體，則個體域中必有 某一個個體具有性質A。,2.5一階邏輯的推理理論,ES規則成立的條件： （1）c是個體域中使A為真的特定的個體常項； （2）c不曾在A(x)或前面的推導公式中出現過； （3）A（x）中除x外還有其他自由變元時，不能用此規則,2.5一階邏輯的推理理論,3、全稱量詞引入規則（UG）,UG規則成立

21、的條件： （1）y在A（y）中自由出現，且y取任何值時A均為真； （2）x不在A（y）中約束出現。,含義：如果個體域的任意個體都具有性質A，則個體域中 的所有個體都具有性質A。,2.5一階邏輯的推理理論,4、存在量詞引入規則（EG）,EG規則成立的條件： （1）c是個體域中某個確定的個體； （2）代替c的x不在A（c）中出現過。,含義：如果個體域有某一個個體c具有性質A，則個體域中 必存在具有性質A的個體。,2.5一階邏輯的推理理論,定義.一階邏輯自然推理系統F的定義 1.字母表：同一階語言的字母表 2.合式公式：同一階語言合式公式的定義 3.推理規則 a.前提引入規則 b.結論引入規則 c.

22、置換規則 d.假言推理規則 e.附加規則 f.化簡規則 g.拒取式規則 h.假言三段論規則 i.析取三段論規則 j.構造性二難規則 k.合取引入規則 l. UI，EI，UG，EG,2.5一階邏輯的推理理論,例7：證明邏輯三段論 所有的人總是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,2.5一階邏輯的推理理論,2.5一階邏輯的推理理論,例10：如果一個人怕困難就不會獲得成功。每一個人或 者獲得成功或者是失敗的。有些人未曾失敗過，所以有 些人不怕困難。（個體域是人的集合）判斷這個推理是 否正確。,例9：根據前提集合：同事之間總是有工作矛盾的， 張平和李明沒有工作矛盾，能得出什么結論？,第二部

23、分 集合論,第三章 集合代數 第四章 二元關系 第五章 函數,第三章 集合代數,3.1 集合的基本概念 3.2 集合的運算 3.3 集合恒等式,一、集合的概念 集合（set)的含義：一個集合是作為整體識別的、確定的、互相區別的一些事物的聚集（全體或總體等)。 構成一個集合的每個事物，成為這個集合中的元素或成員。集合一般用A、B、C表示，集合中的元素用a、b、c表示。但這不是絕對的，因為一個集合可以作為另一個集合的元素。 如果x是集合s的一個元素,記作 ; y不是集合s的元素，記作,3.1集合的基本概念,例1： 1.偶素數集合。 2.二進制的基數集合。 3.英文字母的集合。 4.全體實數的集合。

24、 5.自然數集合。 6.整數集合。 7.有理數集合。 8.素數集合。,3.1集合的基本概念,3.1集合的基本概念,集合的表示方法: 1.列舉法（枚舉法、外延法） 把集合的所有元素（元素較少時）寫在一個花括號內;列出足夠多的元素（元素很多或無窮時）以反映集合中元素的特征。 如例1中的1、2、3、5可分別表示為： 2 0，1 a，b，cz，A，B，CZ 1，2，3,3.1集合的基本概念,2.描述法（概括法） 將集合中的元素的性質用一個謂詞公式來描述，S=X|P(X),意義為:集合S由且僅由滿足為此公式P(X)的對象組成，即 ，當且僅當p(a)為真。 如例1中的4、6、7可表示為：,3.文氏圖 用圖

25、形圖像直觀的描述集合之間的相互關系和有關運算。,3.1集合的基本概念,幾個常見集合的表示符號： N：自然數集合，N=0，1，2，3； I：整數集合； P：素數或質數集合； Q：有理數集合； R：實數集合； C：復數集合；,3.1集合的基本概念,集合的特性: A.互異性：一個集合的個元素是可以區分開的，即每一 元素只出現一次。 B.無序性：集合中元素排列順序無關緊要，即集合表示 形式的不唯一性。 例2：a，b，c=b，c，a=c，a，b=a，c，b= b，a，c=c，b，a,3.1集合的基本概念,C.確定性：任一事物是否屬于某一集合，回答是確定的。,例3：“好書”的全體，這不構成集合。,注意：一

26、個集合是已知的，指的是對任一元素，利用某種方法可以判斷它是否是這個集合的元素，而不是把集合的每一個元素都給出來。,3.1集合的基本概念,集合的元素可以是任何具體或抽象的事物，包括別的集合，但不能是本集合自身。,例4：在一個住著一些人家的偏僻孤島上，島上只有一個理發師a，a給且只給島上所有不能自己理發的人理發。問誰給a理發？,定義1.設A和B是兩個集合，若A中的每一個元素都是B的元素，則稱A是B的子集，也稱B包含A,記作,3.1集合的基本概念,定義2.設A和B是任意兩個集合，若A包含B且B包含A，則稱A與B相等，記作A=B. 即，,二、集合的關系,3.1集合的基本概念,定義3.若A是B的子集且

27、，則稱A為B的真子集，或稱B真包含A，記作，B稱為A的超集。,集合的相等關系的性質：,設A,B,C為3個集合， 集合的包含關系的性質:,3.1集合的基本概念,定義4.不包含任何元素的集合稱為空集，記作或,3.1集合的基本概念,三、特殊集合,定義4：在一定范圍內，如果所有集合均為某一集合的子集，則稱該集合為全集，記作E。,定義5.集合中元素的個數稱為基數或勢，用|A|表示。 基數是有限數的集合稱為有限集，否則稱為無限集。,全集是相對的，不同的問題有不同的全集，即使是同一個問題也可以取不同的全集 。,3.1集合的基本概念,3.1集合的基本概念,含n個元素的集合簡稱n元集，其含有k(kn)個元素的子

28、集稱為它的k元子集。,定義6.由集合S的所有子集組成的集合，稱為集合S的冪 集，記作P（S）。表示為：,有限集S ，|P（S）|=2|S|,例：Aa，b，c，d，c,3.2集合的運算,一、集合的基本運算,3.2集合的運算,定義5.設A 為集合， A 的元素的元素構成的集合稱為A的廣義并，記作A 。,3.2集合的運算,A x|z (zA xz),若A A1,A2,，An，則A A1A2 An,定義6.設A 為非空集合， A 的所有元素的公共元素構成的集合稱為A的廣義交，記作A 。,A x|z (zA xz),若A A1,A2,，An，則A A1 A2 An,例：Aa，b，c，a，b，e B=a

29、C=a，c，d,集合運算的優先級： 高級：廣義并、廣義交、絕對補、求冪集；同級按從右向左的順 序進行 低級：并、交、相對補和對稱差；同級按從左向右的順序進行,3.2集合的運算,3.2集合的運算,文氏圖可以用來描述集合間的關系及其運算.在文氏圖中,全集用矩形表示,子集用圓形表示,陰影部分表示運算結果的集合.,二、文氏圖,3.2集合的運算,3.3集合恒等式,一、集合運算定律,以下列出集合性質中最主要的幾條基本定律，對于全集E的任意子集A，B，C，有：,3.3集合恒等式,1、基本定義法,根據集合相等的充要條件等式兩邊互為子集或由定義進行等價推理。,2、公式法,利用已證明過的恒等式去證明另外的恒等式。

30、若表達式中出現形為 A-B的差集時，用功能完備律先將運算“-”轉化為運算“ ”和“”。,二、集合恒等式證明,3.3集合恒等式,3.3集合恒等式,3.3集合恒等式,3.3集合恒等式,小 結,集合的概念 集合的特性 集合的表示方法:列舉法、描述法、文氏圖 集合的運算：并、交、補、差、求冪 集合間的關系：包含、相等 集合恒等式的證明：定義法、公式法、成員表法,第四章二元關系,4.1 有序對與笛卡兒積 4.2 二元關系 4.3 關系的運算 4.4 關系的性質 4.5 關系的閉包 4.6 劃分和等價關系 4.7 偏序關系,定義1.由兩個具有固定次序的個體a，b組成的序列,稱為序偶,記作.其中a,b稱為序

31、偶的分量.,定義2.設和是兩個序偶,若a=c且b=d,則稱這兩個序偶相等,記作=.,區別:集合a,b=b,a = (a=b),4.1 有序對與笛卡兒積,例3:設A=a,b,c,B=1,0,則,4.1 有序對與笛卡兒積,定義3.設集合A，B，以A的元素作為第一元素，B的元算作為第二元素 的有序對構成的集合稱為A與B的笛卡兒積，記作AB，符號化為 AB =|xAyB,性質1. A=， A=,例4:設A=a,b,B=0,1,C=u,v則,4.1 有序對與笛卡兒積,4.1 有序對與笛卡兒積,4.1 有序對與笛卡兒積,性質5.若AC BD，則A B CD。,4.1 有序對與笛卡兒積,其逆命題不成立。 A

32、=B=，成立； A ，B ，成立； A= 且 B ，不成立； A 且B= ，不成立。,定義4.由n個具有給定次序的個體a1，a2，an組成的序列，稱為有序n元組，記作，其中ai稱為第i個分量。 =當且僅當ai=bi（i=1，2，3，n）。 有序n元組仍然是序偶，即=，an。,4.1 有序對與笛卡兒積,定義5. 設A1，A2，An是任意的n個集合，所有有序n元組組成的集合，稱為集合A1，A2，An的笛卡兒積，并用 表示。其中 （i=1，2，n）,4.1 有序對與笛卡兒積,4.2 二元關系,定義1.若一個集合滿足以下條件之一： （1）集合非空，且它的元素都是有序對 （2）集合是空集 則稱該集合為一

33、個二元關系。,一、關系的定義,4.2 二元關系,例2:任意兩個集合A,B,若|A|=n,|B|=m,求A到B共有多少不同的二元關系?,4.2 二元關系,二、特殊關系,例5.設A=2,3,4,B=2,3,4,5,6,定義A到B的二元關系R:aRb當且僅當a整除b.求R,MR,R=，,4.2 二元關系,三、關系的表示方法,4.2 二元關系,一個有限集合A上的關系R還可以用一個稱為R的關系圖來表示。,4.2 二元關系,例6：設A=a，b，c，d，e，A上關系R=，則R的關系圖為：,例3:設A=1,2,3,4,5,6,B=a,b,c,d, R=,求domR,ranR.,解:domR=2,3,4,6,r

34、anR=a,b,d,4.3 關系的運算,例:1.Z上的關系.,3.空關系的逆是空關系.,例3中R的逆關系R-1=,4.3 關系的運算,4.3 關系的運算,例：1. R1=是的兄弟，R2=是的父親,2. A=1，2，3，4，5，R，S是A上的二元關系 R=， S=，,4.3 關系的運算,關系是以序偶為元素的集合，故可對關系進行集合的運算以產生新的關系。作為關系，絕對補運算是對全關系而言的。,4.3 關系的運算,2. A=1，2，3，4，5，R，S是A上的二元關系 R=， S=，,由此可知，合成關系不滿足交換律，滿足結合律。,4.3 關系的運算,定理8.關系矩陣的乘法滿足結合律，即MR1（MR2M

35、R3）=（MR1MR2）MR3,4.3 關系的運算,定理9.設R1是一個由A1到A2的關系，R2是一個由A2到A3的關系，Rn是一個由An到An+1的關系（Ai都是有限集）。它們的關系矩陣分別是MR1，MR2，MRn，則合成關系R1R2Rn的關系矩陣MR1R2Rn=MR1MR2MRn。,定義5.設R為A上的關系，n為自然數，則R的n次冪定義為： R0=|xA=IA Rn+1=RnR,4.3 關系的運算,冪運算的求解：,若R是列舉法表示，可進行多次右復合；,例：A=a，b，c，d，R=，,例：設A=a，b，c，d，R=，則R0， R2 ，R3，R4。,R0=，,R2=，,R3=，,R4=，,4.

36、3 關系的運算,若R用關系矩陣M表示，則Rn的關系矩陣是Mn；,若R是用關系圖G表示的，則可由G得Rn的關系圖G。 G與G的頂點集合相同，考察G中每個頂點x，若在G中 從x出發經過n步長的路徑到達頂點y，則在G中加一條 從x到y的邊。當把所有頂點都考察完后，就得到G。,4.3 關系的運算,4.3 關系的運算,定理10.冪運算滿足指數定律：Rn Rm=Rn+m （Rn）m=Rmn,冪運算的性質：,定理11.設A為n元集，R是A上的關系，則存在s、tN，使得Rs=Rt。,4.4 關系的性質,定義1.設RAA， 若x(xAR)，則稱R是自反的； 若x(xA R)，則稱R是反自反的； 若x(xAR)

37、y (yA R)， 則稱R是非自反的。,定義2.設RAA， 若xy (x,yA RR)， 則稱R是A上的對稱關系； 若xy (x,yA R R x=y)， 則稱R是A上的反對稱關系； 否則，則稱R是A上的非對稱關系。,空關系既是對稱的又是反對稱的.,非空集合上的空關系是反自反的、對稱的、反對稱的、可傳遞的。,空集合上的空關系則是自反的、反自反的、對稱的、反對稱的和可傳遞的。,4.4 關系的性質,非空集合上的全關系是自反的、對稱的、和可傳遞的。,例2.S=a，b，c，S上的關系R1=，R2=，R3=，,例3.在集合S=a，b，c，d上的關系R：， ,，判斷R的性質。,4.4 關系的性質,定理.設

38、R是A上的二元關系，那么R是傳遞的當且僅當RRR。,4.4 關系的性質,根據定義可證明下面幾個定理是成立的。,4.4 關系的性質,4.4 關系的性質,可能有某種關系，既是對稱的，又是反對稱的。,例4.S=a，b，c，S上的關系R=，,某種關系，既不是對稱的，也不是反對稱的。,例5.S上的關系Q=，,定理5.設R在A上是反自反的和可傳遞的，則R必是反對稱的。,4.4 關系的性質,例6.設A=1，2，3，A上的關系R=和S=都是A上的傳遞關系。,傳遞性對并運算不一定保持。,4.4 關系的性質,關系的閉包運算是關系上的一元運算，他把給出的關系R擴充成一新關系Rc，使Rc具有一定的性質，且進行的擴充又

39、是最小的。,4.5 關系的閉包,該定義表明，r（R）（s（R），t（R）是包含R的 最小自反（對稱，傳遞）關系。,必要性：R=r（R），由定義1（1）知，r（R）是自反的，故R是自反的。,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,3.IA的自反、對稱和傳遞閉包是什么？,4.空關系的自反、對稱和傳遞閉包是什么？,例：A=a，b，c，d，R=，,設R、r(R)、s(R)、t(R)的關系矩陣分別為M、Mr、Ms、Mt，則 Mr=M+E Ms=M+M Mt=M+M2+M3+,設R、r(R)、s(R)、t(

40、R)的關系矩陣分別為G、Gr、Gs、Gt，則 考察G中的每個頂點，若沒有環就加上一個，得到Gr； 考察G中每條邊，若有xi到xj的單向邊（ij），則加xj到xi 的反向邊，得Gs； 考察G中每個頂點xi，找出從xi出發的所有2步、3步n步 長的路徑（n為G中的頂點數）。設路徑的終點為xj1、xj2、 、xjk，若沒有從xi到xjl（l=1，2，k)的邊，就加上這條 邊。考察完所有的頂點后，得到Gt。,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,4.5 關系的閉包,4.6 等價關系與劃分,例：A=1,2,3,4,5,6,7,8，R=|x,yAxy(mod3),4.6 等價關系與劃

41、分,4.6 等價關系與劃分,一個集合的劃分往往不是唯一的。,4.6 等價關系與劃分,4.6 等價關系與劃分,等價關系與劃分一一對應。,4.7 偏序關系,4.7 偏序關系,由以上定義可知，在具有偏序關系的集合中任取x、y，有 xy、xy、x與y不可比,例：A=1,2,3，是A上的整除關系。,蓋住關系的關系圖稱哈斯圖.,求法:1.省略關系圖中每個結點處的自環.,2.若xy且y蓋住x,將代表y的結點放在代表x的結點之上,并在x與y之間連線,省去有向邊的箭頭.,4.7 偏序關系,若xy但y不蓋住x，則省去x與y之間的連線。,4.7 偏序關系,4.7 偏序關系,4.7 偏序關系,B的最小元一定是B的下界

42、，同時也是B的最大下界。 B的最大元一定是B的上界，同時也是B的最小上界。,一般的調度問題可以描述為： 給定有窮的任務集T和m臺機器，T上存在偏序關系。如果 t1t2,那么t1完成以后t2才能開始工作。,tT，l(t):表示完成任務t所需的時間 d(t):表示任務t的截止時間。 l(t),d(t)Z+,設開始時間為0，：T0,1,2,，D表示對任務集T的一個 調度方案。 (t)：表示任務t的開始時間； D：表示完成所有任務的最終時間,4.7 偏序關系,假設每項任務都可以在任何一臺機器上進行加工，如果滿足 下述三個條件，則稱其為可行調度 tT，（t）l(t)d(t) i,0 i D,|t|t T

43、 （t） i （t）l(t)| m t,t T,tt （t）l(t) (t),4.7 偏序關系,第五章 函數,5.1 函數的定義與性質 5.2 函數的復合與反函數,5.1 函數的定義與性質,例1：F1=, F2=,定義2.設F、G為函數，則F=GFGGF. 即滿足條件：domF=domG xdomF，都F(x)=G(x).,5.1 函數的定義與性質,5.1 函數的定義與性質,5.1 函數的定義與性質,5.1 函數的定義與性質,5.1 函數的定義與性質,定義7,單調函數可以定義于一般的偏序集上。 每個子集對應一個特征函數，不同的子集則對應不同的特征函數。 故而可用特征函數來標記不同的子集。 給定

44、集合A和A上的等價關系R，就可以確定一個自然映射，不同的 等價關系將確定不同的自然映射。,5.1 函數的定義與性質,算法的評價標準：時間復雜度、空間復雜度 估計復雜度的方法是：選擇一個基本運算，對于給定規模為n的輸入， 計算算法所做基本運算的次數，將這個次數表示為輸入規模的函數。 最壞情況下的復雜度w（n） 平均情況下的復雜度A（n） 算法分析的主要工作就是估計復雜度函數的階。階越高，增長越快， 算法復雜度越高，效率越低。,5.1 函數的定義與性質,5.1 函數的定義與性質,5.2 函數的復合與反函數,5.2 函數的復合與反函數,5.2 函數的復合與反函數,5.2 函數的復合與反函數,第四部分

45、 圖論,第六章 圖的基本概念 第七章 一些重要的圖,第六章 圖的基本概念,6.1 圖 6.2 通路、回路 6.3 圖的連通性 6.4 圖的矩陣表示 6.5 圖的運算,用點表示事物，用點之間是否有連線表示事物之間是否 有某種關系，這樣構成的圖，就是圖論中的圖。二元關 系的關系圖就是圖，與幾何學中的圖形有本質區別。因 此，先看無序積。,定義1.設A，B為集合，稱a，b|aAbB為A與B 的無序積，記作A&B。為方便，將a，b記為（a，b）,6.1 圖,定義2.圖G=是有序二元組，其中V(G)是有限非空 集；V中元素稱為G的頂點或結點，V稱為G的頂點集。E(G) 是V(G)中諸頂點之間邊或弧的集合，

46、E稱為G的邊集。,圖G的邊可以是無方向的，用vi，vj表示，稱為無向邊， 只由無向邊構成的圖G稱為無向圖。,圖G的邊可以是有方向的，用表示，稱為有向邊， 只由有向邊構成的圖D稱為有向圖。,6.1 圖,如果圖G中既有有向邊，又有無向邊，則稱圖G為混合圖。,6.1 圖,D=,ek=E,稱vi為ek的起點， vj為ek的終點， 并稱vi鄰接到vj或vj鄰接于vi。 若ek的終點是el的起點，則ek、el相鄰。,6.1 圖,定義4.在無向圖中，關聯一對頂點的無向邊若多于1條，則稱這些邊 為平行邊，平行邊的條數為重數。 在D中，關聯一對頂點的有向邊若多于1條，且始點、終點相同，則 稱這些邊為平行邊。 含

47、平行邊的圖為多重圖，不含平行邊、環的圖為簡單圖。,6.1 圖,6.1 圖,6.1 圖,必要條件：階數相同 邊數相同 度數相同的頂點數相同,6.1 圖,6.1 圖,6.1 圖,6.2 通路與回路,定理1.在n階圖G中，若從頂點vi到vj（vivj）存在通路，則 從vi到vj存在長度小于或等于（n-1）的通路。,推論：在n階圖G中，若從頂點vi到vj（vivj）存在通路，則 從vi到vj一定存在長度小于或等于（n-1）的初級通路。,定理2.在n階圖G中，若存在從頂點vi到自身的回路，則一定 存在長度小于或等于n的回路。,推論：在n階圖G中，若存在從頂點vi到自身的簡單回路，則 一定存在長度小于或等

48、于n的初級回路。,6.2 通路與回路,無向圖頂點間的連通關系是V上的一個等價關系，他的所 有等價類構成V的一個劃分。任意兩個頂點vi,vj屬于同一個 等價類當且僅當他們有路連接。,6.3 圖的連通性,6.3 圖的連通性,6.3 圖的連通性,當v是G的點割集，則稱v是G的割點。,若v是連通圖G的一個割點，那么G-v就是不連通或平凡圖。,6.3 圖的連通性,6.3 圖的連通性,6.3 圖的連通性,6.3 圖的連通性,定理3.一個有向圖D是強連通圖的充要條件是D中存在至少 經過每個頂點一次的回路。,6.3 圖的連通性,定理4.設D是n階有向圖，D是單向連通圖當且僅當D中存在 經過每個頂點至少一次的通

49、路。,6.3 圖的連通性,極大路徑法：,設G=為n階無向圖，E。設l為G中一條路 徑。若此路徑的始點或終點與通路外的頂點相鄰，就將它 們擴充到通路中來，繼續這一過程，直到最后得到的通路 的兩個端點不與通路外的頂點相鄰為止。設最后得到的路 徑為l+k，稱其為極大路徑。稱使用此種方法證明問題 的方法為極大路徑法。,鄰接矩陣A的階就是G的頂點數n。,6.4 圖的矩陣表示,圖的表示方法： （1）用邊的集合和邊的集合表示，如G= （2）用圖形表示，頂點用小圓圈表示，邊用線段或弧表示 （3）用矩陣表示,鄰接矩陣依賴于V中個元素的給定次序，對于V中各元素 的不同給定次序，可以得到同一個圖G的不同鄰接矩陣。

50、這些矩陣可以通過交換另一個矩陣的某些行或對應的列而 得到。如果兩個圖有這樣的鄰接矩陣，則這兩個圖是同構 的。,6.4 圖的矩陣表示,若主對角線某元素不為0，則表示該對應頂點上有自環。 零矩陣對應的圖為零圖。,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.5 圖的運算,6.5 圖的運算,第七章 歐拉圖與哈密頓圖,7.1 歐拉圖 7.2 哈密頓圖 7.3二部圖 7.4平面圖 7.5樹,定義1.通過圖G的每條邊一次且僅一次行遍圖中所有頂點的 通路稱為歐拉通路。通過圖G的每條邊一次且僅一次行遍圖 中所有頂點的回路

51、稱為歐拉回路。具有歐拉回路的圖稱為 歐拉圖。具有歐拉通路而無歐拉回路的圖為半歐拉圖。,定理1.無向圖G為歐拉圖當且僅當G是連通圖，且G中所有 頂點的度數都是偶數。,定理2.如果G是歐拉圖，那么G可分成若干個邊不重的回路。,7.1 歐拉圖,定理3.具有一條連接頂點vi和vj的歐拉通路的充要條件是 Vi和vj是G中僅有的具有奇數度的頂點。,定理4.設連通圖G=有k個度為奇數的頂點，則E(G) 可劃分為k/2條簡單通路。,定理5.有向連通圖D為歐拉圖的充要條件是每個頂點的入 度等于出度 。,7.1 歐拉圖,定理6.有向連通圖D存在一條歐拉通路的充要條件是恰有 兩個奇度數頂點，其中的一個入度比出度大1

52、，另一個的 出度比入度大1，而其余頂點的入度等于出度。,7.1 歐拉圖,7.1 歐拉圖,定義1.通過圖G的每個頂點一次且僅一次的回路稱為 哈密頓回路. 哈密頓通路是通過圖G的每個頂點一次 且僅一次的通路.具有哈密頓回路的圖稱為哈密頓圖. 具有哈密頓通路而不具有哈密頓回路的圖稱為哈密頓 圖. 平凡圖是哈密頓圖。,性質:,1.連通,度大于等于2 2.哈密頓通路是度為n-1的基本通路,其回路長為n,7.2 哈密頓圖,7.2 哈密頓圖,7.2 哈密頓圖,例：在某次國際會議的預備會中，共有8人參加，他們來 自不同的國家。已知他們中任何兩個無共同語言的人中的 每一個，與其余有共同語言的人數之和大于或等于8

53、。問 能否將這8人排在圓桌旁，使任何人都能與兩邊的人交談。,定理4.若D為n（n2）階競賽圖，則D中具有哈密頓通路。,帶權圖與貨郎擔問題,貨郎擔問題：,設有n個城市，城市之間均有道路，道路的長度均大于或 等于0。一個旅行商從某個城市出發，要經過每個城市一 次且僅一次，最后回到出發的城市。問他如何走，才能使 路線最短？,7.5 樹,7.5.1 無向樹及其性質 7.5.2 生成樹 7.5.3 根樹及其應用,定義1.連通無回路的無向圖稱為無向樹，簡稱樹，用T 表示 。若無向圖F至少有兩個連通分圖都是樹，稱F為 森林。僅有一個頂點的樹稱為平凡樹。懸掛點稱為樹葉。,定理1.設G=是n階m條邊的無向圖，下

54、列各命題等價； （1）G是樹； （2）G的任意兩個頂點之間有唯一路徑；,7.5.1 無向樹及其性質,（3）G中無回路且m=n-1； （4）G是連通且m=n-1； （5）G是連通的，且G中任何邊均是割邊； （6）G中無回路，但若在G的任意兩個不同的頂點間加 一條邊，則所得的圖中恰有唯一的一個含有新邊的圈。,定理2.設T是n階非平凡的無向樹，則T中至少有兩片樹葉。,7.5.1 無向樹及其性質,定義1.設T是無向圖G的子圖并且為樹，則稱T為G的樹。 若T是G的樹且為生成子圖，則稱T是G的生成樹，T中的 邊稱為樹枝。圖G中不在T中的邊稱作相應生成樹T的弦。 并稱導出子圖GE(G)-E(T)為T的余樹，

55、記作 。,定理1.無向圖G具有生成樹當且僅當G是連通圖。,推論1： 設G為n階m條邊的無向連通圖，則mn-1。,7.5.2 生成樹,7.5.2 生成樹,7.5.2 生成樹,定義4.設G=是無向連通帶權圖，T是G的 一棵生成樹。T中各條邊帶權之和稱為T的權，記作 W(T)。若生成樹T0在所有生成樹中有最小的權，則稱 T0是G的最小生成樹。,7.5.2 生成樹,7.5.2 生成樹,7.5.3 根樹及其應用,在根樹中，由于有向邊的方向一致，故在畫的時候可以省去邊的方向。,設T為根樹，若將T中層數相同的頂點都標定次序，可以將 根樹分成以下各類：, 若T的每個分支點至多有r個兒子，則稱T為r叉樹； 又若

56、r叉樹是有序的，則稱其為r叉有序樹。, 若T的每個分支點恰好有r個兒子，則稱T為r叉正則樹； 又若T是有序的，則稱其為r叉正則有序樹。, 若T為r叉正則樹，且每個樹葉的層數均為樹高，則稱T為r叉 完全正則樹；又若T是有序的，則稱其為r叉完全正則有序樹。,7.5.3 根樹及其應用,2叉正則有序樹的每個分支點的兩個兒子導出的根子樹分別 稱為左子樹和右子樹。,在所有的r叉樹中，2叉樹最重要。,7.5.3 根樹及其應用,在通信中，常用二進制編碼表示符號。如：A，B，C，D就可 用00，01，10，11分別來表示，這叫做等長碼表示方法。適用 于出現的頻率基本相同的情況，當出現的頻率相差較大時，就需 要非

57、等長的編碼。,7.5.3 根樹及其應用,可用2叉樹產生二元前綴碼。,設T是具有t片樹葉的2叉樹，則T的每個分支點有12個兒子。設 V為T的分支點，若v有兩個兒子，在由v引出的兩條邊上，左邊標 上0，右邊標上1。若v只有一個兒子，由它引出的邊上可以標0也 可以標1。,7.5.3 根樹及其應用,設v是T的任意一片樹葉，從樹根到v的通路上各邊的標號（0或1） 按通路上邊的順序放在v處，則t片樹葉處t個符號串組成的集合為 一個二元前綴碼。,定理1.由一棵給定的2叉正則樹，可以產生惟一的一個二元前綴碼。,由產生的任一個前綴碼都可以傳輸符號。但這些符號出現頻率不同 時，就要用各符號出現的頻率為權，利用Huffman算法求最優2叉樹， 由最優2叉樹產生的前綴碼稱為最佳前綴碼。用最佳前綴碼傳輸對應 的各符號能使傳輸的二進制數位最省，即效率最高。,7.5.3 根樹及其應用,7.4 平面圖及圖的著色,7.4.1 平面圖的基本概念 7.4.2 歐拉公式 7.4.3 平面圖的判斷 7.4.4 平面圖的對偶圖 7.4.5 圖中頂點的著色 7.4.6 地圖的著色與平面圖的點著色 7.4.7 邊著色,定義1.若圖G能以這樣一來的方式畫在曲面上，即除 頂點處外無任何邊交叉，則稱圖G可嵌入曲面S。若G 可嵌入平面，則稱G是可平面圖或平面圖。 畫