命题逻辑：联结词、真值表与等值演算

本节导读

命题逻辑是离散数学的第一个单元，也是后面谓词逻辑、归结推理的基础。大纲对这一单元列了七条，本节讲前四条：基本概念与联结词、简单命题的形式化、等值演算、联结词的完备集；下一节讲范式与推理。

常见资料提到数学基础部分有形式化语句、正误判断、证明推导、填空几种题型，这一节的内容都会用到：把一句话写成公式是「形式化」，判断某个公式是不是重言式常以「正误判断」或「填空」出现，用等值演算证明两个公式等值就是「证明推导」。学完你应该能准确写出「只有……才……」「除非……否则……」的公式，会列真值表，并能一步一步写出等值演算的过程。

命题与联结词

能判断真假、而且只有一个真值的陈述句叫命题。「3 是素数」是真命题，「每个偶数都大于 5」是假命题；疑问句、命令句、感叹句不是命题，「x 大于 2」这种含变量、真假随 x 而定的句子也不是命题，「我正在说谎」这类悖论同样不是命题。真值用 1 表示真、0 表示假。

不能再分解的命题叫简单命题（原子命题），用 p、q、r 表示；用联结词连起来的叫复合命题。五个基本联结词的真值规定如下：

联结词	符号	读法	真值规定
否定	$\neg p$¬p	非 p	p 真则假，p 假则真
合取	$p \land q$p∧q	p 并且 q	只有两者都真时才真
析取	$p \lor q$p∨q	p 或 q（可兼）	只有两者都假时才假
蕴涵（条件）	$p \to q$p→q	如果 p 则 q	只有 p 真、q 假时才假
等价（双条件）	$p \leftrightarrow q$p↔q	p 当且仅当 q	两者真值相同时为真

蕴涵最容易出错：前件 p 为假时，$p \to q$p→q 一律为真，不管 q 是什么。可以这样理解——「如果下雨我就带伞」，没下雨时我带不带伞都不算违约。

简单命题的形式化

形式化（符号化）分三步：先找出原子命题并写明每个符号代表什么；再判断句子用了哪个联结词；最后写出公式，必要时加括号。日常说法与联结词的对应关系如下：

日常说法	公式
p 并且 q；虽然 p，但是 q；不但 p，而且 q	$p \land q$p∧q
p 或 q（两者可以同时成立）	$p \lor q$p∨q
p 或 q，二者只取其一（不可兼）	$(p \land \neg q) \lor (\neg p \land q)$(p∧¬q)∨(¬p∧q)
如果 p，那么 q；只要 p，就 q；p 仅当 q	$p \to q$p→q
只有 p，才 q	$q \to p$q→p
除非 p，否则 q	$\neg p \to q$¬p→q
p 当且仅当 q	$p \leftrightarrow q$p↔q

「只有 p，才 q」说的是 p 是 q 的必要条件，q 成立一定有 p，所以写成 $q \to p$q→p，箭头方向和「只要」正好相反。「除非 p，否则 q」意思是「不是 p 的话就 q」，写成 $\neg p \to q$¬p→q，它与 $p \lor q$p∨q 等值。不可兼的「或」也可以写成 $\neg(p \leftrightarrow q)$¬(p↔q)。

真值表与公式的类型

含 n 个命题变元的公式有 $2^n$2n 组赋值，真值表就有 $2^n$2n 行。列表时按二进制从 00…0 写到 11…1，先算内层子公式，再算外层。下面一张表对比三个公式：

$p$p	$q$q	$p \to q$p→q	$\neg p \lor q$¬p∨q	$q \to p$q→p
0	0	1	1	1
0	1	1	1	0
1	0	0	0	1
1	1	1	1	1

第三、四列每行都相同，说明 $p \to q$p→q 与 $\neg p \lor q$¬p∨q 等值；第五列与第三列不同，说明「如果 p 则 q」不能倒过来说成「如果 q 则 p」。

