MATH1081 - Lab Test 2 详细笔记 | 逻辑与组合数学

1 逻辑表达式简化与类型判定Simplify propositions & classify forms

基础操作口诀

这是你填写真值表时需要刻在脑子里的四条规则：

1. ∧ (且/AND)

一假则假

只要有一个 F，结果就是 F

2. ∨ (或/OR)

一真则真

只要有一个 T，结果就是 T

3. ¬ (非/NOT)

真变假，假变真

简单的取反操作

4. → (蕴含/IMPLIES)

真推假，才是假

只有 T → F 是 F，其他都是 T

核心目标：判断表达式类型

重言式 (Tautology)

特征：永真式

无论 p, q 是什么，结果永远是 T

记忆：必然真理

例：$p ∨ ¬p ≡ T$

矛盾式 (Contradiction)

特征：永假式

无论 p, q 是什么，结果永远是 F

记忆：必然矛盾

例：$p ∧ ¬p ≡ F$

偶发式 (Contingency)

特征：不确定

结果有真有假，取决于 p, q 的取值

记忆：看情况

例：$p ∧ q$

万能解题公式

🎯 不要依赖真值表！用下面的公式化步骤，更快更准。

步骤1：简化。用公式工具箱里的公式，把复杂表达式一步步简化到最简形式。
步骤2：判断。看简化后的最终结果：
- 如果结果是 T → 重言式 (Tautology)
- 如果结果是 F → 矛盾式 (Contradiction)
- 如果结果包含 p, q 的式子 → 偶发式 (Contingency)

公式工具箱

必须死记硬背的核心公式：

1. 蕴含等价式 (最重要!)：

$A → B ≡ ¬A ∨ B$

用于消灭 → 符号

2. 德摩根定律：

$¬(A ∨ B) ≡ ¬A ∧ ¬B$

$¬(A ∧ B) ≡ ¬A ∨ ¬B$

用于处理括号外的 ¬ 符号

3. 双重否定律：

$¬(¬A) ≡ A$

负负得正

4. 否定律：

$A ∨ ¬A ≡ T$ (排中律)

$A ∧ ¬A ≡ F$ (矛盾律)

判断重言式和矛盾式的最后一步

5. 其他常用公式：

幂等律： $A ∨ A ≡ A$；$A ∧ A ≡ A$

支配律： $A ∨ T ≡ T$；$A ∧ F ≡ F$

实战演练示例

例1：判断 $¬(¬p ∨ ¬q) ∧ ¬(p → q)$

目标：简化这个表达式

原式： $¬(¬p ∨ ¬q) ∧ ¬(p → q)$
第一步 (德摩根 + 蕴含等价)： $(¬(¬p) ∧ ¬(¬q)) ∧ ¬(¬p ∨ q)$
第二步 (双重否定 + 德摩根)： $(p ∧ q) ∧ (¬(¬p) ∧ ¬q)$
第三步 (双重否定)： $(p ∧ q) ∧ (p ∧ ¬q)$
第四步 (合并同类项)： $p ∧ p ∧ q ∧ ¬q$
第五步 (幂等律 + 否定律)： $p ∧ F$
第六步 (支配律)： $F$

结论：最终结果是 F，所以它是矛盾式 (Contradiction)。

例2：判断 $(¬p ∨ ¬q) → (p ∧ q)$

原式： $(¬p ∨ ¬q) → (p ∧ q)$
第一步 (蕴含等价)： $¬(¬p ∨ ¬q) ∨ (p ∧ q)$
第二步 (德摩根)： $(¬(¬p) ∧ ¬(¬q)) ∨ (p ∧ q)$
第三步 (双重否定)： $(p ∧ q) ∨ (p ∧ q)$
第四步 (幂等律)： $p ∧ q$

结论：最终结果是 $p ∧ q$，它不是 T 也不是 F，它的真假"看情况"，所以它是偶发式 (Contingency)。

Core rules you must recall

Tautology

Always true. Every input yields T.

Think “guaranteed truth”.

Example: $p \lor \neg p$.

Contradiction

Always false. Every input yields F.

Think “built-in conflict”.

Example: $p \land \neg p$.

Contingency

Sometimes true, sometimes false.

Think “depends on inputs”.

Example: $p \land q$.

Two-step decision recipe

🎯 Avoid brute-force truth tables—rewrite and then classify.

Simplify. Use the identity toolkit to remove $\rightarrow$, push negations inward, and condense the expression.
Inspect the result.
- Expression becomes T → tautology.
- Expression becomes F → contradiction.
- Still depends on variables → contingency.

Identity toolkit

Have these five patterns ready:

1. Implication removal:

$A \rightarrow B \equiv \neg A \lor B$

First move whenever an arrow appears.

2. De Morgan’s laws:

$\neg(A \lor B) \equiv \neg A \land \neg B$

$\neg(A \land B) \equiv \neg A \lor \neg B$

Use to push negation inside brackets.

3. Double negation:

$\neg(\neg A) \equiv A$

4. Law of excluded middle / contradiction:

$A \lor \neg A \equiv T$

$A \land \neg A \equiv F$

Final check for tautology vs contradiction.

5. Other helpers:

Idempotent: $A \lor A \equiv A$, $A \land A \equiv A$

Dominance: $A \lor T \equiv T$, $A \land F \equiv F$

Worked examples

Example 1: $\neg(\neg p \lor \neg q) \land \neg(p \rightarrow q)$

