简介面向学习《离散数学及其应用原书第8版》的学生、考研复习者与自学者这份奇数题目答案PDF可用于课后练习核对、章节复习和知识点查漏补缺。内容围绕命题逻辑等核心内容展开既梳理命题、逻辑运算符∧∨¬→↔以及同一律、排中律、幂等律、吸收律、分配律等基本规则也给出奇数编号习题的逐题答案解析涉及命题真值判断、自然语言翻译、蕴含与等价关系等常见题型便于对照Kenneth H.Rosen原书定位问题并理解解题思路。压缩包共1个PDF文件大小约6.34MB轻量易取适合在电脑或平板上直接查阅。已有7607人学习下载读者可借助答案核对检验掌握程度再结合章节总结回看概念提升刷题与复习效率。1. 一份答案册到底在答什么从「这道题为什么是 T」说起学离散数学的人大多有过这种体验书翻开命题、真值表、量词一股脑砸下来例题看着都懂合上书自己做第一道就卡住。卡住的原因往往不是不会算而是不确定自己想的方向对不对——这时候「离散数学及其应用原书第8版奇数题目答案」这类资料的价值就显出来了。它不是让你抄而是给你一个对照系你的符号化写法、你排的真值表、你判断的重言式究竟和标准解法差在哪一步。命题逻辑这门课的特点是答案往往只有一个字母 T 或 F但通往这个字母的路可以有很多条走错一条你也能蒙对结果下次换个题照样翻车。所以真正要搞懂的不是那个字母而是「为什么是这一步」。后面几章把命题、连接词、真值表、逆否命题、范式这些词一个个拆开让你翻答案时能看懂推导而不是只对最后那个符号。2. 命题逻辑到底是什么把一句人话压成符号的理由2.1 先分清什么才算命题命题的定义很短能判断真假的陈述句。判断标准只有一条——这句话本身有没有确定的真假值而不是「你现在知不知道」。比如「2024 年的某一天某地下了雨」即使没人记录它在当时要么下了要么没下所以它是命题而「请把窗户关上」没有真假可言它是祈使句不是命题。最容易踩坑的是含变量的句子。「x 加 1 大于 2」这句话x 没确定之前你没法说它真还是假所以它单独看不是命题只有把 x 代入具体数字之后才变成命题。这就是为什么教材里要引入量词——「对所有 x」「存在 x」量词的作用就是把一个开着口子的句子封上让它重新获得真假。答案册里那些看着像在「翻译」的题目本质上做的就是这件事把一句中文里的变量、范围、条件全部显式写出来。还有一类特殊句子要留意就是自指句比如「这句话是假的」。假设它为真那它说的内容成立它就应该是假假设它为假那它说的内容不成立它就应该是真。两边都推不通这种句子被排除在命题之外。它在后面讲逻辑谜题时会以另一种形式回来先记住这个坑。2.2 五个连接词各有各的分工单个命题叫原子命题用 p、q、r 这样的字母表示。把它们拼起来要靠连接词常用的就五个把这五个的规则吃透第一章的题目基本就通了。符号读法什么时候为真一句话记忆¬p非 pp 为假时为真反过来p ∧ qp 且 q两个都真才真一票否决p ∨ qp 或 q至少一个真就真三缺一也算p → q如果 p 那么 q只有 p 真 q 假时为假只禁止一种情况p ↔ qp 当且仅当 q两者真假相同同生共死其中 ¬、∧、∨ 三个规则直白几乎不会错。真正让人翻车的是 p → q也叫蕴含。它的真值表里只有一行是假前件 p 为真、后件 q 为假。其余三种情况——p 真 q 真、p 假 q 真、p 假 q 假——整个蕴含都算真。为什么前件为假时要说它真打个比方你答应朋友「如果明天下雨我就带伞」。第二天没下雨你带不带伞带也行不带也行朋友都不能说你食言。唯一能说你说话不算数的情况是下了雨而你空着手来。这就是逻辑学里说的「善意推定」一个条件句只有在它的承诺被违反时才算假其余一律按真处理。这个约定在生活里显得别扭在数学和程序里却极其重要因为大量定理都是「如果满足前提则结论成立」而前提不成立时定理不该被判为假。2.3 这套符号在代码里长什么样写程序的人其实天天在用命题逻辑只是没这么叫。一个登录判断age 20 has_ticket True # 对应逻辑里的 age ≥ 18 ∧ has_ticket两个条件都成立才放行 if age 18 and has_ticket: print(允许入场) # 对应 age 18 ∨ has_ticket满足任意一个就放行 if age 18 or has_ticket: print(允许入场)这段代码里and就是 ∧or就是 ∨not就是 ¬。代码中的关键点是and和or两个关键字把两个条件连接起来整个表达式的真假完全由左右两边的真假决定和真假值表里那几行是一一对应的。参数上看age 18是一个能判真假的子表达式has_ticket是一个布尔变量两者都是原子命题的实例。有一处差别要提醒多数编程语言里的and、or是短路求值左边一旦能定结果右边就不算了而逻辑里的 ∧、∨ 没有顺序两边同时成立才算数。写业务代码时短路能省掉空指针报错做数学题时却不能因为「左边已经假了」就跳过右边不判断这是两套语境的细微不同初学时容易混在一起。3. 真值表为什么是黑匣子把「所有可能」一次列干净3.1 行数为什么是 2 的 n 次方真值表是命题逻辑里最笨也最可靠的工具。它的思路很朴素一个公式里出现几个原子命题就把它们所有可能的真假组合枚举一遍每种组合算出一个结果。每个原子命题有两种取值n 个原子命题就是 2 的 n 次方种组合所以只有 p、q 两个变量时是 4 行加上 r 就是 8 行再加一个就是 16 行。排列顺序有约定通常第一个变量变化最慢先全真再全假最后一个变量变化最快真假真假交替。这个顺序本身不影响结论但跟着教材的统一排法走对答案的时候能一行一行对上省掉「明明算对了却找不到对应行」的麻烦。列的顺序也有讲究。不要一上来就写最终结果而是按公式的嵌套层次从左往右加列先列原子命题再列括号里最内层的子公式逐层往外最后一列才是整个公式的值。这样每一步都只依赖前一列中间哪一步算错了一眼就能看出来。答案册里那些表之所以排得密密麻麻就是因为它把每个中间子公式都单独列了一列。3.2 重言式、矛盾式、可满足式看最后一列就够了真值表列完之后判断全靠最后一列。如果最后一列全是 T这个公式叫重言式也叫永真式不管变量取什么值它都成立。如果最后一列全是 F叫矛盾式。如果至少有一行是 T叫可满足式。三者不是并列关系重言式一定是可满足式可满足式不一定是重言式。两个公式如果真值表的最后一列完全一致就称它们逻辑等价记作 p ≡ q。这是答案册里出现频率最高的判断。比如德摩根律说的是 ¬(p ∧ q) ≡ ¬p ∨ ¬q验证方式就是把两个公式各列一列看两列是不是每行都一样。这里用「等价」而不是「相等」是因为两个公式长得完全不同只是在真假行为上无法区分。理解这一点很关键逻辑等价不是文字游戏而是「在任何情况下都不可分辨」。就像两台外观完全不同的机器按下同样的按钮永远给出同样的输出那从使用者的角度看它们就是同一台机器。3.3 位运算和真值表是同一件事计算机里的按位与、按位或、按位异或其实就是把真值表并排跑了很多遍。每一位都是一个命题T 记作 1F 记作 0。a 0b1101 # 二进制 1101 b 0b1011 # 二进制 1011 print(bin(a | b)) # 0b1111 按位或任意一位是 1结果位就是 1 print(bin(a b)) # 0b1001 按位与两位都是 1结果位才是 1 print(bin(a ^ b)) # 0b0110 按位异或两位不同结果位才是 1 print(bin(~a 0b1111)) # 0b0010 按位取反后再截断到 4 位这段代码里a和b是两个 4 位二进制数每一位都对应一个原子命题。|对应 ∨逐位比对只要有一边是 1 就写 1对应 ∧两边都是 1 才写 1^对应异或两位不一样才写 1。最后一行的~a是取反但 Python 的整数是变长的取反会带出无限多个前导 1所以要用 0b1111截断到 4 位这一步不做的话打印出来会是一串负数。参数上唯一需要留意的是位数两个操作数位数不同时短的那边会在高位补 0 再对齐运算这等价于给缺省的命题补上 F。答案册里那些位运算题本质上就是让你手算这几列只是因为位数多用表格竖着写太占地方才改用横排的写法。4. 命题逻辑里最容易混淆的几组概念逆否、析取、蕴含、等价4.1 易混点一逆命题、否命题、逆否命题给定一个蕴含 p → q可以构造出三个「变体」逆命题q → p否命题¬p → ¬q逆否命题¬q → ¬p为什么混中文里说「如果下雨我就不去」紧接着说「如果不下雨我就去」听起来像是同一句话的两种说法日常对话里也确实经常这么用。语言习惯让人本能地以为「否定前件」等于「否定后件」。怎么区分只有逆否命题和原命题逻辑等价逆命题和否命题各自成立、互不牵连。拿一个显然为真的蕴含去检验最省事「如果一个图形是正方形那么它是矩形」这是真话。它的逆命题是「如果是矩形则是正方形」明显为假长方形就是反例。它的否命题是「如果不是正方形则不是矩形」同样为假。它的逆否命题是「如果不是矩形则不是正方形」这句话是真的。四个变体里只有两个真界限一下就清楚了。答案册里这类题经常要求把四个变体全部写出来写的时候不妨在草稿纸边上标一句「只有逆否等价」能省掉后面反复回看的功夫。4.2 易混点二相容或与排斥或p ∨ q 在逻辑里默认是相容或至少一个成立两个都成立也算真。排斥或异或要求恰好一个成立两个都成立反而是假。为什么混中文的「或」两种意思都在用。「有相关经验或有相关学历者优先」显然是相容的两样都有更好而菜单上写「任选一份饮品」你拿两杯就不行这是排斥的。怎么区分问自己一句「两个同时成立时这句话还成立吗」。成立的用 ∨不成立的用异或。答案册里判断「应该用哪种或」的题目标准解法就是从这句话的意图出发看两种解释下语义是否都说得通再选更自然的那个。有时两种解释都说得通题目要的就是让你把两种情况都写出来这时别急着只写一个。4.3 易混点三蕴含的真假与因果无关p → q 只关心真假组合不关心 p 和 q 之间有没有因果关系、有没有时间先后。「如果 1 加 1 等于 3那么雪是黑的」在逻辑上为真因为前件为假。为什么混日常语言里的「如果……就……」几乎总是带着因果或者时序。「如果我按这个按钮灯就会亮」暗含按钮导致灯亮。一旦把这种直觉带进真值表前件为假时就会犹豫该填什么。怎么区分把蕴含当成一张「禁止牌」它只禁止一种情况——前件真而后件假。其余全部放行。做题时不要问「这句话有没有道理」只问「有没有出现前真后假的那一行」。这个思维转换需要练几次练熟之后凡是看到前件明显为假的蕴含直接判真不用再纠结。4.4 易混点四逻辑等价与逻辑蕴含p ≡ q 说的是两个公式在每一行取值都相同是双向的。p ⇒ q逻辑蕴含说的是不存在 p 真而 q 假的行是单向的。前者要求两列一模一样后者只要求没有「前真后假」。为什么混两个概念都在描述真假关系而且经常同时出现——比如「p ∧ q 蕴含 p」成立但「p ∧ q 等价于 p」不成立。学生看到前半句成立就容易顺手把后半句也认了。怎么区分等价要两列完全对上蕴含只要不出现特定的坏行。一个快速判据是看方向等价可以反过来说「q 等价于 p」蕴含反过来不一定成立。上面那个例子里p 为真、q 为假时p ∧ q 是假而 p 是真所以反方向不成立。4.5 易混点五重言式与可满足式重言式在所有行都为真可满足式只要有一行为真。¬(p → q) 是可满足式p 真 q 假时它为真但它远远不是重言式。为什么混两个词都带「成立」的意味中文翻译又都比较正面读起来像是同档次的评价。实际上它们的强度差得很远。怎么区分重言式是「无条件正确」可满足式是「有机会正确」。做题时先看最后一列有没有 F有 F 就一定不是重言式再去数 T 的个数判断是否可满足。反过来如果题目问「这个公式是否可满足」只要找到一行 T 就可以停手不必把整张表列完。5. 范式与函数完备集为什么「与或非」能拼出一切5.1 析取范式照着真值表把公式抄出来真值表是从公式推结果析取范式是反过来从结果推公式。做法很机械找出真值表里所有结果为真的行每一行造一个「小项」最后用 ∨ 把它们全连起来。造小项的规则是这一行里取值为 T 的变量保留原形取值为 F 的变量取否定全部用 ∧ 连起来。举个具体例子公式 p → q 只有一行是假p 真 q 假另外三行为真于是第一行 p 真 q 真小项是 p ∧ q第三行 p 假 q 真小项是 ¬p ∧ q第四行 p 假 q 假小项是 ¬p ∧ ¬q拼起来就是 (p ∧ q) ∨ (¬p ∧ q) ∨ (¬p ∧ ¬q)。这个式子看着比 p → q 长得多但它和 p → q 逻辑等价而且还能继续化简——前两个小项合并出 q后两个小项合并出 ¬p最终化简成 ¬p ∨ q。这正是 p → q 的另一种写法也是教材里反复演示的一个等价式。这套方法的价值在于它是通用的不管公式多复杂只要能列真值表就能机械地写出一个只含 ¬、∧、∨ 的等价公式。答案册里那些让你「用析取范式表示」的题考的就是这个机械转换的熟练度不需要灵感。5.2 函数完备集一种门电路就能搭出整个逻辑既然任何公式都能化成只含 ¬、∧、∨ 的形式那这三个运算符就够用了术语叫「函数完备集」。进一步还可以更省用德摩根律能把 ∧ 消掉¬(¬p ∨ ¬q) 就是 p ∧ q所以 {¬, ∨} 也是完备的。同理 {¬, ∧} 也完备。最极端的情况是只用一个运算符。与非NAND记作 ↑定义为 ¬(p ∧ q)它单独就是完备的# 与非门先与再取反只用这一个运算就能拼出其他所有运算 def nand(a, b): return not (a and b) def NOT(p): # p ↑ p 等价于 ¬(p ∧ p)也就是 ¬p return nand(p, p) def AND(p, q): # ¬(p ↑ q) 等价于 ¬¬(p ∧ q)也就是 p ∧ q return NOT(nand(p, q)) def OR(p, q): # 先把两边各自取反再与非(¬p) ↑ (¬q) 等价于 p ∨ q return nand(NOT(p), NOT(q)) # 逐个验证输出应当全是 True print(AND(True, False) False) print(OR(True, False) True) print(NOT(True) False)这段代码的关键在于三个封装函数它们全都建立在nand这一个原语上。NOT靠把同一个值喂给两个输入实现AND靠把与非的结果再取反OR则先分别取反再与非。参数上没有什么可调的输入就是布尔值输出也是布尔值整个链条不依赖任何其他逻辑运算符。这件事的现实意义不小芯片制造里工艺上把一种门做稳定比做多种门容易得多所以实际电路经常大量使用与非门和或非门用它们组合出所有需要的逻辑。教材把函数完备集放在命题逻辑这一章就是让你看到「符号系统的最小零件」和「物理器件的最小单元」在这里对上了。5.3 骑士与无赖把自然语言压成可满足性问题命题逻辑里有一类题特别有意思就是骑士与无赖谜题岛上的人分两种骑士永远说真话无赖永远说假话你听他们说了几句话要判断谁是谁。这类题看着像脑筋急转弯其实就是一个方程组。解法分三步。第一步给每个角色设一个布尔变量真表示骑士假表示无赖。第二步把每个人说的话翻译成一个含这些变量的公式并且注意「某人说 X」这件事本身等价于「这个人是骑士 ↔ X 为真」。第三步把所有公式用 ∧ 连起来枚举所有赋值找出让整体为真的那一组。from itertools import product # 假设岛上只有 A、B 两人 # A 说B 是无赖 # B 说A 和我是同一种人 solutions [] for a, b in product([True, False], repeat2): a_says (not b) # A 的话的内容 b_says (a b) # B 的话的内容 # 骑士说真话、无赖说假话统一写成「这个人是骑士 ↔ 他说的内容为真」 if (a a_says) and (b b_says): solutions.append((a, b)) print(solutions) # 输出 [(True, False)]即 A 是骑士、B 是无赖代码里product([True, False], repeat2)负责枚举四种赋值组合a a_says这一行是整个解法的核心它把「某人是骑士」和「他说的内容为真」绑定成一个双条件。参数repeat2对应两个角色人数增加时改成对应的数字即可代价是枚举量按 2 的幂增长。这套「翻译成公式再找满足赋值」的流程在计算机科学里有专门的名字叫可满足性问题是理论计算机科学里最著名的问题之一。答案册里那些谜题之所以值得认真做就是因为它把「自然语言 → 符号 → 求解」这条链路完整走了一遍练的是建模能力不是猜谜能力。6. 什么时候该翻这份答案什么时候翻了反而害自己答案册是个放大器它能放大你的理解也能放大你的错觉。同样一本东西用法不同结果完全相反。6.1 三种值得翻的场景第一种推理链已经走完只差核对。你独立把真值表列完、把逆否命题写出来、把范式化到最简这时候翻开答案对一遍是最高效的反馈。哪里对不上说明那一步的理解有裂缝立刻能定位。第二种卡在符号化那一步。命题逻辑的题目难往往不难在计算而是难在把中文翻成公式。你已经知道该用哪种连接词但不确定某个「或者」是相容还是排斥或者不确定「除非」该怎么翻译。这种时候看答案的符号化结果比看最后那个 T/F 有用得多因为前者是可迁移的模板后者只是一次性的结果。第三种复习阶段抽查。隔一两周回头随机抽几道做过的题重做一遍再对答案。如果还能独立推出来说明真的记住了如果只记得「上次答案是 T」那就得回去重看对应的等价式。场景建议原因独立做完核对结果立刻翻反馈越及时记忆越牢卡在符号化只看翻译部分学的是转化方法不是答案复习抽查先重做再对检验的是记忆不是眼熟第一遍就卡住先回看例题缺的是概念不是答案作业赶时间做完再统一对边做边看会跳过思考6.2 三种翻了会后悔的用法第一题目还没读透就翻。看到「用真值表判断」几个字脑子还没开始转手已经翻到答案页。这样做的代价不是这次做错而是你失去了一次「自己发现错误」的机会而那种发现带来的记忆强度是看答案永远给不了的。第二只看最后那个 T 或 F。命题逻辑的答案最迷惑人的地方就在这——结果只有两种可能你瞎猜也有一半概率对。所以只对结果等于没对。真正该对的是中间那些列子公式化简到哪一步、用了哪条等价律、逆否写对了没有。第三把答案里的自然语言句子直接抄进作业。答案册里的句子是为了说明逻辑结构不是标准答案的措辞抄进去既学不到东西也容易在句式上和题目要求对不上。from itertools import product def equivalent(f1, f2, n2): 枚举 n 个变量的所有取值逐个比较两个公式的结果 for values in product([True, False], repeatn): if f1(*values) ! f2(*values): # 找到反例就立刻返回不需要跑完全部组合 return False, values return True, None # 核对德摩根律¬(p ∧ q) 与 ¬p ∨ ¬q 是否逻辑等价 ok, counter equivalent( lambda p, q: not (p and q), lambda p, q: (not p) or (not q), n2 ) print(ok, counter) # 输出 True None说明两列完全一致这个自查脚本的用处在于当你怀疑某个等价式记错了可以直接把两边写成 lambda 跑一遍比手列真值表快。参数n是变量个数两个变量的公式传 2三个变量传 3枚举量按 2 的 n 次方增长超过四五个变量就没必要用脚本了。返回值里ok表示是否等价counter给出第一个反例的取值组合——有反例时这个组合就是最该盯着看的那一行。我自己踩过的坑是有一阵子对答案对得特别勤错的题当场就「看懂了」合上书却复述不出推导。后来改成先合上答案把关键步骤写在纸上再翻页比对错的题会明显变少。从那以后我每次对答案前都强制自己先把真值表和化简过程写完整哪怕写得慢也不再允许自己「扫一眼就懂」。希望帮到你。本文还有配套的精品资源点击获取