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