1、第12章離散結構學習目標 了解離散結構的研究對象及主要內容、代數結構、離散概率。 掌握數理邏輯與簡單推理、集合論基礎知識、圖論基本知識。2計算機科學導論12.1離散結構的研究對象及主要內容 離散結構(Discrete Structure)是現代數學的一個重要學科，它所涉及的概念、方法和理論，被大量應用于計算機科學與技術的研究。 本章將系統傳統離散數學包含的數理邏輯、集合論、代數結構、圖論等4部分的基本內容，使讀者初步了解離散結構的基本知識。3計算機科學導論12.1.1離散結構的研究對象 離散結構的研究對象是離散量的結構和相互關系，以及離散系統結構的數學模型以及建模方法。4計算機科學導論12.1

2、.2離散結構研究的主要內容 離散結構研究的內容主要有傳統離散數學包含的數理邏輯、集合論、代數結構 和圖論等4個部分，另外還包括計算機 應用對象的離散結構的研究，離散概率、運籌學、數值計算、數學建模與模擬等。5計算機科學導論12.212.2.1數理邏輯命題邏輯u命題在數理邏輯中，稱能夠分辨真假、但不能同時既的陳述句為命題 。u原子命題在命題中，有些命題是簡單的陳述句，并且它們不能夠被分成更為簡單的陳述語句，這樣題稱為簡單命題，或者原子命題。6計算機科學導論12.2.1命題邏輯u 復合命題一個簡單命題再加上了一個表示合命題。的連接詞形成的復簡單命題與復合命題都可以用簡單的英文字母來表示。例 用Q表

3、示命題：8是奇數！用P表示命題：不是學生。復合命題的連接詞連接詞，記作“” 合取連接詞，也稱“與”，記作“” 或取連接詞，也稱“或”，記作“” 蘊涵連接詞，也稱“條件”，記作“” 等價連接詞，也稱“雙條件”，記作“ ”7計算機科學導論12.2.1命題邏輯u 2命題公式由命題常元、命題變元與各種邏輯連接詞組合形成的更為復雜題，稱為命題公式，又稱為合式公式。u 3等值演算 (1)重言式如果對命題公式A中命題變元的一切指派，A的真值均為真，則稱命題公式A為重言式，重言式又稱 (2)等價式設A,B為兩個命題公式，若等價式A B是重言式，則稱A邏輯等價于B，或A與B是等值的，記作AB。A B式。不是命題

4、公式。8計算機科學導論12.2.1u 4命題推理推理是從前提出發推出結論的思維過程，命題邏輯前提是已知題公式，結論是從前提出發應用推理規則推出題公式。推理常用的方法: 真值表法 等價證明法 構造證明法9計算機科學導論12.2.1命題邏輯例 證明PQ和 Q的結論是P。證明：只需證明(PQ) 真值表法QP是重言式。按真值表的構造步驟，構造真值表如下：PQPQQP00010101100110111111100110計算機科學導論12.2.1命題邏輯例 證明PQ和 Q的結論是P。證明：只需證明(PQ)QP是重言式。 等價證明法QP (P Q) Q Q)P(PQ)(P Q)PPQ PTQT11計算機科學

5、導論12.2.1例證明：pr, qs, pq證明：命題邏輯 rs 。構造證明法1) pr前提1) 等價置換2) 等價置換3) 等價置換前提5) 等價置換6) 等價置換4)7)假言 前提8)9)假言10) 等價置換2) pr3) r p4) r p5) pq6) p q 7) p q 8) r q9) qs10) r s11) rs12計算機科學導論12.2.2 謂詞邏輯u 對簡單命題做進一步的分解，分析命題內部的邏輯結構和命題間的內在，它是命題邏輯的擴充和發展。 1.詞原子命題中所描述的對象，是可以，可以是具體的，也可以是抽象的。 2.謂詞存在的客體詞的性質或詞之間關系的詞。 3.量詞表示常變