按真值表可以把公式分三类：所有赋值下都真的叫重言式（永真式）；所有赋值下都假的叫矛盾式（永假式）；至少有一组赋值使它为真的叫可满足式。重言式一定可满足，可满足式不一定是重言式。从真值表的角度看，n 个变元一共只有 $2^{2^n}$22n 种互不相同的真值函数，比如 3 个变元的真值表有 8 行，互不等值的公式就是 $2^8 = 256$28=256 种。

等值式与等值演算

如果 $A \leftrightarrow B$A↔B 是重言式，就说 A 与 B 等值，记作 $A \Leftrightarrow B$A⇔B。注意 $\Leftrightarrow$⇔ 是两个公式之间的关系，不是联结词。下面这些基本等值式要熟记（A、B、C 可以是任意公式）：

名称	等值式
双重否定律	$\neg\neg A \Leftrightarrow A$¬¬A⇔A
分配律	$A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)$A∨(B∧C)⇔(A∨B)∧(A∨C)；$A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)$A∧(B∨C)⇔(A∧B)∨(A∧C)
德摩根律	$\neg(A \lor B) \Leftrightarrow \neg A \land \neg B$¬(A∨B)⇔¬A∧¬B；$\neg(A \land B) \Leftrightarrow \neg A \lor \neg B$¬(A∧B)⇔¬A∨¬B
吸收律	$A \lor (A \land B) \Leftrightarrow A$A∨(A∧B)⇔A；$A \land (A \lor B) \Leftrightarrow A$A∧(A∨B)⇔A
零律与同一律	$A \lor 1 \Leftrightarrow 1$A∨1⇔1，$A \land 0 \Leftrightarrow 0$A∧0⇔0；$A \lor 0 \Leftrightarrow A$A∨0⇔A，$A \land 1 \Leftrightarrow A$A∧1⇔A
排中律与矛盾律	$A \lor \neg A \Leftrightarrow 1$A∨¬A⇔1；$A \land \neg A \Leftrightarrow 0$A∧¬A⇔0
蕴涵等值式	$A \to B \Leftrightarrow \neg A \lor B$A→B⇔¬A∨B
等价等值式	$A \leftrightarrow B \Leftrightarrow (A \to B) \land (B \to A)$A↔B⇔(A→B)∧(B→A)
假言易位	$A \to B \Leftrightarrow \neg B \to \neg A$A→B⇔¬B→¬A
输出律	$(A \land B) \to C \Leftrightarrow A \to (B \to C)$(A∧B)→C⇔A→(B→C)

此外还有交换律、结合律、幂等律，以及归谬论 $(A \to B) \land (A \to \neg B) \Leftrightarrow \neg A$(A→B)∧(A→¬B)⇔¬A。

等值演算靠两条定理：代入定理（重言式里同一个变元处处换成同一个公式，仍是重言式）和替换定理（公式里的一部分换成与它等值的公式，整体等值）。演算的常用套路是「先去掉蕴涵和等价，再用德摩根把否定推到变元前，最后用分配、吸收化简」。比如：

$(p \to q) \land (p \to r) \Leftrightarrow (\neg p \lor q) \land (\neg p \lor r) \Leftrightarrow \neg p \lor (q \land r) \Leftrightarrow p \to (q \land r)$(p→q)∧(p→r)⇔(¬p∨q)∧(¬p∨r)⇔¬p∨(q∧r)⇔p→(q∧r)

三步依次用了蕴涵等值式、分配律、蕴涵等值式。考场上每一步后面都写上所用等值式的名字。

联结词的完备集

如果任何一个真值函数都能用某个联结词集合里的联结词表示，这个集合就叫完备集。$\{\neg, \land, \lor\}${¬,∧,∨} 是完备集（主范式就是证明）；再利用 $p \lor q \Leftrightarrow \neg(\neg p \land \neg q)$p∨q⇔¬(¬p∧¬q)、$p \to q \Leftrightarrow \neg(p \land \neg q)$p→q⇔¬(p∧¬q) 可知 $\{\neg, \land\}${¬,∧}、$\{\neg, \lor\}${¬,∨}、$\{\neg, \to\}${¬,→} 也是完备集。

