离散数学-5

(1) 2 既是偶数又是素数。

(2) 一个整数是奇数当且仅当它不能被 2 整除。

(3) 大学里的学生不是本科生就是研究生。

(4) 你的车速超过每小时 100 公里足以接到超速罚单。

(5) 只要你接到超速罚单，你的车速就超过每小时 100 公里。

(6) 要选修离散数学课程，你必须已经选修线性代数或数学分析。

(7) 只要不下雨，我就骑自行车上班。

(8) 只有不下雨，我才骑自行车上班。

(9) 除非你年满 18 周岁，否则你没有选举权。

[解]:

$$\begin{aligned} (1)&\quad \text{2 是偶数} \land \text{2 是素数} \\ (2)&\quad \forall x \in \mathbb{Z},\; (x \text{ 是奇数}) \leftrightarrow (2 \nmid x) \\ (3)&\quad \forall x,\; (\text{学生}(x) \land \text{在大学}(x)) \rightarrow (\text{本科生}(x) \lor \text{研究生}(x)) \\ (4)&\quad (\text{你的速度} > 100) \rightarrow \text{接到超速罚单} \\ (5)&\quad \text{接到超速罚单} \rightarrow (\text{你的速度} > 100) \\ (6)&\quad \text{选修离散数学} \rightarrow (\text{学过线性代数} \lor \text{学过数学分析}) \\ (7)&\quad \neg \text{下雨} \rightarrow \text{骑自行车上班} \\ (8)&\quad \text{骑自行车上班} \rightarrow \neg \text{下雨} \\ (9)&\quad \neg (\text{年龄} \geq 18) \rightarrow \neg \text{有选举权} \end{aligned}$$

判定下列逻辑蕴涵和逻辑等价是否成立，其中 A,B,C 为任意公式。

(1) $A \Rightarrow B \rightarrow A$

(2) $\neg A \rightarrow \neg B \Leftrightarrow B \rightarrow A$

(3) $A \rightarrow (B \rightarrow C) \Rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)$

(4) $A \rightarrow (B \rightarrow C) \Leftrightarrow A \land B \rightarrow C$

(5) $(A \lor B) \rightarrow C \Leftrightarrow (A \rightarrow C) \land (B \rightarrow C)$

(6) $\neg A \lor B, A \rightarrow (B \land C), D \rightarrow B \Rightarrow \neg B \rightarrow C$

[解]:

(1) T

(2) T

(3) T

(4) T

(5) T

(6) F,一个反例是 $A=B=C=D=\text{F}$.

求下列公式的合取范式与析取范式

(1) $\neg (q \rightarrow p) \land (r \rightarrow \neg s)$

(2) $(\neg p \land q) \rightarrow r$

(3) $\neg (p \lor q) \leftrightarrow (p \land q)$

(1)

$\begin{aligned} & \neg (q \rightarrow p) \land (r \rightarrow \neg s) \\ &\quad \equiv \neg (\neg q \lor p) \land (\neg r \lor \neg s) \\ &\quad \equiv (q \land \neg p) \land (\neg r \lor \neg s) \\ &\text{DNF: } (q \land \neg p \land \neg r) \lor (q \land \neg p \land \neg s) \\ &\text{CNF: } (q) \land (\neg p) \land (\neg r \lor \neg s) \\ \\ \end{aligned}$

(2)
$\begin{aligned} &(\neg p \land q) \rightarrow r \\ &\quad \equiv \neg (\neg p \land q) \lor r \\ &\quad \equiv (p \lor \neg q \lor r) \\ &\text{DNF: } p \lor \neg q \lor r \\ &\text{CNF: } (p \lor \neg q \lor r) \\ \\ \end{aligned}$
(3)

