Ownership & Borrowing




# GPT 链接

[Shared Link](https://chat.openai.com/share/b6b91285-3c8d-4324-ae8a-4e364f699e6e)

# 所有权

所有权是Rust最独特的特性之一，旨在提供内存安全而不需要垃圾收集。在Rust中，每个值都有一个被称为其"所有者"的变量。值有以下规则：

- 值在任何时候只能有一个所有者。
- 当所有者（变量）离开作用域，其值将被丢弃。

## 变量被丢弃

一个方法使用了某一个变量，然而没有进行值的返回。在这个过程中，该变量的所有权被该方法所独享，其他函数无法再使用该变量。

解决方法为，尝试让该函数返回使用后的变量，以此达到所有权的回归。

```RUST
fn main() {
    let img = Image::new(256,256);
    
    //变量被使用
    let sist = use_img(img);
}

fn use_img(mut img::Image) {
    .....
    
    
    .....
    
    //返回该变量以回归所有权
    img
}
```

## owned与copy

### 什么是Copy类型

Copy trait是一个标记trait，用于指示类型的值可以通过简单的位复制来"复制"，而不是被移动。当一个类型实现了Copy trait时，它的值在被赋值给另一个变量时不会转移所有权。这意味着原始变量在赋值后仍然可以使用，因为内存中的数据被复制到了新的位置。

不是所有类型都可以实现Copy trait。只有那些不涉及堆分配或资源管理（如文件句柄）的简单类型（如整数、浮点数、布尔值、字符以及这些类型的固定大小数组和元组）默认实现了Copy trait。复杂类型，如`String`或`Vec<T>`，不实现Copy，因为它们在堆上管理内存，其所有权在赋值时需要被转移，以避免双重释放。

```RUST
fn main() {
    let x = 5; // x 是一个整数类型，实现了 Copy trait
    let y = x; // y 是 x 的一个副本，x 不会失去所有权，因为 i32 实现了 Copy trait

    println!("x: {}, y: {}", x, y); // x 和 y 都可以使用，因为 i32 类型的值被复制了
}
```

```RUST
fn main() {
    let s1 = String::from("hello"); // s1 是一个 String 类型，不实现 Copy trait
    let s2 = s1; // s1 的所有权移动到 s2，s1 不再有效

    // println!("s1: {}, s2: {}", s1, s2); // 这行会编译错误，因为 s1 的值已经移动了
    println!("s2: {}", s2); // 只能使用 s2
}
```

## 我能否手动添加copy

当你的复杂字段内部是简单类型时，你可以在声明的时候进行自动派生COPY选项。

```RUST
#[derive(Debug, Clone, Copy)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let point1 = Point { x: 5, y: 10 };
    let point2 = point1; // 因为 Point 实现了 Copy trait，所以这里是复制而不是移动

    println!("point1: {:?}", point1); // 有效，因为 point1 的值被复制到 point2
    println!("point2: {:?}", point2);
}
```

然而，copy仅适合小型而简单的类型。如果类型涉及到内存管理/堆内存分配（例如String和Vec），或者需要特别管理的资源（如文件句柄、网络套接字），就需要使用Clone来提供更复杂的逻辑。

# 借用/引用 Borrowing

在Rust中，借用（borrowing）是一种允许你访问数据而不取得其所有权的机制。这是Rust内存安全保证的核心部分之一，旨在无需垃圾收集即可防止数据竞争等问题。借用在Rust中主要通过引用来实现，分为两种类型：不可变引用（&T）和可变引用（&mut T）。

## 不可变借用（独占借用）

不可变借用允许你读取数据，但不允许修改它。当数据被不可变借用时，原始数据仍然可以被多次借用为不可变引用，但不能被借用为可变引用。这保证了在不可变借用的有效期内，数据不会被意外改变。

```RUST
fn main() {
    let data = vec![1, 2, 3];
    let ref1 = &data; // 不可变借用
    let ref2 = &data; // 另一个不可变借用，与 ref1 同时存在是允许的

    println!("{:?} {:?}", ref1, ref2); // 可以同时访问 ref1 和 ref2
}
```

## 可变借用（共享借用）

可变借用允许你修改数据。当数据被可变借用时，在该借用的有效期内，原始数据不能被其他任何借用（不可变或可变）。这确保了在修改数据时，没有其他引用指向该数据，防止了数据竞争。

```RUST
fn main() {
    let mut data = vec![1, 2, 3];
    let ref1 = &mut data; // 可变借用

    ref1.push(4);
    println!("{:?}", ref1); // 此时只能访问 ref1，不能创建其他任何借用
}
```

## 借用规则

- 同时存在的不可变引用数量不限：你可以有任意数量的不可变引用，因为它们不会改变数据。
- 只能有一个可变引用：在特定作用域中，只能有一个可变引用，防止数据竞争。
- 不可变和可变引用不能同时存在：如果你有一个可变引用，那么就不能再有不可变引用，反之亦然。这规则确保了数据安全和一致性。【参考后文 共享异或可变】


# 共享异或可变 Shared 'XOR' Mutable

在Rust中，"Shared XOR Mutable"（共享异或可变）原则是指对于给定的资源，你可以拥有多个不可变引用（共享访问），或者一个可变引用（独占访问），**但不能同时拥有**。这是Rust内存安全原则的核心之一，旨在在编译时防止数据竞争和其他并发错误。

## 共享访问 Shared

当你通过不可变引用访问数据时，你正在进行共享访问。Rust允许你同时拥有多个这样的引用，因为它们都保证不会修改数据。这意味着，只要数据不被修改，就可以安全地从多个地方读取它，不会引起数据竞争或其他并发问题。

```RUST
let value = 42;
let ref1 = &value; // 第一个不可变引用
let ref2 = &value; // 第二个不可变引用

println!("{} {}", ref1, ref2); // 可以安全地同时访问
```

## 可变访问 Mutable

当你通过一个可变引用修改数据时，你正在进行独占访问。在这种情况下，Rust确保在该可变引用的生命周期内，没有其他的引用（无论是可变的还是不可变的）指向同一数据。这一约束确保了在修改数据时，没有其他代码可以读取或修改这些数据，从而防止了数据竞争。

```RUST
let mut value = 42;
let ref1 = &mut value; // 可变引用

*ref1 += 1; // 可以安全地修改数据
```

## 独占借用的注意事项

### 在独占借用的生命周期内，不能再声明任何其他的独占借用。

当你对某个值进行独占借用时，这意味着你获取了对该值的可变引用。在这个可变引用存在的整个生命周期内，你不能再创建任何其他的对该值的独占借用。这是因为Rust的安全规则确保当你有一个可变引用时，该引用是唯一访问和修改值的方式，从而避免了潜在的数据竞争。

```RUST
let mut value = 10;
let mut_borrow1 = &mut value; // 第一个独占借用
let mut_borrow2 = &mut value; // 错误：不能在 mut_borrow1 存在时创建另一个独占借用
```

### 在独占借用的生命周期内，不能再有任何共享借用。

因为共享亦或可变原则。

当你有一个值的独占借用时，你也不能创建该值的任何共享借用。这保证了当数据可能被修改时，没有其他代码可以读取这些数据，因为即使只是读取，也可能会因为数据的改变而导致不一致性或其他错误。

```RUST
let mut value = 10;
let mut_borrow = &mut value; // 独占借用
let borrow = &value; // 错误：不能在 mut_borrow 存在时创建共享借用
```


# 运用借用Borrow的原则

- 优先使用共享借用。
- 当你需要修改值的时候，再去用可变借用。

COMP6991 3.1 Ownership & Borrowing

COMP9020 Quiz 2, Test started Feb 21, 2024 6:00 PMtoFeb 28, 2024 6:00 PM



## 1.1

```
Let A be the set {b,a,n,a,n,a} and B be the set {p,i,n,e,a,p,p,l,e}.
Which of the following are subsets of A⊕B?
Select all that apply

- {b,p,i,e,p,p,l,e}
- {a,b,e,i,l,n,p}
- {b,p}
- {p,p,p,a,a,n,n,e,e}
- {}
- {a,n}
```

$$
\because
A=\{a,b,n\}, \ \ 
B=\{a,e,i,l,n,p\} \\
\therefore
A \oplus B = \{b, e, i, l, p\}
$$

重复的元素视为同一元素即可。

因此，答案有：

```
- {b,p,i,e,p,p,l,e}
- {b,p}
- {}
```

## 1.2

```
Which of the following sets have exactly 6 elements?  (Intervals are over ℕ)
Select all that apply

- [0,1] × (1,6)
- (0,1) × [1,6]
- (0,2] × [1,4)
- [0,2] × (1,4)
- None of the above
```

- 选项1：

$$
\because
|[0,1]| = 2, \ 
|(1,6)| = 4 \\
\therefore
|[0,1] \times (1,6)|=2*4=8
$$

- 选项2：

$$
\because
|(0,1)| = 0, \ 
|[1,6]| = 6 \\
\therefore
|(0,1) \times [1,6]|=0*6=0
$$

- 选项3：

$$
\because
|(0,2]| = 2, \ 
|[1,4)| = 3 \\
\therefore
|(0,2] \times [1,4)|=2*3=6
$$

- 选项4：

$$
\because
|[0,2]| = 3, \ 
|(1,4)| = 2 \\
\therefore
|[0,2] \times (1,4)|=3*2=6
$$

因此，答案有：

```
- (0,2] × [1,4)
- [0,2] × (1,4)
```

## 1.3

```
Let Σ={a,b}. 
Let w ∈ Σ* be the word "abb",
let v ∈ Σ* be the word "ba".
What is length(vwv)?
```

$$
\because
vwv=baabbba
\\
\therefore
length(vwv)=7
$$

## 1.4

```
Let Σ={c,u,p} and Ψ={s,a,u,c,e,r}
Which of the following words are in Σ* \ Ψ*?
Select all that apply

- ccc
- eee
- saucer
- λ
- cup
- ppp
```

要点：寻找能在集合Σ中组出来的词，并且这个词在集合Ψ中无法组出来。

因此，答案有：

```
- cup
- ppp
```

## 1.5

```
Which of the following statements are true for all sets A, B, C?
Select all that apply

- (A ∪ B)\C = (A\C) ∪ (B\C)
- (A⊕B)ᶜ = (Aᶜ) ⊕ (Bᶜ)
- (C\A)ᶜ = (Cᶜ) \ (Aᶜ)
- (A∪B)∩A = A∪(B∩A)
- C\(A ∪ B) = (C\A) ∪ (C\B)
```

- 选项1：

$$
(A \cup B) \backslash C 
= (A \cup B) \cap C^C \\
= (A \cap C^C) \cup (B \cap C^C) \\
= (A \backslash C) \cup (B \backslash C)
$$

- 选项2：

$$
(A \oplus B)^C \\
= ((A \backslash B) \cup (B \backslash A))^C \\
= ((A \cap B^C) \cup (B \cap A^C))^C \\
= (A \cap B^C)^C \cap (B \cap A^C)^C \\
= (A^C \cup B) \cap (B^C \cup A)
$$

$$
(A^C) \oplus (B^C) \\
= (A^C \backslash B^C) \cup (B^C \backslash A^C) \\
= (A^C \cap B) \cup (B^C \cap A)
$$

- 选项3：

$$
(C \backslash A)^C \\
= (C \cap A^C)^C \\
= C^C \cup A
$$

$$
(C^C) \backslash (A^C) \\
= C^C \cap A
$$

- 选项4：

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

- 选项5：

$$
C \backslash (A \cup B) \\
= C \cap (A \cup B)^C \\
= C \cap (A^C \cap B^C)
$$

$$
(C \backslash A) \cup (C \backslash B) \\
= (C \cap A^C) \cup (C \cap B^C) \\
= C \cap (A^C \cup B^C)
$$


因此，答案有：

```
- (A ∪ B)\C = (A\C) ∪ (B\C)
- (A∪B)∩A = A∪(B∩A)
```

## 2.1

```
For all sets A and B, A∩B = A∪B  if and only if A=B.
```

- if:

```
if A=B, then A∩B = A∪B.
```

$$
\because 
A=B,
\\
\therefore
A \cap B = A \cup B = A = B
$$

- only if:

```
if A∩B = A∪B, then A=B.
```

$$
\because
A \cup B = A \cap B
\\
\therefore
\text{for every element $k$ in } A, 
\\
k \in A,\ and\ k \in B
\\
\therefore
A \subseteq B
\\
\therefore
\text{same reason, }B \subseteq A
\\
\because 
A \subseteq B, \ B \subseteq A,
\\
\therefore 
A = B
$$

因此，答案为：

```
- True
```

## 2.2

```
For all sets A,B,C:
A×(B∩C) = (A×B) ∩ (A×C)
```

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


## 2.3

```

Which of the following sets has cardinality less than or equal to 6?
Select all that appy:

- {n∈ℤ : 6|n}
- {6%n : n∈ℕ and n>0}
- {n∈ℤ : n|6}
- {n%6 : n∈ℤ}
```

- 选项1：

在集合 $\{n \in Z: 6 \mid n\}$ 中，$n$ 代表了整数集合中所有6的倍数，因此是该集是无穷的。

- 选项2：

$$
\{6 \% n： n \in N \ and \ n>0\} = \{0,1,2,6\}
$$

- 选项3：

$$
\{n \in Z: n \mid 6\} = \{-6,-3,-2,-1,1,2,3,6\}
$$

- 选项4：

$$
\{n \% 6: n \in Z\} = \{0,1,2,3,4,5\}
$$

因此，答案有：

```
- {6%n : n∈ℕ and n>0}
- {n%6 : n∈ℤ}
```

## 2.4

```
Suppose A={0,1,2}
For how many sets B⊆ℕ is it the case that A×B = B×A?
Select one alternative:
- 0
- 1
- 2
- 3
- Infinitely many
- None of the above
```

假设集合B不为空集，且元素为：$\{b_1,b_2,b_3,...b_n\}$，那么：

$$
A \times B = \{(0, b_1), (0, b_2), ... (1, b_m), (1, b_{m+1}), ... (2, b_n), (2,b_{n+1}),...\} \\
B \times A = \{(b_1, 0), (b_2, 0), ... (b_m, 1), (b_{m+1},1), ... (b_n, 2), (b_{n+1}, 2),...\}
$$

若要保证 $A \times B = B \times A$ ，需要有：

$$
b_1 = 0, \ \ 
b_1 = b_2 = ...
\\
b_m = 1, \ \ 
b_m = b_{m+1} = ...
\\
b_n=2, \ \ 
b_n=b_{n+1} = ...
$$

因此，当 $B=\{0,1,2\}=A$ 时，有 $A \times B = B \times A$。

假设B为空集，显然：

$$
A \times B = B \times A = \empty
$$

因此，答案有：

```
- 2
```

## 2.5

```
Let Σ = {0,1}.
True or false:
For all languages X ⊆ Σ*: (XX)* = (X*)(X*)
```

反例：
$$
(X^*)(X^*) = (X^1)(X^0) = X \\
(XX)^* \ne X
$$

单字符的字符串无法被$(XX)^*$表示。

因此，答案为：

```
- False
```

COMP9020 Quiz 2

Lecture 4: Set Theory

- Recap of Key Definitions
- Set Equality
- Laws of Set Operations
- Derived Laws
- Two Useful Results




# 主要定义方法之重述 Recap of Key Definitions

具体内容，可以参见：[COMP9020 2.1 Sets and Formal Languages - 定义集合 Defining sets](https://rin977.com/post/COMP9020-2-1#%E5%AE%9A%E4%B9%89%E9%9B%86%E5%90%88%20Defining%20sets)

1. 显式枚举
2. 下定义区间
3. 从已有集合中构造


# 集合相等 Set Equality

欲证明两集合相等，需证明两集合均包含相同的元素。以下是三种方法：

- 直接列出所有的元素并比较是均相同。
- 证明 $A \subseteq B$ 并且 $B \subseteq A$，构成当且仅当后即可证明。
- 使用集合运算法则（Law of Set Operation）。

注意：韦恩图可以作为可视化的辅助措施，但不能作为严谨的证明过程。

# 集合运算法则 Law of Set Operation

- 集合交换律 Commutativity：

$$
A \cup B = B \cup A \\
A \cap B = B \cap A
$$

- 集合结合律 Associativity：

$$
(A \cup B) \cup C = A \cup (B \cup C)   \\
(A \cap B) \cap C = A \cap (B \cap C)
$$

- 集合分配律 Distribution：

$$
A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \\
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
$$

- 补集性质 Complementation：

$$
A \cup (A^C) = U \\
A \cap (A^C) = \empty
$$

- 单位元性质 Identity：

$$
A \cup \empty = A \\
A \cap U = A
$$

- 幂等性 Idempotence：

$$
A \cap A = A \\
A \cup A = A
$$

- 双重补集性质 Double complementation：

$$
(A^C)^C = A
$$

- 消去律 Annihilation：

$$
A \cap \empty = \empty \\
A \cup U = U
$$

- 德摩根定律 De Morgan's Laws：

$$
(A \cap B)^C = A^C \cup B^C \\
(A \cup B)^C = A^C \cap B^C
$$

### 运算法则使用示例


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


# 两种有用的定理 Two Useful Results

## 对偶原理 Principle of Duality

对偶的定义：

> 如果集合 $A$ 是用 $\cap , \cup , \empty , U$ 定义的集合，那么它的对偶 $dual(A)$ 是将 $\cap$ 与 $\cup$ 、 $\empty$ 与 $U$ 相互替换后的产物。

举例说明：

$$
A_1 = A \cup (A \cap B) \\
dual(A_1) = A \cap (A \cup B)
$$

因此，有对偶原理：

> 如果你能证明集合 $A_1 = A_2$，那么你同样可以得到 $dual(A_1)=dual(A_2)。$

## 补集唯一性 Uniqueness of complement

> 当且仅当 $B=A^C$ 时，能够同时存在以下条件：
> - $A \cap B = \empty$
> - $A \cup B = U$


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

COMP9020 2.2 Set Theory

Lecture 3: Sets and Formal Languages

- Introduction to Sets
- Defining Sets
- Set Operations
- Formal Languages



# 集合简介 Introduction to Sets

## 定义 Definition

A set is a collection of objects (elements). If x is an element of A, we write x ∈ A.


- 集合内的元素没有顺序，也没有重复性。
- 单个元素和单元素集合本身需要进行区分。即：$a\ne\{a\}$。
- 空集的表示：$\empty = \{\}$，即没有元素。
- 该集是非空的：$\{\empty\}$，它有一个元素：$\empty$。

---

- The most set is **universe**, $U$.
- Not all "well-defined" universes are possoble.
    - No "set of all sets" (Cantor's paradox)
    - No "sets which do not contain themselves" (Russel's paradox)

---

:::info{title="康托尔悖论"}
Cantor's Paradox 是一个与集合论有关的悖论，由数学家格奥尔格·康托尔（Georg Cantor）提出。它揭示了“所有集合的集合”这一概念在朴素集合论中的自我矛盾性。这个悖论可以这样解释：

朴素集合论中的集合：在朴素集合论中，一个集合可以被理解为任意对象的一个整体，其中的对象称为该集合的元素。集合可以包含其他集合作为其元素。

“所有集合的集合”：如果我们尝试构建一个包含所有集合作为其元素的集合，我们可以称之为“全集”（或“所有集合的集合”）。

Cantor 的对角线论证：康托尔发展了一种称为“对角线论证”的方法，用以证明实数集合的势（或大小）大于自然数集合的势。这个方法也可以用来展示“所有集合的集合”不能存在。

首先，假设存在一个“所有集合的集合”S。
然后，考虑所有从S到其自身的可能子集。根据康托尔的对角线论证，可以证明S的所有子集的集合的势（大小）必然大于S本身的势。
这意味着S不能包含所有可能的集合，因为它至少缺少了一些子集。
悖论的核心：悖论在于，如果我们试图构建一个包含一切可能集合的“全集”，那么根据对角线论证，这个“全集”必须比自身还要大，这是不可能的。这表明在朴素集合论中无法构建一个同时包含所有集合的集合。

解决方案：为了解决这个悖论以及集合论中的其他类似问题，数学家们发展了公理化集合论（如ZFC集合论），在这些理论框架中，通过引入公理来限制集合的构造，从而避免了这类悖论的出现。

Cantor's Paradox 揭示了朴素集合论的局限性，促使数学家寻求更加严格和精细的理论框架来处理集合及其相关概念。
:::


:::info{title="罗素悖论"}
罗素悖论（Russell's Paradox）是由英国哲学家和数学家伯特兰·罗素（Bertrand Russell）提出的一个著名逻辑学和集合论中的悖论。它直接挑战了朴素集合论的基本假设，并促进了集合论的公理化。罗素悖论可以这样解释：

朴素集合论的背景：在朴素集合论中，一个集合可以定义为满足某种特定性质的所有对象的汇总。理论上，任何性质都可以定义一个集合。

自我包含的集合：如果一个集合作为自己的元素，则称这个集合为自我包含的。例如，集合“所有集合”的集合是自我包含的，因为它本身是一个集合，所以它包含自己。

罗素悖论的构造：罗素考虑了这样一个集合R，R包含所有不包含自己作为元素的集合。换句话说，如果一个集合x不是自己的元素，那么x就是R的一个元素。

悖论的发生：

现在我们询问：集合R是否包含自己？有两种可能性：
如果R包含自己，根据R的定义，它只应该包含那些不包含自己的集合。因此，如果R包含自己，它就违背了自己的定义。
如果R不包含自己，根据R的定义，它应该包含所有不包含自己的集合，包括R本身。因此，如果R不包含自己，根据定义，它应该包含自己。
这两种情况都导致矛盾，因此无法确定R是否包含自己。
悖论的意义：罗素悖论展示了朴素集合论中关于集合可以由任意性质定义的假设的问题。它说明了需要更加严格的原则来避免这类逻辑悖论。

解决方案：为了解决罗素悖论以及其他相关悖论，数学家发展了新的集合论体系，如Zermelo-Fraenkel集合论（ZF）和带有选择公理的Zermelo-Fraenkel集合论（ZFC）。这些公理化集合论通过限制集合的构建方式，避免了像罗素悖论这样的自相矛盾。

罗素悖论不仅在数学史上占有重要位置，也对逻辑学、哲学以及数学的基础研究产生了深远影响。通过引入更加严格的集合论公理，数学家能够构建一个更加一致和稳固的数学基础。
:::

---

## 子集 Subsets

如果集合$S$的所有元素都是集合$T$的元素，我们说$S$是$T$的子集，写作$S \subseteq T$。

- $S \subseteq T$包含情况：$S=T$
- $S \subset T$包含情况：$S \ne T$
- 对于所有的集合$S$，均有$\empty \subseteq S$
- 对于所有集合$S$，均有$S \subseteq U$
- $N_{>0} \sub N \sub Z \sub Q \sub R$
- 集合的一个元素，和集合的一个子集，不是一个东西。
$$
a \in \{a,b\}, a \nsubseteq \{a,b\}; \\
\{a\} \subseteq \{a,b\}, \{a\} \notin\{a,b\}
$$

# 定义集合 Defining sets

## 显式枚举 Enum

直接对集合内的元素进行枚举，以得到每一个元素，从而定义一个集合。

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

## 下定义 Defining

使用多项式、不等式等方式为集合元素下定义，从而定义一个集合。

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

### 特殊形式：Intervals

使用符号直接划定范围，该范围可以视为一个集合。

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

## 从已有集合中构造

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


# 集合操作 Set Operations

- 并集 union：

$$
A \cup B = \{x:x \in A \ or\ x \in B\}
$$

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

- 交集 intersection：

$$
A \cap B = \{x:x \in A \ and\ x \in B\}
$$

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


- 补集 complement：

$$
A^C=\{x:x\in U \ and\ x\notin A\}
$$


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


- 不相交 disjoint：

$$
A \cap B = \empty
$$

- 集合差 set difference：

$$
A \backslash B = A \cap B^C \\
\text{A but not B}
$$

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


- 对称差 symmetric difference：

表示两集合中各自独有的元素的集合。

$$
A \oplus B = ( A \backslash B ) \cup ( B \backslash A ) \\
\text{A and not B, or B and not A} \\
\text{A xor B}
$$


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


## 集合操作与子集 Set Operations and Subset

$$
A \cup B = B \ \text{iff} \ A \cap B = A \ \text{iff} \ A \subseteq B
$$

$$
A \oplus A = \empty  \\
A \oplus \empty = A
$$

## 幂集 Power Set

幂集，指一个集合的所有子集，包括了空集和它本身。

## 基数 Cardinality

指集合中元素的数量。它是用来衡量集合大小的属性。

$$
|X| = \#(X) = card(X)
$$

以此，有如下定理：

一个集合的子集数量等于其2的基数幂。

$$
|Pow(X)|=2^{|X|}
$$

另有：

$$
|[m,n]|=n-m+1,\ m<=n,\ m,n \in Z
$$

## 笛卡尔积 Cartesian Product

笛卡尔积（Cartesian Product）是集合论中的一个运算，用来生成由所有可能的**有序对**组成的集合。给定两个集合 A 和 B，它们的笛卡尔积是指形如 (a, b) 的所有有序对的集合，其中 a 属于集合 A，b 属于集合 B。

$$
S \times T=\{(s,t): s \in S, t \in T\} \\
$$

笛卡尔积不支持乘法交换律和乘法结合律。

$$

A \times B \ne B \times A \\

A \times (B \times C) \ne (A \times B) \times C
$$

如果有n个集合，那么它们的笛卡尔积的结果就是所有的有序n元组构成的集合。每个n元组的第i个元素来自集合$S_i$。

$$
\times^n_{i=1}S_i=\{(s_1,...,s_n):s_k \in S_k, \ 1 \le k \le n\} \\
S^2=S \times S \\
S^n = \times_1^nS
$$

有以下基本事实：

$$
\empty \times S=\empty \\
|S \times T| = |S| * |T| \\
|\times^n_{i=1}S_i|= \prod^n_{i=1}|S_i|
$$

注意：$\Pi_n^1$ 是乘积符号（大写的希腊字母Pi），代表累乘。



# 形式化语言 Formal Languages


形式化语言（Formal Language）在数学、逻辑和计算机科学中指的是一套有严格规定的符号和字符串集合，这些字符串是根据某个形式系统的规则从一个字母表中构建的。在形式化语言中，语法规则严格定义了哪些字符串是有效的，哪些不是。这种语言通常用于表达数学、计算机程序的命令和结构以及其他逻辑系统。


## 字母表 Alphabet

一个字母表是一个基本符号或字符的集合，这些符号或字符本身没有预定义的含义。**（有限，非空）**

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

## 字符 Word

字母表中的有限字符序列（字符串）。可以为空，表示为 $λ$ （Lambda）。

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

Concatenation：连接。

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

## 词集 Set of words

通常指的是由特定字母表中的字符构成的所有可能字符串的集合。

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

有以下事实：

$$
\Sigma^1=\Sigma \\
\\
\Sigma^*=\Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...; \ \ 
\Sigma^{\le n}=\bigcup^n_{i=0}\Sigma^i \\
\Sigma^+=\Sigma^1 \cup \Sigma^2 \cup ...=\Sigma^* \backslash \{\lambda\}
$$


## 语言 Languages

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

## 集合操作的形式化语言 Set Operations for Languages

### 字符连接

直接并列写出即可，顺序不可更换。

$$
XY=\{xy: x\in X \ and \ y \in Y\}
$$

### 连续集合内的字符

可以用指数符号与星号代指数量。

$$
X^0=\{\lambda\} \\
X^{i+1}=XX^i \\
X^*=X^0 \cup X^1 \cup X^2 \cup ...
$$


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