第一章命題邏輯備選.ppt

1命題 例 判斷下列語句是否為命題 陳述句一般為命題 1 十是整數(shù) 2 上海是一個(gè)村莊 3 今天下雨 4 加拿大是一個(gè)國家 5 是偶數(shù)而 是奇數(shù) 6 她不是護(hù)士 7 8 今天是星期天 1命題 命令句 感嘆句 疑問句均不是命題 1 把門關(guān)上 2 你到哪里去 語句既為真 同時(shí)又包含假的不是命題 這樣的句子稱為 悖論 3 他正在說謊 在命題邏輯中不討論這類問題 2命題聯(lián)結(jié)詞 例 將下列命題符號化 1 李明是計(jì)算機(jī)系的學(xué)生 他住在312室或313室 2 張三和李四是朋友 3 雖然交通堵塞 但是老王還是準(zhǔn)時(shí)到達(dá)了車站 4 只有一個(gè)角是直角的三角形才是直角三角形 5 老王或小李中有一個(gè)去上海出差 2命題聯(lián)結(jié)詞 解 1 首先用字母表示簡單命題 P 李明是計(jì)算機(jī)系的學(xué)生 Q 李明住在312室 R 李明住在313室 該命題符號化為 P Q R 2 張三和李四是朋友 是一個(gè)簡單句該命題符號化為 P 2命題聯(lián)結(jié)詞 3 首先用字母表示簡單命題 P 交通堵塞 Q 老王準(zhǔn)時(shí)到達(dá)了車站 該命題符號化為 P Q 4 首先用字母表示簡單命題 P 三角形的一個(gè)角是直角 Q 三角形是直角三角形 該命題符號化為 P Q 2命題聯(lián)結(jié)詞 5 首先用字母表示簡單命題 P 老王去上海出差 Q 小李去上海出差 該命題符號化為 P Q也可符號化為 P Q P Q 或者 P Q P Q 命題公式 例 構(gòu)造命題公式 的真值表 命題公式 例 寫出命題公式 的真值表 例 證明 例 證明 為一永真式 4等價(jià)式 證明 原式 它是 永真式 的代換實(shí)例 永真式的代換實(shí)例仍為永真式 4等價(jià)式 證明 原式 它是 永真式 的代換實(shí)例 永真式的代換實(shí)例仍為永真式 4等價(jià)式 例 證明 證明 左邊 4等價(jià)式 左邊 結(jié)論 和 是互為對偶的 7范式和判定 例 證明 證明方法是寫出二個(gè)命題公式的主析范式 看其是否相同 而 主析范式相同 有 8推理理論 例1 P Q S R P Q R S證 1 R附加前提 2 R PP 3 R PT 2 E 4 PT 1 3 I 5 P Q S P 6 Q ST 4 5 I 8推理理論 7 QP 8 ST 6 7 I 9 R SCP例2 P Q P P Q 1 P附加前提 2 P QP 3 QT 1 2 I 4 P QT 1 3 5 P P Q CP 8推理理論 例 證明 P Q P Q 證 1 P Q 假設(shè)前提 2 P QT 1 3 PT 2 4 P QP 5 PT 4 6 P PT 3 5 7 F 8推理理論 例2 證明 R Q R S S Q P Q P 1 P 假設(shè)前提 2 PT 1 3 P QP 4 QT 2 3 5 S QP 6 Q ST 5 7 ST 4 6 8 R SP 9 RT 7 8 8推理理論 10 R QP 11 QT 9 10 12 Q QT 4 11 討論 由上例可見 間接證明法在結(jié)論較為簡單的條件下 使用是比較方便的 實(shí)際上間接證明法也可以用CP規(guī)則代替它 8推理理論 例 一位計(jì)算機(jī)工作者協(xié)助公安人員審查一起謀殺案 經(jīng)調(diào)查 他認(rèn)為下列情況均是真的 1 會計(jì)張某或鄰居王某謀害了廠長 2 如果會計(jì)張某謀害了廠長 則謀害不可能發(fā)生在半夜 3 如果鄰居王某的證詞不正確 則在半夜時(shí)房里燈光未滅 4 如果鄰居王某的證詞是正確的 則謀害發(fā)生在半夜 5 在半夜房子里的燈光滅了 且會計(jì)張某曾貪污過 8推理理論 解 設(shè)P 會計(jì)張某謀害了廠長Q 鄰居王某謀害了廠長N 謀害發(fā)生在半夜O 鄰居王某的證詞是正確的R 半夜時(shí)房子的燈光滅了A 會計(jì)張某曾貪污過列出條件公式 8推理理論 1 P Q 4 Q N 2 P N 5 R A 3 O R推導(dǎo)過程為 1 R AP 6 NT 2 RT 7 P NP 3 O RP 8 PT 4 OT 9 P QP 5 O RP 10 QT結(jié)論 鄰居王某謀害了廠長 例題選講 例1 符號化下列命題 1 辱罵和恐嚇決不是戰(zhàn)斗 2 除非天氣好 否則我是不會去公園的 3 如果晚上做完作業(yè)且沒有其它的事 他就會去看電視或聽音樂 解 1 設(shè)P 辱罵不是戰(zhàn)斗 Q 恐嚇不是戰(zhàn)斗 P Q 2 設(shè)P 今天天氣好 Q 我去公園 Q P 例題選講 3 設(shè)P 他晚上做完了作業(yè) Q 他晚上沒有其它事情 R 他看電視 S 他聽音樂 P Q R S 例2 證明P Q R P Q P R 給出本題的各種證明 1 列真值表 設(shè)M P Q R K P Q P R S P Q R P Q P R 例題選講 例題選講 a 直接證法 P Q R 的真值為T 其對應(yīng)指派下 P Q P R 的真值均為T b 反證法 P Q P R 的真值為F 其對應(yīng)指派下P Q R 的真值為F c 條件永真式 P Q R P Q P R 的真值都為T 及為永真式 2 邏輯推證a 直接證法 設(shè)P Q R 為T 則 P為T Q R為T 有三種情況 P為T Q為T R為T 則 P Q P R 為T 例題選講 P為T Q為F R為T 則 P Q P R 為T P為T Q為F R為F 則 P Q P R 為T P為F Q R為F 則 P為F Q為T R為F 所以P Q為T P R為T 得 P Q P R 為T P為F Q R為T 則 P為F Q為T R為T 則 P Q P R 為T P為F Q為F R為F 則 P Q P R 為T P為F Q為F R為T 則 P Q P R 為T 綜上各點(diǎn) 當(dāng)P Q R 為T時(shí) 必有 P Q P R 為T 例題選講 b 間接證法 設(shè) P Q P R 為F 則必有P Q為T P R為F 故得P為T Q為T R為F 所以P Q R 為F 3 等價(jià)變換S P Q R P Q P R P Q R P Q P R P Q R P Q P R P Q R P Q P R P Q R P R P Q P R P Q R P Q R P Q R P Q R T 例題選講 例3 證明 不是最小聯(lián)結(jié)詞組 證明 設(shè)變元P Q 用聯(lián)結(jié)詞 作用于P Q得到 P Q P Q P Q P P Q Q Q P 但 P Q Q P P P Q Q 故實(shí)際有 P Q P Q P Q P P T A 用 作用于 A 類 得到擴(kuò)大的公式類 包括原公式類 P Q P Q P Q P Q T F B 用 作用于 A 類得到 P Q P P F P Q P Q P P Q Q P P P P Q P P Q Q Q F Q P Q P Q T Q 例題選講 P Q P Q P P Q Q P T P Q P Q P Q T Q P Q P P P Q 因此 A 類使用 運(yùn)算后 仍在 B 類中 同樣 對 B 類使用 運(yùn)算后 結(jié)果仍在 B 中 由上證明 用 兩個(gè)聯(lián)結(jié)詞 反復(fù)作用在兩個(gè)變元的公式中 結(jié)果只能產(chǎn)生 B 類中的公式 總共僅八個(gè)不同公式 而兩個(gè)變元所形成的公式共有222 16個(gè)彼此不等價(jià)的公式 因此 不是功能完備的 更不可能是最小聯(lián)結(jié)詞組 例題選講 例4 求 A B C A B C 的主析取范式與主合取范式 解 1 列表法 設(shè)S A B C A B C R A B C M A B C 根據(jù)真值表中S真值為T的指派 所對應(yīng)的小項(xiàng)析取即為S的主析取范式 S真值為F的指派 所對應(yīng)的大項(xiàng)合取即為主合取范式 S的真值表如下 例題選講 例題選講 S A B C A B C 主析取范式S A B C A B C A B C A B C A B C A B C 主合取范式 2 公式推導(dǎo)法 S A B C A B C A B C A B C B C A A B C A B C B C A A B C A B C B C A A B C A B C m000 m111 0 7 例題選講 當(dāng)求出主析取范式的編碼表達(dá)式后可直接利用編碼關(guān)系 解出主合取范式 即 S A B C A B C A B C A B C m000 m111 0 7 1 2 3 4 5 6 M001 M010 M011 M100 M100 M101 M110 A B C A B C A B C A B C A B C A B C 例題選講 例5 用推理規(guī)則論證下述問題 或者是天晴 或者是下雨 如果是天晴 我去看電影 如果我去看電影 我就不看書 所以 如果我在看書 則天在下雨 解 設(shè)S 今天天晴 R 今天下雨 E 我去看電影 B 我去看書 本題符號化為 S R S E E B B R因?yàn)镾 R S R 故本題為 S R S E E B B R 例題選講 直接證法 1 S R P 2 S RT 1 E 3 S R R S T 2 E 4 R ST 3 I 5 S EP 6 R ET 4 5 I 7 E BP 8 R BT 6 7 I 9 B RT 8 E 例題選講 間接證法 a 1 S R P 2 S RT 1 3 S R R S T 2 4 R ST 3 5 B R P 附加前提 6 B RT 5 7 BT