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

1华南师范大学计算机学院2009－2010学年第2学期期末考试《离散数学I》课程试卷（A卷）参考答案及评分标准一．单选题(本题总分20分，每小题2分)1．以下语句是命题的是(D)。A．你喜欢唱歌吗？B．x+y=20C．给我一杯水吧！D．若7+818，则三角形有4条边。2．A={a,b}，B={c,d}，A和B的笛卡尔积A×B是(C)。A．{a,c,a,d}B．{}C．{a,c,b,d,b,c,a,d}D．{a,c,a,d}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}}B．{{1,2},{3},{4}}C．{{1,2},{3,4}}D．{,{1,2,3},{4}}5．下列式子(D)不正确。A．{}B．{}{{}}C．{}D．{}{{}}6．假设论域是整数集合，下列自然语言的符号化表示中，(C)的值是假的。A．xyG(x,y)，其中G(x,y)表示xy=xB．yxH(x,y)，其中H(x,y)表示xy=xC．yxF(x,y)，其中F(x,y)表示x+y=10D．xyM(x,y)，其中M(x,y)表示x+y=1027．以下联结词的集合(D)不是完备集。A．{,,,,}B．{,,}C．{,}D．{,}8．下面哪个谓词公式是前束范式(C)。A．x(A(x)B(x))B．xA(x)xB(x)C．xx(A(x)B(x))D．xx(A(x)B(x))9．以下式子错误的是(D)。A．xA(x)xA(x)B．x(A(x)B(x))xA(x)xB(x)C．x(A(x)B(x))xA(x)xB(x)D．x(A(x)B(x))xA(x)xB(x)10．以下命题公式是重言式的是(D)。A．q(pq)B．((pq)qC．((pq)q)pD．((pq)q)p二．填空题(本题总分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)=({a,,a,{a},a,{b},a,{a,b},b,,b,{a},b,{b},b,{a,b}})。4．设p：我生病，q：我去学校，则句子“只有在生病时，我才不去学校”符号化为公式(qp)。5．集合A={a,b,c,d}，A上的一个划分π={{a,b},{c,d}}，与π对应的A之上的等价关系是({a,b,b,a,c,d,d,c}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))zC(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={a,b,b,b,b,c,c,d}，t(R)=({a,b,b,b,b,c,c,d,a,c,a,d,b,d})。11．A={a,b,c,d},以下哈斯图所对应的偏序关系R=({a,c,b,d,b,c,d,c}IA)。3主析取范式(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)三．计算/简答题(本题总分20分，每小题10分)1．(10分)用等值演算法求公式(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)bdac主合取范式(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)4证明：1F(a)前提引入2x(F(x)G(x))前提引入3F(a)G(a)2UI4G(a)13假言推理5H(a)前提引入6x(G(x)H(x)I(x))前提引入7G(a)H(a)I(a)6UI8G(a)H(a)45合取9I(a)78假言推理评分标准：符号化表示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,x,xBB。因为AA=BB，则x,xAA。从而xA。故BA。(3)同理可证，AB。故B=A。评分标准：第(1)步3分,第(2)步5分,后面2分