《离散数学I》模拟试题
一、单选题（每小题2分，共20分）
1 以下语句是命题的是（ B ）。 A． y等于x。 B． 每个自然数都是奇数。 C． 请爱护环境。 D． 你今天有空吗？
2 设α是一赋值，α(p)= α(q)=1，α(r)=0，下列公式的值为真的是（ B ）。 A．p∧(q∨r) B．(pr) ? (?rq) C．(rq) ∧(qp) D．(rq)
3 以下联结词的集合（ D ）不是完备集。 A．{?,∧,∨, ,?} B．{?,∧,∨} C．{?, } D．{∧,∨}
4 公式A的对偶式为A*，下列结果成立的是（ D ）。 A．A?A* B．?A?A* C．A|=|A* D．?A|=|A*
5 假设论域是正整数集合，下列自然语言的符号化表示中，（ A ）的值是真的。 A．?x?yG(x,y)，其中G(x,y)表示xy=y B．?x?yF(x,y)，其中F(x,y)表示x+y=y C．?x?yH(x,y)，其中H(x,y)表示x+y=x D．?x?yM(x,y)，其中M(x,y)表示xy=x
6．以下式子错误的是（ D ）。 A．?x?A(x) |=| ??xA(x)
B．?x(A(x)∧B(x)) |=| ?xA(x)∧?x B(x) C．?x(A(x)∨B(x)) |=| ?xA(x)∨?x B(x) D．?x(A(x)∨B(x)) |=| ?xA(x)∨?x B(x)
7. 下列式子（ C ）不正确。 A．{x}∈{{x}} B．{x}∈{{x},x} C．{x}?{{x}} D．{x}?{{x},x}
8. 下列性质正确的是（ D ）。 A．如果A∈B，B∈C，则A∈C C．如果A?B，B∈C，则A∈C
B．如果A∈B，B?C，则A?C D．如果A∈B，B?C，则A∈C
9. 下列说法错误的是（ A ）。
A． 如果R不是自反关系，则R是反自反关系 B． 自反关系的关系矩阵的主对角线元素皆为1 C． 自反关系的关系图每个结点都有一条闭路 D．包含关系?是自反关系
10. 设、都是集合A到集合B的关系，则下列等式错误的是（ B ）。
~
A． ~~= B． ()~=~
~
C． ()~=~ D． ()~=~ ~ 一、单选题（20分） 1 B 2 B (题目改为公式真值为假的是) 3 D 4 D 5 A 6．D 7. C 8. D 9. A 10. B
二、填空题（每小题2分，共20分）
1．句子“只有小王爱唱歌，他才会弹钢琴。”中，把“小王爱唱歌”形式化为命题符p，“小王会弹钢琴”形式化为命题符q，则句子形式化为公式 。 2．公式?(?p∧?q)∨(?p∧q)∨t的对偶是 。 3．公式?xA(x)??xB(x)的前束范式是 。
4．公式?xA(x)∨B(y)中，?量词的辖域是 ，自由变元是 。 5．集合{a,{a,b}}的基数是 ，幂集是 。 6. A={1,3,5}，B={2,3,4}，U={0,1,2,3,4,5,6}，(A∪B-A∩B)-= 。 7． A={a,b,c}，B={x,y,z}，C={1,2,3}，R1={
8．设集合A={0,1,3}上的关系?={<0,1>,<1,3>}，则自反闭包r(?)= ，对称闭包s(?)= 。
9．集合A={a,b,c}，A的一个划分{{a},{b,c}}定义的A之上的等价关系是 。
10．以下哈斯图所对应的序关系是 。
二、填空题（20分） 1．q→p 2．?(?p∨?q)∧(?p∨q)∧f 3．
4．A(x), y
5．2, {Φ,{a},{{a,b},{a,{a,b}}} 6. {0,3,6}
7．{
8．{<0,0>,<1,1>,<3,3>,<0,1>,<1,3>}, {<0,1>,<1,0>,<1,3>,<3,1>} 9．{
10．{
三、计算题（30分）
1．（6分）用等值演算法计算命题公式(?p??q)?(p??q)的析取范式和主析取范式。 2．（7分）设A={1,2,3,4}，A上的关系R={
（3）有多少不同的从X到Y的单射、满射和双射？ 要求写出分析、计算过程。 4．（6分）集合A={1，2，3，4，6，8，12，24}，A上的偏序关系={
（2）求出B的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下界。 5．（4分）设A={1,2,3,4}，构造一个函数f:A→A，使f不是A上的相等关系IA，但f°f=IA。构造一个函数g: A→A，使g2(x)=g(x)。 三、计算题（30分） 1．
倒数第二步可以算做析取范式；最后一步既是析取范式也是主析取范式。 2．（1）R={<1,1>,<2,4>}
（2）沃夏尔算法得t(R)=R。没有增加序偶，原关系具有传递性。
3．(1)29 (2)33
(3)单射：3！＝6 满射：6 双射：6 4．（1）
（2）B的极大元：3，4；极小元：2，3；最大元：无；最小元：无； 上界：12，24；下界：1；最小上界：12；最大下界：1。
5．f、g 都有多个解。
f={<1,2>,<2,1>,<3,4>,<4,3>}
g=IA,或g可以是有传递性的任何函数，例如g={<1,2>,<2,2>,<3,4><4,4>}
四、证明题（20分）
1．（6分）用讨论指派的方法证明A→(B→C)|=| (A→B)→(A→C)