QUIZ 3



## 1.1

### Question

Consider the graph with:

- vertex set `{0,1}×{0,1}×{0,1}`
- an edge between two vertices if they differ in exactly two co-ordinates

What is the degree sequence of this graph?

Select one alternative:
```
- 1,1,1,1,1,1,1,1
- 0,0,2,2,2,2,0,0
- 0,4,4,0,0,00,0,0
- 0,0,0,8,0,0,0,0
- None of the above
```

### Answer

首先这是一个无向图。

其次，这个顶点集的坐标是一个三阶向量，每一位都由0或1组成。因此，顶点有如下几种：

```
(0,0,0) (0,0,1) (0,1,0) (0,1,1)
(1,0,0) (1,0,1) (1,1,0) (1,1,1)
```

现在，对相互之间位数差异位2的点互相连线以构成边，所以只需要考虑哪些点跟其相差有2即可。

但换句话说，这也可以考虑保留一位，另外两位都不同即可。而每一个坐标一共有三位，所以每个点都可以与另外三个点进行连线，换句话说每个点都有三个度。


因此，答案为：

```
3,3,3,3,3,3,3,3

None of the above
```

## 1.2

### Question

Which of the following graphs are isomorphic to this graph:


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

Select all that apply:

![](https://rin977.com/static/img/ae6b3fb5bcdab36f7eb61c3782c35620.image.webp)


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


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


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


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


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

### Answer

画图，设点，一点点推，找到矛盾边、矛盾点即可排除。

答案为：

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

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

## 1.3

### Question

Starting from Vertex 0, which of the following sequences of vertices could arise as a sequence of explored vertices when performing a breadth-first traversal (according to lectures)?


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

Select all that apply:

```
- 0,2,1,3,5,4,8,6,7
- 0,1,2,3,6,5,4,7,8
- 0,3,2,1,4,5,6,8,7
- 0,3,5,8,7,6,4,2,1
- 0,1,3,4,5,8,7,6,2
- 0,1,2,3,4,5,6,7,8
```

### Answer

该图像的同构如图所示：

```
        0
     /  |  \
    3 - 2 - 1
  / |   |
4 - 5   6
    |   |
    8 - 7
```

则根据广度优先算法，我们应当为每一层先进行遍历，再进行下一层。

答案为：

```
- 0,1,2,3,6,5,4,7,8
- 0,3,2,1,4,5,6,8,7
- 0,1,2,3,4,5,6,7,8
```

## 1.4

### Question

Starting from Vertex 0, which of the following sequences of vertices could arise as a sequence of explored vertices when performing a depth-first traversal (according to lectures)?

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

Select all that apply:

```
- 0,1,3,4,5,8,7,6,2
- 0,3,2,1,4,5,6,8,7
- 0,2,1,3,5,4,8,6,7
- 0,3,5,8,7,6,4,2,1
- 0,1,2,3,6,5,4,7,8
- 0,1,2,3,4,5,6,7,8
```

### Answer

可以自己画图试验一下，一个一个试即可。注意：需要给每一个还未遍历但已经被父节点发现的点标注深度，并且一个点不能被重复标注深度。

答案为：

```
- 0,1,3,4,5,8,7,6,2
- 0,3,5,8,7,6,4,2,1
```

## 1.5

### Question

Which of the following properties does this graph have?


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

Select all that apply:

```
- Contains a cycle of length 10
- Bipartite
- Planar
- Hamiltonian path
- Connected
- Chromatic number 3
- Clique number 2
- Eulerian path
```

### Answer

首先为图中的每个点标注序号，方便进行表示。


![0f56485d2899a9d2f2e5b0f3f62f0bdd.png](/static/img/edd7c289e77ade337b8e3b32e1024eac.0f56485d2899a9d2f2e5b0f3f62f0bdd.webp)

- 选项1：循环路径如下。

$$
1 \to 2 \to 3 \to 10 \to 7 \to 5 \to 8 \to 11 \to 9 \to 4 \to 1
$$

- 选项2：通过染色法可尝试证明。如果图能被着成二色，说明是二分的。

$$
black: [1] \\
white: [2, 4, 5, 6] \\
black: [3, 7, 8, 9] \\
white: [10, 11] \\
$$

- 选项3：显然它没有任何的边有相交，因此它是平面的。
- 选项4：不存在，难以证明，但确实不存在。
- 选项5：正确的，每一对顶点都存在路径到达。
- 选项6：上文以证明，色数为2。
- 选项7：由于色数大于等于团数，因此团数最大为2。而找到一条边即包含两个顶点，因此团数可以为2。
- 选项8：对于连通图来说，存在欧拉路径的条件式每个点的度数为偶数或恰好两个顶点的度数是奇数。显然，2, 4, 5, 6, 7, 9, 10, 11的度数都为基数，因此不存在欧拉路径。

因此，答案为：

```
- Contains a cycle of length 10
- Bipartite
- Planar
- Connected
- Clique number 2
```

## 2.1

### Question

Which of the following statements are true for any graph with n≥1 vertices and m≥0 edges?

Select all that apply:

```
- If m < n then the graph is acyclic
- If m ≥ n-1 then the graph is connected
- If m ≥ n then the graph contains a cycle
- If m < n-1 then the graph is not connected
```

### Answer

- 选项1：错误。例如，当前有一个点离散在外，另外n-1个点首尾相接，满足m=n-1<n，然而该图具有环。
- 选项2：错误。例如，当前有一个点离散在外，另外n-1个点首尾相接，满足m=n-1，然而该图并不连通。
- 选项3：正确。在一个有 n 个顶点的图中，如果有至少 n 条边，那么至少有一个顶点的度数大于 1，这意味着在这些顶点中形成了一个环。因为一棵树（没有环的连通图）恰好有 n-1 条边，所以任何边数超过 n-1 的图至少有一个环。
- 选项4：正确。一个有 n 个顶点的图要形成连通图，至少需要 n-1 条边来形成一棵树（树是最少边数的连通图）。如果边的数目少于 n-1，那么一定存在至少一个顶点与图的其他部分不连通。

因此，答案为：

```
- If m ≥ n then the graph contains a cycle
- If m < n-1 then the graph is not connected
```

## 2.2

### Question


Let D0, D1, D2, D3 be the degree sequence of a tree with n≥2 vertices (assume Dk = 0 for k≥4)

Which of the following must necessarily hold:

Select all that apply

```
- D1 is even
- D3 ≥ D2
- D2 ≥ D3
- D1 = 2 + D3
- D0 = 0
- D1 ≥ 2
```

### Answer

对于一棵有 n 个顶点的树，以下性质始终成立：

- 它有 n-1 条边。
- 至少有两个顶点的度数是 1（也就是说，至少有两个叶子节点）。
- 树中没有度数为 0 的顶点，因为树是连通的。

由于在大于等于4的情况下，Dk=0，我们可以认为没有度数大于等于4的节点。

---

- 选项1：错误。至少有两个顶点度数是1，但不一定意味着一直都是偶数。反例如下，D1=3
  ```
   o  o  o
   |  |  |
   o  o  o
    \ | /
      o
  ```
- 选项2：错误。反例如下，D3=1，D2=3
  ```
   o  o  o
   |  |  |
   o  o  o
    \ | /
      o
  ```
- 选项3：错误。反例如下，D3=1，D2=0
  ```
   o  o  o
    \ | /
      o
  ```
- 选项4：正确。设一棵树T有n个顶点，那么它有n-1条边，度数总数则为2(n-1) = 2n-4。由于树没有环，所以每增加一个度数为3的顶点，必须至少增加两个度数为1的顶点（叶子节点）来保持树的结构。这是因为度数为3的顶点在不增加环的情况下提供了两个额外的边缘连接点，这些连接点必须由叶子节点来平衡，因为叶子节点只会增加一个连接点。
- 选项5：正确。树是连通的，因此不存在度数为0的点。
- 选项6：正确。树中至少有两个叶子结点。


因此，答案为：

```
- D1 = 2 + D3
- D0 = 0
- D1 ≥ 2
```

## 2.3

### Question


Which of the following graphs have an Eulerian circuit?

Select all that apply

- $K_{5,5}$
- All graphs with degree sequence 0,0,5,0,5
- All regular graphs with 5 vertices and 10 edges
- All graphs with degree sequence 0,0,3,0,3,0,3
- $K_5$
- $K_{5,5,5}$

### Answer

存在欧拉回路的条件：

1. 所有的点的度数都为偶数。
2. 不满足1，那么需要恰好有两个点的度数为奇数。

- 选项1：错误。由于每一个点都和另外集合内所有点有对应关系，因此所有的点的度数都为5。
- 选项2：错误。不连通。
- 选项3：正确。由于10 = 5*(5-1)，所以这个图是一个完全图。每一个点的度数均为5-1=4。
- 选项4：错误。不连通。
- 选项5：正确。这个图是一个完全图。每一个点的度数均为5-1=4。
- 选项6：正确。这个图是一个完全三部图，每一个点的度数为5+5=10。

因此，答案为：

```
- All regular graphs with 5 vertices and 10 edges
- K_5
- K_{5,5,5}
```

## 2.4

### Question


Let G be a finite directed graph where every vertex has in-degree and out-degree at most 1.

True or false:

G has a vertex of out-degree 0 if and only if G has a vertex of in-degree 0.

### Answer

在一个有限的有向图G中，如果每个顶点的入度和出度最多为1，这意味着每个顶点要么与一个其他顶点相连（作为其唯一的前驱或后继），要么完全不与任何顶点相连（入度和出度都为0）。

为了理解为什么这个陈述是真的，我们可以考虑以下情况：

如果G有一个出度为0的顶点，那么这意味着有一个顶点没有指向任何其他顶点的边。由于图是有限的，并且每个顶点的连接数是受限的（最多1个出度和1个入度），这意味着必须有至少一个顶点的入度为0，因为否则会形成一个封闭的环，使得每个顶点都有出度和入度，这与假设矛盾。

反过来，如果G有一个入度为0的顶点，这意味着有一个顶点没有任何从其他顶点指向它的边。考虑到图中顶点数量有限，以及每个顶点的连接数受限，这就意味着必须有至少一个顶点的出度为0，以防止形成一个完全封闭的环路。否则，如果每个顶点都有一个出度，那么每个顶点也必须有一个入度，以保持平衡，这会导致每个顶点既是某个环的一部分，又是该环的出发点，这与入度为0的假设矛盾。

因此，这个陈述展示了在这种类型的图中，出度为0的顶点的存在必然意味着有一个入度为0的顶点的存在，反之亦然。这是由于图的有限性和每个顶点入度及出度的限制共同决定的。

因此，答案为：

```
True
```

## 2.5

### Question

True or false:

If a graph has chromatic number at least 3, then it must contain a subdivision of K3

### Answer

显然错误。一个环图如果有奇数个点，那么它的色数必然等于3，然而一个环图并不一定是 $K_3$。

因此，答案为：

```
False
```

COMP9020 Quiz 3

COMP9020 3.1 Graph Theory

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)