- Basic Counting Rules: Union & Product
- Combinations and Permutations



# 基本计数规则 Basic Counting Rules

## 定义 Definition

### 并集规则 Union Rule 'or'

并集规则又称“或”规则。如果集合 $S$ 与集合 $T$ 是相交的，那么 $S$ 和 $T$ 的并集 $|S \cup T|$ 的元素个数等于 $|S| + |T|$。

### 乘积规则 Product Rule 'follow by'

乘积规则又称“后”规则。两个集合 $S$ 和 $T$ 的笛卡尔积 $S \times T$ 中的元素个数等于 $|S| · |T|$。

### 计数问题常见策略

1. 直接应用规则：这通常指的是直接使用已知的计数原理或公式来解决问题。

2. 将未知量与已知量关联：比如使用集合的基数（大小）的公式。例子中给出的是两个集合的并和交的基数关系，公式为 $|S| + |T| = |S ∪ T| + |S ∩ T|$。这可以帮助我们在知道其中一些集合的大小的情况下，计算其他集合的大小。

3. 找到一个可数集合的双射：双射是一种一一对应的关系，使得每个元素恰好对应一个元素，这可以帮助我们将复杂的计数问题转化为更容易计算的问题。例如，如果我们可以找到一个与已知集合大小相同的集合，并建立双射关系，那么就可以通过计算已知集合的大小来间接计算未知集合的大小。

## 并集规则 The Union Rule

当前有两个不相交的集合 $S$ 和 $T$，有：

$$
 |S ∪ T| = |S| + |T|
$$

那么，推广出去，如果有 $n$ 个两两不相交的集合$S_1, S_2, ... S_n$，

$$
|S_1 \cup S_2 ... \cup S_n| = \sum |S_i|
$$

### 推论

对于任意集合 $X, Y, Z$，

$$
|Y \backslash X| = |Y| - |X \cap Y| \\
|X \cup Y| = |X| + |Y| - |X \cap Y| \\
|X \cup Y \cup Z| = |X| + |Y| + |Z| - |X \cap Y| - |Y \cap Z| - |X \cap Z| + |X \cap Y \cap Z|
$$

### 基本事实

1. 如果两个集合的并集的基数等于两个集合基数的和，那么这两个集合是不相交的。
$$
|S ∪ T| = |S| + |T|
$$
2. 如果多个集合的并集的基数等于这些集合基数的总和，那么这些集合是两两不相交的。
$$
|\bigcup_{i=1}^nS_i| = \sum_{i=1}^n|S_i|
$$
3. 如果一个集合减去另一个集合的结果的基数等于原集合基数减去另一个集合基数的结果，那么第二个集合是第一个集合的子集。
$$
\text{if } |T \backslash S| = |T| - |S| \text{, then } S \subseteq T
$$

## 乘积规则 The Product Rule

如果要计算多个集合的笛卡尔积的基数，可以将每个集合的基数相乘。

$$
|S₁ × S₂ × ... × Sₖ| = |S₁| · |S₂| · ... · |Sₖ| = \prod_{i=1}^k|S_i|
$$

如果所有的集合 $Sᵢ$ 都等于某个集合 $S$，且集合 $S$ 的基数为 $m$，那么这些集合的笛卡尔积的基数将是 $m^k$。

$$
|S₁ × S₂ × ... × Sₖ| = |S × S × ... × S| = |S|ᵏ = mᵏ
$$

## 组合对称性 Combinatorial Symmetry

数学对象的对称性是指从对象到其自身的双射映射，这种映射保持了“结构”不变。

（组合）对称性定义了一个等价关系，其中等价类的大小都是相同的。

在计数时，我们通常对“直到对称性”为止的集合感兴趣。也就是说，我们关心的是等价类的数量。

这也可以表述为一种约束，它在每个等价类中识别出一个特定的项（对称约束 Symmectric Constraint）。

- k对1函数（k-to-1 function）是一种确切地将k个输入映射到一个输出的函数。
- k对1函数定义了组合对称性的等价关系，反之亦然。

组合对称性在解决计数问题时非常有用，特别是在存在可交换性或不可区分性时。通过对称性来分类，可以将问题简化，并只计数唯一的情况而不是所有可能的排列。

### 例子

- 给定集合 $Σ = \{a, b, c, d, e\}$，问有多少个五字母的单词可以构成，其中字母不重复，且字母a在b前面，在c前面？
- 从字母集合 $\{a, a, a, d, e\}$ 中，可以构成多少个五字母的单词？

这两个问题的答案将是相同的。

对于第一个问题，因为要求a在b前面且在c前面，所以b和c的相对位置可以是任意的，这使得问题与有多个相同字母a的情况等价，因为a的位置已经预设，所以剩下的d和e的位置也就自由了。两个问题都涉及到了不考虑某些元素的特定顺序的情况，而只计算独特的排列方式。

要解这两个问题，可以用5个位置中选取2个位置来放置d和e，剩下的位置自动由a填充。因此，答案是从5个不同位置中选择2个位置的组合数，即 $C_5^2$。


### 乘积规则在对称性的应用 Product rule: Symmetries and duplications

- S₁ 代表考虑了对称性的序列集合。
- S₂ 代表对称性本身的集合。
- S 代表没有考虑对称性的序列集合。

根据乘积规则，可以把不考虑对称性的序列集合S看作是考虑对称性的序列集合S₁与对称性集合S₂的笛卡尔积。

$$
S = S_1 \times S_2
$$

考虑对称性的序列集合的基数 |S₁| 可以通过将没有考虑对称性的序列集合的基数 |S| 除以对称性集合的基数 |S₂| 来计算。