与非 $p \uparrow q \Leftrightarrow \neg(p \land q)$p↑q⇔¬(p∧q) 和或非 $p \downarrow q \Leftrightarrow \neg(p \lor q)$p↓q⇔¬(p∨q) 单独一个就是完备集，因为 $\neg p \Leftrightarrow p \uparrow p$¬p⇔p↑p，$p \land q \Leftrightarrow (p \uparrow q) \uparrow (p \uparrow q)$p∧q⇔(p↑q)↑(p↑q)。反过来，只含 $\land, \lor, \to, \leftrightarrow$∧,∨,→,↔ 的集合都不完备：所有变元都取 1 时，这些联结词算出来全是 1，永远表示不出 $\neg p$¬p。

易错提醒

• ❌ 「只有 p，才 q」写成 $p \to q$p→q。✅ 写成 $q \to p$q→p。因为 p 是必要条件，q 成立才能推出 p。

• ❌ 认为前件为假时蕴涵式的真值「无法确定」。✅ 前件为假，蕴涵式一律为真。因为蕴涵只在「前真后假」这一种情况下为假。

• ❌ 把 $\Leftrightarrow$⇔ 当成和 $\leftrightarrow$↔ 一样的联结词写进公式里。✅ $\Leftrightarrow$⇔ 表示两个公式等值，是关系符号。因为 $A \Leftrightarrow B$A⇔B 的意思是「$A \leftrightarrow B$A↔B 是重言式」。

• ❌ 证明不是重言式时只说「不一定成立」。✅ 给出一组使公式为假的具体赋值。因为反例才是不是重言式的证据。

• ❌ 等值演算一步跳很远，不写依据。✅ 每一步只用一两个等值式，并写明名称。因为证明推导题看的就是每一步的依据。

例题精讲

例题 1（形式化语句）

设 p：今天下雨，q：比赛照常进行。把下面两句符号化：（1）只有不下雨，比赛才照常进行；（2）比赛照常进行当且仅当不下雨。

答题要点示范：（1）「不下雨」是必要条件，写成 $q \to \neg p$q→¬p；（2）写成 $q \leftrightarrow \neg p$q↔¬p。

点评：先写明 p、q 的含义再写公式，是形式化题的基本格式。（1）最容易写反成 $\neg p \to q$¬p→q，那是「只要不下雨，比赛就照常进行」。

例题 2（证明推导）

用等值演算证明：$\neg(p \lor q) \lor (\neg p \land q) \Leftrightarrow \neg p$¬(p∨q)∨(¬p∧q)⇔¬p。

答题要点示范：

$\neg(p \lor q) \lor (\neg p \land q) \Leftrightarrow (\neg p \land \neg q) \lor (\neg p \land q) \Leftrightarrow \neg p \land (\neg q \lor q) \Leftrightarrow \neg p \land 1 \Leftrightarrow \neg p$¬(p∨q)∨(¬p∧q)⇔(¬p∧¬q)∨(¬p∧q)⇔¬p∧(¬q∨q)⇔¬p∧1⇔¬p

依次用了德摩根律、分配律、排中律、同一律。

点评：看到两个合取式里有公共的 $\neg p$¬p，就想到用分配律把它提出来。

例题 3（正误判断）

判断：$(p \to q) \to p$(p→q)→p 是重言式。

答案：错误。取 p 为 0、q 为 0，则 $p \to q$p→q 为 1，整个公式是 $1 \to 0$1→0，真值为 0。

点评：判断「是重言式」为错，最简洁的理由就是一组成假赋值。

本节小结

• 命题是有唯一真值的陈述句；五个联结词中，蕴涵只在前真后假时为假，等价在两边同真值时为真。
• 形式化：先写符号含义；「只有 p 才 q」是 $q \to p$q→p，「除非 p 否则 q」是 $\neg p \to q$¬p→q。
• n 个变元的真值表有 $2^n$2n 行；公式分重言式、矛盾式、可满足式三类。
• 等值演算靠代入定理和替换定理，每一步写清用的是哪个等值式。
• $\{\neg, \land, \lor\}${¬,∧,∨}、$\{\neg, \to\}${¬,→}、$\{\uparrow\}${↑}、$\{\downarrow\}${↓} 等是完备集；不含否定类联结词的集合不完备。