命題邏輯與真值表

命題邏輯 (propositional logic) 把敘述當成真/假的變數,用連接詞組合:$\lnot$(非)、$\land$(且)、$\lor$(或)、$\to$(若則)、$\leftrightarrow$(若且唯若)。真值表 (truth table) 列出所有輸入組合的結果,$n$ 個變數有 $2^n$ 列。

最容易搞錯的是蘊含:$p\to q$ 只有 $p$ 真 $q$ 假時為假;$p$ 假時整句恆真(空虛的真)。所以 $p\to q\equiv\lnot p\lor q$,否定是 $p\land\lnot q$。逆否命題 $\lnot q\to\lnot p$ 與原命題等價,逆命題 $q\to p$ 不等價。

De Morgan 定律:$\lnot(p\land q)\equiv\lnot p\lor\lnot q$、$\lnot(p\lor q)\equiv\lnot p\land\lnot q$——否定穿過括號時 $\land$、$\lor$ 互換。

這是數位電路(AND/OR/NOT 閘)、程式條件判斷、SQL 查詢、數學證明結構的共同語言。