离散数学（上）模拟题
1、命题符号化（共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.
2、简答题（共6道题，共32分）
1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范
式，并写出所有成真赋值。

（5分）
2. 设个体域为{1,2,3}，求下列命题的真值（4分）
a) xy(x+y=4)
b) yx (x+y=4)
3. 求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|
5. 设A是有穷集，|A|=5，问（每小题2分，共4分）
a) A上有多少种不同的等价关系？
b) 从A到A的不同双射函数有多少个？
6. 设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小
元，最大元、极大元、极小元、上界集合、下界集合、上确界、
下确界，(5分)
f g
d e
b c
a
图1
7. 已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求
下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即
可）(6分)
3、证明题（共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))，xR(x) xP(x)
2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R
满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且
<y1,y2>∈R2。

试证明：R是A×B上的等价关系。

（10分）
3. 用伯恩斯坦定理证明（0,1]和(a,b)等势。

（10分）
4. 设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个
元素，若A关于R的商集A/R有r个元素，证明：rs≥n2。

（10分）
4、应用题（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.对每一个城市求出从它出发所能够到达的所有其他城市。