第三章：邏輯公式
在前一章中，我們討論了如何證明命題。現在我們需要一種精確的語言來描述複雜的命題，這就是邏輯公式。
3.1 從命題到命題
我們可以使用邏輯連接詞從簡單命題構建複雜命題：
- NOT (¬): 否定，將真變假，假變真。
- AND (∧): 合取，兩者皆真才為真。
- OR (∨): 析取，兩者至少一者為真即為真。
- XOR (⊕): 異或，兩者真假不同時為真。
3.3 蘊含與等價
蘊含
"P 蘊含 Q" (P IMPLIES Q)，寫作 P → Q。
其定義為：當 P 為真且 Q 為假時，整個敘述為假；其餘情況皆為真。
"P 蘊含 Q" (P IMPLIES Q)，寫作 P → Q。
其定義為：當 P 為真且 Q 為假時，整個敘述為假；其餘情況皆為真。
這是一個反直覺的概念："假命題蘊含任何命題"。這意味著如果 P 是假的，那麼 P → Q 總是真的（空真）。
🧪 互動真值表計算器
點擊下方的開關來切換 P 和 Q 的真假值，觀察結果如何變化：
True
True
P → Q : TRUE
| P | Q | P → Q | 解釋 |
|---|---|---|---|
| T | T | T | 條件符合，結論成立 |
| T | F | F | 條件符合，但結論不成立 (唯一為假) |
| F | T | T | 前提為假，空真 |
| F | F | T | 前提為假，空真 |
註：高亮的那一行對應當前開關選擇的狀態。
3.5 SAT 問題挑戰
SAT (Boolean Satisfiability Problem) 問題是問：是否存在一組變數賦值，使得給定的邏輯公式為真？
這是一個 NP-完全問題，但在這裡我們來玩一個簡單的版本：
公式：
(P ∨ Q) ∧ (¬P ∨ ¬Q)
你的任務：
找到一組 P 和 Q 的值，使公式結果為 TRUE。
結果：FALSE (未滿足)
提示：P 和 Q 的狀態需要不同 (一真一假)。
3.6 謂詞公式
當我們需要表達「對所有 x...」或「存在一個 x...」時，我們需要使用量詞。
- ∀x. P(x): 對於所有的 x，P(x) 都成立。（全稱量詞）
- ∃x. P(x): 存在一個 x，使得 P(x) 成立。（存在量詞）
例如："每個人都愛某人" 可以表示為：
∀x ∃y. Loves(x, y)
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)