语义后果与等价
摘要
在本课中，我们将研究命题逻辑中的语义后果与等价，这是对之前学习内容的自然延续。我们将学习如何从真值分配中得出语义后果的概念，以及这一概念如何与推论定理相关。此外，我们还将通过真值表的使用，学习如何获取如合取消去、析取引入等有用的性质。我们还将探讨语义等价的概念，并了解其与已知性质的关系。最后，我们将展示如何使用模型和推理技术来简化语义后果与等价问题的研究。
学习目标:
完成本课后，学生将能够
- 理解语义后果的概念。
- 理解符号⊨的不同解释。
- 理解推论定理的语义版本及其在研究语义后果和等价中的应用。
- 理解语义等价的定义及其与真值的关系。
- 应用推论定理的语义版本，将后果问题转化为有效性问题。
- 应用真值表的有用性质，证明语义等价。
- 应用吸收律、分配律和德摩根定律，简化复杂表达式。
- 分析模型与推理在命题逻辑研究中的关系。
目录
赋值与模型
推论定理（语义版本）
推论定理在语义后果与等价研究中的应用
语义等价及其性质
总结
对语义后果与等价的研究是我们复习命题逻辑语义的自然延续。现在我们将复习如何从真值分配中获得语义后果的概念，以及如何从中自然地得出推论定理的语义版本。我们将展示使用真值表获取一些有用性质的实际例子。你也可以在YouTube频道上看到这一切。
赋值与模型
首先，让我们从一个定义开始，这是我们将在本文中讨论的关键，语义后果的定义。
| 定义: 如果对于每个赋值\mathcal{A}都成立\mathcal{A}\models F \Rightarrow \mathcal{A}\models G，那么表达式G是另一个表达式F的语义后果。我们用F\models G来表示，这意味着“表达式F模型表达式G”或“G是F的语义后果”。 |
根据这一定义，我们必须注意，符号\models实际上在不同的上下文中有不同的解释：
- \mathcal{A} \models F意味着\mathcal{A}(F) = 1；也就是说，“\mathcal{A}模型F。”
- G \models F意味着如果任何赋值都模型G，那么它也模型F，我们读作“F是G的语义后果。”
- \models F意味着F在任何赋值下都成立；也就是说，F是一个重言式。
因此，尽管符号\models可能有多种解释，但上下文并不模糊。
语义后果的概念与我们之前讨论的“蕴涵”概念非常接近，如果F\models G成立，那么\models (F\rightarrow G)也成立。实际上，这与我们之前几节课讨论的推论定理非常相似。
推论定理（语义版本）
[观看]
| 定理: 如果F和G是任意表达式，那么 F\models G \Leftrightarrow \models (F\rightarrow G) 成立。 | ||||||||||||||||||||||||||||||||||||||||
| 证明: 通过观察真值表，可以轻松得出这个定理的证明。
如果我们专注于F\models G的含义，我们将看到这等同于说\mathcal{A}\models F \Rightarrow \mathcal{A}\models G，这本质上等同于\mathcal{A}\not\models F \vee \mathcal{A}\models G。现在，如果我们注意到\mathcal{A}\not\models F实际上等同于\mathcal{A}\models \neg F，那么我们可以说F\models G等同于\mathcal{A} \models \neg F \vee \mathcal{A}\models G。如果我们为F \rightarrow G创建一个真值表，并将满足条件\mathcal{A} \models \neg F \vee \mathcal{A}\models G的区域标记为绿色，我们会看到如下所示的情况：
由此可见，当F\models G成立时，\models (F \rightarrow G)也成立，反之亦然，这就是推论定理及其语义版本的逆定理。 |
假设我们想知道表达式G是否是另一个表达式F的后果。我们称之为后果问题。利用上述定理，我们可以将该问题转化为有效性问题，因为“如果G是F的后果，则(F\rightarrow G)是定理”。
推论定理在语义后果与等价研究中的应用
通过真值表可以推导出一些与我们以前见过的类似的性质。
| 示例: 使用真值表证明以下性质： | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 合取消去: | (F\wedge G)\models F | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 析取引入: | F\models (F\vee G) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 矛盾: | (F\wedge\neg F)\models G | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 解决方法: 使用我们刚刚回顾的推论定理，我们可以将后果问题转化为有效性问题。 为了解决合取消去，我们可以构建以下真值表：
通过这一真值表，我们证明了((F\wedge G)\rightarrow F)是一个重言式，因此，依据推论定理的逆定理，我们得到(F\wedge G) \models F。 析取引入通过构建适当的真值表以类似的方式解决。
在这里我们看到(F\rightarrow (F\vee G))是一个重言式，因此，根据推论定理的逆定理，我们得到F\models (F\vee G) 最后，使用相同的方法证明了矛盾性质。
通过这个真值表，我们证明了((F\wedge \neg F)\rightarrow G)是一个重言式，因此，根据推论定理的逆定理，我们得到(F\wedge \neg F)\models G。 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
语义等价及其性质
[观看]
| 定义: 如果同时成立F\models G和G\models F，那么我们说F和G在语义上是等价的。这可以表示为F\equiv G。 |
根据这一定义，两种表达式在语义上是等价的，当且仅当它们具有相同的真值。
| 示例: 可以通过真值表证明对称的语义等价是成立的。 |
| (F\downarrow G) \equiv (G\downarrow F) |
| (F\vee G) \equiv (G\vee F) |
| (F\wedge G) \equiv (G\wedge F) |
| (F\leftrightarrow G) \equiv (G\leftrightarrow F) |
| (F\underline{\vee} G) \equiv (G\underline{\vee} F) |
| 示例: 如果F是任意表达式，\top是重言式，\bot是矛盾式，那么可以通过真值表证明以下语义等价成立 |
| (F\wedge \top) \equiv F |
| (F\vee \top) \equiv \top |
| (F\wedge \bot) \equiv \bot |
| (F\vee \bot) \equiv F |
| 这些等价被称为吸收定律。 |
| 示例: 在命题逻辑语义中，合取和析取的分配律也成立。 |
| (F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H)) |
| (F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H)) |
| 示例: 在命题逻辑语义中，德摩根定律也成立。 |
| \neg(F\wedge G) \equiv (\neg F \vee \neg G) |
| \neg(F\vee G) \equiv (\neg F \wedge \neg G) |
| 练习: 一个好的练习是通过真值表证明吸收定律、分配律和德摩根定律的语义等价确实成立。 |
| 示例: 使用语义等价证明以下等价成立： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))。 |
| 解决方法: 我们可以通过真值表证明此等价性，但是如果这样做，我们将面临5个命题变量的表达式，这意味着需要制作一个具有2^5 = 32行的真值表，这最好能避免。为此，我们将使用我们已经展示的等价性。 首先注意(E\vee \neg E)是一个重言式。我们将这一重言式记为\top。然后，使用吸收定律我们得到： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) 使用分配律我们得到： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B)) 最后，通过对称性我们得到： ((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D)) 因此，通过这些等价性我们得到： ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D)) 这就是我们想要证明的内容。 |
总结
如果我们观察最后这个例子的展开，我们会发现，随着变量数量的增加，研究语义后果和等价问题的复杂性会呈指数增长，如果我们依赖真值表。然而，我们看到从模型的概念发展出了一些类似于我们之前详细研究的推理技术。模型和推理之间的这种关系将在不久的将来进一步探讨，结合两者的使用将最终使我们在逻辑研究中免受无数头痛之苦。