Original expression: $\neg(\neg p \lor \neg q) \land \neg(p \rightarrow q)$
Remove implication + apply De Morgan: $(\neg(\neg p) \land \neg(\neg q)) \land \neg(\neg p \lor q)$
Eliminate double negations: $(p \land q) \land (\neg(\neg p) \land \neg q)$
Simplify: $(p \land q) \land (p \land \neg q)$
Collect terms: $p \land p \land q \land \neg q$
Apply identities: $p \land F = F$

Conclusion: final result is F → contradiction.

Example 2: $(\neg p \lor \neg q) \rightarrow (p \land q)$

Rewrite arrow: $\neg(\neg p \lor \neg q) \lor (p \land q)$
Apply De Morgan: $(\neg\neg p \land \neg\neg q) \lor (p \land q)$ → $(p \land q) \lor (p \land q)$
Use idempotent law: $p \land q$

Conclusion: result is $p \land q$, so the overall proposition is a contingency.

2 真值表分析与逻辑等价Truth tables & logical equivalence

示例真值表

p	q	r
T	F	T
F	T	F
T	T	T
F	F	F

Part a) 找出逻辑等价式

核心概念：

双蕴含 X ⟷ Y：意味着 X 和 Y 的真值列必须完全一样
蕴含 Y → Z：只有在 Y 是 T 且 Z 是 F 时，结果才是 F

做题步骤 (口诀："找唯一假，再全验！")：

观察单个命题的真值列：看哪个最特殊
"找唯一假"：计算常见蕴含式的真值列
全面比较：将蕴含式的真值列与所有单个命题比较

示例分析：

1. 计算 p → q 的真值列：

T → F = F (第1行)
F → T = T (第2行)
T → T = T (第3行)
F → F = T (第4行)

所以 p → q 的真值列是：F, T, T, T

2. 比较各命题的真值列：

r 列: T, F, T, F
¬r 列: F, T, F, T
p → q: F, T, T, T

发现：¬r 的真值列与 p → q 的真值列不完全一样，但可能存在其他等价关系。

Part b) 逻辑操作三大类型详解

⚠️ 重要概念区分：

Negation 与 Converse (逆命题) 和 Contrapositive (逆否命题) 是三种完全不同的逻辑操作。

Converse/Contrapositive：是对原命题进行"结构重组"
Negation：是求原命题的"反义词"，即找出让原命题为假的条件

Question 2 速成笔记 (V3.0 最终版)

核心概念：严格区分三种逻辑操作

操作类型	目标	变形规则
1. 求逆命题 (Converse)	$A → B ⇒ B → A$	1. 前后对调得到 $B → A$ 2. 再用蕴含等价式 $¬B ∨ A$ 消灭箭头
2. 求逆否命题 (Contrapositive)	$A → B ⇒ ¬B → ¬A$	1. 换位再取反得到 $¬B → ¬A$ 2. 再用蕴含等价式 $¬(¬B) ∨ ¬A = B ∨ ¬A$ 消灭箭头
3. 求否定 (Negation)	$A → B ⇒ A ∧ ¬B$	方法一 (三连招): 1. $¬(A→B)$ 2. $¬(¬A∨B)$ 3. $A∧¬B$ 方法二 (记口诀): "箭头变'与'，后面取反"

重点：求解"否定(Negation)"的标准公式

对于一个蕴含式 $A → B$，求它的否定 $¬(A → B)$ 有一套固定的"三连招"公式。

"三连招"：消灭箭头 → 德摩根 → 双重否定

第一招：蕴含等价式 (消灭箭头)

$¬(A → B) ≡ ¬(¬A ∨ B)$

第二招：德摩根定律

$¬(¬A ∨ B) ≡ ¬(¬A) ∧ ¬B$

第三招：双重否定律

$¬(¬A) ∧ ¬B ≡ A ∧ ¬B$

结论：$A → B$ 的否定，就是 $A ∧ ¬B$

口诀可以记为："箭头变'与'，后面取反"

解答本题 Part (b) - 完整实战演练

第一步：确定 Part (a) 的右侧命题

首先，我们需要根据真值表确定 Part (a) 的完整陈述。我们来看一下真值表 (p, q, r) 为真的情况：

(T, T, T), (T, F, F), (F, T, T), (F, F, T)

我们来检验一下 r 和 p → q 的关系：

p=T, q=T: p→q 为 T. r 为 T. r ↔ (p→q) 为 T. (匹配)
p=T, q=F: p→q 为 F. r 为 F. r ↔ (p→q) 为 T. (匹配)
p=F, q=T: p→q 为 T. r 为 T. r ↔ (p→q) 为 T. (匹配)
p=F, q=F: p→q 为 T. r 为 T. r ↔ (p→q) 为 T. (匹配)

太棒了！Part(a) 的陈述就是 r ↔ (p → q)。所以，它的右侧命题是 p → q。

第二步：求 p → q 的否定 (Negation)

我们直接套用刚刚总结的公式 $¬(A → B) ≡ A ∧ ¬B$。

在这里, A 是 p, B 是 q。

所以，$¬(p → q)$ 的等价式是：$p ∧ ¬q$

Numbas 答案: 在下拉菜单中选择 p, ∧, ¬q

💡 学习流程总结：

解题流程: "先变形，再消箭头" 或 "直接用否定公式"
三种操作要分清：逆命题 (前后对调)、逆否命题 (换位再取反)、否定 (求"反义词")
否定最重要：掌握"三连招"公式和"箭头变'与'，后面取反"口诀
真值表验证：每次都要先确认 Part a) 的等价关系

Sample truth table

