离散数学逻辑核心：命题逻辑、真值表与谓词逻辑推理

离散数学里逻辑这一章是最容易被低估的部分。不少人图论能刷、组合能推、关系闭包算得飞快一到命题逻辑的真值表就开始凭感觉填一到谓词逻辑的翻译题就开始自由发挥。我自己当年也是这样过来的后来带过几轮课、也看过不少同学的作业慢慢意识到一个事实逻辑这一章考的从来不是计算能力而是把自然语言精确翻译成形式符号、再按规则严格推演的能力。它不像其他章节那样有套路公式一套就出结果的爽感反而处处是语文陷阱和约定俗成的坑。这篇内容就是把这个过程中的核心概念、实操方法、验证手段和我见过的典型翻车场景一次讲透无论你是正在学这门课的学生还是想补一补布尔代数基础、把它用到程序条件判断和电路化简里的工程师都能直接拿去用。1. 逻辑这一章到底在训练什么能力1.1 从会算到会证的转折点离散数学前面几章很多时候是给定输入、按定义输出的机械过程两个集合求交并差、关系矩阵做布尔乘、图的邻接矩阵求可达性。这些内容有一个共同点——答案唯一过程可验证。你算完了回头一检查就知道对不对。逻辑这一章不一样。它第一次要求你面对一个需要你构造过程的问题给一组前提证明某个结论成立。这个过程没有唯一写法同一道题可以用假言推理走三步也可以用反证法走五步还能用附加前提法绕一个弯。于是很多人的第一反应是我推出来了但不知道算不算对。这就是从会算到会证的门槛。我的观察是跨过这道门槛的关键不在于背更多公式而在于建立两个习惯第一每写一步都问自己这一步用了哪条规则、作用在哪两个式子上第二在动手之前先用真值表或者代入特殊值验证一遍结论是否真的成立。前者保证过程可审计后者保证方向没跑偏。这两件小事做扎实逻辑部分的失分能少一大半。另外要提醒的是逻辑的形式化程度比想象中高。日常语言里或者经常是排他的你要么去要么不去如果经常带因果如果下雨地就湿暗含地湿是因为下雨但形式逻辑里这些都只保留真值关系因果关系一律不管。**接受这种降维是学好这一章的心理前提。**很多人学不下去本质上是拒绝接受形式化带来的语义损失。1.2 逻辑和日常写代码的关系比你以为的紧如果只是应付考试上面那段话就够了。但我更想说命题逻辑是所有条件判断的老祖宗。写if (user ! null user.age 18)的时候你其实在写一个合取式。短路求值short-circuit evaluation能成立底层依赖的是¬P → (P ∧ Q ≡ False)这类恒等式——左边假了右边拆开判断就是假与任何值都为假所以没必要算。反过来如果语言不做短路这段代码就会在user为 null 时崩掉。看起来是语法糖本质是逻辑等价式的工程化应用。再比如 SQL 里WHERE age 18 AND age 30当age为NULL时表达式结果不是真也不是假而是UNKNOWN。这是一个三值逻辑系统UNKNOWN AND FALSE FALSE但UNKNOWN AND TRUE UNKNOWN。搞不清楚这一点的人写出来的过滤条件会在边界数据上悄悄丢行或者多行。还有契约式编程里的前置条件、后置条件单元测试里的断言状态机里的跃迁条件甚至正则表达式里的字符类并集都是命题逻辑的直接应用。谓词逻辑则在数据库的EXISTS、FORALL部分引擎以及类型系统里的全称量化中反复出现。把这一章学扎实不是学一门考完就忘的课是给后面所有涉及条件、约束、断言的场景打地基。2. 命题联结词五个符号背后的约定2.1 蕴含符号为什么假命题蕴含一切这是逻辑这一章第一个劝退点也是我见过最多人卡住的地方。真值表里P → Q只在P 真、Q 假时为假其余全真。很多人第一反应是凭什么P是假的时候整个式子就是真的我的解释方式是这样的把P → Q理解成一个承诺。我说如果明天下雨我就带伞。现在请问什么情况下算我说话不算话只有一种明天下雨了而我确实没带伞。如果明天压根没下雨我不管带不带伞你都没法说我食言。如果明天下雨了我也带伞了那我是守信用的。这就是P → Q的真值表。P为假时式子为真术语叫空真vacuously true。这个约定看起来反直觉但它是唯一能让推理规则自洽的选择。如果我们反过来规定P假则P → Q假那么假言推理就废了——因为很多定理的前件在大部分取值下都是假的这些定理就全都变成假命题了。更麻烦的是P → Q和¬P ∨ Q的逻辑等价关系会崩掉整个等价代换体系就得推倒重来。实际做题时有个特别好用的小技巧把蕴含统一改写成非前件或后件。P → Q ≡ ¬P ∨ Q这一步改写之后式子就只剩¬、∨、∧三个联结词后面套德摩根律、套分配律都变得很顺手。我几乎所有的等价推导都是这么开头的。2.2 充分与必要这两个词怎么不搞混自然语言里的四个说法对应四个不同的逻辑式考试里专门用来设陷阱日常说法逻辑形式记忆锚点P 是 Q 的充分条件P → Q有 P 就够推 QP 是 Q 的必要条件Q → P没 P 就没 QP 当且仅当 QP ↔ Q双向都成立只有 P 才 QQ → P只有后面是必要的只有...才...这个句式最容易翻。比如只有通过体检才能上岗形式化是上岗 → 通过体检而不是通过体检 → 上岗。判断方法是把句子读成如果 Q那么必须 P看哪个方向不成立。如果上岗了那么必定通过体检——成立如果通过体检那么必定上岗——不成立。所以箭头从 Q 指向 P。我建议在做这类翻译题时先在草稿上写出如果…那么…的自然语言版本再转换符号不要一步跳到符号。这一步多花十秒钟能避免后面全盘重来。异或⊕、与非↑Sheffer 竖、或非↓这几个多余的联结词之所以常考是因为它们涉及功能完备集的概念{¬, ∧}是完备的{↑}单独也是完备的{↓}单独也是完备的。这个知识点在数字电路里会直接用到——只用一种门电路搭出所有逻辑功能是芯片设计里的基本操作。异或则有天然的可逆性和奇偶校验特性网络传输里的校验位、密码学里的流加密都在用它。3. 真值表最笨的方法往往最稳3.1 一张表怎么排才不会乱真值表看起来毫无技术含量但真正动手排的时候错得最多的恰恰是排表本身。我总结了一套固定流程数变元个数 n确定行数2^n。三个变元就是 8 行四个变元 16 行。先把行数写死不要边写边数。确定列的左右顺序变元列 → 中间子公式列 → 最终结果列。所有子公式都单独成列不要试图心算。变元的取值按照二进制计数排列最右边一列每行交替真假往左一列每两行交替再往左每四行交替。这样排出来最不容易漏行、重行。子公式按依赖顺序依次填先填只含变元的再填复合的。举个具体例子判断(P → Q) ∧ (Q → R) → (P → R)是否永真。变元三个8 行。列分别是P、Q、R、P→Q、Q→R、(P→Q)∧(Q→R)、P→R、整体。填完你会发现最后一列全为真说明这是永真式——也就是假言三段论。提示真值表验证的是是否永真不是是否可满足。如果一个推理的前提合取式是矛盾式那么前提 → 结论恒真但推理本身没有任何意义。所以验证推理有效性时只检查前提全真而结论假的赋值是否存在比直接算蕴含式更贴近本意。3.2 用脚本批量验证把 2 的 n 次方交给机器手排三四个变元还行五个以上就很容易出错而且检查成本极高。我通常会用一段十几行的 Python 脚本兜底先用机器确认结论再回来手写推导过程。脚本不需要装任何第三方库from itertools import product def check(vars_, premises, conclusion): 检查 前提 ∧ 前提 ∧ ... → 结论 是否有效 n len(vars_) print( | .join(vars_) || 结果) valid True for values in product([False, True], repeatn): env dict(zip(vars_, values)) prem_true all(p(env) for p in premises) concl conclusion(env) status if prem_true and not concl: status -- 反例 valid False row | .join(T if v else F for v in values) print(f{row} || {prem_true and concl}{status}) return valid # 例验证 (P→Q) ∧ (Q→R) → (P→R) P lambda e: e[P] Q lambda e: e[Q] R lambda e: e[R] valid check( [P, Q, R], [lambda e: (not P(e)) or Q(e), # P → Q lambda e: (not Q(e)) or R(e)], # Q → R lambda e: (not P(e)) or R(e) # P → R ) print(推理有效 if valid else 推理无效)这段代码的价值不在于替你写作业而在于给你一个独立的裁判。手推完一个五步证明你心里没底跑一遍脚本立刻知道结论对不对。如果错了脚本还会把反例那一行打出来你能反查到具体是哪一步推错了。如果你的环境里装了符号计算库sympy的satisfiable更省事直接把逻辑式子交给它判断可满足性就行。不过要注意它判断的是存在满足赋值验证推理有效性时你需要判断的是前提 ∧ ¬结论是否不可满足别搞反方向。另外有个实用的做法给每个变元起有意义的名字比如用rain、umbrella而不是P、Q。脚本里读起来一目了然也便于你回头对照题目检查翻译对不对。4. 逻辑等价与范式化简是手艺不是背公式4.1 常用等价式该背到什么程度等价式一共就那么十几条但硬背的效果很差。我建议按**作用分组记**而不是按字母顺序记。分组等价式用途消去蕴含与双蕴含P→Q ≡ ¬P∨QP↔Q ≡ (P→Q)∧(Q→P)一切推导的第一步否定内推¬(P∧Q) ≡ ¬P∨¬Q¬(P∨Q) ≡ ¬P∧¬Q¬¬P ≡ P把否定压到变元上分配与合并P∧(Q∨R) ≡ (P∧Q)∨(P∧R)P∨(Q∧R) ≡ (P∨Q)∧(P∨R)转成范式吸收与化简P∨(P∧Q) ≡ PP∧(P∨Q) ≡ P减少变元恒定式P∨¬P ≡ TP∧¬P ≡ FP∨F ≡ PP∧T ≡ P判定永真与矛盾我的实践是前两组必须背到条件反射后三组会用就行。因为任何等价推导的前两步都是消蕴含、推否定这两步卡住就完全动不了。而后三组遇到具体题目现推完全来得及甚至可以靠真值表反查。要特别提醒的是分配律在布尔代数里的对称性。代数学里a(bc)abac但abc≠(ab)(ac)。布尔代数里这两条都成立因为∨和∧互为对偶。这个特性在化简电路时非常有用很多人脑子里还带着算术代数的直觉看到把或分配到与上就觉得别扭其实是没转过弯来。4.2 主析取范式与主合取范式从真值表直接读出来范式是考试的重头戏也是最容易算出一半的地方。我总结的步骤很简单主析取范式Σ 形式跳着看真值表把结果为T的每一行写成一个极小项。极小项的规则是该行中变元取T就写原变元取F就写其否定然后用∧连起来最后用∨把所有极小项串起来。主合取范式Π 形式反过来把结果为F的每一行写成一个极大项。极大项的规则是取T写否定取F写原变元用∨连起来再用∧串联。拿P → Q做例子。真值表四行只有PT, QF那行为假。主析取范式读三个真行分别是¬P∧¬Q、¬P∧Q、P∧Q用二进制编号是m0 ∨ m1 ∨ m3记作Σm(0,1,3)。主合取范式读一个假行得到¬P ∨ Q对应极大项M2记作ΠM(2)。两者是同一个公式的两种面孔可以通过Σm(i)与ΠM(所有未出现的编号)互相转换。这个转换关系非常值得记已知一种范式另一种范式就是把没出现的编号全取上。这里有个实操细节编号的二进制顺序必须固定为变元按字典序排列原变元记 1否定记 0。比如变元是P, Q, R赋值PT, QF, RT对应二进制101即十进制 5。如果顺序搞反编号全乱后面的范式互相转换就全错了。我在批改时见过的错误里编号错位能排进前三。注意主析取范式和主合取范式都不是唯一的写法——极小项之间的顺序可以调换同一极小项内部变元的顺序也可以调换。但编号集合是唯一的。所以答题时写编号集合最安全写成展开式时一定要反复核对每个极小项里哪些变元带否定。5. 推理规则形式证明的招式与心法5.1 八条基本规则怎么记住推理规则本质上是从已有的式子合法地生成新式子的许可证。常用的八条可以按输入形式归类记规则名前提结论一句话理解假言推理MPP→Q,PQ前件成立后件紧跟拒取式MTP→Q,¬Q¬P后件不成立前件也不成立假言三段论P→Q,Q→RP→R蕴含可以连起来析取三段论P∨Q,¬PQ排除一个剩下那个附加PP∨Q真的可以或上任何东西化简P∧QP合取可以拆合取P,QP∧Q两个真可以拼消解P∨Q,¬P∨RQ∨R消掉互补的那个变元这八条里假言推理和拒取式是心脏绝大部分证明都是由这两条驱动的。附加和化简是搬运工负责把式子改造成能套用前两条的形状。消解规则在自动定理证明里地位极高——Prolog 的求解内核本质就是反复做消解把目标取反后推到空子句。记忆上有两个抓手蕴含类规则看箭头方向箭头必须同向才能串假言三段论箭头首尾相接才能推MP析取类规则看互补项能否消掉析取三段论、消解。5.2 证明推不下去时的三条自救路径推证明卡住是常态我通常用三条路径破局按成本从低到高排第一条反证法。把结论取反加进前提推出矛盾。这条路对结论是否定式或结论含→的题目特别有效。因为一旦取反¬(P→Q)就化简成P∧¬Q直接多出两个原子前提弹药立刻充足。我在实战里发现当结论是蕴含式时反证法有八成概率比直接证更短。第二条附加前提法CP 规则。要证P→Q就把P拉进前提集合去证Q证完再收回来。这个方法在逻辑上等价于演绎定理工程上等价于先把目标拆成假设和子目标。写证明时它的好处是前提变多、变元变少路径更清晰。第三条分情况讨论。前提里出现P∨Q又没法消掉的时候就分两支一支假设P一支假设Q两支都推出同一个结论R于是得R。这条路写起来长但几乎不会走死适合作为兜底。再补充一个非常实用的技巧把中间结论写成子公式并编号。比如第 4 步推出¬R第 5 步要用它那就明确写由 2、4 用拒取式得 5.¬P。每一步都标注用了哪几个式子、用了哪条规则这样即使最后结论错了阅卷时也能看出你的思路拿到过程分。而更实际的是标注过的证明自己检查起来快得多——回头一眼扫过去哪一步没有依据立刻能发现。6. 谓词逻辑量词把逻辑从句子推进到结构6.1 翻译题的三步法谓词逻辑的翻译题是失分重灾区。我固定用三步走基本不会跑偏第一步划论域。题目给不给全集很重要。如果论域是所有人那存在一个学生就要写成∃x(Student(x) ∧ ...)如果论域已经被限定为所有学生那Student就不需要了直接∃x(...)。论域一变写法的形态就变很多错误都是从这一步埋下的。第二步定谓词。把句子里的名词、形容词、动词拆成谓词。P(x)x 是人S(x)x 是学生L(x, y)x 喜欢 y。谓词的元数几元要数清楚x 把 y 介绍给 z是三元谓词漏掉一个变元后面全错。第三步定量词和连接词。这里有一条铁律全称配蕴含存在配合取。所有 A 都是 B∀x(A(x) → B(x))有的 A 是 B∃x(A(x) ∧ B(x))为什么是这样用反例法想一下就清楚了。如果写成∀x(A(x) ∧ B(x))它的含义是论域里每一个东西既是 A 又是 B这比原句强得多——原来只说是 A 的那些东西是 B没说所有东西都是 A。而∃x(A(x) → B(x))更糟只要存在一个不是 A 的东西蕴含式就为真这句话几乎恒真毫无约束力。全称配蕴含、存在配合取这句话我建议直接抄在草稿纸顶上每做一道翻译题就抬头看一眼。它背后是上面这个反例分析理解了原因之后你甚至可以自己现推出来。6.2 量词否定与辖域翻车密度最高的地方否定一个带量词的式子规则本身很简单¬∀xP(x) ≡ ∃x¬P(x)¬∃xP(x) ≡ ∀x¬P(x)白话就是并非所有等于存在不是不存在等于全都是不是。但这条规则一旦嵌套就容易开始乱套。处理嵌套的标准做法是从外往里逐层剥最外层是∀就换成∃否定号往里推一格继续处理下一层直到推到谓词上。这个过程和消去蕴含、把否定压到变元上的思路完全一致。比否定更容易错的是量词顺序。∀x∃y L(x,y)和∃y∀x L(x,y)差得非常远∀x∃y L(x,y)每个人都有自己喜欢的人每个人可以喜欢不同的人。∃y∀x L(x,y)存在一个人被所有人喜欢。前者几乎总是成立后者是很强的断言。**全称在前、存在在后是依赖关系存在在前、全称在后是统一对象。**判断的时候问一句这个 y 是不是跟着 x 变的如果答案是是那就是∀x∃y。再有就是辖域和变元绑定。∀x(P(x) ∧ ∃x Q(x))这种写法里内部那个x被内层量词重新绑定了外层的∀x对它无效。这种变元遮蔽在教材里出现得不多但一旦遇到先做约束变元换名把内层的x换成全新名字z式子立刻变得清晰∀x(P(x) ∧ ∃z Q(z))。换名是等价变形不影响语义是我处理复杂式子时的习惯动作。最后提醒量词的分配律只部分成立等价式是否成立∀x(P(x)∧Q(x)) ≡ ∀xP(x)∧∀xQ(x)成立∃x(P(x)∨Q(x)) ≡ ∃xP(x)∨∃xQ(x)成立∀x(P(x)∨Q(x)) ≡ ∀xP(x)∨∀xQ(x)不成立∃x(P(x)∧Q(x)) ≡ ∃xP(x)∧∃xQ(x)不成立前两个成立的直觉是全称管交集、存在管并集。第三个不成立可以取反例每个整数要么是偶数要么是奇数为真但每个整数都是偶数或者每个整数都是奇数为假。第四个的反例是存在一个人既是老师又是学生未必成立但存在老师且存在学生显然为真。只要记住A 配 ∧ 可以提、E 配 ∨ 可以提交叉的都不行剩下的靠反例一想就通。7. 高频翻车现场几种典型错误的复盘7.1 逆命题、否命题、逆否命题的三个方向这是最经典的混淆点而且错的人往往还不觉得自己错。四个命题的关系是名称形式与原命题真假关系原命题P → Q——逆命题Q → P不必同真假否命题¬P → ¬Q不必同真假逆否命题¬Q → ¬P恒同真假真正恒等的只有原命题 ↔ 逆否命题这一对。逆命题和否命题虽然互为逆否关系但它们和原命题没有必然联系。我见过最典型的错误是把所有 A 都是 B的逆否写成所有非 A 都不是 B。正确的逆否是所有非 B 都不是 A。用具体例子检查一下原命题所有矩形都是平行四边形逆否命题应该是所有不是平行四边形的都不是矩形——成立。如果写成所有不是矩形的都不是平行四边形那就错了。**检查方法很简单找一个满足前件、不满足后件的反例如果找得到就说明写反了。**做翻译和改写题时我习惯随手构造一个小反例来验证比死记表格可靠。7.2 逻辑等价和逻辑蕴含的符号混用P ≡ Q和P → Q是两个层面的东西但很多人写着写着就混了。核心区别P → Q是一个公式它本身有真假值可以出现在别的公式里。P ≡ Q是一个元语言断言说的是P 和 Q 的真值对所有赋值都相同它不是一个可以被否定的公式。这个区别在写证明时很现实如果你写由德摩根律得¬(P∧Q) ≡ ¬P∨¬Q这是合法的等价变形但如果你写由德摩根律得¬(P∧Q) → ¬P∨¬Q虽然这个蕴含式也是永真的但下一步你就没法把它当作替换规则用了因为替换需要等价不是蕴含。**判断依据如果你要拿它来替换式子中的子公式必须用等价如果只是要推出某个结论用蕴含。**这个区分看起来吹毛求疵但它直接影响你的证明能不能继续往下写。7.3 真值表列数不够导致的连锁错误还有一种错误非常隐蔽证明过程完全正确但最终答案错了原因是翻译那一步就错了。这种错误真值表查不出来因为你的真值表是在验证一个错的命题。防御办法是回译把形式化后的式子用自然语言重新读一遍看是不是和原句意思一致。比如题目是没有不努力的学生能通过考试形式化为¬∃x(Student(x) ∧ ¬Work(x) ∧ Pass(x))。回译一遍不存在这样一个学生他同时满足是学生、不努力、通过考试——意思对上了。如果回译出来是没有学生是不努力的或者所有不努力的人都不能通过考试那就要检查量词的作用范围是不是画宽了。回译这个动作通常只要十几秒但能拦下大量看起来对但其实翻错的错误。我个人的经验是翻译题的错误率有一半来自这一步没做。8. 把逻辑落到手上几件值得动手做的事8.1 一份可以贴在桌上的自查清单学完这一章我给自己的检查项是固定的几条做任何一道题之前扫一眼蕴含是否已经改写成¬P ∨ Q否定是否已经推到原子命题上量词的作用域在哪里边界括号有没有标清楚全称配的是不是蕴含存在配的是不是合取结论方向有没有搞反充分条件 vs 必要条件变元有没有被内层量词意外捕获用了替换的地方依据的是等价还是蕴含这七条覆盖了我踩过的绝大多数坑。写在便签上贴屏幕边做题时视线扫一遍成本极低。另外还有一个习惯每做完一道证明题用真值表或者脚本把结论验一遍哪怕你确信自己是对的。验证一次一分钟比事后重做半小时划算。我当年就是因为偷懒不验证在一道看似简单的题上把充分条件和必要条件写反整道题白丢。8.2 手推和机验的比例控制有同学会问既然脚本能算还要手推干什么答案是两者解决的是完全不同的问题。脚本擅长的是判定给定一个公式判断它是否永真、是否可满足、给出反例赋值。这一类问题有固定的算法流程机器做得又快又准。手推擅长的是构造从一个前提出发找到一条通向结论的推理链。这个过程没有通用算法能在合理时间内给出最短的证明需要人根据式子的形状去猜、去试、去回溯。而恰恰是这种猜和试的能力才是这一章真正想训练的东西——它迁移到任何需要构造论证的场合写技术方案、做架构决策、排查线上问题时的因果链分析用的都是同一套肌肉。我的建议比例是七成手推、三成机验。手推时把每一步的依据写清楚卡住了跑脚本看反例等推完了再跑一遍脚本确认结论。两边都练两边都不荒废。最后再分享一个我自己用得很顺手的小方法把每一类题型整理成一个急救卡——翻译题写三条论域、谓词、量词搭配等价推导题写三条消蕴含、推否定、转范式证明题写三条反证、附加前提、分情况。一共九条还没一张 A4 纸大。考场上或者项目里真遇到卡壳的时候翻出来按顺序试绝大多数情况下试到第二条就能动了。