2014-2015学年下学期期中

2014-2015学年下学期期中试卷

一、（6 分）

Let $P(m,n)$ be the statement "$m\mid n$", where the domain for both variables consists of all positive integers. Determine the truth values of each of these statements.

(a) $P(4,5)$

(b) $P(2,4)$

(c) $\forall m\forall nP(m,n)$

(d) $\exists m\forall nP(m,n)$

(e) $\exists n\forall mP(m,n)$

(f) $\forall nP(1,n)$

说明：By "$m\mid n$", which we say as "$m$ divides $n$", we mean that $n=km$ for some integer $k$.

---

二、（5 分）

证明下面的公式（不用真值表方法）

$$(p\to q)\lor(r\to q)\equiv (p\land r)\to q$$

---

三、（6 分）

Use rules of inference to show that

if

$$\forall x(P(x)\to(Q(x)\land S(x)))$$

and

$$\forall x(P(x)\land R(x))$$

are true, then

$$\forall x(R(x)\land S(x))$$

is true.

---

四、（6 分）

试用一阶谓词公式描述下面的命题结构（要求使用全称个体域）

(a) 偏序集 $(A,\le)$ 有最小元（即：the least element）

(b) 存在实数 $x$ 和 $y$，使得 $x$ 与 $y$ 之和大于 $x$ 与 $y$ 之积。

---

五、（4 分）

Express the negations of each of these statements so that all negation symbols immediately precede predicates.

(a) $(\exists z)(\forall y)(\forall x)T(x,y,z)$

(b) $(\exists x)(\exists y)P(x,y)\land(\forall x)(\forall y)Q(x,y)$

---

六、（13 分）

按要求完成下列各题：

(1) 判断下列命题的真假：

(a) $v\in\{\{v\}\}$，

(b) $\{v\}\in\{\{v\}\}$

(2) 问 $A\subseteq B$，$A\in B$ 是可能的吗？若是可能的，请举例说明。

(3) 设 $A,B,C,D$ 为任意集合，判断下列命题是否成立，若成立，请给出证明，否则请举一个反例。

(a) 如果 $A\subseteq B$ 且 $C\subseteq D$，那么 $(A\cup C)\subseteq(B\cup D)$

(b) 如果 $A\subset B$ 且 $C\subset D$，那么 $(A\cup C)\subset(B\cup D)$

---

七、（8 分）

Give an example of a function form $\mathbb{N}$ to $\mathbb{N}$ that is

(a) One-to-one but not onto.

(b) Onto but not one-to-one.

(c) Both onto and one-to-one (but different from the identity function).

(d) Neither one-to-one nor onto.

---

八、（7 分）

Show that the union of a countable number of countable sets is countable.

---

九、（6 分）

Determine whether the relation $R$ on the set of all real numbers is reflexive, irreflexive, symmetric, antisymmetric, and/or transitive, where $(x,y)\in R$ if and only if $x=1$ or $y=1$.

Please note: If a property is not satisfied, please provide one counterexample.

---

十、（17 分）

按要求完成下列各题：

(1) 令关系 $R$ 为 $\{(1,2),(1,3),(2,3),(2,4),(3,1)\}$，关系 $S$ 为 $\{(2,1),(3,1),(3,2),(4,2)\}$。

求：$S\circ R$

(2) 令 $A=\{a,b,c\}$，试给出 $A$ 上两个不同的关系 $S$ 和 $T$，使得

$$S^2=S,\qquad T^2=T.$$

(3) 设 $A=\{1,2,3,4,5\}$，$R$ 是 $A$ 上的等价关系，且 $R$ 在 $A$ 上的等价类是：

$$\{1,2\},\qquad \{3,4,5\}$$

求：$R=?$

(4) 设 $A=\{1,2,3,4,5,6\}$，关系 $R$ 为 $A$ 上的关系，

$$R=\{(1,5),(2,5),(3,1),(3,3),(4,5)\}$$

(a) 画出 $R$ 的关系图；

(b) 求关系 $R$ 的传递闭包。

(5) 设集合 $X$ 的元素个数为 $n$，问 $X$ 上有多少种对称关系，并请简述理由。

---

十一、（10 分）

设 $R$ 为 $\mathbb{N}\times\mathbb{N}$ 上的二元关系，$\forall(a,b),(c,d)\in\mathbb{N}\times\mathbb{N}$，

$$(a,b)R(c,d)\quad\text{当且仅当}\quad b=d$$

(1) 证明：$R$ 为 $\mathbb{N}\times\mathbb{N}$ 上的等价关系；

(2) 求 $[(a,b)]_R=?$

---

十二、（12 分）

设 $(A,R)$ 为偏序集，在 $A$ 上定义新关系 $S$ 如下：

对任意 $x,y\in A$，$xSy$ 当且仅当 $yRx$

(1) 证明：$S$ 也是 $A$ 上的偏序关系；

(2) 如果 $R$ 是整数集合上的小于或等于关系，那么 $S$ 是什么关系；如果 $R$ 是正整数集合上的整除关系，那么 $S$ 是什么关系；

(3) 偏序集 $(A,R)$ 和 $(A,S)$ 中的极大元、极小元、最大元、最小元等之间是什么关系？