1. 为什么主析取范式、主合取范式这一节卡住了不少人坦白说很多人在学离散数学的时候前面等值演算部分还挺顺畅一到“主析取范式、主合取范式”就开始犯迷糊。不是因为它难而是因为这一节的知识形态跟前面不太一样前面是告诉你“怎么把公式变短”这一节是让你“把一个公式变成一种标准格式”而这个标准格式有两条完全不同的路线——一个叫主析取范式一个叫主合取范式。问题就出在这里。很多同学会问我已经能用等值演算把一个式子化简了为什么还要再搞出两个“主范式”这俩东西到底有什么用考试考它到底想考什么我的理解是这样的主析取范式和主合取范式本质上是把一个命题公式的表象剥掉直接看它的“行为”。一个公式无论写得多么复杂它最终的真值表是唯一确定的。而主析取范式和主合取范式就是两种把“真值表行为”翻译成公式的方法。你一旦掌握了这一层后面学的很多东西都会通起来。这篇文章我打算按一条完整的实操链路来讲先讲最小项和最大项这两个地基概念再分别讲主析取范式、主合取范式的求法然后讲它们之间怎么互相转换最后清点一下做题时最容易踩的坑以及这玩意儿在电路设计、逻辑判定里的真实用途。我自己带过的学生里凡是这套流程走完的基本再遇到范式题都不会慌。2. 先挖地基最小项和最大项是主范式的两块基石2.1 最小项为什么每个乘积项必须“一个字母不漏”要搞懂主析取范式必须先搞懂最小项。所谓最小项就是对于n个命题变元每个变元要么以原形、要么以否定形式出现一次然后把这些“字母”用合取连接起来得到的式子。比如有三个变元p、q、r那么¬p∧q∧¬r是一个最小项p∧q也是由变元构成的合取式但它不是最小项因为它里面少了r。为什么必须有这个“每个变元恰好出现一次”的硬性要求因为最小项有一个非常漂亮的性质一个最小项在真值表中恰好只在一个赋值为真的行上取值为真。举个例子最小项¬p∧q∧¬r只有当p0、q1、r0时它才是真其他任何赋值下它都是假。这就像一把钥匙只开一把锁给定一个最小项你就知道它对应真值表的哪一行。反过来说一个真值表的某一行也恰好能写出唯一一个在该行为真的最小项。这个一一对应的关系才是主析取范式能成立的根基——主析取范式其实就是“真值表里所有取值为1的行各写一个最小项然后全部用析取连起来”。你甚至可以这么理解主析取范式就是真值表的“1”行清单。2.2 最大项与最小项完美对偶的“或”结构最大项的定义跟最小项正好相反。对于n个变元每个变元以原形或者否定形式出现一次用析取连接起来就是最大项。三个变元下p∨¬q∨r就是一个最大项。最小项在“恰好一个行”为真最大项则是“恰好一个行”为假。比如最大项p∨¬q∨r只有当p0、q1、r0时它才是假其他所有赋值下它都是真。所以最大项和最小项之间有一种奇妙的互补关系一个最大项取反得到的就是编号相同的最小项一个最小项取反得到的也是编号相同的最大项。这一“最小一假”的性质决定了主合取范式的形态一个公式的真值表里所有取值为0的行每个行对应写一个最大项再用合取连起来就得到主合取范式。2.3 编号规则m3和M3里那个“3”到底怎么来的最小项通常记作mi最大项记作Mi下标i就是个编号。这个编号怎么算刚学的人很容易在这里犯迷糊因为不同教材的约定可能略有差异。我在这里采用最常见的一套规则对于最小项把每个变元的“原形”看成1“否定”看成0按变元排列顺序组成一个二进制数转成十进制就是编号。所以两个变元p、q的最小项编号如下最小项对应赋值(p,q)二进制编号¬p∧¬q(0,0)00m0¬p∧q(0,1)01m1p∧¬q(1,0)10m2p∧q(1,1)11m3最大项的编号规则正好相反把变元的“原形”看成0“否定”看成1同样按顺序组成二进制数转十进制。所以最大项对应赋值(p,q)二进制编号p∨q(0,0)00M0p∨¬q(0,1)01M1¬p∨q(1,0)10M2¬p∨¬q(1,1)11M3记住一个口诀最小项里“原形为1”最大项里“原形为0”。这个规则在考试里非常关键因为最后你得到的范式如果写成∑(0,2,5)或者∏(1,3,4)这种紧凑形式编号错了整个表达就全错了。2.4 最小项、最大项的性质清单直接背下来用这部分性质不需要全推但一定要记得住因为很多证明题和化简题会用n个变元一共会产生2ᵑ个最小项同样也有2ᵑ个最大项。任意两个不同的最小项合取结果是永假式。任意两个不同的最大项析取结果是永真式。全部最小项析取起来结果是永真式。全部最大项合取起来结果是永假式。最小项mi的否定等于最大项Mi反之亦然。一个最小项与它的编号对应的最大项之间满足¬mi Mi。这些性质听起来抽象但你只要想一遍真值表就会发现全是顺理成章的每个最小项恰好管一行不同行之间合取自然为空所有行合起来就是全集析取自然为真。3. 真值表法求主析取范式从0/1到公式的最短路径3.1 基本套路只看结果为1的行求主析取范式最稳妥、最不容易丢分的方法就是真值表法。它的思路可以用一句话概括找出真值表中所有结果为1的行为每一行写出一个最小项然后把这些最小项全部析取起来。为什么只看结果为1的行因为主析取范式本质上就是描述“这个公式什么时候为真”的表达式。一个命题公式什么时候为真真值表已经写得清清楚楚。每一个为真的行就对应一个最小项把这些最小项用析取连起来就得到一个恰好只在那些行为真的公式也就是原公式的主析取范式。这里有一个特别重要的验证方法你求完之后可以把这个析取式再画一张真值表跟原始公式的真值表对照。两张表完全一致说明做对了不一致就回去找哪一行的最小项写错了。3.2 一个三变量的完整算例照着走一遍就会了我们用一个实际例子走一遍完整流程。设公式为F (¬p → q) ∧ (q ↔ r)先列真值表三个变元共8行逐行计算pqr¬p→qq↔rF000010001000010100011111100111101100110100111111F取真的一共三行分别是第4行p0, q1, r1。取值为1的变元写原形取值为0的写否定得到最小项¬p∧q∧r。按照2.3的规则这一个的二进制是011所以它是m3。第5行p1, q0, r0。变成最小项p∧¬q∧¬r二进制是100也就是m4。第8行p1, q1, r1。变成最小项p∧q∧r二进制是111也就是m7。所以主析取范式写作F (¬p∧q∧r) ∨ (p∧¬q∧¬r) ∨ (p∧q∧r)用紧凑编号方式可以写成F ⇔ m₃ ∨ m₄ ∨ m₇即∑(3,4,7)。这个例子其实还藏了一个值得注意的点第5行p1, q0, r0很多同学会把否定写反写成¬p∧q∧r结果就跟第4行重复了。所以真值表法有一个操作上的建议每一行写最小项之前先把这个行赋值里的0、1标清楚再动笔。3.3 真值表法的适用边界和局限性真值表法虽然稳但也有明显的天花板。变元数量一多比如5个、6个变元真值表就是32行、64行起步手算基本要命。这时候你就需要等值演算法。不过在你刚开始练手的时候我仍然建议多走真值表法。原因很简单它会强迫你把每个行的赋值和最小项的写法对应起来这种机械对应一旦刻进脑子后面无论是等值演算还是互转公式你都很难出错。4. 等值演算法求主析取范式不画真值表也能做4.1 第一步消去→和↔化成基本的析取范式等值演算法的起点是先把公式里的蕴含联结词、等价联结词全部消掉改写为只含¬、∧、∨的形式。你需要用到两组常用公式p→q 等价于 ¬p∨qp↔q 等价于 (¬p∨q) ∧ (p∨¬q)也等价于 (p∧q)∨(¬p∧¬q)消完之后再用分配律把式子展开成“若干简单合取项的析取”也就是析取范式。所谓简单合取项就是由变元或变元的否定合取而成的一串式子比如¬p∧q、p∧¬q∧r。注意这个阶段不要求“每个变元恰好出现一次”所以它还不是主析取范式。拿一个例子练手。设公式为 p→(q→r)。先用蕴含消去p→(q→r) ⇔ ¬p ∨ (¬q ∨ r) ⇔ ¬p ∨ ¬q ∨ r这个式子已经很短了但它是不是主析取范式不一定。要看它涉及的变元有哪些。如果变元集合是{p, q, r}那么¬p这个简单合取项里只有p缺少q和r¬q里缺少p和rr里缺少p和q。所以它还不是主范式必须补项。4.2 第二步用 x∧(y∨¬y) 补全缺失的变元补项的核心公式只有一个x ⇔ x∧(y∨¬y)意思是说一个合取项如果缺少某个变元y你就把它拆成两份一份配上y一份配上¬y。这个公式之所以成立是因为y∨¬y是永真式任何公式与永真式合取值不变。继续用上面那个例子变元是p、q、r。¬p缺少q和r。先补q¬p ⇔ ¬p∧(q∨¬q) (¬p∧q)∨(¬p∧¬q)。再给这两项分别补r¬p∧q ⇔ (¬p∧q∧r)∨(¬p∧q∧¬r)¬p∧¬q ⇔ (¬p∧¬q∧r)∨(¬p∧¬q∧¬r)¬q缺少p和r同理会得到四个最小项。r缺少p和q同理也会得到四个最小项。到这里你可能会出现十几个最小项。别急着收工下一步是整理。4.3 第三步去重、去矛盾项按编号排序展开之后一定会出现大量重复项。比如¬p∧(q∨¬q)和¬q∧(p∨¬p)展开后会有重复的最小项。重复项直接划掉只留一个。同时如果出现p∧¬p这种既包含原形又包含否定的合取项整个项是永假式直接删掉。最后把剩下的最小项按编号从小到大排序书写规范。还是上面那个例子——放大过程我不再逐项写了直接说结论。经过展开、整理后它的主析取范式是m0, m1, m3, m4, m5, m7。有意思的是它缺少m2和m6也就是¬p∧q∧¬r和p∧q∧¬r这两项。这里有一个特别常见的翻车点补项时很多人图省事只在“整个式子”后面补而不是在每个简单合取项上分别补。比如直接把¬p∨¬q∨r整个乘上(p∨¬p)之类的结果式子被改得面目全非。记住等值演算法是逐项补不是整体补。4.4 两种方法的选型什么时候用哪个我的个人建议是这样的3个变元以内、数据量不大的题目优先用真值表法出错的概率低过程也清晰3个变元以上、或者题目要求用等值演算法证明某个等价关系那就老老实实用演算法。考试里如果题目明确说了“用等值演算法求主析取范式”那就别拿真值表去应付有些阅卷标准是看过程的。另外两条路径可以交叉验证先用真值表法求一遍再用等值演算法求一遍看两个结果是否一致。我自己备课批改作业时发现用这种方法验算的学生几乎不会在这部分丢分。5. 主合取范式的两种求法跟主析取范式是“一币两面”5.1 真值表法求主合取范式看0不看1主合取范式的形态是“若干最大项的合取”。用真值表求的时候找的不是结果为1的行而是结果为0的行。这个方向千万别记反了。规则是对于结果为0的每一行取值为1的变元写否定取值为0的变元写原形然后把所有变元用析取连成一个最大项。所有这样的最大项再用合取连起来就是主合取范式。还是用前面那个例子F (¬p→q) ∧ (q↔r)结果取0的行有5行第1行p0,q0,r0写出最大项p∨q∨r二进制编号000根据“原形为0”的规则它是M0。第2行p0,q0,r1取值0的写原形p、q取值1的写否定¬r得到p∨q∨¬r即M1。第3行p0,q1,r0得到p∨¬q∨r即M2。第6行p1,q0,r1得到¬p∨q∨¬r即M5。第7行p1,q1,r0得到¬p∨¬q∨r即M6。所以F (p∨q∨r) ∧ (p∨q∨¬r) ∧ (p∨¬q∨r) ∧ (¬p∨q∨¬r) ∧ (¬p∨¬q∨r)用编号写就是∏(0,1,2,5,6)。你发现没有前面主析取范式是∑(3,4,7)这里主合取范式是∏(0,1,2,5,6)两个编号集合正好互补3、4、7之外剩下的所有编号就是0、1、2、5、6。这就是接下来要讲的核心关系。5.2 巧用主析取范式反推主合取范式如果你已经求出了主析取范式其实不需要再重新列一遍真值表直接反推就可以得到主合取范式。逻辑链条很简单一个命题公式为真当且仅当它的某个最小项为真它为假当且仅当所有“不在主析取范式编号集合里”的最小项都为假。而这些“最小项取反”之后恰好就是对应编号的最大项。所以已知主析取范式∑(3,4,7)那么主合取范式就是∏(0,1,2,5,6)这一步直接就能写出来。反过来已知主合取范式也能用同样的互补关系推出主析取范式。这个互推关系在解题时极其省时间考试时尤其好用。你只要求出一个另一个用编号集合的补集直接写出。5.3 等值演算法求主合取范式补项公式换一个用等值演算法求主合取范式流程跟主析取范式几乎一样只是补项公式换成了x ⇔ x∨(y∧¬y)意思是一个析取项如果缺少某个变元y就把它拆成两项一项配上y一项配上¬y。记住这里是“析取项”不是“合取项”。举个例子两个变元的公式F p→q先消蕴含得到¬p∨q。要化成主合取范式——注意这次目标是最大项的合取所以¬p∨q本来就是最大项吗两个变元下最大项要求p和q都出现一次。¬p∨q只出现了¬p和q缺哪个不缺啊¬p就是p的否定形式q是q的原形所以¬p∨q本身就是一个最大项它的编号是M2p0, q1等一下按规则最大项“原形为0、否定为1”¬p是1q是0二进制10对应M2。这时F的主合取范式就是它的本身M2。从编号看两个变元一共有M0到M3主合取范式只有M2那么主析取范式就是∑(0,1,3)。验证一下原来的式子p→q真值表里结果为1的有(p0,q0)、(0,1)、(1,1)三行正好对应m0、m1、m3。没毛病。6. 考试和作业里最容易踩的五个坑我帮你提前排掉6.1 变量顺序不一致导致编号全错同一道题里变元顺序必须固定。如果你前面按照p、q、r的顺序写最小项后面却变成p、r、q编号立刻乱套。我的习惯是拿到题目先把变元按字母顺序或题目出现的顺序列好全程不换。6.2 补项时补错方向求主析取范式在简单合取项上补项用x∧(y∨¬y)求主合取范式在简单析取项上补项用x∨(y∧¬y)。混淆这两组公式是重灾区。有个记忆方法目标是“合取就乘着补”目标是“析取就加着补”。6.3 化简失度把主范式又“化”回了普通范式有些人已经求出主析取范式了写完之后手痒看到某项跟某项似乎能合并顺手就用了吸收律、分配律化简。这一步做完得到的式子可能还是等值的但它已经不再是主析取范式了因为没有保持“每个变元恰好出现一次”的形式。主范式题的要求就是写成标准形式千万别画蛇添足。6.4 永真式和永假式的特殊处理永真式在任何赋值下都为真它的主析取范式包含所有最小项按照编号写就是∑(0,1,2,...,2ⁿ-1)。但永真式没有任何为0的行所以它没有主合取范式。永假式正好相反它没有主析取范式主合取范式则包含所有最大项。做题时如果遇到“求某永真式的主合取范式”这种表述你要知道答案是不存在如果题目用紧凑符号常说主合取范式为“空合取”但这在不同教材里约定不一考试时最好问一句或者按教材习惯写。6.5 特定赋值下原形和否定的对应记反在真值表法里求最小项时本行取值为1的变元写原形取值为0的写否定。很多同学由于平时习惯“0代表否定”遇到最小项也下意识把0写否定这是对的但遇到最大项时规则就反过来了取值为0的写原形取值为1的写否定。这里的根因是最大项的编号规则与最小项相反。做题前先把这两套对应关系写在草稿纸旁边能有效防止中途混掉。7. 主范式在电路和逻辑判定里的真实用处远不止考试7.1 从真值表到“与或式”数字电路设计的起点可能很多学计算机的同学在离散数学课上没意识到主析取范式在数字电路里有个更工程化的名字——标准与或式或者叫最小项之和。设计一个组合逻辑电路时最朴素的做法就是先根据需求列出真值表然后从所有结果为1的行写出最小项再把这些最小项“或”起来得到的就是一个直接能翻译成电路的逻辑表达式。每个最小项对应一个“与门”所有最小项的输出再接一个“或门”电路就这么搭起来了。主合取范式对应的是“或与式”也就是最大项之积它对应另一种电路结构先“或门”后“与门”。两种结构各有适用场景有时候“或与式”用到的门更少这就是为什么两个范式都要掌握。7.2 判定公式等值的标准标尺判断两个命题公式是否逻辑等值最朴素的方法是一人画一张真值表再对比。但如果你已经会求主范式办法就简单得多把两个公式都化成主析取范式看编号集合是否完全一致。一致就是等值不一致就一定不等值。这个方法的好处是不会受公式表面形态的影响——你再怎么换写法同一个逻辑函数的主范式是唯一的。这背后是一个非常重要的数学结论主析取范式主合取范式同理是命题公式在逻辑等值关系下的“标准形”每个等值类里只有一个标准形。它就像给每个公式拍了一张标准证件照认人认脸认照片。如果你想进一步了解它在算法设计里的意义可以这样想判断一个公式是否可满足就等价于看它的主析取范式是否为空——不可满足的公式完全没有结果为1的行。这个问题在现代逻辑、自动推理里就是可满足性问题的前身很多软件测试、程序验证工具的核心逻辑都跟它沾边。7.3 学完这一节之后你的思维模型应该升级成什么我从教学和批改作业的体验出发说点可能没人告诉你的事情。学主范式这一节最终要达到的能力不是“会套步骤算题”而是建立一种“真值表即公式、公式即真值表”的双向翻译意识。看到任何一个复杂公式你能很快在脑子里把它翻译成一张由0和1组成的表看到一张表你也能反手写出对应的标准公式。这个能力在后面学谓词逻辑的前束范式、学关系数据库的规范化、学自动机理论的时候都会反复用到。有同学问过我“这些范式题以后写代码用得上吗”我通常这么回答你不太会在日常开发里手算主范式但你写逻辑表达式的化简工具、写编译原理里的布尔表达式分析、做电路综合算法的时候这套形式化翻译的思维方式就是底层能力。它可能不会以考题的形式出现在你的工作里但它训练的那种严谨等价变换的头脑是程序员和工程师都需要的。最后分享一个我让学生反复练过的小技巧学完这一节自己随便写一个三变元的公式分别用真值表法和等值演算法各求一遍主析取范式再反推主合取范式最后对一下编号集合是否互补。第一次做的时候大概率会对不上但只要你把对不上的那一步揪出来你对主范式的理解就又深了一层。这套自我验证流程比我讲任何注意事项都管用。