Chapter 1: The Propositional Calculus (1.5~1.6)

A1 独立的证明

考虑下面这个多值逻辑表

\[ \begin{array} {c c c} A & \neg A & row \\ 0 & 1 & (a)\\ 1 & 1 & (b) \\ 2 & 0 & (c) \\ \end{array} \hspace{8em} \begin{array} {c c c c} A & B & A \Rightarrow B & row \\ 0 & 0 & 0 & (1) \\ 1 & 0 & 2 & (2) \\ 2 & 0 & 0 & (3) \\ 0 & 1 & 2 & (4) \\ 1 & 1 & 2 & (5) \\ 2 & 1 & 0 & (6) \\ 0 & 2 & 2 & (7) \\ 1 & 2 & 0 & (8) \\ 2 & 2 & 0 & (9) \\ \end{array} \]

一个合式公式 \(A\) ，如果其 statement letters 无论取何种取值组合，最终其值（按上述表）都取值 0，则称之为 select （类似重言式）

首先 MP 是保持 selectness 的，这是因为如果 \(A\) 和 \(A \Rightarrow B\) 都是 select 的话，则 \(B\) 也必然是 select 的（见上表，假设某种取值组合下 \(B\) 是非 0，由于 \(A\) 是 select 的因此总是取 0，寻找 \(A\) 是 0 而 \(B\) 非 0 的行只有 (4)/(7) 两行，而其结果均非 0，这与 \(A \Rightarrow B\) 是 select 矛盾，故 \(B\) 只能为 0，也就是也是 select 的）

接下来 A2/A3 均是 select 的：

注意到 \(\Rightarrow\) 链接符的结果只有 0/2 两种可能值，要想 A2 非 0，则只有第 (7) 行这种可能， 即 \(B \Rightarrow (C \Rightarrow D)\) 为 0，\((B \Rightarrow C) \Rightarrow (B \Rightarrow D)\) 为 2，同理后者推出 \(B \Rightarrow C\) 为 0, \(B \Rightarrow D\) 为 2，根据上表，\(B \Rightarrow D\) 为 2 有如下可能：

• row (2) \(B = 1, D = 0\)，要 \(B \Rightarrow C\) 为 0，则 \(C = 2\)，得出 \(B \Rightarrow (C \Rightarrow D) = 2\) 矛盾
• row (4) \(B = 0, D = 1\)，要 \(B \Rightarrow C\) 为 0，则 \(C = 0\)，得出 \(B \Rightarrow (C \Rightarrow D) = 2\) 矛盾
• row (5) \(B = 1, D = 1\)，要 \(B \Rightarrow C\) 为 0，则 \(C = 2\)，得出 \(B \Rightarrow (C \Rightarrow D) = 2\) 矛盾
• row (7) \(B = 0, D = 2\)，要 \(B \Rightarrow C\) 为 0，则 \(C = 0\)，得出 \(B \Rightarrow (C \Rightarrow D) = 2\) 矛盾

同样地，要想 A3 非 0，则 \(\neg C \Rightarrow \neg B\) 为 0，\((\neg C \Rightarrow B) \Rightarrow C\) 为 2，后者推出 \(\neg C \Rightarrow B\) 为 0，\(C\) 为 2，因此 \(\neg C\) 为 0，导致 \(B\) 和 \(\neg B\) 均为 0，与上表矛盾

又 A1 是不 select 的：\(1 \Rightarrow (2 \Rightarrow 1) = 2\)，故 \(A2, A3 \nvdash A1\)，因为如果可以则 A1 也是 select 才对

A2 独立的证明

考虑下面这个多值逻辑表

