命题逻辑

命题逻辑（Propositional Logic）是数理逻辑的基础，研究命题之间的逻辑关系。它是人类思维的基本形式，也是计算机科学中逻辑推理、程序验证、人工智能等领域的理论基础。

什么是命题？

命题（Proposition）是一个能够判断真假的陈述句。每个命题要么为真（True，记为 T 或 1），要么为假（False，记为 F 或 0），不存在第三种可能。

命题的判断标准

判断一个语句是否为命题，需要满足两个条件：

1. 是陈述句：不是疑问句、祈使句或感叹句
2. 有确定的真值：能够判断真假，虽然可能暂时不知道

例子分析

是命题的例子：

• "北京是中国的首都。" → 真命题
• "2 + 2 = 5。" → 假命题
• "地球上有生命存在。" → 真命题（虽然历史上曾不确定）
• "明天会下雨。" → 命题（虽然现在不知道真假，但明天之后有确定答案）

不是命题的例子：

• "今天天气怎么样？" → 疑问句，不是命题
• "请关门。" → 祈使句，不是命题
• "这句话是假的。" → 悖论，没有确定的真值
• "x + 1 = 2。" → 真值取决于 x，不是命题（但称为命题函数或谓词）

命题的表示

在逻辑推理中，我们用小写字母 $p$, $q$, $r$, $s$ 等表示命题。例如：

• $p$：今天下雨
• $q$：明天晴天

这种抽象表示让我们关注命题之间的逻辑关系，而不是具体内容。

逻辑联结词

单个命题是简单的，但我们可以通过逻辑联结词（Logical Connectives）将多个命题组合成复合命题。

否定（Negation）

定义：命题 $p$ 的否定记作 $\neg p$（读作"非 p"），表示对 $p$ 的否定。

真值表：

$p$	$\neg p$
T	F
F	T

理解：如果 $p$ 为真，则 $\neg p$ 为假；如果 $p$ 为假，则 $\neg p$ 为真。

例子：

• $p$："今天是周一。"
• $\neg p$："今天不是周一。"

注意：在自然语言中，否定有时会有歧义。例如"不是所有学生都喜欢数学"与"所有学生都不喜欢数学"含义不同。在逻辑中，否定是对整个命题的否定。

合取（Conjunction）

定义：命题 $p$ 和 $q$ 的合取记作 $p \land q$（读作"p 且 q"），表示 $p$ 和 $q$ 同时为真。

真值表：

$p$	$q$	$p \land q$
T	T	T
T	F	F
F	T	F
F	F	F

理解：只有当 $p$ 和 $q$ 都为真时，$p \land q$ 才为真。

例子：

• $p$："今天是周一。"
• $q$："天气晴朗。"
• $p \land q$："今天是周一且天气晴朗。"

析取（Disjunction）

定义：命题 $p$ 和 $q$ 的析取记作 $p \lor q$（读作"p 或 q"），表示 $p$ 和 $q$ 至少有一个为真。

真值表：

$p$	$q$	$p \lor q$
T	T	T
T	F	T
F	T	T
F	F	F

理解：只要 $p$ 或 $q$ 有一个为真，$p \lor q$ 就为真。这是"可兼或"（inclusive or）。

例子：

• $p$："我会说英语。"
• $q$："我会说法语。"
• $p \lor q$："我会说英语或法语。"（可能两种都会）

注意：日常语言中的"或"有时是"不可兼或"（exclusive or）。例如"你要么去北京，要么去上海"，意味着只能选一个。这在逻辑中用异或（XOR）表示，记作 $p \oplus q$ 或 $p \veebar q$。

异或真值表：

$p$	$q$	$p \oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

蕴含（Implication）

定义：命题 $p$ 蕴含 $q$ 记作 $p \rightarrow q$（读作"如果 p，则 q"或"p 蕴含 q"）。$p$ 称为前件（antecedent），$q$ 称为后件（consequent）。

真值表：

$p$	$q$	$p \rightarrow q$
T	T	T
T	F	F
F	T	T
F	F	T

理解：蕴含的真值表常常让人困惑。关键在于理解"$p \rightarrow q$"的含义是"如果 $p$ 为真，则 $q$ 必须为真"。

• 当 $p$ 为真且 $q$ 为真时，承诺得到履行，所以 $p \rightarrow q$ 为真。
• 当 $p$ 为真且 $q$ 为假时，承诺被违反，所以 $p \rightarrow q$ 为假。
• 当 $p$ 为假时，无论 $q$ 为真还是假，承诺都没有被违反（因为前提不成立），所以 $p \rightarrow q$ 为真。这称为"善意推定"或"空真"（vacuously true）。

例子：

• $p$："下雨。"
• $q$："地湿。"
• $p \rightarrow q$："如果下雨，则地湿。"

如果没下雨，无论地是否湿，这个陈述都不算说错。

蕴含的其他表述：

在自然语言中，$p \rightarrow q$ 可以有多种表述方式：

• "如果 p，那么 q"
• "p 蕴含 q"
• "p 是 q 的充分条件"
• "q 是 p 的必要条件"
• "只有 q，才 p"（注意顺序）
• "除非 q，否则非 p"