$$
|S_1| = |S| / |S_2|
$$

换句话说，对称性约束意味着 |S| 序列中的 1/|S₂| 会满足对称性约束。这提供了一种计算在特定对称性约束下序列数量的方法。

![image.png](/static/img/0c7b12017a8588d287ddf4a09ab1ea17.image.webp)


# 组合与排列 Combinations and Permutations

## 组合对象 Combinatorial Objects

1. 排列（Permutations）：从集合S中选择所有对象的排序，等效于选择所有对象并且认可选择的顺序。

$$
n! = n(n-1)(n-2)...\times 2 \times 1 \\
0! = 1
$$

2. r-排列（r-permutations，不重复排列）：：从n个大小的集合S中选择任意r个对象，不重复选择，同时认可选择的顺序。这种选择的数量是 $(n)_r$，也表示为 $^nP_r$。

$$
^nP_r=n \times (n - 1) ... (n - r + 1) = \frac{n!}{(n-r)!}
$$

3. n个大小的集合S中选择任意r个不同的对象，不重复选择，同时不考虑选择的顺序。这种选择的数量用组合数表示，即$C_n^r$，或者也可以表示为 $(^n_r)$，这就是二项式系数。

$$
(^n_r) = \frac{n!}{r!(n-r)!}
$$

## 选择物品情景汇总 Selecting items summary

![image.png](/static/img/bc6d5b273182bf665aaf5b8284e8462a.image.webp)


## 把球放入盒子的问题 Balls in boxes

假设有n个可区分的盒子，有k个球，球可以是：

1. 不可区分的 (Indist.)
2. 可区分的 (Dist.)

问题是：

A. 每个盒子最多放一个球有多少种方法？(At most one)

B. 每个盒子可以放任意数量的球有多少种方法？(Any number of)

对于问题A和B，如果球是不可区分的，情况会有所不同，而如果球是可区分的，每个球可以看作是一个独立的个体。

对于问题A（每个盒子最多一个球），如果球是不可区分的，那么我们就是在计数从集合K到集合N的单射（injective）函数的数量。如果球是可区分的，这相当于计算所有可能的排列，因为我们不能有重复的球在同一个盒子里。

对于问题B（每个盒子可以有任意数量的球），如果球是不可区分的，这通常涉及到将球划分到盒子中，可能使用的是整数划分的方法。如果球是可区分的，那么我们就是在计数从集合K到集合N的所有可能的函数。

![image.png](/static/img/6bec373bbd5a43a2da6523ea0b9271f8.image.webp)

COMP9020-9-1 Combinatorics

- Propositional Logic, informally
- Propositional Logic, formally
- CNF and DNF Revisited
- Beyond Propositional Logic



# 命题逻辑 非正式 Propositional Logic, informally

## 命题定义 Definition

命题（或句子）是一种陈述句；其内容可以是真也可以是假。

## 逻辑连接词 Logical connectives

逻辑连接词用来将命题连接起来，构建更大的、复合的命题。

逻辑连接词包括"and"（和）、"or"（或）、"not"（不是）、"if...then..."（如果...那么...）等，用于建立逻辑上更复杂的陈述。通过逻辑连接词组合的命题的真假取决于它们所连接的各个简单命题的真假以及这些逻辑连接词本身所代表的意义。

![image.png](/static/img/7a09f3635b3d029e66b68d2430662207.image.webp)

## 复合命题 Compound propositions

复合命题的真理值取决于它的组成部分（原子命题）的真理值。

![image.png](/static/img/c1abdb1c4b83d284d7ad11fe550098cf.image.webp)



## 恒真式、矛盾和偶然性 Tautologies, Contradictions and Contingencies

- 一个命题如果永远为真，就是恒真式（tautology）。
- 一个命题如果永远为假，就是矛盾（contradiction）。
- 一个命题如果既不是恒真式也不是矛盾，就是偶然性（contingency）。
- 如果一个命题不是矛盾，它就是可满足的（satisfiable）。

恒真式是指无论在什么情况下都为真的命题。矛盾是指一个命题和它自身否定同时为真，这在逻辑上是不可能的，因此这样的命题永远是假的。偶然性是指一个命题在某些情况下为真，在其他情况下为假。可满足性指的是至少在一种情况下命题为真。

## 逻辑等价 Logical equivalence

如果两个命题对于其原子命题的相同真值都为真，那么这两个命题是逻辑等价的。逻辑等价意味着两个命题在逻辑上是不可区分的，它们要么同时为真，要么同时为假。在逻辑表达和推理中，逻辑等价的命题可以互换使用。


## 蕴涵与有效性 Entailment and Validity

一个论证由一组称为前提的命题和一个称为结论的陈述句组成。

前提：

- Frank took the Ford or the Toyota.（Frank开了福特或者丰田。）
- If Frank took the Ford he will be late.（如果Frank开了福特，他会迟到。）
- Frank is not late.（Frank没有迟到。）

结论：

- Frank took the Toyota.（Frank开了丰田。）


在这个例子中，结论是基于前提合理推导出来的。第一个前提提供了两种可能性，第二个前提提供了一种条件性的结果，第三个前提是一个事实陈述。结合这些前提，我们可以推导出结论，即Frank开了丰田。这个结论是有效的，因为它符合所有前提。

一个论证是有效的，如果结论在所有前提都为真的情况下为真。因此，如果我们相信前提，我们也应该相信结论。（注：当其中一个前提是假的时候我们不关心会发生什么。）

其他表达相同含义的说法：

