数理逻辑基础

HW1

题目1

(1)

该式为永假公式（矛盾式）.

(2)

该式为永真公式（重言式）.

(3)

该式为可满足公式.

题目2

从而公式 $A$$A$ 和 $B$$B$ 适合德·摩根律

题目3

(1)

(2)

由 $(1)$$(1)$，$(2)$$(2)$，

HW2

题目1

(1)

(2)

(3)

题目2

(1)

(2)

(3)

从而，

题目3

(1)

即原公式的析取范式是 $P\vee \mathrm{\neg }Q$$P\lor\lnot Q$. 同时它也是合取范式.

(2)

即原公式的合取范式是 $P\wedge Q\wedge \mathrm{\neg }Q$$P\land Q\land\lnot Q$，同时它也是析取范式.

(3)

即原公式的析取范式是 $(\mathrm{\neg }P\wedge \mathrm{\neg }Q)\vee (\mathrm{\neg }P\wedge \mathrm{\neg }R)\vee P\vee Q\vee R$$(\lnot P\land\lnot Q)\lor(\lnot P\land \lnot R)\lor P\lor Q\lor R$ 或 $\mathrm{\neg }P\vee P$$\lnot P\lor P$，

合取范式是 $\mathrm{\neg }P\vee P$$\lnot P\lor P$.

HW3

题目1

(1)

主析取范式为

主合取范式为

(2)

主析取范式为

主合取范式为 $\varnothing$$\varnothing$.

(3)

主析取范式为 $\varnothing$$\varnothing$，主合取范式为

题目2

主析取范式为

主合取范式为

题目3

主合取范式为

主析取范式为

HW4

题目1

(1)

(2)

题目2

题目3

所求公式 $G\iff G_1\wedge G_2\wedge G_3$$G\lrArr G_1\land G_2\land G_3$，其中 $G_1\iff A\to C$$G_1\lrArr A\to C$，$G_2\iff B\to \mathrm{\neg }C$$G_2\lrArr B\to\lnot C$，$G_3\iff \mathrm{\neg }C\to (A\vee B)$$G_3\lrArr \lnot C\to(A\lor B)$.

从而

派遣方案：

• A、B 不去，C 去；

• A、C 不去，B 去；

• B 不去，A、C 去.

HW5

题目1

记

• $A$$A$：早饭吃面包；

• $B$$B$：早饭吃蛋糕；

• $C$$C$：早饭喝牛奶；

• $D$$D$：早饭喝咖啡.

前提： $A\vee B$$A\lor B$，$A\to C$$A\to C$，$B\to D$$B\to D$，$\mathrm{\neg }D$$\lnot D$，

结论：$A\wedge C$$A\land C$.

推理：

1. $B\to D$$B\to D$（前提引入）

2. $\mathrm{\neg }D$$\lnot D$ （前提引入）

3. $\mathrm{\neg }B$$\lnot B$ （1, 2 拒取式）

4. $A\vee B$$A\lor B$ （前提引入）

5. $A$$A$ （3, 4 析取三段论）

6. $A\to C$$A\to C$ （前提引入）

7. $C$$C$ （5, 6 假言推理）

8. $A\wedge C$$A\land C$ （5, 7 合取引入）

题目2

根据 CP 规则，只需要从前提 $\{P\to (Q\to S),\mathrm{\neg }R\vee P,Q,R\}$$\{P\to(Q\to S),\lnot R\lor P,Q,R\}$ 推理出 $S$$S$ 即可.

推理：

1. $\mathrm{\neg }R\vee P$$\lnot R\lor P$ （前提引入）

2. $R$$R$ （附加前提引入）

3. $P$$P$ （1, 2 析取三段论）

4. $P\to (Q\to S)$$P\to(Q\to S)$ （前提引入）

5. $Q\to S$$Q\to S$ （3, 4 假言推理）

6. $Q$$Q$ （前提引入）

7. $S$$S$ （5, 6 假言推理）

从而有 $T\models R\to S$$T\vDash R\to S$.

题目3

记

• $A$$A$：国际米兰夺冠

• $B$$B$：AC 米兰获亚军

• $C$$C$：尤文图斯获亚军

• $D$$D$：拉齐奥获亚军

前提： $A\to (B\vee C)$$A\to(B\lor C)$，$C\to \mathrm{\neg }A$$C\to\lnot A$，$D\to \mathrm{\neg }B$$D\to\lnot B$，$A$$A$.

结论：$\mathrm{\neg }D$$\lnot D$.

推理：