双条件（Biconditional）

定义：命题 $p$ 和 $q$ 的双条件记作 $p \leftrightarrow q$（读作"p 当且仅当 q"），表示 $p$ 和 $q$ 有相同的真值。

真值表：

$p$	$q$	$p \leftrightarrow q$
T	T	T
T	F	F
F	T	F
F	F	T

理解：$p \leftrightarrow q$ 等价于 $(p \rightarrow q) \land (q \rightarrow p)$。它表示 $p$ 和 $q$ 互为充分必要条件。

例子：

• $p$："三角形是等边三角形。"
• $q$："三角形的三个角相等。"
• $p \leftrightarrow q$："三角形是等边三角形当且仅当它的三个角相等。"

复合命题的真值

构造真值表

对于任意复合命题，我们可以构造真值表来确定其在所有可能情况下的真值。

步骤：

1. 确定命题中所有原子命题，列出它们的所有真值组合
2. 从内到外，逐步计算每个子命题的真值
3. 最终得到整个命题的真值

例子：构造 $(p \lor q) \rightarrow (p \land q)$ 的真值表

$p$	$q$	$p \lor q$	$p \land q$	$(p \lor q) \rightarrow (p \land q)$
T	T	T	T	T
T	F	T	F	F
F	T	T	F	F
F	F	F	F	T

命题的等价形式

某些命题虽然形式不同，但真值表完全相同，这些命题称为逻辑等价。

常见的等价关系：

德摩根律（De Morgan's Laws）：

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

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

理解：

• "不是（p 且 q）" 等价于 "非 p 或非 q"
• "不是（p 或 q）" 等价于 "非 p 且非 q"

例子：

• $\neg$("他会英语且会法语") $\equiv$ "他不会英语或不会法语"
• $\neg$("今天下雨或下雪") $\equiv$ "今天不下雨且不下雪"

蕴含的等价形式：

$p \rightarrow q \equiv \neg p \lor q$

这意味着"如果 p，则 q" 等价于 "非 p 或 q"。

逆否命题：

$p \rightarrow q \equiv \neg q \rightarrow \neg p$

这是证明蕴含命题的重要方法：通过证明其逆否命题。

分配律：

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

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

吸收律：

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

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

逻辑等价与蕴含

逻辑等价

两个命题 $P$ 和 $Q$ 逻辑等价，记作 $P \equiv Q$ 或 $P \Leftrightarrow Q$，当且仅当它们的真值表完全相同。

验证方法：构造两个命题的真值表，比较每一行的真值。

例子：验证 $p \rightarrow q \equiv \neg p \lor q$

$p$	$q$	$\neg p$	$p \rightarrow q$	$\neg p \lor q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

两个命题在所有情况下的真值相同，因此等价。

重言式、矛盾式与可满足式

重言式（Tautology）：在所有可能的真值赋值下都为真的命题。

例子：$p \lor \neg p$（排中律）

$p$	$\neg p$	$p \lor \neg p$
T	F	T
F	T	T

矛盾式（Contradiction）：在所有可能的真值赋值下都为假的命题。

例子：$p \land \neg p$（矛盾律）

$p$	$\neg p$	$p \land \neg p$
T	F	F
F	T	F

可满足式（Contingency）：在某些真值赋值下为真，在某些真值赋值下为假。

例子：$p \lor q$

$p$	$q$	$p \lor q$
T	T	T
T	F	T
F	T	T
F	F	F

逻辑蕴含

命题 $P$ 逻辑蕴含命题 $Q$，记作 $P \models Q$，当且仅当所有使 $P$ 为真的赋值也使 $Q$ 为真。

注意区分：

• $P \rightarrow Q$ 是一个命题，表示"如果 P 则 Q"
• $P \models Q$ 是一个元语言陈述，表示"从 P 可以推出 Q"

关系：$P \models Q$ 当且仅当 $P \rightarrow Q$ 是重言式。

推理规则

推理规则是从已知命题推出新命题的规则。正确的推理规则保证：如果前提为真，则结论必然为真。

基本推理规则

假言推理（Modus Ponens）：

$\frac{p \rightarrow q, \quad p}{\therefore q}$

含义：如果 $p \rightarrow q$ 为真，且 $p$ 为真，则 $q$ 必然为真。

例子：

• 前提1：如果下雨，则地湿。
• 前提2：下雨了。
• 结论：地湿。

拒取式（Modus Tollens）：

$\frac{p \rightarrow q, \quad \neg q}{\therefore \neg p}$

含义：如果 $p \rightarrow q$ 为真，且 $q$ 为假，则 $p$ 必然为假。

例子：

• 前提1：如果下雨，则地湿。
• 前提2：地没湿。
• 结论：没下雨。

假言三段论（Hypothetical Syllogism）：

$\frac{p \rightarrow q, \quad q \rightarrow r}{\therefore p \rightarrow r}$

含义：蕴含关系具有传递性。

例子：

• 前提1：如果学习努力，则成绩好。
• 前提2：如果成绩好，则能上好大学。
• 结论：如果学习努力，则能上好大学。

