简介离散数学课后习题答案文档由刘玉珍编著教材配套整理面向高校计算机、软件工程等专业学习离散数学的学生帮助验证解题思路、巩固命题逻辑、范式推导等章节知识点。压缩包内共1个文件为doc格式整体大小约3.1MB便于离线查看和按章节检索。文档不仅给出题目直接对应的答案还包含真值表展开、公式等价变换、主析取范式求解等详细过程覆盖习题1.1至1.4等核心内容适合日常练习与考前对照参考。目前已有3230人学习使用是一份实用性较强的离散数学学习辅助材料。1. 离散数学答案是什么一份把“真假逻辑题”翻译成人话的解题地图我第一次翻开离散数学答案时差点以为自己拿错了书。满页都是 ┐、∧、∨、→ 和 0、1看起来像一份被加密过的说明书。后来才慢慢明白这套离散数学答案本质上是一份把抽象逻辑题翻译成人话的解题地图。它对应着很多高校都在用的那本离散数学教材把课后每一类题目的思考过程拆开先判断这句话是不是命题再算真值再证明等价式最后一步步推出结论。为什么要专门搞清楚它因为离散数学是计算机科学的“语法基础”你以后写程序、做数据库、设计算法骨子里都在用这里面的规则。而答案就像地基上的标尺让你知道自己有没有踩对方向。它不是让你背结论而是让你看清一条推理是怎么从“感觉玄学”变成“每一步都有依据”的。2. 命题逻辑为什么一句话能被算成 0 或 1离散数学的开篇几乎都是命题逻辑。第一个要建立的感觉是一句话不是只能分“对”和“错”它还可以被当成数值一样去计算。这套答案里的大量习题反复在训练这件事。2.1 命题是什么有明确真假的陈述句命题的定义很简单一个能判断真假的陈述句。比如“2 是质数”为真“2 是偶数”为真“明天是晴天”在给定条件下也能判断真假。这些都是命题。反过来“你去教室了吗”是疑问句“快去图书馆”是祈使句它们没有真假可言就不是命题。在习题 1.1 里第一道题全是这类判断某个句子到底是命题吗若是命题真值是多少。比如有一小题说“是真值为 0”意思就是这句话算命题但它的内容是假的。另一小题“是真值为 1”则是内容为真的命题。这里最容易犯的错是把“这句话我喜不喜欢”和“这句话客观上是真还是假”混在一起。命题的真假不取决于你信不信只取决于事实。理解了命题下一步就是复合命题。把简单命题用逻辑联结词拼起来就得到“如果明天下雨那么我不去教室”这样的复合句。习题里大量出现“P天下雨Q我去教室┐P → Q”之类的写法就是在做这一层翻译。2.2 五个联结词否定、合取、析取、蕴含、等价的“逻辑开关”命题逻辑里最常用的联结词有五个它们像电路里的开关规则固定谁来了都一样联结词符号读法真值为真的条件否定┐P非 PP 为假时合取P∧QP 且 QP 和 Q 都为真析取P∨QP 或 QP 和 Q 至少一个为真蕴含P→Q如果 P 则 Q只有 P 真且 Q 假时整个式子才为假等价P↔QP 当且仅当 QP 和 Q 同真同假这里面最反直觉的是蕴含。生活里说“如果你去教室我就去图书馆”我们会觉得这是一句因果关系但在逻辑里它只承诺一件事不会出现“你去了教室而我却去了别处”这种情况。换句话说只有当前件真、后件假时P→Q 才是假其他三种情况都是真。哪怕你根本没去教室这句话也算“没说错”。打个比方妈妈说“如果这次考试及格就给你买自行车”。结果你没及格自行车自然没买妈妈这句话算不算说谎按逻辑蕴含的规则不算因为条件没成立。离散数学里很多初学者在这里翻车一看到 P→Q 就脑补因果关系后面主析取范式、推理证明全跟着错。2.3 为什么要做命题符号化把自然语言翻译成公式答案里几乎每道题的第一步都是“设 P 表示……Q 表示……”。这个过程叫命题符号化。为什么要做这一步因为自然语言有歧义你今天说“如果明天是晴天那么我去教室或图书馆”别人可能理解成“晴天发生我就去教室或者去图书馆”也可能理解成“晴天和去教室之间有关系去图书馆是另一件事”。一旦写成公式歧义就消失了。比如习题里的“P你去教室Q我去图书馆P → Q”翻译过来就是如果你去教室那么我去图书馆。它不再关心你们俩明天到底去哪只关心这条逻辑承诺。答案之所以把符号化放在最前面是因为后面所有真值计算、等价化简、推理证明都只认公式不认自然语言。这一步选错后面全错。比如 P 设成“天下雨”Q 设成“我打伞”你想表达“只有下雨我才打伞”符号应该是 Q → P 而不是 P → Q。很多人以为“只有……才……”和“如果……就……”差不多其实两者的方向正好相反。这个细节在习题里反复出现答案的价值就在这里用标准符号告诉你每种句型对应的逻辑结构。2.4 真值计算I(P∨(Q∧R)) 到底怎么算出 1题目里经常出现“I(……)”这种写法它表示“在这个赋值下整个公式的真值”。赋值就是给每个命题变元一个确定的真假P 是 1Q 是 1R 是 0这是输入I(P∨(Q∧R)) 是输出。计算顺序和算术一样先括号再算合取再算析取。看这个例子I(P∨(Q∧R)) I(P) ∨ (I(Q) ∧ I(R)) 1 ∨ (1 ∧ 0) 1。第一步先把公式拆成子公式第二步代入具体真值第三步先算括号里的 1∧0 得 0最后算 1∨0 得 1。整个过程就像代入一元二次方程求值只不过算的是真假。提示不同教材对联结词的优先级略有差异。通常先算否定再算合取再算析取最后算蕴含和等价。遇到不确定时按答案里的小括号顺序走就行。这套答案里的第 1 章习题专门让你练这种计算。它的好处是步骤完整别人只写一个“1”它会写清楚这个 1 是从哪一层括号里算出来的。看懂这一步后续的永真式判断和等值演算就有了基础。3. 永真式与等值演算为什么有的式子“怎么赋值都成立”学会了单个公式求值下一个问题是有些公式不管 P、Q、R 取什么值结果永远是真。这种公式叫永真式。答案里大量出现“原式 T”的写法T 代表 True意思就是这个式子化简到最后是永真式。这一章要解决的问题就是怎么证明一个公式“怎么赋值都成立”。3.1 真值表把所有情况摆成一排的“收银小票”最朴素的办法是列真值表。命题变元只有 0 和 1 两种取值所以两个变元有 4 种组合三个变元有 8 种组合。真值表就是把所有组合一行行列出来再把每一列的真值算出来最后看目标列是不是全为 1。习题 1.2 里的表格就是干这个的。比如 Q∧(P→Q)→P 这个式子要判断它是不是永真式就分别枚举 P0、Q0 到 P1、Q1 的四种情况先算 P→Q再算 Q∧(P→Q)最后看推出 P 的结果。如果最后一列每一行都是 1说明这个式子怎么赋值都真。这就像一个收银员把小票上每一笔钱都列出来最后一对总数发现一分不差。真值表的优点是无脑可靠缺点是变元一多就爆炸3 个变元 8 行4 个变元 16 行10 个变元就是 1024 行手算非常痛苦。所以后面才有了等值演算法。3.2 永真式、矛盾式和可满足式逻辑上的“铁律”与“偶尔成立”按照真值结果公式可以分成三类永真式所有赋值为真。比如 P∨┐P排中律不管 P 是真是假整个式子一定真。矛盾式所有赋值为假。比如 P∧┐P任何情况下都假。可满足式至少存在一组赋值为真但不是所有赋值都为真。比如 P∧Q只有当 P、Q 都为真时才真。答案里经常出现的“原式为可满足式”指的就是第三种。它的意思是这个式子不是永远正确只是有些情况下成立。很多人把“可满足”理解成“挺常见”其实它的定义很严格只要存在一组赋值让它为真就算可满足。哪怕另外七组赋值都是假它依然叫可满足式。用一个比喻永真式是“每天早上都吃早饭”矛盾式是“每天早上都不吃早饭”可满足式是“至少有一天吃了早饭”。前者要求全部满足后者只要有一个例子就行。做题时最怕把可满足式当成永真式因为结论强度完全不同。证明题里你要推出一个结论需要的是永真式的支持而不是“偶尔成立”的巧合。3.3 等值演算德摩根定律、分配律与化简逻辑式列真值表虽然可靠但遇到复杂公式时效率太低。于是答案里大量使用等值演算也就是像做代数题一样把逻辑式一步步化简。常用的“公式”有双重否定┐┐P P德摩根定律┐(P∧Q) ┐P∨┐Q┐(P∨Q) ┐P∧┐Q分配律P∧(Q∨R) (P∧Q)∨(P∧R)P∨(Q∧R) (P∨Q)∧(P∨R)蕴含改写P→Q ┐P∨Q看一个答案里的化简过程原式 ┐(P∨┐Q)∨Q (┐P∧Q)∨Q Q第一步先把 ┐(P∨┐Q) 用德摩根定律展开变成 ┐P∧Q第二步再用吸收律把 ┐P∧Q 和 Q 合并成 Q。这个结果说明原公式是否为真完全取决于 Q 的取值P 根本没起作用。所以它是一个可满足式不是永真式。等值演算最大的价值是让你看到“为什么两个长得完全不一样的式子其实是同一个意思”。答案里那些一步步的箭头就是这种思考过程的实录。很多学生觉得这些步骤像魔术其实每一行都只改了一小块要么是括号挪位要么是用定律替换。看得多了就会发现它本质上就是“逻辑算术”。4. 范式与推理规则把逻辑推导变成机械步骤命题逻辑做到后面不再是“这个式子真还是假”而是“能不能把乱七八糟的式子整理成统一格式”以及“能不能从前提推出结论”。这一章答案里的两个主角是范式和推理规则。4.1 主析取范式与主合取范式每个公式的“真值指纹”主析取范式和主合取范式是两种标准化的写法。为什么要标准化因为两个公式看起来完全不同但它们可能是等价的。与其一个个列真值表去比不如把公式都整理成统一形态一对比就知道是不是一回事。主析取范式的做法是找出所有让公式为真的赋值组合把每一组赋值写成一个“极小项”再把这些极小项用析取∨连起来。比如某个公式为真的解释是 101、100、111、011、001那它的主析取范式就是这五个极小项的析取。这就像一个人的指纹同一枚指纹只能对应一种展开方式两个公式如果展开后完全一样它们就必然等价。主合取范式正好反过来找出所有让公式为假的赋值组合写成一串合取项。一个公式的真和假是互补的所以知道了主析取范式就等于知道了主合取范式。答案里经常先写“为真的解释是……”再直接给出主析取范式或者反过来先写“为假的解释是……”再给主合取范式。关键是要记住主析取范式看真值表里 1 的行主合取范式看 0 的行。这里有个细节容易看晕主析取范式里的每个极小项必须包含公式里的每一个变元而且每个变元恰好出现一次。比如 P、Q、R 三个变元极小项 P∧Q 是不合格的因为缺了 R。所以答案里常常出现 P∧Q∧R、P∧Q∧┐R 这样的长串。这也是“主”字的含义每个变元都要到场一个都不能少。4.2 推理规则从已知到结论的“因为所以清单”范式是静态的推理规则是动态的。一个证明题长这样已知 P∧Q已知 P→(Q→R)让你证明 R。答案会用编号列表给出P∧Q 前提P 由 1 化简P→(Q→R) 前提Q→R 由 2、3 假言推理Q 由 1 化简R 由 4、5 假言推理这套格式就像法官写判决书每一步都必须写明依据。常用的规则不多简化从 P∧Q 推出 P、合取引入从 P 和 Q 推出 P∧Q、假言推理从 P→Q 和 P 推出 Q、拒取式从 P→Q 和 ┐Q 推出 ┐P、析取三段论从 P∨Q 和 ┐P 推出 Q。为什么要把证明写成这么死板因为逻辑推理的目的就是保证“前提为真时结论必然为真”。每一步都套固定规则结论就不会跑偏。答案里那些看似啰嗦的编号行其实是给你的一张踩坑清单很多人证明题丢分不是不会想而是跳步直接写“显然 R 成立”。答案会告诉你R 不是显然的它来自第 4 步和第 5 步的组合。刚开始看这种格式会觉得机械但考试时恰恰需要这种机械。你把每一步按规则填好哪怕是没见过的题也能靠规则一步步推到结论。这就像做饭时照着菜谱称克数虽然少了一点大厨的飘逸但起码不会翻车。4.3 谓词逻辑当“所有人都……”和“存在一个……”出现时命题逻辑处理“P 是晴天”这样的单个命题但很多数学命题长这样“所有人都会死”“存在一个数比 2 大”。这类句子无法用 P、Q 简单表示因为要描述“所有”和“存在”。于是命题逻辑升级成谓词逻辑。谓词逻辑引入两个量词全称量词 ∀x 表示“对所有 x”存在量词 ∃x 表示“存在一个 x”。比如“人都会死”可以写成 ∀x(M(x)→D(x))其中 M(x) 表示 x 是人D(x) 表示 x 会死。再加上“苏格拉底是人”这个前提 M(a)就能推出 D(a)苏格拉底会死。答案里这类题目会专门标注量词的辖域也就是量词后面管到哪一部分。还要区分约束变元和自由变元被量词管住的变元是约束的没被管住的则是自由的。比如 ∀x(P(x)∨Q(x)) 里的 x 是约束的后面 R(x) 里的 x 是自由的。这个区分在下一章还会细说因为它是初学者最容易搞混的地方。5. 易混概念命题逻辑和谓词逻辑里最容易搞错的五组词做了这么多题我发现离散逻辑里最坑人的不是计算而是概念长得太像。这一章专门挑出五组容易混的每组都按“哪里像、为什么混、怎么分”来讲。5.1 蕴含“→”和等价“↔”支配关系和相等关系易混点日常语言里“如果……就……”和“当且仅当”经常被当成一回事。为什么混生活里说“如果下雨就带伞”听起来好像不下雨就不带伞似乎也是双向的。但逻辑里蕴含是单向的只禁止“下雨却没带伞”这一种情况不下雨时带不带伞都不管。等价则要求两个方向都成立P↔Q 等于 (P→Q)∧(Q→P)。怎么区分看反方向是否成立。P→Q 的反方向 Q→P 跟它完全不同。比如“如果 P 是你去了教室Q 是我去图书馆”P→Q 说“你去教室我就去图书馆”Q→P 说“我去图书馆你才会去教室”两者根本不是一回事。只有同时成立才是等价。做题时看到“当且仅当”“充要条件”才是等价看到“如果……那么……”只是蕴含。5.2 “P→Q”和“┐P∨Q”为什么条件句能改写成析取式易混点一个是“如果”一个是“或者”感觉八竿子打不着。为什么混符号长相差很多单靠眼睛看不出来它们有关系。但在真值表里P→Q 为假的情况只有“P 真 Q 假”而 ┐P∨Q 为假的情况也只有“P 真 Q 假”。两列真值完全一样所以它们是等价的。怎么区分不用死记列一次真值表就通了。记住这条等价关系很有用因为很多等值演算题的第一步就是把蕴含改写掉然后整个式子变成全是 ┐、∧、∨ 的“纯代数形式”处理起来简单得多。看到 P→Q 时默念一遍“它可以换成 ┐P∨Q”很多化简题就豁然开朗。5.3 合取范式与析取范式一个是“与的或”一个是“或的与”易混点这两个名词长得像双胞胎做题时经常把外层运算符记反。为什么混它们都由合取和析取组成只是层次不同。合取范式是“若干个析取项再用合取连起来”形如 (A∨B)∧(C∨D)析取范式是“若干个合取项再用析取连起来”形如 (A∧B)∨(C∧D)。一个是外层为∧一个是外层为∨。怎么区分看公式最外层那个运算符。如果最外一层是∧整体是“(……)∧(……)”就是合取范式如果最外一层是∨整体是“(……)∨(……)”就是析取范式。还有一种特殊情况单个简单项 P∨Q∨R 可以同时算析取范式和合取范式因为它的每一项里没有嵌套两层结构都说得通。答案里会在这种地方专门标注“既是析取范式又是合取范式”就是提醒你别把简单项强行归类。5.4 约束变元和自由变元同一个 x身份完全不同易混点公式里到处都是 x搞不清哪个 x 是哪个 x。为什么混符号全都叫 x但有的 x 被量词管着有的 x 在外面自由游荡。比如 ∀x(P(x)∨Q(x)) ∧ R(x)前面括号里的 x 被 ∀ 绑定是约束出现最后一个 R(x) 里的 x 不在量词辖域内是自由出现。它们虽然同名但角色不同。怎么区分从头往后读看 x 出现在哪个量词的管辖范围内。量词后面紧跟着的那部分就是辖域辖域内的同名变元都是约束的走出辖域后的 x哪怕名字一样也是自由的。答案里在换名时最常考这个把约束变元 x 换成 y 不影响原式含义但自由变元不能随便换。比如 ∀xP(x) 和 ∀yP(y) 的意思完全一样可如果公式里还有自由的 R(x)你换成 R(y) 就等于偷偷改写了条件。5.5 永真式和可满足式一个要求全对一个只求存在易混点看到“可满足”三个字很容易理解成“差不多成立”。为什么混汉语里“满足”这个词太日常让人觉得“可满足”就是“大多数情况下成立”。但在逻辑里“可满足”的定义非常弱只要存在一组赋值让公式为真它就是可满足式。哪怕一百种情况里只有一种为真依然是可满足式。怎么区分永真式要求所有赋值都为真可满足式只要求至少一组为真。所以每个永真式一定是可满足式反过来不成立。用前面的比喻永真式是“每天吃饭”可满足式是“某天吃过饭”。答案里判断完一个式子后如果写“原式为可满足式”你要立刻意识到它可能只在两三组赋值下为真离“永远正确”还很远。考试里证明某个推理成立通常需要的是永真式级别的保证而不是可满足式的“偶尔撞对”。6. 什么时候用、什么时候别用一份答案的正确打开方式这份离散数学答案最适合用在三个场景第一你做完一整组题之后逐行对照答案的推理步骤看自己的跳步发生在哪里第二卡在某道题超过十五分钟实在没思路只看答案开头的“设 P 表示……Q 表示……”这一步然后合上答案自己继续推第三考前复习时把主析取范式、推理规则这些固定格式的题当模板看答案怎么组织步骤再自己默写一遍。反过来有三个时刻千万别依赖它。第一题目刚读完就翻答案那等于把解题过程外包给了别人下次题目换个字母你照样不会。第二把答案当成“抄作业素材”一字不改地抄进作业本作业交上去是完成了但考试时会一眼被看穿。第三背答案里的化简路径而不是理解定律。等值演算的路径不止一条这次这么走恰好顺下次换个式子路径就不同死背必翻车。判断一份答案该不该看有个很简单的标准拿到题时你能不能说出“这题考的是蕴含改写还是主析取范式”能说出来说明你已经建立基本概念可以看答案验证细节要是连这题属于命题逻辑还是谓词逻辑都分不清那看答案只会让你越看越晕应该先回教材读概念。某同学就吃过这个亏他做题时直接对着答案抄抄完觉得“我都会了”。结果考试遇到一道类似的证明题只是把 P、Q 换成了 A、B把条件顺序调了一下他就不知道怎么下手因为脑子里只有答案的“原版流程”没有“为什么要这么做”的思路。从那以后他每次对完答案都会在题目旁边写一句话这题考了我什么概念我哪一步跳了答案为什么没跳。坚持了几周之后再看新题时不再发怵因为框架已经长在自己脑子里了。这套离散数学答案说到底是一个陪你验证思路的教练。它最大的价值不是“正确答案”这四个字而是那些编号步骤、箭头化简、表格真值它们把抽象的数学推理变成了可以检查、可以模仿、可以复用的方法。搞清楚什么时候该看、什么时候不该看这份答案才能真正成为你的垫脚石。希望帮到你。本文还有配套的精品资源点击获取