【正文】 偶與范式（續(xù)） 三個(gè)變元 P， Q， R的小項(xiàng)的真值表 : P Q R P ? ?Q ? ? R P ? Q ? R P ? Q ? ?R P ? Q ? R 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 66 16 對偶與范式（續(xù)） 三個(gè)變元 P， Q， R的小項(xiàng)的真值表 : P Q R ?P ? ?Q ? ?R ?P ? ?Q ? R ?P ? Q ? ?R ?P ? Q ? R P ? ?Q ? ? R P ? Q ? R P ? Q ? ?R P ? Q ? R 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 67 16 對偶與范式（續(xù)） 三個(gè)變元 P， Q， R的小項(xiàng)的編碼表 : m000＝ ?P ? ?Q ? ?R m001＝ ?P ? ?Q ? R m010＝ ?P ? Q ? ?R m011＝ ?P ? Q ? R m100＝ P ? ?Q ? ?R m101＝ P ? ? Q ? R m110＝ P ? Q ? ?R m111＝ P ? Q ? R 68 16 對偶與范式（續(xù)） 小項(xiàng)的性質(zhì) : （ 1）每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為 T，在其余 2n1中指派情況下均為 F。 注意：一個(gè)命題的合取范式或析取范式不是唯一的。 P Q P Q T T F T F T F T F F F F 52 15 其它連結(jié)詞 ? 定義： 設(shè) P和 Q是兩個(gè)命題公式，復(fù)合命題 P↑ Q稱為 P和 Q的 “ 與非 ” ，當(dāng)且僅當(dāng) P和 Q的真值都為 T時(shí)， P↑ Q 的真值為 F；否則， P↑ Q的真值為為 T。 證畢。 P Q P?Q ?P (P?Q) ??P 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 例題 3： (P?Q) v(?P??Q)的真值表。 解 找出原子命題： P：上海到北京的 14次列車是下午五點(diǎn)半開。 遞歸定義 基礎(chǔ) 歸納 界限 32 13 命題公式及其賦值 （續(xù)） ? 例如： ? 合式公式： ?(P?Q), ?(P?Q) (P?(P??Q)) ?(((P?Q)?(Q?R))? (S? T)) 非合式公式： (P?Q)?(?Q) (P?Q (P?Q)?Q) 括號不匹配 括號不匹配 ?應(yīng) 是雙目運(yùn)算符 33 13 命題公式及翻譯 ? 聯(lián)結(jié)詞的運(yùn)算優(yōu)先級： 高 低 ? ? ? ? ? ? 命題公式的層（描述公式的復(fù)雜程度） ? 命題公式的賦值（解釋、翻譯） ? 真值表 34 13 命題公式及翻譯 （續(xù)） ? 請看教材 Page 1011。 Q：他可能是 100米或 400米賽跑的冠軍。 0 0 0 0 0 1 0 1 P ? Q 1 0 1 1 P Q P ? Q的真值關(guān)系： 26 12 聯(lián)結(jié)詞 （續(xù)） 析取 設(shè) P， Q為兩個(gè)命題，則新命題“ P或者 Q”稱為命題 P，Q的析取。 記作： ? P 如： P： 2是常數(shù)。一切都好辦。但是，他的招牌說明他不給這類人刮臉，因此他不能自己來刮。 寫成一個(gè)推理．即： 伊勒克持拉不知道站在她面前的這個(gè)人是她的哥哥。這里就產(chǎn)生了問題：理發(fā)師給不給自己刮胡子？如果他給自己刮胡子，他就是自己刮胡子的人，按照他的原則，他不能給自己刮胡子；如果他不給自己刮胡子，他就是不自己刮胡子的人，按照他的原則，他就應(yīng)該給自己刮胡子。 18 希爾伯特證明了切割幾何圖形中的許多重要定理。 悖論是 自相矛盾 的 命題 。 ? 2+3=5 ? 2+3=6 ? 你會(huì)講英語嗎？ ? 3x=5 是命題，真值為 T 是命題，真值為 T 是命題，真值為 F 不是命題 （ 疑問句不是命題） 。也經(jīng)常用 “ 1”表示 “ 真 ” ， “ 0”表示 “ 假 ” 。主要是指引進(jìn)一套 符號體系 的方法，因此數(shù)理邏輯一般又叫符號邏輯。Discrete Mathematics 離散數(shù)學(xué)講義 （電子版） 2 課程概況 教材： 《 離散數(shù)學(xué) （ 第三版 ） 》 ， 耿素云等編著 清華大學(xué)出版社 ， 2022年 3月 參考書： （ 1） 《 離散數(shù)學(xué) (第二版 )》 及其配套參考書 《 離散 數(shù)學(xué)題解 》 作者：屈婉玲，耿素云，張立昂 清華大學(xué)出版社 （ 2） 《 離散數(shù)學(xué) 》 焦占亞主編 電子工業(yè)出版社 2022年 1月 3 課程概況 選修課 /必修課： 選修 周學(xué)時(shí)： 3（ 學(xué)時(shí) ） 上課周： 1－ 16周 總學(xué)時(shí)： 48（ 學(xué)時(shí) ） 4 課程內(nèi)容及學(xué)時(shí)安排 第一篇 數(shù)理邏輯 （ 14學(xué)時(shí) ） 第一章 命題邏輯 （ 8） 第二章 謂詞邏輯（ 6） 第二篇 集合論（ 12學(xué)時(shí)） 第三章 集合（ 4） 第四章 二元關(guān)系與函數(shù)（ 8） 第四篇 圖論（ 14學(xué)時(shí)） 第七章 圖論（ 8） 第八章 一些特殊圖（ 4） 第九章 樹 （ 2） 5 課程考核 考核方式： 閉卷筆試 第四篇 代數(shù)系統(tǒng)（ 8學(xué)時(shí)） 第 6章 圖論（ 8） 6 課程要求 （ 1） 上課認(rèn)真聽講 （ 2） 課后及時(shí)復(fù)習(xí) （ 3） 獨(dú)立 、 認(rèn)真地完成作業(yè) （ 4） 有問題及時(shí)提出 ， 不要積累問題 7 什么是離散數(shù)學(xué)？ ? 是研究離散對象和它們之間的關(guān)系 的現(xiàn)代數(shù)學(xué)。 10 課程內(nèi)容 第一篇 數(shù)理邏輯 11 第一篇 數(shù)理邏輯 ? 數(shù)理邏輯是用數(shù)學(xué)方法來研究推理過程的科學(xué)。 一般 用字母 “ T”表示 “ 真 ” ， “ F”表示“ 假 ” 。 11 命題及其表示法 （續(xù)） 15 判斷下列句子哪些是命題？ ? 地球是圓的。 11 命題及其表示法 （續(xù)） 17 我正在說謊 悖論 (paradox)是一種矛盾命題。萊布尼茨也寫到過他在獨(dú)自玩插棍游戲（一種在小方格中插小木條的游戲）時(shí)分析問題的樂趣。 19 例如比較有名的 理發(fā)師悖論 ：某鄉(xiāng)村有一位 理發(fā)師 ，一天他宣布：只給不自己刮胡子的人刮胡子。它的基本內(nèi)容是：伊勒克特拉有位哥哥奧列斯特回家了．盡管伊勒支持拉知道奧列斯特是她的哥哥．但她并不認(rèn)識站在她面前的這個(gè)男人。 M：誰給這位理發(fā)師刮臉呢？ M：如果他自己刮臉，那他就屬于自己刮臉的那類人。 問，你來這里做什么？ M：如果旅游者回答對了。 注意：命題變項(xiàng)不是命題，它不具有唯一真值 24 12 聯(lián)結(jié)詞 否定 設(shè) P為一命題，則新命題“ P是不對的”稱為 P的否定。 P∧ Q：北京是中國的首都并且是一個(gè)古都。 例如： P：今天晚上我在家看電視或去劇場看戲。 ? （ 4）當(dāng)且僅當(dāng)能夠有限次地應(yīng)用上面 （ 1）、（ 2）、 （ 3） 所得到的包含命題變元、聯(lián)結(jié)詞合括號的 符號串是合式公式。 35 13 命題公式及翻譯 （續(xù)） 例題 2： 上海到北京的 14次列車是下午五點(diǎn)半或六點(diǎn) 開。 P Q ?P ?P?Q 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 1 39 14 真值表與等價(jià)公式 （續(xù)） 例題 2： (P?Q) ??P的真值表。 證明： 由吸收律， (P ? (P ? Q)) ? P 因此，根據(jù)上面的定理，有 Q ? (P ? (P ? Q)) ? Q ? P 。 51 15 其它連結(jié)詞 ? 定義： 設(shè) P和 Q是兩個(gè)命題公式，復(fù)合命題 P Q稱為 P和 Q的條件否定， P Q的真值為 T，當(dāng)且僅當(dāng) P的真值為 T， Q的真值為 F；否則， P Q的真值為為 F。 定義： 一個(gè)命題稱為 析取范式 ，當(dāng)且僅當(dāng)它具有如下的形式： A1?A2 ? … ? An， (n≥1) 其中 A1,A2,… ,An都是由命題變元或其否定所組成的合取式。 一般說來， n個(gè)命題變元共有 2n個(gè)小項(xiàng)。其中每個(gè)變元與它的否定不能同時(shí)存在，但兩者必須且僅出現(xiàn)一次。 ? 定義： 給定一個(gè)命題，若無論對分量作怎樣的指派，其對應(yīng)的真值永遠(yuǎn)為 F，則稱該命題公式為矛盾式或永假公式。 ? ? Q = ? P稱為它的 逆反式 。 推廣： 定義： 設(shè) H1,H2,… ,Hn,C是命題公式，當(dāng)且僅當(dāng) H1 ? H2 ? … ? Hn=C 稱 C是一組前提 H1,H2,… ,Hn的有效結(jié)論。 前提： ?P ? (P ? Q) 結(jié)論： Q ?P ? (P ? Q)=Q 85 18 推理理論 （續(xù)） 解： 公式 ?P ? (P ? Q)的真值表如下： P Q ?P P ? Q ?P ? (P ? Q) T T F T F T F F T F F T T T T F F T F F 所以有 ?P ? (P ? Q)=Q。 96 18 推理理論 （續(xù)） 例題 5. 證明 A?（ B?C）， ?D?A， B重言式蘊(yùn)涵 D?C。 21 謂詞的概念與表示 謂詞演算是對原子命題進(jìn)行分解，它刻劃了命題內(nèi)部的邏輯結(jié)構(gòu)，從而可以深入研究形式邏輯中的推理問題。 A(d)：李四是個(gè)大學(xué)生。如： P（ x1,x2,…xn）是一個(gè)以 x1…xn的個(gè)體域?yàn)槎x域，以 0、1為值域的 n元函數(shù) 注意： n元謂詞 P不是命題 106 量詞：全稱量詞和存在量詞 全稱量詞 (for all)： ? xF(x) 存在量詞 (exist)： ? xG(x) 舉例：書中例子 特性謂詞 使用量詞時(shí)需注意的地方：見書 page40 謂詞公式（一階邏輯合式公式）定義 量詞 107 定義 1： 由一個(gè)謂詞和一些變元所組成的表表達(dá)式稱為 簡單命題函數(shù) 。 解：設(shè) L(x,y)： x大于 y， a： 2， b： 3， c： 4， 則 命題符號化為 L(a,b) ? L(a,c)。 設(shè)： M(x)： x是人。 （ b）一些人是聰明的。 解： 設(shè) F(x,y)： x擺滿了 y； R(x)： x是大紅書柜； Q(y)： y是古書； a：這只； b：那些。 見書 P41關(guān)于字母表、項(xiàng)、原子公式、謂詞公式定義 原子公式 ： A(x1,x2,?,x n)，這里 x1,x2,?,x n是客體變元。 （ 2）換名時(shí)一定要換為作用域中沒有出現(xiàn)過的變元名稱。若對 A和 B的任意一組變元進(jìn)行賦值，所得命題的真值相同，則稱謂詞公式 A和 B在 E上是等價(jià)的。 轉(zhuǎn)化公式： 1.?(?x)P(x)?(?x)?P(x) 2.?(?x)P(x)?(?x)?P(x) 127 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 上述公式的推廣： 設(shè)個(gè)體域中的客體變元為 a1,a2,?,a n，則 1. ?(?x)A(x) ??(A(a1)?A(a2)?… ?A(an)) ??A(a1)??A(a2)?… ??A(an)) ?(?x)?A(x) 2. ?(? x)A(x) ??(A(a1)?A(a2)?… ?A(an)) ??A(a1)??A(a2)?… ??A(an)) ?(?x)?A(x) 128 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 結(jié)論： 當(dāng)將量詞前面的聯(lián)結(jié)詞 ?移到量詞的后面去時(shí)，存在量詞改為全稱量詞，全稱量詞改為存在量詞；反之，如果將 量詞后面的聯(lián)結(jié)詞 ?移到量詞的前面去時(shí)，也要做相應(yīng)的改變。 (?y)(?x)A(x,y) 表示對于乙 村所有的人，甲村都有人和他同