简介这份 PDF 答案册对应《离散数学及其应用原书第8版》面向正在学习离散数学的高校学生、考研复习者以及需要核对课后习题的读者重点解决奇数编号习题缺少参考答案、命题逻辑等章节练习难以自检的问题。压缩包内共 1 个文件为 6.34MB 的 PDF文件按原书章节与题号组织便于快速定位内容围绕命题逻辑基本符号、逻辑运算符、真值判断、条件语句、自然语言命题转写等练习展开。该 PDF 以奇数题答案为主线并配合知识点归纳读者可对照答案梳理符号化与等价表述思路用于课后复习、作业核对和考前查漏补缺。目前已有 7607 人学习下载适合计算机、数学及相关专业学习者作为原书配套的核对型资料使用。1. 从一份奇数题答案看离散数学的地图「离散数学及其应用 习题答案」这份材料最容易被误当成对答案的工具真翻进去才发现它是一张反向铺开的知识地图奇数题答案按章节顺序排下来哪一节考什么、考到多深看答案的密度就能读出来。原书第 8 版第一章在答案册里占掉开头整整几页命题逻辑、逻辑等价、布尔检索、位运算挤在一起越往后每节的答案越短分值分布并不均匀这个信号比任何复习提纲都直接。系统学这门课的人拿到它等于拿到一份带评分标准的路线图知道哪类题会反复出现、答案写到什么颗粒度算合格正在备考的人拿到它等于提前看到了扣分点。梳理下来会发现奇数题答案的价值不在“核对数字”而在它把每一节的解题动作固定成了模板翻译题怎么拆句子、等价题怎么推链条、谜题怎么列约束、位运算怎么对齐。下按「地图 → 模块要点 → 易错点 → 自测清单」的顺序走重点压在答案最厚的命题逻辑部分其余章节给判断标准。2. 命题逻辑三件套联结词、真值表与翻译2.1 五个联结词的真值定义与优先级命题逻辑这一节答案册给出的信息量最大因为它把每道翻译题和真值表题的结果都摊开了。要读懂这些结果第一步是把五个联结词的真值定义背到条件反射¬p 翻转真值p ∧ q 只有两边都真才真p ∨ q 只有两边都假才假p → q 只在前件真、后件假时为假p ↔ q 只在两边同真同假时为真。容易漏掉的是异或 p ⊕ q它在答案里出现频率不低规则是“两边不同才为真”和 ∨ 只差一行真值。优先级是另一个必须固化的东西¬ 最高其次 ∧再是 ∨然后 →最后 ↔。答案里大量式子靠这个优先级省掉括号比如 (p ∨ q) ∧ (p → ¬q) 这种复合式如果优先级记错读出来就是另一个命题。同一优先级从左到右结合但 → 是右结合的p → q → r 默认读成 p → (q → r)这一点在答案里出现得不多考试里却常被拿来挖坑。提示真值表行数永远是 2 的 n 次方。两变量 4 行、三变量 8 行、四变量 16 行答案册里三变量的表格都恰好 8 行行数对不上基本可以判定自己漏了组合。from itertools import product # 六个联结词的 lambda 定义直接对应答案册里真值表的列顺序 ops { NOT: lambda p, q: not p, AND: lambda p, q: p and q, OR: lambda p, q: p or q, XOR: lambda p, q: p ! q, # 异或两边不同才为真 IMP: lambda p, q: (not p) or q, # p - q 等价于 ¬p ∨ q IFF: lambda p, q: p q, # 双条件同真同假 } # 按 TT、TF、FT、FF 的顺序枚举和手写真值表的习惯一致 print(f{p:3}{q:3} .join(f{k:6} for k in ops)) for p, q in product([True, False], repeat2): row .join(f{str(f(p, q)):6} for f in ops.values()) print(f{str(p):3}{str(q):3}{row})这段代码的作用是把“背定义”变成“看得见”跑一遍就能确认自己对 → 的理解有没有偏。product([True, False], repeat2)生成 4 种赋值顺序是先真后假f(p, q)里not p or q这一句是蕴涵的标准展开后面所有等价推演都靠它起步。想加联结词往ops字典里塞一条即可列宽会自动对齐。注意Python 的布尔运算返回布尔值而and/or在整数上会短路返回操作数。做位运算时不要混用这一套否则拿到的不是 0/1 而是某个整数。2.2 从自然语言到符号翻译题的三种套路答案册里翻译题占比最大形式无非两向给自然语言写符号式或者给符号式写回自然语言。做完一整轮能总结出三个固定动作。第一步圈原子命题把每句里独立成立的最小断言拎出来命名一句话里出现两个断言就说明要用二元联结词。第二步认骨架先找“并且”“或者”“不”“如果……那么”“当且仅当”这些连接词再看有没有“除非”“仅当”“既不……也不”这类变形。第三步处理嵌套括号跟着语义走不要跟着语序走。最容易出错的是几个变形词。“A 仅当 B”写出来是 A → B不是 B → A因为“仅当”标出的是必要条件在后件位置。“A 当 B”反过来写 B → A。“除非 B否则 A”等价于 ¬B → A也等价于 B ∨ A两种写法答案都接受。“既不 A 也不 B”是 ¬A ∧ ¬B不是 ¬(A ∧ B)后者只在两边同时为真时才假前者要求两边都假。“不是两者都”才是 ¬(A ∧ B)等价于 ¬A ∨ ¬B。这两个一字之差是批改里最常见的丢分点。自然语言符号化备注A 且 Bp ∧ q两边都要成立A 或 Bp ∨ q默认相容或要么 A 要么 Bp ⊕ q明确排斥时才用异或既不 A 也不 B¬p ∧ ¬q不是 ¬(p ∧ q)不是两者都¬(p ∧ q)等价于 ¬p ∨ ¬q如果 A 那么 Bp → q充分条件在前件A 仅当 Bp → q后件是必要条件A 当 Bq → p与上一行方向相反除非 B否则 A¬q → p也写作 q ∨ p答案里还有一类题要求把同一个复合式读成自然语言比如给出 (p ∨ q) ∧ (p → ¬q)要求用一句通顺的中文说出来。这类题的评分点不在措辞而在有没有把括号结构讲清楚外层是“并且”左边是“p 或 q”右边是“如果 p 那么非 q”。写成“p 或 q并且 p 蕴含非 q”即可硬凑成一句漂亮中文反而容易丢结构。2.3 条件语句的四个变体逆、逆否、反、原条件语句有四个位置答案册专门用一整道题把四者列全原命题 p → q、逆命题 q → p、逆否命题 ¬q → ¬p、否命题 ¬p → ¬q。关键结论只有两条原命题与逆否命题逻辑等价逆命题与否命题逻辑等价但原命题与逆命题之间没有等价关系。这条结论是后面所有证明题的地基背不下来就推到真值表上现算。常见的误解是把“逆否”和“否”搞混。否命题只把前后件各自取反方向不动逆否命题既取反又换位。判断等价时看的是真值表是否逐行相同而不是句子读起来像不像。from itertools import product # 四个变体用 ¬A ∨ B 展开避免手写真值表时抄错 orig lambda p, q: (not p) or q # p - q converse lambda p, q: (not q) or p # q - p contrapos lambda p, q: q or (not p) # ¬q - ¬p inverse lambda p, q: p or (not q) # ¬p - ¬q for p, q in product([True, False], repeat2): print(p, q, orig(p, q), converse(p, q), contrapos(p, q), inverse(p, q))跑完会发现第 1 列和第 4 列完全一致第 2 列和第 3 列完全一致这就是两组等价的机器证明。做题时如果时间紧与其背结论不如把这两列对一遍比回忆口诀稳。参数上四个 lambda 的自变量顺序统一为 (p, q)调换顺序会得到完全不同的表写的时候留意不要串位。3. 逻辑等价与范式恒等式、对偶与功能完备集3.1 恒等式清单与德摩根律的展开逻辑等价这一节的题量不如翻译题但难度明显上台阶因为它要求在不查真值表的前提下做符号变形。答案册给出的推演链条全都建立在十来个基本恒等式上把这些记熟后面的化简、对偶、完备集才有落脚点。名称形式一形式二同一律p ∨ F ≡ pp ∧ T ≡ p支配律p ∨ T ≡ Tp ∧ F ≡ F幂等律p ∨ p ≡ pp ∧ p ≡ p双重否定¬(¬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 ∨ ¬p ≡ Tp ∧ ¬p ≡ F蕴涵消去p → q ≡ ¬p ∨ q—逆否等值p → q ≡ ¬q → ¬p—双条件展开p ↔ q ≡ (p → q) ∧ (q → p)p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)这张表的使用顺序有讲究先消 → 和 ↔把式子降到只剩 ¬、∧、∨再用德摩根把否定号往里推推到原子命题上最后用分配律、吸收律、幂等律收尾。答案册里的推演几乎全是这个节奏中间步骤看起来啰嗦但每一步都能在表里找到出处考试时写出处比写“显然”安全得多。德摩根律是最容易用反的一条。¬(p ∧ q) 展开成 ¬p ∨ ¬q连接词要跟着翻¬(p ∨ q) 展开成 ¬p ∧ ¬q同样要翻。很多人只翻否定号不动连接词写出来的式子和原式真值完全不同自己却看不出来因为两边的“否定”字样都在。3.2 真值表证明与代数推演两条路怎么选证明两个命题等价有两条路。真值表是暴力枚举把两边的所有赋值列出来逐行比对列相同即等价代数推演是从一边出发用恒等式一步步变到另一边。答案册两种都给说明考试两种都认。选哪条路看两个因素。变量不超过三个、式子里 ↔ 或 ⊕ 多走真值表更快因为这类联结词展开成 ∧∨¬ 会写得很长枚举反而干净。变量多、结构重复、能看出吸收律或分配律的形状走推演更快因为枚举行数会炸。经验值是三个变量以内真值表四个变量以上先试着推。代数推演有一个隐形的规范每一步只改一处改完在旁边标出用的律名。答案册的推演之所以能当模板抄就是因为它严格一步一行。自己写的时候图省事一步跨三步错在中途根本定位不到。from itertools import product # 用穷举代替手写真值表返回第一个反例比返回 True/False 更有用 def equiv(f, g, n2): for vals in product([True, False], repeatn): if f(*vals) ! g(*vals): return False, vals # 找到反例立即返回便于定位 return True, None # 验证分配律p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) print(equiv(lambda p, q, r: p and (q or r), lambda p, q, r: (p and q) or (p and r), n3)) # 验证吸收律p ∨ (p ∧ q) ≡ p print(equiv(lambda p, q: p or (p and q), lambda p, q: p))equiv的第三个参数n是变量个数决定了枚举 2^n 种赋值两个函数对象的参数顺序必须一致否则比对的是错位的两列。返回反例而不是布尔值是这套脚本最实用的地方——等价不成立时直接告诉你是哪一行崩的比对的成本从“重算一遍”降到“看一眼”。提示把答案册里自己写错的那几条等价式抄进这个脚本跑一遍拿到反例行再把反例行代回原式手算一次比反复看正确答案记得牢。3.3 对偶原理与功能完备集对偶的规则很干脆把式子里的 ∧ 全换成 ∨、∨ 全换成 ∧、T 全换成 F、F 全换成 T原子命题和否定号都不动得到的式子叫原式的对偶。对偶原理说如果两个式子等价它们的对偶也等价这条在答案册里被用来批量生成新结论。最容易漏的是 T 和 F 的互换——很多人只换连接词常量忘了换对偶式看着像但其实不成立。双重对偶要单独记一句把对偶再求一次会回到原式因为 ∨ 换回 ∧、∧ 换回 ∨、T 换回 F、F 换回 T来回一轮正好复原。这条结论在证明题里通常只占一行但能省掉一堆展开。功能完备集是这一节最抽象的部分落到题目上其实只有三个结论。第一{¬, ∧, ∨} 是完备的理由是任何复合命题都能写成析取范式——把真值表里所有为真的行各写一个合取项再全部用 ∨ 连起来。第二{¬, ∧} 和 {¬, ∨} 各自完备因为分配律能把多出来的那个连接词消掉。第三NAND 和 NOR 各自单独完备这是最反直觉的一条也是考得最多的一条。NAND 的记号是 p ↑ q定义为 ¬(p ∧ q)NOR 的记号是 p ↓ q定义为 ¬(p ∨ q)。单独完备意味着只用一种门就能造出所有逻辑。标准构造是先做否定再做合取¬p ≡ p ↑ pp ∧ q ≡ (p ↑ q) ↑ (p ↑ q)。NOR 同理¬p ≡ p ↓ pp ∨ q ≡ (p ↓ q) ↓ (p ↓ q)。写这类题时括号必须一层不落少一层括号意思就整个变了这是批改里扣分最集中的位置。4. 命题逻辑的应用层谜题、检索式与位运算4.1 骑士与无赖把每句话写成约束逻辑谜题是命题逻辑最像“应用题”的部分。设定通常是岛上居民分两类一类永远说真话一类永远说假话偶尔再加第三类说话真假随意。题目给几句互相指认的话要求判断每个角色的身份。建模动作固定成三步。第一步定取值两类情形用真假两值出现第三类时改成三值并且要额外加一条“三类各一人”的约束。第二步逐句翻译每个角色说的那句话本身是一个命题它的真值必须等于该角色的类型——说真话的人命题为真说假话的人命题为假。第三步枚举全部赋值筛掉不满足约束的组合剩下的就是解。答案册里这类题的结论往往是唯一的一组说明约束足够紧。做不出唯一解的时候八成是漏掉了“恰好一人是骑士”这类数量约束没有它会有多组解同时成立。另一个常见疏漏是把“某人是无赖”这句话本身当成了真假未知实际上在建模时它是可以被判定真假的普通命题不需要额外处理。from itertools import product # 三值谜题0骑士(永真) 1无赖(永假) 2间谍(真假随意) # 三句话分别是A 说「B 是间谍」B 说「C 是无赖」C 说「A 是骑士」 def satisfy(a, b, c): claims [ (a, b 2), # A 的断言内容 (b, c 1), # B 的断言内容 (c, a 0), # C 的断言内容 ] for who, content in claims: if who 0 and not content: # 骑士说假话排除 return False if who 1 and content: # 无赖说真话排除 return False return True # 三类各一人的约束用 len(set) 3 表达 for a, b, c in product(range(3), repeat3): if len({a, b, c}) 3 and satisfy(a, b, c): print(a, b, c)claims列表是整段代码的核心每条是「谁说的」加「说了什么」换一道题只改这个列表求解框架不用动。len({a, b, c}) 3这一行负责“三类各一人”去掉它会出现多个解这也解释了为什么有些题不加这句就无解可判。product(range(3), repeat3)枚举 27 种分配规模小到可以暴力角色变多时再考虑剪枝。4.2 布尔检索式AND、OR、NOT 的括号游戏布尔检索是命题逻辑在信息检索里的直接投影答案册用一组查询改写题来练这件事。三条基本规则AND 收窄结果集两个条件都要满足OR 扩宽结果集满足其一即可NOT 排除但只作用于紧跟其后的那个词或括号组。括号的位置决定语义这是检索题唯一的难点。想表达“含 A且 B 和 C 至少有一个”写成 A AND B OR C 会先算 B OR C 再和 A 取交看起来对但换个顺序写 A OR B AND C 就完全变了因为 AND 的优先级高于 OR实际含义是“含 A或者同时含 B 和 C”。避免踩坑的办法是只要出现两种以上连接词就无条件加括号宁可多写一层。检索需求检索式说明同时含 A 和 BA AND B结果最窄含 A 或含 BA OR B结果最宽含 A 但不含 BA AND NOT BNOT 只否定紧跟项含 A且 B、C 至少一个A AND (B OR C)括号不能省既不含 A 也不含 BNOT (A OR B)等价于 NOT A AND NOT B含 A但不同时含 B 和 CA AND NOT (B AND C)括号位置是关键最后一行的写法值得单独记NOT (B AND C) 表示“不能两者都有”允许只有 B 或只有 C而 NOT B AND NOT C 表示“两个都没有”。两句中文只差一个字检索式差一整层括号。答案册里这类改写题就是在练这个语感。4.3 位运算OR、AND、XOR 的三种用途按位运算是命题联结词在二进制上的逐位应用规则完全一致按位 OR 有 1 则 1按位 AND 全 1 才 1按位 XOR 不同为 1。答案册给出的题目都是给两个二进制串求三种运算的结果看着机械实际考的是位对齐——位数不同的两个数要先补前导零再运算。三种运算各有固定用途记住用途比记住规则更有用。OR 用来置位把某些位强制打开AND 用来做掩码只保留关心的那几位XOR 用来翻转和 1 异或取反、和 0 异或不变。这三条在底层数据处理里天天出现也是这门课少数能直接用的部分。a 0b1010_1100 b 0b0110_1010 print(bin(a | b)) # 0b1110_1110 按位或任一为 1 则 1 print(bin(a b)) # 0b0010_1000 按位与全 1 才 1 print(bin(a ^ b)) # 0b1100_0110 按位异或不同为 1 print(bin(~a 0xFF)) # 0b0101_0011 取反后截断到一个字节前三行的结果直接对应答案册里那几小问。第四行是最容易翻车的地方Python 的整数是变长补码~a得到的是负数必须用 0xFF截断到 8 位才能看到期望的字节结果。手写答案时位宽是题目给定的不会遇到这个问题写代码验证时忘了截断会得到一串负号开头的二进制看着像自己算错了其实是位宽没限定。5. 易错点清单五处最容易翻车的地方5.1 语义坑「或」到底是哪一种易漏点把自然语言里的“或者”一律翻成 ∨遇到明确排斥的语境也不改。为什么漏中文的“或”本身两义相容和排斥全靠语境判断而教材里 ∨ 和 ⊕ 的真值表只差一行视觉上几乎分不出来。答案册有些题会同时给出两种解释并说明哪种更合理这种题最容易被当成“答案不唯一”跳过。怎么补看到“或”先问一句“能不能同时成立”。能用 ∨不能用 ⊕。句子里出现“两者只能选一个”“要么……要么……”这类限定基本锁定 ⊕出现“至少一个”“其中之一或全部”锁定 ∨。做完翻译再回头读一遍原句看自己的符号式在语义上是否说得通。5.2 方向坑条件的箭头指向易漏点「仅当」「当」「除非」三个词的方向记混箭头写反。为什么漏这三个词的中文语序和逻辑位置正好错位“仅当”后面跟的是必要条件却要放在箭头右边“当”后面跟的也是必要条件却要放在左边。只记关键词不记位置考场上手一抖就反。怎么补不要在符号层面记改成句子层面改写。把原句强制念成“如果……那么……”的形式念通了再写符号。“A 仅当 B”念成“如果 A 成立那么 B 必然成立”箭头自然从左到右“A 当 B”念成“如果 B 成立那么 A 成立”方向自动反过来。这个方法慢一点但基本不会错。5.3 符号坑否定号的作用范围易漏点¬p ∧ q 和 ¬(p ∧ q) 当成一回事¬(p → q) 展开成 ¬p → ¬q。为什么漏否定号的管辖范围靠括号表达而手写时括号经常省略或写得太小。条件语句的否定尤其反直觉很多人凭语感把它当成“前件后件都取反再保持箭头”。怎么补两条硬规则。第一否定号只管紧邻的那个原子命题要否定整个式子必须加括号。第二遇到 ¬(p → q) 先把箭头消掉再否定p → q ≡ ¬p ∨ q所以 ¬(p → q) ≡ ¬(¬p ∨ q) ≡ p ∧ ¬q结果是“前件成立且后件不成立”和 ¬p → ¬q 毫无关系。养成“先消箭头再动否定”的顺序这类错能砍掉大半。5.4 对偶坑T 和 F 也要换易漏点求对偶时只把 ∧ 和 ∨ 互换忘了常量 T、F 也要互换。为什么漏对偶式在结构上和原式长得几乎一样眼睛扫过去觉得对只有把常量代进去才会暴露。教材里对偶的定义通常写成一行∧↔∨ 很显眼T↔F 藏在后面容易被略读掉。怎么补把对偶规则写全成四组对应——∧ 对 ∨、∨ 对 ∧、T 对 F、F 对 T做题时逐条过一遍再下笔。检查办法是代一组具体赋值进原式和对偶式如果两个结果一个恒真一个恒假说明常量换对了如果两个结果一样多半是常量没动。5.5 完备性坑NAND 展开漏括号易漏点用 NAND 表示合取时写成 p ↑ q ↑ p ↑ q或者少一层括号。为什么漏NAND 是二元运算且不满足结合律(p ↑ q) ↑ r 和 p ↑ (q ↑ r) 结果不同省略括号等于换了一个式子。而它的标准构造 (p ↑ q) ↑ (p ↑ q) 里同一个子式出现两次抄的时候很容易合并成一次。怎么补分两步写不要一步到位。第一步写否定¬p ≡ p ↑ p这一步单独成行。第二步写合取p ∧ q ≡ ¬(p ↑ q) ≡ (p ↑ q) ↑ (p ↑ q)把第一步的结论代进去。两步之间不要合并宁可多写一行。NOR 的构造同理¬p ≡ p ↓ pp ∨ q ≡ (p ↓ q) ↓ (p ↓ q)一样分两步。6. 复习路线把奇数题答案用成自测清单奇数题答案最有效的用法不是对答案是当自测卷。做法是先把该节的概念过一遍然后遮住答案做奇数题做完只检查对错、不立刻看解析把错的题号记下来隔一天再回头重做。隔夜重做这一步很关键当天看解析会觉得“懂了”隔一天还能独立做出来才算真会。错题不要只记题号要归因。下面这张表按错误类型分列填一次就能看出自己的薄弱环节集中在哪里。错误类型典型表现回补动作语义误判“或”翻错、“仅当”方向反重读那六个变形词的对照表符号疏漏括号丢失、否定范围错手写十遍德摩根律的两种形式推演跳步一步跨三行、中间步骤对不上照答案册的链式推演抄两遍枚举不全真值表少行、谜题漏约束先数行数再填表约束逐条列位宽问题取反结果带负号、位数不对齐补前导零代码里显式截断归因填完第二轮只刷同一列里出现两次以上的题型不要整节重刷。这样一轮下来通常能压到两三个薄弱点比平均用力省一半时间。from itertools import product # 把易错的等价式批量验证一次列出所有反例 def check(name, f, g, n2): bad [] for vals in product([True, False], repeatn): if f(*vals) ! g(*vals): bad.append(vals) print(f{name}: {全部通过 if not bad else bad}) # 三条最常写错的式子逐条对着自己的笔记核 check(德摩根, lambda p, q: not (p and q), lambda p, q: (not p) or (not q)) check(蕴涵消去, lambda p, q: (not p) or q, lambda p, q: (not p) or q) check(分配律, lambda p, q, r: p and (q or r), lambda p, q, r: (p and q) or (p and r), n3)这个脚本的用法是把自己笔记里写下的每一条等价式都抄成一对函数丢进去跑完看哪一条报反例。n的取值跟着变量个数走两变量填 2三变量填 3填错会漏枚举。bad收集全部反例而不是遇到第一个就返回是因为多个反例往往指向同一个概念漏洞看全了才好定位。提示答案册是奇数题答案意味着偶数题是空的。空着的那一半正好可以当第二轮的自测题——同一知识点换一道没见过的题能独立做出来才算过关。从那以后我每做完一节都会强制走一遍“做题—归因填表—隔夜重做”这三步宁可进度慢一天也不让同一类错误出现第三次。离散数学这门课的知识点本身不难难的是每个符号背后那点细微的语义差别而奇数题答案恰好把这些差别一道道摊开给你看。希望帮到你。本文还有配套的精品资源点击获取