p	q	r
T	F	T
F	T	F
T	T	T
F	F	F

Part (a) Locate the equivalent statement

Key ideas

Biconditional $X \leftrightarrow Y$: the two columns must match exactly.
Implication $Y \rightarrow Z$: only fails when $Y$ is T and $Z$ is F.

Procedure (“spot the unique F, then confirm”)

Scan each column. Look for distinctive truth patterns.
Compute common implications. Build candidate truth columns such as $p \rightarrow q$.
Compare. Match the candidate with the existing statements and pick the identical one.

Worked analysis

1. Truth column for $p \rightarrow q$.

T → F = F (row 1)
F → T = T (row 2)
T → T = T (row 3)
F → F = T (row 4)

So the column is F, T, T, T.

2. Compare with the given propositions.

$r$: T, F, T, F
$\neg r$: F, T, F, T
$p \rightarrow q$: F, T, T, T

Outcome: $r$ and $p \rightarrow q$ agree exactly on all rows when wrapped in a biconditional, so Part (a) is $r \leftrightarrow (p \rightarrow q)$.

Part (b) Distinguish the three transformations

Important distinctions

Converse and contrapositive rearrange the statement; negation finds when the original is false.

Question 2 quick sheet (V3.0 final)

Goal: keep the three operations straight.

Operation	Target form	Transformation steps
1. Converse	$A \rightarrow B \Rightarrow B \rightarrow A$	1. Swap premise/conclusion → $B \rightarrow A$ 2. Remove the arrow using $\neg B \lor A$
2. Contrapositive	$A \rightarrow B \Rightarrow \neg B \rightarrow \neg A$	1. Swap and negate → $\neg B \rightarrow \neg A$ 2. Remove the arrow: $\neg(\neg B) \lor \neg A = B \lor \neg A$
3. Negation	$A \rightarrow B \Rightarrow A \land \neg B$	Method 1 (three moves): 1. $\neg(A \rightarrow B)$ 2. $\neg(\neg A \lor B)$ 3. $A \land \neg B$ Method 2 (mnemonic): “arrow becomes AND, negate the back half”

Highlight: negation’s three-move combo

To negate $A \rightarrow B$, always run the same trio of identities.

Sequence: remove arrow → apply De Morgan → clear double negation

1. Implication equivalence.

$\neg(A \rightarrow B) \equiv \neg(\neg A \lor B)$

2. De Morgan.

$\neg(\neg A \lor B) \equiv \neg(\neg A) \land \neg B$

3. Double negation.

$\neg(\neg A) \land \neg B \equiv A \land \neg B$

Conclusion: $\neg(A \rightarrow B) = A \land \neg B$.

Mnemonic: “arrow to AND, negate the tail”.

Full solution for Part (b)

Step 1. Confirm the right-hand statement in Part (a)

Check the rows where $(p,q,r)$ is true:

(T, T, T), (T, F, F), (F, T, T), (F, F, T)

Evaluate $r$ versus $p \rightarrow q$:

$p=T, q=T$: $p \rightarrow q = T$, $r = T$ → biconditional true.
$p=T, q=F$: $p \rightarrow q = F$, $r = F$ → biconditional true.
$p=F, q=T$: $p \rightarrow q = T$, $r = T$ → biconditional true.
$p=F, q=F$: $p \rightarrow q = T$, $r = T$ → biconditional true.

Therefore Part (a) is $r \leftrightarrow (p \rightarrow q)$, so the “right-hand statement” we negate is $p \rightarrow q$.

Step 2. Negate $p \rightarrow q$

Apply the combo above: $\neg(p \rightarrow q) = p \land \neg q$.

Numbas input: select $p$, $\land$, and $\neg q$ from the menus.

💡 Study summary

Two approaches: rewrite first, or jump straight to the negation identity.
Keep the trio straight: converse (swap), contrapositive (swap + negate), negation (premise AND not conclusion).
Master the three-move combo. It guarantees the correct negation quickly.
Always verify with the table. Confirm the equivalence in Part (a) before submitting Part (b).

3 组合数学综合应用Combinatorics applications

核心概念区分

组合 (Combination)

$C(n, k)$ 或 $\binom{n}{k}$

定义：从 n 个不同元素中选出 k 个元素，不考虑顺序

公式：$C(n,k) = \frac{n!}{k!(n-k)!}$

口诀："只选不排"

适用：挑选小组成员、抽奖、选水果

排列 (Permutation)

$P(n, k)$ 或 $A_n^k$

定义：从 n 个不同元素中选出 k 个元素并进行排列

公式：$P(n,k) = \frac{n!}{(n-k)!}$

口诀："选了要排"

适用：排队、分配职务、数字密码

阶乘 (Factorial)

$n! = n × (n-1) × (n-2) × \ldots × 2 × 1$

特殊值：$0! = 1$，$1! = 1$

全排列：$P(n,n) = n!$

Part a) 剧团选角与角色分配

题目：19 人试镜，8 人入选。其中 6 人有命名角色。问有多少种情况？

思路分解：这是分两步进行的事件，每一步都是独立的，所以用乘法原理。

第一步：从 19 人中选出 8 人入选

"选出"意味着不考虑顺序，所以是组合
计算：$C(19, 8)$

第二步：从这 8 名入选者中，有 6 人获得命名角色

"命名角色"意味着有特定的职务或位置，需要排序，所以是排列
注意：这 6 人是从已经选出的 8 人中选出来的
计算：$P(8, 6)$

答案：$C(19, 8) × P(8, 6)$