\[ \begin{array} {c c c} A & \neg A & row \\ 0 & 1 & (a)\\ 1 & 0 & (b) \\ 2 & 1 & (c) \\ \end{array} \hspace{8em} \begin{array} {c c c c} A & B & A \Rightarrow B & row \\ 0 & 0 & 0 & (1) \\ 1 & 0 & 0 & (2) \\ 2 & 0 & 0 & (3) \\ 0 & 1 & 2 & (4) \\ 1 & 1 & 2 & (5) \\ 2 & 1 & 0 & (6) \\ 0 & 2 & 1 & (7) \\ 1 & 2 & 0 & (8) \\ 2 & 2 & 0 & (9) \\ \end{array} \]

类似于上面， 一个合式公式 \(A\) ，如果其 statement letters 无论取何种取值组合，最终其值（按上述表）都取值 0，则称之为 grotesque 的

首先 MP 是保持 grotesqueness 的，又 A1/A3 也是 grotesque 的（不再详细验证了），最后 \((0 \Rightarrow (0 \Rightarrow 1)) \Rightarrow ((0 \Rightarrow 0) \Rightarrow (0 \Rightarrow 1)) = 2\) 所以 A2 不是 grotesque 的

故 \(A1, A3 \nvdash A2\)

A3 独立的证明

令 \(h(B)\) 为将合式公式 \(B\) 中所有 \(\neg\) 擦除之后的式子，如果 \(h(B)\) 是重言式，称 \(B\) 是 super 的；显然 A1/A2 都是 super 的 （因为都没有 \(\neg\) 符号）；再有 MP 是保持 superness 的，因为如果 \(h(B \Rightarrow C)\) 和 \(h(B)\) 是重言式，则 \(h(C)\) 也是 （因为 \(h(B \Rightarrow C) = h(B) \Rightarrow h(C)\)，根据 Proposition 1.2 \(h(C)\) 也是重言式），但 \(h(A3) = (C \Rightarrow B) \Rightarrow ((C \Rightarrow B) \Rightarrow C)\) 并不是重言式（令 \(C = F\) 以及 \(B = F\) 可知），

故 \(A1, A2 \nvdash A3\)

我想用多值逻辑其实也可以证明 A3 的独立性

其实就是 Exercises 1.51（不过书中的答案更简洁），方法同上面：构造一个多值逻辑的真值表， 使得 A1/A2 总是取值 0，MP 也保持这种特性，而 A3 不总是取值 0 即可

首先如果合式公式 \(A \Rightarrow B\) 和 \(A\) 总是 0，要使得 \(B\) 也总是 0 的话，则表必须满足下面的要求 \[ \begin{array} {c c c c} A & B & A \Rightarrow B & row \\ 0 & 0 & 0 & (1) \\ 1 & 0 & & (2) \\ 2 & 0 & & (3) \\ 0 & 1 & \neq 0 & (4) \\ 1 & 1 & & (5) \\ 2 & 1 & & (6) \\ 0 & 2 & \neq 0 & (7) \\ 1 & 2 & & (8) \\ 2 & 2 & & (9) \\ \end{array} \]

例如为使得尽量容易出现 0，其他位置都填上 0

\[ \begin{array} {c c c c} A & B & A \Rightarrow B & row \\ 0 & 0 & 0 & (1) \\ 1 & 0 & 0 & (2) \\ 2 & 0 & 0 & (3) \\ 0 & 1 & 1 & (4) \\ 1 & 1 & 0 & (5) \\ 2 & 1 & 0 & (6) \\ 0 & 2 & 2 & (7) \\ 1 & 2 & 0 & (8) \\ 2 & 2 & 0 & (9) \\ \end{array} \]

容易验证上表对于 A1/A2 来说总是 0 的

最后我们构造一个 \(\neg\) 表使得 A3 不总是 0，例如

\[ \begin{array} {c c} A & \neg A \\ 0 & 1 \\ 1 & 0 \\ 2 & 1 \\ \end{array} \]

若 \(B = 1, C = 2\) 则 \((\neg 2 \Rightarrow \neg 1) \Rightarrow ((\neg 2 \Rightarrow 1) \Rightarrow 2) = 0 \Rightarrow (0 \Rightarrow 2) = 2\)