离散数学考试题及详细参考答案 .pdfVIP

离散数学考试题(后附详细答案)

一、命题符号化（共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分）

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)（AB）－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分)

fg

de

bc

a

图1

7.已知有限集S={a,a,…,a},N为自然数集合，R为实数集合，求下列集合的基数

12n

N

n

S;P(S);N,N;P(N);R,R×R,{o,1}（写出即可）(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)

2.设R是A上的等价关系，R是B上的等价关系，A≠且B≠，关系R满足：

12

x,y,x,y∈R，当且仅当x,x∈R且y,y∈R。试证明：R是A×B上的

1122121122

等价关系。（10分）

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

4.设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R

2

的商集A/R有r个元素，证明：rs≥n。（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表示命题“我去看电影”，R表示命题“在家里读书”，S

表示命题“在家看报”，命题符号化为：（P⇄Q）(P⇄RS)

b)设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→

Q

c)设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P

2.用谓词逻辑把下列命题符号化

a)设R(x)表示“x是实数