Chapter 4 Problems

标签：Chapter neg Problems vdash mathscr quad aligned rightarrow

T1

证明\(\neg A\rightarrow B, \neg A\rightarrow \neg B \vdash A\)

可用定理：\(\vdash (\neg A\rightarrow A)\rightarrow A\)

Proof

\[\begin{aligned} A_1:\quad &\neg A\rightarrow B & \in \Gamma \\ A_2:\quad &\neg A\rightarrow \neg B & \in \Gamma \\ A_3:\quad &(\neg A\rightarrow \neg B)\rightarrow(B\rightarrow A) & \mathscr A_3\\ A_4:\quad & B\rightarrow A & A_2, A_3 \vdash A_4 \\ A_5:\quad & (B\rightarrow A)\rightarrow( \neg A \rightarrow (B\rightarrow A)) & \mathscr A_1\\ A_6:\quad & \neg A \rightarrow (B\rightarrow A) & A_4, A_5 \vdash A_6 \\ A_7:\quad & (\neg A \rightarrow (B\rightarrow A))\rightarrow\\ &((\neg A \rightarrow B)\rightarrow (\neg A\rightarrow A)) & \mathscr A_2\\ A_8:\quad & (\neg A \rightarrow B)\rightarrow (\neg A\rightarrow A) & A_6, A_7 \vdash A_8 \\ A_9:\quad & \neg A\rightarrow A & A_1, A_8 \vdash A_9 \\ A_{10}:\quad & (\neg A\rightarrow A)\rightarrow A & \vdash (\neg A\rightarrow A)\rightarrow A \\ A_{11}:\quad & A & A_9, A_{10} \vdash A_{11} \end{aligned} \]

T2

根据证明长度归纳，分类讨论证明

\[\text若 C,A\vdash B \text 则 C\vdash A\rightarrow B \]

其中，\(B\)符合以下四种情形之一：

1. \(B\)是公理；

2. \(B\)是\(C\)；

3. \(B\)是\(A\)；

4. \(C,A\vdash B\)的证明序列中\(B\)由合式公式\(Q\)、\(Q\rightarrow B\)通过MP规则得到

Proof

本题提供了一种把「使用演绎定理构造的证明」转化为「普通证明」的方法

• 情形1：此时有\(C\vdash B\)

\[\begin{aligned} C \vdash &B\\ C \vdash &B\rightarrow (A\rightarrow B) & \mathscr A_1\\ C \vdash &A\rightarrow B & \text{MP} \end{aligned} \]

• 情形2：此时有\(C\vdash B\)，与情形1同理

• 情形3：若\(B\equiv A\)，由于\(\vdash A\rightarrow A\)，显然成立

\[\begin{aligned} C\vdash& A\rightarrow((A\rightarrow A)\rightarrow A) & \mathscr A_1\\ C\vdash& (A\rightarrow((A\rightarrow A)\rightarrow A)) \rightarrow \\ &((A\rightarrow(A\rightarrow A))\rightarrow (A\rightarrow A)) & \mathscr A_2\\ C\vdash& (A\rightarrow(A\rightarrow A)) \rightarrow (A\rightarrow A) & \text{MP}\\ C\vdash& A\rightarrow(A\rightarrow A) & \mathscr A_1\\ C\vdash& A\rightarrow A & \text{MP} \end{aligned} \]

• 情形4：此时根据归纳假设有\(C\vdash A\rightarrow Q;\ C\vdash A\rightarrow (Q\rightarrow B)\)

\[\begin{aligned} C\vdash &A\rightarrow Q & Hypo\\ C\vdash &A\rightarrow (Q\rightarrow B) & Hypo\\ C\vdash &(A\rightarrow (Q\rightarrow B))\rightarrow\\ &((A\rightarrow Q)\rightarrow(A\rightarrow B)) & \mathscr A_2 \\ C\vdash &(A\rightarrow Q)\rightarrow(A\rightarrow B) & \text{MP}\\ C\vdash &A\rightarrow B & \text{MP} \end{aligned} \]

T3

证明\(\vdash ((A\rightarrow B)\rightarrow A)\rightarrow A\)

可用定理：

\[\begin{aligned} &\vdash A\rightarrow A\\ &\vdash (P\rightarrow Q)\rightarrow(\neg Q\rightarrow \neg P)\\ &Q\rightarrow(P\rightarrow R), P \vdash Q\rightarrow R\\ &P \rightarrow Q ,Q \rightarrow R \vdash P \rightarrow R \end{aligned} \]

Proof

\[\begin{array}{lll} A_1:& \neg A\rightarrow(\neg(A\rightarrow B)\rightarrow \neg A ) &\mathscr A_1\\ A_2:& (\neg(A\rightarrow B)\rightarrow \neg A )\rightarrow (A\rightarrow (A\rightarrow B))&\mathscr A_3\\ A_3:& (A\rightarrow (A\rightarrow B))\rightarrow( (A\rightarrow A)\rightarrow (A\rightarrow B )) &\mathscr A_2\\ A_4:& ((A\rightarrow A)\rightarrow (A\rightarrow B ))\rightarrow\\ & (\neg(A\rightarrow B )\rightarrow \neg(A\rightarrow A)) & \vdash (P\rightarrow Q)\rightarrow(\neg Q\rightarrow \neg P)\\ A_5:& \neg A\rightarrow(\neg(A\rightarrow B )\rightarrow \neg(A\rightarrow A)) & A_{1},A_2,A_3,A_4\vdash A_5\\ A_6:& (\neg A\rightarrow(\neg(A\rightarrow B )\rightarrow \neg(A\rightarrow A)))\rightarrow \\ & ((\neg A\rightarrow\neg(A\rightarrow B ))\rightarrow( \neg A\rightarrow\neg(A\rightarrow A)))) &\mathscr A_2\\ A_7:& (\neg A\rightarrow\neg(A\rightarrow B ))\rightarrow( \neg A\rightarrow\neg(A\rightarrow A)))& A_5,A_6\vdash A_7\\ A_8:& ((A\rightarrow B)\rightarrow A)\rightarrow( \neg A\rightarrow\neg(A\rightarrow B)) \\ &\qquad \vdash (P\rightarrow Q)\rightarrow(\neg Q\rightarrow \neg P)\\ A_9:& (\neg A\rightarrow\neg(A\rightarrow A)))\rightarrow( (A\rightarrow A)\rightarrow A)& \mathscr A_3 \\ A_{10}:& ((A\rightarrow B)\rightarrow A)\rightarrow( (A\rightarrow A)\rightarrow A) & A_{8},A_7,A_9\vdash A_{10} \\ A_{11}:& A\rightarrow A & \vdash A\rightarrow A\\ A_{12}:& ((A\rightarrow B)\rightarrow A)\rightarrow A & Q\rightarrow(P\rightarrow R), P\vdash Q\rightarrow R \end{array} \]

