# 离散数学 (A) 2018年机经 by 相逢有时 @学习部 考试时间：2019年01月11日 ## 总体情况 题量和16年差不多，难度比16年和样卷都要大得多。不仅考察了细枝末节的各类知识点（比如良序集、求闭包的顺序等，考点几乎没有死角），而且要求灵活运用所学知识，有较高思维难度，题目的综合性和交叉性很大。 考完基本上是跪了，所调查范围内的同学没有一位表示做完了题目，最后两题没做是常态，普遍表示整体难度都很大。（笔者也是在心态爆炸中艰难地写完本片机经的orz） 某大佬的做题感言： > 五教气候温暖宜人，试卷印刷清晰，考试氛围良好，明年还会继续体验。 ## 选择题 - 有一个关于命题的定义的，有点坑。答案似乎是选“含命题变项”的一项 - 有一个关于集合对称差的，简单 - 有一个关于存在、任意两次的使用的，简单 - 关于关系的题目，较难：设xRy表示x是y的父亲，xSy表示x是y的母亲。问以下哪种关系表示x是y的妻子？ 1. R o S^-1 2. S o R^-1 3. R^-1 o S 4. S^-1 o S - 关于集合运算的题目，选择错误的一项，较难。 - 关于连续统假设和集合基数的问题，中等。 - …… ## 判断题 - 集合 A∈B 等价于 P(A) ∈ P(B) - 良序集不一定是全序集（虽然良序集好像不在考纲里，但他还是考了orzorz） - …… ## 填空题 - 波兰表达式：!P V (Q ^ !R) V !!Q（大概是） - 基数运算题，简单。（如 ∩{23, 43} ) - 给一个10元素的集合，给一种划分{{1,2,3,4}, {5,6,7}, {8,9}, {10}}，问等价关系中有序对的个数。(30) - 关系的计数，较难。问，对于元素个数为n的集合A，A上的以下关系分别有多少种？（用n表示） - 自反关系 - 反自反关系 - 对称关系 - 反对称关系 - 非自反且非反自反关系 - 自反并且对称的关系 ## 大题 题量大，笔者写满了整个答卷orz。难度阶梯明显 - 有一个关于容斥原理，简单：给了三个集合A、B、C中A和B的元素个数，给了全集元素个数，给了ABC任意两个的交的元素个数，给了A交B交C的元素个数，叫你求C的元素个数。 - 有一个主合取、主析取范式的题目，较简单：命题很长，直接化简十分麻烦（含双箭头和很多单箭头），但是整个式子只含P、Q两个命题，所以可以直接打表（枚举4次就完了，很简单）或者写成极小式再析取。 - 有一个命题形式化的题目，第一个难度较大： - 过平面上的不共线的三点，有且仅有一个圆。（注意三点不共线、有且仅有、三点共圆的形式化） - 数列A（下标从0到n-1）是升序列。 - 证明： (A-B)对称差(A-C) = ∅ 等价于 A∩B = A∩C - 证明：左边是一个前束范式，右边是一个范式。简单。 - 哈斯图，难度较大。 定义集合 $ A = \{2, 2^2, ..., 2^{12}\} $ 偏序关系 $ R = \{ | x \in \N_+ \and y \in \N_+ \and (\exist p) (p \in \N_+ \and y = x^p)\} ​$ 1. 求 $ R_1 = (A \times A) \cap R​$ 的哈斯图（建议表示成2的指数形式，这样容易发现指数之间是简单的整除关系） 2. 求 $R_1$ 最小元、最大元、极小元、极大元。 3. 在 $ \N_+ $ 上求 $$ 的上下界、上下确界。（用最小公倍数和最大公约数来求解） 4. 求所有最长链、最长反链（这个有点多，要仔细数） - 函数构造题，综合性、难度较大。（4分） 设 $\N \to \Z$ 的函数 $f(t) = a t^2 + c$ ，其中a、c都是可以调节的自然数。试构造 $\N \to \Z$ 的**不依赖于a、c的取值**的函数$g(t)$，使得对于**任意**的 $a, c \in \N$ ，始终存在 $t_0 \in \N$，使得 $f(t_0) = g(t_0)$ 例如，当c = 0时，可以构造 $g(t) = t^3​$，这样对于任意的a，可以取$t_0 = a​$，$f(t_0) = g(t_0) = a^3​$ 1. 设 $c \in \{0, 1\}​$，构造 g(t) 2. 设 c 可以是任何自然数，构造 g(t) （思路大概是要构造 $\N \to \Z^2​$ 的双射，by耀神） - 用罗素公理系统证明 $ p \leftrightarrow p $ 是重言式。卷尾给了3条定义、4条公理、7条定理。较难。（5分）