我刚开始啃《离散数学》02324的时候第一章“命题与命题公式”就让我卡了好一阵。明明每个字都认识合在一起就不知道在讲什么。后来才明白这一章是整个离散数学的“语法入门”——后面的谓词逻辑、集合论、关系、图论全都建立在这套命题符号和推理规则之上。学不好这一章后面几乎没法推进。这篇文章就把我折腾出来的经验、踩过的坑、做题套路一并整理出来给正在备考自考02124或者刚上完离散数学课的朋友做个参考。内容按“概念理解、公式记忆、做题方法、常见坑”四条线展开既讲清楚“是什么”也讲清楚“为什么这样规定”以及考场上怎么快速拿分。教材以左孝凌版为主但知识点和大多数离散数学教材是通用的。1. 学第一章前先搞清楚要学成什么样1.1 这一章的四个核心能力目标离散数学第一章不是让你背概念而是培养四种基本能力。我后来发现考试里所有题目基本都逃不出这四个能力范围。第一能把自然语言翻译成符号语言。给你一句话比如“只有天下雨我才带伞”你要能写成 P→Q 的形式并且研究方向不能反。第二能判断复合命题的真假。给一个复杂的公式比如 (P→Q)∧(¬P∨Q)你能通过真值表确定它到底是重言式、矛盾式还是可满足式。第三能证明两个命题公式等价。用等值演算一步步把公式变形证明左边能变成右边或者两者都能变成同一个标准形式。第四会做逻辑推理。给你几个前提和一个结论你能用蕴含式和推理规则写出一串证明说明结论是可靠推出的。这四项能力在考试中对应的是选择题、填空题、计算题和证明题。不少人第一遍学完感觉“都看懂了”一做题就懵问题就出在只看了定义没有刻意训练这四种能力。1.2 第一章和其他章节怎么关联讲个我自己的体会离散数学这门课各章节之间是有依赖关系的。第一章是地基第二章谓词逻辑是它的扩展第三章集合论用的是命题逻辑的语言来描述元素属于集合第四章关系中的自反性、对称性定义里全是“如果...那么...”这类命题公式判断后面图论中的可达性、连通性同样需要逻辑推理能力。所以真的不能抱着“先混过去后面再说”的心态学第一章。你后面遇到的很多表示法和推理思路底层逻辑都来自这里。我身边有同学第一章死活弄不明白“蕴含”的方向结果学关系那一章讲到“偏序关系、函数单射满射”的时候完全跟不上又回来补基础反而更费劲。2. 命题、联结词与真值表必须刻进脑子的基础层2.1 命题的定义并不是所有句子都是命题命题的定义本身很简单能判断真假的陈述句。关键是“能判断真假”这五个字。疑问句“你今天吃饭了吗”不是命题因为无法判定真假祈使句“把门关上”也不是感叹句“好美的风景”同样不是。每本教材都会强调这一点考试会专门出选择题考你“下列哪个语句是命题”。这里有个容易忽略的坑有些句子当时的真假不知道但原则上是确定的它仍然是命题。比如“火星上有生命”我们现在可能还不知道答案但它一旦有确定的客观事实就有真或假所以它算命题。反过来“这个数很大”这种含糊其辞的句子因为“大”没有标准不能判断真假所以不是命题。这类判断题的关键是“真假是否客观唯一”而不是“我是否知道真假”。还有一个点需要注意悖论不是命题。“这句话是假的”这种自我指涉的句子如果它为真那么它说的是真的也就是它为假如果它为假那么“这句话是假的”为假也就是说这句话是真的。真和假都矛盾不能判定真假所以不是命题。我一开始总把这个记混考试前专门在笔记上标红过。命题变元则用一个字母通常 P、Q、R来表示任意命题。命题变元本身没有真假只有代入具体命题后才有真假。这和代数里的x有点像x不是具体数字但可以代入具体数字去算。2.2 五个联结词从自然语言到符号语言的关键复合命题由原子命题通过联结词构成。核心联结词有五个否定 ¬P、合取 P∧Q、析取 P∨Q、蕴含 P→Q、等价 P↔Q。我逐个说否定 ¬P就是“非P”真值反转P真则¬P假P假则¬P真。自然语言里的“不”“没有”“并非”都对应它。合取 P∧Q表示“P并且Q”只有当两个都为真时才为真。生活中常说“不但...而且...”“虽然...但是...”在逻辑上都表示合取。析取 P∨Q表示“P或者Q”只要有一个为真整个就为真。这是最容易出问题的地方因为自然语言里的“或”有两种兼或和异或。普通析取是兼或允许两者同时成立。而“他要么去北京要么去上海”是异或两者不能同时为真。命题逻辑里默认的“或”是兼或除非题目特别说明否则别把“或”理解成非此即彼。蕴含 P→Q读作“如果P那么Q”。P叫前件Q叫后件。真值规定只有当前件真、后件假时整个命题为假其余情况都为真。等价 P↔Q读作“P当且仅当Q”两者真假相同则为真否则为假。它本质上是 (P→Q)∧(Q→P) 的缩写。我当初最不理解的就是蕴含。为什么“如果113那么地球是方的”是真的左孝凌教材里直接把这个列为约定当时我死活想不通。后来我找到一个直观解释蕴含式 P→Q 承诺的是“如果P发生Q一定发生”。如果P没发生前件假这个承诺并没有被违背所以不算假。举个例子“如果我中了彩票我就给你买辆车”——只要我没中彩票这句话无论怎样都不是假话因为承诺的前提没发生。只有我真中了彩票却没给你买车这句话才是假的。这样理解之后蕴含的真值表就记住了。2.3 联结词的优先级和自然语言翻译的坑五个联结词有规定的运算优先级这一点做题时必须按顺序处理¬ 最高然后是 ∧然后是 ∨然后是 →最后是 ↔。遇到括号先算括号内。记不住优先级的时候最稳妥的办法就是加括号公式里没有歧义比简洁重要。自然语言翻译成符号语言是考试重灾区。比如“只有P才Q”翻译成 Q→P 而不 是 P→Q“除非P否则Q”等价于 ¬P→Q也等价于 ¬Q→P这些反直觉的地方大家要格外留意。左孝凌教材里有一类题专门练自然语言翻译我建议把常见的句子类型整理成一个表自然语言表达符号化结果说明如果P那么QP→Q前件是条件只有P才QQ→P翻译成“Q推出P”只要P就QP→Q与“如果”一致除非P否则Q¬P→Q等价于 ¬Q→PP仅当QP→Q强调P是Q的充分条件当且仅当P↔Q双向推出我当时照着这个表反复造句翻译练了大概两三天后才算顺手。做这类题的时候第一件事不是急着写符号而是先找出“谁是条件”“谁是结论”再决定箭头方向。3. 命题公式类型与等值演算做题的核心武器3.1 三种公式类型重言式、矛盾式、可满足式命题公式由命题变元、联结词和括号组成。给公式中的每个变元赋值公式就会得到一个真值。根据所有赋值下的真假情况可以把公式分成三类重言式永真式无论变元取什么值公式都为真。比如 P∨¬P。矛盾式永假式无论变元取什么值公式都为假。比如 P∧¬P。可满足式至少有一种赋值让公式为真。重言式和矛盾式之外所有公式都属于这一类也就是说可满足式的范围最大。判断一个公式属于哪一类最无脑的方法是真值表法列出所有赋值情况一列真值看看结果全为真、全为假还是有真有假。这个方法慢但不容易错。我复习时遇到复杂公式第一遍就用真值表打底确保自己理解正确然后再学等值演算来提速。考试里常见问法有三种判断公式类型、求主析取范式、求主合取范式。后两者我稍后会详细讲这里先确认一个观念判断类型是基本功后面所有逻辑推理题都建立在“有效性”这个概念上而有效推理本质上就是“前提合取蕴含结论”是重言式。3.2 常用等值式背熟等于拿到送分题等值式就是两个公式在所有赋值下真假相同记为 A⇔B。最稳的记忆方法是先理解再记忆但有几个是纯规则建议直接背双重否定律¬¬P ⇔ P等幂律P∨P ⇔ PP∧P ⇔ P交换律P∨Q ⇔ Q∨PP∧Q ⇔ Q∧P结合律(P∨Q)∨R ⇔ P∨(Q∨R)(P∧Q)∧R ⇔ P∧(Q∧R)分配律P∨(Q∧R) ⇔ (P∨Q)∧(P∨R)P∧(Q∨R) ⇔ (P∧Q)∨(P∧R)德摩根律¬(P∧Q) ⇔ ¬P∨¬Q¬(P∨Q) ⇔ ¬P∧¬Q吸收律P∨(P∧Q) ⇔ PP∧(P∨Q) ⇔ P零律P∨1 ⇔ 1P∧0 ⇔ 0这里的1代表重言式0代表矛盾式同一律P∨0 ⇔ PP∧1 ⇔ P否定律P∨¬P ⇔ 1P∧¬P ⇔ 0蕴含等值式P→Q ⇔ ¬P∨Q等价等值式P↔Q ⇔ (P→Q)∧(Q→P) ⇔ (P∧Q)∨(¬P∧¬Q)假言易位P→Q ⇔ ¬Q→¬P归谬论(P→Q)∧(P→¬Q) ⇔ ¬P这里我需要专门讲一下蕴含等值式 P→Q ⇔ ¬P∨Q因为它是很多演算题的入口。理解了它蕴含就化成了否定和析取后面再做主范式、做推理运算规律就全都统一了。它和我们之前说的蕴含真值表本质是一回事只有 P 为真且 Q 为假时整个式子为假其余时候都为真。你仔细看 ¬P∨Q 的真值表会发现完全一致。做等值演算时有一个原则看到 → 就想办法换成 ¬ 和 ∨看到 ↔ 就先展开成两个蕴含的合取。这是在标准解法里最通用的处理顺序。等值演算就是反复用这些规则把公式变形直到得到你想要的形式。3.3 等值演算实操三步套路等值演算题大概率会考“证明 A⇔B”。我做完大量真题之后总结出一个非常实用的三步套路第一步把等号两边都化成只含 ¬、∧、∨ 的形式。有 → 就往 ¬P∨Q 化有 ↔ 就往 (P→Q)∧(Q→P) 化。第二步盯着复杂的一边用分配律、德摩根律、吸收律往简单的那边凑。第三步两边都变到同一个中间形式等式成立。举个例子证明 ¬(P→Q) ⇔ P∧¬Q。先处理左边因为 P→Q ⇔ ¬P∨Q所以 ¬(P→Q) ⇔ ¬(¬P∨Q)。再用德摩根律¬(¬P∨Q) ⇔ ¬¬P∧¬Q ⇔ P∧¬Q。整个过程只有三步但对初学者来说难在“要不要用德摩根律”这个判断上。我的经验是看到括号外有否定优先考虑德摩根律看到嵌套的括号先处理最内层括号看到 P∨(P∧Q) 这种结构直接用吸收律化简。这些模式见多了之后一眼就能瞄出破绽。做这一节时我建议大家准备一张A4纸做“公式速查卡”左边写公式名右边写公式本身考前反复看闭卷默写一遍默不出来的重点标记。左孝凌教材课后习题里有一整组等值演算题跟着那个顺序练熟练度上得很快。我当初刚开始演算很慢一道题要写十几步练了一周后基本能稳定在5步左右解决。4. 蕴含关系与推理规则考试证明题的主场4.1 什么是“蕴含值”“蕴含值”这一说法在自考题中经常出现说得直白一点就是如果 A→B 是重言式就称 A“蕴含”B记作 A⇒B。这里的 ⇒ 不是联结词而是表示两个公式之间存在永真的蕴含关系。这个符号和 → 的区别一定要搞清楚→ 是公式里的联结词而 ⇒ 是在说“无论变元怎么取值蕴含都为真”是对公式关系的一种判断。如何判断 A⇒B最可靠的方法是看 A→B 是不是重言式。还有一种常用判定方法是假设前件 A 为真若能推出 B 也必须为真则蕴含成立或者假设后件 B 为假若能推出 A 也为假则蕴含成立。这两种方法在证明题中非常实用尤其是归谬式的证明。4.2 左孝凌教材里那组基本蕴含式怎么记左孝凌版教材列出了12个基本蕴含式I1到I12自考计算题和证明题经常直接考。我当年把它们分成三组来记第一组是“加减法组”直观易懂A∧B⇒AA∧B⇒B合取变小项目A⇒A∨BB⇒A∨B小项目变大析取¬A⇒A→B从假前提可以推出任何命题B⇒A→B结论为真时任何蕴含都成立¬(A→B)⇒A¬(A→B)⇒¬B蕴含为假时前件真且后件假第二组是“附加前提组”做题时用于往前提里增加条件A→B⇒A→(B∨C)结论加析取项不影响成立A→B⇒(A∧C)→(B∧C)前后件同时合取一个命题蕴含关系保留A→B⇒(A∨C)→(B∨C)前后件同时析取一个命题蕴含关系保留第三组是“推理骨架组”对应我们后面要用的推理规则A→BB→C⇒A→C假言三段论A→B¬B⇒¬A拒取式A∨B¬A⇒B析取三段论记这12个式子不能死记要结合上面的分组去理解。我自己有个笨办法每记一个式子就举一个生活中的例子验证它为什么成立。比如 ¬A⇒A→B意思是“如果P是假的那么‘如果P则Q’这句话是真的”这正是我们前面讲蕴含真值表时的约定想通之后这个式子就不再抽象了。4.3 推理证明题的标准写法推理证明题在考试里通常是给出若干前提要求证明某个结论。本质上就是在已知条件成立的前提下不断用蕴含式和推理规则推出新结论直到推出目标。最常用的推理规则有四个假言推理分离规则A→BA 得到 B拒取式A→B¬B 得到 ¬A析取三段论A∨B¬A 得到 B假言三段论A→BB→C 得到 A→C另外有构造性二难A→BC→DA∨C 得到 B∨D。部分教材会考左孝凌教材里也有相关内容建议一并记住。举个例子证明题前提 P→QQ→R¬R结论 ¬P。写法如下(1) P→Q 前提 (2) Q→R 前提 (3) ¬R 前提 (4) P→R (1)(2)假言三段论 (5) ¬P (3)(4)拒取式格式上每一行都要标明依据不能直接跳步。我见过很多同学考试时跳步省事结果被判过程分不足。自考判卷按步骤给分所以每一步都要写清楚用了哪条规则别嫌啰嗦。还有一种解法会用到 CP规则附加前提法要证 A→C可以把 A 当作临时前提加进去推出 C然后就得到 A→C。如果结论本身是个蕴含式用这个规则特别方便。我在真题里试过很多次确实比直接证要快不少。做推理题时我建议先看一眼结论再从前提里找和结论相关的关键项。比如结论是 ¬P我就重点看前提里有哪些与 P 相关的蕴含式或析取式设法先凑出 P 或 ¬P 的判定条件。这种“由果溯因”的倒推法比盲目乱推高效得多。5. 主范式与真题实战分数到手的关键环节5.1 极小项与极大项别被名字吓到到了主范式这一节很多同学开始打退堂鼓其实它只是把一个公式标准化。先说极小项对于 n 个命题变元每个变元在项中出现一次且用合取 ∧ 连接每个变元要么本身出现要么以否定形式出现这样得到的合取式叫极小项。以两个变元 P、Q 为例极小项一共有四个¬P∧¬Q、¬P∧Q、P∧¬Q、P∧Q。每个极小项都只在一种赋值下为真这是它最重要的性质。把“变元为假”记为0“变元为真”记为1极小项可以编码为 m0、m1、m2、m3顺序按二进制排序。极大项与极小项对偶用析取 ∨ 连接每个变元出现一次记为 M0、M1、M2、M3。比如 P∨Q 编码是 M3因为 P1、Q1 时它才为假。主析取范式就是让公式为真的那些赋值所对应的极小项用 ∨ 连接起来。主合取范式就是让公式为假的那些赋值所对应的极大项用 ∧ 连接起来。你会发现只要画出真值表主析取范式和主合取范式几乎可以秒写出来真值为1的行对应极小项真值为0的行对应极大项。很多同学在这里绕了半天其实就是没把“真值表的行”和“项”对应起来。5.2 一个例子看懂主范式求法我拿公式 F P→Q 来示范先画真值表PQP→Q001011100111公式为真的行是第1、2、4行对应极小项¬P∧¬Qm0、¬P∧Qm1、P∧Qm3。所以主析取范式是 (¬P∧¬Q)∨(¬P∧Q)∨(P∧Q)简写为 m0∨m1∨m3或者用主范式求和号写成 Σ(0,1,3)。公式为假的行只有第3行对应极大项¬P∨QM2所以主合取范式是 ¬P∨Q。简写为 Π(2)。这里有个很容易搞混的点极大项 ¬P∨Q 对应的编码 M2 来自 P1、Q0刚好是真值为0的那一行。千万别把极小项编码看真值1和极大项编码看真值0混在一起用。我考试前专门给自己出过几道乱序练习题就是专门练这种编码对应关系。另一个细节同一个公式主析取范式和主合取范式之间存在互补关系。知道 Σ(1,2,3) 就能直接写出 Π(0)因为所有2^n个编码被两者平分。这个小规律在选择题里能帮你省出不少时间。5.3 考场上的实战建议自考题里主范式这节最常见的考法有三种第一种是给一个具体公式让你求主析取范式和主合取范式。推荐用真值表法因为不容易错只需要细心。算主析取时看所有真值为1的行算主合取时看所有真值为0的行。第二种是给了主析取范式的编码让你判断哪些赋值下公式为真。这时候要能快速把编码翻译回赋值。比如 Σ(0,2,5)要能说出赋值000、010、101时公式为真。对三变元来说二进制编码按P、Q、R顺序排列这个是基本功。第三种是判断两个公式是否等价。若两个公式的主析取范式相同则等价。这个方法比暴力画四五个真值表快也适合做证明题。我就见过一位考友在求主合取范式时直接用主析取范式的反码来写结果因为公式有3个变元应该用2³8个编码范围但他只列了4个算出来的结果自然不对。所以拿到题第一步先数变元个数再确定编码范围这个小检查能避免大部分低级错误。5.4 复习笔记怎么做才不白做最后分享一点复习方法。很多人的笔记是抄书抄完就丢完全没有复习价值。我后来改进了一种“三层笔记法”第一层上课或看书时记录核心定义、公式、定理这是骨架第二层针对每个知识点写一道典型例题把解题步骤完整写清楚这是血肉第三层在每章末尾总结错误点和易混淆点专门记录自己做错的题这是经验。我第一章的笔记上专门有两页是“坑点清单”比如蕴含方向写反、小项编码数错、德摩根律分配错误、推理题跳步丢分。考前我基本不翻课本只看这份笔记和公式速查卡效率高很多。《离散数学》第一章的题目不考智商考的是熟练度。我那会儿每天固定刷一组等值演算题和一组推理证明题坚持了三周从最初一道题磨二十分钟到最后5分钟内写完整手感完全不一样。只要你肯花时间练这一章的分数是非常好拿的。现在如果你刚开始学这一章看到满屏的符号先别焦虑按着“概念理解→公式熟练→刷题巩固”的顺序来很快就能找到节奏。