记忆点：

"挑人入选" → 组合 (无序)
"命名角色" → 排列 (有序)
"分步完成" → 乘法

Part b) 男女交替排列

题目：4 男 4 女排成一列，使男女交替排列。问有多少种方式？

思路分解：交替排列意味着两种基本模式：

男-女-男-女-男-女-男-女 (BGBGBGBG)
女-男-女-男-女-男-女-男 (GBGBGBGB)

计算步骤：

内部排列：4 名男生可以有 4! 种方式排列
内部排列：4 名女生可以有 4! 种方式排列
模式选择：有 2 种交替模式（以男开头或以女开头）

答案：$4! × 4! × 2$

= 24 × 24 × 2 = 1152

记忆点："交替排列" → 考虑开头（男女两种），然后各自内部排列

Part c) 5 位数，所有数字不同且都是奇数

题目：有多少个 5 位数，满足所有数字都不同，并且所有数字都是奇数？

思路分解：

确定可用数字：奇数有 1, 3, 5, 7, 9，总共 5 个
确定位数：5 位数
条件：所有数字都不同，且都是奇数

这意味着我们必须使用这 5 个奇数，并且把它们全部排列起来组成 5 位数。这实际上是 5 个不同元素的全排列。

计算：

第一位有 5 种选择 (从 1, 3, 5, 7, 9 中选一个)
第二位有 4 种选择 (剩下的 4 个中选一个)
第三位有 3 种选择
第四位有 2 种选择
第五位有 1 种选择

答案：$5 × 4 × 3 × 2 × 1 = 5! = 120$

记忆点："所有数字不同，且所有数字都是奇数，组成一个由这些奇数组成的 5 位数" → 就是这些奇数的全排列

Part d) 元素相邻问题 - 捆绑法详解

题目：7个男生和3个女生排成一列，要求两个特定的学生必须相邻。有多少种排列方式？

问题分析：为什么"男女交替"的笔记不适用？

男女交替：核心要求是形成一个特定模式 (Pattern)，比如 BGBGBG...
两人相邻：核心要求是让某几个元素"黏"在一起，像胶水一样粘住，不关心其他人的位置模式

所以，我们需要为这个新题型建立一个全新的"速成笔记"。

解题方法："捆绑法"三步走

口诀："先捆绑，再排外，后排内"

1 第一步：捆绑 (Bundle)

任务：把必须相邻的元素看作一个不可分割的整体
操作：题目要求"两个特定的学生"相邻。我们用一根绳子把这两个学生"捆"在一起，把他们当成一个"巨无霸学生"
示例：比如这两个学生是 A 和 B，我们就创造一个新单位 (AB)

2 第二步：排外 (Arrange the Outside)

任务：将"巨无霸"单位和其他剩余的元素进行全排列
操作：
- 原来总共有 7+3 = 10 个学生
- 我们拿走了 2 个学生，捆成了 1 个"巨无霸"
- 现在需要排列的"单位"总数是：8 个普通学生 + 1 个"巨无霸"单位 = 9 个单位
- 把这 9 个单位进行全排列，方法数是 9!

3 第三步：排内 (Arrange the Inside)

任务：考虑被"捆绑"的那个整体，其内部成员也可以有自己的排列
操作：
- 我们捆绑的是 A 和 B 两个学生
- 在"巨无霸"单位内部，可以是 (A, B) 的顺序，也可以是 (B, A) 的顺序
- 他们内部的排列方法数是 2!

4 最后一步：相乘

根据乘法原理，总的排列方法数就是"排外"的方法数乘以"排内"的方法数。

总方法数 = 9! × 2!

Numbas 答案格式

根据系统偏好，使用 perm(n, k) 函数来表示阶乘 n! (perm(n, n))。

最终答案：perm(9, 9) * perm(2, 2)

【新】捆绑法通用公式表

题型	核心方法	口诀	公式化步骤
元素相邻问题 (如: 2人相邻, 3人相邻)	捆绑法 (Bundling)	先捆绑，再排外，后排内	1. 捆绑: 将 k 个必须相邻的元素视为 1 个大单位。 2. 排外: 计算 (总人数 - k + 1) 个单位的全排列，即 (n - k + 1)!。 3. 排内: 计算被捆绑的 k 个元素内部的全排列，即 k!。 4. 相乘: 最终答案 = (n - k + 1)! * k!
男女交替问题	插空法/模式法	先排一队，再插另一队	1. 内部排: 计算男队内部排列 (男!) 和女队内部排列 (女!)。 2. 模式选: 看有几种开头模式 (男开头或女开头)。 3. 相乘: 答案 = 男! * 女! * 模式数。

高级应用技巧

常见解题策略：

分步计数原理：如果一个过程可以分解为几个步骤，用乘法
分类计数原理：如果问题可以分为几种情况，用加法
容斥原理：总数 - 不满足条件的数量
限制条件处理：先处理限制，再处理其余
相邻问题：捆绑法（相邻的看作一个单位）
不相邻问题：插空法（先排其他，再插入）

复杂示例：编程竞赛队组建

情境：15名学生申请，选6人组队，其中4人担任特定角色，2人为普通队员

解题思路：

第一步：从15人中选6人 → $C(15,6)$
第二步：从6人中选4人担任特定角色 → $P(6,4)$
答案：$C(15,6) × P(6,4)$

或者用另一种思路：

直接选4人担任角色：$P(15,4)$
从剩下11人中选2人：$C(11,2)$
答案：$P(15,4) × C(11,2)$

