《离散数学及其应用》第一章·逻辑和证明 学习笔记
一、先导概念
- 命题：是一个陈述句，或真或假，但不能既真又假。
接下来我们字母表示命题变元，例如 p，q，r，s 等。后文所述真值可理解为命题的真假性，命题为真记作 T，命题为假记作 F。
- p的否定/逆命题：$\lnot p$ 或 $\overline{p}$ ，读作 “非 p”
| p | $\lnot p$ |
|---|---|
| T | F |
| F | T |
从真值表中可以看出，命题 p 和 命题 p 的否定真值相反。
- p，q 的合取命题（AND）：$p \bigwedge q$，读作 “p 并且 q”
| p | q | output |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
从真值表可以看出，当且仅当合取的两命题均为真时，结果为真。
- p，q 的析取命题（OR）：$p \bigvee q$，读作 “p 或 q”
| p | q | output |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
从真值表可以看出，只要两个合取的两命题有一个为真时，结果为真。
- p，q 的异或命题（XOR）：$p \bigoplus q$，读作 “p 异或 q”
| p | q | output |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
从真值表可以看出，当异或的两个命题中恰好只有一个为真（两命题的真值不同），结果为真。
- 条件语句：$p \rightarrow q$，读作 “如果 p，则 q”。我们通常将 p 称为 （前提）前件，将 q 称为（结论）后件。
| p | q | output |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
相比之前的概念，这个真值表可能较难理解，在此举一个例子：设 p 为命题 “天下雨”，命题 q 为 “我不去打球”。则条件语句 “$p \rightarrow q$” 可以翻译为 “如果天下雨，我就不去打球”。将不同的真值带入：
| p 的真值 | 命题 | q 的真值 | 命题 | output |
|---|---|---|---|---|
| T | 天下雨 | T | 我不去打球 | T |
| T | 天下雨 | F | 我去打球 | F |
| F | 天不下雨 | T | 我去打球 | T |
| F | 天不下雨 | F | 我不去打球 | T |
可以发现，只有当 p（前提） 的真值为 T ，q（结论） 的真值为 F，条件语句才为 F。
- 逆命题：$p \rightarrow q$ 和 $q \rightarrow p$ 互为逆命题，也就是交换前提和结论。
- 逆否命题： $p \rightarrow q$ 和 $\lnot q \rightarrow \lnot p$ 互为逆命题，也就是交换前提和结论，并且取条件和结论的逆命题。
- 反命题：$p \rightarrow q$ 和 $\lnot p \rightarrow \lnot q$ 互为反命题，也就是取条件和结论的逆命题。
以下为有关逆命题、逆否命题、反命题的一些结论：
- 原命题和逆否命题的真值相同
- 逆命题和反命题都不具有相同的真值
一般地，我们称两个总具有相同真值的复合命题为等价命题。同时，为表达命题的等价，我们同样也可以运用双条件语句。
- 双条件语句：$p \leftarrow\rightarrow q$，读作 “p 当且仅当 q”，也称 p 为 q 的充分必要条件。等价于 $(p \rightarrow q) \bigwedge (q \rightarrow p)$
| p | q | output |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
较为容易理解，因为双条件语句的定义是 p 和 q 等价，所以只有当 p 和 q 的真值相同时结果才为 T 。
至此我们介绍了部分逻辑运算符，我们希望你可以了解一下逻辑运算符的优先级：
| 运算符 | 优先级 |
|---|---|
| $\lnot$ | 1 |
| $\bigwedge$ | 2 |
| $\bigvee$ | 3 |
| $\rightarrow$ | 4 |
| $\leftarrow \rightarrow$ | 5 |
二、一些逻辑恒等式
| 等价式 | 解释 | 名称 |
|---|---|---|
| $p \bigwedge T \equiv p$ $p \bigvee F \equiv p$ |
恒等律 | |
| $p \bigvee T \equiv T$ $p \bigwedge F \equiv F$ |
支配律 | |
| $p \bigvee p \equiv p$ $p \bigwedge p \equiv p$ |
对于合取与析取的幂运算，结果仍为论元本身 | 幂等律 |
| $\lnot (\lnot p) \equiv p$ | 双重否定律 | |
| $p \bigvee q \equiv q \bigvee p$ $p \bigwedge q \equiv q \bigwedge p$ |
合取与析取满足交换律 | 交换律 |
| $(p \bigvee q) \bigvee r \equiv p \bigvee (q \bigvee r)$ $(p \bigwedge q) \bigwedge r \equiv p \bigwedge (q \bigwedge r)$ |
合取与析取满足结合律 | 结合律 |
| $(p \bigvee q) \bigwedge r \equiv (p \bigvee r) \bigwedge (q \bigvee r)$ $(p \bigwedge q) \bigvee r \equiv (p \bigwedge r) \bigvee (q \bigwedge r)$ |
合取与析取满足分配律 | 分配律 |
| $\lnot (p \bigwedge q) \equiv \lnot p \bigvee \lnot q$ $\lnot (p \bigvee q) \equiv \lnot p \bigwedge \lnot q$ |
将 $\lnot$ 分配到每个论元，合取与析取互换 | 德·摩根律 |
| $p \bigvee \lnot p \equiv T$ $p \bigwedge \lnot p \equiv F$ |
否定律 | |
| $p \bigvee (p \bigwedge q) \equiv p$ $p \bigwedge (p \bigvee q) \equiv p$ |
p 并 （p和q的交集）还是 p p 交 （p和q的并集）还是 p |
吸收律 |
| $p \rightarrow q \equiv \lnot p \bigvee q$ $p \rightarrow q \equiv \lnot q \rightarrow \lnot p$ $p \bigvee q \equiv \lnot p \rightarrow q$ $p \bigwedge q \equiv \lnot (p \rightarrow \lnot q)$ $\lnot(p \rightarrow q) \equiv p \bigwedge \lnot q$ $(p\rightarrow q) \bigwedge (p \rightarrow r) \equiv p \rightarrow (q \bigwedge r)$ $(p \rightarrow r) \bigwedge (q \rightarrow r) \equiv (p \bigvee q) \rightarrow r$ $(p \rightarrow q) \bigvee (p \rightarrow r) \equiv p \rightarrow (q \bigvee r)$ $(p \rightarrow r) \bigvee (q \rightarrow r) \equiv (p \bigwedge q) \rightarrow r$ |
$\rightarrow$ 可以理解为 $\lnot \bigvee$ 第三个和第四个需要牢记 |
条件命题的逻辑等价式 |
| $p \leftarrow \rightarrow q \equiv (p \rightarrow q) \bigwedge (q \rightarrow p)$ $p \leftarrow \rightarrow q \equiv \lnot p \leftarrow \rightarrow \lnot q$ $p \leftarrow \rightarrow q \equiv (p \bigwedge q) \bigvee (\lnot p \bigwedge \lnot q)$ $\lnot (p \leftarrow \rightarrow q) \equiv p \leftarrow \rightarrow \lnot q$ |
$\lnot$ 可以挪到双条件表达式的后项 | 双条件命题的逻辑等价式 |
三、谓词、量词
- 谓词
一般地，涉及 n 个变量 $x_1$，$x_2$，…，$x_n$ 的语句可以表示为 $P(x_1，x_2，…，x_n)$ ，我们将其称为命题函数 P 在 n 元组 ( $x_1$，$x_2$，…，$x_n$) 的值，P 也称为 n 元谓词。
量词：量词比命题演算中所有逻辑运算符的优先级都更高
- 全称量词：全体域均可使命题成立。用符号 $\forall$ 表示。
- 存在量词：存在一个个体使命题成立。用符号 $\exists$ 表示。
量化表达式的否定：$\forall x P(x) \equiv \exists x \lnot P(x)$
嵌套量词：一个量词出现在另一个量词的作用域中，例如 $\forall x \forall y (x + y = y + x)$
量词的顺序：量词的顺序十分重要，除非所有的量词均为全称量词或者存在量词。（言下之意：如果只有全称量词或存在量词，则可前后交换顺序）
嵌套量词的否定
$\lnot (\forall x \exists y (xy = 1)) = \exists x \lnot \exists y (xy = 1)$ (将否定词移入所有量词之中)
= $\exists x \forall y \lnot (xy = 1)$ = $\exists x \forall y \lnot (xy \not= 1)$
四、推理
- 推理规则：
| 名称 | 永真式 | 理解 |
|---|---|---|
| 假言推理 | $p \bigwedge ( p \rightarrow q)) \rightarrow q$ | 已知 p ，$p \rightarrow q$，可以推得 q |
| 取拒式 | $(\lnot q \bigwedge (p \rightarrow q)) \rightarrow \lnot p$ | 已知 $\lnot q$，$p \rightarrow q$，可以推得 $\lnot p$ |
| 假言三段论 | $((p \rightarrow q) \bigwedge (q \rightarrow r)) \rightarrow (p \rightarrow r)$ | 已知 $p \rightarrow q$，$q \rightarrow r$，可以推得 $p \rightarrow r$ |
| 析取三段论 | $((p \bigvee q) \bigwedge \lnot p) \rightarrow q$ | 已知 $p \bigvee q$，$\lnot p$，可以推得 q |
| 附加律 | $p \rightarrow (p \bigvee q)$ | 已知 p，可以推得 $p \bigvee q$ |
| 化简律 | $(p \bigwedge q) \rightarrow p$ | 已知 $p \bigwedge q$，可以推得 p |
| 合取律 | $((p) \bigwedge (q)) \rightarrow (p \bigwedge q)$ | 已知 p，q，可以推得 $p \bigwedge q$ |
| 消解律 | $((p \bigvee q) \bigwedge (\lnot p \bigwedge r)) \rightarrow (q \bigvee r)$ | 已知 $p \bigvee q$，$\lnot p \bigvee r$，可以推得 $q \bigvee r$ |
- 量化命题的推理规则：
- 全称实例：由 $\forall x P(x)$ 得出 $P(c)$
- 全称引入：由 论域中所有元素 c 都存在$P(c)$，得出 $\forall x P(x)$
- 存在实例：由 $\exists x P(x)$，得出 $P(c)$。但是 c 不知道确切的值，仅知道存在。
- 存在引入：由 $P(c)$，得出 $\exists x P(x)$
五、证明
直接证明法：（$p \rightarrow q$）
第一步：假设 p 为真；第二步：用推理规则构造；第三步：推导出 q 为真。
反证法：（$p \rightarrow q$ 等价于 $\lnot q \rightarrow \lnot p$）
第一步：假设 $\lnot q$；第二步：用推理规则构造；第三步：推导出 $\lnot p$ 为真。
空证明：如果能证明 p 为假，则我们就有了一个 $p \rightarrow q$ 的证明方法
平凡证明：如果能证明 p 为真，则我们也可以很快证明出 $p \rightarrow q$
归谬证明：如果我们能证明对于某个命题 r，$\lnot p \rightarrow (r \bigwedge \lnot r)$为真，则可以得出：p 是真的
等价证明法：为了证明双命题条件 $p \leftarrow \rightarrow q$，则需要证明 $p \rightarrow q$ 和 $q \rightarrow p$
唯一性证明：（存在性：P(c)）&&（唯一性：如果 $b \not= c$，则 P(b) 不成立）
参考书籍：《离散数学及其应用》Kenneth H. Rosen 著