《离散数学》课程教学资源（试卷习题）试卷（答案）04

离散数学试卷（四）参考答案 一、填空10%（每小题2分） 1、P真值为1，Q的真值为0：2、x(F(x)AL(x,0)→(Fy)AL(y,x》:3、 x(-P(x)VQ(x)》:4、约束变元：5、3xA(x)一A(y),y为D的某些元素。 二、选择25%（每小题2.5分） 题目12345678910 答案A.CADC,DA,DB,CAB,C,D,ECAB(4 三、逻辑判断30% 1、(1)等值演算法 A=(P→Q)A(Q→P》←(P→Q)台(PQ)(P+Q)台T (2)真值表法 pQP→QQ→P (P→Q)A(Q→P)PQA 11 10 0 1 0 0 01 1 0 0 0 00 1 1 1 所以A为重言式。 2、(1)不成立。 若取C=T则4vT台T BVTeT有AvC一BvC台T 但A与B不一定等价，可为任意不等价的公式。 (2)成立。 证明：4一B充要条件A)B一T 即： T台(A→B)A(-B→4)台(AVB)A(BV40 台(BVA)A(AVB)台(A→B)A(B→A)一A)B 所以A)B白T故AB

离散数学试卷（四）参考答案 27 一、 填空 10%（每小题 2 分） 1、P 真值为 1，Q 的真值为 0；2、 x(F(x)  L(x,0) → y(F( y)  L( y, x)) ；3、 x(P(x)  Q(x)) ；4、约束变元；5、xA(x)  A( y) ，y 为 D 的某些元素。 二、 选择 25%（每小题 2.5 分） 题目 1 2 3 4 5 6 7 8 9 10 答案 A,C A,D C,D A,D B,C A,B,C,D,E C A B (4) 三、 逻辑判断 30% 1、（1）等值演算法 A = ((P → Q)  (Q → P))  (P  Q)  (P  Q)  (P  Q)  T （2）真值表法 P Q P → Q Q → P (P → Q)  (Q → P) P  Q A 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 所以 A 为重言式。 2、（1）不成立。 若取 C = T 则AT T BT T 有 AC  BC T 但 A 与 B 不一定等价，可为任意不等价的公式。 （2）成立。 证明： A  B 充要条件 A B T 即： B A A B A B B A A B T A B B A A B B A        →  →     →    →        ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 所以 A  B T 故 A  B

离散数学试卷（四）参考答案 3、解：设P:厂方拒绝增加工资：Q:罢工停止：R罢工超壶过一年；R:撤换厂长 前提：P→(-(R入S)→Q),P,R结论：Q ①P→((RAS)→Q) ②P ③-(RAS)→Q T①②】 ④R P ⑤RvS TOI ⑥-(RAS) T⑤E ⑦-Q T③⑥L 罢工不会停止是有效结论。 四、计算10% 1、解，v→0n0》1v)=v0→0)1 =1v0)分1=11=1 (P0)OARPVO)(OR) 2、 (PAQ)A(QAR)PA-QAOARF 它无成真赋值，所以为矛盾式。 五、谓词逻辑推理15% 解：M(x):x是人F(x:x是花G(x):x是杂草H(x,y):x喜欢 3x(M(x)AFy)→H(x,y》x(M(x)→Gy)→H(x,y》 →x(Fx)→G(x》 证明： )3r(M(x)AFUy)→H(x,y)》 (②M(a)AFy)→Ha,y》 ES(D) (3)M(a) T2I ④Fy)→H(a,y》 T2)1

离散数学试卷（四）参考答案 28 3、解：设 P：厂方拒绝增加工资；Q：罢工停止；R 罢工超壶过一年；R：撤换厂长 前提： P → ((R  S) → Q) , P, R 结论： Q ① P → ((R  S) → Q) P ② P P ③ (R  S) → Q T①②I ④ R P ⑤ R  S T④I ⑥ (R  S) T⑤E ⑦ Q T③⑥I 罢工不会停止是有效结论。 四、计算 10% 1、 解： (1 0) 1 1 1 1 (1 (1 0 0))) (1 1) (1 (1 0) 1 =   =  =  →    =  →  2、 P Q Q R P Q Q R F P Q Q R P Q Q R             →         ( ) ( ) ( ) ( ) ( ) 它无成真赋值，所以为矛盾式。 五、谓词逻辑推理 15% 解： M(x): x是人; F(x): x是花; G(x): x是杂草; H(x, y): x喜欢y x(M (x)  y(F( y) → H(x, y))) x(M (x) → y(G( y) → H(x, y)))  x(F(x) → G(x)) 证明： ⑴ x(M (x)  y(F( y) → H(x, y))) P ⑵ M (a)  y(F( y) → H(a, y)) ES⑴ ⑶ M (a) T⑵I ⑷ y(F( y) → H(a, y)) T⑵I

离散数学试卷（四）参考答案 ⑤x(Mx)→Gy)→H(x,y)》 ⑥M(a)→Gy)→H(a,y》 US⑤ ()yGy)→H(a,y) T3)61 (8)Ha,y)→Gy》 TDE ⑨F(e)→H(a,) US(4 0H(a,)→G(z) US(8) aDF(e)→G) T9001 mx(F(x)→G(x) 四、正明10% xA(x)xB(x)(A(a)A(b)A(c)v(B(a)B(b)B(c) (A(a)v B(a))(A(a)v B(b))(A(a)v B(c)) (A(b)vB(a)(A(b)B(b)(A(b)B(c)) (A(e)v B(a))(A(c)v B(b))(A(c)v B(c)) (A(a)B(a))(A(b)B(b))(A(c)B(c) 台x(A(x)vB(x)》

离散数学试卷（四）参考答案 29 ⑸ x(M (x) → y(G( y) → H(x, y))) P ⑹ M (a) → y(G( y) → H(a, y)) US⑸ ⑺ y(G( y) → H(a, y)) T⑶⑹I ⑻ y(H(a, y) → G( y)) T⑺E ⑼ F(z) → H(a,z) US⑷ ⑽ H(a,z) → G(z) US⑻ ⑾ F(z) → G(z) T⑼⑽I ⑿ x(F(x) → G(x)) UG⑾ 四、 证明 10% ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( ) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ( ) ( )) ( ) ( ) ( ( ) ( ) ( ) ( ( ) ( ) ( ) x A x B x A a B a A b B b A c B c A c B a A c B b A c B c A b B a A b B b A b B c A a B a A a B b A a B c x A x x B x A a A b A c B a B b B c                                    