- 结论逻辑上从前提中得出。（The conclusion logically follows from the premises.）
- 结论是前提的逻辑后果。（The conclusion is a logical consequence of the premises.）
- 前提蕴涵结论。（The premises entail the conclusion.）

有效性是逻辑推理中的关键概念，它确保了如果我们接受前提，那么由这些前提推理出的结论也应当被接受。这与前提的真实性无关；即使前提是假的，但如果逻辑结构是正确的，那么论证就是有效的。**在逻辑分析中，我们只关注论证的形式结构，而不是前提的实际内容。**

# 命题逻辑 正式 Propositional Logic, formally

## 语法与语义 Syntax vs Semantics

逻辑正式定义的第一步是区分语法和语义。语法是指事物如何被书写，即定义了一个公式。语义是指事物的含义，即一个公式为何为“真”。

## 语法：合成公式 Syntax: Well-formed formulas

有命题集合：$PROP=\{p, q, r...\}$

考虑字母表：

$$
\Sigma=PROP \cup \{⊤, ⊥, ¬, ∧, ∨, →, ↔,(,) \}
$$

⊤代表"真"（tautology），在任何可能的情况下都是真的。

⊥代表"假"（contradiction），在任何可能的情况下都是假的。

PROP 上的合式公式（wffs）是 Σ 上的最小字集，满足以下条件：
- ⊤, ⊥ 以及 PROP 的所有元素都是 wffs。
- 如果 $φ$ 是一个 wff，那么 $¬φ$ 也是一个 wff。
- 如果 $φ$ 和 $ψ$ 都是 wffs，那么 $(φ ∧ ψ)$, $(φ ∨ ψ)$, $(φ → ψ)$, 和 $(φ ↔ ψ)$ 也都是 wffs。

![image.png](/static/img/0e4a2a3a01dbe4c78f6bdcfc4936af8c.image.webp)


## 语法：约定 Syntax: Conventions

为了帮助提高可读性，一些约定和绑定规则将被使用：

- 如果没有歧义，可以省略括号（例如 p ∧ q）。
- ¬ 比 ∧ 和 ∨ 绑定得更紧密，而 ∧ 和 ∨ 比 $→$ 和 $↔$ 绑定得更紧密（例如 p ∧ q → r 代替 ((p ∧ q) → r)）。
- ∧ 和 ∨ 默认向左结合（例如 p ∨ q ∨ r 代替 ((p ∨ q) ∨ r)）。

其他在本门课中中很少使用或假定的约定：

- ′ 或 : 代替 ¬。
- + 代替 ∨。
- . 或紧邻代替 ∧。
- ∧ 比 ∨ 绑定得更紧密。
- $→$ 和 $↔$ 默认向右结合（例如 p → q → r 代替 (p → (q → r))）。

## 语法：解析树 Syntax: Parse trees

合式公式（以及其他由语法定义的句法结构）的结构可以用解析树来展示。


![image.png](/static/img/62ddf4cc9e49232cf59b2697d2723844.image.webp)

形式化地，我们可以按照以下方式定义解析树：
一个解析树可以是：

- （B）一个包含 ⊤ 的节点；
- （B）一个包含 ⊥ 的节点；
- （B）一个包含命题变量的节点；
- （R）一个包含 ¬ 和单个解析树子节点的节点；
- （R）一个包含 ∧ 和两个解析树子节点的节点；
- （R）一个包含 ∨ 和两个解析树子节点的节点；
- （R）一个包含 → 和两个解析树子节点的节点；
- （R）一个包含 $↔$ 和两个解析树子节点的节点。

这里的（B）代表基本情况，而（R）代表递归规则。基本情况意味着一个节点可以直接表示一个命题逻辑的常量或变量，而递归规则意味着可以从一个或两个子节点构建更复杂的逻辑结构。解析树的每个节点都对应一个逻辑运算符或操作数，树的结构显示了复合命题中不同部分之间的关系。

## 语义：布尔代数 Semantics: Boolean Algebras

回顾两元素布尔代数 𝔹 = {true, false} = {⊤, ⊥} = {1, 0}，以及操作 !, &&, ||。

定义派生布尔函数 $⇝$ 和 $↭$：
$$
x ⇝ y = (!x) || y = max\{1 - x, y\} \\

x ↭ y = (x ⇝ y) \&\& (y ⇝ x) = (1 + x + y) \% 2
$$

## 语义：真值赋值 Semantics: Truth valuations

真值赋值（也称为真值评价）是一个函数 $v:Prop→B$.

我们可以按照如下方式将真值赋值 v 扩展到所有命题逻辑的合式公式 (wffs)：


![image.png](/static/img/9377f9369a9534637dd311d181e2f61f.image.webp)

![image.png](/static/img/dd5e6a1111a6b97fa28612dcb520c705.image.webp)


## 语义：真值表 Semantics: Truth tables

每个真值赋值 —— 即为 Prop 的元素赋予 T/F —— 都对应一行。每个子公式对应一列。

![image.png](/static/img/d7ed70db7025301892bf34c994f62804.image.webp)

## 可满足性，有效性，等价性 Satisfiability, Validity and Equivalence

一个公式 φ：

- 如果存在某个真值赋值 v 使得 v(φ) = true，则称 φ 是可满足的（φ satisfies v）。
- 如果对所有的真值赋值 v，v(φ) = true，则称 φ 是一个重言式（tautology）。或者也可以说是个恒等式。
- 如果对所有的真值赋值 v，v(φ) = false，则称 φ 是不可满足的（unsatisfiable），或者说是一个矛盾（contradiction）。

## 逻辑等价 Logical equivalence

