計(jì)算機(jī)科學(xué)導(dǎo)論 學(xué)習(xí)計(jì)算機(jī)專業(yè)的第一門基礎(chǔ)課程 第 11章 離散結(jié)構(gòu) 本章要點(diǎn)： 離散結(jié)構(gòu)的研究對象及主要內(nèi)容 數(shù)理邏輯與簡單推理 集合論基礎(chǔ)知識 代數(shù)結(jié)構(gòu) 圖論基本知識 離散概率 數(shù)值分析特點(diǎn)與方法 運(yùn)籌學(xué)概念與步驟 數(shù)學(xué)建模與計(jì)算機(jī)模擬的概念與步驟 離散數(shù)量關(guān)系以及離散系統(tǒng)結(jié)構(gòu)的數(shù)學(xué)模型以及建模方法 。 傳統(tǒng)離散數(shù)學(xué)包含的數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)和圖論等四個(gè)部分，以及計(jì)算機(jī)應(yīng)用對象的離散結(jié)構(gòu)的研究，離散概率、運(yùn)籌學(xué)、數(shù)值計(jì)算、數(shù)學(xué)建模與模擬等。 理邏輯 離散數(shù)量關(guān)系以及離散系統(tǒng)結(jié)構(gòu)的數(shù)學(xué)模型以及建模方法 。 命題 在數(shù)理邏輯中，稱能夠分辨真假、但不能同時(shí)既真又假的陳述句為命題 。 (1) 原子命題 在命題中，有些命題是簡單的陳述句，并且它們不能夠被分成更為簡單的陳述語句，這樣的命題稱為簡單命題，或者原子命題。 理邏輯 (2) 復(fù)合命題 一個(gè)簡單命題再加上了一個(gè)表示否定的連接詞形成的復(fù)合命題。 簡單命題與復(fù)合命題都可以用簡單的英文字母來表示。 例 用 8是奇數(shù)！ 用 平不是學(xué)生。 構(gòu)成復(fù)合命題的連接詞 否定連接詞，記作“ ” 合取連接詞，也稱“與”，記作“ ” 或取連接詞，也稱“或”，記作“ ” 蘊(yùn)涵連接詞，也稱“條件”，記作“ ” 等價(jià)連接詞，也稱“雙條件”，記作“ ” 理邏輯 命題公式 命題常元、命題變元與各種邏輯連接詞組合形成的更為復(fù)雜的命題，就可以稱為命題公式，又叫做合式公式。 (1) 命題常元 單個(gè)的已知命題 (可以是具體的命題、常真命題、常假命題 ) 。 (2) 命題變元 不代表具體命題的、但是取值范圍仍然為“真”與“假”或“ 1”與“ 0”的符號表示的命題 。 理邏輯 等值演算 命題常元、命題變元與各種邏輯連接詞組合形成的更為復(fù)雜的命題，就可以稱為命題公式，又叫做合式公式。 (1) 重言式 如果對命題公式 稱命題公式 言式又稱永真式。 (2) 等價(jià)式 設(shè) A,等價(jià)式 A 稱 ，或 是等值的，記作 A B。 A 理邏輯 命題推理 推理是從前提出發(fā)推出結(jié)論的思維過程，前提是已知的命題公式，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。 (1) 真值表法 (2) 等價(jià)證明法 (3) 構(gòu)造證明法 理邏輯 例 證明 P 。 證明 ：只需證明 (P Q) QP 是重言式。 真值表法 按真值表的構(gòu)造步驟，構(gòu)造真值表如下： (P Q) (P Q) P Q P Q Q Q Q P 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 理邏輯 例 證明 P 。 證明 ：只需證明 (P Q) QP 是重言式。 等價(jià)證明法 (P Q) Q P (P Q) Q Q) P (P Q) P P Q P T Q T 理邏輯 例 證明： p r, q s, p q r s 。 證明 ： 構(gòu)造證明法 1) pr 前提 2) p r 1) 等價(jià)置換 3) r p 2) 等價(jià)置換 4) r p 3) 等價(jià)置換 5) p q 前提 6) p q 5) 等價(jià)置換 7) p q 6) 等價(jià)置換 8) r q 4)7)假言三段論 9) qs 前提 10) r s 8)9)假言三段論 11) r s 10) 等價(jià)置換 理邏輯 是對簡單命題做進(jìn)一步的分解，分析命題內(nèi)部的邏輯結(jié)構(gòu)和命題間的內(nèi)在聯(lián)系，它是命題邏輯的擴(kuò)充和發(fā)展。 個(gè)體詞 原子命題中所描述的對象，是可以獨(dú)立存在的客體，可以是具體的，也可以是抽象的。 謂詞 用來描述個(gè)體詞的性質(zhì)或個(gè)體詞之間關(guān)系的詞。 量詞 表示個(gè)體常元或變元之間數(shù)量關(guān)系的詞稱為量詞。 理邏輯 (1) 全稱量詞 全稱量詞表示“所有的”，“每一個(gè)”，“對任何一個(gè)”，“一切”，“任意的”。符號為“ ”。 (2) 存在量詞 表示“存在著”，“有一個(gè)”，“至少有一個(gè)”，“存在一些”，“對于一些”，“某個(gè)”等。符號為“ ”。 理邏輯 例 將以下命題用謂詞邏輯符號化。 (1) 所有的自然數(shù)都是大于零的。 (2) 沒有不犯錯(cuò)誤的人。 (3) 這個(gè)班有些學(xué)生請假了。 解： (1) 設(shè) A(x)： B(x)： 則原命題符號化為： x(A(x) B(x)。 (2) 設(shè) A(x)： B(x)： 則原命題符號化為： x(A(x) B(x)。 (3) 設(shè) A(x)： B(x)： 則原命題符號化為： x(A(x) B(x)。 理邏輯 謂詞推理 謂詞邏輯推理是命題邏輯推理的推廣。謂詞邏輯的推理也是利用命題公式間的各種等價(jià)關(guān)系、蘊(yùn)涵關(guān)系，通過一些推理規(guī)則，從已知命題公式推出一些新的公式。 合論 是對簡單命題做進(jìn)一步的分解，分析命題內(nèi)部的邏輯結(jié)構(gòu)和命題間的內(nèi)在聯(lián)系，它是命題邏輯的擴(kuò)充和發(fā)展。 集合的概念與表示 事物匯集在一起組成的一個(gè)整體叫做集合，而這些事物就可以稱為這個(gè)集合的元素或者成員。 集合通常用大寫的英文字母來標(biāo)記。 表示一個(gè)集合的方法 (1) 列舉法 ： A 1,2,3,n, (2) 描述法 ： B x|的正整數(shù) 合論 集合間關(guān)系 (1) 設(shè) A ， 果 中的元素，則稱 的子集合，簡稱子集。這時(shí)也稱 包含，或 。 (2) 設(shè) A， 果 A A，則稱 相等 ，記作 A B 。 (3) 設(shè) A， 果 BA，則稱 的 真子集 。記作 B A。 (4) 不含任何元素的集合叫做 空集 ，記作 。 (5) 給定集合 A，由集合 為集合 集 ，記作P(A) 。 (6) 在一個(gè)具體問題中，如果所涉及的集合都是某個(gè)集合的子集，則稱這個(gè)集合為全集 ，記作 E(或 U)。 合論 集合運(yùn)算 (1) 定義： 設(shè) 為集合， 的并運(yùn)算 、交運(yùn)算 、差運(yùn)算 - ，分別定義為， A B=x|(x A) (x B) AB=x|(x A) (x B) A - B =x|(x A) (x B) (2) 定義： 設(shè) A E，則 作 ，定義為， A E xx E xA 或 A xxA (3) 定義： 設(shè) 為集合， 的對稱差，記作 ，定義為， AB (A B)(AB 合論 笛卡兒積 (1) 序偶 由兩個(gè)元素 x和 y(允許 x =y)按一定的順序排列成的二元組叫做一個(gè)有序?qū)?(也稱序偶 )，記作 ，其中 有序?qū)Φ奶攸c(diǎn)： 當(dāng) x 。 兩個(gè)有序?qū)ο嗟?，?的充分必要條件是 x u且 y v。 合論 (2)笛卡兒積 設(shè) A， 成有序?qū)?，所有這樣的有序?qū)M成的集合叫做 的笛卡兒積，記作A B。符號化表示為 A B (x,y)|x A y B 例 有兩個(gè)集合 A a,b， B 0,1,2，則 A B , B A , 合論 二元關(guān)系 (1) 二元關(guān)系定義 如果一個(gè)集合為空集或者它的元素都是有序?qū)?，則稱這個(gè)集合是一個(gè)二元關(guān)系，一般記作 R。 對于二元關(guān)系 R，如果有序?qū)?R，則記作 x R y 。 設(shè) A,A 到 別當(dāng) A 叫做 3種特殊的關(guān)系： 其中之一就是空集 ，稱做空關(guān)系。 另外兩種就是全域關(guān)系 A。 對任何集合 A， x A y A A A x A 合論 (2) 關(guān)系的表示 通常用關(guān)系圖來表示一個(gè)關(guān)系。 例 A=1,2,3,4， R=,，可以畫出如下的關(guān)系圖。 合論 (3) 關(guān)系的基本運(yùn)算 ) x y( R) ) y | x( R) | F。 的左復(fù)合記作 F G， F G z( G F) 的右復(fù)合記作 F G， F G z( F G) 合論 (4) 關(guān)系的性質(zhì) 自反性 若對于任意 ，都有 ，那么，就說 上是自反的。 反自反性 若對于任意 ，都不存在 ，那么，就說 上是反自反的。 對稱性 若對于任意 x,，都有 R ，那么，就稱 上的對稱關(guān)系。 反對稱性 若對于任意 x,，都不存在 R ，那么，就稱 上的反對稱關(guān)系。 例如 等關(guān)系，空關(guān)系都是 恒等關(guān)系和空關(guān)系也是 傳遞性 若對任意的 x,y,，假如都存在 ，那么，就稱 上的傳遞關(guān)系。 ,x A x x R ,x A x x R ,x y A ,y x R ,y x R ,x y z A ,x y R ,y z R ,x z R 合論 (5) 兩類重要的二元關(guān)系 等價(jià)關(guān)系 設(shè) 上的二元關(guān)系，若 稱性和傳遞性，則稱 上的等價(jià)關(guān)系。 利用等價(jià)關(guān)系，可以對一些對象進(jìn)行分類。例如，集合上的恒等關(guān)系即是等價(jià)關(guān)系。 偏序關(guān)系 設(shè) 上的二元關(guān)系，若 對稱性和傳遞性，則稱 上的偏序關(guān)系，偏序關(guān)系可以記為 。集合 上的偏序關(guān)系 為 (A,)，如果有 (a,b) R，可以表示為 ab 。 根據(jù)偏序關(guān)系可以畫出關(guān)系圖，通常稱為哈斯圖。 合論 例 已知 為偏序集，集合 A=a,b, c,d,e,f，關(guān)系 =(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，畫出 關(guān)系的哈斯圖。 解：按照偏序集哈斯圖的規(guī)則，可以得到如下哈斯圖。 合論 函數(shù) (1) 函數(shù)的定義 設(shè) 對于任意的 x，都存在惟一的讓 稱 于任意函數(shù) F，如果都有 記做，并稱 在 (2) 函數(shù)的性質(zhì) 設(shè)函數(shù) f :AB 若對于任何的 x1,A， x1有 f(f(則 稱 若 f) B，則稱 若 是單射的，則稱 合論 (3) 特殊函數(shù) 復(fù)合函數(shù) 設(shè) 到集合 到集合 f和 f g 表示為 f g =(a,c)|a A c C b(b B) (a,b) f (b,c) g 反函數(shù) 設(shè)函數(shù) 到集合 到集合 于 y Y，都分派一個(gè)惟一的 x 得 f(x)=y 。f 1: YX ，即 f 1(y)=x。 數(shù)結(jié)構(gòu) 運(yùn)算的定義及性質(zhì) （以二元運(yùn)算為例） 設(shè) 數(shù) f： S SS 稱為 稱為二元運(yùn)算。 二元運(yùn)算的一些性質(zhì)。 (1) 設(shè) 為 果對于任意的 x,y x y =y x，則稱運(yùn)算 在 換律 。 (2) 設(shè) 為 果對于任意的 x,y,z (x y)z =x (y z)，則稱運(yùn)算 在 合律 。 (3) 設(shè) 果對于任意的 x S有 x x =x，則稱運(yùn)算 在 等律 。 (4) 設(shè) 和 為 果對于任意的 x,y,z S，有 x(y z) (xy) (xz) (左分配律 ) (y z)x (yx) (zx) (右分配律 ) 則稱 運(yùn)算 對運(yùn)算 滿足分配律 。 (5) 設(shè) 和 為 果對于任意的 x,y S，都有 x (x y) x x (x y) x 則稱 運(yùn)算 和 滿足吸收律 。 數(shù)結(jié)構(gòu) 代數(shù)結(jié)構(gòu)的定義 代數(shù)結(jié)構(gòu)通常指由以下三個(gè)部分組成的數(shù)學(xué)結(jié)構(gòu)： 一個(gè)非空集合 S，稱為代數(shù)結(jié)構(gòu)的載體。 一組刻畫載體 通常，代數(shù)結(jié)構(gòu)用一個(gè)多元序組 來表示，其中， ，*， 為各種運(yùn)算。有時(shí)， 如幺元、零元、逆元 )也會被列入這個(gè)多元組的末尾。 例如，以自然數(shù)集 +”運(yùn)算可以作為二元運(yùn)算組成一個(gè)代數(shù)結(jié)構(gòu)，記為 。 數(shù)結(jié)構(gòu) 格 有序集 稱為格 (如果 常，用 a a,b的上確界，用 a a,b的下確界。 分配格 稱格 為分配格，如果它滿足分配律，即對任意的 a,b,c A, a (b c)=(a b) (a c) a (b c)=(a b) (a c) 有界格 格 稱為有界格，如果 ，又有下確界 0。則， 0和 1稱為 有補(bǔ)格 對于 a，如果有 a b =1， a b=0 則 稱 b為 a 的補(bǔ)元或補(bǔ)。記為 a。 如果 有界格 稱為有補(bǔ)格。 數(shù)結(jié)構(gòu) 布爾代數(shù) 代數(shù)系統(tǒng) 稱為布爾代數(shù)，如果 運(yùn)算 ， 滿足交換律。 運(yùn)算對 運(yùn)算滿足分配律， 運(yùn)算對 運(yùn)算也滿足分配律。 運(yùn)算幺元 1和 運(yùn)算零元 0、 運(yùn)算幺元 0和 運(yùn)算零元 1。 對 a，均存在元素 a，使 a a=1， a a=0 論 圖的由來 哥尼斯堡七橋問題 論 圖的基本概念 (1) 圖的定義 定義： 圖 (由三個(gè)部分所組成： 非空集合 V(G)，稱為圖 成員稱為節(jié)點(diǎn)或頂點(diǎn) (or 集合 E(G)，稱為圖 成員稱為邊 ( I 函數(shù) (G):E(G)(V(G) ， V(G)，稱為邊與頂點(diǎn)的關(guān)聯(lián)映射 ( 論 圖的基本概念 當(dāng) (u,v)用作有序偶對時(shí)， (V(G),V(G) =V(G) V(G)， e以 圖 當(dāng) (u,v)用作無序偶對時(shí)， (u,v) = (v,u)，稱 或邊 )，圖 或圖 )。 論 圖的基本概念 (2) 節(jié)點(diǎn)的度 在無向圖中，節(jié)點(diǎn) d(v)是 有向圖中，節(jié)點(diǎn) 度 d +(v)(以 d -(v)( 點(diǎn)的度是 論 路及連通性 圖 指如下頂點(diǎn)與邊的序列： ,v l v l 其中 ,v l v 的頂點(diǎn)， ,e l e i( i= 1,2, ,l 以 v i及 v i +1為端點(diǎn)， (對有向圖 G， v i +1為終點(diǎn) )；擬路徑的邊數(shù) l 1稱為該擬路徑的長度。當(dāng) e i( i= 1,2, , l 各不相同時(shí)，該擬路徑稱為路徑 (又當(dāng) v i(i = 1,2, ,l) 各不相同時(shí) (除 則稱此路徑為通路 ( 論 關(guān)聯(lián)矩陣 論 鄰接矩陣 散概率 樣本空間 樣本空間指的是概率試驗(yàn)的所有結(jié)果的集合，通常記為 S。樣本空間中的每個(gè)元素分別稱為樣本點(diǎn)。如果樣本空間含有有限個(gè)或可數(shù)的離散的樣本點(diǎn)，該樣本空間就是離散樣本空間 。 事件 離散樣本空間 為是 離散概率 設(shè) 的離散樣本空間，且試驗(yàn)的每個(gè)結(jié)果的可能性相同，如果 相關(guān)的一個(gè)事件，則 為： ，其中，|A| 表示事件 |S|表示離散樣本空間 |()|A 值分析 數(shù)值分析的特點(diǎn) 具有數(shù)學(xué)的科學(xué)性、嚴(yán)謹(jǐn)性，還具有實(shí)踐性與技術(shù)性。 數(shù)值分析方法 常用的數(shù)值計(jì)算方法有構(gòu)造法、離散法、遞推法及近似替代法。 數(shù)值分析工具 籌學(xué) 運(yùn)籌學(xué)的特點(diǎn) 運(yùn)籌學(xué)以一定的數(shù)學(xué)模型為基礎(chǔ)，同時(shí)具有綜合性、實(shí)效性、全局性等特征。 運(yùn)籌學(xué)的研究步驟 (1) 根據(jù)求解問題的目標(biāo)，對問題進(jìn)行分析和表述，抽象出問題本質(zhì)，并構(gòu)造合適的數(shù)學(xué)模型。 (2) 用已有的或?qū)で笮碌慕夥?，對模型進(jìn)行求解。 (3) 從以上兩個(gè)步驟得到的可行方案中選出系統(tǒng)的最優(yōu)解法。 (4) 對