文档介绍：a 离散数学考试题( 后附详细答案) 一、命题符号化(共 6 小题,每小题 3 分,共计 18 分) 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨,我去看电影,否则就在家里读书或看报。 b) 我今天进城,除非下雨。 c) 仅当你走,我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数 x ,总存在 y 使得 xy=1 。 c)f 是从 A到B 的函数当且仅当对于每个 a∈A 存在唯一的 b∈B ,使得 f(a)=b. 二、简答题(共 6 道题,共 32 分) 1. 求命题公式(P→(Q→ R)) (R→(Q→ P)) 的主析取范式、主合取范式, 并写出所有成真赋值。(5 分) {1,2,3} ,求下列命题的真值( 4 分) a)x y(x+y=4) b)yx (x+y=4) x(F(x) → G(x)) →( xF(x) → xG(x)) 的前束范式。(4 分) 4. 判断下面命题的真假,并说明原因。(每小题 2 分,共 4 分) a)(AB )- C=(A-B) (A-C) b)若f 是从集合 A 到集合 B 的入射函数,则|A|≤|B| 是有穷集, |A|=5 ,问(每小题 2 分,共 4 分) a)A 上有多少种不同的等价关系? b)从A到A 的不同双射函数有多少个? 6. 设有偏序集<A, ≤> ,其哈斯图如图 1 ,求子集 B={b,d,e} 的最小元,最大元、极大元、极小元、上界集合、下界集合、上确界、下确界, (5分) fgdebc图1 7. 已知有限集 S={a 1 ,a 2,…,a n },N 为自然数集合, R 为实数集合,求下列集合的基数 S;P(S);N,N n ;P(N);R,R × R,{o,1} N (写出即可) (6分) 三、证明题(共 3 小题,共计 40 分) 1. 使用构造性证明,证明下面推理的有效性。(每小题 5 分,共 10 分) a)A→(B∧ C),(E → F)→ C,B→(A∧ S)B→E b) x(P(x) → Q(x)), x(Q(x) ∨ R(x)) ,x R(x) x P(x) 1是A 上的等价关系, R 2是B 上的等价关系, A≠且B≠,关系 R 满足: <<x 1 ,y 1 >,<x 2 ,y 2 >> ∈R ,当且仅当<x 1,x 2>∈R 1且<y 1 ,y 2>∈R 2 。试证明: R是A×B 上的等价关系。( 10 分) 3. 用伯恩斯坦定理证明( 0,1] 和(a,b) 等势。( 10 分) 是集合 A 上的等价关系,A 的元素个数为 n,R 作为集合有 s 个元素,若A 关于 R 的商集 A/R 有r 个元素,证明: rs≥n 2。( 10 分) 四、应用题( 10 分) 在一个道路上连接有 8 个城市, 分别标记为 a,b,c,d,e,f,g,h 。城市之间的直接连接的道路是单向的,有 a→ b,a→ c,b→ g,g→ b,c→ f,f→ e,b→ d,d→ f. 对每一个城市求出从它出发所能够到达的所有其他城市。离散数学考试题答案一、命题符号化(共 6 小题,每小题 3 分,共计 18 分) 1. 用命题逻辑把下列命题符号化 a)设P 表示命题“上午下雨”,Q 表示命