$$\begin{aligned} & \neg (p \lor q) \leftrightarrow (p \land q) \\ &\quad \equiv (\neg (p \lor q) \rightarrow (p \land q)) \land ((p \land q) \rightarrow \neg (p \lor q)) \\ &\quad \equiv ((p \lor q) \lor (p \land q)) \land (\neg (p \land q) \lor \neg (p \lor q)) \\ &\quad \equiv (p \lor q) \land (\neg p \lor \neg q) \land (\neg p \lor \neg q) \\ &\quad \equiv (p \lor q) \land (\neg p \lor \neg q) \\ &\text{DNF: } (p \land \neg p) \lor (p \land \neg q) \lor (q \land \neg p) \lor (q \land \neg q) \\ &\quad \equiv (p \land \neg q) \lor (q \land \neg p) \\ &\text{CNF: } (p \lor q) \land (\neg p \lor \neg q) \end{aligned}$$

求下列公式的主合取范式与主析取范式。

(1) $p \rightarrow (p \land q)$

(2) $(p \lor q) \rightarrow (q \rightarrow r)$

(3) $(p \rightarrow (p \land q)) \lor r$

$$\begin{aligned} &\text{(1) } p \rightarrow (p \land q) \\ &\quad \equiv \neg p \lor (p \land q) \\ &\quad \equiv (\neg p \lor p) \land (\neg p \lor q) \\ &\quad \equiv \top \land (\neg p \lor q) \\ &\quad \equiv \neg p \lor q \\ &\quad (p,q) = (0,0), (0,1), (1,1) \Rightarrow \text{小项 } m_0, m_1, m_3 \\ &\text{主析取范式: } (\neg p \land \neg q) \lor (\neg p \land q) \lor (p \land q) \\ &\text{主合取范式: } (\neg p \lor q) \\ \\ &\text{(2) } (p \lor q) \rightarrow (q \rightarrow r) \\ &\quad \equiv \neg (p \lor q) \lor (\neg q \lor r) \\ &\quad \equiv (\neg p \land \neg q) \lor \neg q \lor r \\ &\quad \equiv \neg q \lor r \lor (\neg p \land \neg q) \\ &\quad \equiv \neg q \lor r \\ &\text{主析取范式: 所有非2,6的极小项之析取，即 } m_0 \lor m_1 \lor m_3 \lor m_4 \lor m_5 \lor m_7 \\ &\quad = (\neg p \land \neg q \land \neg r) \lor (\neg p \land \neg q \land r) \lor (\neg p \land q \land r) \lor (p \land \neg q \land \neg r) \lor (p \land \neg q \land r) \lor (p \land q \land r) \\ &\text{主合取范式: } (p \lor \neg q \lor r) \land (\neg p \lor \neg q \lor r)\\ \\ &\text{(3) } (p \rightarrow (p \land q)) \lor r \\ &\quad \equiv (\neg p \lor (p \land q)) \lor r \\ &\quad \equiv (\neg p \lor r) \lor (p \land q) \\ &\quad \equiv (\neg p \lor r \lor p) \land (\neg p \lor r \lor q) \\ &\quad \equiv \top \land (\neg p \lor q \lor r) \\ &\quad \equiv \neg p \lor q \lor r \\ &\text{主合取范式: } M_4 = (\neg p \lor q \lor r) \\ &\text{主析取范式: 所有除 } m_4 \text{ 外的极小项之析取} \\ &\quad = m_0 \lor m_1 \lor m_2 \lor m_3 \lor m_5 \lor m_6 \lor m_7 \\ &\quad = (\neg p \land \neg q \land \neg r) \lor (\neg p \land \neg q \land r) \lor (\neg p \land q \land \neg r) \lor (\neg p \land q \land r) \\ &\qquad \lor (p \land \neg q \land r) \lor (p \land q \land \neg r) \lor (p \land q \land r) \end{aligned}$$

用 $\{ \neg, \rightarrow \}$ 等价表示下列公式

(1) $p \lor (p \land q) \leftrightarrow p$

(2) $((p \lor q) \lor r) \leftrightarrow (p \lor (q \lor r))$

(3) $((p \land q) \land r) \leftrightarrow (p \land (q \land r))$

(4) $(p \land (q \lor r)) \leftrightarrow ((p \land q) \lor (p \land r))$

