离散数学一、二章检测题及答案

1、天津理工大学中环信息学院?离散数学?第一、二章检测题请将填空题答案填入下面相应位置I. ；2.；3.；4.；5.6.；7.；8.；9.；10.II. ；12.；13.；14.；15.请将选择题答案填入下表相应位置12345678910得分一、填空题(每空2分，共30分)1设P表示“我将去书店 ，Q表示“我有时间，那么命题“我将去书店，仅当我有时间符号化为 。 P Q2设P表示“天下雨 ，Q表示“我骑自行车上班，那么命题“除非下雨，否那么我骑自行车上班符号化为 。P Q3写出下表中各列所定义的命题联结词PQP工QP_QP A QPQ001001011100100 1001111114.设命题公式

2、A的真值表为PQR000001010011100101110111A00101100那么命题公式 A的主析取范式为 ,主合取范式为(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设个体域 A a,b,c，消去公式中的量词，那么 (x)P(x) A ( x)Q(x)P(a) P(b) P(c) (Q(a) Q(b) Q(c)6.命题公式PQ的逆反式是。QP7.设命题公式(PQ)的主析取范式为(P Q) (QP)。8.谓词公式(x)P(x) ( x),(x)P(x)(x)P(x), P(x)9设G(x)表示“ x是金

3、子，F(x)表示“ x是闪光的，那么命题“金子是闪光的，但闪光的不一定是金子符号化为(x)(G(x)F(x)( x)(F(x)G(x)或(x)(G(x)F(x)( y)(F(y)G(y)2N10. N个命题变元可以构成互不等价的命题公式 个。(2)、单项选择题(每题2分，共20 分)1.设S(x)表示x是演员。T(x)表示x是老师，A(x, y)表示x钦佩y。那么命题“所有演 员都钦佩某些老师符号化为(2)。(1) . x(S(x) A(x, y) ;(2). x(S(x) y(T(y) A(x, y);(3) . ( x)( y)(S(x) T(y) A(x, y) ；(4) . ( x)(

4、 y)(S(x) T(y) A(x,y).2 .以下蕴含式不成立的是(1).(1).x(F(x)G(x)xF(x)xG(x) ;(2).x(F(x)G)xF(x);.x(F(x)G(x)xF(x)xG(x) ；(4).x(F(x)G)xF(x).以下等价式不成立的是(2).(1).x(F(x)G(x)xF(x)xG(x);.x(F(x)G(x)xF(x)xG(x).x(F(x)G)xF(x) G.x(F(x) G) xF(x) G(1) x(P(x) yR(x,y)；(2) P(x)；(3) Q(x)；(4) (P(x) yR(x, y) 5 .以下哪个命题是真命题(2) (1) 如果2 +3

5、=5，那么太阳从西方升起；(2)如果2 +3=6，那么太阳从西方升起；(3) 严禁吸烟；(4)我正在说谎6 .谓词演算中，P(a)是(x)P(x)的有效结论，其理论依据是(1) (1) 全称指定规那么( US)；(2) 全称推广规那么( UG)；(3) 存在指定规那么(ES);(4)存在推广规那么(EG 7 以下哪个命题是假命题(1)(1) 如果2是偶数，那么一个命题公式的析取范式唯一；(2) 如果2是偶数，那么一个命题公式的析取范式不唯一；(3) 如果2是奇数，那么一个命题公式的析取范式唯一；(4) 如果2是奇数，那么一个命题公式的析取范式不唯一.&以下公式中不是前束范式的是(3) (1)

6、( x)( y)(Q(x)R(y)；(2) ( x)( y)( z)(Q(x,z)R(x,y,z)；(3) Q(x,z) ( x)( y)R(x,y,z)；(4)( x)( y)Q(x,y) 9以下等价公式正确的选项是()。( 2)(1) P QQP；( 2)PQP Q ；( 3) P QQ P ；4)PQQP10以下推理错误的选项是()。(2)(1) P, P QQ；(2)PQP；(3) Q,P QP；(4)P,PQQ三、简答题 (每题 6 分，共 12 分)1.求谓词公式(x)( P(x) Q(x, y)(y)P(y) ( z)Q(y, z)的前束析取范式.( x)(P(x)Q(x,y)(

7、 y)P(y) ( z)Q(y,z)( x)(u)( z)( P( x)Q(x, y) (P(u)Q( y, z)求命题公式(PQ) R)P 的主析取范式和主合取范式。(PQ)R)P(PQ) R)P 1分(PQ)R)P 1分(PR)(QR) PP(QR)(P(QQ)(R R)(P P) (QR)1分(PQR) (PQ R)(P Q R)(PQR)(PQR)( P QR) 1分(PQR) (PQ R)(P Q R)(PQR)m2m4m5 m6 m7 这是主析取范式 1分M0M1M 3 这是主合取范式(PQR) (PQ R)(P Q R)1分(2( P Q R)四证明题 共 38 分( x)( P

8、(x) Q(x, y)(x(P(x) x(P(x)Q(x,y)Q(x,y)( y)P(y) ( z)Q(y,z) y)P(y) ( z)Q(y,z) u)P(u) ( z)Q(y,z)1. 10分符号化以下命题并推证其结论.任何人如果他喜欢音乐 , 他就不喜欢体育每个人或者喜欢体育，或者喜欢美术有的人不喜欢美术.因而有的人不喜欢音乐.A x :x喜欢美术.该命题符号化为：x M xf(设 M(x) : x 喜欢音乐， S(x) : x 喜欢体育，S ( x) A( x) (S (x )V A (x) A( x)( S( x)V A( x)，( x) A( x)(1)P(3)( 2)(4)I P

9、(6)(7)E(5)( 8)I(9)A (x)t( ( x) M (x) 前提：(x) ( M( xS (x),(结论：( x) M( x) 证：( 1 )( x) A ( x)P( 2) A( a)ES( 3 )(x)( S( x)V A( x )( 4 ) S( a)V A( a )US( 5 ) S( a)T(6) ( x) ( M( x)t S (x)(7) M (a S (a)US(8) S (aM (a)T( 9) M( a)T( 10 )( x ) M ( x )EG2. (12 分)用 CP规那么证明 P ( Q R), Q (R S), P Q S ;1.PP6.(R S)T

10、(4,5) I(1分2.P(QR) P7.RT(3,4) I(1分3.QRT(1,2) I(2 分) 8.ST(6,7)I ( 1分4.QP(附加前提 9.(Q S)CP 1 分5.Q(RS) P(2) .用归谬法证明AB,( CB),C SA.证:1AP 附加前提 1 分2 A BP3BT1,2I( 1 分) 4CBP5CT3,4I(1 分) 6CSP7CT6I(1 分) 8CCT5,7I 1 分由 8 得出了矛盾，根据归谬法说明原推理正确1 分3. 6 分 指出下面推理证明过程中的错误 , 并给出正确的证明. 用谓词演算的推理规那么证明 :x(Q(x) R(x) x(Q(x)Z(x)x(R

11、(x)Z(x)证 : (1)x(Q(x) R(x)P(6)Z(a)T(4) I(2)Q(a)R(a)US(1)(7)R(a)T(2),(5) I(3)x(Q(x) Z(x)P(8)R(a) Z(a)T(6),(7) I(4)Q(a) Z(a)ES(3)(9)x(R(x) Z(x)EG(8)(5)Q(a)T(4) I该证明的错误在于 : 1 、 2 与 3 、 4 的顺序颠倒了，应该先指定存在后指定全称。 (2 分)正确的证明是：(4 分)(1)x(Q(x) Z(x) P(6)Z(a)T(2) I(2)Q(a) Z(a) ES (1)(7)R(a)T(4),(5) I(3)x(Q(x) R(x) P(8)R(a) Z(a) T(6),(7) I(4)Q(a) R(a) US (3)(9)x(R(x)Z(x) EG(8)(5)Q(a)T(2) I4(10 分)公安人员审理某珠宝商店的钻石项链的失窃案，侦察结果如下：(1)营业员A或B盗窃了钻石项链( 2)假设 B 作案，那么作案时间不在营业时间(3)假设A提供的证词正确，那么货柜未上锁( 4)假设 A 提供的证词不正确，那么作案发生在营业时间(5) 货柜上了锁 试问：作案者是谁要求写出推理过程。解：令A表示“营业员A盗窃了钻石项链 ；B表示“营业员B