作业 12 · 谓词公理系统与元性质

#作业

来源为 2024作业/作业12.docx。源目录中没有“作业 11”，所以编号从 10 直接跳到 12。

一、判断题

  1. 如果对每个公式 QQ 都有 Γ⊢Q\Gamma\vdash Q，则称 Γ\Gamma 协调；
  2. 命题逻辑公理系统具有一致性；
  3. 存在含二元谓词的一阶谓词演算系统是可判定的；
  4. 谓词逻辑完全性定理是 Γ⊢Q⇒Γ⊨Q\Gamma\vdash Q\Rightarrow\Gamma\models Q；
  5. 一个系统证明的定理都为真，说明系统可靠；
  6. 所有语义上为真的公式都可证，说明系统完全；
  7. 若某永真式 PP 满足 T⊢PT\vdash P，则 TT 协调；
  8. 若 T⊢0T\vdash0，则所用公理系统不可靠。
查看答案

依次为错误、正确、错误、错误、正确、正确、错误、错误。

  • 能推出每个公式恰恰是不协调；
  • 至少含一个二元谓词的一阶系统一般不可判定；
  • 第 4 句写的是可靠性方向，完全性方向是 Γ⊨Q⇒Γ⊢Q\Gamma\models Q\Rightarrow\Gamma\vdash Q；
  • 不协调的 TT 也能推出永真式；
  • T⊢0T\vdash0 可能是前提集自身矛盾，不能据此责怪公理系统。

二、综合证明

1. 全称量词保持蕴含

已知 Γ⊢A→B\Gamma\vdash A\to B，且 xix_i 不在 Γ\Gamma 中自由出现，证明

Γ⊢∀xiA→∀xiB.\Gamma\vdash\forall x_iA\to\forall x_iB.
查看源证明思路

由已知式对 xix_i 使用 UG 得 Γ⊢∀xi(A→B)\Gamma\vdash\forall x_i(A\to B)，再用谓词公理五

∀xi(A→B)→(∀xiA→∀xiB)\forall x_i(A\to B)\to(\forall x_iA\to\forall x_iB)

和 MP 即得结论。

2. 存在量词保持蕴含

在同样条件下证明

Γ⊢∃xiA→∃xiB.\Gamma\vdash\exists x_iA\to\exists x_iB.
查看源证明思路

由 A→BA\to B 的换位定理得 ¬B→¬A\neg B\to\neg A，再用上一题推出

∀xi¬B→∀xi¬A.\forall x_i\neg B\to\forall x_i\neg A.

将 ∃xC\exists xC 视为 ¬∀x¬C\neg\forall x\neg C，再作一次换位，得到目标式。

3. 存在量词消去

若 Γ⊢A→B\Gamma\vdash A\to B，且 xix_i 不在 B,ΓB,\Gamma 中自由出现，证明

Γ⊢∃xiA→B.\Gamma\vdash\exists x_iA\to B.
查看源证明思路

由换位得 ¬B→¬A\neg B\to\neg A。因为 xix_i 不在 ¬B\neg B 中自由出现，可把量词放到后件，得到

¬B→∀xi¬A.\neg B\to\forall x_i\neg A.

再换位，并用 ∃xiA≡¬∀xi¬A\exists x_iA\equiv\neg\forall x_i\neg A，即得结论。

4. 全称量词保持等价

若 Γ⊢A↔B\Gamma\vdash A\leftrightarrow B，且 xix_i 不在 Γ\Gamma 中自由出现，证明

Γ⊢∀xiA↔∀xiB.\Gamma\vdash\forall x_iA\leftrightarrow\forall x_iB.
查看答案

把 A↔BA\leftrightarrow B 展开为 A→BA\to B 与 B→AB\to A 的合取，分别应用第 1 题，再合取得到两个量化公式的等价。

5. 存在量词引入

若项 tt 对 AA 中的 xix_i 可代入，证明

⊢Atxi→∃xiA.\vdash A_t^{x_i}\to\exists x_iA.
查看答案

