Truth table 不只告诉我们某个 formula 在一次赋值下的真值。看最终列，还能判断它是否可能为真、是否可能为假，以及一个 argument 是否 valid。Predicate 和 quantifier 则把这套真假的语言扩展到指定 universe 中的对象。

Propositional formula 的分类

如果至少有一种真值赋值使 propositional formula 为真，就称它 satisfiable；如果至少有一种赋值使它为假，就称它 falsifiable。因此，读 truth table 的最终列就能区分下面三类 formula：

下表为每一类检查一个例子。其中 implication $p\Rightarrow q$ 只有在 $p=1$ 且 $q=0$ 时为假。

根据最终列，可以作出如下分类：

$$p\lor\neg p\text{ is a tautology}, \qquad p\land\neg p\text{ is a contradiction}, \qquad p\Rightarrow q\text{ is a contingency}.$$

Formula classes overlap in one place

为什么完整 truth table 的计算量很大

含有 $n$ 个不同 propositional variables 的 formula 有 $2^n$ 种可能的真值赋值，因此完整 truth table 有 $2^n$ 行。列数则取决于我们选择展示多少个中间表达式。

逐行检查是一种有效的 decision procedure，但计算量随 $n$ 呈指数增长。Boolean satisfiability problem，通常简称 SAT，问的是一个 formula 是否至少有一种使它为真的赋值。SAT 是 NP-complete：如果存在能处理所有 SAT instances 的 polynomial-time algorithm，就能证明 $P=NP$；如果证明不存在这样的 algorithm，就能证明 $P\ne NP$。Logical identities 可以让我们不必列出所有行，就判断许多具体 formula 的类别，但目前并没有由此得到适用于所有 SAT instances 的已知 polynomial-time 方法。

Valid arguments 与 syllogisms

一个 argument 由 premises $P_1,\ldots,P_k$ 和 conclusion $C$ 组成。把所有 premises 用 conjunction 连接，再让它们 imply conclusion，得到

$$(P_1\land\cdots\land P_k)\Rightarrow C$$

如果这个 formula 是 tautology，argument 就是 valid。这并不表示 premises 在现实中一定为真，而是说：不可能出现所有 premises 都为真、conclusion 却为假的情况。这样，判断 validity 就转化成了判断 formula 是否为 tautology。

Modus ponens

Modus ponens 的形式是

$$\frac{p\Rightarrow q\qquad p}{q}.$$

对应的 formula 为

$$((p\Rightarrow q)\land p)\Rightarrow q.$$

用 logical identities 可以将它化简为 true。先展开内外两层 implication，再用 De Morgan's law 把 negation 推入 conjunction，最后重新组合各项：

$$\begin{aligned} ((p\Rightarrow q)\land p)\Rightarrow q &\equiv \neg((\neg p\lor q)\land p)\lor q\\ &\equiv \bigl(\neg(\neg p\lor q)\lor\neg p\bigr)\lor q\\ &\equiv \neg(\neg p\lor q)\lor(\neg p\lor q)\\ &\equiv 1. \end{aligned}$$

最后一步是 $\neg A\lor A$ 的形式，因此这个 argument valid。

另外两种 valid 形式

第二种形式是沿 implication 反向推理的正确方式：如果 $p$ 会迫使 $q$ 成立，而 $q$ 为假，那么 $p$ 就不可能为真。不要把它与另一种无效推理混淆：从 $p\Rightarrow q$ 和 $q$ 推出 $p$。

Predicate 与 universe of discourse

“Socrates 会死”是一个有真值的 proposition；但“会死”本身还没有指定对象。Predicate 表示这样的性质，给它一个对象之后，才能得到真或假的陈述。Universe of discourse 记作 $U$，是当前讨论的所有对象组成的 set。单变量 predicate 是一个 Boolean-valued function：

$$P:U\longrightarrow\mathbb B, \qquad \mathbb B=\{0,1\}.$$

$P(x)=1$ 表示对象 $x$ 具有这个性质；$P(x)=0$ 表示它不具有这个性质。

例如，取一个包含本例中希腊人物的小 universe，定义

$$M(x)=\text{“}x\text{ is mortal.”}$$

这里 $x$ 是 variable，$M$ 是 predicate。指定对象后，$M(x)$ 就成为 proposition。按本例采用的解释，

$$M(\text{Socrates})=1, \qquad M(\text{Zeus})=0.$$

Universe 不能省略不管：只能对 predicate 定义域中的对象求值，而且真值还取决于我们采用的解释。

Predicate 可以有多个变量。例如，实数上的双变量 predicate 的类型可以是

$$L:\mathbb R^2\longrightarrow\mathbb B.$$

令 $L(x,y)$ 表示 $x\le y$，那么

$$L(1,2)=1, \qquad L(4,2)=0.$$

在变量尚未赋值、也未被 quantifier 绑定之前，$L(x,y)$ 是 open formula，而不是具有一个确定真值的 proposition。

Quantifier、scope 与 bound variables

Quantifier 说明需要多少个对象满足 predicate。两种基本 quantifiers 是

如果 quantifier 旁边没有写出更小的 domain，$x$ 就在所选 universe $U$ 中取值。

$$\forall x\,P(x)$$

为真，当且仅当每个 $x\in U$ 都使 $P(x)=1$。只要找到一个使 $P(x)=0$ 的元素，就找到了 counterexample，足以推翻这个 universal statement。

