---
title: "02-离散数学"
created: 2026-08-29
tags:
  - 基础与理论
  - 信息基础大赛
---

# 第 11~20 题：离散数学

> 📚 本文是 [[00-信息基础大赛|信息基础大赛]]（10.29 备赛）的第 2 篇，题目以截图为主、文字为点拨。

**战术定位**：这一块一时半会补不清楚，**靠记答案**，能碰到几题是几题。不过**命题树（树）这块写得出些**，目标拿到 **7 分左右**——树的度数计算、平面图欧拉公式是稳定送分点，见下文【图论】。

## 命题逻辑

### 什么算命题

> 下列语句是命题的有（　）
> 明年中秋节的晚上是晴天 ／ x+y>0 ／ x\*y>0 当且仅当 x 和 y 都大于 0 ／ 我正在说谎

判断标准三条：

1. **真值客观唯一**（哪怕现在不知道）→ 是命题。"明年中秋晚上是晴天"真值确定，是命题
2. **含自由变量、真值随取值变** → 不是。x+y>0 就不是
3. **悖论（自我指涉）** → 不是。"我正在说谎"无法赋真值

> 下列**不是**命题的是（　）
> 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：李四。命题"张三是三好学生而李四不是"符号化为（　）

![[image9.png]]

点拨："……而……不是"就是**合取**：S(a) ∧ ¬S(b)，选含这一形式的选项。

### CP 规则与推理定律

> 命题逻辑演绎的 CP 规则为（　）
> ① 在推演过程中可随便使用前提
> ② 在推演过程中可随便使用前面演绎出的某些公式的逻辑结果
> ③ 如果要演绎出的公式为 B→C 形式，那么将 B 作为附加前提，演绎出 C
> ④ 设 B 是含公式 A 的公式，则可用 B 替换其中的 A

答案：**③**。CP 规则（条件证明规则）：欲证 B→C，把 B **作为附加前提**引入，若能推出 C，则 B→C 成立。② 说的是推理的一般规则，④ 是置换规则。

> 下面 4 个推理定律中，**不正确**的为（　）

![[image10.png]]

![[image11.png]]

![[image12.png]]

![[image13.png]]

答案：**第 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。

⬅️ [[01-进制与编码|上一篇]] 🏠 [[00-信息基础大赛]] ➡️ [[03-专利与知识产权|下一篇]]