2024-2025学年下学期第一二章测验题

2024-2025学年下学期第一二章测验题

一、

Please say which of the following formulas are tautologies, which are contradictions, and which are contingencies. In each case, use truth tables plus accompanying text to prove your claims.

(i) $(p\to q)\lor(q\to p)$

(ii) $p\oplus p$ (where $\oplus$ is the exclusive disjunction)

(iii) $(p\to q)\to(\neg q\to\neg p)$

-------- Aberdeen 2005

---

二、

Translate the following argument into propositional logic, and prove it.

Premises: If it rains then it's wet. If it's wet then I'm miserable. I'm not miserable.

Conclusion: It does not rain.

-------- Aberdeen 2006

---

三、

True or False. You do not need to justify your answers on this problem.

$\mathbb{N}$ denotes the set of natural numbers, $\{0,1,2,\ldots\}$.

$\mathbb{Z}$ denotes the integers, $\{\ldots,-2,-1,0,1,2,\ldots\}$.

( ) (a) If the implication $P\to Q$ is true, then its converse is guaranteed to be true.

( ) (b) $\forall w\in\mathbb{Z}.\exists x\in\mathbb{Z}.\forall y\in\mathbb{Z}.\exists z\in\mathbb{Z}.w+x=y+z$

( ) (c) $\exists x\in\mathbb{N}.\forall p\in\mathbb{Z}.p>5\to x^2\equiv 1\pmod p$

( ) (d) $\forall p\in\mathbb{Z}.p>5\to\exists x\in\mathbb{N}.x^2\equiv 1\pmod p$

-------- Berkeley Fall 2003 Midterm

---

四、

(a) Consider the function $f(x)=20-4x^2$ from the set $\{-3,-2,-1,0,1,2,3\}$ to the set $\{-16,4,16,20,36\}$. Is it an injection? Is it a surjection? Explain your answer.

(b) Is the function $f(x)=2x-1$ a bijection from the set of positive integers to the set of positive integers? Explain your answer.

(c) What is the inverse of $f(x)=5-2x^{3/2}$?

(d) Let $f(x)=x^{2/3}+2x+7$ and $g(x)=3x+4$ be functions from the set of real numbers to the set of real numbers. What is $f\circ g$? And what is $g\circ f$?

-------- Queens Univ October 2006 Test1

---

五、

Give an example of a function $f:\mathbb{N}\to\mathbb{Z}$ that is:

(a) Neither injective nor surjective.

(b) Injective but not surjective.

(c) Surjective but not injective.

(d) Surjective and injective.

-------- Stanford February 2006

---

六、

Prove or give a counterexample for each of the following:

(a) If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

(b) If $A\in B$ and $B\in C$, then $A\in C$.

-------- Stanford February 2007

---

七、

Let us add the following two operations to our dealings with sets:

• Pairwise addition: $A\oplus B:=\{a+b\mid a\in A,\ b\in B\}$ (This is also called the Minkowski addition of sets A and B.)
• Pairwise multiplication: $A\otimes B:=\{a\times b\mid a\in A,\ b\in B\}$

For example, if $A$ is $\{1,2\}$ and $B$ is $\{10,100\}$, then $A\oplus B=\{11,12,101,102\}$ and $A\otimes B=\{10,20,100,200\}$. Please describe the following sets:

i. $\mathbb{N}\oplus\varnothing$;

ii. $\mathbb{N}\oplus\mathbb{N}$

iii. $\mathbb{N}^{+}\oplus\mathbb{N}^{+}$

iv. $\mathbb{N}^{+}\otimes\mathbb{N}^{+}$

-------- Stanford Homework

---

八、

用一阶谓词公式描述下列命题的结构（使用全总个体域）

(a) 自然数不是奇数就是偶数

(b) 没有最大的自然数

---

九、

构造下面推理的证明

前提：

$$\exists xF(x)\to\forall y(G(y)\to H(y)),$$ $$\exists xM(x)\to\exists y(G(y))$$

结论：

$$\exists x(F(x)\land M(x))\to\exists y(H(y))$$

---

十、

设 $A$，$B$，$C$ 为任意的集合，证明：

(1) $(A-B)-C=(A-C)-B$

(2) $A\cap(B\oplus C)=(A\cap B)\oplus(A\cap C)$

说明：$B\oplus C$ 表示集合 $B$ 和集合 $C$ 的对称差，即 $(B\cup C)-(B\cap C)$，也即：$(B-C)\cup(C-B)$。

---

十一、

若 $A$ 是不可列的无限集，$B$ 为无限可列集，且 $A\cap B=\varnothing$，试建立 $A\cup B$ 到 $A$ 的一一对应。

---

十二、

若 $A_1,A_2,\ldots,A_m$ 都是无限集，且都是可列集，并且它们两两互不相交，证明：

$$\bigcup_{i=1}^{m}A_i$$

是可列集。

---

十三、

(ECNU 2024, midterm) Let $A$, $B$ and $C$ be sets. Prove that $B-C\subseteq\overline{A}$ if and only if $A\cap B\subseteq C$.