Test started Mar 6, 2024 6:00 PM to Mar 13, 2024 6:00 PM

1.1

Question

Consider the relation:

Which of the following properties does R satisfy?

Select all that apply:

- Symmetry (S)
- Transitivity (T)
- Antisymmetry (AS)
- Reflexivity (R)
- Antireflexivity (AR)

Answer

该关系可以被分解为：

那么，我们可以进一步将之写为：

• 选项1：对称性。

无论怎么改变顺序，都不影响它们的值，也就不影响两个数的平方除以5后余数相同，因此这个选项是正确的。

• 选项2：传递性。

无论如何传递，都不影响它们的值，也就不影响三个数的平方除以5后余数相同，因此这个选项是正确的。

• 选项3：反对称性。

既然对称性能选，并且它们可以不相等，因此这个选项是不正确的。

• 选项4：自反性。

相同的数的平方除以5后的余数当然相同，因此这个选项是正确的。

• 选项5：反自反性。

显然，$(m,m)$ 是可以存在在这个关系中的，因此这个选项是错误的。

- Symmetry (S)
- Transitivity (T)
- Reflexivity (R)

1.2

Question

Let $Σ = \{a,b,c\}$ and define a binary relation $R$ on $Σ*$ as follows:

$(w,v) ∈ R$ if and only if $length(w) = length(v)$.

Which of the following is true?

- R is neither an equivalence relation nor a partial order
- R is both an equivalence relation and a partial order
- R is a partial order and not an equivalence relation
- R is an equivalence relation and not a partial order

Answer

根据定义，等价需要满足：自反性，对称性，传递性；偏序需要满足：自反性，反对称性，传递性。

• 自反性。

显然， $(x,x) \in R$，因为相同的字符串长度相等。

• 对称性。

显然，$(x,y) \in R$，同时 $(y,x) \in R$，因为顺序改变不影响它们的长度。

• 传递性。

显然，$(x,y) \in R, (y,z) \in R$，能够推断出 $(x,z) \in R$，因为它们的长度完全相同。

• 反对称性。

显然，在上文对称性的例子中，没有强制要求 $x=y$，因此反对称性不成立。

综上所述，我们可以认为，该关系具有等价关系，而不具有偏序关系。

- R is an equivalence relation and not a partial order

1.3

Question

Consider the poset $\{(1,3,5,9,15,45), \mid \}$

What is glb(15,9)?

- 1
- 3
- 5
- 9
- 15
- 45
- Doesn't exist

Answer

我感觉这个题目多少有点问题，应该写：what is glb({15,9})?

满足能够整除这两个数的元素有：1，3

因此最大的下界元素就是3。

- 3

1.4

Question

True or false:

For all relations $R$, if $R$ is symmetric, then $R = R^←$

Answer

因为具有对称性，所以对于任何反序的数对，其仍然存在于 $R$ 中。因此答案为：

- True

1.5

Question

True or false:

For all relations $R$, if $R$ is transitive and antisymmetric, then $R$ is reflexive

Answer

反例：

这个关系满足传递性、反对称性，但显然不满足自反性。

因此，答案为：

- False

2.1

Let $Σ = {0,1}$ and consider the relation on $Σ^*$ given by $R = \{(w,v) : length(w) ≥ 2 \times length(v)\}$

Which of the following properties does R satisfy?

Select all that apply:

- Antireflexivity (AR)
- Symmetry (S)
- Transitivity (T)
- Reflexivity (R)
- Antisymmetry (AS)

Answer

• 选项1：反自反性。

如果 $x$ 的长度为0，那么 $(x,x)$ 存在与关系 $R$ 中。因此反自反性不成立。

• 选项2：对称性。

显然，长度的二倍关系在调换顺序后并不成立。

• 选项3：传递性。

显然，长度的二倍关系在传递后会变成4倍关系（反正比2倍大），因此总是成立。

• 选项4：自反性。

如果 $x$ 的长度不为0，那么 $(x,x)$ 不存在与关系 $R$ 中。因此自反性不成立。

• 选项5：反对称性。

显然，长度的二倍关系在调换顺序后并不总是成立，除非长度都为0。成立。

