离散数学学到第三章很多同学第一次被“范式”这个词卡住。我当时复习命题逻辑的时候也在这个地方反复绕了很久明明一个公式已经能算真值了为什么还要把它变成析取范式、合取范式、主析取范式、主合取范式这四样东西到底有什么用等把这块啃下来回头看才发现范式这一节不只是“会算”就行它其实是整个命题逻辑从“求真假”走向“做推理”的枢纽后面学谓词逻辑、推理理论、数字电路全都要从这里接上。这篇笔记就把我自己梳理清楚的内容完整写出来从“范式是什么”到“怎么求”再到“学了能干什么”直接用 (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的某个赋值比如 p0、q1 这一行要写成 (¬p∧q)对使结果为0的某个赋值比如 p1、q1 这一行要写成 (¬p∨¬q)。原理不复杂p0 时 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 完整走一遍。先看真值表pqrp→q(p→q)↔r0001000111010100111110001101001101011111真值表法直接读成真赋值是 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₇)所以 ¬Fm₀∨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给的是普通范式不一定输出主范式所以验证主范式时最稳妥的方式还是自己根据真值表输出构造成真赋值对应极小项做或成假赋值对应极大项做与。这个自检方法省了非常多时间。手工算完一组主范式再用代码一验对上了就放心对不上就按上面表格逐项排查。把“人算”和“机算”配合起来事半功倍。我个人复习下来的最大体会是范式这一节难不在计算而在理解“为什么需要”。一旦想清楚它是把逻辑表达式变成标准形态后面主范式的唯一性、可满足性判定、卡诺图化简、归结推理就全都顺了。最后再分享一个小技巧考试时先写解题结构也就是“第一步消去蕴含等价、第二步否定内移、第三步分配、第四步补全变元”每一步在草稿纸上列一个小标题再往里面填式子。看起来多花几十秒实际能避免大量低级失误。
离散数学范式详解：从析取范式到主合取范式，逻辑推理与数字电路的核心
离散数学学到第三章很多同学第一次被“范式”这个词卡住。我当时复习命题逻辑的时候也在这个地方反复绕了很久明明一个公式已经能算真值了为什么还要把它变成析取范式、合取范式、主析取范式、主合取范式这四样东西到底有什么用等把这块啃下来回头看才发现范式这一节不只是“会算”就行它其实是整个命题逻辑从“求真假”走向“做推理”的枢纽后面学谓词逻辑、推理理论、数字电路全都要从这里接上。这篇笔记就把我自己梳理清楚的内容完整写出来从“范式是什么”到“怎么求”再到“学了能干什么”直接用 (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的某个赋值比如 p0、q1 这一行要写成 (¬p∧q)对使结果为0的某个赋值比如 p1、q1 这一行要写成 (¬p∨¬q)。原理不复杂p0 时 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 完整走一遍。先看真值表pqrp→q(p→q)↔r0001000111010100111110001101001101011111真值表法直接读成真赋值是 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₇)所以 ¬Fm₀∨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给的是普通范式不一定输出主范式所以验证主范式时最稳妥的方式还是自己根据真值表输出构造成真赋值对应极小项做或成假赋值对应极大项做与。这个自检方法省了非常多时间。手工算完一组主范式再用代码一验对上了就放心对不上就按上面表格逐项排查。把“人算”和“机算”配合起来事半功倍。我个人复习下来的最大体会是范式这一节难不在计算而在理解“为什么需要”。一旦想清楚它是把逻辑表达式变成标准形态后面主范式的唯一性、可满足性判定、卡诺图化简、归结推理就全都顺了。最后再分享一个小技巧考试时先写解题结构也就是“第一步消去蕴含等价、第二步否定内移、第三步分配、第四步补全变元”每一步在草稿纸上列一个小标题再往里面填式子。看起来多花几十秒实际能避免大量低级失误。
