2024-2025学年下学期期中

2024-2025学年下学期期中试卷（A）（含答案）

一、Logic (5 questions, 35 points)

1. (6 points) Determine the truth value of each of these statements if the universe of discourse for all variables consists of all integers.

   1. $\forall x\exists y(x+y=1)$
   2. $\exists x\exists y(x+2y=2 \land 2x+2y=5)$
   3. $\exists x\forall y(x<y^2)$
   解：

   1. T
   2. F
   3. T

   ---

2. (5 points) 证明下面的公式（不用真值表方法）

   $$\neg(p\leftrightarrow q)\equiv ((p\lor q)\land \neg(p\land q)).$$
   解：

   $$\begin{aligned} \text{左边} &\equiv \neg((p\to q)\land(q\to p)) && \text{等价等值}\\ &\equiv \neg((\neg p\lor q)\land(\neg q\lor p)) && \text{蕴含等值}\\ &\equiv \neg(\neg p\lor q)\lor\neg(\neg q\lor p) && \text{德摩根律}\\ &\equiv (p\land\neg q)\lor(q\land\neg p) && \text{德摩根律}\\ &\equiv (p\lor q)\land(p\lor\neg p)\land(\neg q\lor q)\land(\neg q\lor\neg p) && \text{分配律}\\ &\equiv (p\lor q)\land\neg(p\land q)\\ &\equiv \text{右边}. \end{aligned}$$

   ---

3. (9 points) 将下列命题符号化（要求使用全总个体域）

   1. 火车比轮船快
   2. 在北京工作的人未必都是北京人
   3. 部分序集 $(A,\le)$ 没有最大元
   解：

   （1）令 $F(x)$：$x$ 是火车，$G(y)$：$y$ 是轮船，$H(x,y)$：$x$ 比 $y$ 快。

   $$\forall x\forall y((F(x)\land G(y))\to H(x,y)).$$

   （2）令 $P(x)$：$x$ 是北京人，$Q(x)$：$x$ 在北京工作。

   $$\neg\forall x(Q(x)\to P(x)).$$

   （3）令 $P(x)$：$x\in A$，$Q(x,y)$：$x\le y$。

   $$\neg\exists x(P(x)\land\forall y(P(y)\to Q(y,x))).$$

   ---

4. (7 points) 试证明下面的推理为有效推理

   前提：

   $$\forall x(F(x)\lor G(x))$$ $$\forall x(G(x)\to \neg R(x))$$ $$\forall xR(x)$$

   结论：

   $$\forall xF(x)$$
   解：

   1. $\forall x(G(x)\to\neg R(x))$，前提引入。
   2. $G(a)\to\neg R(a)$，由（1）UI 规则。
   3. $\forall xR(x)$，前提引入。
   4. $R(a)$，由（3）UI 规则。
   5. $\neg G(a)$，由（2）（4）拒取。
   6. $\forall x(F(x)\lor G(x))$，前提引入。
   7. $F(a)\lor G(a)$，由（6）UI 规则。
   8. $F(a)$，由（5）（7）析取三段论。
   9. $\forall xF(x)$，UG 规则。

   ---

5. (8 points) 判断如下的结论是否正确

   1. $\forall x(A(x)\land B(x))\equiv \forall xA(x)\land \forall xB(x)$
   2. $\exists x(A(x)\land B(x))\equiv \exists xA(x)\land \exists xB(x)$
   3. $\forall x(A(x)\lor B(x))\equiv \forall xA(x)\lor \forall xB(x)$
   4. $\exists x(A(x)\lor B(x))\equiv \exists xA(x)\lor \exists xB(x)$
   解：

   1. True.
   2. False.
   3. False.
   4. True.

---

二、Sets and Functions (3 questions, 20 points)

6. (6 points) Let $A,B$ and $C$ be sets. Prove that

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

   if and only if $C\subseteq A$.

   解：

   $\Rightarrow$：若 $(A-B)\cup C=A-(B-C)$，则

   $$C\subseteq (A-B)\cup C=A-(B-C)\subseteq A.$$

   $\Leftarrow$：若 $C\subseteq A$，则

   $$\begin{aligned} (A-B)\cup C &=(A\cap \overline{B})\cup C\\ &=(A\cup C)\cap(\overline{B}\cup C)\\ &=A\cap(\overline{B}\cup C)\qquad //\text{ because }C\subseteq A\\ &=A\cap\overline{(B\cap\overline{C})}\\ &=A-(B-C). \end{aligned}$$

   ---

7. (8 points) Determine whether these statements are true or false.

   1. $\varnothing\in\{\{\varnothing\}\}$.
   2. If $A$ and $B$ are both uncountable sets, then $A\cap B$ is also uncountable.
   3. The mapping $f$ from $\mathbb{R}$ to $\mathbb{R}$ defined by $f(x)=\dfrac{1}{x^2}$ is a function which is neither onto nor one-to-one.
   4. The mapping $f$ from $\mathbb{R}$ to $\mathbb{R}$ defined by $f(x)=2-2x$ is a function which is both onto and one-to-one.
   解：

   1. False.
   2. False. If $A=\mathbb{R}^+$ and $B=\mathbb{R}^-$, then $A\cap B=\varnothing$.
   3. False. $f$ is not a function since it is undefined at $x=0$.
   4. True.

   ---

