《離散數(shù)學第一章命題邏輯.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學第一章命題邏輯.ppt（51頁珍藏版）》請在裝配圖網上搜索。

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