Core distinctions

Combination ($C(n,k)$)

Choose $k$ items from $n$ with no attention to order.

Formula: $C(n,k)=\frac{n!}{k!(n-k)!}$.

Use for pure selection problems.

Permutation ($P(n,k)$)

Choose and arrange $k$ items; order matters.

Formula: $P(n,k)=\frac{n!}{(n-k)!}$.

Use for ordering, seating, role assignment.

Factorial recap

$n!$ counts all permutations of $n$ distinct items; remember $0! = 1$.

Worked subproblems

(a) Theatre casting

Select 8 actors with $C(19,8)$, then order 6 named roles with $P(8,6)$ → multiply the two.

(b) Alternating genders

Two start patterns (M/F). Within each pattern, arrange men $4!$ and women $4!$ → answer $2\cdot 4!\cdot 4!$.

(c) Five-digit odd numbers

Permute the digits {1,3,5,7,9}; total $5! = 120$.

(d) Two students must stay together

Bundle the pair into one block.
Arrange block + remaining eight → $9!$ ways.
Swap within the block → $2!$ ways.

Total $9!\times2$ (expressible as `perm(9,9)*perm(2,2)` for Numbas).

Bundling quick reference

Adjacent constraints → treat glued elements as one unit, then multiply by their internal permutations.
Alternation patterns → count valid layouts, then multiply by internal permutations.
Mixed roles → combine combinations (choose who) with permutations (assign order).

Extended example: programming team

Select 6 from 15, assign 4 special roles: $C(15,6) \times P(6,4)$.

Equivalent approach: choose role-holders directly $P(15,4)$, then choose two additional members $C(11,2)$.

Strategies: use multiplication for sequential steps, addition for disjoint cases, complement or inclusion–exclusion for restrictions.

4 日程安排与鸽巢原理Scheduling & Pigeonhole Principle

Part a) 计算日程总数

🎯 核心思路：分两步走，先选出哪几天是全天，再为剩下的半天安排时段。

万能公式:

总日程数 = C(总天数, 全天数) × 2^(半天数)

在 Numbas 中输入: comb(n, k1) * 2^k2

解题步骤：

识别题目参数：
- 总天数 (n): 公司每周工作的总天数
- 全天数 (k1): 员工需要工作的全天数量
- 半天数 (k2): 员工需要工作的半天数量
第一部分 (选日子)：从 n 天中选 k1 天作为全天 → C(n, k1)
第二部分 (排时段)：剩下的 k2 天是半天，每天有2种选择 → 2^k2
最终结果：comb(n, k1) × 2^k2

例子：n=7, k1=2, k2=5

计算：comb(7, 2) × 2^5 = 21 × 32 = 672

Part b) 鸽巢原理 - 相同日程的最少人数

万能公式 (向上取整):

ceil(员工总数 / 日程总数)

记忆口诀："人数除以选项数，结果向上取个整"

解题步骤：

识别参数：员工总数 (N)，日程总数 (k，来自Part a)
计算：N ÷ k
取整：如果是整数直接用；如果是小数，向上取整

例子：N=3972, k=672

计算：ceil(3972 ÷ 672) = ceil(5.91...) = 6

Part c) 保证特定人数有相同日程的最少员工数

万能公式 (逆向思考):

最少员工数 = (日程总数) × (目标人数 - 1) + 1

记忆口诀："选项数乘以(目标数减一)，最后再加一"

解题步骤：

识别参数：日程总数 (k)，目标人数 (m)
计算：k × (m - 1) + 1

例子：k=672, m=5

计算：672 × (5 - 1) + 1 = 672 × 4 + 1 = 2689

Part a) Counting all possible schedules

🎯 Key idea: break it into two phases—pick full-day slots, then assign morning/afternoon for part-days.

General formula

Total schedules = $C(\text{days}, \text{full-days}) \times 2^{\text{half-days}}$

Numbas entry: `comb(n, k1) * 2^k2`.

Step-by-step

Identify parameters.
- $n$: working days in the roster.
- $k_1$: number of full-day shifts required.
- $k_2$: number of half-day shifts required.
Select full days. Choose $k_1$ days out of $n$ → $C(n, k_1)$.
Assign half days. Each of the $k_2$ remaining days has two choices (AM or PM) → $2^{k_2}$.
Multiply. Final answer: `comb(n, k1) * 2^k2`.

Example. $n=7$, $k_1=2$, $k_2=5$.

Computation. $\text{comb}(7,2) \times 2^5 = 21 \times 32 = 672$.

Part b) Minimum people sharing a schedule

Ceiling rule

$\left\lceil \dfrac{\text{employees}}{\text{distinct schedules}} \right\rceil$

Think “people ÷ options, round up”.

How to apply

Gather inputs. Total employees $N$ and schedule count $k$ from Part (a).
Divide. Compute $N / k$.
Ceiling. Round up to the next integer if needed.

Example. $N=3972$, $k=672$.

Computation. $\lceil 3972 / 672 \rceil = \lceil 5.91… \rceil = 6$.

Part c) Guarantee $m$ people share a schedule

Reverse pigeonhole

Minimum employees $= \text{(schedule count)} \times (m-1) + 1$

Mnemonic: “options × (target−1), then add one”.

Worked example

Inputs. Schedule count $k$, target group size $m$.
Plug in. Compute $k \times (m - 1) + 1$.

Example. $k=672$, $m=5$.

Computation. $672 \times (5 - 1) + 1 = 672 \times 4 + 1 = 2689$.

5 分组计数问题Grouping & Counting

