华南师范大学 计算机学院《离散数学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