从真值表到卡诺图

命题逻辑公式的直观化简法

祝瑞

真值表：从句法到语义

对于任何一个给定的命题逻辑公式（句法），我们都可以通过真值表来精确地确定它的性质（语义）。

p q r p ∧ q (p ∧ q) → r
1 1 1 1 1
1 1 0 1 0
1 0 1 0 1
1 0 0 0 1
0 1 1 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 0 1

逆向工程：从语义到句法

现在，如果我们只知道一个真值表的“结果”，能否反向推导出它所对应的逻辑公式呢？

p q r Unknown Formula
1 1 1 0
1 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 0

卡诺图：真值表的“升维”

p q r F
1 1 1 0
1 1 0 1
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 0
p \ qr 00 01 11 10
0 0 1 0 0
1 1 0 0 1
  • 红格子: p=1, r=0 ➞ p ∧ ¬r
  • 蓝格子: p=0, q=0, r=1 ➞ ¬p ∧ ¬q ∧ r

最终最简析取范式：

$$ F = (p \land \lnot r) \lor (\lnot p \land \lnot q \land r) $$

卡诺图练习（一）

p \ qr 00011110
0 0100
1 1 1 1 1
  • 红色背景的格子: p=1 ➞ p
  • 蓝色背景的格子: q=0, r=1 ➞ ¬q ∧ r

最终最简析取范式： $$ F = p \lor (\lnot q \land r) $$

卡诺图练习（二）

p \ qr 00011110
0 1 1 1 1
1 0011
  • 红色背景的格子: q=1 ➞ q
  • 蓝色背景的格子: p=0 ➞ ¬p

最终最简析取范式：

$$ F = \lnot p \lor q $$

卡诺图的实用意义

逻辑与算法层面

  • 公式化简

    以最直观、系统的方式找到布尔函数的最简析取范式，降低逻辑复杂性。

  • 辅助自动推理

    其思想是奎因-麦克拉斯基算法（Quine–McCluskey algorithm）等自动逻辑化简程序的基础。

硬件与工程层面

真值表 化简 卡诺图 最简逻辑表达式 最优逻辑门电路
  • 数字电路设计

    最直接的应用。更简单的公式意味着使用更少的逻辑门，从而降低芯片的成本、功耗和延迟。

思考与练习

  • 从卡诺图看，本质不同的3变量命题逻辑公式有多少个？

    提示：一个3变量卡诺图有8个格子，每个格子可以填0或1。每一种独特的填写方式，就对应一个逻辑上不等价的公式。这是一个排列组合问题。

  • 我们只学习了3变量卡诺图。请思考或查阅资料，4变量的卡诺图（4x4网格）是如何操作的？5变量呢？（提示：维度越高，“相邻”关系越复杂。）

  • 我们总是在圈1，那0有什么用呢？

  1. 练习一：化简下面的公式：

    p ∧ (¬q ∨ (¬r → p))

  2. 练习二：化简下面的公式：

    (¬p∧q∧r) ∨ (¬p∧q∧¬r) ∨ (p∧¬q∧¬r) ∨ (p∧¬q∧r) ∨ (p∧q∧r) ∨ (p∧q∧¬r)