两个公式 φ 和 ψ 被认为是逻辑等价的，记为 φ ≡ ψ，如果对所有真值赋值 v，v(φ) = v(ψ)。

![image.png](/static/img/fee90edbf59ca0e2e9ab4c73396fc155.image.webp)

![image.png](/static/img/5046cc43f2a647a9fb7a6e8a8e0da65a.image.webp)

![image.png](/static/img/e5274122c0385f5e8daac1d5fc5fab7b.image.webp)

## 理论和蕴含 Theories and entailment

一组公式（Formula）的集合被称为理论（Theory）。

如果一个真值赋值$v(t) = true$ 对所有的 $t \in T$ 都成立，我们说这个真值赋值v满足理论T。

如果一个公式 $φ$ 使得 $v(φ) = true$ 对于所有的满足T的真值赋值v都成立，那么我们说理论T蕴含一个公式 $φ$ ，记作 $T⊨φ$。

COMP9020-8-2 Propositional Logic

- Boolean Logic
- Boolean Functions
- Conjunctive and Disjunctive Normal Form
- Karnaugh Maps
- Boolean Algebras



# 布尔逻辑

布尔逻辑是关于在一个“简单”的数学结构中进行计算。
- 复杂计算可以完全由这些简单的计算构建
- 可以帮助识别简化措施，这些简化措施可以在电路级别提高性能
- 可以帮助识别简化措施，这些简化措施可以在编程级别提高表现

## 布尔代数

（两元素）布尔代数被定义为：

集合： B = {0,1}

函数：

- !: B → B
- &&: B² → B
- ||: B² → B 

如下所定义：

- !x = (1 - x)
- x && y = min{x, y}
- x || y = max{x, y}

![image.png](/static/img/59196e44cb564d7de26bdba80fcf2b86.image.webp)

# 布尔函数 Boolean Function

## 定义 Definition

一个n元的布尔函数是一个映射：

$$
f: B^n \rightarrow B
$$

一个布尔函数只能输出1位的0或1（F/T）。

![image.png](/static/img/6ddd853c89f500e17238f296e87bf4bf.image.webp)


# 联结和析取范式 Conjunctive and Disjunctive normal form

- 文字（literal）是一个一元布尔函数。
    - 这是最基本的概念。一个文字就是一个变量或者它的否定。比如，x 和 ¬x（或写作 !x）都是文字。
- 最小项（minterm）和最大项（maxterm）：
    - 最小项是所有变量的AND（与）操作，这些变量可能是原始的，也可能是它们的否定。比如，对于两个变量 x 和 y，x AND ¬y 是一个最小项。
    - 最大项是所有变量的OR（或）操作，这些变量可能是原始的，也可能是它们的否定。比如，x OR ¬y 是一个最大项。
    - 每个最小项在变量取特定值时只有一个输出为真（1），其他都为假（0）；每个最大项在变量取特定值时只有一个输出为假（0），其他都为真（1）。
- 合取范式（CNF, Conjunctive Normal Form）:
    - 合取范式是一个布尔函数的表示方法，它是由一个或多个最大项组成的AND操作。例如，(x OR y) AND (¬x OR ¬y) 是一个合取范式，因为它是两个最大项 x OR y 和 ¬x OR ¬y 的AND操作。
- 析取范式（DNF, Disjunctive Normal Form）:
    - 析取范式也是一个布尔函数的表示方法，它是由一个或多个最小项组成的OR操作。例如，(x AND ¬y) OR (¬x AND y) 是一个析取范式，因为它是两个最小项 x AND ¬y 和 ¬x AND y 的OR操作。

简单来说，合取范式像是多个逻辑或表达式的集合，这些表达式被与在一起；析取范式像是多个逻辑与表达式的集合，这些表达式被或在一起。在布尔逻辑中，任何复杂的表达式都可以用这两种范式之一来表示。



:::note{title="注"}
![image.png](/static/img/545e9f0bf16b40e1908e7c34e6c6c939.image.webp)

由于 (x && (!y) && z) 本身是AND的集合体（即最小项），所以它可以视为一个仅有一个最小项组成的OR操作的析取范式；

每一个文字，都可以视作仅有一个元素的最小项/最大项，所以(x && (!y) && z)可以看作三个仅有一个元素的最大项的AND操作，即合取范式。

因此，(x && (!y) && z)既是析取范式，又是合取范式。
:::

> 每一个布尔函数都可以写成DNF和CNF的形式。


## 标准析取范式 Canonical DNF

定义最小项（Minterm）：给定一个n元布尔函数 $f: Bⁿ → B$，其中 $B$ 是布尔代数的集合 $\{0, 1\}$。对于 $Bⁿ$ 中的每个元素 $b = (b₁, ..., bₙ)$，定义一个最小项 $m_b$。这个 $m_b$ 是几个 $lᵢ(xᵢ)$ 的 AND 运算的结果。每个 $lᵢ(xᵢ)$ 要么是变量 $xᵢ$，要么是它的否定 $!xᵢ$（或 $¬xᵢ$），这取决于 $b$ 中对应的元素 $bᵢ$。如果 $bᵢ$ 是 1，那么 $lᵢ(xᵢ)$ 就是 $xᵢ$；如果 $bᵢ$ 是 0，那么 $lᵢ(xᵢ)$ 就是 $!xᵢ$。

构造DNF公式：对于函数 $f$ 对每个可能的输入 $b$ 产生输出 1 的情况，找出所有对应的最小项 $m_b$。然后，将这些最小项通过 OR 运算（析取）组合起来，形成函数 $f$ 的析取范式公式 $f_DNF$。符号 $∑$ 表示对所有使得 $f(b) = 1$ 的 $b$ 对应的最小项 $m_b$ 进行 OR 运算。