8. (6 points) Suppose $A$ is an infinite set. Prove that $A$ has a proper subset $B$ (i.e., $B\subset A$) such that $|A|=|B|$.

   解：

   Since $A$ is infinite, it has a infinite countable subset $A_0\subseteq A$. Suppose

   $$A_0=\{a_1,a_2,a_3,\ldots\}.$$

   Let

   $$B=A-\{a_1\}.$$

   We can construct a bijection $f$ from $A$ to $B$ as:

   $$f(x)= \begin{cases} x, & x\in A-A_0,\\ a_{i+1}, & x=a_i. \end{cases}$$

   Thus we have $|A|=|B|$ and complete the proof.

---

三、Relations (4 questions, 45 points)

9. (10 points) 设 $R\subseteq A\times A$，分别定义以下操作：

   • $r(R)$：对 $R$ 取自反闭包
   • $s(R)$：对 $R$ 取对称闭包
   • $t(R)$：对 $R$ 取传递闭包

   （1）请考虑两个组合操作：

   $$R_1=t(s(r(R)))$$ $$R_2=s(t(r(R)))$$

   请证明或举反例说明：是否恒有 $R_1=R_2$？若成立请证明；若不成立，请给出一个集合 $A$ 和关系 $R$ 的具体例子，并分别写出 $R_1$ 与 $R_2$。

   （2）是否存在一个唯一的最小关系 $S(R\subseteq S)$，同时满足以下三个性质：自反性、对称性、传递性。如果存在，请说明该关系 $S$ 的构造方法；如果不存在，请说明原因。

   解：

   （1）不成立。举例 $A=\{1,2,3\}$，$R=\{(1,3),(2,3)\}$。

   $$\begin{aligned} R_1 &=t(s(r(R)))\\ &=\{(1,1),(2,2),(3,3),(1,3),(2,3),(3,1),(3,2),(1,2),(2,1)\}. \end{aligned}$$$$\begin{aligned} R_2 &=s(t(r(R)))\\ &=\{(1,1),(2,2),(3,3),(1,3),(2,3),(3,1),(3,2)\}. \end{aligned}$$

   $R_2$ 不包含 $(1,2)$ 和 $(2,1)$，两者不相等。

   （2）存在唯一的最小关系 $S$，即 $R$ 的等价闭包。构造方法为：先取 $R$ 的自反闭包 $r(R)$，再取对称闭包 $s(r(R))$，最后取传递闭包 $t(s(r(R)))$。

   ---

10. (10 points) Considering relations on the set $A=\{1,2,3,\ldots,100\}$ consisting of the first 100 positive integers, please answer the following questions:

    (a) How many nonzero entries does the matrix representing the relation have if $R=\{(a,b)\mid a>b\}$;

    (b) How many relations are there on set $A$ that are asymmetric（非对称）;

    (c) How many relations are there on set $A$ that are both symmetric and antisymmetric（对称且反对称）.

    解：

    (a)

    $$\binom{100}{2}=4950.$$

    (b)

    $$3^{\frac{100^2-100}{2}}=3^{4950}.$$

    (c)

    $$2^{100}.$$

    仅包含自环，每个元素可选是否包含自环。

    ---

11. (12 points) Given a function $f:X\to Y$, define the relation

    $$R=\{(x_1,x_2)\mid f(x_1)=f(x_2),\ x_1,x_2\in X\}.$$

    (a) Prove that the relation $R$ is an equivalence relation.

    (b) Give the corresponding set $B$ of all equivalence classes.

    (c) Define the function $g:B\to f(X)$ by $g([x])=f(x)$. Prove that $g$ is a bijective function.

    解：

    (a) To prove that $R$ is an equivalence relation, we need to show that it satisfies reflexivity, symmetry, and transitivity.

    1. Reflexivity: For any $x\in X$, we have $f(x)=f(x)$. Therefore, $(x,x)\in R$. This shows that $R$ is reflexive.
    2. Symmetry: If $(x,y)\in R$, then $f(x)=f(y)$. This implies $f(y)=f(x)$, so $(y,x)\in R$. This shows that $R$ is symmetric.
    3. Transitivity: If $(x,y)\in R$ and $(y,z)\in R$, then $f(x)=f(y)$ and $f(y)=f(z)$. This implies $f(x)=f(z)$, so $(x,z)\in R$. This shows that $R$ is transitive.

    Since $R$ satisfies all three properties, it is an equivalence relation.

    (b) The set of equivalence classes $B$ is given by the partition of $X$ induced by the relation $R$. Each equivalence class consists of all elements in $X$ that are related to each other under $R$. Formally, the set of equivalence classes $B$ is:

    $$B=\{[x]\mid x\in X\},$$

    where

    $$[x]=\{y\in X\mid (x,y)\in R\}=\{y\in X\mid f(x)=f(y)\}.$$

    (c) Define $g:B\to f(X)$ by

    $$g([x])=f(x).$$

    We need to show that $g$ is both injective (one-to-one) and surjective (onto).

    Injectivity: Suppose $g([x])=g([y])$. Then $f(x)=f(y)$. By the definition of equivalence classes, $x$ and $y$ are in the same equivalence class, i.e., $[x]=[y]$. Therefore, $g$ is injective.

    Surjectivity: For any $y\in f(X)$, there exists some $x\in X$ such that $f(x)=y$. Then $g([x])=f(x)=y$. This shows that every element in $f(X)$ is the image of some equivalence class in $B$. Therefore, $g$ is surjective.

    Since $g$ is both injective and surjective, it is a bijective function.

    ---

