数学逻辑与离散基础
在海淀第二赛段(计算思维)中,数学逻辑类题目占比高达 30%。计算机程序的本质是离散数学模型的物理执行,本模块将带你建立严密的离散推演能力。
1.2 集合与容斥原理(Inclusion-Exclusion Principle)
集合是具有某种特定性质的对象聚集。在算法计数中,经常遇到“求满足条件 A 或条件 B 的元素总数”的问题。为避免对同时满足 A 和 B 的重叠部分重复计算,我们需要使用容斥原理。
📌 核心计算公式
两集合容斥公式:
三集合容斥公式:
口诀:“奇加偶减” —— 奇数个集合的交集取正号累加,偶数个集合的交集取负号扣除。
容斥原理韦恩图(Venn Diagram)动态实验室
拖动下方滑块调节集合 A、集合 B 以及交集 A ∩ B 的元素数量,观察重叠阴影与总并集 |A ∪ B| 的动态计算过程:
1.3 函数映射与复合运算(真题直击)
在 2025 年海淀初赛中,连续考察了两道关于函数本质的题目。在现代数学与编程中,函数代表一种确定性规则:每个输入必须对应唯一确定的输出。
集合间的映射函数个数
设集合 A = {1, 2, 3} 为定义域,B = {a, b, c} 为值域。从 A 到 B 的不同函数个数是多少?
• 元素 1 在 B 中有 3 种选择;
• 元素 2 在 B 中有 3 种选择;
• 元素 3 在 B 中有 3 种选择;
根据乘法原理,总映射数 = 3 × 3 × 3 = 3³ = 27 种。
(推广规律:若 |A| = m, |B| = n,则函数总数为 nᵐ)
复合函数运算 f(g(x))
若已知 f(x) = 2x + 3 与 g(x) = x - 1,求 f(g(2)) 的值。
1. 先算内层:g(2) = 2 - 1 = 1;
2. 再算外层:将结果 1 代入 f(x),即求 f(1);
3. f(1) = 2 × 1 + 3 = 5。
提示:与 Scratch 中嵌套积木积木逻辑完全一致!
1.4 排列组合进阶三法宝(捆绑、插空、隔板)
第二赛段的计数问题往往带有复杂的限制条件(如“必须相邻”、“不能相邻”或“正整数解”)。掌握以下三大经典模型,即可秒杀此类题目:
捆绑法 —— 处理“必须相邻”问题
核心思路:将必须相邻的元素“打包捆绑”视作一个单一的大元素,先与其他元素一起全排列,最后乘上大元素内部各个小元素的排列数。
• 把 3 本语文书捆成一个大元素 [语],内部全排列为 A(3, 3) = 6 种;
• [语] 与 1 本数学书进行排列,排列数为 A(2, 2) = 2 种。
插空法 —— 处理“不能相邻”问题
核心思路:先排好没有不相邻限制的普通元素,这些元素之间以及两端会形成若干个“空隙”,再将不能相邻的特殊元素插入到这些空隙中。
_ [语] _ [数] _),共产生 3 个互不相邻的空隙。• 2 本英语书不能相邻,插入这 3 个空位中,方案数为 A(3, 2) = 3 × 2 = 6 种;
• 乘法原理总计:6 × 2 × 6 = 72 种。
隔板法 —— 处理“不定方程正整数解”
核心思路:将 n 个相同的小球排成一排,在小球之间形成的 n - 1 个空隙中插入 k - 1 块隔板,将其分成 k 份。
• 12 个相同小球排成一排,内部有 12 - 1 = 11 个空隙;
• 分成 3 份需要插入 3 - 1 = 2 块隔板;
• 解的组数等于组合数 C(11, 2) = (11 × 10) / (2 × 1) = 55 组。
1.5 逻辑命题与真假推理(五人猜城市推演)
逻辑推理题是初赛必考题型。解决“每人只答对一半”题型的核心是假设分析法或排除代入法。
五位同学猜五个城市 A、B、C、D、E(北京、天津、湖北、重庆、吉林),每人恰好猜对一半:
- 甲:B 是北京,E 是天津
- 乙:B 是湖北,D 是重庆
- 丙:C 是湖北,D 是吉林
- 丁:A 是重庆,E 是吉林
- 戊:B 是天津,C 是北京
2. 丙前半句“C是湖北”必为假(因为B已经是湖北),则后半句“D是吉林”必为真;
3. 丁后半句“E是吉林”必为假(因为D已经是吉林),则前半句“A是重庆”必为真;
4. 甲前半句“B是北京”必为假(B是湖北),则后半句“E是天津”必为真;
5. 此时已确定:A=重庆, B=湖北, D=吉林, E=天津。只剩 C 未定,剩下唯一城市是北京,即 C=北京。
6. 验证戊:B是天津(假),C是北京(真),恰好对一半!全部条件完美吻合!
模块一 · 全真过关检测(共6题)
对于定义域 A 中的每一个元素,在值域 B 中都有 3 种可能的对应选择:元素 1 有 3 种选择,元素 2 有 3 种选择,元素 3 也有 3 种选择。根据乘法原理,总的映射函数个数为 3 × 3 × 3 = 3³ = 27 种。故选 C。
第一步算内层:g(2) = 2 - 1 = 1;
第二步算外层:f(1) = 2 × 1 + 3 = 5。故选 B。
经典隔板法模型:12 个相同小球之间有 11 个内部空隙,在 11 个空隙中插入 2 块隔板分为 3 份。选法数为组合数 C(11, 2) = (11 × 10) / (2 × 1) = 55 组。故选 A。
捆绑法:3 本语文书排 A(3,3)=6 种;与数学书排 A(2,2)=2 种;产生 3 个空隙;
插空法:2 本英语书插 3 个空隙 A(3,2)=6 种;
总排法 = 6 × 2 × 6 = 72 种。故选 C。
甲说:B 是北京,E 是天津
乙说:B 是湖北,D 是重庆
丙说:C 是湖北,D 是吉林
丁说:A 是重庆,E 是吉林
戊说:B 是天津,C 是北京
请问正确的城市对应关系是( )。
选项 D 中:甲对E、乙对B、丙对D、丁对A、戊对C,五人均恰好只猜对一半,且五座城市互不重复,完全成立。故选 D。
能被 5 整除末位只能是 0 或 5:
• 末位为 0:偶数再选 1 个 C(4,1)=4,奇数选 2 个 C(4,2)=6,前三位排 A(3,3)=6,共 4×6×6 = 144 个;
• 末位为 5:奇数再选 1 个 C(3,1)=3。若偶数含 0(C(4,1)=4,排法 2×2×1=4,计 3×4×4=48 个);若偶数不含 0(C(4,2)=6,排法 A(3,3)=6,计 3×6×6=108 个);合计 48+108 = 156 个;
• 总计 = 144 + 156 = 300 个。故选 C。