T4

证明$\vdash \forall x P(x) \rightarrow \neg \exists x \neg P(x) $

可用定理：\(P \rightarrow Q ,Q \rightarrow R \vdash P \rightarrow R;\quad \vdash Q \rightarrow \neg \neg Q\)

Proof

\[\begin{aligned} \omega_1 &\quad \forall x P(x)\rightarrow P(x) & \text{公理四}\\ \omega_2 &\quad P(x) \rightarrow \neg \neg P(x) & \vdash Q \rightarrow \neg \neg Q\\ \omega_3 &\quad \forall x P(x) \rightarrow \neg \neg P(x) & \omega_1, \omega_2 \vdash \omega_3\\ \omega_4 &\quad \forall x(\forall x P(x) \rightarrow \neg \neg P(x)) & \text{UG}(\omega_3)\\ \omega_5 &\quad \forall x(\forall x P(x) \rightarrow \neg \neg P(x)) \rightarrow (\forall x P(x) \rightarrow \forall x \neg \neg P(x)) &\text{公理五}\\ \omega_6 &\quad \forall x P(x) \rightarrow \forall x \neg \neg P(x) &\omega_5 = \omega_4 \rightarrow \omega_6 (MP)\\ \omega_7 &\quad \forall x \neg \neg P(x) \rightarrow \neg \neg\forall x \neg \neg P(x) & \vdash Q \rightarrow \neg \neg Q\\ \omega_8 &\quad \forall x P(x) \rightarrow \neg \neg \forall x \neg \neg P(x) & \omega_6, \omega_7 \vdash \omega_8 (\text{传递律})\\ \end{aligned} \]

T5

1. 证明\(\vdash (\neg Q\rightarrow Q)\rightarrow(R\rightarrow Q)\)

2. 证明\(Q\rightarrow (P\rightarrow R), P\vdash Q\rightarrow R\)

3. 借助前两问结论证明\(\vdash (\neg A\rightarrow A)\rightarrow A\)

可用定理：

\[\begin{aligned} & P \rightarrow Q ,Q \rightarrow R \vdash P \rightarrow R;\\ \end{aligned} \]

答案及解析：

(1)

\[\begin{aligned} A_1:&\quad \neg Q\rightarrow (\neg\neg R\rightarrow \neg Q) & \mathscr A_1\\ A_2:&\quad (\neg\neg R\rightarrow \neg Q)\rightarrow (Q\rightarrow \neg R) & \mathscr A_3\\ A_3:&\quad \neg Q\rightarrow(Q\rightarrow \neg R) & A_1,A_2\vdash A_3\\ A_4:&\quad (\neg Q\rightarrow(Q\rightarrow \neg R))\rightarrow\\ &\quad ((\neg Q\rightarrow Q)\rightarrow(\neg Q\rightarrow \neg R) ) & \mathscr A_2\\ A_5:&\quad (\neg Q\rightarrow Q)\rightarrow(\neg Q\rightarrow \neg R) & A_3,A_4\vdash A_5\\ A_6:&\quad (\neg Q\rightarrow \neg R)\rightarrow(R\rightarrow Q) & \mathscr A_3\\ A_7:&\quad (\neg Q\rightarrow Q)\rightarrow(R\rightarrow Q) & A_5, A_6\vdash A_7 \end{aligned} \]

(2)

\[\begin{aligned} A_1:&\quad P & \in\Gamma\\ A_2:&\quad P\rightarrow(Q\rightarrow P) & \mathscr A_1\\ A_3:&\quad Q\rightarrow P & A_1,A_2\vdash A_3\\ A_4:&\quad Q\rightarrow(P\rightarrow R) & \in\Gamma\\ A_5:&\quad (Q\rightarrow(P\rightarrow R))\rightarrow\\ &\quad ((Q\rightarrow P)\rightarrow(Q\rightarrow R)) & \mathscr A_2\\ A_6:&\quad (Q\rightarrow P)\rightarrow(Q\rightarrow R) & A_4,A_5\vdash A_6\\ A_7:&\quad Q\rightarrow R & A_3,A_6\vdash A_7 \end{aligned} \]

(3)

\[\begin{aligned} A_1\quad& (\neg A\rightarrow A)\rightarrow( (Q\rightarrow(P\rightarrow Q))\rightarrow A ) ) & Lemma1\\ A_2\quad& Q\rightarrow(P\rightarrow Q) & \mathscr A_1\\ A_3\quad& (\neg A\rightarrow A)\rightarrow A & Lemma2 \end{aligned} \]

标签：Chapter,neg,Problems,vdash,mathscr,quad,aligned,rightarrow
From： https://www.cnblogs.com/fallqs/p/18221823