6、元之間數量關系的詞稱為量詞。13計算機科學導論12.2.2 謂詞邏輯例 將以下命題用謂詞邏輯符號化。(1)(2)(3)所有的自然數都是大于零的。沒有不犯錯誤的人。這個班有些學生請假了。解：(1) 設A(x)：x是自然數；B(x)：x大于零。則原命題符號化為：x(A(x) B(x)。(2) 設A(x)：x是人；B(x)：x犯錯誤。則原命題符號化為：x(A(x) B(x)。(3) 設A(x)：x是這個班的學生；B(x)：x請假了。則原命題符號化為：x(A(x)B(x)。14計算機科學導論12.2.2 謂詞邏輯u 4謂詞推理 (1) 全稱量詞消去規則。如果謂詞公式xA(x)為真， 則可推出A(c)

7、為真，即xA(x) A(c) 式中，c是域中任意一個確定的。 (2) 存在量詞消去規則。如果謂詞公式xA(x)為真， 則可推出A(c) 為真，即xA(x) A(c) 式中，c是域中滿足條件A的常元。15計算機科學導論12.2.2 謂詞邏輯(3) 全稱量詞引入規則。如果謂詞公式A(x)中的變元x無論取論域中的任何值，A(x)自由都為真，則可推出xA(x)為真，即A(x) xA(x) 式中，x是域中任意一個。(4) 存在量詞引入規則。如果謂詞公式A(c)為真，則可推出xA(x) 為真，即A(c)xA(x) 式中，c是域中滿足條件A的常元。16計算機科學導論12.3集合論12.3.1集合的基本概念與

8、運算對簡單命題做進一步的分解，分析命題內部的邏輯結構和命題間的內在，它是命題邏輯的擴充和發展。u1.集合的概念與表示事物匯集在一起組成的一個整體叫做集合，而這些事物就可以稱為這個集合的元素或者成員。集合通常用大寫的英文字母來標記。表示一個集合的方法：A1,2,3,n,：Bx|x是大于等于8的正整數列舉法描述法17計算機科學導論12.3.1u 2.集合間關系 設A ，B是集合，如果B中的每個元素都是A中的元素，則稱B是A的子集合，簡稱子集。這時也稱B被A包含，或A包含B。 設A，B為集合，如果A B且B A，則稱A與B相等，記作AB 。 設A，B為集合，如果BA且BA，則稱B是A的真子集。記作B

9、 A。 不含任何元素的集合叫做空集，記作。集合的基本概念與運算 給定集合A，由集合A的集為元素組成的集合，稱為集合A的冪集，記作P(A) 。 在一個具體問題中，如果所涉及的集合都是某個集合 的子集，則稱這個集合為全集，記作E(或U)。18計算機科學導論12.3.1u 3.集合運算 (1) 定義：設A與B為集合，A與B的并運算、交運算、差運算 - ，分別定義為，AB=x|(x A) (x B)AB=x|(x A) (x B)A - B =x|(x A) (x B) (2) 定義：設E為全集，A E，則A的補運算，記作，定義為，AE -AxxExA 或 AxxA (3) 定義：設A與B為集合，A與

10、B的對稱差，記作，定義為集合的基本概念與運算AB(AB)(AB )19計算機科學導論12.3.2u 1.笛卡兒積 (1) 序偶由兩個元素x和y(關系與函數x =y)按一定的順序排列成的二元組叫做一個有序對(也稱序偶)，記作，其中x是它的第一元素，y是它的第二元素。u 有序對的特點： 當x y時，。 兩個有序對相等，即 的充分必要條件是xu且yv。20計算機科學導論12.3.2關系與函數 (2)笛卡兒積設A，B為集合，用A中元素作為第一元素，B中元素作為第二元素，有序對，所有這樣的有序對組成的集合叫做A和B的笛卡兒積，記作AB。符號化表示為AB(x,y)|xAyB例 有兩個集合Aa,b，B0,1

11、,2，則AB,BA,21計算機科學導論12.3.2關系與函數u 2.二元關系(1) 二元關系定義如果一個集合為空集或者它的元素都是有序對，則稱這個集合是一個二元關系，一般記作R對于二元關系R，如果有序對R，則記作x R y設A,B為集合，AB的任何子集所定義的二元關系稱作從A到B的二元關系，特別當AB時，則叫做A上的二元關系22計算機科學導論12.3.2 關系與函數u 3種特殊的關系： 其中之一就是空集，稱做空關系。 另外兩種就是全域關系EA和恒等關系IA。 對任何集合A，EAxAyAAA IAxA23計算機科學導論12.3.2u (2) 關系的表示 通常用關系圖來表示一個關系。關系與函數例A

12、=1,2,3,4，R=,，可以畫出如下的關系圖。24計算機科學導論12.3.2關系與函數u (3) 關系的基本運算Dom(R)x $y(R)Ran(R)y | $x(R) F的逆記作：|F。 F與G的左復合記作GF ，GF $z(GF) F與G的右復合記作F G，FG $z(FG)25計算機科學導論u(4) 關系的性質自反性若對于任意x屬于集合A，都有x A R ，那么，就說R在A 上是自反的。反自反性若對于任意x屬于集合A，都不存在x A R ，那么，就說R在A上是反自反的。對稱性若對于任意x,y屬于集合A，都有x, y A R R，那么，就稱R為A上的對稱關系。稱性若對于任意x,y屬于集合

13、A，都不存在 R R，那么，就稱R為A上的稱關系。例如A上的全域關系，恒等關系，空關系都是A上的對稱關系。而恒等關系和空關系也是A上傳遞性稱關系。若對任意的x,y,z都屬于集合A，假如都存在 x, y, z A R R R，那么，就稱R為A上的傳遞關系。26計算機科學導論12.3.2關系與函數u (5) 兩類重要的二元關系 等價關系設R為非空集合A上的二元關系，若R具有自反性、對稱性和傳遞性，則稱R為A上的等價關系。利用等價以對一些對象進行分類。例如，集合上的恒等關系即是等價關系。 偏序關系設R為非空集合A上的二元關系，若R具有自反性、 稱性和傳遞性，則稱R為A上的偏序關系，偏序關系可以記為。

14、集合A和A上的偏序關系R一起叫做偏序集，記為(A,)，如果有(a,b)R，可以表示為ab 。根據偏序以畫出關系圖，通常稱為。27計算機科學導論12.3.2關系與函數例 已知為偏序集，集合A=a,b, c,d,e,f，關系=(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，畫出關系的。解：按照偏序集的規則，可以得到如下28計算機科學導論12.3.2關系與函數u 4.函數函數(Functions)也稱(Mapping)。函數也是一種二元關系，與普通的二元關系相比，函數可以看作是一種特殊的二元關系。 (1) 函數的定義設F為二元關系，若對于任意的x，都存在惟一的讓

15、xFy成立，則稱F為函數。對于任意函數F， 如果都有xFy，則記做，并稱y為F在x上的值。29計算機科學導論12.3.2u (2) 特殊函數 函數的性質 設函數f :AB若對于任何的x1,x2A，x1x2，都有f(x1)f(x2)，則關系與函數稱f是的。 若Ran(f)B，則稱f是。的，則稱f是 若f既是的，又是的。30計算機科學導論12.3.2關系與函數 復合函數設f是從集合A到集合B的函數，g是從集合B到集合C的函數，f和g的復合用f g表示為f g =(a,c)|aAcC$b(bB)(a,b)f(b,c)g 反函數設函數f是集合X到集合Y的一個函數。則f的反函數是集合Y到集合X的函數，對

16、于yY，都分派一個惟一的xX和它對應，使得f(x)=y 。f的反函數記作：f 1: YX，即f 1(y)=x。31計算機科學導論12.4代數結構12.4.1代數結構概述u 1.運算的定義及性質 （以二元運算為例）設S為集合，函數 f：S SS 稱為S上的二元運算，簡稱為二元運算。 二元運算的一些性質： (1) 設 為S上的二元運算，如果對于任意的x,yS都有x y =y x，則稱運算 在S上滿換律。 (2) 設 為S上的二元運算，如果對于任意的x,y,zS都有 (x y)z =x (y z)，則稱運算 在S上滿足結合律。32計算機科學導論12.4.1代數結構概述 (3) 設 S上的二元運算，如

17、果對于任意的xS有x x=x則稱運算 在S上滿足冪等律。 (4) 設 和*為S上兩個二元運算，如果對于任意的x,y,zS，有x*(y z) (x*y) (x*z)(左分配律)(右分配律)(y z)*x (y*x) (z*x)則稱運算*對運算滿足分配律。 (5) 設 和*為S上兩個可交換的二元運算，如果對于任意的x,yS，都有x *(x y)xx (x *y)x 則稱運算和*滿足吸收律。33計算機科學導論u 2運算中的特殊元素集合中有些元素在運算過程中具有特殊的性質，它們 是集合運算中的特殊元素。 (1)元。設*為S上的二元運算，如果元素eS且對任意元素xS，有x*e=e*x=x則稱e為S上關于

18、*運算的元，且唯一。 (2)零元。設*為S上的二元運算，如果元素OS且對任 意元素xS，有x*O=O*x=O則稱O為S上關于*運算的零元，且唯一。 (3)逆元。設*為S上的二元運算，eS為運算*的 對于元素xS，且對任意元素yS，有元。x*y=y*x=e則稱y為x的逆元。34計算機科學導論12.4.1代數結構概述u 3.代數結構的定義代數結構通常指由以下三個部分組成的數學結構：一個非空集合S，稱為代數結構的載體。S上的若干運算。一組刻畫載體S上各運算所滿足性質的公理。通常，代數結構用一個多元序組來表示，其中，S是載體， ，*，為各種運算。有時，S中地位比較特殊的元素(如也會被列入這個多元組的末

19、尾。元、零元、逆元)例如，以自然數集N為載體，“+”運算可以作為二元運算組成一個代數結構，記為。35計算機科學導論12.4.2格與布爾代數u 1.格 (1)格的定義：有序集稱為格(lattice)，如果A的任何兩個元素的子集都有上確界和下確界。通常，用ab表示a,b的上確界，用ab表示a,b的下確界。(b)(a) 格36計算機科學導論12.4.2格與布爾代數 (2)分配格稱格為分配格，如果它滿足分配律，即對任意a,b,cA,a(bc)=(ab) (ac)a(bc)=(ab) (ac)37計算機科學導論12.4.2格與布爾代數 (3)有界格格稱為有界格，如果A中既有上確界1，又有下確界0。則，0

20、和1稱為A的界。對于A中的一個元素a，如果有 ab =1，ab=0則稱b為a 的補補。記為a。如果A中的每個元素都有補元，則有界格稱為有補格。38計算機科學導論12.4.2格與布爾代數u 2.布爾代數的定義定義：代數系統稱為布爾代數，如果 B滿足以下條件： 運算，滿換律。 運算對運算滿足分配律，運算對運算也滿足分配律。 B有運算元1和運算零元0、運算元0和運算零元1。 對B中的每一個元素a，均存在元素a，使aa=1， aa=039計算機科學導論12.5圖論12.5.1圖的基本概念u 1圖的由來 哥七橋問題40計算機科學導論12.5.1圖的基本概念u 2.圖的基本概念(1) 圖的定義圖(grap

21、h)G由三個部分所組成： 非空集合V(G)，稱為圖G的節點集，其成員稱為節點或頂點(nodes or vertices)。 集合 E(G)，稱為圖G的，其成員稱為邊(edges)。 函數(G):E(G)(V(G)，V(G)，稱為邊與頂點的關聯(associatve mapping)。41計算機科學導論12.5.1圖的基本概念u (2) 關于圖的概念設圖G為 當V和E為有限集時，稱G為有限圖，否則稱G為無限圖。在此只討論有限圖。 當G為，稱G為；當G為非，稱G為重圖，又稱滿足(e1) = (e2)的不同邊e1、e2為重邊，或平行邊。 當(e)(v,v)(或)時，稱e為環(loops)。無環。當G

22、為有限簡和重邊的無向稱為簡時，也常用(n,m)表示圖G，其中n = V，m = E 。42計算機科學導論12.5.1圖的基本概念 在G中，(e)(u,v)(或)時，也用(u,v)(或)表示邊e，這時稱u,v鄰接e, u,v是e的端點(或稱u為e的起點，v為e的終點)；也稱e關聯結點u,v 。不是任何邊的端點的節點稱為孤立結點，僅由孤立結點構 成的圖(E = )稱為零圖。43計算機科學導論12.5.1圖的基本概念u (3) 結點的度 定義：在無，結點v的度(degree)d(v)是v作為邊的端點的數目。在有，結點v的出度d +(v)(out-degree)是以v作為有向邊起點的數目，v的入度d

23、-(v)(in-degree)是v 作為有向邊終點的數目。結點的度是v的出度與入度之和。44計算機科學導論12.5.2路徑、回路及連通性 定義：圖G的頂點v1到頂點vl的擬路徑(pseudo path)是指如下頂點與邊的序列：v1 ,e1 ,v2 ,e2 ,v3 , ,v l -1 ,el-1 , v l 其中v1 ,v2 ,v3 , ,v l -1 ,v l為G的頂點，e1 ,e2 , ,e l -1為G的邊，且e i( i= 1,2, ,l-1 )以v i及v i +1為端點，(對有G，ei以vi為起點，以v i +1為終點)；擬路徑的邊數l1稱為該擬路徑的長度。當e i( i= 1,2,

24、 , l-1 )各不相同時，該擬路徑稱為路徑(walk)，又當v i(i = 1,2, ,l)各不相同時(除v1與v1)，則稱此路徑為通路(Path)。v1v1 的路徑稱為閉路徑(closed walk)；v1= v1的通路稱為回路(circuit)。45計算機科學導論12.5.2 定義：稱無路徑、回路及連通性G是連通的(Connected)，如果G的任何兩個頂點都是相互可達的。 定義：稱有G是強連通的，如果G的任何兩個G是單向連通的，頂點都是相互可達的；稱有如果G的任何兩個頂點中，至少從一個頂點到另一G是弱連通的，如果G是連通的。個頂點是可達的；稱有的有向邊被看作無(a) 強連通圖(b) 單

25、向連通圖(c)弱連通圖46計算機科學導論12.5.3圖的矩陣表示 (1)關聯矩陣47計算機科學導論12.5.3圖的矩陣表示 (2) 鄰接矩陣48計算機科學導論12.6離散概率概率(Probability)在推理過程中具有非常重要的作用，它通常用來衡量發生的可能性的大小，或者說用來衡量人們期待的占總體的比例u 離散概率(Discrete Probability)的一些基本知識： 定義：概率試驗通常指人們對隨機現象的結果進行的過程，通常記為E。觀察、 定義：樣本空間指的是概率試驗的所有結果的集合，通常記為S。樣本空間中的每個元素分別稱為樣本點。如果樣本空間含有有限個或可數的離散的樣本點， 該樣本空間就是離散樣本空間。 同一個概率試驗可以有不同的樣本空間。49計算機科學導論12.6離散概率 定義：離散樣本空間S的任意子集，稱為S