华南师范大学 计算机学院 2009 －2010 学年第2学期期末考试
《 离散数学I 》课程试卷（A卷）
参考答案及评分标准
一．单选题(本题总分20分，每小题2分) 1．以下语句是命题的是( D )。 A．你喜欢唱歌吗？
2．A={a,b}，B={c,d}，A和B的笛卡尔积A×B是( C )。 A． {
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 / 4
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 )， fog(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之上的等价关系是({
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={
11．A={a,b,c,d}, 以下哈斯图所对应的偏序关系R=({
2 / 4
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 / 4
主合取范式 (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)