综上所述，答案为：

- Transitivity (T)
- Antisymmetry (AS)

2.2

Question

Which of the following relations (over $ℕ$) are also functions? Select all that apply:

- The | relation
- The ≤ relation
- The = relation
- The relation {(n-1, n) : n ∈ ℕ > 0}
- The relation {}
- The relation {(n, m, n+m) : n,m ∈ ℕ}

Answer

对于集合 $S$ 中的每一个元素 $s$，都有且只有一个元素$t$ 在集合 $T$ 中与之关联。

• 选项1：整除

这显然是不对的。对于这个关系来说，一个输入可以有很多输出。即：一个数可以被很多数整除，因此不满足定义。

• 选项2：小于等于

这显然是不对的。对于这个关系来说，一个输入可以有很多输出。即：一个数可以大于等于很多数，因此不满足定义。

• 选项3：等于

对于这个关系来说，一个输入可以有很多输出。即：一个数可以一个数，因此满足定义。（这是个偏序关系）

• 选项4：某种运算定义

这个关系意为一个数对，该数对内容为$(n-1,n)$。我们每输入一个数 $n$ 就可以得到一个唯一的 $n-1$，因此满足定义。（这是个等价关系）

• 选项5：空函数

它没有输入，没有输出。

• 选项6：某种运算定义

这是个三元组，完全违反了函数的定义。（需要是一个二元关系）

综上所述，答案为：

- The = relation
- The relation {(n-1, n) : n ∈ ℕ > 0}

2.3

Question

Let $F=ℕ^ℕ$ denote the set of functions from ℕ to ℕ. Define the relation $R$ on $F×F$ as follows:

Which of the following properties does $R$ satisfy?

- Antisymmetry (AS)
- Transitivity (T)
- Symmetry (S)
- Reflexivity (R)
- Antireflexivity (AR)

Answer

关系R在函数集F上定义，如果函数f和g在自然数集N上只有有限个n使得f(n) ≠ g(n)，那么f和g就处于这个关系R中。

太抽象的话，想象函数的图像，该关系被描述为两图像仅有有限个交点。

因此，答案为：

- Transitivity (T)
- Symmetry (S)
- Reflexivity (R)

2.4

Question

Let $F=ℕ^ℕ$ denote the set of functions from ℕ to ℕ. Define the relation $R$ on $F×F$ as follows:

Which of the following properties does $R$ satisfy?

- Reflexivity (R)
- Transitivity (T)
- Antisymmetry (AS)
- Symmetry (S)
- Antireflexivity (AR)

Answer

关系R在函数集F上定义，如果函数f和g在自然数集N上有无穷个n使得f(n) 小于等于 g(n)，那么f和g就处于这个关系R中。

太抽象的话，想象函数的图像，该关系被描述为f(n)有无穷个点是在g(n)下方的。（有一小段就行，因为可以无限微分）

• 选项1：自反性

显然是成立的，自己肯定无限等于自己。

• 选项2：传递性

想想f,g,h。如果f有一小段小于等于g，g有一小段小于等于h，但这并不代表f有一小段能小于等于h，因为(f,g)、(g,h)关系成立的区间可能是不相同的。因此不成立。

• 选项3：反对称性

如果(f,g)存在，那么(g,f)就一定不存在吗？未必，只需要g也有一小段小于f就可以了。不成立。

• 选项4：对称性

如果(f,g)存在，那么(g,f)就一定存在吗？也未必，只需要g永远大于f就可以了。不成立。

• 选项5：反自反性

显然是不成立的，因为自反性成立了。

综上所述，答案为：

- Reflexivity (R)

2.5

Question

Let $Σ = \{0,1\}$ and define $f:Σ^*×Σ^*→Σ^*$ and $g,h,k:Σ^*→Σ^*$ as follows:

$f(v,u) = uv \text{ for all } v,u ∈ Σ^*$

$g(w) = f(01,w)$

$h(w) = f(10,w)$

$k = g∘h$

What is g(110)?

What is h(110)?

What is k(110)?

Answer

g(110) = f(01, 110) = 11001

h(110) = f(10, 110) = 11010

k(110) = g(h(100)) = g(11010) = 1101001