![image.png](/static/img/69480731fe4ca7e2dbf4c6d41bd2cb35.image.webp)


:::note{title="注"}
考虑所有可能的输入组合：比如对于两个输入的函数，可能的输入组合有 (0,0), (0,1), (1,0), (1,1)。

找出函数输出为1的所有输入组合：这就是说，我们要找到函数 f 返回1的所有可能情况。

为每个输出为1的情况创建一个最小项：一个最小项是一串用AND连接的输入，如果输入是1我们就直接写下它，如果是0我们就写它的否定形式（比如 !x 或 ¬x）。例如，如果 x=1, y=0 时函数输出为1，那么对应的最小项就是 x AND !y。

将所有这些最小项用OR连接起来：这样做就创建了一个表达式，它精确地描述了函数 f 何时会输出1。如果我们有多个最小项，我们就把它们用OR（||）连接起来，表示这个函数在这些最小项对应的输入情况下都会输出1。
:::

![image.png](/static/img/3af7d28b5291d823408157f34493002e.image.webp)


# 卡诺图 Karnaugh Maps

制作卡诺图: 根据你的变量个数，画出一个表格。比如两个变量就画2x2的表格，三个变量就画2x4的表格，四个变量则是4x4的表格。

标记变量：表格的行和列要代表所有变量可能的状态组合，这些状态要按格雷码顺序排列，也就是说，每次只变化一个变量的状态。（例：00 - 01 - 11 - 10）

找规律：找出那些可以合并的标记的格子。合并的原则是形成尽可能大的矩形区域，且每个矩形里的单元格数必须是2的幂次个（1, 2, 4...）。这些矩形代表了函数的简化形式。

写出表达式：每一个矩形都对应一个表达式的部分，你只需查看未改变的变量，将它们连接起来。如果变量在矩形中的所有单元格中都是1，就直接写这个变量；如果都是0，就写它的否定形式。如果变量在矩形内的状态既有0也有1，就忽略这个变量。

合并表达式：最后，将所有找到的矩形对应的表达式用OR连接起来，这就是简化后的布尔表达式。

![image.png](/static/img/72bfa852734e0b0eb2a78c71b219e13f.image.webp)


![image.png](/static/img/6be71e387ef623643d20374cd364318e.image.webp)


# 布尔代数 Boolean Algebra

## 性质

交换律（Commutativity）：

- $x ∨ y = y ∨ x$
- $x ∧ y = y ∧ x$

结合律（Associativity）：

- $(x ∨ y) ∨ z = x ∨ (y ∨ z)$
- $(x ∧ y) ∧ z = x ∧ (y ∧ z)$

分配律（Distributivity）：

- $x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)$
- $x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)$

同一律（Identity）：

- $x ∨ 0 = x$
- $x ∧ 1 = x$

补足律（Complementation）：

- $x ∨ x′ = 1$
- $x ∧ x′ = 0$

![image.png](/static/img/9c06b16f845c10eaaf7a096b1fea24fb.image.webp)


![image.png](/static/img/8af710f92be0eb1c742c48bdf6b8797c.image.webp)



![image.png](/static/img/218e3472bdc336ff0d30edc016610724.image.webp)


![image.png](/static/img/337225a01daaccca77ca4bd97d3a9d5d.image.webp)


## 对偶性 Duality

对偶性定义:
如果 $E$ 是用变量（比如 $x,y,z$）和常数（0 和 1）以及布尔代数操作（∧ 表示与，∨ 表示或，′ 表示非）定义的表达式，那么 $E$ 的对偶表达式 $dual(E)$ 就是通过将所有的 ∧ 替换为 ∨，将所有的 ∨ 替换为 ∧，将所有的 0 替换为 1，将所有的 1 替换为 0 得到的。

布尔代数的对偶:
如果有一个布尔代数 $(T,∧,∨,′,0,1)$，它的对偶布尔代数是 $(T,∨,∧,′,1,0)$。这里只是交换了与（∧）和或（∨）操作，以及常数 0 和 1 的位置。

对偶性原理定理:
如果你能通过布尔代数的定律证明 $E1=E2$，那么 $dual(E1)=dual(E2)$ 也成立。这个原理告诉我们，一个布尔等式的对偶等式也是成立的。

COMP9020 8.1 Boolean logic

Test started Mar 13, 2024 6:00 PMtoMar 27, 2024 6:00 PM



## 1.1

### Question


Suppose $f:S→S$ and $g:S→S$ are bijections.

Which of the following are true for all such functions?

Select all that apply


