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

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