命题演算（又名：Propositional Logic 命题逻辑，有的时候也称为 Zeroth-Order Logic 零阶逻辑）
1.1 Propositional Connectives: Truth Tables
命题联接词可以由真值表表达
\[ \begin{array} {c c c c c c c} & & Negation & Conjunction & Disjunction & Conditional & Biconditional \\ A & B & \neg A & A \wedge B & A \vee B & A \Rightarrow B & A \Leftrightarrow B \\ T & T & F & T & T & T & T \\ F & T & T & F & T & T & F \\ T & F & F & F & T & F & F \\ F & F & T & F & F & T & T \\ \end{array} \]
其中 \(A\Rightarrow{B}\)，唯有当 \(A\) 是 \(T\) 而 \(B\) 是 \(F\) 时这个式子是明确地不成立，其余情况都设置为成立1
- Statement form
-
- 所有 statement letters 以及带数字下标（诸如 \(A, B, C, A_1, A_2\)）的都是 statement form
- 由上述联接词（\(\neg \wedge \vee \Rightarrow \Leftrightarrow\)）联接的 statement form 也是 statement form
- 只有由 1/2 产生的才是 statement form
1.2 Tautologies
- Tautology
- 如果一个 statement form 无论其中的 statement letters 如何取值，其结果都为真时， 则称该 statement form 为重言式（又名：恒真式）
- Logically imply
- \(B\) 和 \(C\) 均为 statement form，假如对于每一种能令 \(B\) 为真的 statement letters 的取值组合， 也能让 \(C\) 得到真值，则 \(B\) 逻辑蕴含 \(C\)
- Logically equivalent
- 假如对于每一种 statement letters 的取值组合，\(B\) 和 \(C\) 这两个 statement form 的值都是一样的话， 则它们两者逻辑等价
Proposition 1.1
\(B\) 蕴含 \(C\) 当且仅当 \(B \Rightarrow C\) 是一个重言式
若 \(B\) 蕴含 \(C\)，则任意 statement letters 的取值不可能出现 \(B\) 为真而 \(C\) 为假，故 \(B \Rightarrow C\) 总是为真；反之若 \(B \Rightarrow C\) 是重言式，则不存在一个 statement letters 的取值使得 \(B\) 为真而 \(C\) 为假，故蕴含成立
\(B\) 等价 \(C\) 当且仅当 \(B \Leftrightarrow C\) 是一个重言式
Proposition 1.2
假如 \(B\) 和 \(B \Rightarrow C\) 都是重言式，则 \(C\) 也是
若前者成立，则 statement letters 的任意取值下\(B\) 和 \(B \Rightarrow C\) 为真， 此时若 \(C\) 为假会矛盾，故 \(C\) 为真，所以也是重言式
Proposition 1.3
假如 \(T\) 是一个包含了 \(A_1, A_2, ... A_n\) 的重言式，用任意 statement forms \(T_1, T_2, ... T_n\) 一一对应地替换这些 statement letters 仍然会得到一个重言式
Proposition 1.4
假如 \(T_C\) 中有一个或多个 \(C\)，将 \(C\) 全部替换成 \(B\) 得到 \(T_B\), 则 \((B \Leftrightarrow C) \Rightarrow (T_B \Leftrightarrow T_C)\) 是重言式
1.3 Adequate Sets of Connectives
每一个包含 \(n\) 个 statement letters 的 statement form 生成一个有 \(n\) 个参数的真值函数， 即 \(f(x_1, x_2, ..., x_n), x_i \in \{T, F\}\)， 逻辑等价的 statement form 生成相同的真值函数
Proposition 1.5
每一个真值函数可以仅由只包含 \(\neg\wedge\vee\) 联接词的 statement form 生成 2
由以下例子说明
\[ \frac{ \begin{array} {c c c c c} x_1 & x_2 & f(x_1, x_2) & i & C_i \\ T & T & F & 1 & \\ F & T & T & 2 & \neg A_1 \wedge A_2 \\ T & F & T & 3 & A_1 \wedge \neg A_2 \\ F & F & T & 4 & \neg A_1 \wedge \neg A_2 \\ \end{array} }{D=C_2 \vee C_3 \vee C_4=(\neg A_1 \wedge A_2) \vee (A_1 \wedge \neg A_2) \vee (\neg A_1 \wedge \neg A_2)} \]
有 \(n\) 个参数的真值函数可以由 \(2^n\) 行真值表表达，（如上 \(n=2\) 则有 4 行）， 对于每一行 \(i\)：如果 \(f_i\) 取值为真，则令 \(C_i=U_1^i \wedge U_2^i \wedge ... \wedge U_n^i\)， 其中若 \(x_j\) 为真则 \(U_j^i=A_j^i\)，否则 \(U_j^i=\neg A_j^i\)； 最后令 \(D\) 为所有这些 \(C_i\) 的 disjunction。
假如 \(f_i\) 均为非真，则直接取 \(D=A_1 \wedge \neg A_1\)。
很容易验证 \(D\) 的真值函数就是 \(f\)：任何一个参数取值组合能令真值表对应行的 \(C_i\) （如果有的话）取 \(T\)，而 其他 \(C_i\) 均取 \(F\)；\(D\) 是这些 \(C_i\) 的 disjunction，因此只要该参数取值组合对应行有 \(C_i\)，也就是 \(f_i\) 为真的时候， 其取值为 \(T\)
而 \(D\) 仅仅包含 \(\neg\wedge\vee\) 联接词
Corollary 1.6
更进一步，每一个真值函数都可以仅包含 \(\neg\wedge\) 或 \(\neg\vee\) 或 \(\neg\Rightarrow\) 联结词的 statement form 生成
\(B \vee C\) 逻辑等价于 \(\neg (\neg B \wedge \neg C)\)，因此将 Proposition 1.5 里 \(D\) 中的 disjunction 联接词替换掉就能得出仅仅使用 \(\neg\wedge\) 的等价 statement form 了；其余两个证明类似
更更进一步，定义两种新的联结词
\[ \begin{array} {c c c c} & & Joint Denial & Alternative Denial \\ A & B & A \downarrow B & A | B \\ T & T & F & F \\ F & T & F & T \\ T & F & F & T \\ F & F & T & T \\ \end{array} \]
而 \(\neg A \Leftrightarrow (A \downarrow A)\) 和 \((A \wedge B) \Leftrightarrow ((A \downarrow A) \downarrow (B \downarrow B))\) 均是重言式
\(\neg A \Leftrightarrow (A|A)\) 和 \((A \vee A) \Leftrightarrow ((A|A)|(B|B))\) 也均是重言式
因此只需要以上任意一个就可以生成任意的真值函数了
Proposition 1.7
\(\downarrow |\) 是唯二两种能单独构建所有真值函数的二元联结词