1. 范式到底在解决什么问题1.1 学之前为什么教材要把范式单独拿出来离散数学学到第三章命题逻辑前半部分还算友好联结词、真值表、等值演算每一步都有明确的规则做题就像套公式。等到“范式”这个词出现很多人的第一反应是这东西到底是干嘛的我当年学的时候也有同样的困惑。后来才明白命题逻辑前面讲等值演算本质上是在解决“两个公式是否等价”的问题。但等值演算有个尴尬的地方——它依赖技巧。同一个公式一个人三步推完另一个人可能绕了十步还不一定推得对。范式就是来解决这个问题的它把公式改写成一种“标准格式”让判断等价、判断类型、甚至机械地比较两个公式是否相同都变成流水线操作。打个比方。生活中判断两份合同是否内容一致最靠谱的办法不是逐字读而是把两份合同都填成同一套标准模板然后逐格比对。范式就是命题逻辑里的“标准模板”。任何复杂的命题公式经过等值演算都能化成两种标准形态之一——析取范式或合取范式。如果进一步要求每个子项都包含所有命题变元就得到主析取范式和主合取范式。后者的价值更大一个公式的主范式是唯一的也就是说公式和它的主范式是“一一对应”的。这个“唯一性”是整个第三章后半部分的灵魂。判断两个看似不同的公式是否等价不用再做复杂的推导直接各自求主范式比一下编号集合是否相同结果一目了然。判断一个公式是重言式、矛盾式还是可满足式也不用瞪着眼睛观察看主范式的结构特征就能机械判断。这也是范式的核心意义。另外说一句范式这部分不是考完就扔的内容。后续在谓词逻辑里会有前束范式在数理逻辑里会用到斯柯伦范式在自动定理证明里会接触归结原理这些本质上都是“把公式规范化之后做机械推理”的思路。第三章的范式就是这套思维的第一个落脚点。1.2 哪个环节最值得花时间以我自己的学习经验来说范式这一章有三个环节值得投入时间。第一个环节是理解“简单合取式”和“简单析取式”的概念。很多人在这里第一次卡住因为名字太像了。简单合取式是若干个文字命题变元或其否定用“且”连接起来的公式比如 p∧q、p∧¬q简单析取式是若干个文字用“或”连接起来的公式比如 p∨q、p∨¬q。记住口诀合取是“且”析取是“或”。第二个环节是熟练等值演算的几个基本公式特别是蕴含等值式 p→q ⇔ ¬p∨q、德摩根律、双重否定律、分配律。做范式题的第一步几乎都是消去蕴含这一步不熟后面全是空中楼阁。建议把等值演算的常用公式抄在一张纸上做习题的时候放在旁边对照等做到十道题以上自然就记住了。第三个环节是理解极小项和极大项的编号规则。这是主范式最核心的难点也是考试最喜欢出题的点。极小项对应成真赋值极大项对应成假赋值编号规则完全一致命题变元按顺序排列变元本身记作该位为1变元的否定记作该位为0得到的二进制数翻译成十进制就是该项的下标。后面我会用具体例子详细拆解。如果这三个环节都能过关范式这块的内容就基本拿下了。2. 范式的两个基本形态2.1 析取范式与合取范式怎么区分不混淆先看两种基本范式的定义。析取范式形如“简单合取式 用∨连接”即 A₁∨A₂∨…∨Aₙ其中每个 Aᵢ 是简单合取式若干个文字用∧连接合取范式形如“简单析取式 用∧连接”即 B₁∧B₂∧…∧Bₙ其中每个 Bᵢ 是简单析取式若干个文字用∨连接。这个定义有一个非常容易踩的坑名字和结构是反直觉的。析取范式外表看是“一堆合取项用析取连接”合取范式外表看是“一堆析取项用合取连接”。也就是说判断范式的类型看的是最外层的主联结词而不是每一项内部的联结词。我自己的记忆方法很简单析取范式最外层是“或”合取范式最外层是“且”。而每一项内部的联结词跟外层正好相反。有人把这个叫做“里外相反律”。刚开始做题的时候可以每次都先把“最外层主联结词”圈出来习惯之后就不会混了。这里还要区分一个概念简单合取式和简单析取式本身都算范式只是退化形式。单个文字既是简单合取式也是简单析取式所以一个单独的 p 既可以看作析取范式也可以看作合取范式。这个细节在有些题目里有用比如判断“公式是否为析取范式”单个文字的答案总是“是”。另外要注意不是所有公式都能不经处理直接看出属于哪种范式。一个公式如果是 ¬(p∧q) 的形式外层是否定严格来说它连范式都不是因为否定联结词出现在最外层而且作用域是整个括号。处理办法是用德摩根律把否定内移¬(p∧q) ⇔ ¬p∨¬q这样就得到了析取范式。判断一个公式是不是范式标准很简单只看“∧”“∨”“¬”三种联结词并且否定符号只能直接出现在命题变元前面不能作用于括号或更复杂的子公式。2.2 什么时候用哪种范式两种基本范式都用于判断公式类型但各有侧重。对于一个已经化成的析取范式如果它每个简单合取式都包含一对互为否定的文字比如某个子项里同时出现 p 和 ¬p那么这一项恒为假可以去掉不影响公式的真值如果所有项都被去掉了说明公式是矛盾式。反之如果一个析取范式含有一个至少一项“可满足”的子句它就有可能是可满足式。对比之下合取范式更适合判断重言式。一个合取范式如果每个简单析取式都含有一对互为否定的文字那么每一项恒为真整个公式就是重言式。比如 (p∨¬p)∧(q∨¬q)一眼就能看出它恒真。可惜这个方法只适用于基本范式不能用来判断主范式类型。主范式因为是标准形式每个子项都含所有变元所以“某个子项包含 p 和 ¬p”的情况不会出现需要用另外的规则。实际做题时如果题目说“求公式的析取范式”就用等值演算一步步推保留有用项如果只是“判断公式类型”其实有更快的办法——先看它是否重言式或矛盾式再决定是否需要继续化简。因为真值表法和主范式法虽然机械可靠但遇到变元多的公式会非常繁琐考试时时间有限优先选择特征观察法。下面给一个简单示例。公式 (p→q)∧p→q。用蕴含等值式先消去箭头¬(¬p∨q)∧p ∨ q。注意这里有个经典的括号问题原式看成 (A→B) 的形式其中 A 是 (p→q)∧pB 是 q所以整个公式先变成 ¬A∨B不要漏掉最外层括号。继续化简¬(¬p∨q)∨¬p∨q再用德摩根律和双重否定律得到 (p∧¬q)∨¬p∨q。这个析取范式里的第二项和第三项各含一个变元说明它还不是主范式需要通过补项来进一步处理。3. 主范式标准化的标准3.1 极小项与极大项真值表背后的编码基本范式不够“标准”因为同一个公式可以写出很多不同的析取范式各项的长短也不一样。要得到“唯一标准”就需要主范式。主范畴的核心概念是极小项对应主析取范式和极大项对应主合取范式。这里我直接说结论性的实操理解。在有 n 个命题变元的公式中极小项是包含全部 n 个变元每个变元或其否定恰好出现一次且按顺序排列的简单合取式。因为每个变元有两种出现方式本身或否定所以一共有 2ⁿ 个不同的极小项。同理极大项是包含全部变元的简单析取式也有 2ⁿ 个。极小项有一个重要性质在全部 2ⁿ 个赋值中每个极小项只在一种赋值下为真。比如两个变元 p、q极小项 p∧q 只在 p1、q1 时为真极小项 ¬p∧q 只在 p0、q1 时为真。这一特性让极小项成了“赋值的编码”。反过来极大项在全部赋值中只在一种赋值下为假。比如极大项 p∨q 只在 p0、q0 时为假极大项 ¬p∨q 只在 p1、q0 时为假。编号规则是考试的重头戏。对于极小项把变元按顺序排好变元本身记1变元的否定记0得到的二进制串翻译成十进制就是下标。比如两个变元时¬p∧¬q 对应 00记为 m₀¬p∧q 对应 01记为 m₁p∧¬q 对应 10记为 m₂p∧q 对应 11记为 m₃。三个变元时¬p∧¬q∧¬r 对应 000记为 m₀依此类推。极大项的编号规则跟极小项刚好相反变元本身记0变元的否定记1。因为极大项是“在一种赋值下为假”这个赋值的二进制编码就是它的下标。比如两个变元时p∨q 对应 00记为 M₀p∨¬q 对应 01记为 M₁¬p∨q 对应 10记为 M₂¬p∨¬q 对应 11记为 M₃。注意 m 小写M 大写m 的下标对应使该项为真的赋值M 的下标对应使该项为假的赋值。这个对应关系搞反是常见错误后面我会专门列一个避坑清单。3.2 主析取范式与主合取范式的相互转换一个公式如果有 n 个变元它的极小项和极大项一共 2ⁿ 个。任何不是矛盾式或不是重言式的公式它的主析取范式包含若干极小项主合取范式包含若干极大项两者的下标集合合起来正好是全集 {0, 1, …, 2ⁿ-1}。这个互补性质非常实用。当求出一个公式的主析取范式之后主合取范式可以直接“反着写”看全部下标里没有出现哪些极小项把这些编号对应的极大项用合取连接起来就是主合取范式。反过来也一样。举一个具体例子。某公式有两个变元它的主析取范式是 m₁∨m₃说明下标集合是 {1, 3}。全集是 {0,1,2,3}那么未出现的下标是 {0,2}。对应的极大项是 M₀p∨q和 M₂¬p∨q所以主合取范式就是 M₀∧M₂也就是 (p∨q)∧(¬p∨q)。这里有一个重要的前提必须是有 n 个变元的标准形式并且“全集”是按照 n 个变元来算的。如果题目中公式里有一些变元虽然在表达式中没有直接出现但题干明确给出了变元集合那么求主范式时必须把它们也算进去。比如公式 p∨q 在变元集合 {p,q} 下是主析取范式 m₁∨m₂∨m₃但如果题目说变元集合是 {p,q,r}那 p∨q 就不是主范式需要补上 r。很多人在这一步翻车。4. 实操一题到底把步骤拆成模板4.1 题目与等值演算方法步骤我用一道常见例题来演示完整流程题目是求公式 (p→q)∧(q→r) 的主析取范式和主合取范式。这道题变元不多不少刚好能把所有步骤走一遍非常适合用来建立解题模板。第一步消去蕴含。把 p→q 化为 ¬p∨q把 q→r 化为 ¬q∨r。原式变成 (¬p∨q)∧(¬q∨r)。第二步判断是否已经是某种范式。这个式子是“两个简单析取式的合取”所以已经是合取范式了。但它还不是主合取范式因为第一项缺 r第二项缺 p。第三步补项。补项的原则是缺哪个变元就用“这个变元∨它的否定”去“∧”进当前项。对于合取范式缺项补项的公式是 A ⇔ A∨(B∧¬B)再用分配律展开。现在处理第一项 (¬p∨q)补 r得到 (¬p∨q)∨(r∧¬r)再用分配律展开为 (¬p∨q∨r)∧(¬p∨q∨¬r)。处理第二项 (¬q∨r)补 p得到 (¬q∨r)∨(p∧¬p)展开为 (¬q∨r∨p)∧(¬q∨r∨¬p)。第四步整理编号。为了对照方便把变元顺序统一调整为 p、q、r用“变元本身记0否定记1”的规则给极大项编号。这里每一项都要仔细写出来。第一项展开后的两个子项是 (¬p∨q∨r) 和 (¬p∨q∨¬r)它们对应的二进制串分别是 100 和 101所以是 M₄ 和 M₅。第二项展开后的两个子项是 (¬q∨r∨p) 和 (¬q∨r∨¬p)按 p、q、r 排序调整为 (p∨¬q∨r) 和 (¬p∨¬q∨r)二进制串分别是 010 和 110所以是 M₂ 和 M₆。合并所有极大项得到主合取范式 M₂∧M₄∧M₅∧M₆。第五步由主合取范式反推主析取范式。三个变元的全集是 {0,1,2,3,4,5,6,7}已出现的极大项下标是 {2,4,5,6}所以未出现的下标是 {0,1,3,7}。这些下标对应的极小项分别是 m₀、m₁、m₃、m₇。于是主析取范式就是 m₀∨m₁∨m₃∨m₇。这里要特别注意在第三步补项时我用的是合取范式补项的方法展开之后得到的是极大项。如果题目要求主析取范式其实可以直接从原式开始做析取范式的补项流程也可以用极大项反推。实际考试中从主合取反推主析取是最省时的因为只需要做一次补项展开。4.2 真值表法对照验证等值演算的方法容易因为某一步写错而“全盘皆输”所以我强烈建议在练习阶段用真值表法对照验证。考试时如果时间充裕也可以在草稿纸上快速复查。以这道题为例公式 (p→q)∧(q→r) 的真值表共有 8 行。逐行算 (p→q) 和 (q→r)再取合取得到结果为真的行是 000、001、011、111 四行二进制赋值对应十进制下标 0、1、3、7。这正好与刚才求出的主析取范式 m₀∨m₁∨m₃∨m₇ 完全吻合。真值表法还有一个额外的好处它能直观地解释“为什么主范式唯一”。因为一个公式在所有赋值下的真值情况是唯一的而主析取范式恰好把所有“结果为真”的赋值对应的极小项都列了出来所以主析取范式当然唯一。同理主合取范式把所有“结果为假”的赋值对应的极大项都列了出来也唯一。我做题时的习惯是先用真值表求出成真赋值和成假赋值直接写出主析取范式和主合取范式的编号集合再用等值演算验证其中一个。两种方法互相印证一旦编号集合对不上说明肯定有一处写错了这时候回头检查比盲目重推高效得多。5. 常见错误与高频考点避坑5.1 教材里不写但考试爱考的陷阱我在带学弟学妹复习离散数学时发现范式的错误高度集中。下面这些坑几乎每个人都踩过这里列成一个速查表做题前扫一眼能省不少时间。常见错误错误示范正确做法出错原因主联结词判断反把 (¬p∨q)∧¬q 当成析取范式这是合取范式只看了括号里是“或”没看最外层是“且”否定作用域漏掉¬(p∧q) 直接当作析取范式先德摩根化成 ¬p∨¬q 再说否定符号后面是括号必须先处理m 和 M 编号规则混用m₀ 对应 p∧qm₀ 对应 ¬p∧¬q极小项看真赋值极大项看假赋值两者对应规则相反补项只补一次(p∨q) 补成 (p∨q∨r) 就完事还要补 ¬r得到两项每个变元有两种出现方式缺一个变元必须补两个子项漏掉变元全集公式没出现 r就不补 r题干说明变元是 {p,q,r} 就必须补主范式的“全集”由变元集合决定不由表达式决定重点说一下补项这个坑。很多人在把合取范式变成主合取范式时觉得“式子缺 r那我就给它加上 r”然后写出一项 (p∨q∨r)以为完事了。这是错的。因为主范式的每个子项必须包含所有变元缺失的变元应该以“本身或否定”两种形式各出现一次。例如 (p∨q) 补 r应该变成 (p∨q∨r)∧(p∨q∨¬r)两项都保留。同理析取范式补项时也要补两个A ⇔ A∧(B∨¬B)再分配。另一个容易忽视的点是题目里如果给了“变元集合”比如“设公式含变元 p、q、r”但公式本身写出来只有 p、q那么求主范式时依然要按三个变元处理。平时如果不养成看题干条件的习惯考试很容易在这种地方丢分。5.2 快速判断与省时间的技巧范式的题目说到底就那么几种题型求主析取范式、求主合取范式、判断公式类型、证明两个公式等价。针对这些题型有一些省时间的套路。第一个技巧先判断公式类型再决定写哪种主范式。如果公式是重言式它的主析取范式包含所有 2ⁿ 个极小项主合取范式可以直接写“∅”或省略如果公式是矛盾式主合取范式包含所有极大项主析取范式可以直接写“∅”。这种情况下就不用做复杂的补项展开。第二个技巧利用“主析取范式等价于主合取范式的互补性”。在求出一种主范式之后另一种直接按“全集减已出现集合”来写不需要再从头推。前面例题已经演示过这里再强调一遍所求集合和未出现集合必须加起来等于全集 {0,1,…,2ⁿ-1}这是检查结果是否正确的有力工具。第三个技巧真值表法优先。如果公式变元不超过三个真值表通常比等值演算更快。三变元真值表 8 行每行判断一次公式真值然后直接列出极小项和极大项整个过程不超过两分钟。需要手写卷面的情况下这个方法不容易因为步骤跳步被扣分但在平时练习时还是要以等值演算为主因为考试中可能有要求“用等值演算求主范式”的题目。第四个技巧验证主范式时用“代入一个赋值”来快速检验。比如已经求出主析取范式是 m₁∨m₃可以取赋值 p0、q1对应下标1看看这个赋值下原公式是否为真。如果为真说明主范式包含 m₁ 没问题取一个未出现的赋值 p1、q0下标2原公式应该为假。这种“抽查式验证”可以在考场上用非常有价值能抓出不少笔误。6. 范式在计算机里的影子6.1 命题范式与数字电路离散数学在很多计算机专业学生看来是“纯理论”其实范式在数字电路里有一个非常直接的应用。数字电路中的“与或式”就是析取范式的工程化表达每个“与门”的输出对应一个简单合取式再用“或门”将这些输出合并。而“或与式”对应合取范式先用“或门”生成简单析取式再用“与门”合并。主范式则对应电路中“基于最小项/最大项的标准型设计”。学过数电的同学对卡诺图一定不陌生。卡诺图化简的核心思想就是在一个按格雷码排列的网格中把相邻的极小项合并消除互补的文字。这个操作的依据正是布尔代数中的吸收律和互补律和离散数学里范式的等值演算是一回事。所以第三章范数学得好数电的卡诺图、逻辑门化简会轻松不少。反过来如果用命题逻辑的观点看数字电路每个门电路都可以对应一个联结词一条电路就是一个命题公式。判断两个电路是否功能相同不需要逐个输入测试直接把两个公式都化成主范式对比编号集合即可。这就是“等价性检验”的底层原理。工业界里很多硬件验证工具核心算法之一就是把电路转换成正则形式后做比较跟用主范式判断公式等价的思路一脉相承。6.2 范式思想在其他领域的延伸除了数字电路范式这种“规范化”思维在其他领域也经常出现举个例子很多刚刚接触数据库的同学会把“数据库范式”和离散数学里的“命题范式”搞混。两者除了名字里都有“范式”二字其实不是同一个概念。数据库中的第一范式、第二范式、BCNF 范式解决的是“表结构是否存在冗余和异常”的问题它的“范式”更像一种设计规范而不是数学上可计算的正则形式。不过这两种“范式”有一个共同的思维内核标准化。数据库范式把一张表规范化成“每个属性不可再分”“非主属性完全依赖主键”等标准形态目的和命题公式化成标准形态完全一致——消除歧义、避免冗余、让后续处理更机械可靠。包括互联网圈经常说的“反范式设计”本质上也是在“标准化”和“性能”之间做权衡。这个权衡思路放到命题逻辑里也成立主范式虽然标准唯一但往往比原公式冗长所以实际电路设计不会一股脑全用主范式而是尽量化简。可见“规范化”并不是目标本身手段而已。另一个相关的热点是专家系统。比如经典的医学专家系统常被提到的 MYCIN 系统就用到了产生式规则一条规则可以表示成“如果条件1且条件2则结论”形式化之后就是命题逻辑里的蕴含式比如 (A∧B)→C。当系统需要进行规则推理时可以借助范式和归结原理把知识库中的规则转换成便于机器处理的形式。这里的“把规则转成标准形式再推理”的思路本质上就是范式思想在人工智能知识表示中的应用。有人可能会问命题逻辑能表达的东西很有限为什么还要学因为谓词逻辑是在命题逻辑基础上扩展出来的而谓词逻辑中的很多处理方法比如前束范式、Skolem 化都沿用命题逻辑范式“先标准化再处理”的基本框架。把第三章的基础打牢后面学谓词逻辑、推理理论时才不会感觉突然“换了一个世界”。我自己在学完第三章后最大的感受是范式就像一个“翻译器”把人的直觉推理翻译成机器可以执行的机械步骤。数学里很多概念看似抽象其实都是这个“标准化→机械化→自动化”链条上的一环。理解了这一点再回头看 m₀、M₅ 这些繁琐的编号就不会觉得它们只是无聊的符号游戏而是一套让逻辑推理变得可计算的关键接口。最后分享一个我教学生时常用的小技巧在求主范式之前先把“变元集合”写在题目旁边再在全集 {0,1,…,2ⁿ-1} 上画一个数轴把已经算出的下标勾出来。这样补项的时候一眼就能看出哪些下标没出现主范式之间的转换也会清晰很多。这个小习惯帮我省了非常多检查时间你也可以试试。