[!info] related notes

• 所属 MOC: logic-moc
• 前置概念: propositional-logic-and-connectives
• 并列概念: validity-and-soundness
• 易混淆概念:
• 关系笔记:

真值表

一句话定义

真值表通过列出原子命题所有可能的真假组合，再逐步计算复合命题的真值，让“这个逻辑式到底在什么情况下成立”变得完全可见。

为什么需要真值表

自然语言很容易凭直觉判断，而复杂条件一多，直觉就不可靠。

例如：

(P → Q) ∧ ¬Q

它到底能不能推出 ¬P？

真值表可以把所有可能情况列出来，不靠感觉。

两个命题有几种组合

若有两个原子命题 P、Q，每个都有真/假两种状态，因此一共：

2² = 4 种

P	Q
真	真
真	假
假	真
假	假

三个原子命题就是：

2³ = 8 种

一般来说，n 个独立原子命题需要 2^n 行。

基本联结词

P	Q	¬P	P ∧ Q	P ∨ Q	P → Q	P ↔ Q
真	真	假	真	真	真	真
真	假	假	假	真	假	假
假	真	真	假	真	真	假
假	假	真	假	假	真	真

最值得熟记的不是整张表，而是：

• P ∧ Q：必须两个都真；
• P ∨ Q：至少一个真；
• P → Q：只有“P 真、Q 假”时为假；
• P ↔ Q：两边真假一致时为真。

用真值表验证一个有效推理

经典形式：

P → Q
P
∴ Q

这叫肯定前件（modus ponens）。

判断有效性时，不是只看结论，而是寻找：

有没有“所有前提都真，但结论假”的一行？

P	Q	P → Q	前提 P	结论 Q
真	真	真	真	真
真	假	假	真	假
假	真	真	假	真
假	假	真	假	假

唯一让两个前提都真的行是第一行，而结论也真，因此不存在反例行，所以形式有效。

验证一个无效推理

P → Q
Q
∴ P

也就是肯定后件。

看这一行：

P = 假
Q = 真

此时：

• P → Q 为真；
• Q 为真；
• P 为假。

于是我们找到了“前提全真、结论假”的情况，所以这个形式无效。

真值表还能做什么

判断重言式

如果一个公式在每一行都为真，它是重言式（tautology）。

例如：

P ∨ ¬P

经典逻辑中无论 P 真或假，整体都真。

判断矛盾式

如果一个公式每一行都为假，它是矛盾式（contradiction）。

例如：

P ∧ ¬P

判断逻辑等价

如果两个公式在所有行的真值都完全相同，它们逻辑等价。

例如德摩根律之一：

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

这在代码条件重构、布尔表达式化简里也非常实用。

通俗理解：穷举测试

程序员可以把真值表理解成：

对一个纯布尔规则做完整状态空间测试。

假设业务规则：

CanAccess = IsAdmin ∨ (IsOwner ∧ IsActive)

如果条件很关键，可以枚举所有真假组合，确认是否存在没想到的权限状态。

所以真值表和软件测试的思想非常接近：

所有可能输入
→ 计算输出
→ 查找反例

使用场景

• 检查一段条件推理是不是有效；
• 理解复杂 if 条件；
• 验证两个布尔表达式重构前后是否等价；
• 分析“如果……那么……”类自然语言推理；
• 理解数字电路和布尔代数的基础；
• 为权限、状态机和规则系统设计测试矩阵。

真值表的局限

命题逻辑只把整句话看成 P、Q。

它不能自然表达：

所有开发者都会使用某种工具。 小王是开发者。 因此小王会使用某种工具。

这里需要分析“所有”“小王”“是开发者”这些内部结构，必须进入谓词逻辑。

另外，当原子命题很多时，2^n 会快速爆炸。此时自然演绎、SAT 求解等方法更适合。

快速自测

不用完整画表，判断下面是否存在反例：

P → Q
¬Q
∴ ¬P

如果前提都真：

• ¬Q 真，所以 Q 假；
• 要让 P → Q 仍为真，在 Q 假时 P 只能假；
• 因此 ¬P 必真。

所以这是有效形式——否定后件（modus tollens）。

来源

• Open Logic Project, forall x: Calgary, Part III — Truth tables: https://forallx.openlogicproject.org/
• Stanford Introduction to Logic: https://logic.stanford.edu/intrologic/public/