谓词公理四给出

∀xi¬A→(¬A)txi.\forall x_i\neg A\to(\neg A)_t^{x_i}.

换位后得到

¬(¬A)txi→¬∀xi¬A,\neg(\neg A)_t^{x_i}\to\neg\forall x_i\neg A,

即 Atxi→∃xiAA_t^{x_i}\to\exists x_iA。

6. 存在量词分配到合取的单向式

证明

⊢∃xi(A∧B)→(∃xiA∧∃xiB).\vdash\exists x_i(A\land B)\to(\exists x_iA\land\exists x_iB).
查看答案

由命题定理 A∧B→AA\land B\to A 和 A∧B→BA\land B\to B，分别应用第 2 题：

∃xi(A∧B)→∃xiA,\exists x_i(A\land B)\to\exists x_iA, ∃xi(A∧B)→∃xiB.\exists x_i(A\land B)\to\exists x_iB.

再用合取引入得到结论。

7. 不使用演绎定理的公理证明

只用公理、MP 和已允许定理证明

⊢(¬Q→Q)→Q.\vdash(\neg Q\to Q)\to Q.
查看源答案

源文件给出五个公式组成的 Hilbert 推导，核心是把公理三

(¬A→¬B)→(B→A)(\neg A\to\neg B)\to(B\to A)

作适当代入，并与 Q→QQ\to Q 配合两次 MP。原 DOCX 的变量在这一页严重错位，但目标式和“不得用演绎定理”的要求清晰，我保留此作答边界。

8. 用归纳法证明演绎定理

按证明长度归纳，证明

Γ,A⊢B⟹Γ⊢A→B.\Gamma,A\vdash B\Longrightarrow\Gamma\vdash A\to B.
查看答案

对证明序列最后一步分类：

  1. 若 BB 是公理或 Γ\Gamma 中前提，则先有 Γ⊢B\Gamma\vdash B，再由 A1 得 Γ⊢A→B\Gamma\vdash A\to B；
  2. 若 B=AB=A，使用定理 ⊢A→A\vdash A\to A；
  3. 若 BB 由 QQ 与 Q→BQ\to B 经 MP 得到，归纳假设给出 A→QA\to Q 和 A→(Q→B)A\to(Q\to B)，再用 A2 与两次 MP 得 A→BA\to B。

四种末步情形都成立，归纳完成。

9. 十个命题定理

使用命题逻辑公理系统证明：

  1. (Q→R)→((P→Q)→(P→R))(Q\to R)\to((P\to Q)\to(P\to R))；
  2. (P→(Q→R))→(Q→(P→R))(P\to(Q\to R))\to(Q\to(P\to R))；
  3. ¬¬Q→Q\neg\neg Q\to Q；
  4. Q→¬¬QQ\to\neg\neg Q；
  5. (Q→R)→(¬R→¬Q)(Q\to R)\to(\neg R\to\neg Q)；
  6. Q→(¬R→¬(Q→R))Q\to(\neg R\to\neg(Q\to R))；
  7. Q→R∨QQ\to R\lor Q；
  8. Q→Q∨RQ\to Q\lor R；
  9. Q∧R→QQ\land R\to Q；
  10. Q∧R→RQ\land R\to R。
查看源答案边界

源文件只写“见 PPT 或教材 4.5 节”，没有逐式提交证明。因此这里只保留题目，不补造为源答案。

10. 一个谓词公理证明

证明

⊢∀x(P(x)→Q(x))→(∀xP(x)→∀xQ(x)).\vdash\forall x(P(x)\to Q(x)) \to(\forall xP(x)\to\forall xQ(x)).
查看源证明结构

源答案先用公理四实例化全称前提，再借 A2 得

∀x(P(x)→Q(x))→(∀xP(x)→Q(x)).\forall x(P(x)\to Q(x))\to(\forall xP(x)\to Q(x)).

随后对自由的 xx 使用 UG，并以公理五把全称量词从后件提升，最终得到目标式。共八步。

评论