第 11~20 题：离散数学
📚 本文是 信息基础大赛（10.29 备赛）的第 2 篇，题目以截图为主、文字为点拨。
战术定位：这一块一时半会补不清楚，靠记答案，能碰到几题是几题。不过命题树（树）这块写得出些，目标拿到 7 分左右——树的度数计算、平面图欧拉公式是稳定送分点，见下文【图论】。
命题逻辑
什么算命题
下列语句是命题的有（ ） 明年中秋节的晚上是晴天 ／ x+y>0 ／ x*y>0 当且仅当 x 和 y 都大于 0 ／ 我正在说谎
判断标准三条：
- 真值客观唯一（哪怕现在不知道）→ 是命题。"明年中秋晚上是晴天"真值确定，是命题
- 含自由变量、真值随取值变 → 不是。x+y>0 就不是
- 悖论（自我指涉） → 不是。"我正在说谎"无法赋真值
下列不是命题的是（ ） 7 能被 3 整除 ／ 当且仅当太阳从西边升起，5 是素数 ／ x+7 小于 0 ／ 南昌大学科技学院位于南昌市北京东路
答案：x+7 小于 0（真值不确定）。其余虽然真假各异，但真值都客观唯一。"7 能被 3 整除"是假命题——假命题也是命题。
复合命题真值（ iff 真值表）
下列各命题中真值为真的有（ ） ① 2+2=4 当且仅当 3 是奇数 ② 2+2=4 当且仅当 3 不是奇数 ③ 2+2≠4 当且仅当 3 是奇数 ④ 2+2=4 当且仅当 3 不是奇数
⚠️ 原文 ②④ 文字重复，疑转录缺字。按 P⟷Q 同真同假才为真 验算：3 是奇数 = 真，2+2=4 = 真 → ① 真 ⟷ 真 = 真；② 真 ⟷ 假 = 假；③ 假 ⟷ 真 = 假。真值为真的是 ①（若 ④ 实为"≠…不是奇数"，则假⟷假也真，注意区分）。
下面哪一个命题是假命题（ ） ① 如果 2 是偶数，那么一个公式的析取范式唯一 ② 如果 2 是偶数，那么一个公式的析取范式不唯一 ③ 如果 2 是奇数，那么一个公式的析取范式唯一 ④ 如果 2 是奇数，那么一个公式的析取范式不唯一
答案：①。2 是偶数 = 真，但析取范式不唯一（这是事实）→ 前件真后件假 → 条件式为假。③ 前件假 → 条件式恒真。
符号化
设 p：王平努力学习，q：王平取得好成绩。命题"除非王平努力学习，否则他不能取得好成绩"的符号化形式为（ ） p→q ／ ¬p→q ／ ¬q→p ／ q→p
答案：q→p。"除非 p，否则 r" ⇔ ¬p→r。这里 r = "不能取得好成绩" = ¬q，故 ¬p→¬q，逆否即 q→p。
设 S(x)：x 是三好学生，a：张三，b：李四。命题"张三是三好学生而李四不是"符号化为（ ）
点拨："……而……不是"就是合取：S(a) ∧ ¬S(b)，选含这一形式的选项。
CP 规则与推理定律
命题逻辑演绎的 CP 规则为（ ） ① 在推演过程中可随便使用前提 ② 在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 ③ 如果要演绎出的公式为 B→C 形式，那么将 B 作为附加前提，演绎出 C ④ 设 B 是含公式 A 的公式，则可用 B 替换其中的 A
答案：③。CP 规则（条件证明规则）：欲证 B→C，把 B 作为附加前提引入，若能推出 C，则 B→C 成立。② 说的是推理的一般规则，④ 是置换规则。
下面 4 个推理定律中，不正确的为（ ）
答案：第 4 条（拒取式）——图中写的是 (A→B)∧¬B ⇒ A，结论少了否定号。正确的拒取式是 (A→B)∧¬B ⇒ ¬A：已知"B 不成立"，只能否定前件推出 ¬A，推不出 A。
其余三条都对：附加律 A ⇒ A∨B；析取三段论 (A∨B)∧¬A ⇒ B；假言推理 (A→B)∧A ⇒ B。
集合与关系
A 是素数集合，B 是奇数集合，则 A−B =（ ） 素数集合 ／ 奇数集合 ／ 空集 ／ {2}
答案：{2}。A−B = 素数中不是奇数的——唯一的偶素数 2。
集合 A={1,2,…,10} 上的关系 R={<x,y> | x+y=10, x,y∈A}，则 R 的性质为（ ） 反对称的 ／ 对称的 ／ 传递的、对称的 ／ 传递的
答案：对称的。x+y=10 则 y+x=10 → 对称 ✓；(1,9) 与 (9,1) 同时在 R 中 → 非反对称；1+9=10、9+1=10 但 1+1≠10 → 非传递；2+2≠10 → 非自反。
在自然数集 N 上，下列哪种运算是可结合的？（ ） a*b=a−b ／ a*b=max(a,b) ／ a*b=a+2b ／ a*b=|a−b|
答案：max(a,b)。逐个代入 (a*b)*c 与 a*(b*c) 验算：减法不结合（(5−3)−1≠5−(3−1)）；a+2b 不结合；|a−b| 不结合；max 满足 max(max(a,b),c)=max(a,b,c) ✓。
Q 为有理数集，Q 上定义运算 * 为 a*b=a+b−ab，则 <Q，*> 的幺元为（ ） a ／ b ／ 1 ／ 0
答案：0。幺元 e 需满足 a*e = a+e−ae = a → e(1−a)=0 对一切 a 成立 → e=0。
下面给出的集合中，哪一个是前缀码？（ ） {0,10,110,10111} ／ {1,11,101,001,0011} ／ {b,c,aa,ab,aba} ／ {01,001,000,1}
答案：{01,001,000,1}。前缀码 = 任一编码都不是另一编码的前缀。逐项验：A 中 10 是 10111 的前缀 ✗；B 中 1 是 11 的前缀 ✗；C 中 ab 是 aba 的前缀 ✗；D 中 01、001、000 两两仅在第 3 位后才分岔，互不为前缀 ✓。
在（ ）中，补元是唯一的？ 有界格 ／ 有补格 ／ 分配格 ／ 有补分配格
答案：有补分配格。定理：分配格中若元素有补元，则补元必唯一——有补分配格既保证补元存在、又保证唯一。
图论
一个割边集与任何生成树之间（ ） 没有关系 ／ 割边集诱导子图是生成树 ／ 有一条公共边 ／ 至少有一条公共边
答案：至少有一条公共边。把割边集全部删去图就不连通，而生成树连通——若某生成树与割边集无公共边，删割边集后生成树完好，矛盾。
设 G 是一棵树，n、m 分别表示顶点数和边数，则（ ） n=m ／ n=m+1 ／ m=n+1 ／ 不能确定
答案：n=m+1。树的边数 m = n−1，移项即 n = m+1。
一棵树有 10 片树叶，3 个 3 度结点，其余全是 4 度结点，则该树有（ ）个 4 度结点 1 ／ 2 ／ 3 ／ 4
⚠️ 按树叶数公式验算出原题数字对不上。树叶数公式：n₁ = n₃ + 2n₄ + 2（推导：Σ度数 = 2(n−1)，消去 2 度结点得 n₁ = 2 + n₃ + 2n₄）。代入 10 = 3 + 2n₄ + 2 → n₄ = 2.5 非整数——原题数字疑有出入（常见变体："2 个 3 度结点"则 n₄=3；"9 片树叶"则 n₄=2）。记住公式 n₁ = 2 + n₃ + 2n₄，考场代数字验算。
一棵无向树 T 有 4 度、3 度、2 度的分枝点各 1 个，其余顶点均为树叶，则 T 中有（ ）片树叶 3 ／ 4 ／ 7 ／ 6
按公式 n₁ = 2 + n₃ + 2n₄（2 度结点不影响）= 2 + 1 + 2×1 = 5。原文选项无 5，疑转录有出入——考场直接用公式算，别背选项。
设 S={0,1}，* 为普通乘法，则 <S，*> 是（ ） 半群，但不是独异点 ／ 只是独异点，但不是群 ／ 群 ／ 环，但不是群
答案：只是独异点，但不是群。乘法在 {0,1} 上封闭且 1×x=x（幺元 1）→ 独异点；但 0 无逆元 → 非群。
六阶群的子群的阶数可以是（ ） 1,2,5 ／ 2,4 ／ 3,6,7 ／ 2,3
答案：2,3。拉格朗日定理：子群的阶整除群的阶。6 的约数：1、2、3、6。
6 阶有限群的任何子群一定不是（ ） 2 阶 ／ 3 阶 ／ 4 阶 ／ 6 阶
答案：4 阶。4 不整除 6。同一考点正反两面考。
G 是简单有向图，可达矩阵 P(G) 刻画（ ）关系 点与边 ／ 边与点 ／ 点与点 ／ 边与边
答案：点与点。P[i][j]=1 表示从顶点 i 到顶点 j 存在通路——顶点间的可达性。
具有 6 个顶点、12 条边的连通简单平面图中，每个面都是由（ ）条边围成 2 ／ 4 ／ 3 ／ 5
答案：3。欧拉公式 F = E − V + 2 = 12 − 6 + 2 = 8 个面；Σ面次数 = 2E = 24；24 ÷ 8 = 3。
设 G 是有 n 个结点、m 条边的连通平面图，且有 k 个面，则 k =（ ） m−n+2 ／ n−m−2 ／ n+m−2 ／ m+n+2
答案：m−n+2。欧拉公式 V − E + F = 2 的直接变形。
设无向图 G 有 18 条边且每个顶点的度数都是 3，则图 G 有（ ）个顶点 10 ／ 4 ／ 8 ／ 12
答案：12。握手定理 Σdeg = 2m：3n = 36 → n = 12。
在任何图中必定有偶数个（ ） 度数为偶数的结点 ／ 入度为奇数的结点 ／ 度数为奇数的结点 ／ 出度为奇数的结点
答案：度数为奇数的结点。握手定理推论：奇度结点个数必为偶数。
设 n 阶图 G 有 m 条边，每个结点度数不是 k 就是 k+1。若 G 中有 Nₖ 个 k 度结点，则 Nₖ =（ ） n·k ／ n·(k+1) ／ n·(k+1)−m ／ n·(k+1)−2m
答案：n·(k+1)−2m。Σ度 = Nₖ·k + (n−Nₖ)(k+1) = 2m，解出 Nₖ = n(k+1) − 2m。
💬 评论