邏輯學真值表及命題演算.ppt

《邏輯學真值表及命題演算.ppt》由會員分享，可在線閱讀，更多相關《邏輯學真值表及命題演算.ppt（56頁珍藏版）》請在裝配圖網上搜索。

第五章真值表方法與命題演算 教學重點與要點完全真值表法的判定功用歸謬賦值法的操作與判定命題演算證明方法的應用與構造 一 真值聯(lián)結詞 定義 真值聯(lián)結詞是指僅僅表示復合命題與肢命題之間真假關系的聯(lián)結詞 真值聯(lián)結詞主要有五個 否定 合取 析取 蘊涵 等值 二 真值形式 定義 真值形式是指由真值聯(lián)結詞和命題變項所構成的形式結構 五種基本的真值形式否定式 p合取式 p q析取式 p q蘊涵式 p q等值式 p q 三 五種基本真值形式的真值表 定義 真值表是數理邏輯中用以定義命題聯(lián)結詞并確定復合命題真或假的一種圖表 T表示 真 F表示 假 1 p 2 p q 3 p q 4 p q 5 p q 真值表判定程序的三個要求 1 程序的每一步都是由事先給定的規(guī)則明確規(guī)定好的 2 對于所判定的對象是否具有某種性質 該程序能夠給出唯一確定的結果 3 該程序能夠在有窮步驟結束 判定程序的特點 機械的 能行的 可判定的 完全真值表法 完全真值表的作法三個步驟 1 找出已給命題公式的所有變項 并豎行列出這些變項的所有真值組合 2 根據命題公式的結構 由繁到簡的依次橫行列出 一次只引進一個連接詞 直至列出該公式本身 3 依據基本真值表 有變項的真值逐步計算出每個部分的真值 最后列出整個公式得真值 完全真值表法的判定功能 1 命題公式的性質判定 2 推理形式有效性的判定 3 命題公式之間關系的判定 重言式 矛盾式 可滿足式的判定 1 重言式 又叫永真式 是指在一個命題形式中不論其中的變項取什么值 該命題形式的值總是真的 如 p p 2 矛盾式 又叫永假式 是指在一個命題形式中不論其中的變項取什么值 該命題形式的值總是假的 如 p p 3 可滿足式 協(xié)調式 是指在一個命題形式中不論其中的變項取什么值 該命題形式的值至少在一種情況下是真的 如 p q 真值表判定任一命題形式是否是重言式 例1 p q p q 例2 p q p q 真值表判定任意兩個復合命題之間是否具有等值關系 例1 p q p q 由真值表可知這兩個命題之間具有等值關系 例2 p q p q 三 真值表幫助解決一些推理問題 例 列出A B C三命題的真值表 并回答當A B C三命題恰有一個為真時 甲是否是木工 A 如果甲不是木工 則乙是泥工 B 如果乙不是泥工 則甲不是木工 C 甲不是木工 且乙不是泥工 解設p表示 甲是木工 q表示 乙是泥工 A p qB q pC p q 練習題 一 用真值表判定下列真值形式是否是重言式1 P q p q2 P q q P 二 請用真值表判定下列各組命題形式之間是否具有等值關系 1 P q P q2 P q P q 三 列出A B兩命題的真值表 并回答A B恰有一個為假時 王軍是否考上了大學 A 如果王軍考上了大學 那么李偉就沒有考上大學 B 王軍沒有考上大學 四 列出A B C三命題的真值表 并回答當A B C三命題恰有一真時 是否甲村所有人家都有彩電 A 甲村所有人家都有彩電 并且乙村所有人家都有彩電 B 或者甲村所有人家都有彩電 或者乙村所有人家都有彩電 C 如果乙村所有人家都有彩電 那么甲村有些人家沒有彩電 真值表法的局限性 1 完全真值表法的局限性判定多變項命題公式過于繁瑣 2 歸謬賦值法的局限性僅能判定蘊涵式 3 真值樹法的局限性判定結構復雜的公式時 樹冠過大操作不便 4 問題 是否有一種方法既能解決命題邏輯有效性的判定問題又能解決有效性的推導問題 命題演算的證明方法 一 命題演算方法概述1 命題演算方法在問題求解上的必要性認知2 命題演算與形式系統(tǒng)構造3 公理系統(tǒng)與自然演繹系統(tǒng)4 自然演繹法的基本思想5 具體推證方法的認知 直接證明法 間接證明法 反證法 一 直接證明法 1 直接證明法的特點認知勿需附加任何前提即可依規(guī)則從給定的前提推導出結論 2 直接證明法的操作步驟 1 依序編號排列前提 將結論寫在最后一個前提的右側并用 斷開 2 依據已知前提結合相關規(guī)則推出新的命題 依次編號寫在下面 3 在推出的新命題右側括號內注明前提依據和規(guī)則依據 4 證明結束寫上證畢字樣 推證實例分析1 A B2 C D3 A C B D 直接證明法 1 A B2 C D3 A C B D4 A C 3 等值 5 A D 4 2 連鎖 6 B A 1 易位 7 B D 6 4 連鎖 8 B D 7 等值 證畢 二 假設證明法 1 間接推證法的特點認知給定前提不夠 需要附加 2 假設證明法的基本思路附加假設 依據蘊涵引入的規(guī)則有條件的推出相關結論 3 假設證明法的模式構造 解法二 假設證法 1 A B2 C D3 A C B D4 B 假設 4 D 假設 5 A 1 4 銷去 5 C 2 4 銷去 6 C 3 5 銷去 6 A 4 5 銷去 7 D 2 6 銷去 7 B 1 6 銷去 8 B D 4 7 引入 8 D B 4 7 引入 9 B D 8 等值 9 D B 8 等值 證畢 10 B D 9 交換 證畢 三 反證法 1 反證法的特點認知前提不夠 需要附加 附加與結論相矛盾的命題作為假設依據規(guī)則進行推導尋求矛盾 找到矛盾后利用否定引入或銷去規(guī)則反證結論成立 2 反證法的模式構造 解法三 反證法 1 A B2 C D3 A C B D4 B D 反設 5 B D 4 等值 6 B 5 銷去 7 A 1 6 銷去 8 C 3 7 銷去 9 D 2 8 銷去 10 D 5 銷去 11 D D 9 10 引入 12 B D 4 11 銷去 證畢 假設證明法與反證法的區(qū)別與綜合應用 一 假設證明法與反證法的區(qū)別二 假設證明法與反證法的綜合應用1 在證明中的綜合應用 例析4301 2 在推理中的綜合應用 4302 三 命題邏輯定理的證明 p q p qpqp q p q p p q p qTTTTTTFFFTFTTFTFFTFT 畫一個完全真值表 實例分析2 pqp pq qp qTTTFTTFTFTFTTFTFFTFF永真式永假式可真式 實例分析3 判斷3p q p q p q的真假關系 pqp q p qp qTTTTFTFFFTFTTTFFFTTF 等值 矛盾 實例分析4 用歸謬賦值法判定 p q q P這個推理是否有效 p q q PFTFTTTFTT 由上表可知 q的賦值出現矛盾 此命題形式是重言式 與之相對應的推理形式是有效式 運用歸謬賦值法要注意 由于給變項賦值過程中有先后的不同 因而具體矛盾的出現可能不同 只有當賦值過程中矛盾不可避免的出現時 才能表明原公式是重言式 相應的推理有效 賦值過程中 變項的值有時候不能惟一的確定 此時需要討論 返回 1 A B2 B C3 C D4 D A5 C 3 4 銷去 6 B 2 5 銷去 7 A 1 6 銷去 證畢 直接證明法 實例分析一 直接證法 實例分析二 1 A B C2 C D3 B D A4 D 2 銷去 5 C 2 銷去 6 B 3 4 銷去 7 A B 1 5 銷去 8 A B 7 等值 9 A 6 8 銷去 證畢 回溯思考方法1 A B C 2 A D3 C E F 4 D F E 1 回溯 思考 首先要考察待證結論與前提的關聯(lián)性 待證結論處在 命題的后件 要獲證必須基于對前件C的肯定 2 C與前提1關聯(lián) 要獲取必須基于主聯(lián)結關系 的銷去 3 前提1的 銷去 取決于對前提2中條件A的否定 4 要獲取對A的否定 必須基于對后件D的否定 而后件D的否定處在前提4之中 要獲取 D必先分解前提4 直接證明法 推導結論 1 B D 2 C D3 A B4 E F C5 A F6 A 5 銷去 7 B 3 6 銷去 8 B D 1 7 等值 9 D 7 8 銷去 10 C 2 9 銷去 11 E F 4 10 銷去 12 E F 11 等值 13 F 5 銷去 14 E 12 13 銷去 直接證明法前提一致性判定 1 A B2 B C3 D C4 A D5 D6 C7 B8 A9 A10 A A 直接證明法前提一致性判定之02 1 A B2 B C3 D C4 A D5 A6 B7 C8 D 假設證明法的模式構造 1 給定前提2 3 p q4 p 假設 10 q11 p q 4 10 引入 1 B A2 B A C A C3 A 假設 4 B 1 3 銷去 5 A C 2 4 銷去 6 C 5 銷去 A C 3 6 引入 證畢 假設證明法 實例分析一 1 A C2 C E H I 3 F I A F E 4 A 假設 5 C 1 4 銷去 6 E H I 2 5 銷去 7 F 假設 8 I 3 7 銷去 9 I H 8 引入 10 H I 9 交換 11 H I 10 等值 12 E 6 11 銷去 13 F E 7 12 引入 14 A F E 4 13 引入 證畢 假設證明法 實例分析二 反證法的模式構造 1 2 p p 反設 9 q q10 p 4 9 銷去 證畢 1 2 3 p4 P 反設 9 q q10 p 4 9 引入 證畢 1 A B2 C B3 A C A4 A C 3 等值 5 A 反設 6 B 1 5 銷去 7 C 2 6 銷去 8 C 4 5 銷去 9 C C 7 8 引入 10 A 5 9 引入 證畢 反證法 實例分析一 在證明中的綜合應用 1 A B C2 A B C B C3 C 假設 4 A B 2 3 銷去 5 A B 4 等值 6 A B 1 3 銷去 7 B 反設 8 A 5 7 銷去 9 A 6 7 銷去 10 A A 8 9 引入 11 B 7 10 銷去 12 C B 3 11 引入 13 C B 12 等值 14 B C 13 交換 證畢 在推理中的綜合應用 1 A B C2 B D A C 3 B A C D 4 B C A5 B 假設 6 C 反設 7 B C 5 6 引入 8 A 4 7 銷去 9 B A 5 8 引入 10 C D 3 9 銷去 11 D 6 10 銷去 12 B D 5 11 引入 13 A C 2 12 銷去 14 A 8 13 銷去 15 A A 8 14 引入 16 C 6 15 銷去 17 B C 5 16 引入