您好,欢迎来到华佗健康网。
搜索
您的当前位置:首页华南师范大学 计算机学院《离散数学I》模拟试题(带答案)

华南师范大学 计算机学院《离散数学I》模拟试题(带答案)

来源:华佗健康网


华南师范大学 计算机学院 2009 -2010 学年第2学期期末考试

《 离散数学I 》课程试卷(A卷)

参及评分标准

一.单选题(本题总分20分,每小题2分) 1.以下语句是命题的是( D )。 A.你喜欢唱歌吗?

2.A={a,b},B={c,d},A和B的笛卡尔积A×B是( C )。 A. {, } B.{} C.{, , , }

3.设A={a,{a}},下列命题错误的是( B )。

A.{a}P(A) B.{a}P(A) C.{{a}}P(A) D.{{a}}P(A)

4.设A={1, 2, 3, 4},下列( D )不是A的划分。 A.{{1}, {2}, {3}, {4}}

5.下列式子( D )不正确。 A.{}

6.假设论域是整数集合,下列自然语言的符号化表示中,( C )的值是假的。 A.xyG(x,y),其中G(x,y)表示xy=x B.yxH(x,y),其中H(x,y)表示xy=x C.yxF(x,y),其中F(x,y)表示x+y=10 D.xyM(x,y),其中M(x,y)表示x+y=10

B.{}{{}} C.{} D.{}{{}}

B.{{1, 2}, {3}, {4}}

D.{, {1, 2, 3}, {4}}

C.{{1, 2}, {3, 4}}

D.{, }

B.x+y=20

C.给我一杯水吧! D.若7+818,则三角形有4条边。

1

7.以下联结词的集合( D )不是完备集。 A.{, , , , } B.{, , }

8.下面哪个谓词公式是前束范式( C )。 A.x(A(x)B(x))

9.以下式子错误的是( 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)

10.以下命题公式是重言式的是( D )。 A.q(pq)

二.填空题(本题总分30分,每空2分)

1.实数集上的函数f(x)=2x2+1,g(x)= -3x+10,g-1(x)=( (10-x)/3 ), fºg(x)= ( -6x2+7 )。 2.谓词公式x(P(x) yR(y)) Q(x)中量词x的辖域是(P(x)yR(y))。

3.若A={a,b},则A×P(A)=({, , , , , , , })。

4.设p:我生病,q:我去学校,则句子“只有在生病时,我才不去学校”符号化为公式 (qp)。

5.集合A={a,b,c,d},A上的一个划分π={{a, b},{c, d}},与π对应的A之上的等价关系是({, , , }IA)。

6.设S={1,2,3,4},A上的关系R={<1,2>,<2,1>,<2,3>,<3,4>},则RR=({<1,1>,<1,3>,<2,2>,<2,4>}),R-1 ={<2,1>,<1,2>,<3,2>,<4,3>}。 7.集合A上的等价关系的三个性质是 (自反性、对称性和传递性)。

8.公式x((A(x)B(y,x))z C(y,z))D(x)中,自由变元是(x, y),约束变元是(x, z)。 9.A={1,2,3,4},B={3,4,5},全集E={0,1,2,3,4,5,6,7}, A(AB)=({0,3,4,5,6,7}), ( B - A)= ({0,1,2,3,4,6,7})。

10. A={a,b,c,d}, A之上的关系R={, , , }, t(R)=( {, , , , , , })。

11.A={a,b,c,d}, 以下哈斯图所对应的偏序关系R=({, , , }IA)。

2

C.{, } D.{, }

B.xA(x) xB(x)

D.xx (A(x) B(x))

C.xx (A(x) B(x))

B.((pq)q

D.((pq)q)p

C.((pq)q)p

a

c

d b

三.计算/简答题(本题总分20分,每小题10分)

1.(10分)用等值演算法求公式(pq)r的主合取范式和主析取范式。 解:

主析取范式 (pq)r (pq(rr))((pp) (qq)r) (pqr)(pqr)) (pqr) (pqr)  (pqr)  (pqr) (pqr)(pqr))(pqr)(pqr)  (pqr) 评分标准:主合取范式和主析取范式各5分

2.(10分) 求公式的前束范式:(x1F(x1, x2)x2G(x2))x2H(x1, x2) 解: (x1F(x1, x2)x2G(x2))x2H(x1, x2)

 (x1F(x1, x2)x3G(x3))x4H(x5, x4)  x1x3(F(x1, x2)G(x3))x4H(x5, x4)  x1x3x4((F(x1, x2)G(x3))H(x5, x4)) 评分标准:老师根据过程给分

四.证明题(本题总分30分,每小题10分)

1.(10分) 在自然推理系统N中构造下面推理的证明(个体域为人的集合)。

每个科学工作者都是刻苦钻研的,每个刻苦钻研而又聪明的人在他的事业中将获得成功。张三是科学工作者,并且他是聪明的,所以张三在他的事业中将获得成功。

设F(x): x是科学工作者,G(x): x是刻苦钻研的,H(x): x是聪明的,I(x): x在事业中将获得成功。

前提:x(F(x) G(x)), x(G(x) H(x) I(x)), a: 张三, F(a), H(a) 结论:I(a)

3

主合取范式 (pq)r (pr) (qr) (p( qq)r)(( pp)qr) (pqr) (pqr)( pqr)(pqr) (pqr) (pqr)(pqr) 证明:1 F(a) 前提引入 2 x(F(x) G(x)) 前提引入 3 F(a) G(a) 2 UI

4 G(a) 1 3 假言推理 5 H(a) 前提引入 6 x(G(x) H(x) I(x)) 前提引入 7 G(a) H(a) I(a) 6 UI 8 G(a) H(a) 4 5 合取 9 I(a) 7 8 假言推理 评分标准:符号化表示4分,推理过程6分

2.(10分) 若R和S都是非空集A上的等价关系,则RS是A上的等价关系。 证明:

aA,因为R和S都是A上的等价关系,所以xRx且xSx。故xRSx。从而RS是自反的。

a,bA,aRSb,即aRb且aSb。因为R和S都是A上的等价关系,所以bRa且bSa。故bRSa。从而RS是对称的。

a,b,cA,aRSb且bRSc,即aRb,aSb,bRc且bSc。因为R和S都是A上的等价关系,所以aRc且aSc。故aRSc。从而RS是传递的。AB

故RS是A上的等价关系。

评分标准:三个性质每个3分,总结一分

3.(10分) 对任意集合A,B,证明:若AA = BB,则A=B。 证明:

(1)若B=,则BB=。从而AA =。故A=。从而B=A。

(2)若B,则BB。从而AA。

对xB, BB。因为AA = BB,则AA。从而xA。故BA。 (3)同理可证,AB。 故B=A。

评分标准:第(1)步3分, 第(2)步5分, 后面2分

4

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo0.com 版权所有 湘ICP备2023021991号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务