Part a & b) 选人投骰子

🎯 核心思路：将不同的人根据结果分组，遵循"先选人，再管剩下的人"原则。

解题模板:

总方式 = (选第一组人的方式) × (选第二组人的方式) × ... × (剩下的人的方式)

步骤详解：

第一组：从总人数中选出符合第一个条件的人 → C(总人数, 第一组人数)
第二组：从剩下的人数中选出符合第二个条件的人 → C(剩下人数, 第二组人数)
重复此步骤，直到所有"特殊"组都选完
处理"剩下的人"：
- 计算最终还剩多少人
- 由于"exactly(恰好)"限制，他们不能投出任何前面特殊组的结果
- 公式：(总选项数 - 已被占用的选项数)^(剩下的人数)

实战演练：

Part a) 8人投10面骰，恰好5人投出8：

选人投8：从8人中选5人 → C(8, 5)
剩下的人：剩下3人，不能投8，每人有9种选择 → 9^3
总数：C(8, 5) × 9^3

Part b) 45人投12面骰，分3组：

选5人投5：C(45, 5)
选6人投6：C(40, 6)
选10人投10：C(34, 10)
剩下24人不能投5,6,10，每人有9种选择：9^24
总数：C(45, 5) × C(40, 6) × C(34, 10) × 9^24

Part c) 带约束的数字计数

🎯 对于"小于某个数"的限制，必须使用分类讨论，从最高位开始分析。

解题模板:

明确限制：可用数字、位数、上限
按最高位分类：
- "安全" Case：最高位使数字必然小于上限
- "边界" Case：最高位与上限最高位相同，需继续细分
逐位细分边界Case
汇总：将所有不重叠的Case结果相加

实战演练 (小于4122，数字0-6)：

Case 1: 第一位是1,2,3 (安全) → 3 × 7^3
Case 2: 第一位是4 (边界)
- Sub-case 2a: 第二位是0 → 1 × 1 × 7 × 7
- Sub-case 2b: 第二位是1 (继续细分)

总数 = 各Case之和

Part a & b) Grouping dice outcomes

🎯 Strategy: partition players by the outcome they show—"pick the special groups first, then handle the rest".

Template

Total ways = choose group 1 × choose group 2 × … × handle leftovers.

Detailed workflow

First special group. Pick the people assigned to the first outcome → $C(\text{total}, k_1)$.
Second group. From those remaining, choose the next block → $C(\text{remaining}, k_2)$.
Repeat. Continue until all labelled outcomes are allocated.
Leftover players.
- Count how many people remain.
- Because the question says “exactly”, they must avoid the occupied faces.
- Formula: $(\text{faces} - \text{reserved faces})^{\text{remaining players}}$.

Practice examples

Part (a). Eight people roll a 10-sided die; exactly five show 8.

Choose who rolls 8 → $C(8,5)$.
Remaining three avoid 8 → $9^3$ options.
Total → $C(8,5) \times 9^3$.

Part (b). Forty-five people roll a 12-sided die; three outcomes are specified.

Pick five to show 5 → $C(45,5)$.
Pick six to show 6 → $C(40,6)$.
Pick ten to show 10 → $C(34,10)$.
Remaining 24 avoid 5,6,10 → $9^{24}$.
Multiply all factors for the final count.

Part c) Counting numbers with an upper bound

🎯 Rule: when “less than” appears, split cases by the highest digit.

Case-by-case recipe

List the constraints. Allowed digits, length, numerical cap.
Classify by the leading digit.
- Safe case: leading digit strictly below the cap.
- Boundary case: leading digit equals the cap → drill down.
Refine boundary cases digit by digit.
Add the disjoint counts.

Example (numbers < 4122 using digits 0–6)

Case 1. Leading digit 1,2,3 → $3 \times 7^3$.
Case 2. Leading digit 4 → inspect the next digit.
- 2a. Second digit 0 → remaining two spots free: $1 \times 1 \times 7 \times 7$.
- 2b. Second digit 1 → continue splitting by the third digit to stay below 4122.

Total count = sum of all disjoint cases.

6 整数方程解Integer Equation Solutions

⚠️ 重要提醒：在MATH1081的Numbas系统中，xᵢ ∈ ℕ 定义为 xᵢ ≥ 0 (非负整数)，而不是 xᵢ ≥ 1。

核心方程: x₁ + x₂ + x₃ + x₄ + x₅ + x₆ = 61，其中 xᵢ 为正整数 (xᵢ ≥ 1)

Part a) 下限问题：xᵢ ≥ 4 for all i

Numbas答案: comb(42, 5)

口诀："先给足，再平移，剩下随便分"

下限平移法：

变量代换：令 yᵢ = xᵢ - 4，则 yᵢ ≥ 0
平移方程：
- (y₁+4) + (y₂+4) + ... + (y₆+4) = 61
- y₁ + y₂ + ... + y₆ = 61 - 24 = 37
套用公式：C(37 + 6 - 1, 6 - 1) = C(42, 5)

Part b) 上限问题：xᵢ ≤ 27 for all i

Numbas答案: comb(60, 5) - comb(6, 1) * comb(33, 5) + comb(6, 2) * comb(6, 5)

口诀："总量减去坏的，再加上多减的"

上限容斥法：

计算总量：忽略上限，只考虑 xᵢ ≥ 1 → C(60, 5)
减去"至少一个坏"：至少一个 xᵢ ≥ 28 → C(6,1) × C(33,5)
加回"至少两个坏"：至少两个 xᵢ ≥ 28 → C(6,2) × C(6,5)
"三个或更多坏"：3×28=84>61，不可能

