跳至内容
Topos Uranos
中文 (中国)

德摩根律与分配律

摘要

本课以两族全部数学都在使用的等价式结束演绎单元：德摩根律，它说明否定如何穿过合取或析取；分配律，它说明合取如何对析取分配，析取如何对合取分配。在证明它们之前，先澄清它们所依赖的一个区别：指称同一个符号串的两个表达式可以直接互相代替，因为它们是同一个公式；而仅仅等价的两个公式，只能借助等价替换，一层一层地在另一个公式内部互相代替。有了这一谨慎，就用推演证明两条德摩根律、它们的变体（其中包括蕴涵的否定）以及两条分配律，每条都证两个方向。问题利用它们得到幂等律、吸收律和结合律、简单的范式，以及把德摩根律与逆否律结合起来的推演。

学习目标

  1. 区分符号串的恒等与可证等价：前者允许在任何位置把缩写换成它的展开式，后者只允许借助等价替换在公式内部进行替换；并在推演中把等价连成链。
  2. 用推演证明两条德摩根律及其变体（包括蕴涵的否定），并认识双重否定替换规则在其中的作用。
  3. 在两个方向上证明合取对析取的分配律和析取对合取的分配律，每次选择合适的分情况证明。
  4. 通过逐步给出依据的等价链把公式化为简单的范式，并用推演得到幂等律、吸收律和结合律。
  5. 构造带前提的推演，把德摩根律与逆否律以及联结词的引入和消去规则结合起来。

本单元前面的几课一课接一课地建立了推演的工具：公理系统和分离规则，四种基本技巧和双重否定替换，联结词的对称性和经典逻辑的技巧。本课不添加任何新规则；它让这些规则一起工作。若是如此，本课的意义与其说在于那些陈述（它们也许在别的课程中已经见过），不如说在于得到它们的方式：每一行都必须以公理、前提、定义、两条初始规则之一或一个已证明的结果为依据，任何一行都不能依赖于“看起来显然”的东西。

所用的工具及其衔接

从关于形式演绎系统的一课中，取来卢卡西维茨的公理 A1、A2 和 A3，分离规则（MP），也包括带前提的形式，自反性（自反：若 φ∈Γ\varphi \in \Gamma，则 Γ⊢φ\Gamma \vdash \varphi），单调性（单调），切割规则（切割：若 Γ⊢φi\Gamma \vdash \varphi_i 对每个 ii 成立，且 Γ∪{φ1,…,φn}⊢ψ\Gamma \cup \{\varphi_1, \ldots, \varphi_n\} \vdash \psi，则 Γ⊢ψ\Gamma \vdash \psi），演绎定理，以及可证等价（φ⊣⊢ψ\varphi \dashv\vdash \psi 的意思是 {φ}⊢ψ\{\varphi\} \vdash \psi 且 {ψ}⊢φ\{\psi\} \vdash \varphi）及其性质：它是自反的、对称的和传递的，并且若 φ⊣⊢ψ\varphi \dashv\vdash \psi，则 Γ⊢φ\Gamma \vdash \varphi 当且仅当 Γ⊢ψ\Gamma \vdash \psi。从关于四种推演技巧的一课中，取来双重否定（φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi）、逆否律（逆否），特别是 (φ→ψ)⊣⊢(¬ψ→¬φ)(\varphi \rightarrow \psi) \dashv\vdash (\neg\psi \rightarrow \neg\varphi)，以及本课程系统的第二条初始规则，即双重否定替换（双否替换），有了它，演绎定理依然成立：若 χ′\chi' 是把 χ\chi 中子公式 θ\theta 的一次出现替换为 ¬¬θ\neg\neg\theta，或把 ¬¬θ\neg\neg\theta 的一次出现替换为 θ\theta 而得到的，则由 χ\chi 可推出 χ′\chi'；由第 ii 行这样得到的行，以双否替换(i)(i) 为依据。它的直接推论包括 (φ↓ψ)⊣⊢(¬¬φ↓ψ)(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)、(φ↓ψ)⊣⊢(φ↓¬¬ψ)(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)，以及一般地 χ⊣⊢χ′\chi \dashv\vdash \chi'（只要 χ′\chi' 由 χ\chi 经双否替换得到）；由此可知，双否替换(i)(i) 也适用于形如 χ⊣⊢φ\chi \dashv\vdash \varphi 的行，用来改变 φ\varphi 中的一个双重否定。从关于联结词的对称性的一课中，取来等价替换和对称性（对称），其中包括 (φ∨ψ)⊣⊢(ψ∨φ)(\varphi \vee \psi) \dashv\vdash (\psi \vee \varphi) 和 (φ∧ψ)⊣⊢(ψ∧φ)(\varphi \wedge \psi) \dashv\vdash (\psi \wedge \varphi)。

