离散数学试卷（十） 一、 填空10%（每小题2分） 1、若P,Q为二命题，P→Q真值为1，当且仅当」 2、对公式(yP(x,)A3Q(x,》VxRx,y)中自由变元进行代入的 公式为 3、xF(x)A(3xGx)的前束范式为_ 4、设x是谓词合式公式A的一个客体变元，A的论域为D,A(x)关于y的自由的，则 被称为全称量词消去规则，记为US。 5、与非门的逻辑网络为 二、选择30%（每小题3分） 1、下列各符号串，不是合式公式的有( )。 A、(PAQ)AR:B、(P→Q)→(RAS): C、PVOVAR:D、(-(PvQ)A)vS. 2、下列语句是命题的有( A、2是素数：B、x+5>6:C、地球外的星球上也有人：D、这朵花多好看呀！。 3、下列公式是重言式的有( A、(PQ):B、(PAQ)→Q:C、(Q→P)AP:D、(P→Q)P 4、下列问题成立的有( )。 A、若AVCBVC,则AB:B、若AACBAC,则A白B: C、若A白B,则A台B: D、若A白B,则A⊙一B。 5、命愿逻辑演绎的CP规则为( )。 A、在推演过程中可随便使用前提： B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 C、如果要演绎出的公式为B→C形式，那么将B作为前提，设法演绎出C: D、设(4)是含公式A的命题公式，B一A,则可用B替换D(A)中的A。 62
离散数学试卷（十） 62 一、 填空 10% （每小题 2 分） 1、 若 P，Q 为二命题， P Q 真值为 1，当且仅当 。 2、 对公式 (yP(x, y) zQ(x,z)) xR(x, y) 中自由变元进行代入的 公式为 。 3、 xF(x) (xG(x)) 的前束范式为 。 4、 设 x 是谓词合式公式 A 的一个客体变元，A 的论域为 D，A（x）关于 y 的自由的，则 被称为全称量词消去规则，记为 US。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3 分） 1、 下列各符号串，不是合式公式的有（ ）。 A、 (P Q) R ； B、((P → Q) → (R S) ； C、 P Q R ； D、((P Q) R) S 。 2、 下列语句是命题的有（ ）。 A、2 是素数；B、x+5 > 6；C、地球外的星球上也有人；D、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A、 (P Q) ；B、(P Q) → Q ；C、(Q → P) P ；D、(P → Q) P 4、 下列问题成立的有（ ）。 A、 若 AC BC ，则 A B ； B、若 AC B C ，则 A B ； C、若 A B ，则 A B ； D、若 A B ，则 A B。 5、 命题逻辑演绎的 CP 规则为（ ）。 A、 在推演过程中可随便使用前提； B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C、如果要演绎出的公式为 B →C 形式，那么将 B 作为前提，设法演绎出 C； D、设 (A) 是含公式 A 的命题公式， B A ，则可用 B 替换 (A) 中的 A
离散数学试卷（十） 6、命题“有的人喜欢所有的花”的逻辑符号化为( 设D:全总个体域，F(x):x是花，Mx):x是人，H(xy):x喜欢y A、x(M(x)→y(F(y)→H(x,y):B、x(M(x)A(Fy)→H(x,y》: C、3x(M(x)→y(Fy)→H(x,y)》):D、3x(M(x)AFy)→H(xy》。 7、公式xP(x,)VQ,》A3xPx,y)换名( A、xu(P(x,)vQ(,》A3rPxy):B、xP(x,)vQ(u,》A3xPx,): C、xP(x,y)vQy,》A3xPx,0):D、P(4,yvQy,=》A3Pu,y)。 &、给定公式3rPx)→xPx),当D-{a,b时，解释( )使该公式真值为0： A、P(a0、Pb0:B、P(a0、Pb)=l:C、P(a=l、Pb)0:D、PaF=l、Pb)l 9、下面蕴涵关系成立的是( )。 A、xPx)Arx)x(P(x)vQx): B、3xPx)→xQx)→x(P(x)→Q(x): C、xPx)→xx)→x(P(x)→Q(x): D、3xAxy)→归xAx,y)。 10、下列推理步骤错在( ①yF(xy) ②3F(e,y) Us① ③F(e,c) ES② ④VxFx,c) UG ⑥3xFx,y) EG④ A、①→②：B、②→③：C、③-④：D、④-⑤
离散数学试卷（十） 63 6、 命题“有的人喜欢所有的花”的逻辑符号化为（ ）。 设 D：全总个体域，F（x）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢 y A、x(M (x) → y(F( y) → H(x, y))) ；B、x(M (x) y(F( y) → H(x, y))) ； C、 x(M (x) → y(F( y) → H(x, y))) ；D、x(M (x) y(F( y) → H(x, y))) 。 7、 公式 xy(P(x, y) Q( y,z)) x P(x, y) 换名（ ）。 A、xu(P(x,u) Q(u,z)) x P(x, y) ；B、xy(P(x,u) Q(u,z)) xP(x,u) ； C、xy(P(x, y) Q( y,z)) x P(x,u) ；D、uy(P(u, y) Q( y,z)) uP(u, y) 。 8、 给定公式 xP(x) → xP(x) ，当 D={a,b}时，解释（ ）使该公式真值为 0。 A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=1 9、 下面蕴涵关系成立的是（ ）。 A、x P(x) x Q(x) x(P(x) Q(x)) ； B、 x P(x) → x Q(x) x(P(x) → Q(x)) ； C、x P(x) → x Q(x) x(P(x) → Q(x)) ； D、 xyA(x, y) yxA(x, y) 。 10、下列推理步骤错在（ ）。 ① yyF(x, y) P ② yF(z, y) US① ③ F(z,c) ES② ④ xF(x, c) UG③ ⑤ yxF(x, y) EG④ A、①→②；B、②→③；C、③→④；D、④→⑤
离散数学试卷（十） 三、逻辑判断28% 1、(8分)下列命题相容吗？A→B,一(BVC),A 2、(10分)用范式方法判断公式(P→Q)A(P→R),P→QAR是否等价 3、(10分)下列前提下结论是否有效？ 今天或者天晴或者下雨。如果天晴，我去看电影：若我去看电影，我就不看书。故我在看书 时，说明今天下雨。 四、计算12% 1、(5分)给定3个命愿：P:北京比天津人口多：Q:2大于1：R:15是素数。求复合命题： (Q→R)(PA一R)的真值。 2、(7分)给定解释1：D-{2,3,L(xy)为(2,2)=L(3,3)=1,L(2,3)=L(3,2)0, 求谓词合式公式3yxL(x,y)的真值。 五、逻辑推理20% 1、(10分)所有有理数是实数，某些有理数是整数，因此某些实数是整数。 2、(10分)符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是 骗子”。并推证其结论
离散数学试卷（十） 64 三、 逻辑判断 28% 1、（8 分）下列命题相容吗？ A → B, (B C), A 2、（10 分）用范式方法判断公式 (P → Q) (P → R) , P → Q R 是否等价。 3、（10 分）下列前提下结论是否有效？ 今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书 时，说明今天下雨。 四、 计算 12% 1、（5 分）给定 3 个命题：P：北京比天津人口多；Q：2 大于 1；R：15 是素数。 求复合命题： (Q → R) (P R) 的真值。 2、（7 分）给定解释 I：D={2，3}，L（x,y）为 L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 , 求谓词合式公式 y xL(x, y) 的真值。 五、 逻辑推理 20% 1、（10 分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。 2、（10 分）符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是 骗子”。并推证其结论