$$\exists x\,P(x)$$

为真，当且仅当至少一个 $x\in U$ 使 $P(x)=1$。这样的元素称为 witness。证明 existential statement，只需要一个 witness；只有当整个 $U$ 中的对象都使 $P(x)=0$ 时，这个 statement 才为假。

A universal statement requires a constant true predicate

把“所有人都会死”写成符号

令 $H(x)$ 表示“$x$ 是人”，$M(x)$ 表示“$x$ 会死”。那么

$$\forall x\,(H(x)\Rightarrow M(x))$$

就表示“所有人都会死”。这里必须使用 implication。一个不是人的对象不会反驳这句话：它使 antecedent $H(x)$ 为假，因此对应的 implication 为真。

Free variables 与 bound variables

Quantifier 会 bind 它的 scope 内相应变量的出现。例如，在

$$\forall x\,Q(x,y),$$

中，$x$ 是 bound variable，但 $y$ 仍然是 free variable，formula 的真值仍可能依赖 $y$。而在

$$\forall x\,\exists y\,Q(x,y),$$

中，两个变量都被绑定。因此，一旦确定 universe 和 predicate 的解释，整个表达式就是 proposition。

Quantifier 的顺序会影响意思。一般来说，

$$\forall x\,\exists y\,Q(x,y) \not\equiv \exists y\,\forall x\,Q(x,y).$$

第一个 formula 允许针对每个 $x$ 选择不同的 $y$；第二个 formula 则要求同一个 $y$ 对所有 $x$ 都有效。

对 quantified statement 取 negation

Quantifier 的 negation 遵循 De Morgan's law 的形式：

$$\boxed{\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)}, \qquad \boxed{\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)}.$$

第一条 identity 表示：universal claim 为假，恰好意味着存在一个 counterexample，也就是“并非每个都满足”等价于“有一个不满足”。第二条表示：existential claim 为假，恰好意味着所有候选对象都不满足，也就是“没有任何一个满足”等价于“每个都不满足”。Negation 会把“所有”和“存在”的要求互换，同时否定内部的 predicate。

例：nested quantifiers

对下面的 statement 取 negation：

$$\forall x\,\bigl(P(x)\lor\exists y\,Q(x,y)\bigr).$$

把 negation 一层一层向内推进：

1. 穿过 universal quantifier，将 $\forall x$ 换成 $\exists x$。
2. 对 disjunction 使用 De Morgan's law，将 $\lor$ 换成 $\land$，并对两部分分别取 negation。
3. 将剩余的 negation 穿过 existential quantifier，把 $\exists y$ 换成 $\forall y$。

$$\begin{aligned} \neg\forall x\,\bigl(P(x)\lor\exists y\,Q(x,y)\bigr) &\equiv \exists x\,\neg\bigl(P(x)\lor\exists y\,Q(x,y)\bigr)\\ &\equiv \exists x\,\bigl(\neg P(x)\land\neg\exists y\,Q(x,y)\bigr)\\ &\equiv \exists x\,\bigl(\neg P(x)\land\forall y\,\neg Q(x,y)\bigr). \end{aligned}$$

最后得到的 statement 说：存在某个 $x$ 不满足 $P$，而且对同一个 $x$，无论 $y$ 取什么值，$Q(x,y)$ 都不成立。

Universe 为什么会改变真值

不带 domain restriction 的 quantified statement 可能随 universe 改变真值。例如，

$$\forall x\,(x>0)$$

在 $U=\{1,2,3,\ldots\}$ 时为真；在 $U=\mathbb R$ 时为假，因为 $0$ 和所有负实数都是 counterexamples。如果采用的约定把 $0$ 包含在 $\mathbb N$ 中，那么它在 $\mathbb N$ 上也为假。应当明确写出 universe，而不是依赖没有说明的约定。

Restricted quantifiers

如果 $A\subseteq U$，可以把 quantifier 的范围限制在 $A$ 中：

$$\forall x\in A\,P(x) \equiv \forall x\,(x\in A\Rightarrow P(x)),$$

以及

$$\exists x\in A\,P(x) \equiv \exists x\,(x\in A\land P(x)).$$

这两种展开使用不同的 connective，是因为它们要表达的要求不同：

• Universal restriction 使用 implication。$A$ 外的对象不应成为 counterexamples。
• Existential restriction 使用 conjunction。一个 witness 必须既属于 $A$，又满足 $P$。

例如，

$$\forall x\in\mathbb N\,(x\ge0)$$

在 $\mathbb N$ 的常用约定下都为真。如果外部 universe 还包含 $-1$，它并不影响这个 statement，因为展开后的 implication

$$-1\in\mathbb N\Rightarrow -1\ge0$$

有一个为假的 antecedent，因此整个 implication 为真。

同样，

$$\exists x\in\mathbb N\,(x>9000)$$

为真，因为 $10{,}000$ 是一个 witness。$\mathbb N$ 外的对象既不能证明它，也不能反驳它。

使用 De Morgan's laws 取 negation 时，domain restriction 保持不变：

$$\neg\forall x\in A\,P(x) \equiv \exists x\in A\,\neg P(x),$$ $$\neg\exists x\in A\,P(x) \equiv \forall x\in A\,\neg P(x).$$