从关于经典逻辑的技巧的一课中，取来下列规则，它们都带有前提集 Γ\Gamma。析取引入（∨\vee引入）：若 Γ⊢φ\Gamma \vdash \varphi，则 Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) 且 Γ⊢(ψ∨φ)\Gamma \vdash (\psi \vee \varphi)。析取消去（∨\vee消去，即析取三段论）：若 Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi) 且 Γ⊢¬φ\Gamma \vdash \neg\varphi，则 Γ⊢ψ\Gamma \vdash \psi。合取引入（∧\wedge引入）：若 Γ⊢φ\Gamma \vdash \varphi 且 Γ⊢ψ\Gamma \vdash \psi，则 Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi)。合取消去（∧\wedge消去）：若 Γ⊢(φ∧ψ)\Gamma \vdash (\varphi \wedge \psi)，则 Γ⊢φ\Gamma \vdash \varphi 且 Γ⊢ψ\Gamma \vdash \psi。排中律：⊢(φ∨¬φ)\vdash (\varphi \vee \neg\varphi)。还有分情况证明（分情况）的两种形式：若 Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi 且 Γ∪{¬φ}⊢χ\Gamma \cup \{\neg\varphi\} \vdash \chi，则 Γ⊢χ\Gamma \vdash \chi；若 Γ∪{φ}⊢χ\Gamma \cup \{\varphi\} \vdash \chi、Γ∪{ψ}⊢χ\Gamma \cup \{\psi\} \vdash \chi 且 Γ⊢(φ∨ψ)\Gamma \vdash (\varphi \vee \psi)，则 Γ⊢χ\Gamma \vdash \chi。在推演中，第一种形式引用两行，记作分情况(i,j)(i, j)，第二种引用三行，记作分情况(i,j,k)(i, j, k)，次序与陈述一致：先是两个情况，最后是析取。那一课还提醒，每条已证明的规则在语境 Γ\Gamma 之内都成立，这里正是这样使用双重否定和逆否律的。

符号串的名字与等价的公式

回忆关于命题逻辑的语言的一课：除 ↓\downarrow 之外的联结词都是缩写，有正式且唯一的定义：¬φ:=(φ↓φ)\neg\varphi := (\varphi \downarrow \varphi)、(φ∨ψ):=¬(φ↓ψ)(\varphi \vee \psi) := \neg(\varphi \downarrow \psi)、(φ∧ψ):=¬(¬φ∨¬ψ)(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi)、(φ→ψ):=(¬φ∨ψ)(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi)、(φ↔ψ):=((φ→ψ)∧(ψ→φ))(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi)) 和 (φ⊻ψ):=¬(φ↔ψ)(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi)。定义并不对公式作出任何断言：它只是给一个已经存在的符号串取第二个名字。由此可知，如果两个表达式指称同一个符号串，那么一个可以在任何地方代替另一个，在更大的公式内部也是如此，因为写下的是同一串圆圈与圆盘。因此，¬(φ∧ψ)\neg(\varphi \wedge \psi) 和 ¬¬(¬φ∨¬ψ)\neg\neg(\neg\varphi \vee \neg\psi) 是同一个符号串：后者是在前者内部写出合取的展开式而得到的。在推演中，这种改名以“定义”为依据，后面写上被展开或被收回的联结词。

然而，可证等价不是恒等。φ⊣⊢¬¬φ\varphi \dashv\vdash \neg\neg\varphi 的意思是每一个都可由另一个推出，而不是它们是同一个符号串：¬¬φ\neg\neg\varphi 比 φ\varphi 长得多。因此，知道 φ⊣⊢φ′\varphi \dashv\vdash \varphi' 并不能直接允许在更大的公式中把 φ′\varphi' 写在 φ\varphi 的位置上。它也不允许“两边同时取否定”：由 φ⊣⊢φ′\varphi \dashv\vdash \varphi' 得出 ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi' 是一个定理，即等价替换，它的证明要用到逆否律，而不是一个显然的操作。只有一种情况，系统直接允许在公式的任何位置进行替换：把 θ\theta 换成 ¬¬θ\neg\neg\theta，或者反过来，这就是双重否定替换规则；而关于演绎系统的一课借助标记表明，就连这种情况也不能由公理和分离规则推出，因此必须把它作为公设。这种谨慎并非迂腐；正是它把证明与符号摆弄区分开来，后者若用于别的联结词或别的系统，可能导致谬误。

