離散數(shù)學-命題邏輯.ppt

《離散數(shù)學-命題邏輯.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學-命題邏輯.ppt（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第一章數(shù)理邏輯 一命題邏輯命題及其表示法聯(lián)結(jié)詞命題公式與翻譯真值表與等價式等價式與蘊含式對偶與范式推理理論 二謂詞邏輯謂詞的概念與表示命題函數(shù)與量詞謂詞公式與翻譯變元的約束謂詞演算的等價式與蘊含式前束范式謂詞演算的推理理論本章作業(yè) 真值表與等價公式 定義1 4 1在命題公式中 對于分量指派真值的各種可能組合 就確定了這個命題公式的各種真值情況 把它匯列成表 就是命題公式的真值表 例1構(gòu)造 P Q的真值表 例2給出 P Q P的真值表 例3給出 P Q P Q 的真值表 例4給出 P Q P Q 的真值表 等價式和蘊涵式 一 幾個定義與定理定義1 5 1給定一命題公式 若無論對分量作怎樣的指派 其對應的真值永為T 則稱該命題公式為重言式或永真公式 定義1 5 2給定一命題公式 若無論對分量作怎樣的指派 其對應的真值永為F 則稱該命題公式為矛盾式或永假公式 定理1 5 1任何兩個重言式的合取或析取 仍然是一個重言式 證明 設(shè)A和B為兩個重言式 則不論A和B的分量指派任何真值 總有A為T B為T 故A B T A B T 定理 一個重言式 對同一分量都用任何合式公式置換 其結(jié)果仍為一個重言式 證明 由于重言式的真值與分量的指派無關(guān) 故對同一分量以任何合式公式置換后 重言式的真值仍永為T 定義1 4 2給定兩個命題公式A和B 設(shè)P1 P2 Pn為所有出現(xiàn)于A和B中的原子變元 若給P1 P2 Pn任一組真值指派 A和B的真值都相同 則稱A和B是等價的或邏輯相等 記作A B 例5證明P Q P Q Q P 定理 設(shè)A B為兩個命題公式 A B當且僅當A B為一個重言式 等價式 下表列出的命題定律 都可以用真值表予以驗證 補充 其它常用等價公式 1 P Q P Q 2 P Q P Q Q P P Q 3 P Q P Q P 歸繆論 4 P Q Q P 逆反式 我們稱Q P為逆換式 稱 P Q為反換式定義1 4 3如果X是合式公式A的一部分 且X本身也是一個合式公式 則稱X為公式A的子公式 定理1 4 1設(shè)X是合式公式A的子公式 若X Y 如果將A中的X用Y來置換 所得到的公式B與公式A等價 即A B 證明 因為在相應變元的任一種指派情況下 X與Y的真值相同 故以Y取代X后 公式B與公式A在相應的指派情況下 其真值亦必相同 故A B 注 滿足定理1 4 1條件的置換稱為等價置換 等價代換 例題7證明Q P P Q Q P例題8證明 P Q P Q P例題9證明P Q R Q P R R Q P 例題10證明 P Q P Q R P Q P R T 下一節(jié) 例7證明設(shè)A 因為故B 即例8證明 例9證明又 例10證明原式左邊 例1解 例2解 例3解 例4解 例5解 定義 當且僅當P Q是一個重言式時 我們稱 P蘊含Q 并記作P Q 注意 區(qū)別條件與蘊含 同時 二者存在聯(lián)系 定理 設(shè)P Q為任意兩個命題公式 P Q的充分必要條件是P Q且Q P 證明 若P Q 則P Q為重言式 因為P Q P Q Q P 故P Q為T且Q P為T 即P Q Q P成立 反之 若P Q且Q P 則P Q為T且Q P為T 因此P Q為T P Q是重言式 即P Q 證畢 蘊含式 二 蘊含有下面幾個常用的性質(zhì) 1 設(shè)A B C為合式公式 若A B且A是重言式 則B必是重言式 2 若A B B C 則A C 即蘊含關(guān)系是傳遞的 3 若A B且A C 那么A B C 4 若A B且C B 則A C B 三 下表所列各蘊含式都可推理證明 重言式 等價式與蘊涵式的證明 例題1證明 P S R P S R 為重言式 例題2證明 P Q P Q 例題3推證 Q P Q P BACK 例題1證明因為P P T 如以 P S R 置換P即得 P S R P S R T例題2證明由上節(jié)例題4表可知 P Q P Q 為重言式 故根據(jù)定理1 5 3 P Q P Q 例題3證法1假定 Q P Q 為T 則 Q為T 且 P Q 為T 由Q為F P Q為T 則必須P為F 故 P為T 證法2假定 P為F 則P為T A 若Q為F 則P Q為F Q P Q 為F B 若Q為T 則 Q為F Q P Q 為F 所以 Q P Q P成立