# 2020秋-离散数学（1）期末考试

## 总体

比较中规中矩，显著比去年的阴间卷简单。没有延长时间。

题型和祖传的16年样卷基本一致，难度稍大一点。也有一些祖传题目。

感谢我的同学 lzy, pyz 提供了部分试题的回忆。

## 还记得的试题

> 不保证记忆准确性

### 选择题

“爱笑的女孩运气不会太差”可以推出...

### 判断题

> 主要是考察概念和常见反例

SKOLEM标准型和原式在不可满足意义下等价（？）

$A \in B \Lrarr P(A) \in P(B)$

良序集都是全序集。

### 填空题

$\{1,2,3,4,5,6,7,8,9\}$ 上自反的关系个数，自反且对称的关系个数，不自反且也不反自反的关系个数。

### 解答题

> 需要注意相对分值大小，长度差不多的两道题可能一道20分，一道6分

$(\forall x)((P(x) \rarr Q(x))\rarr R(x)) \Rarr(\forall x)(P(x) \and Q(x)) \rarr(\forall x)R(x)$ 仅修改**一个**量词使推理仍然成立，并证明结论。

$(P \or (\lnot Q \rarr \lnot R)) \lrarr (\lnot P \land Q \and \lnot R)$ 的主析取&主合取范式。

$[100,999]$ 中不能被 $6,10,15$ 中任何一个数整除的数的个数。

证明： $(A-B)-C = (A-C)-(B-C)$

用等势的定义证明 $\mathbf R \approx \mathbf R - \mathbf Q$ 。

在自然数集上定义关系 $R$ 。对于自然数 $a,b$ ，$aRb$ 当且仅当 $a$ 的每个十进制位都小于等于 $b$ 的对应十进制位（不存在的位置视作为 $0$）。（1） 证明 $R$ 是偏序关系。（2） 定义集合 $A_1 = \{123,246,294,356, 379,\cdots\}$ （大概七八个三位数，记不住了），$R_1 = R \cap (A_1 \times A_1)$  ，求 $R_1$ 下 $A_1$  在 $\mathbf N$ 上的最小元/最大元/极小元/极大元，画出 $R_1$ 的哈斯图。 

用罗素公理系统证明 $\vdash((P \rarr Q) \or P)$ .

（压轴题）有限集合 $X$ 上的关系 $R_1$，$R_2$ 满足：$R_1 \circ R_2=I_X$ .（1） 试证明存在 $X$ 上的函数 $f_1,f_2$ 使得：$af_1b$ 等价于 $aR_1b$ ，$cf_2d$ 等价于 $cR_2d$  . （2） 若集合 $X$ 是无限集合，上述结论是否成立？成立证明，否则举出反例。