12. (13 分) 设 $\Pi_n$ 表示集合 $S_n=\{1,2,\ldots,n\}$ 的所有划分构成的集合。给定集合 $S_n$ 上的两个划分 $P_1=\{A_1,A_2,\ldots,A_r\}$ 和 $P_2=\{B_1,B_2,\ldots,B_s\}$，若对于每个 $A_j$ 均有某个 $B_k$，使 $A_j\subseteq B_k$，则称 $P_1$ 是 $P_2$ 的加细，记为 $P_1\preceq P_2$。

    (a) 证明：集合 $(\Pi_n,\preceq)$ 是一个偏序集。

    (b) 对于 $n=3$，画出偏序集 $(\Pi_n,\preceq)$ 的哈斯图。

    (c) 对于 $n=5$，求 $\{P_1,P_2\}$ 的最大下界和最小上界，其中 $P_1=\{\{1,2\},\{3\},\{4,5\}\}$，$P_2=\{\{1\},\{2,3\},\{4\},\{5\}\}$。

    解：

    (a) To show that $(\Pi_n,\preceq)$ is a poset, we need to verify three properties:

    1. Reflexivity: For any partition $P\in\Pi_n$, clearly every block of $P$ is a subset of itself, so $P\preceq P$.

    2. Antisymmetry: Suppose $P_1\preceq P_2$ and $P_2\preceq P_1$. Let $X\in P_1$. Since $P_1\preceq P_2$, there exists $Y\in P_2$ such that $X\subseteq Y$. Since $P_2\preceq P_1$, there exists $Z\in P_1$ such that $Y\subseteq Z$. But $X\subseteq Y\subseteq Z$ and $X,Z\in P_1$. Since the sets in a partition are non-overlapping, $X=Y=Z$. Similarly, for any set in $P_2$, it is equal to a set in $P_1$. Thus, $P_1=P_2$, and the relation is antisymmetric.

    3. Transitivity: If $P_1\preceq P_2$ and $P_2\preceq P_3$, then any block of $P_1$ is contained in some block of $P_2$, which in turn is contained in some block of $P_3$. Thus $P_1\preceq P_3$.

    Therefore, $(\Pi_n,\preceq)$ is a poset.

    (b) For $n=3$, the set $S_3=\{1,2,3\}$ has 5 partitions:

    $$P_0=\{\{1\},\{2\},\{3\}\}\quad\text{(finest partition)}$$$$P_1=\{\{1\},\{2,3\}\}$$$$P_2=\{\{1,2\},\{3\}\}$$$$P_3=\{\{1,3\},\{2\}\}$$$$P_4=\{\{1,2,3\}\}\quad\text{(coarsest partition)}$$

    The Hasse diagram is:

           P4
        /  |  \
      P1   P2   P3
        \  |  /
           P0

    (c) Given:

    $$P_1=\{\{1,2\},\{3\},\{4,5\}\},\qquad P_2=\{\{1\},\{2,3\},\{4\},\{5\}\}.$$

    Greatest Lower Bound: The meet is the finest partition that is coarser than both $A_1$ and $A_2$. We find it by taking pairwise intersections:

    • The element $1$ is merged with $2$ in $A_1$, but forms a separate block in $A_2$. Therefore, $1$ must form a separate block on its own.
    • The element $2$ is merged with $1$ in $A_1$ and with $3$ in $A_2$. Therefore, $2$ must form a separate block on its own.
    • Through similar analysis, it can be concluded that all elements form separate blocks.

    $$GLB=\{\{1\},\{2\},\{3\},\{4\},\{5\}\}.$$

    Least Upper Bound (LUB): The join is the coarsest partition that refines both $A_1$ and $A_2$. We find it by taking connected components of the union:

    • The block $\{1,2\}$ of $A_1$ and the block $\{2,3\}$ of $A_2$ intersect due to the element $2$, and they are merged into $\{1,2,3\}$.
    • The block $\{4,5\}$ of $A_1$ is split into $\{4\}$ and $\{5\}$ in $A_2$. However, since the LUB needs to be coarser than $A_1$, the block $\{4,5\}$ is retained.

    $$LUB=\{\{1,2,3\},\{4,5\}\}.$$