析取三段论（Disjunctive Syllogism）：

$\frac{p \lor q, \quad \neg p}{\therefore q}$

含义：如果 $p$ 或 $q$ 为真，且 $p$ 为假，则 $q$ 必然为真。

附加规则（Addition）：

$\frac{p}{\therefore p \lor q}$

含义：如果 $p$ 为真，则 $p \lor q$ 为真（无论 $q$ 是什么）。

化简规则（Simplification）：

$\frac{p \land q}{\therefore p}$

含义：如果 $p$ 且 $q$ 为真，则 $p$ 为真。

合取规则（Conjunction）：

$\frac{p, \quad q}{\therefore p \land q}$

含义：如果 $p$ 为真且 $q$ 为真，则 $p \land q$ 为真。

推理的有效性

一个推理是有效的，当且仅当不可能出现前提都为真而结论为假的情况。

验证方法：

1. 将前提和结论表示为命题公式
2. 构造蕴含式 $(P_1 \land P_2 \land \ldots \land P_n) \rightarrow C$
3. 如果该蕴含式是重言式，则推理有效

例子：验证以下推理是否有效

• 前提1：如果下雨，则比赛取消。($p \rightarrow q$)
• 前提2：比赛没有取消。($\neg q$)
• 结论：没有下雨。($\neg p$)

验证 $(p \rightarrow q) \land \neg q \rightarrow \neg p$ 是否为重言式：

$p$	$q$	$p \rightarrow q$	$\neg q$	$(p \rightarrow q) \land \neg q$	$\neg p$	$(p \rightarrow q) \land \neg q \rightarrow \neg p$
T	T	T	F	F	F	T
T	F	F	T	F	F	T
F	T	T	F	F	T	T
F	F	T	T	T	T	T

该蕴含式是重言式，推理有效。

范式

范式是命题公式的标准形式，便于判断公式的性质和进行等价变换。

合取范式（CNF）

合取范式（Conjunctive Normal Form）是若干个简单析取式的合取。

形式：$(A_1 \lor B_1 \lor \ldots) \land (A_2 \lor B_2 \lor \ldots) \land \ldots$

例子：$(p \lor q) \land (\neg p \lor r) \land (q \lor r)$

析取范式（DNF）

析取范式（Disjunctive Normal Form）是若干个简单合取式的析取。

形式：$(A_1 \land B_1 \land \ldots) \lor (A_2 \land B_2 \land \ldots) \lor \ldots$

例子：$(p \land q) \lor (\neg p \land r) \lor (q \land r)$

转换方法

任何命题公式都可以转换为等价的 CNF 或 DNF：

1. 消除 $\rightarrow$ 和 $\leftrightarrow$：

   • $p \rightarrow q \equiv \neg p \lor q$
   • $p \leftrightarrow q \equiv (\neg p \lor q) \land (\neg q \lor p)$

2. 将 $\neg$ 移到原子命题前（德摩根律）

3. 使用分配律整理形式

例子：将 $p \rightarrow (q \land r)$ 转换为 CNF

$p \rightarrow (q \land r) \equiv \neg p \lor (q \land r) \equiv (\neg p \lor q) \land (\neg p \lor r)$

应用实例

逻辑电路

数字电路的基础就是命题逻辑。每个逻辑门对应一个逻辑运算：

• 与门（AND gate）→ 合取 $\land$
• 或门（OR gate）→ 析取 $\lor$
• 非门（NOT gate）→ 否定 $\neg$

例子：设计一个投票电路，三人投票，超过半数通过。

设 $A$, $B$, $C$ 分别表示三人投赞成票，输出 $F$ 表示通过：

$F = (A \land B) \lor (A \land C) \lor (B \land C)$

程序验证

在程序正确性证明中，命题逻辑用于描述程序状态和验证条件。

例子：验证分支语句

if (x > 0) {
    y = x;
} else {
    y = -x;
}
// 断言：y >= 0

逻辑验证：

• 如果 $x > 0$，则 $y = x > 0$，所以 $y \geq 0$
• 如果 $x \leq 0$，则 $y = -x \geq 0$

两种情况下 $y \geq 0$ 都成立，程序正确。

知识表示

在人工智能中，命题逻辑用于知识表示和自动推理。

例子：简单的专家系统规则

• 规则1：如果发烧且咳嗽，则可能是感冒。
• 规则2：如果是感冒，则建议休息。

设：

• $p$：发烧
• $q$：咳嗽
• $r$：感冒
• $s$：建议休息

逻辑表示：

• $p \land q \rightarrow r$
• $r \rightarrow s$

如果已知发烧且咳嗽，则可推出建议休息。

小结

本章介绍了命题逻辑的核心概念：

• 命题是能判断真假的陈述句
• 逻辑联结词将简单命题组合成复合命题
• 真值表是确定复合命题真值的基本工具
• 逻辑等价的两个命题具有相同的真值表
• 推理规则是从前提推出结论的保证正确的模式
• 范式是命题公式的标准形式

命题逻辑是谓词逻辑和更高级逻辑系统的基础。下一章将学习谓词逻辑，引入量词的概念，处理更复杂的逻辑问题。