- $(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (f^{-1})∘(g^{-1})$
- $(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (g^{-1})∘(f^{-1})$
- $(f;g)^←$ always exists and $(f;g)^← = (f^←);(g^←)$
- $(f;g)^←$ always exists and $(f;g)^← = (g^←);(f^←)$
- None of the above

### Answer

因为是双射，所以反函数一直存在，逆关系一直存在。

令： $(b,c) \in f, (a,b) \in g$

则有：
$$
(a,c) \in f \circ g \\

(b,a) \in g^{-1} \\
(c,b) \in f^{-1} \\

(c,a) \in (f \circ g)^{-1} \\
(c,a) \in g^{-1} \circ f^{-1}

$$

因此，答案为：

- $(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (g^{-1})∘(f^{-1})$
- $(f;g)^←$ always exists and $(f;g)^← = (g^←);(f^←)$


## 1.2

### Question

$$
A = 
\begin{pmatrix}
3 & 1 \\
4 & 1
\end{pmatrix}
$$

Which of the following matrices is $AA - 2A^T$?

### Answer

$$
AA = 
\begin{pmatrix}
3*3 + 1*4 & 3*1 + 1*1 \\
4*3 + 1*4 & 4*1 + 1*1
\end{pmatrix}
=
\begin{pmatrix}
13 & 4 \\
16 & 5
\end{pmatrix}
$$

$$
2A^T = 
\begin{pmatrix}
6 & 8 \\
2 & 2
\end{pmatrix}
$$

因此，答案为：

$$
\begin{pmatrix}
7 & -4 \\
14 & 3
\end{pmatrix}
$$

## 1.3

### Question

Suppose $T(n)$ is defined recursively as:

- $T(0) = 1$
- $T(n) = 3T(n/3) + O(n)$

True or false: $T(n) ∈ O(n)$

### Answer

这里使用主定理。

首先将该式子化成一个简单些的式子：

$$
T(n) = 3T(n/3) + cn
$$

之后，我们可以假设 $n = 3^k$，以此简化操作：

$$
\begin{align*}
    T(n) &= 3(3T(n/9)+cn/3)+cn \\
         &= 9T(n/9) + 2cn \\
         &= 9(3T(n/27)+cn/9)+2cn \\
         &= 27T(n/27)+3cn \\
         &= ... \\
         &=3^kT(1)+kcn \\
         &=n + cnlog_n \\
         &\in O(nlogn)
\end{align*}
$$

因此，答案为：False

## 1.4

### Question

Suppose $f,g:{a,b}^*→{a,b}^*$ are defined recursively as follows:

- $f(λ)=a$
- $g(λ)=b$
- $f(aw) = f(w)g(w)$
- $f(bw) = g(w)f(w)$
- $g(aw)=g(bw)=f(w)$

What is f(bba)?

### Answer

$$
\begin{align*}
    f(bba) &= g(ba)f(ba) \\
           &= f(a)g(a)f(a)
\end{align*}
$$

$$
\begin{align*}
    f(a) &= f(aλ) \\
         &= f(λ)g(λ) \\
         &= ab
\end{align*}
$$

$$
\begin{align*}
    g(a) &= g(aλ) \\
         &= f(λ) \\
         &= a
\end{align*}
$$

$$
f(bba) = f(a)g(a)f(a) = abaab
$$

因此，答案为：abaab

## 1.5

Consider the following code snippet:

```
myFunc(n):
    if n==0:
        return 1
    else:
        return myFunc(n-1) + myFunc(n-1)
```
Which of the following hold with regard to the running time T(n) of this code

Select all that apply

- $T(n) ∈ O(n^2)$
- $T(n) ∈ O(n)$
- $T(n) ∈ O(log n)$
- $T(n) ∈ O(2^n)$
- None of these options

### Answer

假设：`myFunc(n)` 的用时是 $T(n)$，则 `myFunc(n-1)` 的用时是 `T(n-1)` 。

因为return中调用了两次，**所以时间也要计算两倍**！具体可对比1.6。

$$
\begin{align*}
    T(n) &= 2T(n-1) + O(1) \\
         &= 4T(n-2) + 3 \cdot O(1)\\
         &= ... \\
         &= 2^nT(n-n) + \frac{(1+n)n}{2} \cdot O(1) \\
         &= 2^n + \frac{n^2+n}{2} \cdot O(1)\\
         &\in O(2^n)
\end{align*}
$$

因此，答案为：
- $T(n) ∈ O(2^n)$

## 1.6

Consider the following code snippet:

```
myFunc(n):
    if n==0:
        return 1
    else:
        return 2 * myFunc(n-1)
```
Which of the following hold with regard to the running time T(n) of this code

Select all that apply

- $T(n) ∈ O(n^2)$
- $T(n) ∈ O(n)$
- $T(n) ∈ O(log n)$
- $T(n) ∈ O(2^n)$
- None of these options

### Answer

假设：`myFunc(n)` 的用时是 $T(n)$，则 `myFunc(n-1)` 的用时是 `T(n-1)` 。

$$
\begin{align*}
    T(n) &= T(n-1) + O(1) \\
         &= T(n-2) + 2 \cdot O(1) \\
         &= ... \\
         &= T(0) + n \cdot O(1) \\
         &= n \cdot O(1) \\
         &\in O(n)
\end{align*}
$$

因此，答案为：

- $T(n) ∈ O(n)$

## 1.7

### Question


Recall the definition of a valid expression for the proof checker:

- ∅ and U are valid expressions
- Any single letter A-Z or a-z is a valid expression
- If E is a valid expression, then:
    - (E) is a valid expression
    - Eᶜ is a valid expression
- If E₁ and E₂ are valid expressions, then:
    - (E₁ ∩ E₂) is a valid expression
    - (E₁ ∪ E₂) is a valid expression
    - (E₁ \ E₂) is a valid expression
    - (E₁ ⊕ E₂) is a valid expression

Based on the above definition, which of the following are valid expressions?

Select all that apply:

- $Aᶜᶜᶜ$
- $(((U \backslash ∅) \backslash U) \backslash ∅)$
- $((A ∩ B) ∪ (C ∩ (D)))$
- $((A ∪ a) ∩ (B ∪ b) ∩ (C ∪ c))ᶜ$
- $((A1 ⊕ A2)ᶜ)ᶜ$
- $((A ∩ B))$

### Answer

- 选项1
    
    根据规则，一个单字母是有效的表达式。如果 E 是有效表达式，则 Eᶜ 也是有效表达式。因此，对一个单字母连续进行三次补集操作是有效的。
- 选项2
    
    根据规则，∅ 和 𝓤 是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ \ E₂) 也是有效表达式。因此，从 𝓤 中减去 ∅，然后再进行两次相似的操作是有效的。
- 选项3
    
    根据规则，单个字母是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ ∩ E₂) 和 (E₁ ∪ E₂) 也是有效表达式。因此，这个表达式有效。
- 选项4
    
    单字母是有效表达式，(E₁ ∪ E₂) 和 (E₁ ∩ E₂) 也是有效表达式。如果 E 是有效表达式，则 Eᶜ 也是有效表达式。因此，这个表达式有效。
- 选项5
    
    A1和A2不是有效表达式，因此它们的组合也不应该是。
- 选项6
    
    根据规则，单字母是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ ∩ E₂) 也是有效表达式。果 E 是有效表达式，则 (E) 也是有效表达式。因此，这个表达式有效。

