语义后承与语义等价

摘要

本课从公式的真值转向公式之间的关系。它定义从前提集（有穷或无穷）出发的语义后承，并明确后承符号的读法，包括其否定的读法：否定说的是某个东西不是有效的，而不是说它是矛盾的。它使用写成多项式的联结词的值，这把一条定律的验证变成一次计算；并证明后承的结构性质（自反性、单调性、切割和传递性）、语义演绎定理，以及把后承化归为不可满足性的定理，归结法将以后者为基础。随后它定义语义等价，证明它是一个等价关系，与相互后承以及双条件的有效性相一致，并对复杂度归纳证明使我们能够运用它的两个定理：把一个子公式的一次出现替换为另一个与之等价的公式，以及用公式对变元作统一代入。借助它们，本课确立带有正确名称的定律目录，并用等价链化简公式，而不使用真值表。

学习目标

判定一个公式是否是一个（有穷或无穷的）公式集的语义后承，方法是给出一个否证它的赋值，或者证明这样的赋值不存在。
证明并应用后承的性质、语义演绎定理以及把后承化归为不可满足性的定理。
用真值表、用值的计算以及用等价链来确立语义等价，并正确地给出每条定律的名称。
对复杂度归纳证明语义替换定理和统一代入定理，并区分各自在何时适用。

从上一课用到的内容

关于命题逻辑的语义学的一课赋予了公式以意义，本课把它当作已知。赋值是一个函数 $v\colon V \to \{0, 1\}$ ，它给每个变元指派一个真值， $1$ （真）或 $0$ （假）。由关于归纳法的一课中公式上的递归定义定理，每个赋值都借助或非的条款以唯一的方式扩张到所有公式；只需要这一条条款，因为这门语言只有一个联结词：

v((\varphi \downarrow \psi)) = 1 \;\Leftrightarrow\; v(\varphi) = 0, \;\; v(\psi) = 0

由于扩张是唯一的，扩张的值也写作 $v(\varphi)$ ；不带下标的字母 $v$ 总是表示一个赋值（ $v'$ 、 $w$ 、 $u$ 表示别的赋值），而变元总是带着它的下标。和关于形式化的一课一样， $p$ 、 $q$ 、 $r$ 、 $s$ 和 $t$ 表示变元 $v_1$ 到 $v_5$ ，而 $V(\varphi)$ 是 $\varphi$ 的变元集合。称 $v$ 满足 $\varphi$ ，记作 $v \models \varphi$ ，条件是 $v(\varphi) = 1$ ；称它否证该公式，记作 $v \not\models \varphi$ ，条件是 $v(\varphi) = 0$ 。一个公式是有效的（或重言式），记作 $\models \varphi$ ，如果每个赋值都满足它；是可满足的，如果某个赋值满足它；是不可满足的（或矛盾式），如果没有赋值满足它；是偶然式，如果它可满足而不有效。一个赋值满足公式集合 $\Gamma$ （记作 $v \models \Gamma$ ），是指它满足其中的每个公式； $\Gamma$ 是可满足的，如果某个赋值满足它，否则是不可满足的。最后， $\top := (v_1 \rightarrow v_1)$ ， $\bot := \neg\top$ ，于是对任意赋值都有 $v(\top) = 1$ 且 $v(\bot) = 0$ 。

此外还用到那一课的两个结果。第一个是一致引理：如果两个赋值在 $\varphi$ 的变元上一致，它们在 $\varphi$ 上也一致；由此，含 $n$ 个变元的公式的值只依赖于 $2^{n}$ 种组合，它的真值表是有穷的。第二个是派生联结词的值的定理，它从正式缩写出发，把每个联结词的值算成各成分之值的多项式。设 $a = v(\varphi)$ 且 $b = v(\psi)$ ：

v(\neg\varphi) = 1 - a, \qquad v((\varphi \vee \psi)) = a + b - ab, \qquad v((\varphi \wedge \psi)) = ab

v((\varphi \rightarrow \psi)) = 1 - a(1 - b), \qquad v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b), \qquad v((\varphi \veebar \psi)) = a + b - 2ab

本课的证明几乎都在于比较真值，而这些多项式使我们能够用一次计算来比较，而不必逐一检查情形。它们唯一附加的规则是： $0$ 和 $1$ 是仅有的与其平方相等的数：若 $x$ 等于 $0$ 或 $1$ ，则 $x^{2} = x$ 且 $x(1 - x) = 0$ 。此外，最好手边备有相同值的另外三种写法，它们通过展开乘积得到：

v((\varphi \downarrow \psi)) = (1 - a)(1 - b), \qquad v((\varphi \vee \psi)) = 1 - (1 - a)(1 - b), \qquad v((\varphi \leftrightarrow \psi)) = 1 - a - b + 2ab

第一种是或非的条款（ $1 - a$ 与 $1 - b$ 的乘积等于 $1$ ，恰好当 $a = b = 0$ 时）；第二种说析取等于 $0$ ，仅当两个成分都等于 $0$ ；第三种说双条件等于 $1$ （若 $a = b$ ，因为 $1 - 2a + 2a^{2} = 1$ ），等于 $0$ （若 $a \neq b$ ，因为此时 $a + b = 1$ 且 $ab = 0$ ）。