跳到主要内容

2014-2015学年下学期期中

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

一、（6 分）​

Let P(m,n)P(m,n) be the statement "m∣nm\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)P(4,5)

(b) P(2,4)P(2,4)

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

(d) ∃m∀nP(m,n)\exists m\forall nP(m,n)

(e) ∃n∀mP(m,n)\exists n\forall mP(m,n)

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

说明：By "m∣nm\mid n", which we say as "mm divides nn", we mean that n=kmn=km for some integer kk.

二、（5 分）​

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

(p→q)∨(r→q)≡(p∧r)→q(p\to q)\lor(r\to q)\equiv (p\land r)\to q

三、（6 分）​

Use rules of inference to show that

if

∀x(P(x)→(Q(x)∧S(x)))\forall x(P(x)\to(Q(x)\land S(x)))

and

∀x(P(x)∧R(x))\forall x(P(x)\land R(x))

are true, then

∀x(R(x)∧S(x))\forall x(R(x)\land S(x))

is true.

四、（6 分）​

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

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

(b) 存在实数 xx 和 yy，使得 xx 与 yy 之和大于 xx 与 yy 之积。

五、（4 分）​

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

(a) (∃z)(∀y)(∀x)T(x,y,z)(\exists z)(\forall y)(\forall x)T(x,y,z)

(b) (∃x)(∃y)P(x,y)∧(∀x)(∀y)Q(x,y)(\exists x)(\exists y)P(x,y)\land(\forall x)(\forall y)Q(x,y)

六、（13 分）​

按要求完成下列各题：

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

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

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

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

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

(a) 如果 A⊆BA\subseteq B 且 C⊆DC\subseteq D，那么 (A∪C)⊆(B∪D)(A\cup C)\subseteq(B\cup D)

(b) 如果 A⊂BA\subset B 且 C⊂DC\subset D，那么 (A∪C)⊂(B∪D)(A\cup C)\subset(B\cup D)

七、（8 分）​

Give an example of a function form N\mathbb{N} to N\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 RR on the set of all real numbers is reflexive, irreflexive, symmetric, antisymmetric, and/or transitive, where (x,y)∈R(x,y)\in R if and only if x=1x=1 or y=1y=1.

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

十、（17 分）​

按要求完成下列各题：

(1) 令关系 RR 为 {(1,2),(1,3),(2,3),(2,4),(3,1)}\{(1,2),(1,3),(2,3),(2,4),(3,1)\}，关系 SS 为 {(2,1),(3,1),(3,2),(4,2)}\{(2,1),(3,1),(3,2),(4,2)\}。

求：S∘RS\circ R

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

S2=S,T2=T.S^2=S,\qquad T^2=T.

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

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

求：R=?R=?

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

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

(a) 画出 RR 的关系图；

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

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

十一、（10 分）​

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

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

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

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

十二、（12 分）​

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

对任意 x,y∈Ax,y\in A，xSyxSy 当且仅当 yRxyRx

(1) 证明：SS 也是 AA 上的偏序关系；

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

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