1. $A\to (B\vee C)$$A\to(B\lor C)$ （前提引入）

2. $A$$A$ （前提引入）

3. $B\vee C$$B\lor C$ （1, 2 假言推理）

4. $C\to \mathrm{\neg }A$$C\to\lnot A$ （前提引入）

5. $\mathrm{\neg }C$$\lnot C$ （2, 4 拒取式）

6. $B$$B$ （3, 5 析取三段论）

7. $D\to \mathrm{\neg }B$$D\to\lnot B$ （前提引入）

8. $\mathrm{\neg }D$$\lnot D$ （6, 7 拒取式）

9. $D$$D$ （结论的否定，附加前提引入）

10. $D\wedge \mathrm{\neg }D$$D\land\lnot D$ （合取引入）

10 为一个矛盾式，故根据归谬法，原结论成立，论述有效.

HW6

题目1

• 直接证明：

  1. $p;$$p;$ （假定）

  2. $p\to (q\to p);$$p\to(q\to p);$ （L1）

  3. $q\to p;$$q\to p;$ （1, 2 MP）；

  4. $q\to (p\to r);$$q\to(p\to r);$ （假定）

  5. $(q\to (p\to r))\to ((q\to p)\to (q\to r));$$(q\to(p\to r))\to((q\to p)\to(q\to r));$ （L2）

  6. $(q\to p)\to (q\to r);$$(q\to p)\to (q\to r);$ （4, 5 MP）

  7. $q\to r.$$q\to r.$ （3,6 MP）

• 演绎定理：

  $\mathrm{\Gamma }\cup \{p\}⊢q\iff \mathrm{\Gamma }⊢p\to q$$\Gamma\cup\{p\}\vdash q\lrArr \Gamma\vdash p\to q$. 则只需要证明 ${\mathrm{\Gamma }}^{\prime }⊢r$$\Gamma'\vdash r$，其中 ${\mathrm{\Gamma }}^{\prime }=\mathrm{\Gamma }\cup \{q\}=\{p,q,(q\to (p\to r))\}$$\Gamma'=\Gamma\cup\{q\}=\{p,q,(q\to(p\to r))\}$.

  1. $q;$$q;$ （新假定）

  2. $q\to (p\to r);$$q\to(p\to r);$ （假定）

  3. $p\to r;$$p\to r;$ （1, 2 MP）

  4. $p;$$p;$ （假定）

  5. $r.$$r.$ （3, 4 MP）

题目2

(1)

$\mathrm{\Gamma }=\{q\to p\}$$\Gamma=\{q\to p\}$，证明 $\mathrm{\Gamma }⊢(\mathrm{\neg }p\to \mathrm{\neg }q)$$\Gamma\vdash(\lnot p\to \lnot q)$.

1. $q\to p;$$q\to p;$ （假定）

2. $(q\to p)\to (\mathrm{\neg }p\to \mathrm{\neg }q);$$(q\to p)\to(\lnot p \to\lnot q);$ （换位律）

3. $\mathrm{\neg }p\to \mathrm{\neg }q.$$\lnot p\to\lnot q.$ （1, 2 MP）

(2)

$\mathrm{\Gamma }=\{\mathrm{\neg }(p\to q)\}$$\Gamma=\{\lnot(p\to q)\}$，证明 $\mathrm{\Gamma }⊢(q\to p)$$\Gamma\vdash(q\to p)$.

由演绎定理，只需要证明 $\{q,\mathrm{\neg }(p\to q)\}⊢p$$\{q,\lnot(p\to q)\}\vdash p$.

1. $\mathrm{\neg }(p\to q)\to ((p\to q)\to p);$$\lnot(p\to q)\to((p\to q)\to p);$ （否定前件律）

2. $\mathrm{\neg }(p\to q);$$\lnot(p\to q);$ （假定）

3. $(p\to q)\to p;$$(p\to q)\to p;$ （1, 2 MP）

4. $q\to (p\to q);$$q\to(p\to q);$ （L1）

5. $q;$$q;$ （新假定）

6. $p\to q;$$p\to q;$ （4, 5 MP）

7. $p.$$p.$ （3, 6 MP）

(3)

$\mathrm{\Gamma }=\{((p\to q)\to p)\}$$\Gamma=\{((p\to q)\to p)\}$，证明 $\mathrm{\Gamma }⊢p$$\Gamma\vdash p$.

1. $(p\to q)\to p;$$(p\to q)\to p;$ （假定）

2. $((p\to q)\to p)\to (p\to q);$$((p\to q)\to p)\to (p\to q);$ （假定）