(5) $(p \lor (q \land r)) \leftrightarrow (p \lor q) \land (p \lor r)$

只要知道:

$$\begin{align} \qquad A \lor B &\equiv \neg A \rightarrow B \\ \qquad A \land B &\equiv \neg(A \rightarrow \neg B) \\ \quad A \leftrightarrow B &\equiv (A \rightarrow B) \land (B \rightarrow A) \end{align}$$

即可.

$$\begin{aligned} &\text{(1)}\quad \bigl(\neg(\neg p \rightarrow \neg(p \rightarrow \neg q)) \rightarrow p\bigr) \land \bigl(p \rightarrow \neg(\neg p \rightarrow \neg(p \rightarrow \neg q))\bigr) \\ &\text{(2)}\quad \Bigl(\neg\bigl(\neg(\neg p \rightarrow q) \rightarrow r\bigr) \rightarrow \neg\bigl(\neg p \rightarrow \neg(q \rightarrow \neg r)\bigr)\Bigr) \\ &\qquad \land \Bigl(\neg\bigl(\neg p \rightarrow \neg(q \rightarrow \neg r)\bigr) \rightarrow \neg\bigl(\neg(\neg p \rightarrow q) \rightarrow r\bigr)\Bigr) \\ &\text{(3)}\quad \Bigl(\neg\bigl(\neg p \rightarrow \neg(\neg q \rightarrow \neg r)\bigr) \rightarrow \neg\bigl(\neg(\neg p \rightarrow \neg q) \rightarrow \neg r\bigr)\Bigr) \\ &\qquad \land \Bigl(\neg\bigl(\neg(\neg p \rightarrow \neg q) \rightarrow \neg r\bigr) \rightarrow \neg\bigl(\neg p \rightarrow \neg(\neg q \rightarrow \neg r)\bigr)\Bigr) \\ &\text{(4)}\quad \Bigl(\neg\bigl(\neg p \rightarrow \neg(\neg q \rightarrow r)\bigr) \rightarrow \neg\bigl(\neg(\neg p \rightarrow \neg q) \rightarrow \neg(\neg p \rightarrow \neg r)\bigr)\Bigr) \\ &\qquad \land \Bigl(\neg\bigl(\neg(\neg p \rightarrow \neg q) \rightarrow \neg(\neg p \rightarrow \neg r)\bigr) \rightarrow \neg\bigl(\neg p \rightarrow \neg(\neg q \rightarrow r)\bigr)\Bigr) \\ &\text{(5)}\quad \Bigl(\neg\bigl(\neg p \rightarrow \neg(\neg q \rightarrow \neg r)\bigr) \rightarrow \neg\bigl(\neg(\neg p \rightarrow q) \rightarrow \neg(\neg p \rightarrow r)\bigr)\Bigr) \\ &\qquad \land \Bigl(\neg\bigl(\neg(\neg p \rightarrow q) \rightarrow \neg(\neg p \rightarrow r)\bigr) \rightarrow \neg\bigl(\neg p \rightarrow \neg(\neg q \rightarrow \neg r)\bigr)\Bigr) \end{aligned}$$

(注意此答案由大模型生成,Costannt不保证其正确性!)

用 $\downarrow$、$\uparrow$ 分别等价表示下列公式。

(1) $\neg p \lor q$

(2) $p \land \neg q$

(3) $\neg p \lor \neg q$

(4) $p \leftrightarrow q$

只要知道：

$$\quad \text{NOR（}\downarrow\text{）: } p \downarrow q \equiv \neg(p \lor q) \\ \quad \text{NAND（}\uparrow\text{）: } p \uparrow q \equiv \neg(p \land q)$$

即可.

