Complete knowledge summary of 8 practice problems organized from Notion notes基于 Notion 笔记整理的8道练习题完整知识点总结
Covering set theory, logical reasoning, function counting, number theory, graph theory and other core concepts包含集合理论、逻辑推理、函数计数、数论、图论等核心概念
掌握集合的基数计算、并集交集的性质、以及函数计数的基本方法
∈ (属于) 和 ⊆ (子集) 是集合论的基础关系。
对于连续整数集合，使用公式：(最后一个 - 第一个) + 1
| 运算类型 | 符号 | 含义 | 区间处理 |
|---|---|---|---|
| 并集 (Union) | $\bigcup S_n$ | 存在于某些集合中 | 最小下界到最大上界 |
| 交集 (Intersection) | $\bigcap S_n$ | 存在于所有集合中 | 最大下界到最小上界 |
| 子集的集合 | $\{X \mid X \subseteq A\}$ | A的所有子集 | 幂集 $\mathcal{P}(A)$ |
$n^m$
每个自变量有 n 种选择
$P(n,m)$
条件：$m \leq n$
存在条件
条件：$m \geq n$
题目设定：A 是由16个集合组成的集合，每个集合 $S_n$ 为连续整数区间
掌握英文逻辑句式到符号表达式的转换，以及逻辑等价的核心规则
用简单字母 P 和 Q 代替复杂术语
P = "X is skew-differentiable"
Q = "X is quantised"
$A \to B \equiv \neg A \lor B$
这是连接"if-then"和"or"的关键桥梁
将相似的逻辑表达式归类分组
找出等价命题的共同模式
| 符号 | 含义 | 英文表达 | 示例 |
|---|---|---|---|
| $\to$ | 蕴含 | if... then... | if P, then Q |
| $\land$ | 合取 | and | P and Q |
| $\lor$ | 析取 | or | P or Q |
| $\neg$ | 否定 | not | not P |
命题编号：{1, 6, 8}
命题编号：{3, 5}
等价原因：$Q \to P \equiv \neg Q \lor P$
命题编号：{4, 7}
等价原因：$\neg Q \to P \equiv Q \lor P$
命题编号：{2}
独立组：是第一组的否定
理解交集、并集、对称差的性质，掌握集合包含关系的证明方法
A, B, C
$$A \oplus B = (A \cup B) \setminus (A \cap B)$$
对称差包含属于A或属于B，但不同时属于A和B的元素。
优点：速度快，直观，适合考试
缺点：可能误判，例子成立不代表永远成立
示例：
设 A={1,2,3}, B={2,3,4}, C={1,5}
优点：结论100%可靠，理解本质
缺点：需要更多时间和逻辑推理
反例构造：
对命题(1) $Y \subseteq X \cup Z$：
令 A={1}, B={2}, C={3}
原因：$X = A \cap B \subseteq A \subseteq A \cup C = Y$
原因：X是公共部分，Z是非公共部分，它们的交集为空集，空集是任何集合的子集
原因：基于命题(8)，X⊆Y 自然包含在更大的集合 Y∪Z 中
学会用反例法推翻错误命题，理解向下取整函数的性质
"x是整数" ⟺ "⌊0.628x⌋ + ⌊0.372x⌋ = x"
向下取整函数：⌊y⌋ 表示不大于 y 的最大整数
例如：⌊7.9⌋ = 7，⌊-4.1⌋ = -5
即使是"证明题"，其命题本身也可能是错误的。在开始复杂证明前，先用简单数字检验。
我们将通过反例来反驳："如果 x 是整数，那么 ⌊0.628x⌋ + ⌊0.372x⌋ = x"
令 x = 1。显然 x = 1 满足"是整数"的前提条件。
LHS = ⌊0.628×1⌋ + ⌊0.372×1⌋
= ⌊0.628⌋ + ⌊0.372⌋
= 0 + 0 = 0
RHS = x = 1
LHS = 0 ≠ 1 = RHS
因此当 x = 1 时，等式不成立。
由于找到了反例，"当且仅当"命题的一个方向不成立，因此整个原命题是伪命题。
掌握线性同余方程的解题方法，包括解的存在性判断和求解技巧
对于方程 $$ax \equiv b \pmod{m}$$
如果 $d = \gcd(a,m)$ 不能整除 $b$
则解的数量 $n = 0$
如果 $d = \gcd(a,m)$ 可以整除 $b$
则恰好有 $d$ 个不同的解
用欧几里得算法计算 $d = \gcd(60, 325) = 5$
检查 $d$ 能否整除 $b$：$5 \mid 195$ ✓
因此方程有 $5$ 个解
方程两边和模数同时除以 $d = 5$：
$$12x \equiv 39 \pmod{65}$$
用扩展欧几里得算法找到特解：$x_0 = 52$
使用公式：$x = x_0 + k \cdot \frac{m}{d}$，其中 $k = 0, 1, 2, ..., d-1$
解集：{52, 117, 182, 247, 312}
如果 $b$ 未知但给出解 $x = 100$：
直接计算 $b \equiv ax \pmod{m}$
技巧：利用已知解避免复杂的扩展欧几里得算法
解的数量 $n$ 只有两种可能：
对于 $a = 18$：
$n$ 的可能值 = {0, 1, 2, 3, 6, 9, 18}
理解偏序关系的性质，掌握最小元、最大元、最小元素的概念和计算方法
$$S = \{n \in \mathbb{N} : 11 \leq n \leq 130 \text{ and } n = 3^i \cdot 7^j\}$$
| j值 | 形式 | 符合条件的数 |
|---|---|---|
| j = 0 | $n = 3^i$ | 27, 81 |
| j = 1 | $n = 3^i \cdot 7$ | 21, 63 |
| j = 2 | $n = 3^i \cdot 49$ | 49 |
最终集合：$S = \{21, 27, 49, 63, 81\}$
关系是 $|$ (整除)
$a | b$ 表示 a 整除 b
不被任何其他元素整除的元素
{21, 27, 49}
不能整除任何其他元素的元素
{49, 63, 81}
蓝色：最小元 | 橙色：最大元
与"最小元"的区别：
在所有 $3^i \cdot 7^j$ 形式的数中，只有 $1 = 3^0 \cdot 7^0$ 是最小元素。
结论：$n_0$ 最大值为 1
目标：找最大的 $n_0$，使 $T$ 最多有两个最小元
方法：排序 $3^i \cdot 7^j$ 的数：1, 3, 7, 9, 21, ...
| $n_0$ | $T$ 的最小元 | 数量 |
|---|---|---|
| 7 | {7, 9} | 2 ✓ |
| 8 | {9, 21, 49} | 3 ✗ |
结论：$n_0$ 最大值为 7
掌握补集法、两步法、容斥原理等高级计数技巧，解决复杂约束条件下的排列问题
符合条件的 = 总数 - 不符合条件的
适用场景：当"不符合"比"符合"更简单直接时
适用于本题的 (a) 和 (b) 部分
1. 选字母 (Choose) × 2. 排字母 (Arrange)
适用场景：复杂的排列问题分解为选择和排列
适用于本题的 (c) 和 (d) 部分
$n^m$
元素可重复时使用
如 (a) 部分
$P(n,k)$
不可重复且顺序重要
如 (b) 部分
$C(n,k)$
不可重复且顺序不重要
用于"选字母"步骤
例：(d) 中从17个字母中再选2个：$C(17,2) = 136$
容斥原理公式：
符合条件的排列 = 总排列 - (违反1个) + (违反2个) - (违反3个) + ...
(c) 中的计算：
$5! - [C(4,1) \cdot 4! - C(4,2) \cdot 3! + C(4,3) \cdot 2! - C(4,4) \cdot 1!] = 53$
将"选字母"和"排字母"的结果相乘
(d) 答案： $C(17,2) \times 50 = 136 \times 50 = 6800$
理解桥接图的构造，掌握度序列分析、图的性质验证和欧拉公式应用
图中所有顶点的度的列表，通常按降序排列
度 = 连接到该顶点的边数
两个独立图 $G_1$ 和 $G_2$ 通过一条边连接形成的图 $H$
桥会使连接的两个顶点度数各+1
度为1的顶点
在图的结构分析中很重要
$G_1$ 和 $G_2$ 各有一个度为1的顶点，为消除它们，桥必须连接这两个顶点。
$H$ 的度序列：{3, 3, 3, 3, 2, 2, 2, 2, 2, 2}
结论：这种度序列与桥接图的结构相矛盾
答案：有时为真，有时为假
原因：欧拉迹需要0个或2个奇数度顶点
桥改变连接顶点的奇偶性，可能导致4个奇数度顶点
答案：总是为真
原因：可通过合并相应集合构建$H$的两个集合
即使桥连接同侧顶点，也可通过对调修正
答案：总是为真
原因：连接两个独立树的边不会形成环
结果仍然是连通且无环的图
答案：总是为假
原因：只有一条桥连接两部分
无法形成包含所有顶点的闭合环路
答案：不会违反，$H$ 仍满足 $V - E + F = 2$
$V_H = V_1 + V_2$
$E_H = E_1 + E_2 + 1$
$F_H = F_1 + F_2 - 1$
$V_H - E_H + F_H$
$= (V_1 + V_2) - (E_1 + E_2 + 1) + (F_1 + F_2 - 1)$
$= (V_1 - E_1 + F_1) + (V_2 - E_2 + F_2) - 2$
$= 2 + 2 - 2 = 2$ ✓
Master cardinality calculation, union/intersection properties, and basic function counting methods
∈ (belongs to) and ⊆ (subset) are fundamental relations in set theory.
For consecutive integer sets, use formula: (last - first) + 1
| Operation Type | Symbol | Meaning | Interval Handling |
|---|---|---|---|
| Union | $\bigcup S_n$ | Exists in some sets | Smallest lower bound to largest upper bound |
| Intersection | $\bigcap S_n$ | Exists in all sets | Largest lower bound to smallest upper bound |
| Set of subsets | $\{X \mid X \subseteq A\}$ | All subsets of A | Power set $\mathcal{P}(A)$ |
$n^m$
Each argument has n choices
$P(n,m)$
Condition: $m \leq n$
Existence condition
Condition: $m \geq n$
Problem setup: A is a set of 16 sets, each set $S_n$ is a consecutive integer interval
Master converting English logical phrases to symbolic expressions and core logical equivalence rules
Replace complex terms with simple letters P and Q
P = "X is skew-differentiable"
Q = "X is quantised"
$A \to B \equiv \neg A \lor B$
This is the key bridge connecting "if-then" and "or"
Group similar logical expressions together
Find common patterns among equivalent propositions
| Symbol | Meaning | English Expression | Example |
|---|---|---|---|
| $\to$ | Implication | if... then... | if P, then Q |
| $\land$ | Conjunction | and | P and Q |
| $\lor$ | Disjunction | or | P or Q |
| $\neg$ | Negation | not | not P |
Proposition numbers: {1, 6, 8}
Proposition numbers: {3, 5}
Equivalent because: $Q \to P \equiv \neg Q \lor P$
Proposition numbers: {4, 7}
Equivalent because: $\neg Q \to P \equiv Q \lor P$
Proposition numbers: {2}
Independent group: negation of Group 1
Understand intersection, union, symmetric difference properties, master set inclusion proof methods
A, B, C
$$A \oplus B = (A \cup B) \setminus (A \cap B)$$
Symmetric difference contains elements that belong to A or B, but not both.
Pros: Fast, intuitive, suitable for exams
Cons: May lead to wrong conclusions, example success doesn't mean always true
Example:
Let A={1,2,3}, B={2,3,4}, C={1,5}
Pros: 100% reliable conclusion, understand the essence
Cons: Requires more time and logical reasoning
Counterexample Construction:
For proposition (1) $Y \subseteq X \cup Z$:
Let A={1}, B={2}, C={3}
Reason: $X = A \cap B \subseteq A \subseteq A \cup C = Y$
Reason: X is the common part, Z is the non-common part, their intersection is empty set, and empty set is a subset of any set
Reason: Based on proposition (8), X⊆Y is naturally contained in the larger set Y∪Z
Learn to disprove false propositions using counterexamples, understand floor function properties
"x is an integer" ⟺ "⌊0.628x⌋ + ⌊0.372x⌋ = x"
Floor function:⌊y⌋ represents the greatest integer not greater than y
For example: ⌊7.9⌋ = 7, ⌊-4.1⌋ = -5
Even "proof problems" may have false propositions. Before starting a complex proof, verify with simple numbers.
We will disprove by counterexample: "If x is an integer, then ⌊0.628x⌋ + ⌊0.372x⌋ = x"
Let x = 1. Clearly x = 1 satisfies the premise "is an integer".
LHS = ⌊0.628×1⌋ + ⌊0.372×1⌋
= ⌊0.628⌋ + ⌊0.372⌋
= 0 + 0 = 0
RHS = x = 1
LHS = 0 ≠ 1 = RHS
Therefore when x = 1, the equation does not hold.
Since we found a counterexample, one direction of the "if and only if" proposition fails, making the original proposition false.
Master solution methods for linear congruence equations, including existence judgment and solving techniques
For equation $$ax \equiv b \pmod{m}$$
If $d = \gcd(a,m)$ does not divide $b$
Then number of solutions $n = 0$
If $d = \gcd(a,m)$ divides $b$
Then exactly $d$ distinct solutions exist
Use Euclidean algorithm to compute $d = \gcd(60, 325) = 5$
Check if $d$ divides $b$: $5 \mid 195$ ✓
Therefore equation has $5$ solutions
Divide both sides and modulus by $d = 5$:
$$12x \equiv 39 \pmod{65}$$
Use extended Euclidean algorithm to find: $x_0 = 52$
Use formula: $x = x_0 + k \cdot \frac{m}{d}$, where $k = 0, 1, 2, ..., d-1$
Solution set: {52, 117, 182, 247, 312}
If $b$ is unknown but solution $x = 100$ is given:
Calculate directly $b \equiv ax \pmod{m}$
Tip: Use known solution to avoid complex extended Euclidean algorithm
Number of solutions $n$ has only two possibilities:
For $a = 18$:
Possible values of $n$ = {0, 1, 2, 3, 6, 9, 18}
Understand partial order relation properties, master minimal/maximal/least element concepts and calculation methods
$$S = \{n \in \mathbb{N} : 11 \leq n \leq 130 \text{ and } n = 3^i \cdot 7^j\}$$
| j value | Form | Matching numbers |
|---|---|---|
| j = 0 | $n = 3^i$ | 27, 81 |
| j = 1 | $n = 3^i \cdot 7$ | 21, 63 |
| j = 2 | $n = 3^i \cdot 49$ | 49 |
Final set: $S = \{21, 27, 49, 63, 81\}$
Relation is $|$ (divides)
$a | b$ means a divides b
Elements not divisible by any other element
{21, 27, 49}
Elements that cannot divide any other element
{49, 63, 81}
Blue: Minimal elements | Orange: Maximal elements
Difference from "Minimal Element":
Among all numbers of form $3^i \cdot 7^j$, only $1 = 3^0 \cdot 7^0$ is the least element.
Conclusion: Maximum value of $n_0$ is 1
Goal: Find largest $n_0$ such that $T$ has at most two minimal elements
Method: Sort numbers of form $3^i \cdot 7^j$: 1, 3, 7, 9, 21, ...
| $n_0$ | Minimal elements of $T$ | Count |
|---|---|---|
| 7 | {7, 9} | 2 ✓ |
| 8 | {9, 21, 49} | 3 ✗ |
Conclusion: Maximum value of $n_0$ is 7
Master advanced counting techniques including complement method, two-step method, inclusion-exclusion principle for complex constrained permutation problems
Valid = Total - Invalid
When to use: When "invalid" is simpler to describe than "valid"
Applies to parts (a) and (b) of this problem
1. Choose letters × 2. Arrange letters
When to use: Complex permutation problems broken into selection and arrangement
Applies to parts (c) and (d) of this problem
$n^m$
When repetition is allowed
e.g., part (a)
$P(n,k)$
No repetition, order matters
e.g., part (b)
$C(n,k)$
No repetition, order doesn't matter
Used in "choose letters" step
Example: in (d) Choose 2 more letters from 17: $C(17,2) = 136$
Inclusion-Exclusion Formula:
Valid arrangements = Total - (violate 1) + (violate 2) - (violate 3) + ...
Calculation in (c):
$5! - [C(4,1) \cdot 4! - C(4,2) \cdot 3! + C(4,3) \cdot 2! - C(4,4) \cdot 1!] = 53$
Multiply "choose letters" and "arrange letters" results
(d) Answer: $C(17,2) \times 50 = 136 \times 50 = 6800$
Understand bridge graph construction, master degree sequence analysis, graph property verification, and Euler's formula application
List of all vertex degrees in a graph, usually sorted in descending order
Degree = number of edges connected to a vertex
Graph $H$ formed by connecting two independent graphs $G_1$ and $G_2$ with a single edge
Bridge adds 1 to degree of both connected vertices
Vertex with degree 1
Important in graph structure analysis
$G_1$ and $G_2$ each have one degree-1 vertex. To eliminate them, bridge must connect these two vertices.
$H$ degree sequence: {3, 3, 3, 3, 2, 2, 2, 2, 2, 2}
Conclusion: This degree sequence contradicts bridge graph structure
Answer: Sometimes true, sometimes false
Reason: Euler trail requires 0 or 2 odd-degree vertices
Bridge changes parity of connected vertices, may result in 4 odd-degree vertices
Answer: Always true
Reason: Can construct two sets of $H$ by merging corresponding sets
Even if bridge connects same-side vertices, can be fixed by swapping
Answer: Always true
Reason: Edge connecting two independent trees won't form a cycle
Result is still a connected, acyclic graph
Answer: Always false
Reason: Only one bridge connects the two parts
Cannot form a closed loop containing all vertices
Answer: No, $H$ still satisfies $V - E + F = 2$
$V_H = V_1 + V_2$
$E_H = E_1 + E_2 + 1$
$F_H = F_1 + F_2 - 1$
$V_H - E_H + F_H$
$= (V_1 + V_2) - (E_1 + E_2 + 1) + (F_1 + F_2 - 1)$
$= (V_1 - E_1 + F_1) + (V_2 - E_2 + F_2) - 2$
$= 2 + 2 - 2 = 2$ ✓