离散数学学到第三章，很多同学第一次被“范式”这个词卡住。我当时复习命题逻辑的时候也在这个地方反复绕了很久：明明一个公式已经能算真值了，为什么还要把它变成析取范式、合取范式、主析取范式、主合取范式，这四样东西到底有什么用？等把这块啃下来回头看，才发现范式这一节不只是“会算”就行，它其实是整个命题逻辑从“求真假”走向“做推理”的枢纽，后面学谓词逻辑、推理理论、数字电路，全都要从这里接上。这篇笔记就把我自己梳理清楚的内容完整写出来，从“范式是什么”到“怎么求”再到“学了能干什么”，直接用 (p→q)↔r 这类公式从头走一遍。适合正在学离散数学、准备期末复习，或者工作中要接触逻辑推理、电路设计想补基础的人。
1. 先搞懂：范式到底在解决什么问题
1.1 逻辑表达式为什么需要“规范化”
先说一个最简单的例子：(p→q) 和 (¬p∨q) 从真值表看完全一样，但写法完全不同。如果再混入等价联结词、吸收率、分配率，同一个逻辑含义能写出十几种看起来毫不相关的表达式。问题就来了：如果两个表达式长得不一样，我们怎么确定它们逻辑等价？如果表达式特别长，怎么知道它到底是永真还是永假？
解决这类问题的通用思路就是“规范化”：把千奇百怪的表达式统一转成少数几种标准形态，再在这些形态里做比较和判断。范式就是命题逻辑里的标准形态，它有两种基本类型，析取范式（DNF）和合取范式（CNF）。
可以和生活里的事情做个类比：你要比较两段文字表达的意思是否一样，第一反应不是逐字对比，而是先提炼出“中心思想”，再比中心思想。范式就相当于给逻辑表达式做“中心思想提取”，只不过它提取出来的不是语义，而是一套完全机械化的标准书写格式。
1.2 析取范式与合取范式的定义与本质
先给定义，不用背，上面理解清楚之后这定义其实是自然结论。
一个“简单合取式”是若干个命题变元或其否定用“且（∧）”连接起来的式子，比如 (p∧¬q) 就是一个简单合取式。若干个简单合取式再用“或（∨）”连起来，得到一个“析取范式”，形如 (p∧¬q) ∨ (¬p∧r) ∨ q。反过来，若干个“简单析取式”用“且（∧）”连起来，得到“合取范式”，形如 (p∨¬q) ∧ (¬p∨r) ∧ q，这里 (p∨¬q) 就是简单析取式。
为什么任何命题公式都能化成这两种形态？背后的支撑是等价等值式里的三组核心工具：蕴含等值式 A→B≡¬A∨B 用于消去蕴含；等价等值式 A↔B≡(¬A∨B)∧(A∨¬B) 用于消去等价；德摩根律 ¬(A∧B)≡¬A∨¬B、¬(A∨B)≡¬A∧¬B 用于把否定号一层层“压”到单个变元上。最后再用分配律展开，就可以把表达式整理成范式。
这里插一句很多人会忽略的点：范式是“同类标准形态”，但它不一定是“唯一形态”。同一个公式可能对应多个不同的析取范式，可能一个更短、一个更长。如果我们想要唯一的标准形态，那就得升级到主范式，这个概念第三节再展开。
1.3 注意：数据库BCNF这些“范式”不是同一个东西
网上搜“范式”的时候，出来一堆“数据库范式”“BCNF范式”“反范式设计”，很多同学一下就懵了。这里要专门澄清一下：“关系数据库中的范式”讨论的是表结构的冗余和更新异常问题，解决的是“数据表设计合不合理”；“心理学里的stroop范式”说的是实验设计模式；“经济学范式”说的是分析框架。只有离散数学里的“范式”才是纯粹的逻辑表达式标准形态。它们只是中文译名撞了车，数学内涵完全不是一个东西。
不过这倒提示了一件事：学任何概念，先认准语境，再看定义。如果你是在离散数学课上听到“范式”，那讨论的必然是命题演算。如果是在数据库课程里听到“范式”，那讨论的是表结构。两个都逃不掉的是，它们本质上都在做同一件事——用一个统一标准去衡量对象是否“合格”，只是对象不同。
2. 最常用的两种求法：真值表法和等值演算法
2.1 真值表法：从真值表直接读出范式
对初学者来说，真值表法是最直观、最不容易错的方法，因为它本质上是“查表出结果”。
操作分两步。第一步先列真值表，把公式在所有赋值下的真值写出来。第二步分两种目标：如果要求析取范式，就把所有使公式真值为1的赋值挑出来，每个赋值写成一个“合取式”，再把这些合取式全部用∨连接；如果要求合取范式，就把所有使公式真值为0的赋值挑出来，每个赋值写成一个“析取式”，再用∧连接。
关键是每个赋值怎么对应一个子句。有人总是搞反，我提供一个不容易忘的口诀：析取范式是“为真的情况逐条罗列”，合取范式是“为假的情况逐条拒绝”。对于使结果为1的某个赋值，比如 p=0、q=1 这一行要写成 (¬p∧q)；对使结果为0的某个赋值，比如 p=1、q=1 这一行要写成 (¬p∨¬q)。原理不复杂：p=0 时 p 为假，要让整个合取式在“这个赋值下”为真，必须写 ¬p；要让整个析取式在“这个赋值下”为假，也必须写 ¬p。一个手动补全为真，一个手动制造为假，方向不同，根源是合取式和析取式的真值特性不同。
2.2 等值演算法：机械化流程
如果真值表法是“查表法”，等值演算法就是“变形法”，它不依赖穷举，而是靠等值式一步一步把原公式改写成目标形态。好处是能处理变元很多、真值表很长的公式，缺点是对等值式熟练度要求高。
流程统一是四步。第一步消去蕴含和等价：把 A→B 换成 ¬A∨B，把 A↔B 换成 (¬A∨B)∧(A∨¬B)，或者先把它拆成 (A→B)∧(B→A) 再消去。第二步把否定号内移：用德摩根律把 ¬(A∨B) 变成 (¬A∧¬B)，把 ¬(A∧B) 变成 (¬A∨¬B)，双重否定 ¬¬A 直接删掉。第三步用分配律展开：求DNF时反复用 A∧(B∨C)≡(A∧B)∨(A∧C)，求CNF时反复用 A∨(B∧C)≡(A∨B)∧(A∨C)。第四步用幂等律、吸收律、矛盾律、同一律做一些化简。
注意第三步是最容易翻车的地方：求析取范式时，∧ 对 ∨ 分配；求合取范式时，∨ 对 ∧ 分配。两个方向完全相反，下笔之前先确认自己现在求的是哪一种，否则很可能写着写着就串了。
2.3 完整案例：(p→q)↔r 的DNF/CNF求解
光说定义不过瘾，拿一个考试高频公式 (p→q)↔r 完整走一遍。先看真值表：
| p | q | r | p→q | (p→q)↔r |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
真值表法直接读：成真赋值是 001、011、100、111，所以一个析取范式是 (¬p∧¬q∧r) ∨ (¬p∧q∧r) ∨ (p∧¬q∧¬r) ∨ (p∧q∧r)。成假赋值是 000、010、101、110，所以一个合取范式是 (p∨q∨r) ∧ (p∨¬q∨r) ∧ (¬p∨q∨¬r) ∧ (¬p∨¬q∨r)。
再用等值演算法验算一次。先把等价消去：
(p→q)↔r ≡ ((¬p∨q)→r) ∧ (r→(¬p∨q)) ≡ (¬(¬p∨q)∨r) ∧ (¬r∨¬p∨q) ≡ ((p∧¬q)∨r) ∧ (¬r∨¬p∨q)
要化成合取范式，继续对第一项做 ∨ 对 ∧ 的分配，注意第一项已经是 (A∨r) 其中 A=(p∧¬q)，对它分配得到 (p∨r)∧(¬q∨r)，所以整体是 (p∨r)∧(¬q∨r)∧(¬r∨¬p∨q)。细看其实和我上面用真值表写出的主合取范式还不太一样，说明普通合取范式确实不是唯一的，但逻辑等价性没问题。这就直观验证了“范式是标准形态，但不一定唯一”这件事。
其实到这一步，大部分同学已经能应付作业了。但考试里通常不止要求“任意范式”，而是直接要求“主范式”，那就是下一节的内容。
3. 主范式：把公式变成唯一编码
3.1 极小项与主析取范式
刚才说过，普通范式不唯一，这给“两个公式是否等价”的判断带来了麻烦。为了得到一个唯一的“标准编码”，就要引入主范式。构造主范式需要一个新概念：极小项。
n 个命题变元可以组成 2^n 个极小项，每个极小项都是 n 个变元或其否定的合取。以两个变元 p、q 为例，极小项共有四个：¬p∧¬q、¬p∧q、p∧¬q、p∧q。它们可以看作是对变元赋值模式的“穷举”：每个赋值恰好让一个极小项为真，其它极小项都为假。这个性质和二进制编码高度对应，所以通常把变元看成一个二进制位，变元本身对应1，否定对应0，按 (p,q,r) 的顺序编码。比如赋值 011 对应的极小项就是 (¬p∧q∧r)，它的下标是二进制 011 的十进制值 3，记作 m₃。
主析取范式就是把公式所有成真赋值对应的极小项用∨连接起来。上节例子 (p→q)↔r 的成真赋值是 001、011、100、111，对应极小项 m₁、m₃、m₄、m₇，因此主析取范式是 m₁∨m₃∨m₄∨m₇，展开写就是 (¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧q∧r)。这里有个很重要的性质：一个公式的主析取范式是唯一的。因为成真赋值集合唯一，对应的极小项集合也唯一。
3.2 极大项与主合取范式
极大项和极小项完全对偶：n 个变元的极大项也有 2^n 个，每个极大项都是 n 个变元或其否定的析取，并且每个赋值恰好让一个极大项为假。编码规则也相反：变元本身对应0，否定对应1，因为极大项要为假，变元为1时必须取 ¬p，变元为0时必须取 p。于是赋值 011 对应的极大项是 (p∨¬q∨¬r)，记作 M₃，下标同样是二进制值。
主合取范式就是把所有成假赋值对应的极大项用∧连接起来。继续看 (p→q)↔r，成假赋值是 000、010、101、110，所以主合取范式是 M₀∧M₂∧M₅∧M₆，展开就是 (p∨q∨r)∧(p∨¬q∨r)∧(¬p∨q∨¬r)∧(¬p∨¬q∨r)。
到这里可以总结一个极其实用的规律：主析取范式统计“哪些赋值为真”，主合取范式统计“哪些赋值为假”。一个公式有 n 个变元，那么极小项数量和极大项数量加起来一定是 2^n。如果主析取范式里有 k 个极小项，主合取范式里就一定有 2^n−k 个极大项。这个互补关系后面做转换题非常有用。
3.3 两套主范式如何互转
很多题目会要求“先求主析取范式，再写出主合取范式”，或者反过来。转换方法有两种，都很快。
方法一是走真值表思路：已经知道主析取范式包含哪些极小项，说明剩下的赋值都是成假赋值，直接把这些剩下赋值的下标对应成极大项写主合取范式即可。反过来也一样，知道主合取范式的极大项下标，剩下的下标就是极小项。
方法二是用“取否定再德摩根”的演算。设 F 的主析取范式是 m₁∨m₃∨m₄∨m₇，对 F 取否定得到 ¬F 的主析取范式是 m₀∨m₂∨m₅∨m₆。再对整个式子取否定并做德摩根：F=(m₁∨m₃∨m₄∨m₇)，所以 ¬F=m₀∨m₂∨m₅∨m₆，再取否定得 ¬(m₀∨m₂∨m₅∨m₆)=(¬m₀)∧(¬m₂)∧(¬m₅)∧(¬m₆)=M₀∧M₂∧M₅∧M₆，与直接查表结果一致。这里用到了 Mᵢ 与 mᵢ 互为否定的性质。
做题时我更喜欢第一种方法，因为它直接利用“成真赋值和成假赋值互补”这一事实，几乎不用动脑子。但只有理解了第二种方法的推导，你才算真正明白为什么 Mᵢ 和 mᵢ 下标相同却能互为否定，考试遇到变形题才不慌。
3.4 应试最容易踩的四个坑
先说我见过的错误，大家避开。
第一个坑是符号优先级。否定号优先级最高，其次按 ∧、∨、→、↔ 递减。写法上比如 ¬p∧q 表示 (¬p)∧q，不是 ¬(p∧q)。做等值演算时，遇到题目没加括号的长式子，先按优先级默默补上隐形括号，不然第二步否定内移极易出错。
第二个坑是极小项和极大项的编码方向混淆。极小项中变元为1写原变元，变元为0写否定；极大项中变元为0写原变元，变元为1写否定。有人只记“极小项看1、极大项看0”却忽略了后半句“怎么写”，结果下标对、表达式写反，一样丢分。
第三个坑是“普通范式”和“主范式”混着答。题目问主析取范式，你写了普通析取范式，虽然逻辑等价，但因为没有体现成真赋值的唯一编码，判卷直接扣分。区分方法很简单：主范式里每个子句必须包含全部命题变元，缺一个变元都不是主范式。
第四个坑是下标编号顺序。如果在同一道题里调整了变元顺序，比如题目写的是 (q,p)，而自己习惯写成 (p,q)，那么同样一行赋值 01 对应的下标会从 1 变成 2。解决办法是动笔前先明确变元顺序，全程保持一致，最后写答案前再检查一遍。
4. 范式在真实场景中干什么活
4.1 可满足性判定与SAT问题
离散数学的范式看起来像纯数学玩具，实际上直接对应计算机科学里的核心问题：可满足性问题，也就是SAT问题。
一个公式的可满足性可以通过主范式一眼看出：如果主析取范式包含全部 2^n 个极小项，说明所有赋值都让公式为真，这是永真式；如果主析取范式一个极小项都没有，说明所有赋值都让公式为假，这是永假式；只要有至少一个极小项，公式就可满足。用主合取范式判断则反过来：主合取范式为空集对应永真，包含全部极大项对应永假。
SAT问题不仅是理论问题，更是现代芯片验证、软件形式化验证、人工智能规划背后的基础。实际求解SAT时并不会真的把主范式全列出来（那样指数爆炸），而是用DPLL、CDCL这类算法在CNF结构上做搜索。但你在离散数学课上学到的“范式”正是理解这些算法入口：为什么算法都默认输入是CNF？因为CNF结构天然适合做“子句冲突”分析，一个子句只要一个文字为真，整个子句就为真，非常容易剪枝。
4.2 数字电路里的SOP/POS与卡诺图
如果你学过数字电路，会发现“主析取范式”和“主合取范式”换了个马甲：最小项之和（SOP）和最大项之积（POS）。
数字电路里的组合逻辑设计，本质就是先根据需求列出真值表，再写出SOP或POS表达式，最后用门电路实现。比如设计一个多数表决器，3个输入中有2个及以上为1时输出1，直接查真值表得到SOP表达式，再用与非门化简。很多教材会把“卡诺图化简”单独拿来教，核心思想其实是把主析取范式中相邻的极小项合并，达到消变量的目的。也就是说，卡诺图化简的本质是在做“主范式的可视化化简”，不是另一套孤立的技术。
这里有个很实用的笔记技巧：离散数学主范式题目不光要求“会求”，还要求“求完能化简”。你在卡诺图里画的每一个圈，本质上就是结合律、吸收律在等值演算里的重复使用。懂了这个，再回头看离散数学的化简题会轻松不少。
4.3 规则引擎、专家系统与逻辑推理
再看一个更贴近人工智能的场景：专家系统和规则引擎。热词检索里有“mycin专家系统与命题逻辑”，这个方向恰好能说明范式为什么是推理的底层工具。
MYCIN是上世纪70年代的医学专家系统，核心是一堆“如果…那么…”的产生式规则，比如“如果细菌是革兰氏阴性且形态是杆状，那么它是肠杆菌科”。在逻辑上，每条规则都是一个蕴含式。要进行计算机推理，通常会先把知识库里的规则转成CNF，再用归结原理去判断某个结论是否成立。归结原理一次只处理一个子句和一个子句，能直接操作的前提就是知识都已经规范成CNF。
今天我们在后端开发里经常接触的规则引擎、策略引擎，底层思路也类似：把用户输入的约束条件、业务规则编码成逻辑表达式，再推演是否满足、有没有冲突。所以别觉得离散数学范式只能应付考试，它真的是不少系统的地基。
4.4 “范式”在不同学科里都是高频词，别串台
顺带回应一下开头的澄清。数据库里的BCNF、3NF，解决的是表设计冗余；心理学里的stroop范式，说的是认知实验设计；编程里的“反范式设计”，说的是打破常规模式。这些词全都叫“范式”，但在离散数学里谈范式，唯一指的就是命题逻辑的标准形态。
学习时被这些同名术语干扰很正常，尤其在刷题阶段，一搜索满屏都是数据库范式，很容易心态崩掉。我的应对办法是：看到“范式”先扫一眼上下文有没有“命题”“合取”“析取”“极小项”这些词，有就一定是离散数学的范式；看到“BCNF”“函数依赖”“主键”，那就是数据库的范式。分清楚语境，比多背十页笔记都管用。
5. 常见问题排查与期末复习速成方案
5.1 一做就错的典型问题与排查思路
我在复习时给自己整理过一个“错题对照表”，按错误表现逐项排查，很实用。
| 错误表现 | 可能原因 | 排查方法 |
|---|---|---|
| 否定号作用范围不对 | 优先级理解错误，把 ¬(p∧q) 写成 ¬p∧q | 先补全隐形括号，再做否定内移 |
| 分配律展开后式子变长且无法化简 | 分配方向选反了，求CNF误用了∧对∨分配 | 确认目标形态：DNF用∧对∨，CNF用∨对∧ |
| 主范式下标错位 | 变元顺序不统一或编码时看错二进制位 | 固定变元顺序，极小项“1写原变元0写否定”，极大项反过来 |
| 求出的普通范式与答案不同 | 普通范式本身不唯一 | 检查每一处替换是否都是合法等值式，而非追求和答案一模一样 |
| 永真/永假判断不出来 | 主范式概念不清 | 永真式的极小项集合为全集，永假式为空集 |
| 合取范式和析取范式写反 | 分不清“∧连接子句”还是“∨连接子句” | 看最外层连接词：最外层是∨则是析取，最外层是∧则是合取 |
还有一个非常隐蔽的错误：化简时用了 “同一律” 但符号写反。比如把 p∨p 化简成 p 是对的（幂等律），把 p∧¬p 化简成 p 就是错的，结果应该是 0（矛盾律）。每化简一步都问自己：这一步用的是哪条等值式？答不出来就是凭感觉在乱化，迟早出错。
5.2 期末复习三步法
如果你已经没时间做很多题，我推荐一个三步突击法，亲测有效。
第一步，把基础等值式默写一遍。重点不是背名字，而是能闭着眼写出：蕴含等值式、等价等值式、德摩根律、分配律、吸收律、幂等律、同一律、零律、矛盾律、排中律、双重否定律。一共十几条，每天默写一遍，坚持三天基本固化。
第二步，每天做两个公式的完整练习。一个公式要求“真值表+主析取+主合取”，另一个公式要求“等值演算+普通范式+主范式”。做完之后把两种方法的结果互相对照，如果有差异，花时间找出原因而不是直接跳过。对照的过程就是查漏补缺的过程。
第三步，专练主范式互转。找 4 到 5 个有三个变元的公式，先写主析取，再写主合取，再用“取否定法”验证一次。这个练习能把第 3 节的“互补关系”和“对偶关系”彻底变成肌肉记忆。
教材方面，我用的比较多的是屈婉玲的《离散数学》，课后题难度和期末相当，主范式部分题型很全，逐题做一遍基本不会碰见不会的类型。如果手头有罗森的《离散数学及其应用》，直接做命题逻辑部分“范式与主范式”的小节题也可以，它更偏应用，例子多，适合理解概念来源。
5.3 自学资源与自检方法（包括用Python验证）
如果你和我一样，做完题总怀疑自己算错了，强烈建议用Python做交叉验证。用一个很小的脚本就能把真值表列出来，快速核对成真赋值和成假赋值是否对得上。
from sympy import symbols from sympy.logic.boolalg import truth_table p, q, r = symbols('p q r') expr = (p >> q) >> r # sympy中蕴含用 >>，等价用 == for row in truth_table(expr, [p, q, r]): print(row)注意sympy里to_cnf和to_dnf给的是普通范式，不一定输出主范式，所以验证主范式时，最稳妥的方式还是自己根据真值表输出构造：成真赋值对应极小项做或，成假赋值对应极大项做与。
这个自检方法省了非常多时间。手工算完一组主范式，再用代码一验，对上了就放心，对不上就按上面表格逐项排查。把“人算”和“机算”配合起来，事半功倍。
我个人复习下来的最大体会是：范式这一节难不在计算，而在理解“为什么需要”。一旦想清楚它是把逻辑表达式变成标准形态，后面主范式的唯一性、可满足性判定、卡诺图化简、归结推理就全都顺了。最后再分享一个小技巧：考试时先写解题结构，也就是“第一步消去蕴含等价、第二步否定内移、第三步分配、第四步补全变元”，每一步在草稿纸上列一个小标题，再往里面填式子。看起来多花几十秒，实际能避免大量低级失误。
