Propositional logic 研究真或假的陈述，以及把这些陈述组合起来的规则。Truth table 列出所有可能的真值组合，让我们逐一检查这些规则。

Proposition 与真值

Proposition 是一个陈述句，它要么为真，要么为假，不能同时为真和假。例如：

• $p$：“$42$ 能被 $3$ 整除”为真。
• $q$：“$2+2=5$”为假。
• $r$：“地外生命存在”也有真值，即使我们目前还不知道它是真是假。

一个 proposition 的真值属于 Boolean set

$$\mathbb B=\{0,1\}=\{\text{false},\text{true}\}.$$

这里，$0$ 表示 false，$1$ 表示 true。

基本 logical connectives

Logical connective 用来组合 proposition，或改变一个 proposition 的真值。

$p\lor q$ 中的“或”是 inclusive OR，包含两个 proposition 同时为真的情况。本页中 negation 的优先级高于 binary connectives，不过用括号明确运算顺序最不容易产生歧义。

基本 connective 的 truth table

Logical equivalence

如果两个 proposition 在每一种可能的情况下都有相同真值，就称它们 logically equivalent，记作

$$P\equiv Q.$$

用 truth table 证明 equivalence 时，只要检查两个表达式的最终列是否逐行相同。

De Morgan's law

考虑表达式

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

从内向外计算：先求 $\neg p$ 和 $\neg q$，再求它们的 conjunction，最后对这个 conjunction 取 negation。

最后两列完全相同，因此

$$\boxed{\neg(\neg p\land\neg q)\equiv p\lor q}.$$

这是 De Morgan's law 的一种写法。它的两种常用形式是

$$\neg(p\land q)\equiv\neg p\lor\neg q, \qquad \neg(p\lor q)\equiv\neg p\land\neg q.$$

Logical identities

Logical identities 与 set identities 有紧密的对应关系：conjunction 对应 intersection，disjunction 对应 union，negation 对应取 complement。

Symmetric difference $A\triangle B$ 包含恰好属于 $A$、$B$ 其中一个 set 的元素，因此对应 exclusive OR。

例如，set identity $A\cap U=A$ 对应

$$p\land1\equiv p.$$

下面几个 identities 也很常用：

$$\begin{aligned} \neg\neg p&\equiv p &&\text{double negation},\\ p\lor(p\land q)&\equiv p &&\text{absorption},\\ p\land(p\lor q)&\equiv p &&\text{absorption}. \end{aligned}$$

第一条 distributive law

Conjunction 对 disjunction 满足 distributive law：

$$p\land(q\lor r)\equiv(p\land q)\lor(p\land r).$$

中间列展示了两边各自的计算过程。两个完整表达式所在的列在每一行都相同。

第二条 distributive law

Disjunction 对 conjunction 也满足 distributive law：

$$p\lor(q\land r)\equiv(p\lor q)\land(p\lor r).$$

例：化简 proposition

化简

$$p\lor\neg(\neg p\lor\neg\neg q).$$

从最里面的 negation 开始，逐步向外处理：

$$\begin{aligned} p\lor\neg(\neg p\lor\neg\neg q) &\equiv p\lor\neg(\neg p\lor q) &&\text{double negation}\\ &\equiv p\lor(\neg\neg p\land\neg q) &&\text{De Morgan's law}\\ &\equiv p\lor(p\land\neg q) &&\text{double negation}\\ &\equiv p &&\text{absorption.} \end{aligned}$$

Exclusive OR

Exclusive OR 可以用 conjunction、disjunction 和 negation 表示：

$$p\oplus q\equiv(p\lor q)\land\neg(p\land q).$$

第一个条件要求至少一个 proposition 为真；第二个条件排除了两者同时为真的情况。

Conditional 与 biconditional

Conditional

Conditional

$$p\Rightarrow q$$

有三种等价的读法：

• “If $p$, then $q$”：如果前者成立，后者就成立。
• “$q$ if $p$”：if 后面的条件成立时，前面的结论成立。
• “$p$ only if $q$”：只有后者成立，前者才可能成立。

这里，$p$ 是 antecedent，$q$ 是 consequent。Conditional 要求的是：只要 $p$ 为真，$q$ 就必须为真。因此，它只有在 $p=1$ 且 $q=0$ 时才为假。$p$ 为假时，不论 $q$ 的真值如何，conditional 都为真；这称为 vacuous truth。

例如，“如果我付 1,000 dollars，你就给我送一杯咖啡”只有在我付了钱、咖啡却没送来时才为假。

Conditional 可以等价地写成

$$p\Rightarrow q\equiv\neg p\lor q.$$

Biconditional

Biconditional $p\Leftrightarrow q$ 表示两个 proposition 可以互相推出：

$$p\Leftrightarrow q \equiv(p\Rightarrow q)\land(q\Rightarrow p) \equiv(p\land q)\lor(\neg p\land\neg q) \equiv\neg(p\oplus q).$$

它恰好在 $p$ 和 $q$ 真值相同时为真。

对 “only if” 取 negation

校园 Wi-Fi 例子

设

• $W$：你可以接入校园 Wi-Fi；
• $S$：你是学生；
• $E$：你是员工。

陈述

只有你是学生或员工，才能接入校园 Wi-Fi。

写成符号就是

$$W\Rightarrow(S\lor E).$$

它的 negation 为

$$\begin{aligned} \neg[W\Rightarrow(S\lor E)] &\equiv\neg[\neg W\lor(S\lor E)]\\ &\equiv W\land\neg(S\lor E)\\ &\equiv W\land\neg S\land\neg E. \end{aligned}$$

Negation 只在 $W=1$、$S=0$ 且 $E=0$ 的那一行为真。用文字说就是：你既不是学生，也不是员工，却可以接入校园 Wi-Fi。