3. $p\to q;$$p\to q;$ （1, 2 MP）

4. $p.$$p.$ （1, 3 MP）

(4)

$\mathrm{\Gamma }=\{p\to q\}$$\Gamma=\{p\to q\}$，证明 $\mathrm{\Gamma }⊢((\mathrm{\neg }p\to q)\to q)$$\Gamma\vdash((\lnot p\to q)\to q)$.

由演绎定理，只需要证明 ${\mathrm{\Gamma }}^{\prime }=\{p\to q,\mathrm{\neg }p\to q\}⊢q$$\Gamma'=\{p\to q,\lnot p\to q\}\vdash q$.

又由反证律，只需要证明 ${\mathrm{\Gamma }}^{″}=\{p\to q,\mathrm{\neg }p\to q,\mathrm{\neg }q\}⊢p$$\Gamma''=\{p\to q,\lnot p\to q,\lnot q\}\vdash p$ 且 ${\mathrm{\Gamma }}^{″}=\{p\to q,\mathrm{\neg }p\to q,\mathrm{\neg }q\}⊢\mathrm{\neg }p$$\Gamma''=\{p\to q,\lnot p\to q,\lnot q\}\vdash \lnot p$ 即可.

一方面，

1. $p\to q;$$p\to q;$ （假定）

2. $(p\to q)\to (\mathrm{\neg }q\to \mathrm{\neg }p);$$(p\to q)\to(\lnot q\to\lnot p);$ （换位律）

3. $\mathrm{\neg }q\to \mathrm{\neg }p;$$\lnot q\to\lnot p;$ （1, 2 MP）

4. $\mathrm{\neg }q;$$\lnot q;$ （反证律-新假定）

5. $\mathrm{\neg }p.$$\lnot p.$ （3, 4 MP）

另一方面，

1. $\mathrm{\neg }p\to q;$$\lnot p\to q;$ （演绎定理-新假定）

2. $(\mathrm{\neg }p\to q)\to (\mathrm{\neg }q\to p);$$(\lnot p\to q)\to(\lnot q\to p);$ （换位律）

3. $\mathrm{\neg }q\to p;$$\lnot q\to p;$ （1, 2 MP）

4. $\mathrm{\neg }q;$$\lnot q;$ （反证律-新假定）

5. $p.$$p.$

故根据反证律，有 ${\mathrm{\Gamma }}^{\prime }⊢q$$\Gamma'\vdash q$，再根据演绎定理有 $\mathrm{\Gamma }⊢((\mathrm{\neg }p\to q)\to q)$$\Gamma\vdash ((\lnot p\to q)\to q)$.

题目3

归谬律：$\mathrm{\Gamma }\cup \{p\}⊢q$$\Gamma\cup\{p\}\vdash q$ 且 $\mathrm{\Gamma }\cup \{p\}⊢\mathrm{\neg }q\Rightarrow \mathrm{\Gamma }⊢\mathrm{\neg }p$$\Gamma\cup\{p\}\vdash\lnot q\rArr\Gamma\vdash\lnot p$.

反证律：$\mathrm{\Gamma }\cup \{\mathrm{\neg }p\}⊢q$$\Gamma\cup\{\lnot p\}\vdash q$ 且 $\mathrm{\Gamma }\cup \{\mathrm{\neg }p\}⊢\mathrm{\neg }q\Rightarrow \mathrm{\Gamma }⊢p$$\Gamma\cup\{\lnot p\}\vdash \lnot q\rArr\Gamma\vdash p$.

已知 $q$$q$ 是从 $\mathrm{\Gamma }\cup \{\mathrm{\neg }p\}$$\Gamma\cup\{\lnot p\}$ 的证明，即

$(1)$$(1)$ ...

$(k)$$(k)$ $\mathrm{\neg }p\to q;$$\lnot p\to q;$ // $\mathrm{\neg }p\to q$$\lnot p\to q$ 从 $\mathrm{\Gamma }$$\Gamma$ 的证明

$(k+1)$$(k+1)$ $\mathrm{\neg }p;$$\lnot p;$ （新假定）

$(k+2)$$(k+2)$ $q.$$q.$ （$(k)$$(k)$，$(k+1)$$(k+1)$ MP）

将引入的 $\mathrm{\neg }p$$\lnot p$ 替换为 $\mathrm{\neg }\mathrm{\neg }(\mathrm{\neg }p)$$\lnot\lnot(\lnot p)$，再根据双重否定律，改写如下：