$$\begin{aligned} &\text{(1) } \neg p \lor q \\ &\quad \downarrow:\; \bigl((p \downarrow p) \downarrow q\bigr) \downarrow \bigl((p \downarrow p) \downarrow q\bigr) \\ &\quad \uparrow:\; p \uparrow (q \uparrow q) \\ \\ &\text{(2) } p \land \neg q \\ &\quad \downarrow:\; \Bigl( ((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q) \Bigr) \downarrow \Bigl( ((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q) \Bigr) \\ &\quad \uparrow:\; \bigl(p \uparrow (q \uparrow q)\bigr) \uparrow \bigl(p \uparrow (q \uparrow q)\bigr) \\ \\ &\text{(3) } \neg p \lor \neg q \\ &\quad \downarrow:\; \bigl((p \downarrow p) \downarrow (q \downarrow q)\bigr) \downarrow \bigl((p \downarrow p) \downarrow (q \downarrow q)\bigr) \\ &\quad \uparrow:\; p \uparrow q \\ \\ &\text{(4) } p \leftrightarrow q \\ &\quad \uparrow:\; \Bigl( \bigl((p \uparrow q) \uparrow (p \uparrow q)\bigr) \uparrow \bigl((p \uparrow q) \uparrow (p \uparrow q)\bigr) \Bigr) \\ &\qquad\qquad \uparrow \Bigl( \bigl(((p \uparrow p) \uparrow (q \uparrow q)) \uparrow ((p \uparrow p) \uparrow (q \uparrow q))\bigr) \uparrow \bigl(((p \uparrow p) \uparrow (q \uparrow q)) \uparrow ((p \uparrow p) \uparrow (q \uparrow q))\bigr) \Bigr) \\ &\quad \downarrow:\; \text{（类似构造，略）} \end{aligned}$$

(注意此答案由大模型生成,Costannt不保证其正确性!)

请注意:关于证明\推理,不同的教学年和教师要求可能不同,此处只能给出一种可行的方案,请认真自行完成作业,约定公理和一些常用的定理如下:

$A1:A \rightarrow(B\rightarrow A)$

$A2:(A\rightarrow(B\rightarrow C))\rightarrow((A\rightarrow B)\rightarrow(A \rightarrow C))$

$A3:(\neg A\rightarrow \neg B)\rightarrow(B \rightarrow A)$

$rmp:A=\text{Ture},A\rightarrow B=\text{True},then \, B=\text{True}$

$T1:A \rightarrow A$

$T2:A=\text{Ture},then \,(B \rightarrow A)=\text{True}$

$T3:\neg A \rightarrow(A \rightarrow B)$

$T3':A\rightarrow(\neg A\rightarrow B)$

$T4:\neg \neg A \Leftrightarrow A$

$T5:(B\rightarrow C)\rightarrow((A\rightarrow B) \rightarrow(A\rightarrow C))$

$T6:(A\rightarrow(B\rightarrow C))\rightarrow(B\rightarrow(A\rightarrow C))$

$T7:(A\rightarrow B)\rightarrow((B\rightarrow C)\rightarrow(A\rightarrow C))$

$T8:(\neg A \rightarrow A)\rightarrow A$

$T8':(A\rightarrow \neg A)\rightarrow\neg A$

$T9:\neg \neg A\rightarrow A$

$T10:A\rightarrow \neg \neg A$

$T11:(A\rightarrow\neg B)\rightarrow(B \rightarrow \neg A)$

$T12:(A\rightarrow B)\rightarrow(\neg B\rightarrow\neg A)$

$T13:(\neg A\rightarrow B)\rightarrow(\neg B\rightarrow A)$

$T14:(A\rightarrow C)\rightarrow((B\rightarrow C)\rightarrow((\neg A\rightarrow B)\rightarrow C))$

$T15:if\, A\rightarrow B,and\,C\rightarrow D,then\,(B\rightarrow C)\rightarrow(A\rightarrow D)$

对初学者,请认真理解每个定理的证明思想,特别要熟悉 $T14$ 的证明和使用,在后面的练习中会发现,大多数习题若能转化为使用 $T14$ 来解决,尽管会增加书写量,但能够简化思考难度.

在 PC 中证明下列事实：

(1) $\vdash (A \rightarrow (A \rightarrow B)) \rightarrow (A \rightarrow B)$

(2) $\neg A \vdash A \rightarrow B$

(3) $A \rightarrow B, \neg (B \rightarrow C) \rightarrow \neg A \vdash A \rightarrow C$

(4) $\vdash (A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow (D \rightarrow B)) \rightarrow (A \rightarrow (D \rightarrow C)))$

(5) $\vdash (A \rightarrow (B \rightarrow C)) \rightarrow ((C \rightarrow D) \rightarrow (A \rightarrow (B \rightarrow D)))$

(6) $\vdash ((A \rightarrow B) \rightarrow C) \rightarrow (B \rightarrow C)$

(7) $\vdash ((A \rightarrow B) \rightarrow (B \rightarrow A)) \rightarrow (B \rightarrow A)$

(8) $\vdash A \rightarrow ((A \rightarrow B) \rightarrow (C \rightarrow B))$

(9) $\vdash ((A \rightarrow B) \rightarrow A) \rightarrow A$

(10) $\vdash ((A \rightarrow B) \rightarrow C) \rightarrow ((C \rightarrow A) \rightarrow A)$

(11) $\vdash ((A \rightarrow B) \rightarrow C) \rightarrow ((A \rightarrow C) \rightarrow C)$

(12) $\vdash (((A \rightarrow B) \rightarrow C) \rightarrow D) \rightarrow ((B \rightarrow D) \rightarrow (A \rightarrow D))$

(13) $\vdash (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow (((A \rightarrow B) \rightarrow B) \rightarrow C))$

(14) $\vdash (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow (((B \rightarrow A) \rightarrow A) \rightarrow C))$

(1)

1. $(A \rightarrow B)\rightarrow(A\rightarrow B)\qquad T1$

2. $((A \rightarrow B)\rightarrow(A\rightarrow B)) \rightarrow ((A \rightarrow (A\rightarrow B))\rightarrow(A \rightarrow B)) \qquad T6$

3. $A \rightarrow ((A \rightarrow B) \rightarrow B)\qquad1,2,rmp$

4. $(A \rightarrow ((A \rightarrow B) \rightarrow B)) \rightarrow((A \rightarrow (A \rightarrow B))\rightarrow(A \rightarrow B))\qquad A2$

5. $(A \rightarrow (A \rightarrow B))\rightarrow(A \rightarrow B)\qquad 3,4,rmp$

(2)

1. $\neg A \rightarrow (A \rightarrow B)\qquad T3$

2. $\neg A$ 已知

3. $A \rightarrow B\qquad1,2,rmp$

(3)

1. $\neg(B\rightarrow C)\rightarrow\neg A$ 已知

2. $(\neg(B\rightarrow C)\rightarrow \neg A)\rightarrow (A\rightarrow(B\rightarrow C))\qquad A3$

3. $A\rightarrow(B\rightarrow C)\qquad1,2,rmp$

4. $(A\rightarrow(B\rightarrow C))\rightarrow((A \rightarrow B)\rightarrow(A \rightarrow C))\qquad A2$

5. $(A \rightarrow B)\rightarrow(A \rightarrow C)\qquad 3,4,rmp$

6. $A \rightarrow B$ 已知

7. $A \rightarrow C\qquad 5,6,rmp$

(4)

1. $(A\rightarrow (B\rightarrow C))\rightarrow(D\rightarrow(A\rightarrow(B\rightarrow C)))\qquad T2$

2. $(D\rightarrow(A\rightarrow(B\rightarrow C)))\rightarrow (A\rightarrow(D\rightarrow(B\rightarrow C)))\qquad T6$

3. $(D \rightarrow(B \rightarrow C)) \rightarrow((D\rightarrow B)\rightarrow(D \rightarrow C))\qquad A2$

4. $(A\rightarrow (B\rightarrow C))\rightarrow (A\rightarrow((D\rightarrow B)\rightarrow(D \rightarrow C)))$ 1,2,3连用三段论

5. $(A\rightarrow((D\rightarrow B)\rightarrow(D \rightarrow C)))\rightarrow((A\rightarrow(D\rightarrow B))\rightarrow(A\rightarrow(D\rightarrow C))) \qquad A2$

6. $(A\rightarrow (B\rightarrow C))\rightarrow ((A\rightarrow(D\rightarrow B))\rightarrow(A\rightarrow(D\rightarrow C)))$ 4,5用三段论

(5)

1. $(B \rightarrow C)\rightarrow((C\rightarrow D)\rightarrow(B\rightarrow D))\qquad T7$

2. $A \rightarrow ((B \rightarrow C)\rightarrow((C\rightarrow D)\rightarrow(B\rightarrow D)))\qquad T2$

3. $(A \rightarrow ((B \rightarrow C)\rightarrow((C\rightarrow D)\rightarrow(B\rightarrow D))))\rightarrow((A \rightarrow(B\rightarrow C))\rightarrow(A\rightarrow((C\rightarrow D)\rightarrow(B\rightarrow D))))\qquad A2$

4. $(A \rightarrow(B\rightarrow C))\rightarrow(A\rightarrow((C\rightarrow D)\rightarrow(B\rightarrow D)))\qquad 2,3,rmp$

5. $(A\rightarrow((C\rightarrow D)\rightarrow(B\rightarrow D)))\rightarrow ((C\rightarrow D)\rightarrow(A\rightarrow(B\rightarrow D))) \qquad T6$

6. $(A \rightarrow(B\rightarrow C))\rightarrow((C\rightarrow D)\rightarrow(A\rightarrow(B\rightarrow D)))$ 4,5,用三段论

(6)

1. $B \rightarrow(A\rightarrow B)\qquad A1$

2. $(B \rightarrow(A\rightarrow B))\rightarrow(((A\rightarrow B)\rightarrow C)\rightarrow(B \rightarrow C)) \qquad T7$

3. $((A\rightarrow B)\rightarrow C)\rightarrow(B \rightarrow C)\qquad 1,2,rmp$

(7)(本题采用T14证明)

1. $(A \rightarrow B)\rightarrow(\neg(A\rightarrow B)\rightarrow A) \qquad T3$

2. $B\rightarrow ((A \rightarrow B)\rightarrow(\neg(A\rightarrow B)\rightarrow A))\qquad T2$

3. $(B\rightarrow ((A \rightarrow B)\rightarrow(\neg(A\rightarrow B)\rightarrow A)))\rightarrow ((B\rightarrow(A \rightarrow B))\rightarrow (B\rightarrow(\neg(A\rightarrow B)\rightarrow A)))\qquad A2$

4. $(B\rightarrow(A \rightarrow B))\rightarrow (B\rightarrow(\neg(A\rightarrow B)\rightarrow A))\qquad 2,3,rmp$

5. $B\rightarrow(A \rightarrow B)\qquad A1$

6. $B\rightarrow(\neg(A\rightarrow B)\rightarrow A) \qquad 4,5,rmp$

7. $(B\rightarrow(\neg(A\rightarrow B)\rightarrow A)) \rightarrow (\neg(A\rightarrow B)\rightarrow(B\rightarrow A))\qquad T6$

8. $\neg(A\rightarrow B)\rightarrow(B\rightarrow A) \qquad 6,7,rmp$

9. $(B\rightarrow A)\rightarrow(B\rightarrow A) \qquad T1$

10. $(\neg(A \rightarrow B)\rightarrow(B\rightarrow A))\rightarrow(((B\rightarrow A)\rightarrow(B\rightarrow A))\rightarrow((\neg \neg(A\rightarrow B)\rightarrow(B\rightarrow A))\rightarrow(B\rightarrow A))) \qquad T14$

11. $((B\rightarrow A)\rightarrow(B\rightarrow A))\rightarrow((\neg \neg(A\rightarrow B)\rightarrow(B\rightarrow A))\rightarrow(B\rightarrow A)) \qquad 8,10,rmp$

12. $(\neg \neg(A\rightarrow B)\rightarrow(B\rightarrow A))\rightarrow(B\rightarrow A)\qquad 9,11,rmp$

13. $(\neg(B\rightarrow A)\rightarrow\neg(A\rightarrow B))\rightarrow(\neg \neg(A\rightarrow B)\rightarrow(B\rightarrow A)) \qquad T13$

14. $((A\rightarrow B)\rightarrow(B\rightarrow A))\rightarrow(\neg(B\rightarrow A)\rightarrow\neg(A\rightarrow B)) \qquad T12$

15. $((A\rightarrow B)\rightarrow(B\rightarrow A))\rightarrow(B\rightarrow A)$ 12,13,14连用三段论

(8)

1. $(C\rightarrow A)\rightarrow((A\rightarrow B)\rightarrow(C \rightarrow B)) \qquad T7$

2. $A\rightarrow(C\rightarrow A)\qquad A1$

3. $A\rightarrow ((A\rightarrow B)\rightarrow(C \rightarrow B))$ 1,2用三段论

(9)(本题采用T14证明)

1. $\neg A \rightarrow (A \rightarrow B)\qquad T3$

2. $(\neg A\rightarrow(A\rightarrow B))\rightarrow(\neg(A\rightarrow B)\rightarrow A)\qquad T13$

3. $\neg(A\rightarrow B)\rightarrow A\qquad1,2,rmp$

4. $(\neg(A\rightarrow B)\rightarrow A)\rightarrow((A\rightarrow A)\rightarrow(\neg\neg(A\rightarrow B)\rightarrow A))\qquad T14$

5. 后续证明路径可效仿(7)题,此处是显然有 $\neg\neg A \leftrightarrow A$,不直接使用这个关系的原因是我们使用PC演算系统,只包含$\{\rightarrow,\neg\}$

(10)(本题采用T14证明)

1. $\neg A \rightarrow (A \rightarrow B)\qquad T3$

2. $(\neg A\rightarrow(A\rightarrow B))\rightarrow(\neg(A\rightarrow B)\rightarrow A)\qquad T13$

3. $\neg(A\rightarrow B)\rightarrow A\qquad1,2,rmp$

4. $A \rightarrow ((C\rightarrow A)\rightarrow A)\qquad A1$

5. $\neg(A\rightarrow B)\rightarrow ((C\rightarrow A)\rightarrow A)$ 3,4,用三段论

6. $(\neg(A\rightarrow B)\rightarrow ((C\rightarrow A)\rightarrow A))\rightarrow((C\rightarrow((C \rightarrow A)\rightarrow A)\rightarrow((\neg\neg(A\rightarrow B)\rightarrow C)\rightarrow((C\rightarrow A)\rightarrow A)))) \qquad T14$

7. 后续证明路径可效仿(7)题

(11)(本题采用T14证明)

1. $\neg A \rightarrow (A \rightarrow B)\qquad T3$

2. $(\neg A\rightarrow(A\rightarrow B))\rightarrow(\neg(A\rightarrow B)\rightarrow A)\qquad T13$

3. $\neg(A\rightarrow B)\rightarrow A\qquad1,2,rmp$

4. $(\neg(A\rightarrow B)\rightarrow A)\rightarrow((A\rightarrow C)\rightarrow(\neg(A\rightarrow B)\rightarrow C))\qquad T7$

5. $(A\rightarrow C)\rightarrow(\neg(A\rightarrow B)\rightarrow C)\qquad 3,4,rmp$

6. $((A\rightarrow C)\rightarrow(\neg(A\rightarrow B)\rightarrow C)) \rightarrow (\neg(A\rightarrow B)\rightarrow((A\rightarrow C)\rightarrow C))\qquad T6$

7. $\neg(A\rightarrow B)\rightarrow((A\rightarrow C)\rightarrow C)\qquad 5,6,rmp$

8. $(\neg(A\rightarrow B)\rightarrow((A\rightarrow C)\rightarrow C)) \rightarrow((C\rightarrow((A\rightarrow C)\rightarrow C))\rightarrow((\neg\neg(A\rightarrow B)\rightarrow C)\rightarrow((A\rightarrow C)\rightarrow C))) \qquad T14$

9. 后续证明路径可效仿(7)题

(12)