离散数学数理逻辑复习题(6页).doc

-离散数学数理逻辑复习题-第 6 页数理逻辑复习题1. 将下列命题符号化(1)刘晓月跑得快，跳得高。pq，其中，p：刘晓月跑得快，q：刘晓月跳得高。(2)老王是山东人或河北人。pq，其中，p：老王是山东人，q：老王是河北人。(3)因为天气冷，所以我穿了羽绒服。pq，其中，p：天气冷，q：我穿了羽绒服。(4)王欢与李乐组成一个小组。p，其中，p：王欢与李乐组成一个小组，是简单命题。(5)如果天下大雨，他就乘班车上班。pq，其中，p：天下大雨，q：他乘班车上班。(6)只有天下大雨，他才乘班车上班。pq，其中，p：他乘班车上班，q：天下大雨。(7)除非天下大雨，他才乘班车上班。pq，其中，p：他乘班车上班，q：天下大雨。2. 判断下列公式的类型：（1）p(pqr)（2）(pq)q（3）(qr)r（4）(pq)(qp)（5）(pr)(pq)（6）(pq)(qr)(pr) （7）(pq)(rs) 答案： (1)、(4)、(6)为重言式。 (3)为矛盾式。  (2)、(5)、(7)为可满足式。3. 用等值演算法证明下面等值式：（1）¬(pq)(pq)¬(pq)（2）(p¬q)(¬pq)(pq)¬(pq)答案：（1）(pq) (pq)(qp) (pq)(qp) (pq)(qp) (pq)(pp)(qq)(pq) (pq)(pq) （2）(pq)(pq) (pp)(pq)(qp)(qq) (pq)(pq)4. 求下列公式的主析取范式，再用主析取范式求合取范式：  （1）(pq)r（2）(pq)(qr)答案：（1）m1m3m5m6m7M0M2M4（2）m0m1m3m7M2M4M5M65. 用附加前提法证明下面各推理：（1）前提：p(qr), sp, q 结论：sr  证明：  s 附加前提引入 sp 前提引入 p 假言推理 p(qr)前提引入 qr假言推理 q 前提引入 r假言推理（2）前提：(pq)(rs), (st)u       结论：pu    证明： p 附加前提引入 pq 附加 (pq)(rs) 前提引入 rs 假言推理 s 化简 st 附加 (st)u 前提引入 u 假言推理6. 用归谬法证明下面推理： （1） 前提：pq, rq, rs 结论：p（1）证明： p 结论否定引入 pq 前提引入 q 假言推理 rq 前提引入 r 析取三段论 rs 前提引入 r 化简 rr合取  为矛盾式，由归谬法可知，推理正确。（2） 前提：pq, pr, qs      结论：rs证明： (rs) 结论否定引入 pq 前提引入 pr前提引入 qs前提引入 rs构造性二难 (rs)(rs) 合取  为矛盾式，所以推理正确。7. 给定解释I如下：  (a) 个体域D=3,4。  (b) f (x)为f (3)=4，f (4)=3。  (c) F(x,y)为F(3,3)=F(4,4)=0，F(3,4)=F(4,3)=1。试求下列公式在I下的真值：  (1) xyF(x,y)  (2) xyF(x,y)  (3) xy(F(x,y)F(f(x),f(y)答案：(1) xyF(x,y) (F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10)1(2) xyF(x,y) (F(3,3)F(3,4)(F(4,3)F(4,4) (01)(10)0(3) xy(F(x,y)F(f(x),f(y) (F(3,3)F(f(3),f(3)  (F(4,3)F(f(4),f(3)  (F(3,4)F(f(3),f(4)  (F(4,4)F(f(4),f(4) (00)(11)(11)(00)18. 给定解释I如下：  （a）个体域D=N（N为自然数）。  （b）D中特定元素a=2。  （c）D上函数f (x, y)=xy，g(x, y)=x·y。  （d）D上谓词F(x, y)：x=y。  说明下列公式在I下的含义，并指出各公式的真值：  （1）xF(g(x,a),x)  （2）xy(F( f(x,a),y)F( f (y,a),x)  （3）xyz(F(f (x,y),z)  （4）xF(f (x,x),g(x, x)  (1) x(x·2=x)，真值为0。  (2) xy(x+2=y)(y+2=x)，真值为0。  (3) xyz(x+y=z),真值为1。  (4) x(x+x=x·x),真值为1。