離散數(shù)學(xué)第一章命題邏輯.ppt

《離散數(shù)學(xué)第一章命題邏輯.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第一章命題邏輯.ppt（51頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第一章命題邏輯PropositionLogic 1 1命題及其表示法1 2聯(lián)結(jié)詞1 3命題公式與翻譯1 4重言式 矛盾式 可滿足公式1 5等價(jià)與蘊(yùn)含1 6推理理論 3 1 202011 33AM chapter1 2 1 1命題及其表示法 1 命題命題 非真即假的陳述句 斷言是一陳述語(yǔ)句 一個(gè)命題是一個(gè)或真或假而不能兩者都是的斷言 如果命題是真 我們說(shuō)它的真值為真 如果命題是假 我們說(shuō)它的真值是假 3 1 202011 33AM chapter1 3 例1 判定下列各語(yǔ)句是否為命題 a 巴黎在法國(guó) b 煤是白色的 c 3 2 5 d 別的星球上有生物 e 全體立正 f 明天是否開(kāi)大會(huì) g 天氣多好啊 h 我正在說(shuō)謊 i 如果天氣好 那么我去散步 j x 3 是 是 是 是 否 祈使句 否 疑問(wèn)句 否 感嘆句 否 悖論 是 復(fù)合命題 否 不能確定真值 1 1命題及其表示法 3 1 202011 33AM chapter1 4 2 命題的表示命題變?cè)?常用P Q R S等大寫(xiě)字母或加下標(biāo)的大寫(xiě)字母P1 Q2 R10 表示來(lái)表示一個(gè)命題 稱為命題變?cè)?如 P 巴黎在法國(guó) Q 煤是白色的 1 1命題及其表示法 3 1 202011 33AM chapter1 5 3 命題相關(guān)概念簡(jiǎn)單命題 原子命題 不能再分解的命題 復(fù)合命題 由若干個(gè)簡(jiǎn)單命題復(fù)合而成的命題 真值表 把組成復(fù)合命題的各命題變?cè)恼嬷档乃薪M合及其相對(duì)應(yīng)的復(fù)合命題的真值列成表 稱為真值表 1 1命題及其表示法 3 1 202011 33AM chapter1 6 例2 求公式 P Q P的真值表 解 分以下 步求得 1 寫(xiě)出公式 P的真值表 2 寫(xiě)出公式P Q的真值表 3 根據(jù) 1 和 2 寫(xiě)出公式 P Q P的真值表 為清楚起見(jiàn) 我們將這 步列在一個(gè)表內(nèi) 見(jiàn)下表 1 1命題及其表示法 3 1 202011 33AM chapter1 7 例3 求公式 P R Q R 的真值表 解 公式含有 個(gè)命題變?cè)狿 Q R 真值表有 3 8行 其真值表如下表所示 1 1命題及其表示法 3 1 202011 33AM chapter1 8 1 2聯(lián)結(jié)詞 命題和原子命題?？赏ㄟ^(guò)一些聯(lián)結(jié)詞構(gòu)成新命題 這種新命題叫復(fù)合命題 CompositionalProposition 例如 P 明天下雪 Q 明天下雨是兩個(gè)命題 利用聯(lián)結(jié)詞 不 并且 或 等可構(gòu)成新命題 明天不下雪 明天下雪并且下雨 明天下雪或下雨 等 3 1 202011 33AM chapter1 9 1 2聯(lián)結(jié)詞 即 非P P并且Q P或Q 等 在代數(shù)式x 3中 x 3叫運(yùn)算對(duì)象 叫運(yùn)算符 x 3表示運(yùn)算結(jié)果 在命題演算中 聯(lián)結(jié)詞就是命題演算中的運(yùn)算符 叫邏輯運(yùn)算符或叫邏輯聯(lián)結(jié)詞 常用的有以下5個(gè) 3 1 202011 33AM chapter1 10 1 否定 P是P的否定 讀作 非P P的否定 如 P 成都是中國(guó)的首都 P 成都不是中國(guó)的首都 否定與漢語(yǔ)中的 非 不是 否定 是一致的 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 11 2 合取 P Q是P和Q的合取 讀做 P與Q 或 P并且Q 如 P 王華的成績(jī)很好 Q 王華的品德很好 P Q 王華的成績(jī)很好并且品德很好 合取與漢語(yǔ)中的 和 與 并且 是一致的 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 12 3 析取 P Q是P和Q的析取 讀做 P或Q 如 P 小王喜歡唱歌 Q 小王喜歡跳舞 P Q 小王喜歡唱歌或喜歡跳舞 從真值表可知P Q為真 當(dāng)且僅當(dāng)P或Q至少有一為真 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 13 或 字常見(jiàn)的含義有兩種 一種是 可兼或 如上例中的或 它不排除小王既喜歡唱歌又喜歡跳舞這種情況 一種是 排斥或 異或 例如 人固有一死 或重于泰山 或輕于鴻毛 中的 或 它表示非此即彼 不可兼得 運(yùn)算符 表示可兼或 排斥或以后用另一符號(hào)表達(dá) 如 1 小李明天出差去上?；蛉V州 2 劉昕這次考試可能是全班第一也可能是全班第二 這兩例表示的均是排斥或 即兩種情況不能同時(shí)出現(xiàn) 這時(shí)便不能僅用析取詞 表示 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 14 4 條件 P Q 讀做 如果P 那么Q 或 P則Q 運(yùn)算對(duì)象P叫做前提 假設(shè)或前件 而Q叫做結(jié)論或后件 1 2聯(lián)結(jié)詞 如 P 雪是黑的 Q 太陽(yáng)從東方升起 P Q 如果雪是黑的 則太陽(yáng)從東方升起 命題P Q是假 當(dāng)且僅當(dāng)P是真而Q是假 3 1 202011 33AM chapter1 15 條件與漢語(yǔ)中 如果 就 相類似 但有所區(qū)別 1 自然語(yǔ)言中 如果P則Q 往往P和Q有一定的因果關(guān)系 而條件復(fù)合命題P Q中P和Q可以完全不相關(guān) 2 自然語(yǔ)言中 如果P則Q 當(dāng)P為0 Q為1時(shí) 整個(gè)句子真值難以確定 而條件復(fù)合命題P Q中 當(dāng)P為0時(shí) 復(fù)合命題的真值為1 P則Q的邏輯含義 P是Q的充分條件 Q是P的必要條件 所以 如果P則Q 只要P則Q 只有Q才P 僅當(dāng)Q則P 都可符號(hào)化為P Q的形式 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 16 如 小李對(duì)小王說(shuō) 如果天不下雨 我就來(lái)找你 天沒(méi)下雨 小李去找了小王 天沒(méi)下雨 小李沒(méi)去找小王 天下雨了 小李去找了小王 天下雨了 小李沒(méi)去找小王 1 2聯(lián)結(jié)詞 例4 電燈不亮是電燈壞或電路有毛病 解 設(shè)P 電燈不亮 Q 電燈壞 R 電路有毛病 上述語(yǔ)句應(yīng)表示為 Q R P 3 1 202011 33AM chapter1 17 5 雙條件 P Q 讀做 P當(dāng)且僅當(dāng)Q 如 P 兩個(gè)三角形全等 Q 兩個(gè)三角形的對(duì)應(yīng)邊相等 P Q 兩個(gè)三角形全等當(dāng)且僅當(dāng)其對(duì)應(yīng)邊相等 P當(dāng)且僅當(dāng)Q的邏輯含義 P和Q互為充要條件 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 18 6 聯(lián)結(jié)詞的優(yōu)先次序聯(lián)結(jié)詞的優(yōu)先級(jí) 括號(hào)優(yōu)先 如 P Q R可寫(xiě)成 P Q R P Q R可寫(xiě)成 P Q R P Q R R P Q 可寫(xiě)成 P Q R R P Q為方便起見(jiàn) 公式最外層的括號(hào)可省略 有時(shí)為了看起來(lái)清楚醒目 也可保留某些原可省去的括號(hào) 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 19 單個(gè)命題變?cè)兔}常元叫原子公式 由以下形成規(guī)則生成的公式叫命題公式 簡(jiǎn)稱公式 1 單個(gè)原子公式A B是命題公式 2 如果A和B是命題公式 則 A A B A B A B A B 是命題公式 3 只有有限步使用 1 和 2 所組成的包含命題變?cè)?聯(lián)結(jié)詞以及成對(duì)的括號(hào)組成的符號(hào)串才是命題公式 這種定義叫歸納定義 也叫遞歸定義 由這種定義產(chǎn)生的公式也叫合式公式 Well FormedFormulas 簡(jiǎn)寫(xiě)為wff 1 3命題公式 3 1 202011 33AM chapter1 20 例5 判斷下列表達(dá)式是否為合式公式 p p q p q r p q r p q q r pq r p q r s p q r s 是 是 否 否 否 是 是 1 3命題公式 3 1 202011 33AM chapter1 21 例6 將下列自然語(yǔ)言形式化 a 如果天不下雨并且不刮風(fēng) 我就去書(shū)店 解 設(shè)P 今天天下雨 Q 今天天刮風(fēng) R 我去書(shū)店 則原命題符號(hào)化為 P Q R b 小王邊走邊唱 解 設(shè)p 小王走路 q 小王唱歌 則原命題符號(hào)化為 p q c 除非a能被2整除 否則a不能被4整除 解 設(shè)p a能被2整除 q a能被4整除 則原命題符號(hào)化為 p q或q p 1 3命題公式 3 1 202011 33AM chapter1 22 d 此時(shí) 小剛要么在學(xué)習(xí) 要么在玩游戲 解 設(shè)p 小剛在學(xué)習(xí) q 小剛在玩游戲 則原命題符號(hào)化為 p q p q 或 p q p q e 如果天不下雨 我們?nèi)ゴ蚧@球 除非班上有會(huì) 解 設(shè)p 今天天下雨 q 我們?nèi)ゴ蚧@球 r 今天班上有會(huì) 則原命題符號(hào)化為 r p q 1 3命題公式 3 1 202011 33AM chapter1 23 1 重言式 Tautology 重言式 永真式 真值恒為1的公式 如 P P 例7 判斷 P P P Q 是否為重言式 P P P Q 為重言式 1 4重言式 矛盾式 可滿足公式 3 1 202011 33AM chapter1 24 2 矛盾式 Contradiction 矛盾式 永假式 真值恒為0的公式 如 P P 例8 判斷 P Q P是否為矛盾式 P Q P 為矛盾式 1 4重言式 矛盾式 可滿足公式 3 1 202011 33AM chapter1 25 3 可滿足公式 Satisfaction 可滿足公式 至少有一種真值為1的情況 除矛盾式之外的公式 永真式也是可滿足公式 定理 由n個(gè)命題變?cè)还部山M成個(gè)不同的命題 其中永真式有一個(gè) 矛盾式有一個(gè) 可滿足公式有個(gè) 1 4重言式 矛盾式 可滿足公式 3 1 202011 33AM chapter1 26 例9 構(gòu)造公式 P Q P Q P Q Q P的真值 解 真值表如下 由例題可見(jiàn) 公式 P Q P Q P Q Q P的真值表是完全相同的 我們稱其為等值的 那么如何判斷兩個(gè)公式等值呢 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 27 1 5 1等價(jià)1 等價(jià)的定義等價(jià) 設(shè)A B是兩個(gè)命題公式 當(dāng)A與B有完全相同的真值 則稱A和B等價(jià) 即為A B 定理 設(shè)A B是兩個(gè)命題公式 A B的充要條件是A B為永真式 等價(jià)置換 假設(shè)X是公式A的子公式 如果X Y 則將X置換為Y所得的公式與A等價(jià) 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 28 2 等價(jià) 與雙條件 的區(qū)別等價(jià) 不是一個(gè)聯(lián)結(jié)詞 A B不是一個(gè)命題公式 表示的是A B之間的邏輯關(guān)系 雙條件 是一個(gè)聯(lián)結(jié)詞 A B是命題公式 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 29 3 常用的等值式 1 雙重否定律A A 2 冪等律A A AA A A 3 交換律A B B AA B B A 4 結(jié)合律 A B C A B C A B C A B C 5 分配律A B C A B A C A B C A B A C 6 德 摩根律 A B A B A B A B 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 30 7 吸收律A A B AA A B A 8 零律A 1 1A 0 0 9 同一律A 0 AA 1 A 10 否定律A A 1A A 0 11 蘊(yùn)涵等值式A B A B 12 等價(jià)等值式A B A B B A 13 逆反律A B B A 14 輸出律A B C A B C 15 歸謬論 A B A B A 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 31 思考 證明兩個(gè)公式等價(jià)的方法 1 構(gòu)造真值表 2 等價(jià)推導(dǎo)法 若一個(gè)公式變?cè)?由于n個(gè)變?cè)M成的真值表有2n行 所以用等價(jià)推導(dǎo)的方法來(lái)證明 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 32 例11 用等值演算證明p q r p q r 證明 p q r p q r 蘊(yùn)涵等值式 p q r 蘊(yùn)涵等值式 p q r 結(jié)合律 p q r 德 摩根律 p q r 蘊(yùn)涵等值式 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 33 例12 化解公式 p q r q r p r 解 p q r q r p r p q r q p r p q r q p r p q q p r p q q p r 1 r r 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 34 1 5 2蘊(yùn)含1 蘊(yùn)涵的定義蘊(yùn)含 設(shè)A B是兩個(gè)命題公式 若A為真 B必定為真 則稱A蘊(yùn)含B 記作A B 定理 設(shè)A B是兩個(gè)命題公式 A B的充要條件是A B為永真式 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 35 2 蘊(yùn)含 與條件 的區(qū)別蘊(yùn)含 不是一個(gè)聯(lián)結(jié)詞 A B不是一個(gè)命題公式 表示的是A B之間的邏輯關(guān)系 條件 是一個(gè)聯(lián)結(jié)詞 A B是命題公式 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 36 例13 證明 P Q P Q 證明 真值表如下 由真值表可見(jiàn) P Q P為1時(shí) Q為真 P Q P Q 1 5等價(jià)與蘊(yùn)涵 3 1 202011 33AM chapter1 37 1 6 1推理推理 已知H1 H2 Hm 證明C的過(guò)程 寫(xiě)成命題邏輯的形式為 H1 H2 Hm C其中 H1 H2 Hm稱為推理的前提 C為這一組前提的有效結(jié)論 推理的過(guò)程就是證明H1 H2 Hm C的過(guò)程 1 6 2推理方法證明H1 H2 Hm C為永真式 1 真值表法2 等價(jià)推導(dǎo)法 1 6推理理論 3 1 202011 33AM chapter1 38 例14 證明 P Q Q R P R 證明 P Q Q R P R P Q Q R P R P Q Q R P R P Q Q R P R P Q Q R P R P Q P Q R R Q P Q R T 1 6推理理論 3 1 202011 33AM chapter1 39 3 幾種常用的推理的定律 1 假言推理 肯定的肯定 P P Q Q通過(guò)肯定條件的前件從而肯定條件的后件 如 P Q 如果他喝酒 則他臉紅 P 他喝酒 Q 他臉紅 注意 不能通過(guò)肯定條件的后件而肯定條件的前件 1 6推理理論 3 1 202011 33AM chapter1 40 2 拒取式 否定的否定 Q P Q P通過(guò)否定條件的后件從而否定條件的前件 如 P Q 小王評(píng)上三好學(xué)生 則小王成績(jī)好 Q 小王成績(jī)不好 P 小王沒(méi)評(píng)上三好學(xué)生 注意 不能通過(guò)否定條件的前件而肯定條件的后件 1 6推理理論 3 1 202011 33AM chapter1 41 3 析取三段論 P Q P Q產(chǎn)生一個(gè)事件的原因有P和Q 否定P 則一定是Q 如 P Q 成績(jī)不好是老師教得不好或自己不努力 P 老師教得好 Q 自己不努力 推廣 P Q R S P Q R S 1 6推理理論 3 1 202011 33AM chapter1 42 4 假言三段論 P Q Q R P R如 P Q 如果不下雨 就開(kāi)運(yùn)動(dòng)會(huì) Q R 如果開(kāi)運(yùn)動(dòng)會(huì) 就不上課 P R 如果不下雨 就不上課 1 6推理理論 3 1 202011 33AM chapter1 43 1 6推理理論 常用的蘊(yùn)涵式 3 1 202011 33AM chapter1 44 4 證明方法 形式演繹 1 P規(guī)則 前提引入規(guī)則 給定的前提在證明的過(guò)程中隨時(shí)都可以加以引用 2 規(guī)則 結(jié)論引用規(guī)則 在證明過(guò)程中產(chǎn)生的結(jié)論可以作為后續(xù)證明的前提加以引用 3 CP規(guī)則 附加前提引入規(guī)則 如果證明的形式為H1 H2 Hm A B 等價(jià)于證明H1 H2 Hm A B A稱為附加前提 1 6推理理論 3 1 202011 33AM chapter1 45 證明 證明H1 H2 Hm A B等價(jià)于證明 H1 H2 Hm A B 為永真式 H1 H2 Hm A B H1 H2 Hm A B H1 H2 Hm A B H1 H2 Hm A B 證明H1 H2 Hm A B等價(jià)于證明H1 H2 Hm A B 1 6推理理論 3 1 202011 33AM chapter1 46 例15 證明 P Q P R Q S R S 證明 P QP P QT Q SP P ST S PT P RP S RT R ST 1 6推理理論 3 1 202011 33AM chapter1 47 例16 證明P Q S R P Q R S 證明 R PP R PT RCP PT P Q S P Q ST QP ST 1 6推理理論 3 1 202011 33AM chapter1 48 例17 證明下面諸命題推得的結(jié)論是有效的 如果今天是星期三 那么我有一次離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)測(cè)驗(yàn) 如果離散數(shù)學(xué)課老師有事 那么沒(méi)有離散數(shù)學(xué)測(cè)驗(yàn) 今天是星期三且離散數(shù)學(xué)老師有事 所以 我有一次數(shù)據(jù)結(jié)構(gòu)測(cè)驗(yàn) 證明 先將各命題形式化 設(shè)A 今天是星期三 B 我有一次離散數(shù)學(xué)測(cè)驗(yàn) C 我有一次數(shù)據(jù)結(jié)構(gòu)測(cè)驗(yàn) D 離散數(shù)學(xué)課老師有事 則本題要求證 A B C D B A D C 1 6推理理論 3 1 202011 33AM chapter1 49 A B C D B A D C A DP AT A B CP B CT DT D BP BT CT 1 6推理理論 3 1 202011 33AM chapter1 50 例17 公安人員審一件盜竊案 已知 1 甲或乙盜竊了電腦 2 若甲盜竊了電腦 則作案時(shí)間不能發(fā)生在午夜前 3 若乙證詞正確 則在午夜時(shí)屋里燈光未滅 4 若乙證詞不正確 則作案時(shí)間發(fā)生在午夜前 5 午夜時(shí)屋里燈光滅了 問(wèn) 誰(shuí)是盜竊犯 解 設(shè)P 甲盜竊了電腦 Q 乙盜竊了電腦 R 作案時(shí)間發(fā)生在午夜前 S 乙證詞正確 T 午夜時(shí)屋里燈光滅了 前提 P Q P R S T S R T 1 6推理理論 3 1 202011 33AM chapter1 51 前提 P Q P R S T S R T推理 TP S TP ST S RP RT P RP PT QT 因此可得結(jié)論 乙是盜竊犯 1 6推理理論