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

第一章命題邏輯PropositionLogic 1 1命題及其表示法1 2聯(lián)結(jié)詞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 是 是 是 是 否 祈使句 否 疑問句 否 感嘆句 否 悖論 是 復(fù)合命題 否 不能確定真值 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 命題相關(guān)概念簡單命題 原子命題 不能再分解的命題 復(fù)合命題 由若干個簡單命題復(fù)合而成的命題 真值表 把組成復(fù)合命題的各命題變元的真值的所有組合及其相對應(yīng)的復(fù)合命題的真值列成表 稱為真值表 1 1命題及其表示法 3 1 202011 33AM chapter1 6 例2 求公式 P Q P的真值表 解 分以下 步求得 1 寫出公式 P的真值表 2 寫出公式P Q的真值表 3 根據(jù) 1 和 2 寫出公式 P Q P的真值表 為清楚起見 我們將這 步列在一個表內(nèi) 見下表 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)結(jié)詞 命題和原子命題?？赏ㄟ^一些聯(lián)結(jié)詞構(gòu)成新命題 這種新命題叫復(fù)合命題 CompositionalProposition 例如 P 明天下雪 Q 明天下雨是兩個命題 利用聯(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叫運算對象 叫運算符 x 3表示運算結(jié)果 在命題演算中 聯(lián)結(jié)詞就是命題演算中的運算符 叫邏輯運算符或叫邏輯聯(lián)結(jié)詞 常用的有以下5個 3 1 202011 33AM chapter1 10 1 否定 P是P的否定 讀作 非P P的否定 如 P 成都是中國的首都 P 成都不是中國的首都 否定與漢語中的 非 不是 否定 是一致的 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 11 2 合取 P Q是P和Q的合取 讀做 P與Q 或 P并且Q 如 P 王華的成績很好 Q 王華的品德很好 P Q 王華的成績很好并且品德很好 合取與漢語中的 和 與 并且 是一致的 1 2聯(lián)結(jié)詞 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)結(jié)詞 3 1 202011 33AM chapter1 13 或 字常見的含義有兩種 一種是 可兼或 如上例中的或 它不排除小王既喜歡唱歌又喜歡跳舞這種情況 一種是 排斥或 異或 例如 人固有一死 或重于泰山 或輕于鴻毛 中的 或 它表示非此即彼 不可兼得 運算符 表示可兼或 排斥或以后用另一符號表達 如 1 小李明天出差去上海或去廣州 2 劉昕這次考試可能是全班第一也可能是全班第二 這兩例表示的均是排斥或 即兩種情況不能同時出現(xiàn) 這時便不能僅用析取詞 表示 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 14 4 條件 P Q 讀做 如果P 那么Q 或 P則Q 運算對象P叫做前提 假設(shè)或前件 而Q叫做結(jié)論或后件 1 2聯(lián)結(jié)詞 如 P 雪是黑的 Q 太陽從東方升起 P Q 如果雪是黑的 則太陽從東方升起 命題P Q是假 當且僅當P是真而Q是假 3 1 202011 33AM chapter1 15 條件與漢語中 如果 就 相類似 但有所區(qū)別 1 自然語言中 如果P則Q 往往P和Q有一定的因果關(guān)系 而條件復(fù)合命題P Q中P和Q可以完全不相關(guān) 2 自然語言中 如果P則Q 當P為0 Q為1時 整個句子真值難以確定 而條件復(fù)合命題P Q中 當P為0時 復(fù)合命題的真值為1 P則Q的邏輯含義 P是Q的充分條件 Q是P的必要條件 所以 如果P則Q 只要P則Q 只有Q才P 僅當Q則P 都可符號化為P Q的形式 1 2聯(lián)結(jié)詞 3 1 202011 33AM chapter1 16 如 小李對小王說 如果天不下雨 我就來找你 天沒下雨 小李去找了小王 天沒下雨 小李沒去找小王 天下雨了 小李去找了小王 天下雨了 小李沒去找小王 1 2聯(lián)結(jié)詞 例4 電燈不亮是電燈壞或電路有毛病 解 設(shè)P 電燈不亮 Q 電燈壞 R 電路有毛病 上述語句應(yīng)表示為 Q R P 3 1 202011 33AM chapter1 17 5 雙條件 P Q 讀做 P當且僅當Q 如 P 兩個三角形全等 Q 兩個三角形的對應(yīng)邊相等 P Q 兩個三角形全等當且僅當其對應(yīng)邊相等 P當且僅當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)先級 括號優(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)結(jié)詞 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)結(jié)詞以及成對的括號組成的符號串才是命題公式 這種定義叫歸納定義 也叫遞歸定義 由這種定義產(chǎ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 如果天不下雨并且不刮風 我就去書店 解 設(shè)P 今天天下雨 Q 今天天刮風 R 我去書店 則原命題符號化為 P Q R b 小王邊走邊唱 解 設(shè)p 小王走路 q 小王唱歌 則原命題符號化為 p q c 除非a能被2整除 否則a不能被4整除 解 設(shè)p a能被2整除 q a能被4整除 則原命題符號化為 p q或q p 1 3命題公式 3 1 202011 33AM chapter1 22 d 此時 小剛要么在學習 要么在玩游戲 解 設(shè)p 小剛在學習 q 小剛在玩游戲 則原命題符號化為 p q p q 或 p q p q e 如果天不下雨 我們?nèi)ゴ蚧@球 除非班上有會 解 設(shè)p 今天天下雨 q 我們?nèi)ゴ蚧@球 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 構(gòu)造公式 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 等價的定義等價 設(shè)A B是兩個命題公式 當A與B有完全相同的真值 則稱A和B等價 即為A B 定理 設(shè)A B是兩個命題公式 A B的充要條件是A B為永真式 等價置換 假設(shè)X是公式A的子公式 如果X Y 則將X置換為Y所得的公式與A等價 1 5等價與蘊涵 3 1 202011 33AM chapter1 28 2 等價 與雙條件 的區(qū)別等價 不是一個聯(lián)結(jié)詞 A B不是一個命題公式 表示的是A B之間的邏輯關(guān)系 雙條件 是一個聯(lián)結(jié)詞 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 結(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等價與蘊涵 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 構(gòu)造真值表 2 等價推導(dǎo)法 若一個公式變元太多 由于n個變元組成的真值表有2n行 所以用等價推導(dǎo)的方法來證明 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 結(jié)合律 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 蘊涵的定義蘊含 設(shè)A B是兩個命題公式 若A為真 B必定為真 則稱A蘊含B 記作A B 定理 設(shè)A B是兩個命題公式 A B的充要條件是A B為永真式 1 5等價與蘊涵 3 1 202011 33AM chapter1 35 2 蘊含 與條件 的區(qū)別蘊含 不是一個聯(lián)結(jié)詞 A B不是一個命題公式 表示的是A B之間的邏輯關(guān)系 條件 是一個聯(lián)結(jié)詞 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為這一組前提的有效結(jié)論 推理的過程就是證明H1 H2 Hm C的過程 1 6 2推理方法證明H1 H2 Hm C為永真式 1 真值表法2 等價推導(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通過肯定條件的前件從而肯定條件的后件 如 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產(chǎn)生一個事件的原因有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ī)則 結(jié)論引用規(guī)則 在證明過程中產(chǎn)生的結(jié)論可以作為后續(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 證明下面諸命題推得的結(jié)論是有效的 如果今天是星期三 那么我有一次離散數(shù)學或數(shù)據(jù)結(jié)構(gòu)測驗 如果離散數(shù)學課老師有事 那么沒有離散數(shù)學測驗 今天是星期三且離散數(shù)學老師有事 所以 我有一次數(shù)據(jù)結(jié)構(gòu)測驗 證明 先將各命題形式化 設(shè)A 今天是星期三 B 我有一次離散數(shù)學測驗 C 我有一次數(shù)據(jù)結(jié)構(gòu)測驗 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 午夜時屋里燈光滅了 問 誰是盜竊犯 解 設(shè)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 因此可得結(jié)論 乙是盜竊犯 1 6推理理論