因此，答案为：

- $Aᶜᶜᶜ$
- $(((U \backslash ∅) \backslash U) \backslash ∅)$
- $((A ∩ B) ∪ (C ∩ (D)))$
- $((A ∪ a) ∩ (B ∪ b) ∩ (C ∪ c))ᶜ$
- $((A ∩ B))$

## 2.1

### Question

Suppose T(n) is defined recursively as:

- $T(0) = 1$
- $T(n) = 3T(n-3) + O(n)$

True or false: $T(n) ∈ O(2^n)$

### Answer

这里使用主定理。

我们可以假设 $n = 3i$，首先将该式子化成一个简单些的式子：

$$
\begin{align*}
    T(n) &= 3T(n-3) + c_1 \cdot n \\
    T(n-3) &= 3T(n-6) + c_1 \cdot (n-3) \\
    & ... \\
    T(3) &= 3T(0) + c_1 \cdot 3
\end{align*}
$$

我们看到每次递归成本减少 $n$ 的三分之一，但是成本的系数会翻三倍。

$$
\begin{align*}
    T(n) &= 3^iT(0) + c_1 \cdot (n+(n-3) + (n-6) + ... +3 + 0) \\
         &= 3^{\frac{n}{3}} + c_1 \cdot (\frac{n \cdot n}{3} - 3 \cdot (1 + \frac{n}{3}) \cdot \frac{n}{3 \cdot 2}) \\
         &\in O(3^{\frac{n}{3}})
\end{align*}
$$

$3^{\frac{n}{3}}$ 是一个指数函数，但是它要比 $2^n$ 慢很多。

因此，答案为：False

## 2.2

### Question

Consider the following code fragment that works on an array:

```
myFunc(A, lo, hi):
    if lo + 1 >= hi:
        return
    
    j = (lo + hi) / 2
    if A[lo] < A[hi]:            
        myFunc(A, lo, j)
        myFunc(A, j, hi)
    else:
        myFunc(A, j, hi)
        myFunc(A, lo, j)
 
    for i ∈ [lo, hi):
        print(A[i])
```
In terms of n = hi - lo, which of the following hold for the running time T(n) of this code?

- $T(n) ∈ O(n log n)$
- $T(n) ∈ O(2^n)$
- $T(n) ∈ O(1)$
- $T(n) ∈ O(n²)$
- $T(n) ∈ O(n)$
- $T(n) ∈ O(log n)$

### Answer

在递归部分，每次都会把区间分为两部分进行两次递归调用，所以递归树的每一层都有两倍于上一层的调用次数，这种行为在二叉树中是常见的。递归的深度是 O(log n)，因为每次调用都将问题的规模减半。

递归调用中的分支因素是2（因为最坏情况下，两次递归都会执行），但在每层递归中，对区间的打印操作是线性的。这意味着，即使递归深度是 O(log n)，但是每一层递归都要执行 O(n) 的打印操作。所以我们需要将这两者结合起来，得到整体的复杂度。

所以整体复杂度是每层 O(n) 的打印操作乘以 O(log n) 层的递归深度，即 T(n) ∈ O(n log n)。

所以正确的选项是：

- $T(n) ∈ O(n log n)$

## 2.3

### Question

Consider a subset, EXP, of valid expressions (see Question 1.7), defined recursively as follows:

- ∅ and U are elements of EXP
- X,Y,Z ∈ EXP
- If E ∈ EXP, then:
    - (E) ∈ EXP
    - Eᶜ ∈ EXP
- If E₁, E₂ ∈ EXP, then:
    - (E₁ ∩ E₂) ∈ EXP
    - (E₁ ∪ E₂) ∈ EXP

Consider dual: EXP → EXP defined recursively as follows:

- dual(∅) = U
- dual(U) = ∅
- dual(X) = X, dual(Y) = Y, dual(Z) = Z
- If E ∈ EXP, then
    - dual( (E) ) = ( dual(E) )
    - dual( Eᶜ ) = dual(E) ᶜ
- If E₁, E₂ ∈ EXP, then
    - dual( (E₁ ∩ E₂) ) = ( dual(E₁) ∪ dual(E₂) )
    - dual( (E₁ ∪ E₂) ) = ( dual(E₁) ∩ dual(E₂) )
 
What is $dual(((X ∩ Yᶜ) ∪ U))$?

- $((Xᶜ ∩ Y) ∪ ∅)$
- $∅$
- $((X ∪ Yᶜ) ∩ ∅)$
- $((Xᶜ ∪ Y) ∩ ∅)$
- None of the above

### Answer

