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

广义德摩根律与分配律

摘要

德摩根律与分配律到目前为止只是对两项陈述的；而范式汇集任意多项的合取与析取，并要求这些定律具有这样的一般性。本课用递归定义公式列表 (φ1,…,φn)(\varphi_1, \ldots, \varphi_n) 的合取与析取，分别记作 ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i 和 ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i，按左结合方式组合，并对项数归纳证明：值引理（合取为真当且仅当它的所有项都为真；析取为真当且仅当某一项为真）、允许重新分组的广义结合律、与顺序和重复无关性、广义德摩根律，以及范式一课将使用的那种形式的广义分配律：两个析取（分别有 nn 项和 mm 项）的合取，等价于从每个析取各取一项所组成的 nmnm 个合取的析取；对偶地亦然。习题计算赋值的个数，找出一个把重新分组冒充为定义的证明中的错误，度量一次分配所引起的增长，并由此得到一个有 2n2^n 项的重言式。

学习目标

  1. 写出 nn 项的合取与析取，使用记号 ⋀\bigwedge 和 ⋁\bigvee，把它们展开为左结合的符号串，并用值引理计算它们的真值。
  2. 对项数归纳证明广义结合律、与顺序和重复无关性以及广义德摩根律，并在每一步区分符号串的恒等与语义等价。
  3. 通过组织对两个指标的归纳，证明广义分配律及其对偶，并计算一次分配产生的项数。
  4. 找出一个归纳证明中的错误，其基始写错了，或者其归纳步骤暗藏了一次重新分组，并加以修正。

任意项数的定律

关于语义后承与语义等价的一课确立了两项的等价律：其中有 ∧\wedge 与 ∨\vee 的交换律和结合律、德摩根律以及两条分配律。然而，析取范式中的公式是若干合取的析取，每个合取需要多少项就有多少项，而把一个公式化为这种形式，需要对任意长度的合取与析取进行否定、重新分组和分配。如果是这样，二元定律照原样是不够的：必须把它们推广到 nn 项，并且一次性地对所有 nn 做到这一点。

对每个固定的 nn，nn 项的德摩根律可以用一张 2n2^n 行的真值表来验证，表中写有 nn 个变元，而上一课的统一代入作用于两边之间的双条件，便可把它推广到任意公式。但 nn 的值有无穷多个，任何数量的表都穷尽不了它们。由此可知，“对所有 nn”这一断言不是两个公式之间的一个等价，而是关于无穷多个等价的一个陈述，是在元语言中表述的；它的证明，就像关于自然数上与公式上的归纳法一课中的证明那样，是一个外部证明，其工具是对项数的归纳。记号 ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i 同样属于元语言：它不是语言中的一个新符号，而是由圆圈和圆盘组成的某个符号串的名称，正如 (φ∧ψ)(\varphi \wedge \psi) 也是这样的名称。

最好从现在起就确定三种不可混淆的关系。等式 α=β\alpha = \beta 说的是 α\alpha 与 β\beta 是同一个符号串；定义用 :=:= 书写，它为符号串引入名称，而展开一个定义所得到的东西与原来的东西相等，而不仅仅是等价。语义等价 α≡β\alpha \eqsem \beta 说的是 v(α)=v(β)v(\alpha) = v(\beta) 对每个赋值 vv 成立。演绎单元中的可证等价 α⊣⊢β\alpha \dashv\vdash \beta 说的是两个公式中的每一个都可以从另一个推演出来。本课使用前两种关系；第三种只在一处评注中出现。

所用的内容

从关于命题逻辑的语义学的一课中，我们取用：赋值，即从变元 v1,v2,…v_1, v_2, \ldots 到 {0,1}\{0, 1\} 的函数，以及它到所有公式的扩张，仍用同一个字母 vv 表示；由正式缩写算出的派生联结词的值：v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi)，v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi)，因此合取取值 11 当且仅当它的两个成分都取值 11，并且 v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 当且仅当 v(φ)=1v(\varphi) = 1 或 v(ψ)=1v(\psi) = 1；一致引理（若两个赋值在一个公式的变元上一致，则它们在该公式上一致）；以及公式 ⊤\top 和 ⊥\bot，即一个固定的重言式和一个固定的矛盾式。从关于语义后承与语义等价的一课中，我们取用：≡\eqsem 是自反的、对称的和传递的；语义替换定理；以及带有名称的定律目录：交换律，(φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) 和 (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi)；结合律，(φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) 以及关于 ∨\vee 的类似定律；德摩根律，¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) 和 ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)；分配律，(φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) 和 (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))；双重否定，¬¬φ≡φ\neg\neg\varphi \eqsem \varphi；幂等律，(φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi；同一律，(φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi；以及排中律，⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi)。这些定律对任意公式 φ\varphi、ψ\psi、χ\chi 都成立，它们是元变元。

在下面各个证明的每一步中，都把公式的某一部分替换成与之等价的另一部分。语义替换定理允许每次对一次出现这样做；下面的引理是它的一个特例，它对否定、合取或析取的各部分一次性地给出这一点。需要注意，这并不是语法上的平凡之事：¬α\neg\alpha 是符号串 (α↓α)(\alpha \downarrow \alpha)，其中 α\alpha 出现两次，因此 (α∧β)(\alpha \wedge \beta) 含有 α\alpha 的八次出现和 β\beta 的八次出现。

引理联结词与等价的兼容性

若 α≡α′\alpha \eqsem \alpha' 且 β≡β′\beta \eqsem \beta'，则 ¬α≡¬α′\neg\alpha \eqsem \neg\alpha'，(α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta')，并且 (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta')。

证明

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    设 vv 是任意赋值。由假设，α\alpha 与 α′\alpha' 取相同的值，β\beta 与 β′\beta' 也是如此。

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    否定的值和合取的值只依赖于它们的成分的值。

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    析取也是如此：它取值 11 当且仅当某个成分取值 11，而两边的成分取相同的值。

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    由于 vv 是任意的，这三个等价都成立。