离散数学命题逻辑全解：真值表、等值演算与推理证明实战

1. 写给自考人的话这门《离散数学》到底在考什么先纠正一个事儿。你看到的标题“命理逻辑篇”我猜十有八九是“命题逻辑篇”的谐音误写——不过这个误写挺有意思因为每年确实有大批自考生在命题逻辑这儿“算命式”做题凭感觉猜联结词靠直觉写推理过程最后成绩出来一脸茫然。所以这篇博文咱们就把“命理”俩字当成一个提醒命题逻辑不是玄学它是有一套严格规则的。我手上这本是辛运帏主编、机械工业出版社2014年版的02324离散数学教材。这是全国高等教育自学考试计算机及应用、计算机信息管理等专业的指定教材。整本书覆盖数理逻辑、集合论、关系、函数、图论、代数系统几大块而咱们这篇聚焦的是最前面的“数理逻辑”部分具体点说就是命题逻辑以及顺带会用到的一阶谓词逻辑基础。这篇文章适合谁看两类人。第一类是正在备考02324的自考生尤其是对逻辑符号发怵、一做证明题就脑子空白的同学。第二类是自学离散数学、想快速抓住“逻辑”这条主线的人。我会把命题逻辑的学习拆成“知识点真值表等值演算推理证明”四个台阶用真题风格例题带你过一遍再告诉你哪些地方最容易丢分、怎么避免。先说个结论命题逻辑是整本《离散数学》里性价比最高的章节。它概念不复杂题型相对固定只要把几个核心方法练熟选择题、填空题、证明题的分数都能稳稳拿到。但如果你没掌握方法它也是最容易“一听就懂、一做就错”的章节。下面我从教材的编排逻辑讲起。2. 教材结构与命题逻辑的学习主线2.1 辛运帏版教材的特点为什么它和别的《离散数学》不一样很多同学会去网上搜“左孝凌离散数学pdf”因为左孝凌版是老牌经典教材内容全、例题多。但我要提醒你自考是按指定教材出题的02324指定的是辛运帏这本2014年版复习必须以上课教材和考试大纲为准。左孝凌版可以作为参考但章节顺序、符号定义、习题风格和自考教材有差异拿来当主线容易乱。辛运帏版教材在逻辑部分的编排有几个明显特点。第一它把命题逻辑和谓词逻辑放在第一章也就是全书起点这说明编者的意图是先给你一套“形式化推理”的工具后面集合、关系、图论都要用到这套符号语言。第二它的符号体系比较规范统一教材里用的符号考试就按这个符号打分比如否定用“¬”、合取用“∧”、析取用“∨”、蕴含用“→”、等价用“↔”这些千万别自己发明创造。第三教材在每章后面配有相当数量的习题不少自考试题就是从课后题变形来的这个我后面细说。2.2 命题逻辑在02324考试中的真实分量按历年真题的分布看数理逻辑一章在考试中大约占20到25分。题型分配大致是题型涉及内容大致分值单项选择题命题判断、联结词真值、等值式判断68分填空题符号化、公式类型、主范式相关46分计算/化简题求主析取范式、主合取范式、真值表68分证明题用推理规则证明结论46分你可能觉得20多分不算多但要注意这是一门60分及格的考试而且后面集合论、图论的大题更依赖逻辑表达能力。很多同学在关系闭包、函数性质、图的可达性这些题目上丢分本质上是逻辑推理没学扎实。所以命题逻辑这章表面上是考逻辑实际上是给你整门课打地基。2.3 学习和复习的四个阶段我总结的复习路径是这样的也建议你按这个顺序来符号化阶段能判断一个句子是否是命题能把自然语言翻译成逻辑公式。真值表阶段会构造真值表能从真值表判断公式类型重言式、矛盾式、可满足式。等值演算阶段背熟基本等值公式能用等值演算化简公式、求主范式。推理证明阶段掌握推理规则和证明方法能写出规范的证明过程。这四个阶段是递进关系。符号化不过关真值表画出来也看不懂真值表不熟等值演算就容易出错等值演算不熟练求主范式就会很慢推理证明是所有方法的综合应用。下面每个阶段我都用教材里的核心内容展开讲。3. 核心知识点拆解从“人话”到“符号”3.1 命题与联结词先学会判断“是不是命题”命题的定义很简单能判断真假的陈述句。但考试里关于命题判断的丢分点不在定义本身而在一些边界情况。“x 5”是命题吗不是。因为x没赋值无法判断真假。这属于命题变元或叫命题变量不是命题。“这个函数在x0处连续吗”不是命题疑问句不判断真假。“请把门关上。”不是命题祈使句没有真假。“我正在说谎。”比较特殊它涉及自指悖论通常不当作命题讨论自考一般不会考这种极端例子。“如果明天是晴天我们就去爬山。”这是一个复合命题其中“明天是晴天”和“我们去爬山”是子命题用蕴含联结词连接。判断命题还有个小技巧一个句子只要能问“这句话是真的吗”并且能给出确定答案它就是命题。考试中如果给你一个含变量的句子一般会说“该命题的真值取决于变量的值”然后让你求“在什么条件下为真/假”这时候要按命题变元和赋值来理解。再说联结词。教材里一共给了五个否定“¬”、合取“∧”、析取“∨”、蕴含“→”、等价“↔”。大部分同学在“∧”和“∨”上不会混真正的重灾区是蕴含联结词“→”。蕴含“P→Q”读作“如果P那么Q”它的真值特点是只有当P为真且Q为假时整个公式为假其余情况都为真。这个定义和日常语言习惯有冲突。平常我们说“如果下雨就带伞”隐含的意思是“下雨且没带伞”不合理所以这句话为假但“没下雨”时不管带没带伞这句话大家通常认为是“没违背承诺”或者“无从判断”。逻辑学里采取了最宽松的处理前件为假时蕴含式为真这叫“空真”vacuous truth。举个例子命题“如果113那么月亮是奶酪做的”。前件“113”为假按照蕴含定义整个命题为真。虽然听着很离谱但逻辑学就是这么规定的。考试里经常拿这类“前件为假”的式子来考真值判断你只要记住定义就能得分。还有一个高频考点自然语言中“只要……就……”“只有……才……”的符号化。这是最让自考生头疼的地方。“只要P就Q”→ 符号化为 P→Q。关键词“只要”后面是前件。“只有P才Q”→ 符号化为 Q→P。关键词“只有”后面是后件的前件……不对这里容易乱。我教你一个稳妥的判断方法把句子改写成“P是Q的充分条件”还是“P是Q的必要条件”。如果原句说“只要P就Q”意思是“P发生足以推出Q”所以P是Q的充分条件逻辑式是 P→Q。如果原句说“只有P才Q”意思是“P是Q的必要条件”也就是说“没有P就没有Q”等价于“Q能推出P”所以逻辑式是 Q→P。我常跟学生讲“只有”强调的是门槛门槛在前面挡着Q要过门槛就得让P先成立所以是 Q→P。3.2 真值表一切公式判断的“万能工具”真值表是命题逻辑最基础的判定方法。两个原则要记住一个有n个命题变元的公式其真值表有2^n行。排列变元真值时一般按二进制顺序列比如两个变元按 00、01、10、11对应 FF、FT、TF、TT排列。当然有的教材按 00、10、01、11不影响结果但考试中建议用标准二进制递增序阅卷时更直观。为什么要掌握真值表因为它是“最后兜底”的工具。等值演算做不出来、主范式分不清、公式类型判断不了的时候画真值表一定能得到答案只是慢一些。考试时如果题目分值不高用真值表法反而更稳妥至少不容易因为演算符号错误丢分。如果是证明题或者化简题等值演算更快真值表就太啰嗦了。关于公式类型教材定义了三种重言式永真式真值表最后一列全为真。矛盾式永假式真值表最后一列全为假。可满足式真值表最后一列至少有一个真。补充一个考试常用的结论任何两个等值的公式它们的真值表最后一列完全相同。反过来说如果两个公式的真值表最后一列一样它们就是等值的。这就是用真值表验证等值式的原理后面做证明题时经常用。3.3 等值公式背公式不等于会用公式教材里给出了一组基本等值式我按使用频率给你排个优先级。最优先背诵的双重否定律¬¬A ⇔ A幂等律A∨A ⇔ AA∧A ⇔ A交换律A∨B ⇔ B∨AA∧B ⇔ B∧A结合律(A∨B)∨C ⇔ A∨(B∨C)(A∧B)∧C ⇔ A∧(B∧C)分配律A∨(B∧C) ⇔ (A∨B)∧(A∨C)A∧(B∨C) ⇔ (A∧B)∨(A∧C)德摩根律¬(A∨B) ⇔ ¬A∧¬B¬(A∧B) ⇔ ¬A∨¬B吸收律A∨(A∧B) ⇔ AA∧(A∨B) ⇔ A其次是与蕴含、等价相关的蕴含等值式A→B ⇔ ¬A∨B等价等值式A↔B ⇔ (A→B)∧(B→A)假言易位A→B ⇔ ¬B→¬A归谬论(A→B)∧(A→¬B) ⇔ ¬A最后是零律和同一律零律A∨1 ⇔ 1A∧0 ⇔ 0同一律A∨0 ⇔ AA∧1 ⇔ A排中律A∨¬A ⇔ 1矛盾律A∧¬A ⇔ 0这些公式看起来多其实核心就两套逻辑。第一套是“关于∨和∧的运算规律”和四则运算里的交换、结合、分配很像第二套是“否定如何穿透”也就是德摩根律它告诉你把括号拆开时联结词要变号。德摩根律是所有化简题里出错率最高的一个点因为学生拆括号时经常忘记变号¬(A∨B) 拆开应该是 ¬A∧¬B而不是 ¬A∨¬B。至于蕴含等值式 A→B ⇔ ¬A∨B是解题的第一把钥匙。凡是公式里出现“→”优先考虑把它换成“¬A∨B”出现“↔”优先换成 (A→B)∧(B→A)再进一步换掉“→”。这样处理之后很多等值演算题就化成了纯的∧、∨运算可以套各种律。3.4 主析取范式与主合取范式标准化才是王道简单合取式是若干个命题变元或其否定用“∧”连接比如 P∧¬Q。简单析取式是若干个命题变元或其否定用“∨”连接比如 P∨¬Q。由若干个简单合取式用“∨”连接起来的公式叫析取范式由若干个简单析取式用“∧”连接起来的公式叫合取范式。教材里对“主范式”的要求是每个简单合取式对主析取范式而言必须包含公式中所有命题变元且每个变元只出现一次。这个包含所有变元的简单合取式称为极小项对应地包含所有变元的简单析取式称为极大项。举个例子公式涉及P、Q两个变元极小项有¬P∧¬Q对应00编码m0¬P∧Q对应01编码m1P∧¬Q对应10编码m2P∧Q对应11编码m3主析取范式的本质是把公式“拆”成哪些行赋值组合上为真然后把对应极小项用“∨”并起来。所以求主析取范式有两个方法方法一真值表法。列出真值表找出公式为真的所有行把每行对应赋值写成极小项全部析取起来。方法二等值演算法。先把公式化为析取范式再对缺少变元的简单合取式进行“补项”如果一个简单合取式缺少变元P就把它变成 (原式∧P) ∨ (原式∧¬P)因为它与 P∨¬P 等值乘进去相当于“多此一举但合法”。然后消去重复的极小项。主合取范式是“反面”操作找出公式为假的行每行写成极大项用“∧”连接起来。这里有个考试技巧如果题目让你求主析取范式你可以先求主合取范式再用编码关系快速写出主析取范式。因为一个n变元公式总共有2^n个极小项和2^n个极大项。设主析取范式出现的极小项编号集合为A主合取范式出现的极大项编号集合为B则B正好是全体编号中A的补集。比如两个变元时主析取范式是 m0∨m2那主合取范式就是 M1∧M3。这个方法在检查答案时特别有用。4. 实操推演三道典型例题带你走完全流程4.1 例题一命题判断与符号化将下列语句符号化并说明各命题变元的含义 1只有你努力学习才能通过考试。 2除非天气好否则我不去爬山。第1句“只有……才……”结构。设P你努力学习Q你能通过考试。按前面讲的方法“只有P才Q”符号化为 Q→P。读一下验证如果你通过考试那么你一定努力学习了。逻辑上说得通。第2句“除非……否则……”是另一个高频结构。设P天气好Q我去爬山。“除非P否则Q”的标准翻译是 ¬P→Q意思是“如果P不成立那么Q成立”。这里要注意“否则”后面是结果前件是非P。所以这句符号化为 ¬P→¬Q等等原句是“除非天气好否则我不去爬山”也就是“如果天气不好那么我不去爬山”即 ¬P→¬Q。那“除非P否则¬Q”就是 ¬P→¬Q。很多同学会把“除非”理解成“只有”其实“除非A否则B”可以改写为“如果不A就B”即 ¬A→B。所以第2句符号化为 ¬P→¬Q。做这种题我的经验是先找句子主干再去抠逻辑关键词。先把“天气好”“我去爬山”这种原子命题用字母表示再根据关联词判断逻辑结构最后把整个句子拆成公式。4.2 例题二用真值表判断公式类型并求主范式判断公式 (P→Q) ∧ (P∧¬Q) 的类型并求它的主范式。这种题看起来复杂其实就是送分题。先用蕴含等值式换掉“→”(P→Q) ∧ (P∧¬Q) ⇔ (¬P∨Q) ∧ (P∧¬Q)再用分配律展开注意这里是合取对合取的展开要小心(¬P∨Q) ∧ (P∧¬Q) ⇔ (¬P∧P∧¬Q) ∨ (Q∧P∧¬Q)第一项 ¬P∧P∧¬Q 中出现 ¬P∧P这是矛盾式等于0第二项 Q∧P∧¬Q 中出现 Q∧¬Q也是0。所以整个公式 ⇔ 0∨0 ⇔ 0。按这个推导公式恒为假是矛盾式。主范式矛盾式的主析取范式为空没有极小项可以记作0主合取范式是全部极大项的合取对两个变元就是 M0∧M1∧M2∧M3。这类题在考试中出现频率不低它考察的是“化简路径”。我的建议是先尝试等值演算过程中如果发现推出了矛盾项基本就可以判断是矛盾式然后直接在答案里写“无极小项”或“0”不用再列真值表。4.3 例题三求真值表验证等值式用真值表证明P→(Q→R) ⇔ (P∧Q)→R。这是教材里非常重要的一组等值式叫输出等价式或归约规则在推理证明中特别常用。列真值表。三个变元共8行PQRQ→RP→(Q→R)P∧Q(P∧Q)→R00011010011101010010101111011001101101110111000101111111P→(Q→R) 这一列和 (P∧Q)→R 这一列完全相同因此两公式等值。这个等值式的意义在于条件证明CP规则的依据就是它。证明时如果想证明 P→(Q→R)可以暂时把P作为附加前提去证明 Q→R等证明出 Q→R 后再用 CP规则得出结论 P→(Q→R)。同理只要证明出 R就能用 (P∧Q)→R 推出原式。这是推理证明中最高频的操作之一务必熟练。4.4 例题四推理证明题的标准写法用推理规则证明前提 P→QQ→RP结论 R。这道题简单但是标准写法必须规范证明过程P 前提引入P→Q 前提引入Q 1,2 假言推理P, P→Q ⇒ QQ→R 前提引入R 3,4 假言推理结束。这就是最基础的三段论推理。考试评分时每一步什么理由、用了哪条规则必须写清楚只写一个“显然”或者“由前提可得”是不够的会被扣过程分。再给一道典型证明题用推理规则证明前提 ¬P∨Q¬Q∨RP结论 R。思路如果想用假言推理得先把 ¬P∨Q 变成 P→Q把 ¬Q∨R 变成 Q→R然后就和上面的题一样了。证明过程¬P∨Q 前提引入P→Q 1, 蕴含等值式的逆用¬Q∨R 前提引入Q→R 3, 蕴含等值式的逆用P 前提引入Q 2,5 假言推理R 4,6 假言推理这里用了蕴含等值式的“反向替换”即把 ¬A∨B 还原成 A→B。这个操作在推理题里非常常见因为很多题目给的前提是析取式而推理规则组合更偏向使用蕴含式。4.5 推理规则和证明方法汇总教材里常用的推理规则我整理成一张表你做题时对照着用就行规则名称逻辑形式含义假言推理分离规则A, A→B ⇒ B前提中若有一条蕴含式且有前件则可得后件拒取式A→B, ¬B ⇒ ¬A取蕴含式的逆否后件不成立则前件不成立假言三段论A→B, B→C ⇒ A→C蕴含式可以串联析取三段论A∨B, ¬A ⇒ B析取式中否定一个则另一个成立构造性二难A→B, C→D, A∨C ⇒ B∨D两条件析取则结论析取证明方法上有三种考试中常见的是前两种直接证明法从前提出发不断用推理规则得到结论。附加前提法CP规则结论是蕴含式 A→B 时把A作为附加前提如果推出B则原结论得证。归谬法反证法把结论的否定作为附加前提如果能推出矛盾说明原结论成立。CP规则在考试中出现频率很高。比如题目要证 “前提集合推出 P→Q”如果你从 P 入手用附加前提推导出 Q那整个证明就清晰很多。因为 P 暂时被当作已知条件你可以顺藤摸瓜。归谬法的核心思路假设结论不成立即加入 ¬结论 作为新前提推出一个形如 A∧¬A 的矛盾。矛盾一旦出现就说明假设错误所以原结论必须成立。这个方法在做难证明题时是“最后的兜底”因为结论加进来之后可用条件变多推理路径也变宽了。5. 常见问题与排查技巧考前最容易栽的坑5.1 坑一蕴含联结词的方向搞反这是命题逻辑第一丢分点。很多同学把“P→Q”理解为“P等于Q”其实 Q→P 和 P→Q 完全不同。P→Q 只有一种情况为假就是P真Q假。而 Q→P 是Q真P假时为假。怎么避免我的经验是拿到一个蕴含式先问“这个命题什么时候为假”。比如“如果P则Q”只有当P成立而Q不成立时这句话才是在撒谎。其他情况P不成立都不算撒谎。把这个“假的条件”刻在脑子里方向就不会乱了。5.2 坑二德摩根律拆括号不变号¬(A∨B) 拆成 ¬A∨¬B 还是 ¬A∧¬B正确答案是 ¬A∧¬B。口诀否定作用在合取/析取式上时联结词要“翻转”∨变∧∧变∨同时每个子命题都取否定。这类题型判断真值表时也容易出错因为如果拆错了后面整道化简题全错。建议做这类题后随手用真值表验证一行A真B真时¬(A∨B)为假而 ¬A∧¬B 为假¬A∨¬B 为假等等A真B真时 ¬A∨¬B 0∨0 0两种拆法在这行都是假。再看A真B假¬(A∨B)¬10¬A∧¬B 0∧1 0¬A∨¬B 0∨1 1。后面的拆法显然不对。可见一两个关键行就能验证出拆法是否正确。5.3 坑三求主范式时“补项”补错等值演算法求主析取范式时需要对缺变元的简单合取式补项。比如有一个简单合取式是 P∧Q但公式涉及P、Q、R三个变元那么 P∧Q 缺R。正确做法是P∧Q ⇔ (P∧Q∧R) ∨ (P∧Q∧¬R)因为 R∨¬R 恒为真所以 P∧Q ∧ (R∨¬R) (P∧Q∧R) ∨ (P∧Q∧¬R)。这里用了分配律。很多同学把“缺哪个变元就补哪个变元”理解成“加上这个变元就行”忘了还要同时补它的否定。少补一个项最后答案就少了极小项直接扣分。补完项之后还要检查是否有重复的极小项有则合并。因为如果两个极小项完全一样按幂等律 A∨A ⇔ A可以消去一个。5.4 坑四推理证明题不写依据有一部分同学在考场上证明了题目也写对了每一步但因为没写“假言推理”“拒取式”这类规则名称或者没标注用的哪两个前提被扣了过程分。这很可惜。自学考试阅卷是按步给分的。一道证明题4到6分结论1分中间每一步1分没写依据最多给一半。所以我的建议是从平时练习就养成好习惯每一行都写“第几行第几行什么规则”就像4.4节示范的那样。这不仅方便阅卷老师也方便你自己检查逻辑漏洞。5.5 坑五混淆“条件证明”和“反证法”CP规则附加前提法用在结论是蕴含式时把结论的前件作为附加前提归谬法反证法则是把结论的否定作为附加前提目的是推出矛盾。两者都“额外加前提”但目标不同一个是想推出后件一个是要推出矛盾。做题时如果结论不是蕴含式别硬用CP规则改用反证法更合适。如果结论是蕴含式优先考虑CP规则因为附加前提等于把目标变短了常常能让证明简化不少。5.6 备考节奏课后题怎么刷最有效辛运帏教材每章的课后题是宝矿。我的建议是第一遍只做标记不动笔。把每一道题里涉及的知识点标出来比如“判断命题”“求范式”“推理证明”然后分类统计。你会发现大部分题目集中在有限的几个题型上。第二遍再按题型刷每种题型挑5道做透而不是从头到尾做一遍。具体到逻辑这一章选择题和填空题的题感很重要因为考试时它们占的分值不小但时间很紧。你可以在考前两周把教材里的判断题、选择题全部过一遍重点是看符号化是否准确。计算题尤其是求主范式要计时练习每道题控制在5分钟以内。证明题每天固定练2道坚持一个礼拜基本就能把假言推理、拒取式、CP规则、反证法这几种套路吃熟。6. 考前一周的临阵磨枪策略如果离考试只剩一周来不及系统复习那就按优先级来。第一优先是符号化和蕴含等值式因为这是所有题的敲门砖。第二优先是求主范式因为这是最容易短期突破的计算题练熟了就能拿分。第三优先是假言推理和CP规则因为推理证明题必考一种而这两招能应付大部分题目。选择题和填空题里的公式类型判断用真值表法保底。虽然慢但准确率高。遇到“以下哪个公式是重言式”这类题宁可列出真值表也不要凭感觉猜。真值表虽然费时间但只要你列得对一定能选出正确答案不会出现“四个选项看起来都像对的”的情况。最后一天把所有公式手抄一遍重点是蕴含等值式、德摩根律、假言推理、拒取式、CP规则这五样。进考场前再看一遍比刷十道新题都管用。我这里特别提醒一点考试时如果发现某道题卡住了先跳过最后回来处理。逻辑题有个特点一旦陷入某个符号细节很容易在同一个地方消耗大量时间。而你只要把基本题做对20分的逻辑分基本可以拿到15分以上这一章就不算失守。7. 我的个人体会命题逻辑是整个离散数学的“语法课”我见过很多自考生学集合论、图论的时候还能靠背记撑一撑但一到关系闭包、传递闭包、图的连通性这些证明题就开始“因为所以显然可得”。本质原因就是命题逻辑那套推理规则没内化导致后面所有“形式化推导”都变成了凭感觉。所以我真心建议别把命题逻辑只当成第一章来应付。你花费在推理规则和等值演算上的时间在后面学习“关系”“函数”“图论”时会加倍还给你。你练熟了“A→B, ¬B ⇒ ¬A”这类规则再看“关系的对称性”“图的最短路径”这些内容思路会清晰得多。最后分享一个小技巧做题时尤其是做推理证明题把每一步的“理由”先写在草稿纸上最后形成正文时再精简。这样做的好处是即使结论没证完中间步骤也能挣到不少过程分。自考阅卷是按步给分的你的草稿纸越像一份规范证明最终得分就越接近满分。命题逻辑就是这么一门课。它不是靠天赋也不靠猜它是一套可以练习、可以复盘的规则游戏。你只要把规则背熟、把典型题练够考试时它就是白送的20分。祝复习顺利考场上别做“命理派”做“推理派”。