- Random Variables and Expectations
- Linearity of Expectation
- Expected Time to Success
-  Standard Deviation and Variance



# 随机变量与期望 Random Variables and Expectatiions

## 随机变量

整数随机变量X是一个从 $ Ω $ 到 $ ℤ $ 的函数。换句话说，它将每一个结果都与一个数值关联起来。

- 随机变量通常用 X, Y, Z 等字母表示。
- 我们以自然的方式将算术运算扩展到随机变量上。

给定随机变量 $X: Ω → ℤ$ 和随机变量 $Y: Ω → ℤ$ 以及整数 $k$，我们可以将 X、Y 和 k 组合起来，得到以下在所有 $ω ∈ Ω$ 上的函数：

- 变量加法：$X + Y ：ω ↦ X(ω) + Y(ω)$
- 变量乘法：$X · Y ：ω ↦ X(ω) · Y(ω)$
- 标量加法：$X - k ：ω ↦ X(ω) - k$
- 标量乘法：$kX ：ω ↦ k · X(ω)$

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

## 期望

随机变量 X 的期望值（通常称为“期望”或“平均值”）是通过下面的公式计算的：

$$
E(X) = \sum_{k \in Z}P(X=k) \times k
$$

期望是一个真正普遍的概念；它是所有决策、估计盈亏、在风险下行动的基础。在概率论概念出现之前，期望值这一基本概念就已经存在了。


# 期望值的线性 Linearity of expectation

对于任意随机变量 X 和 Y，以及整数 k，有：

- $E(X+Y) = E(X) + E(Y)$
- $E(k \times X) = k \times E(X)$

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

## 观察可得 Observations

如果 $X_1$，$X_2$，...，$X_n$ 是独立同分布的随机变量，那么：

$$
E(X_1+X_2+...+X_n) = E(nX_1) = nE(X_1)
$$

当随机变量独立同分布时，它们和的期望值等于任意一个随机变量期望值的n倍。

尽管 $X_1+X_2+...+X_n$ 与 $nX_1$ 期望值相同，但这两个表达式代表的随机变量本身是非常不同的。

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


# 成功的期望时间 Expected Time to Success

几何级数 & 递归

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

一个更简单但同样有效的论证是，你预期在一次抛掷中得到“一半”的正面，所以你应该期望在两次抛掷中得到一个“完整”的正面。

## 成功与期望值

问题：高成功概率是否导致高期望值？

一般来说，不是这样。例如：

- 购买更多的彩票可以增加中奖的机会，但是中奖的期望却降低了。

## 赌徒陷阱 Gambler's ruin

很多所谓的“获胜系统”声称提供一个获胜策略，实际上它们提供了一个频繁获得适度胜利的方案，但代价是偶尔会有非常大的损失。

事实上，有一个正式的定理表明，没有任何系统可以将一个“不公平”的游戏转变为一个“公平”的游戏。在决策理论中，“不公平”指的是那些每个个别投注都有负期望值的游戏。

很容易验证，无论是在轮盘赌上的个别投注，购买彩票，或者任何商业提供的游戏上的投注，都具有负的期望值。


# 标准差与方差

对于随机变量X，其期望值为 $μ = E(X)$，标准差为：

$$
\sigma = \sqrt{E((X-μ)^2)}
$$

方差为：

$$
\sigma^2
$$

标准差和方差度量了随机变量的值分散程度。方差越小，我们越能确信对于随机选择的 $ω$，有：

$$
X(ω) = E(X)
$$

并且，方差可以计算为：

$$
E((X-μ)^2) = E(X^2) - μ^2
$$

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

COMP9020 10.1 Statistics

quiz8



## 1.1

### Question

In a class of 200:

- 80 are funny
- 130 are clever
- 42 are neither funny nor clever
How many are both funny and clever?

### Answer


$$
|F \cup C| = |F| + |C| - |F \cap C|
$$

因此，答案为：52

## 1.2

### Question

How many integers are there between 1 and 1000 which are divisible by 6 or 15 but not both?

### Answer
$$
|A \cup B| = |A| + |B| - |A \cap B|
$$

- 集合A的大小，即1到1000之间可以被6整除的数的数量。（199）
- 集合B的大小，即1到1000之间可以被15整除的数的数量。（66）
- 集合A和B的交集的大小，即1到1000之间可以被30整除的数的数量。（33）


因此，答案为：166（因为33被计算了两次，所以199+66-33*2）

## 1.3

### Question

Let S be a set of size n, and fix a constant k>1 (i.e k does not depend on n). Which of the following gives the best asymptotic upper bound for the number of subsets of S of size k?

### Answer

集合不考虑顺序，因此只需要在n里选出k个元素，即 $(^n_k)$。

$$
(^n_k)=\frac{(n-k)!}{k!}
$$

同时，由于k是常数，所以直接忽略。且：$(n-k)! \rightarrow O(n^k)$

因此，答案为：$O(n^k)$。

## 1.4

### Question

Suppose I place 2 red balls, 3 green balls, and 4 blue balls into a hat, and draw two balls without replacement.

What is the probability they are both blue?

### Answer

第一个球是蓝球的概率是4/9，满足第一次的情况下出现第二个蓝球的概率是4-1/9-1=3/8

因此，答案为：1/6

## 2.1

### Question

How many ways are there of choosing an ordered sequence of three letters (with no replacements) from 'SYDNEY'?

### Answer

计算三个字母的有序序列的总数，我们需要分四种情况来考虑：

- 序列中没有"Y"。
- 序列中有一个"Y"。
- 序列中有两个"Y"。

第一种情况，我们要从"SDNE"中选择三个，并组成有序序列，共有：$C_4^3 \times A^3_3 = 4 \times 6 = 24$。

第二种情况，我们要从"SDNE"中选择两个，并和另一个Y组成有序序列，共有：$C_4^2 \times A_3^3 = 6 \times 6 = 36$。

第三种情况，我们要从"SDNE"中选择一个，和另外两个"Y"组成有序序列。两个Y构成插槽，因此实际上该字母能选择位置只有3个，共有：$C_4^1 \times 3 = 12$。


因此，答案为：72


## 2.2

### Question

How many sequences of 2n coin flips have exactly n heads and n tails?

### Answer

我们只需要考虑，在这2n个硬币中，选择n个正面朝上即可，我们不需要考虑它的顺序或者别的东西。

因此，答案为：$(^{2n}_n)$

## 2.3

### Question

How many ways are there of placing 6 indistinguishable balls into 3 distinguishable boxes so that each box contains at least 1 ball?

### Answer

六个球是等价的，三个盒子不等价。我们可以先在每个盒子中都放一个球，把问题转化为：

现在有3个球，放入三个不同的盒子中，有几种放法？

有三种情况：

1. 三个球在一个盒子里（3种）
2. 有一个盒子是空的，另外两个盒子2&1分布（3*2）
3. 三个球在三个盒子里（1种）

因此，答案为：10

## 2.4

### Question

Suppose I place 2 red balls, 3 green balls, and 4 blue balls into a hat, and draw two balls without replacement.

What is the probability that the second ball is blue, given that the first ball is blue?

### Answer

感觉跟前面那题没区别，答案为3/8

COMP9020 Quiz 8

- 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⊨φ$。