【正文】 在一定區(qū)間內(nèi)可以任意取值的變量叫連續(xù)變量 ,其數(shù)值是連續(xù)不斷的 ,相鄰兩個(gè)數(shù)值可作無(wú)限分割 ,即可取無(wú)限個(gè)數(shù)值 .其數(shù)值只能用 測(cè)量或計(jì)量 的方法取得 . 第一類(lèi)是研究運(yùn)動(dòng)的時(shí)候直接出現(xiàn)的，也就是求即時(shí)速度的問(wèn)題。 第二類(lèi)問(wèn)題是求曲線(xiàn)的切線(xiàn)的問(wèn)題。 ? 計(jì)算機(jī)的結(jié)構(gòu)是離散的（硬、軟件 —晶體管，集成塊，元件，部件，設(shè)備，軟件 :程序，語(yǔ)句，符號(hào)）計(jì)算機(jī)所服務(wù)的對(duì)象均是離散的，而對(duì)連續(xù)對(duì)象計(jì)算機(jī)是無(wú)能為力的。 離散數(shù)學(xué)的特點(diǎn) Institute of Computer Software 王兵 2022/4/14 計(jì)算機(jī)學(xué)院 10 離散數(shù)學(xué)的構(gòu)成 數(shù)理邏輯 集合論 圖論 代數(shù)系統(tǒng) 命題邏輯 謂詞邏輯 集合 關(guān)系 圖的基本概念 幾個(gè)特殊圖 代數(shù)系統(tǒng)的基本概念 幾個(gè)特殊代數(shù)系統(tǒng) 離散數(shù)學(xué) 函數(shù) 圖的連通性 代數(shù)系統(tǒng)的同態(tài)與同構(gòu) Institute of Computer Software 王兵 Institute of Computer Software 王兵 ?數(shù)理邏輯（ Mathematical Logic） —— 是研究演繹推理的一門(mén)學(xué)科，用 數(shù)學(xué)的方法 來(lái)研究 推理的規(guī)律 統(tǒng)稱(chēng)為數(shù)理邏輯。” 以下各項(xiàng)陳述都可以從裁縫的斷言中邏輯地推出， 除了 A. 凡是不稱(chēng)職的人都看不見(jiàn)這衣服。 ? 聰明的俘虜 問(wèn)題： “ 你來(lái)這里做什么 ？ ” 被火燒死。 (1) 2是素?cái)?shù)。 (5)明年國(guó)慶節(jié)是晴天 。 非陳述語(yǔ)句都不是命題 ，如： I ： 天哪！ ( 祈使句 ) J：你好嗎？ ( 疑問(wèn)句 ) K：立正！ (命令句 ) 不能判斷真假的陳述語(yǔ)句叫悖論 。 (如果他講真話(huà)，則他說(shuō)的是真的，也就是他是在說(shuō)謊 ) ∴ 此話(huà)既不是說(shuō)謊也不是講真話(huà)，不能判斷它的真假值。 ┐Q: 這些不都是男同學(xué) 。 (b) R: G是正方形 , S: G的四邊相等 。 Institute of Computer Software 王兵 2022年 4月 14日 36 ? 如果我當(dāng)選了，則我將會(huì)減稅 蘊(yùn)含真值理解 p q p → q T T T T F F F T T F F T 在 數(shù)理邏輯 中，當(dāng)前件 P為假 時(shí)，不管 Q的真假如何，則 P→Q 都為真 。 Institute of Computer Software 王兵 例 令： P：天氣好。 ，我就去公園。 P→ Q P→ Q P→ Q Q→ P Q→ P Q→ P Institute of Computer Software 王兵 蘊(yùn)含 (implication) ? 蘊(yùn)涵與 if 語(yǔ)句之間有所不同 – if p then s ? if 2+3=5 then x=x+1 – if (p) s。 （ 2）設(shè)Ｐ：王超是一個(gè)思想品德好的學(xué)生； Ｑ：王超是一個(gè)學(xué)習(xí)成績(jī)好的學(xué)生； R：王超是一個(gè)體育成績(jī)好的學(xué)生。 則命題（ 4）可表示為 Ｐ → Ｑ 。這個(gè)剃頭匠只給那些不自己剃須的人刮胡子。 p? ﹁ q：顯然這個(gè)邏輯表達(dá)式是為假的。 Institute of Computer Software 王兵 64 邏輯等價(jià) (equivalence) ? 若 p?q是永真式，則命題 p與 q邏輯等價(jià) –記號(hào)： p≡q、 p?q –判定命題等價(jià)的方法 –真值表 –恒等式變換 Institute of Computer Software 王兵 65 重要的等價(jià)關(guān)系 ? 表 11表 11表 115 –最基本的邏輯等價(jià)關(guān)系 –邏輯運(yùn)算的規(guī)則 ? 用于構(gòu)造其他等價(jià)關(guān)系 –邏輯等價(jià)的命題之間 ?可以相互替換 ?具有可傳遞性 Institute of Computer Software 王兵 證明 ?(pVq) 和 ?p ∧ ? q 等價(jià) Institute of Computer Software 王兵 證明 p?q和 ?p ∨ q等價(jià) 求下列命題公式的真值表 ? ( p ? q ) ? q 真值分析如下： p q p ? q ? ( p ? q ) ? ( p ? q ) ? q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 表 Institute of Computer Software 王兵 69 用等價(jià)推導(dǎo)證明命題等價(jià)？ ? 等價(jià)推導(dǎo)比真值表驗(yàn)證簡(jiǎn)單 –含 n個(gè)命題變量的真值表有 2n行 ? 隨著 n的增長(zhǎng)，行數(shù)呈現(xiàn)指數(shù) (幾何級(jí)數(shù) )增長(zhǎng) –等價(jià)推導(dǎo)不能直接證明兩個(gè)公式不等價(jià) Institute of Computer Software 王兵 常用的重要等值公式 A ? ? (? A) A ? A ? A A ? A ? A A ? B ? B ? A A ? B ? B ? A (A ? B) ? C ? A ? (B ? C) (A ? B) ? C ? A ? (B ? C) 雙重否定律 結(jié)合律 交換律 等冪律 Institute of Computer Software 王兵 分配律 零律 吸收律 德 q ? r) ? (172。摩根 律 蘊(yùn)涵等值式 Institute of Computer Software 王兵 77 實(shí)際問(wèn)題推理 ? 求解實(shí)際問(wèn)題 –例：某單位要從 A、 B、 C三人中選派若干人出國(guó)考察 , 需滿(mǎn)足下述條件 ? (1)若 A去，則 C必須去 ? (2) 若 B去，則 C不能去 ? (3) A和 B必須去一人且只能去一人 –問(wèn)有幾種可能的選派方案？ Institute of Computer Software 王兵 78 實(shí)際問(wèn)題推理 ? 解：記 p: 派 A去， q: 派 B去， r: 派 C去 – (1)若 A去，則 C必須去 ? p?r – (2)若 B去，則 C不能去 ? q??r – (3) A和 B必須去一人且只能去一人 ? (p??q)?(?p?q) Institute of Computer Software 王兵 79 實(shí)際問(wèn)題推理 ? 記 p: 派 A去， q: 派 B去， r: 派 C去 – (1)若 A去，則 C必須去： p?r – (2)若 B去，則 C不能去： q??r – (3)A和 B必須且只能去一人： (p??q)?(?p?q) ? 求下式的成真賦值 – A=(p?r)?(q??r)?((p??q)?(?p?q)) Institute of Computer Software 王兵 80 實(shí)際問(wèn)題推理 ? A=(p?r)?(q??r)?((p??q)?(?p?q)) ?(?p?r)?(?q??r)?((p??q)?(?p?q)) ?((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q)) ?((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?p??r)?(?p?q))?((r??q)?(?p?q)) ?(p??q?r)?(?p?q??r) Institute of Computer Software 王兵 81 實(shí)際問(wèn)題推理 ? A=(p?r)?(q??r)?((p??q)?(?p?q)) –?(p??q?r)?(?p?q??r) –成真賦值 :101,010 –結(jié)論 ?方案 1：派 A、 C去 ?方案 2：派 B去 Institute of Computer Software 王兵 82 第 1章 基礎(chǔ)：邏輯和證明、集合、函數(shù) ? 謂詞和量詞 Institute of Computer Software 王兵 83 引言 ? 命題邏輯有局限 ? 研究命題之間關(guān)系，基本單位是原子命題 李明是西南石油大學(xué)學(xué)生 張鵬是西南石油大學(xué)學(xué)生 劉璐是西南石油大學(xué)學(xué)生 Institute of Computer Software 王兵 命題邏輯只能進(jìn)行 命題間關(guān)系 的推理，無(wú)法解決與 命題的結(jié)構(gòu)和成分 有關(guān)的推理問(wèn)題。 解決辦法： 將命題進(jìn)行分解 。 刻劃客體的性質(zhì) （ 3） 王紅 是個(gè)大學(xué)生 。 ??????????Institute of Computer Software 王兵 ? 刻劃 一個(gè)客體性質(zhì) 的詞稱(chēng)之為 一元謂詞 ,刻劃 n個(gè)客體之間關(guān)系 的詞稱(chēng)之為 n元謂詞 . ? 一般我們用大寫(xiě)英文字母表示 謂詞， 用小寫(xiě)英文字母表示客體名稱(chēng)， (1) F(a) a： 張明 (2) F(b) b： 李華 (3) G(c) c： 王紅 (4) H(s,t) s： 小李 t：小趙 (5) R(a,b,c) (6) S(a,b) a:阿杜 。 x：個(gè)體詞 P：謂詞 P(x):命題函數(shù) P(x) 命題函數(shù) =變量 +謂詞 (predicate) Institute of Computer Software 王兵 例 設(shè)有如下命題，并用 n元謂詞進(jìn)行表示。 Institute of Computer Software 王兵 93 謂詞實(shí)例 ? 程序語(yǔ)言中的謂詞 – if (x0) x=x+1。 則有：（ 1） 所有的 x， P(x) x∈ {老虎｝； （ 2） 每一個(gè) x， Q(x) x∈ {大學(xué)生 }； （ 3） 所有的 x， R(x) x∈ {人 }； （ 4） 有一些 x， S(x) x∈ {人 }； （ 5） 有一些 x， T(x) x∈ {自然數(shù) }。個(gè)體域可以是有限事物的集合，也可以是無(wú)限事物的集合。 （ 2） 每個(gè)學(xué)生都要參加考試 。 則 （ 1） 符號(hào)化為 ?x(M(x) ?F(x)). Institute of Computer Software 王兵 (2) 當(dāng)個(gè)體域?yàn)?全體學(xué)生的集合 時(shí)： 令 P(x): x要參加考試 。 則 （ 3） 符號(hào)化為 ?x(P(x)∨ N(x)) 當(dāng)個(gè)體域?yàn)?全總個(gè)體域 時(shí)： 令 I(x): x是 整數(shù) 。 則 （ 2） 符號(hào)化為 ?xG(x) 當(dāng)個(gè)體域?yàn)?全總個(gè)體域 時(shí)： 令 M(x): x是人 。 118 翻譯語(yǔ)句 ? 用謂詞將命題符號(hào)化 –墨西哥位于南美洲 –若 是無(wú)理數(shù)，則 是有理數(shù) –如果 23，則 34 2 3119 解答 ? 在謂詞邏輯中： – F(a) ? a：墨西哥， F(x)： x位于南美洲 – F( )?G( ) ? F(x)： x是無(wú)理數(shù)， G(x)： x是有理數(shù) – F(2, 3)?G(3, 4) ? F(x, y)： xy， G(x, y)： xy 2 3120 翻譯語(yǔ)句 ? 王強(qiáng)是大學(xué)生李華也是大學(xué)生 –令 F(x)： x是大學(xué)生 –令 a：王強(qiáng)， b：李華 – F(a)?F(b) 121 翻譯語(yǔ)句 ? 中國(guó)代表團(tuán)訪(fǎng)問(wèn)朝鮮 –令 F(x,y)： x訪(fǎng)問(wèn) y –令 a：中國(guó)代表團(tuán)， b：朝鮮 – F(a,