Part c) 复合限制：x₁ ≥ 15 and xᵢ ≡ i (mod 5)

Numbas答案: comb(12, 5)

口诀："按模改写，代入化简，解新方程"

模限制代换法：

按模改写：
- x₁=5k₁+1, x₂=5k₂+2, x₃=5k₃+3
- x₄=5k₄+4, x₅=5k₅+5, x₆=5k₆+1
代入原方程：5(Σkᵢ) + 16 = 61 → Σkᵢ = 9
附加限制：x₁ ≥ 15 → 5k₁+1 ≥ 15 → k₁ ≥ 3
再次平移：令j₁=k₁-3，得到 Σjᵢ = 6，所有jᵢ ≥ 0
最终答案：C(6+6-1, 6-1) = C(12, 5)

⚠️ Reminder: in the MATH1081 Numbas system, $x_i \in \mathbb{N}$ means $x_i \ge 0$, not $x_i \ge 1$.

Base equation

$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 61$ with each $x_i \ge 1$ unless stated otherwise.

Part a) Lower bounds $x_i \ge 4$

Numbas entry: `comb(42,5)`

Mantra: “top up first, shift, then distribute freely”.

Shift method

Substitute. Let $y_i = x_i - 4 \ge 0$.
Rewrite the sum. $(y_1+4)+\cdots+(y_6+4)=61$ → $\sum y_i = 37$.
Apply stars and bars. $C(37+6-1, 6-1) = C(42,5)$.

Part b) Upper bounds $x_i \le 27$

Numbas entry: `comb(60,5) - comb(6,1)comb(33,5) + comb(6,2)comb(6,5)`

Mantra: “total minus bad cases, plus the over-subtracted ones”.

Inclusion–exclusion

Total without caps. $C(60,5)$ for $x_i \ge 1$.
Subtract ≥1 violator. Choose the offending variable $C(6,1)$ and shift it: $C(33,5)$.
Add back ≥2 violators. $C(6,2) \times C(6,5)$.
Higher overlaps. Three variables ≥28 impossible because $3 \times 28 > 61$.

Part c) Mixed constraints $x_1 \ge 15$, $x_i \equiv i \pmod 5$

Numbas entry: `comb(12,5)`

Mantra: “rewrite by modulus, plug in, solve the transformed sum”.

Modular substitution

Express residues.
- $x_1 = 5k_1 + 1$, $x_2 = 5k_2 + 2$, $x_3 = 5k_3 + 3$
- $x_4 = 5k_4 + 4$, $x_5 = 5k_5 + 5$, $x_6 = 5k_6 + 1$
Substitute. $5\sum k_i + 16 = 61$ → $\sum k_i = 9$.
Apply the extra bound. $x_1 \ge 15$ → $k_1 \ge 3$.
Shift again. Let $j_1 = k_1 - 3$ so $\sum j_i = 6$ with $j_i \ge 0$.
Stars and bars. $C(6+6-1, 6-1) = C(12,5)$.

7 递推关系Recurrence Relations

核心公式: 通解 = 齐次解 + 特解 (General = Homogeneous + Particular)

第一步：求齐次解 aₙ⁽ʰ⁾

口诀："移项、立特征、解方程、定形态"

步骤：

标准形式：aₙ + c₁aₙ₋₁ + c₂aₙ₋₂ = 0
特征方程：r² + c₁r + c₂ = 0
解出特征根r，确定齐次解形态：

特征根情况	齐次解形态
两个不等实根 r₁, r₂	A × r₁ⁿ + B × r₂ⁿ
重复根 r	(A + Bn) × rⁿ

第二步：求特解 aₙ⁽ᵖ⁾

口诀："尾巴长啥样，我就猜啥样；一有撞车，立马乘n"

猜测规则：

"小尾巴"F(n)形式	初步猜测
一次多项式 (-36n-12)	Dn + E
指数函数 (-12×3ⁿ)	D × 3ⁿ

⚠️ 撞车检查 - 最关键的陷阱！

无撞车：直接使用初步猜测
一次撞车：初步猜测 × n
二次撞车：初步猜测 × n²

撞车示例：

例子1 (无撞车)：bₙ = -6bₙ₋₁ - 5bₙ₋₂ - 36n - 12

齐次解：A×(-1)ⁿ + B×(-5)ⁿ
猜测：Dn+E (无撞车，直接使用)

例子2 (一次撞车)：cₙ = -3cₙ₋₁ + 40cₙ₋₂ - 26×5ⁿ

齐次解：A×5ⁿ + B×(-8)ⁿ
初步猜测：D×5ⁿ (与A×5ⁿ撞车)
升级猜测：Dn×5ⁿ

第三步：合并通解并求解系数

最终步骤：

合并：aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾
代入初值：使用给定的初始条件建立方程组
求解：解出所有未知系数
最终答案：写出完整的递推关系解

示例：cₙ = (A + Bn - 6n²) × 3ⁿ

通过c₀=2, c₁=-6 可求出 A=2, B=2

最终答案：cₙ = (2 + 2n - 6n²) × 3ⁿ

Key identity: general solution = homogeneous part + particular part

Step 1 — Homogeneous solution $a_n^{(h)}$

Mnemonic: “rearrange → characteristic → solve roots → write the shape”.

Procedure

Standard form. Move everything to one side: $a_n + c_1 a_{n-1} + c_2 a_{n-2} = 0$.
Characteristic equation. $r^2 + c_1 r + c_2 = 0$.
Use the roots to write $a_n^{(h)}$.