两个结果精确地规定了什么是允许的。第一个是关于形式演绎系统的一课中关于可证等价之性质的命题：若 Γ⊢φ\Gamma \vdash \varphi 且 φ⊣⊢φ′\varphi \dashv\vdash \varphi'，则 Γ⊢φ′\Gamma \vdash \varphi'，因此可证等价可以作用于一行的整个公式；而且可证等价是自反的、对称的和传递的，因此等价可以连成链（若 χ⊣⊢φ\chi \dashv\vdash \varphi 且 φ⊣⊢φ′\varphi \dashv\vdash \varphi'，则 χ⊣⊢φ′\chi \dashv\vdash \varphi'），而指称同一个符号串的两个表达式，由自反性，是可证等价的。第二个是下面的引理，为了引用方便，它汇集了等价替换向析取与合取的推广；关于对称性的一课对否定、蕴涵和或非证明了等价替换，并在它的一道例题中把它推广到这两个联结词。

引理析取与合取中的替换

若 φ⊣⊢φ′\varphi \dashv\vdash \varphi'，则对每个公式 ψ\psi，都有 (φ∨ψ)⊣⊢(φ′∨ψ)(\varphi \vee \psi) \dashv\vdash (\varphi' \vee \psi)、(ψ∨φ)⊣⊢(ψ∨φ′)(\psi \vee \varphi) \dashv\vdash (\psi \vee \varphi')、(φ∧ψ)⊣⊢(φ′∧ψ)(\varphi \wedge \psi) \dashv\vdash (\varphi' \wedge \psi) 和 (ψ∧φ)⊣⊢(ψ∧φ′)(\psi \wedge \varphi) \dashv\vdash (\psi \wedge \varphi')。

证明

  1. (φ∨ψ)=¬(φ↓ψ)(\varphi \vee \psi) = \neg\resaltar{(\varphi \downarrow \psi)}

    按定义，析取是一个或非的否定。

  2. (φ↓ψ)⊣⊢(φ′↓ψ)\dato{int}{(\varphi \downarrow \psi) \dashv\vdash (\varphi' \downarrow \psi)}

    关于或非的等价替换给出内层的等价。

  3. (φ∨ψ)⊣⊢(φ′∨ψ)\dato{disy}{\resaltar{(\varphi \vee \psi)} \dashv\vdash \resaltar{(\varphi' \vee \psi)}}

    关于否定的等价替换把它带到外层，即 ¬(φ↓ψ)⊣⊢¬(φ′↓ψ)\neg(\varphi \downarrow \psi) \dashv\vdash \neg(\varphi' \downarrow \psi)，这就是析取。同样，由 (ψ↓φ)⊣⊢(ψ↓φ′)(\psi \downarrow \varphi) \dashv\vdash (\psi \downarrow \varphi') 可得右侧的替换。

  4. (φ∧ψ)=¬(¬φ∨¬ψ),¬φ⊣⊢¬φ′(\varphi \wedge \psi) = \neg(\resaltar{\neg\varphi} \vee \neg\psi), \qquad \neg\varphi \dashv\vdash \neg\varphi'

    合取是否定式的析取的否定。关于否定的替换先给出 ¬φ⊣⊢¬φ′\neg\varphi \dashv\vdash \neg\varphi'。

  5. ¬(¬φ∨¬ψ)⊣⊢¬(¬φ′∨¬ψ),(φ∧ψ)⊣⊢(φ′∧ψ)\neg(\neg\varphi \vee \neg\psi) \dashv\vdash \neg(\neg\varphi' \vee \neg\psi), \qquad \resaltar{(\varphi \wedge \psi)} \dashv\vdash \resaltar{(\varphi' \wedge \psi)}

    已对析取证明的部分，应用于 ¬φ\neg\varphi 和 ¬φ′\neg\varphi'，给出 (¬φ∨¬ψ)⊣⊢(¬φ′∨¬ψ)(\neg\varphi \vee \neg\psi) \dashv\vdash (\neg\varphi' \vee \neg\psi)，再用关于否定的替换把等价带到合取上；右侧同理。

此后，“等价替换”指任何形式的等价替换，也包括这条引理中的形式，并且可以一层一层地连续使用多次，以到达任意深度的子公式。当一行是由第 ii 行应用一个已证明的等价而得到的，无论作用于整个公式，还是借助等价替换作用于它的某个部分，都以该等价的名称和行号为依据：双重否定(i)(i)、“等价替换，德摩根(i)(i)”。改名并不应用任何等价，只是重写同一个符号串；它也以同样的方式给出依据，即以“定义”为依据，后面写上被展开或被收回的联结词：定义 ∧\wedge (i)(i)。关于形式演绎系统的一课中的那个命题保证这样的行是有依据的，无论第 ii 行断言的是 Γ⊢φ\Gamma \vdash \varphi，还是一个逐步延伸的等价 χ⊣⊢φ\chi \dashv\vdash \varphi。