离散数学数理逻辑复习题.docx

数理逻辑复习题将下列命题符号化(1)刘晓月跑得快，跳得高。p∧q，其中，p：刘晓月跑得快，q：刘晓月跳得高。(2)老王是山东人或河北人。p∨q，其中，p：老王是山东人，q：老王是河北人。(3)因为天气冷，所以我穿了羽绒服。p→q，其中，p：天气冷，q：我穿了羽绒服。(4)王欢与李乐组成一个小组。p，其中，p：王欢与李乐组成一个小组，是简单命题。(5)如果天下大雨，他就乘班车上班。p→q，其中，p：天下大雨，q：他乘班车上班。(6)只有天下大雨，他才乘班车上班。p→q，其中，p：他乘班车上班，q：天下大雨。(7)除非天下大雨，他才乘班车上班。p→q，其中，p：他乘班车上班，q：天下大雨。判断下列公式的类型：（1）p→(p∨q∨r)（2）(p→┐q)→┐q（3）┐(q→r)∧r（4）(p→q)→(┐q→┐p)（5）(p∧r)(┐p∧┐q)（6）((p→q)∧(q→r))→(p→r)?（7）(p→q)(rs)?答案：(1)、(4)、(6)为重言式。?(3)为矛盾式。?(2)、(5)、(7)为可满足式。用等值演算法证明下面等值式：（1）?(pq)(p∨q)∧?(p∧q)（2）(p∧?q)∨(?p∧q)(p∨q)∧?(p∧q)答案：（1）┐(pq)?┐((p→q)∧(q→p))?┐((┐p∨q)∧(┐q∨p))?(p∧┐q)∨(q∧┐p)?(p∨q)∧(p∨┐p)∧(┐q∨q)∧(┐p∨┐q)?(p∨q)∧┐(p∧q) （2）(p∧┐q)∨(┐p∧q)?(p∨┐p)∧(p∨q)∧(┐q∨┐p)∧(┐q∨q)?(p∨q)∧┐(p∧q)求下列公式的主析取范式，再用主析取范式求合取范式：?（1）(p∧q)∨r（2）(p→q)∧(q→r)答案：（1）m1∨m3∨m5∨m6∨m7M0∧M2∧M4（2）m0∨m1∨m3∨m7M2∧M4∧M5∧M6用附加前提法证明下面各推理：（1）前提：p→(q→r), s→p, q结论：s→r??证明： ?①s 附加前提引入?②s→p 前提引入?③p ①②假言推理?④p→(q→r)前提引入?⑤q→r③④假言推理?⑥q 前提引入?⑦r⑤⑥假言推理（2）前提：(p∨q)→(r∧s), (s∨t)→u????? 结论：p→u??证明：?①p 附加前提引入?②p∨q ①附加?③(p∨q)→(r∧s) 前提引入?④r∧s ②③假言推理?⑤s ④化简?⑥s∨t ⑤附加?⑦(s∨t)→u 前提引入?⑧u ⑥⑦假言推理用归谬法证明下面推理：前提：p→┐q, ┐r∨q, r∧┐s?结论：┐p（1）证明：?①p 结论否定引入?②p→┐q 前提引入?③┐q ①②假言推理?④┐r∨q 前提引入?⑤┐r ③④析取三段论?⑥r∧┐s 前提引入?⑦r ⑥化简?⑧┐r∧r⑤⑦合取??⑧为矛盾式，由归谬法可知，推理正确。前提：p∨q, p→r, q→s??????结论：r∨s证明：?①┐(r∨s) 结论否定引入?②p∨q 前提引入?③p→r前提引入?④q→s前提引入?⑤r∨s②③④构造性二难?⑥┐(r∨s)∧(r∨s)合取??⑥为矛盾式，所以推理正确。给定解释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))?(0∨1)∧(1∨0)1(2) xyF(x,y)?(F(3,3)∧F(3,4))∨(F(4,3)∧F(4,4))?(0∧1)∨(1∧0)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)))?(0→0)∧(1→1)∧(1→1)∧(0→0)1给定解释I如下：??（a）个体域D=N（N为自然数）。??（b）D中特定元素a=2。??（c）D上函数f(x,y)=x＋y，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。