《离散数学I》模拟试题

《离散数学I》模拟试题

一、单选题（每小题2分，共20分）

1 以下语句是命题的是（ B ）。 A． y等于x。 B． 每个自然数都是奇数。 C． 请爱护环境。 D． 你今天有空吗？

2 设α是一赋值，α(p)= α(q)=1，α(r)=0，下列公式的值为真值为假的是（ ）。 A．p∧(q∨r) B．(p?r) ? (?r?q) C．(r?q) ∧(q?p) D．(r?q)

3 以下联结词的集合（ D ）不是完备集。 A．{?,∧,∨, ?,?} B．{?,∧,∨} C．{?, ?} D．{∧,∨}

4 公式A的对偶式为A*，下列结果成立的是（ ）。 A．A?A* B．?A?A* C．A|=|A* D．?A|=|A*

5 假设论域是正整数集合，下列自然语言的符号化表示中，（ ）的值是真的。 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．以下式子错误的是（ ）。 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. 下列式子（ ）不正确。 A．{x}∈{{x}} B．{x}∈{{x},x} C．{x}?{{x}} D．{x}?{{x},x}

8. 下列性质正确的是（ ）。 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． 如果R不是自反关系，则R是反自反关系 B． 自反关系的关系矩阵的主对角线元素皆为1 C． 自反关系的关系图每个结点都有一条闭路 D．包含关系?是自反关系

10. 设?、?都是集合A到集合B的关系，则下列等式错误的是（ ）。 A． ?~~=? B． (???)~=?~??~ C． (???)~=?~??~ D． (???)~=?~? ?~

二、填空题（每小题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={,,,}，R2={,}，R1oR2= 。

8．设集合A={0,1,3}上的关系?={<0,1>,<1,3>}，则自反闭包r(?)= ，对称闭包s(?)= 。

9．集合A={a,b,c}，A的一个划分{{a},{b,c}}定义的A之上的等价关系是 。

10．以下哈斯图所对应的序关系是 。

三、计算题（30分）

1．（6分）用等值演算法计算命题公式(?p??q)?(p??q)的析取范式和主析取范式。 2．（7分）设A={1,2,3,4}，A上的关系R={|a,b∈A且a=b2}。 （1）画出R的关系图，写出其关系矩阵； （2）通过关系矩阵求出R的传递闭包t(R)。 3．（7分）令X={1,2,3}，Y={a,b,c}， （1）有多少不同的从X到Y的关系？ （2）有多少不同的从X到Y的映射？

（3）有多少不同的从X到Y的单射、满射和双射？ 要求写出分析、计算过程。 4．（6分）集合A={1，2，3，4，6，8，12，24}，A上的偏序关系?={|x,y?A且y能

被x整除}，B={2,3,4}， （1）画出哈斯图；

（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)。

四、证明题（20分）

1．（6分）用讨论指派的方法证明A→(B→C)|=| (A→B)→(A→C) 2．（6分）设A和B为两个集合，证明A?B当且仅当A∪B=B（6分）

3．（8分）设R是集合A上的关系。令S={(a,b)| ?c∈A,使(a,c)∈R且(c,b)∈R}。证明：如果R是等价关系，则S也是等价关系。

五、综合题（10分）

在谓词逻辑自然推理系统FND中，构造下面的证明。要求写出所有谓词的含义，分别写出前提、结论和证明过程。

“某学术会议的每个成员都是专家也是工人。有些成员是青年人。所以，有些成员是青年专家。”

《离散数学I》模拟试题参考答案

一、1 B

6．D

2 B 3 D 7. C 8. D

4 D 5 A

9. A 10. B

二、填空题（20分）

1．q→p

2．?(?p∨?q)∧(?p∨q)∧f 3． ?x(?A(x)?B(x))

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．

(?p??q)?(p??q)|?|?(?p??q)?(p??q)?(?q?p)|?|(p?q)?(?p??q)?(q?p)|?|(p?q)?(?p?p)?(?p?q)?(?q?p)?(?q?q)|?|(p?q)?(?p?q)?(p??q)

倒数第二步可以算做析取范式；最后一步既是析取范式也是主析取范式。 2．（1）R={<1,1>,<2,4>}

?1?0??0??0000000000?1?? 0??0?（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．证明：当赋值α使左式为真时，有α(A)=0或α(A)=1且α(B→C)=1。 当α(A)=0时，α(A→B)＝α(A→C)＝1，所以α((A→B)→(A→C))＝1。 α(A)=1且α(B→C)=1时，有α(B)＝0或α(B)＝1且α(C)＝1。 α(A)=1且α(B)＝0时，α(A→B)＝0，α((A→B)→(A→C))＝1。

α(A)=1且α(B)＝1且α(C)＝1时，α(A→B)＝α(A→C)＝1，所以α((A→B)→(A→C))＝1。 因此A→(B→C)|= (A→B)→(A→C)。

当赋值α使右式为真时，为证α((A→B)→(A→C))＝1时有α(A→(B→C))＝1，等价于证α(A→(B→C))＝0时有α((A→B)→(A→C))＝0。

α(A→(B→C))＝0时，α(A)=1且α(B→C)=0，即α(A)=1且α(B)＝1且α(C)＝0。此时α(A→B)＝1，α(A→C)＝0，所以α((A→B)→(A→C))＝0。 因此(A→B)→(A→C)|= A→(B→C)。 因此A→(B→C)|=| (A→B)→(A→C)。 2．（1）首先证A?B时有A∪B=B。

为证A∪B=B成立，证A∪B?B且B?A∪B。 对任意x∈B，有x∈A∪B，所以B?A∪B。

对任意x∈A∪B，有x∈A或x∈B。因为A?B，所以x∈A时有x∈B。所以A∪B?B。 所以A∪B=B。

（2）证A∪B=B时有A?B。

对任意x∈A，由∪定义有x∈A∪B。因为A∪B=B，所以x∈B。所以A?B。

3．（1）对任意x∈A，因为R有自反性，所以∈R。由S定义知∈C。所以S有自反性。 （2）设∈S，则?c∈A,使∈R且∈R。因为R有对称性，则∈R且∈R，则∈S，所以S有对称性。

（3）设∈S且设∈S，由S的定义知?c∈A,使∈R且∈R，?d∈A,使∈R且∈R。因为R有传递性，所以∈R 且∈R 。则∈S 。所以S有传递性。

五、综合题（10分）

解答：设谓词：S(x): x是专家；W(x): x是工人；Y(x): x是青年人。 前提：?x(S(x)?W(x)),?xY(x); 结论：?x(S(x)?Y(x)) 证明过程：

（1）?xY(x) 前提引入 （2）Y(c)

（1），ES

前提引入

（3）?x(S(x)?W(x))

（4）S(c)∧W(c) (3), US

（5）S(c) (4) T, I （6）S(c) ∧Y(c) (2)(5) T, E （7）?x(S(x)?Y(x))

(6), EG

本文来源：https://www.bwwdw.com/article/e94v.html