数理逻辑复习题复习要求：掌握命题、逻辑联结词的概念；公式与解释的概念，用基本等价式化简其他公式；会用真值表法和主范式判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法.一阶逻辑的基本概念，一阶逻辑公式及其解释，等值演算，推理理论；一阶逻辑公式的三种类型，即逻辑有效式（永真式），矛盾式和可满足式；用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系.命题逻辑与一阶逻辑推理理论.一、命题逻辑部分 1、填空题.⑴ 公式（p ∧⌝q ）∨（⌝p ∧q ）的成真赋值为 01，10 .⑵ 设p 、r 为真命题，q 、s 为假命题，则复合命题（p →q ）↔（⌝r →s ）的真值为 0 . ⑶ 设p 、q 为命题，在 p 、q 不能同时发生 条件下，p 与q 的排斥或也可以写成p 与q 的相容或. ⑷ 设A 为任意公式，B 为重言式，则A ∨B 的类型是 重言式⑸ 设A 是含命题变项p 、q 、r 的重言式，则公式A ∨（（p ∧q ）→r ）的类型为重言式. ⑹ 设B 是含命题变项p 、q 、r 的矛盾式，则公式B ∧（（p ↔q ）→r ）的类型为矛盾式 . ⑺ 矛盾式的主析取范式是 0 . ⑻ 重言式的主合取范式是 1 .⑼ 设公式A 含命题变项p 、q 、r 已知A 主合取范式是M 0∧M 2∧M 5∧M 6，则A 的主析取范式是 . ⑽ 已知公式⌝（q →p ）∧p 是矛盾式，则公式⌝（q →p ）∧p ∧⌝r 的成真赋值是 成假赋值 .⑾已知公式（p →（p ∨q ））∧（（p ∧q ）→p ）是重言式，公式p →（p ∨q ）及（p ∧q ）→p 类型是 .⑿已知公式（p ∧q ）→p 是重言式，则公式（（p ∧q ）→p ）∨r 的成真赋值是 成假赋值 .⒀（A →B ）∧⌝B ⇒ 为拒取式推理定律. ⒁（A ∨⌝B ）∧B ⇒ 为析取三段论推理定律.⒂（⌝A →B ）∧（B →⌝C ）⇒ 为假言三段论推理定律. ⒃（⌝A →⌝B ）∧⌝A ⇒ 为假言推理定律. 2、将下列命题或语句符号化.⑴ 不是无理数是不对的. ⌝⌝p （p ） ⑵ 小刘既不怕苦，又很钻研. ⌝p ∧q ⑶ 只有不怕困难，才能战胜困难 q →⌝p⑷ 只要别人有困难，老王就帮助别人，除非问题解决了. ⌝r →（p →q ）；（⌝r ∧p ）→q 或⌝q →（⌝p ∨r ）⑸ 整数n 是偶数当且仅当n 能被2整除. p ↔q ⑹ 若地球上没有树木，则人类不能生存. q p ⌝→⌝ ⑺ 若422=+，则地球是静止不动的. q p → 3、求下列复合命题真值.P ：2能整除5，q ：旧金山美国的首都，r ：一年有四季 ⑴（（p ∨q ）→r ）∧（r →（p ∧q ）⑵（（⌝q ↔p ）→（r ∨p ））∨（（⌝p ∧⌝q ）∨⌝r ）4、判断下面一段论述是否为真：“3是无理数.并且，如果3是无理数，则2也是无理数.另外，只有6能被2整除，6才能被4整除.”解 设p ：3是无理数，q ：3是无理数，r ：2是无理数，s ：6能被2整除， t ：6能被4整除. 则原命题为：)()(s t r q p →∧→∧，这里0,1,1,0,1=====t s r q p . 则)()(s t r q p →∧→∧1111)10()10(1⇔∧∧⇔→∧→∧⇔. ５、判断公式的类型.⑴（⌝（q ↔p ）→（（p ∧⌝q ）∨（（⌝p ∧q ）））∨r 重言式 ⑵（p ∧⌝（q →p ））∧（r ∧q ） 矛盾式 ⑶（p ↔⌝r ）→（r ↔q ） 可满足式 ６、求公式p →（（q ∧r ）∧（p ∨（⌝q ∧⌝r ）））的主析取范式和主合取范式.m 0∨m 1∨m 2∨m 3∨m 7７、求公式⌝（⌝（p →q ）∨（⌝q →⌝p ）的主合取范式.８、将公式p →（q →r ）化成与之等值的且仅含{⌝，∧}中联结词的公式. ⌝（p ∧q ∧⌝r ）９、用主析取范式或主合取范式判断两公式是否等值.⌝（p ↔q ）与（（p ∨q ）∧⌝（p ∧q ）） 等值 10、在自然推理系统P 中，构造下面推理的证明.⑴前提：⌝（p ∧⌝q ），q →⌝ r ，r 结论：⌝p⑵前提： p → r ，q →s ，p ，q结论：（r ∧s ）∨t11、在自然推理系统P 中，用附加前提法证明下面推理.⑴前提：⌝p ∨（q → r ），s →p ，q 结论：⌝r →⌝s⑵前提：⌝p →q ，⌝p ∨r ，q →s 结论：⌝s →r12、在自然推理系统P 中，用归谬法证明下面推理.前提： p →（q →r ），p ∧q 结论： r ∨s13、在自然推理系统P 中，构造下面用自然语言给出的推理.若小张喜欢数学，则小赵或小李也喜欢数学. 若小李喜欢数学，他也喜欢物理.小张确实喜欢数学，可小李不喜欢物理，所以小赵喜欢数学.P ：小张喜欢数学 q ：小赵喜欢数学 r ：小李喜欢数学 S ：小李喜欢物理前提：P →（q ∨r ） ，r →s ，p ， ⌝s 结论：q证明 ① r →s ② ⌝s ③ ⌝r④ P →（q ∨r ） ⑤ p ⑥ q ∨r ⑦ q14、设p ：A 到过受害人房间 q ：A 在11点以前离开房间 r ：A 犯谋杀罪看门人看到A则{p ∧⌝q →r ，p ，q →s ，⌝s}|=r① ⌝s 前提引入 ② q →s 前提引入 ③⌝ q① ②拒取④ p 前提引入 ⑤p ∧⌝ q ③ ④合取⑥ p ∧⌝q →r 前提引入 ⑦ r ⑤ ⑥假言推理 二、一阶逻辑部分1.在一阶逻辑中将下列命题符号化.⑴ 所有的整数，不是负整数，就是正整数，或者是零.解 F （x ）：x 是整数G （x ）：x 是正整数H （x ）：x 是负整数L （x ）：x 是0∀x （F （x ）→ G （x ）∨H （x ）∨L （x ））或∀x （F （x ）∧⌝ G （x ）→H （x ）∨L （x ）） ⑵ 有的实数是有理数有的实数是无理数. 解 F （x ）：x 是实数 G （x ）：x 是有理数 H （x ）：x 是无理数∃x （F （x ）∧G （x ））∧∃y （F （y ）∧ H （y ）） ⑶ 不存在能表示成分数无理数.解 F （x ）：x 能表示成分数 G （x ）：x 是无理数⌝∃x （G （x ）∧ F （x ））⇔∀x （G （x ）→⌝ F （x ））⑷ 若x 、y 都是实数，且x>y ，则x+2>y+2. 解 F （x ）：x 是实数 H （x ，y ）：x>y∀x ∀y （F （x ）∧F （y ）∧ H （x ，y ）→ H （x+2，y+2）） ⑸不存在最大的自然数.解 F （x ）：x 是自然数 H （x ，y ）：x>y⌝∃x （F （x ）∧∀y （F （y ）→ H （x ，y ））⑹ 在北京卖菜的人不全是外地人.解 设)(x M ：x 是外地人. )(x F ：x 在北京卖菜. 则符号化为))()((x F x M x ∧⌝∃. ⑺ 设：)(x M ：x 是火车. )(x H ：x 是轮船. )(x F ：x 是汽车. ),(y x G ：x 比y 快. 则“火车都比轮船快.”符号化为)),()()((y x G y H x M y x →∧∀∀. 则“有的火车比有的汽车快.”符号化为)),()()((y x G y F x M y x ∧∧∃∃.则“不存在比所有火车都快的汽车.”符号化为)))),()(()(((y x G y M y x F x →∀∧∃⌝. 4、 指出下列公式中的指导变元，量词的辖域，各个体变项的自由出现和约束出现： （1）)),()((y x G x F x →∀解 x ∀的辖域：),()(y x G x F →.x 是指导变元. x 是约束出现，y 是自由出现. （2）),(),(y x yG y x xF ∃→∀解 x ∀的辖域：),(y x F .x 是指导变元. x 是约束出现，y 是自由出现.y ∃的辖域：),(y x G .y 是指导变元. x 是自由出现，y 是约束出现.5、 证明下面公式既不是永真式也不是矛盾式： （1）))),()(()((y x H y G y x F x ∧∃→∀证明1解释1I ：R D =，)(x F ：x 是正数.)(y G ：y 是负数.),(y x H ：0=+y x .))),()(()((y x H y G y x F x ∧∃→∀指对任意正数x ，存在负数y ，使得0=+y x .在该解释下，命题为“真”. 2解释2I ：}3,2,1{-=D ，)(x F ：x 是正数.)(y G ：y 是负数.),(y x H ：0=+y x .则对1=x 时，不存在负数D y ∈，使0=+y x ，故在该解释下，命题为“假”，所以（1）公式既不是永真式也不是矛盾式. （2）)),()()((y x H y G x F y x →∧∀∀6、设个体域},,{c b a D =，消去下列各式的量词： （1）))()((y G x F y x ∧∃∀)))()(((y G a F y ∧∃⇔)))()(((y G b F y ∧∃∧)))()(((y G c F y ∧∃∧∨∧⇔))()(((a G a F ∨∧))()((b G a F ∧∧)))()((c G a F ∨∧))()(((a G b F ∨∧))()((b G b F ∧∧)))()((c G b F ∨∧))()(((a G c F ∨∧))()((b G c F )))()((c G c F ∧（2）))()((y G x F y x ∨∀∀)))()(((y G a F y ∨∀⇔)))()(((y G b F y ∨∀∧)))()(((y G c F y ∨∀∧∧∨⇔))()(((a G a F ∧∨))()((b G a F ∧∨)))()((c G a F ∧∨))()(((a G b F ∧∨))()((b G b F ∧∨)))()((c G b F ∧∨))()(((a G c F ∧∨))()((b G c F )))()((c G c F ∨7、求前束范式⑴⌝∃x ∀yF （x ，y ）（⇔ ∀x ∃y ⌝F （x ，y ）） ⑵（∃xF （x ，y ）→∀yG （x ，y ，z ））→∃z H （z ）.（⇔∃x ∃y ∃z （F （x ，t ）→G （u ，y ，v ）→H （z ）））⑶⇔∀→∀),()(y x yG x xF ),()(y z yG x xF ∀→∀)),()((y z G x F y x →∀∃⇔⑷ ⇔∃→∀)),,(),((z y x yG y x F x ⇔∃→∀)),,(),((z y x yG t x F x )),,(),((z y x G t x F y x →∃∀ ⑸ ⇔∃↔∀),(),(y x xG y x xF ),(),(y z zG t x xF ∃↔∀)),(),(()),(),((t x xF y z zG y z zG t x xF ∀→∃∧∃→∀⇔ )),(),(()),(),((h r rF g s sG y z G t x F z x ∀→∃∧→∃∃⇔ )),(),(()),(),((h r F g s G r s y z G t x F z x →∀∀∧→∃∃⇔ ))),(),(()),(),(((h r F g s G y z G t x F r s z x →∧→∀∀∃∃⇔8、在自然推理系统 N L 中构造下面推理的证明.⑴前提：∃xF （x ）→∀y （G （y ）→H （y ）），∃xR （x ）→∃yG （y ） 结论：∃x （ F （x ）∧ R （x ））→∃x H （x ） 证明1 ⑴ ∃x （ F （x ）∧ R （x ）） ⑵ F （c ）∧ R （c ） ⑶ F （c ） ⑷ R （c ） ⑸ ∃x F （x ）⑹∃xF （x ）→∀y （G （y ）→H （y ）） ⑺ ∀y （G （y ）→H （y ）） ⑻ G （c ）→H （c ） ⑼R （c ） ⑽∃x R （x ）⑾∃xR （x ）→∃yG （y ） ⑿∃yG （y ） ⒀G （c ） ⒁H （c ） ⒂∃x H （x ）证明2： ⑴∃x （ F （x ）∧ R （x ）） ⑵∃x F （x ）∧∃x R （x ）） ⑶∃x F （x ）⑷∃xF （x ）→∀y （G （y ）→H （y ）） ⑸∀y （G （y ）→H （y ）） ⑹G （c ）→H （c ）⑺∃xR（x）→∃yG（y）⑻∃x R（x））⑼∃yG（y）⑽G（c）⑾H（c）⑿∃x H （x）⑵人都喜欢吃蔬菜.但说所有的人都喜欢吃鱼是不对的.所以存在只喜欢吃蔬菜而不喜欢吃鱼的人.F（x）：x是人G（x）：喜欢吃蔬菜H （x）：喜欢吃鱼前提：∀x（F（x）→G（x））⌝∀x（F（x）→H（x））结论：∃x（F（x）∧G（x）∧⌝H（x））证明：⑴⌝∀x（F（x）→H（x））⑵∃x⌝（F（x）→H（x））⑶∃x（F（x）∧⌝H（x））⑷F（c）∧⌝H（c）⑸∀x（F（x）→G（x））⑹F（c）→G（c）⑺F（c）⑻G（c）⑼F（c）∧⌝H（c）∧G（c）⑽∃x（F（x）∧G（x）∧⌝H（x））⑶任意三角形的内角和等于1800，ABC三角形，则ABC的内角和等于1800.证明设F（x）：x是三角形G（x）：x的内角和等于1800a：ABC前提：∀x（F（x）→G（x））F（a）结论：G（a）证明：⑴∀x（F（x）→G（x））⑵F（a）→G（a）⑶F（a）⑷G（a）（4）每个喜欢步行的人都不喜欢骑自行车.每个人或者喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车.所以有的人不喜欢步行.（个体域为人类集合）.证明设F（x）：x喜欢步行G（x）：x喜欢骑自行车H（x）：x喜欢乘车｛∀x（F（x）→⌝G（x）），∀x （G（x）∨H（x），∃x ⌝H（x））→∃x ⌝F（x）①∃x ⌝H（x）②⌝H（c）③∀x （G（x）∨H（x））④G（c）∨H（c）⑤G（c）⑥∀x（F（x）→⌝G（x））⑦F（c）→⌝G（c）⑧⌝F（c）⑨∃x ⌝F（x）(5)每个科学工作者都是刻苦钻研的，每个刻苦钻研而有聪明的人在他的事业中都将获得成功.王大海是科学工作者，并且是聪明的.所以王大海在他的事业中将获得成功.（个体域为人类集合）.证明设F（x）：x是科学工作者G（x）：x喜欢钻研H（x）：x聪明W（x）：x事业成功a：王大海｛∀x（F（x）→G（x）），∀x（G（x）∧H（x）→W（x）），F（a），H（a）｝→W（a）①∀x（F（x）→G（x））②F（a）→G（a））③∀x （G（x）∧H（x）→W（x））④G（a）∧H（a）→W（a）⑤F（a）⑥G（a）⑦H（a）⑧G（a）∧H（a）⑨W（a）。