- Elementary Discrete Probability
- Independence
- Infinite Sample Spaces
- Recursive Probability Computations
- Conditional Probability
- Independence, revisited



# 初等离散概率 ELementary Discrete Probability

## 初等概率 Elementary Probability

### 概念定义

1. 样本空间（Sample Space）：包含所有可能结果的集合，每一个元素代表一个可能的结果。
$$
Ω = \{ω₁, ..., ωₙ\}
$$
2. 事件（Event）：是结果的集合，是样本空间的子集。
3. 概率分布（Probability Distribution）：是一个函数 $P: Pow(Ω)→ ℝ$，满足：

$$
P(Ω)=1 \\
\text{如果事件E和F不相交（互斥），那么} P(E ∪ F) = P(E) + P(F)
$$

### 基本事实

- $P(∅) = 0$，意味着一个不可能事件的概率是0。
- $P(Eᶜ) = 1 - P(E)$，其中 $Eᶜ$ 是 $E$ 的补事件，这表示事件 $E$ 不发生的概率。

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

## 均匀分布 Uniform Distribution

在均匀概率分布中，样本空间Ω中的每个结果ωᵢ都是等可能的。具体地，对于样本空间Ω中的每个结果ω₁, ω₂, ..., ωₙ，它们发生的概率相同，用概率论的术语表示为：

$$
P(ω₁)=P(ω₂)= ... = P(ωₙ) = \frac{1}{n}
$$

这称为样本空间Ω上的均匀概率分布。在这种分布下，每个单独事件发生的概率是相等的，这是一个在理想化的公平游戏或者是理想情况下的随机实验中常见的分布。

## 通过计数计算概率 Computing Probabilities by Counting

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

在没有其他资料的情况下，"随机选择"这个表述通常意味着"根据均匀分布"进行选择。这意味着每个可能的结果都有相同的概率发生。

大多数计数规则可以直接转换为关于均匀分布的概率。这是因为在均匀分布下，概率直接与样本空间中特定事件的数量相关联。

## 组合事件 Combining Events

通过组合简单事件来构造复杂事件：

- 事件A和事件B同时发生：使用交集符号表示，即 $A \cap B$。
- 事件A或事件B发生（至少一个发生）：使用并集符号表示，即 $A \cup B$。
- 事件A不发生：使用补集符号表示，即 $ \Omega \backslash A$。
- 事件A发生后事件B发生：这通常涉及条件概率或序列事件，可能用其他概率规则来描述。

前三种构造涉及到来自同一样本空间的事件，而最后一种可能涉及来自不同样本空间的事件（例如先掷骰子再抛硬币）。

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


# 独立事件 Independence

## 统一不同集合的结果 Unifying sets of outcomes

- 抛硬币的样本空间可以表示为 $\Omega_1 = \{heads, tails\}$
- 掷骰子的样本空间可以表示为 $\Omega_2 = \{1, 2, 3, 4, 5, 6\}$


这两个活动可以结合起来创建一个新的样本空间 $\Omega = \Omega_1 \times \Omega_2$，包括所有可能的组合。

这种方法也可以用来建模结果序列。这意味着它不仅仅用于单次事件，还可以用于表示一系列连续事件的所有可能结果。这种方法在多阶段实验中非常有用，其中每个阶段都可能有不同的结果集。

## 乘积分布 Product Distribution

$$
P(E_1 \times E_2 \times ... \times E_n) = P_1(E_1) \times P_2(E_2) \times ... \times P_n(E_n)
$$

表示在一个维度上的事件的概率不会受到其他维度上结果的影响。这个性质是独立性的体现，它是说在乘积空间中的事件发生的概率是各自独立事件概率的乘积。

## 独立性 Independence

### 非正式定义

事件被认为是独立的，如果一个事件的结果不影响另一个事件的结果。

### 正式定义

如果两个事件，事件A和事件B，同时发生的概率等于各自发生概率的乘积，那么它们被称为（随机）独立的（记作 $A⊥B$ ）。

$$
P(A \cap B) = P(A)P(B)
$$

除非另有说明，当我们在统一事件时（在适当的情况下），我们假设事件是独立的。这个假设是为了简化问题分析，因为在实际应用中，事件的独立性往往需要明确指出或由问题的背景决定。

### 全独立性与成对独立性

- 全独立性 Full Independence：所有事件之间都相互独立，它们同时发生的概率等于它们各自发生概率的乘积。
- 成对独立性 Pairwise Independence：相对更弱，它只要求每对事件之间相互独立，而不是要求所有事件之间。

例如，考虑两次抛硬币的实验：

1. 事件A：第一次抛硬币得到正面（H）
2. 事件B：第二次抛硬币得到正面（H）
3. 事件C：两次抛硬币中恰好一次得到正面（H）