Roots	Homogeneous form
Distinct reals $r_1, r_2$	$A r_1^n + B r_2^n$
Repeated root $r$	$(A + Bn) r^n$

Step 2 — Particular solution $a_n^{(p)}$

Mnemonic: “copy the forcing term’s shape; if it clashes, multiply by $n$”.

Guessing table

Forcing $F(n)$	Initial guess
Linear polynomial $-36n-12$	$Dn + E$
Exponential $-12 \cdot 3^n$	$D \cdot 3^n$

⚠️ Resonance check

No clash: keep the initial guess.
First clash: multiply by $n$.
Second clash: multiply by $n^2$.

Resonance examples

Example 1 (no clash). $b_n = -6 b_{n-1} - 5 b_{n-2} - 36n - 12$

Homogeneous: $A(-1)^n + B(-5)^n$.
Guess: $Dn + E$ fits immediately.

Example 2 (one clash). $c_n = -3 c_{n-1} + 40 c_{n-2} - 26\cdot 5^n$

Homogeneous: $A\cdot 5^n + B\cdot (-8)^n$.
Initial guess $D \cdot 5^n$ collides with $A\cdot5^n$.
Upgrade to $Dn \cdot 5^n$.

Step 3 — Combine and solve constants

Final wrap-up

Add. $a_n = a_n^{(h)} + a_n^{(p)}$.
Plug initial conditions. Form equations for $A, B, \dots$
Solve. Determine all unknown coefficients.
State the final formula.

Example. $c_n = (A + Bn - 6n^2) \cdot 3^n$.

Using $c_0 = 2$, $c_1 = -6$ gives $A = 2$, $B = 2$.

Final answer. $c_n = (2 + 2n - 6n^2) \cdot 3^n$.

MATH1081 Lab Test 2 Detailed NotesMATH1081 Lab Test 2 详细笔记

Logic simplification | Truth tables | Combinatorics逻辑表达式简化 | 真值表分析 | 组合数学应用

Question 1

Question 2

Question 3

Question 4-7

1 逻辑表达式简化与类型判定Simplify propositions & classify forms

基础操作口诀

1. ∧ (且/AND)

2. ∨ (或/OR)

3. ¬ (非/NOT)

4. → (蕴含/IMPLIES)

核心目标：判断表达式类型

重言式 (Tautology)

矛盾式 (Contradiction)

偶发式 (Contingency)

万能解题公式

公式工具箱

必须死记硬背的核心公式：

实战演练示例

例1：判断 $¬(¬p ∨ ¬q) ∧ ¬(p → q)$

例2：判断 $(¬p ∨ ¬q) → (p ∧ q)$

Core rules you must recall

Tautology

Contradiction

Contingency

Two-step decision recipe

Identity toolkit

Have these five patterns ready:

Worked examples

Example 1: $\neg(\neg p \lor \neg q) \land \neg(p \rightarrow q)$

Example 2: $(\neg p \lor \neg q) \rightarrow (p \land q)$

2 真值表分析与逻辑等价Truth tables & logical equivalence

示例真值表

Part a) 找出逻辑等价式

核心概念：

做题步骤 (口诀："找唯一假，再全验！")：

示例分析：

Part b) 逻辑操作三大类型详解

⚠️ 重要概念区分：

Question 2 速成笔记 (V3.0 最终版)

重点：求解"否定(Negation)"的标准公式

"三连招"：消灭箭头 → 德摩根 → 双重否定

解答本题 Part (b) - 完整实战演练

第一步：确定 Part (a) 的右侧命题

第二步：求 p → q 的否定 (Negation)

Sample truth table

Part (a) Locate the equivalent statement

Key ideas

Procedure (“spot the unique F, then confirm”)

Worked analysis

Part (b) Distinguish the three transformations

Important distinctions

Question 2 quick sheet (V3.0 final)

Highlight: negation’s three-move combo

Sequence: remove arrow → apply De Morgan → clear double negation

Full solution for Part (b)

Step 1. Confirm the right-hand statement in Part (a)

Step 2. Negate $p \rightarrow q$

3 组合数学综合应用Combinatorics applications

核心概念区分

组合 (Combination)

排列 (Permutation)

阶乘 (Factorial)

Part a) 剧团选角与角色分配

题目：19 人试镜，8 人入选。其中 6 人有命名角色。问有多少种情况？

Part b) 男女交替排列

题目：4 男 4 女排成一列，使男女交替排列。问有多少种方式？

Part c) 5 位数，所有数字不同且都是奇数

题目：有多少个 5 位数，满足所有数字都不同，并且所有数字都是奇数？

Part d) 元素相邻问题 - 捆绑法详解

题目：7个男生和3个女生排成一列，要求两个特定的学生必须相邻。有多少种排列方式？

解题方法："捆绑法"三步走

1 第一步：捆绑 (Bundle)

2 第二步：排外 (Arrange the Outside)

3 第三步：排内 (Arrange the Inside)

4 最后一步：相乘

Numbas 答案格式

【新】捆绑法通用公式表

高级应用技巧

Question 2 quick sheet (V3.0 final)

Sequence: remove arrow → apply De Morgan → clear double negation

Full solution for Part (b)

Step 1. Confirm the right-hand statement in Part (a)

Step 2. Negate $p \rightarrow q$

Numbas entry: `comb(60,5) - comb(6,1)comb(33,5) + comb(6,2)comb(6,5)`