首先，根据dual( (E) ) = ( dual(E) )，我们将内部最外层的括号提取到外部最外层：

$$
dual(((X ∩ Yᶜ) \cup U)) = (dual((X \cap Y^C) \cup U))
$$

这样，我们提取括号内的dual，相当于变相去除了一层括号。

根据dual( (E₁ ∪ E₂) ) = ( dual(E₁) ∩ dual(E₂) )，我们把两部分分开：

$$
dual((X \cap Y^C) \cup U) = dual((X \cap Y^C)) \cap dual(U)
$$

对于 $dual((X \cap Y^C))$，可以单拎出来继续拆分：

$$
\begin{align*}
    dual((X \cap Y^C)) &= (dual(X) \cap Y^C)) \\
                       &= (dual(X) \cup dual(Y^C)) \\
                       &= (dual(X) \cup dual(Y)^C) \\
                       &= (X \cup Y^C)
\end{align*}
$$

且：dual(U) = ∅

因此答案为：

- $((X \cup Y^C) \cap \empty)$

COMP9020 Quiz 5

- Motivation
- Standard Approach
- Examples
- Simplifying with Worst Case and Big-O
- Recursive Examples



# 动机 Motivation

算法分析的目的是为了量化和评价算法在处理大量数据时的性能，以便在不同算法之间做出合理选择。通过将算法资源需求表述为输入大小的函数，我们可以更好地理解和预测算法在实际应用中的表现。我们希望比较不同的算法，尤其是那些能够解决任意大规模实例的算法。

# 标准处理流程 Standard Approach

渐近分析：关注的是随着输入规模增加，成本（如运行时间、内存等）如何增长。

标准（默认）方法包括：

- 考虑成本函数的渐近增长。
- 考虑最坏情况（成本最高）的输入。
- 考虑运行时间成本，即基本操作的数量。

还有其他方法，例如：
- 情况分析：考虑算法在所有可能输入上的平均性能。
- 空间（内存）成本：评估算法在运行过程中所需的内存空间。

这些分析方法提供了不同的视角来评估算法的效率，帮助我们了解在不同情况下算法可能的表现。

基本操作被非正式地定义为一个计算步骤，它在计算过程中占用固定数量的计算周期。
一些基本操作的例子包括：

- 算术运算（如加、减、乘、除）
- 两个值的比较
- 赋值操作，即将一个值赋给一个变量
- 访问数组元素
- 调用一个函数
- 返回一个值
- 打印一个字符

在进行算法分析时，应将操作计数为常数因子，$O(1)$，而不是精确数字。这意味着在分析算法的复杂度时，我们不关心具体执行了多少次基本操作，而是关注基本操作的总体趋势。




# 例子 Examples

## 运行时间 vs 执行时间 Running time vs Execution time

- 运行时间是对算法执行时间的一种估计，它基于简化的假设，比如忽略基本操作的具体耗时。
- 在大O记号中通常会隐藏常数因子，这意味着我们关注的是算法性能的增长趋势，而非确切的执行时间。
- 大O记号着重于当输入规模 $n$ 变得非常大时的性能限制。

例如：

一个计算平方的实现，即下文中的 `square(n)`，随着 $n$ 的增大其运行时间会变长。

一个“解决棋类问题”的程序可能会在 $O(1)$ 时间内运行，这意味着不论棋盘的大小，它的解决时间都被认为是常数。这可能指的是对于一个确定的棋局，如固定的开局或结束局面，程序能够立即给出解决方案。

## 具体示例

![image.png](/static/img/9758185f871306b4bf8d5bb32ec6d9ef.image.webp)

![image.png](/static/img/6a960a451552f53408661dd13b9db80e.image.webp)

![image.png](/static/img/aaac1756f0193ecffb96e2406c32dd7c.image.webp)

# 使用最坏情况估计和大O进行问题简化 Simplifying with Worst Case and Big-O

## 最坏情况估计

在本例中，直接使用 $n$ 替换 $i$。

![image.png](/static/img/d576976c80df3b43e2ebbc8a65aecd64.image.webp)

![image.png](/static/img/dbc352c9855da1533dca754078c1fe3e.image.webp)

## 使用大O简化问题

在本例中，没有固定的循环执行的次数，只知道该次数为在0-n中间，即 $O(n)$，那么直接使用 $O(n)$ 替换：

![image.png](/static/img/0efe3ec623bca51194a72b9f275e7867.image.webp)

## 其他方式

最坏情况假设和大O记号的结合可以简化分析，但这种简化可能会导致非最优的界限。为了得到最好的界限，可能需要进行更细粒度的上界分析，或者分析特定情况以找到匹配的下界（大Omega记号）。

大Omega记号用于分析最坏情况的下界，它不是最佳情况分析。也就是说，当我们说某算法的性能是大Omega记号的某个函数时，我们是在说即使在最坏的输入情况下，算法的性能也至少有这么好。

![image.png](/static/img/085297d229c4168e5e59924b4c9af703.image.webp)


# 递归例子 Recursive examples

## 例子 1

![image.png](/static/img/a828d170372aa845aaf60c601c369384.image.webp)

可以假设对于 `fact(n)` 来说，所需要的时间为 $T(n)$，那么：

![image.png](/static/img/e4a942519f84552d75bf14756a7abd93.image.webp)

## 例子 2

![image.png](/static/img/329b4a4808a153a515898532b5d3c380.image.webp)

## 例子 3

![image.png](/static/img/efa7fd46e9f3fc2e9d1e7be734fce87e.image.webp)

## 例子 4

![image.png](/static/img/bd99246c59848952cb7be52d798a05c8.image.webp)