虽然A和B是独立的，A和C是独立的，B和C也是独立的（即所有的成对事件独立，$P(A) = P(B) = P(C) = \frac{1}{2}$， 且 $P(A∩B) = P(A∩C) = P(B∩C) = \frac{1}{4}$），但事件A、B和C并不是全独立的，因为 $P(A∩B∩C) = 0 \ne P(A)·P(B)·P(C)$。

这个例子说明了成对独立性并不总是蕴含全独立性。而且还可以构造一组n个事件，其中任意k个是独立的，但任意k+1个就不是独立的（$k < n$）。

## 二项分布 Binomial Distribution

在一系列的n个独立试验中，每次试验成功的概率为p，那么恰好有k次成功的概率可以用下面的公式来表示：

$$
P = (_k^n)p^kq^{n-k} \\
q = 1 - p
$$

这种概率分布模式被称为二项分布。二项分布是离散概率分布的一个重要例子，常用于描述固定数量独立试验中成功次数的概率。这里的“成功”可以指任何感兴趣的二分结果，例如抛硬币得到正面或者负面，测试结果为阳性或阴性等。


# 无穷样本空间 Infinite Sample Spaces

在连续空间中（例如实数 ℝ）：

- 概率分布被视为度量（measures）。
- 求和操作通过积分来完成。
- 非零概率适用于范围而不是单点。
- 单个事件的概率是0，但这并不意味着该事件是不可能的，因为在连续空间中，有无限多个可能的结果。

在离散空间中（例如自然数 ℕ）：

- 概率为0确实意味着某个事件是不可能的。
- 不存在均匀分布，因为不能给无限个事件赋予相同的非零概率，使它们的总和为1。
- 非均匀分布是存在的。例如，可以有一个分布，其中 $P(0) = 1$ 而所有 $P(n) = 0（n > 0）$，或者分布 $P(0) = 0, P(n) = \frac{1}{2^n} (n > 0)$。
- 在某些情况下，如果合理的话，可以考虑极限概率。


# 递归概率计算 Recursive Probability Computations

- H: Head，正面。
- T: Tail，反面。

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


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


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

大多数概率和统计问题没有简洁优雅的解决方案。因此，使用计算机进行精确计算或近似模拟变得必不可少。然而，递归的使用简化了这样的计算，或者很多时候，使这样的计算成为可能。递归是指自己调用自己的函数，这在处理复杂的概率计算时特别有用，尤其是在可以将问题分解成更小、更简单的子问题时。


# 条件概率 Conditional Probability

事件E在事件S已经发生的条件下发生的概率，记为 $P(E|S)$，定义为：

$$
P(E|S) = \frac{P(E \cap S)}{P(S)}
$$

条件概率只有在 $P(S) \ne 0$ 时才有定义。


:::note{title="注"}
通常， $P(A|B)$ 和 $P(B|A)$ 之间可以说完全没有关系，知道一个并不能告诉我们关于另一个的任何信息。
:::

## 基本事实

- $A \subseteq B \rightarrow P(A|B) \le P(A)$：在事件B发生的条件下事件A发生的概率至少和A无条件发生的概率一样大。
- $A \subseteq B \rightarrow P(B|A) =1$：如果事件A发生了，那么事件B肯定发生。
- $P(A \cap B | B) = P(A | B)$
- $A \ne \empty \rightarrow P(\empty | A) = 0$：对于非空事件A，在事件A发生的条件下，不可能事件发生的概率是0。
- $P(A|\Omega) = P(A)$：在整个样本空间发生的条件下事件A发生的概率就是事件A本身的概率。
- $P(A^C|B) = 1-P(A|B)$：事件A在B发生的条件下不发生的概率等于1减去A在B发生的条件下发生的概率。

:::note{title="注"}
$P(A|B)$ 和 $P(A|B^C)$ 之间通常不相关。知道了在B发生的条件下A的概率，并不能告诉我们在B不发生的条件下A的概率。
:::

### 独立性与条件概率

假设事件A和事件B时随即独立的，即：

$$
P(A \cap B) = P(A)P(B)
$$

如果 $P(A) \ne 0, P(B) \ne 0$，那么下列陈述完全等价：

- $P(A \cap B) = P(A)P(B)$
- $P(A|B) = P(A)$
- $P(B|A) = P(B)$
- $P(A^C|B) = P(A^C)$
- $P(A|B^C) = P(A)$
- $P(A^C|B^C) = P(A^C)$

如果A和B独立，则A的补集和B独立，A和B的补集独立，A的补集和B的补集也独立。即：如果两个事件A和B独立，它们的补集之间的关系也是独立的。

COMP9020-9-2 Probability

- 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)$