《数理逻辑复习题.docx》由会员分享，可在线阅读，更多相关《数理逻辑复习题.docx（9页珍藏版）》请在三一办公上搜索。
1、数理逻辑复习题数理逻辑复习题 复习要求： 掌握命题、逻辑联结词的概念；公式与解释的概念，用基本等价式化简其他公式；会用真值表法和主范式判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法.一阶逻辑的基本概念，一阶逻辑公式及其解释，等值演算，推理理论；一阶逻辑公式的三种类型，即逻辑有效式，矛盾式和可满足式；用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系.命题逻辑与一阶逻辑推理理论. 一、命题逻辑部分 1、填空题. 公式的成真赋值为 01，10 . 设p、r为真命题，q、s为假命题，则复合命题的真值为 0 . 设p、q为命题，在 p、q 不能同时发生 条件下
2、，p与q的排斥或也可以写成p与q的相容或. 设A为任意公式，B 为重言式，则AB的类型是 重言式 设A是含命题变项p、q、r的重言式，则公式Ar）的类型为重言式. 设B 是含命题变项p、q、r的矛盾式，则公式Br）的类型为矛盾式 . 矛盾式的主析取范式是 0 . 重言式的主合取范式是 1 . 设公式A含命题变项p、q、r已知A主合取范式是M0M2M5M6，则A的主析取范式是 . 已知公式p是矛盾式，则公式pr的成真赋值是 成假赋值 . 已知公式）p）是重言式，公式p及p类型是 . 已知公式p是重言式，则公式p）r的成真赋值是 成假赋值 . B 为拒取式推理定律. B 为析取三段论推理定律. 为
3、假言三段论推理定律. A 为假言推理定律. 2、将下列命题或语句符号化. 说7不是无理数是不对的. p 小刘既不怕苦，又很钻研. pq 只有不怕困难，才能战胜困难 qp q或q 只要别人有困难，老王就帮助别人，除非问题解决了. r； 整数n是偶数当且仅当n能被2整除. pq 若地球上没有树木，则人类不能生存. pq 若2+2=4，则地球是静止不动的. pq 3、求下列复合命题真值. P：2能整除5，q：旧金山美国的首都，r：一年有四季 r） ）r） 4、判断下面一段论述是否为真：“3是无理数.并且，如果3是无理数，则2也是无理数.另外，只有6能被2第 1 页 共 6 页 整除，6才能被4整除.
4、” 解 设p：3是无理数，q：3是无理数，r：2是无理数，s：6能被2整除， t：6能被4整除. 则原命题为：p(qr)(ts)，这里p=1,q=0,r=1,s=1,t=0. 则p(qr)(ts)1(01)(01)1111. 、判断公式的类型. ）r 重言式 ） 矛盾式 可满足式 、求公式p）的主析取范式和主合取范式. m0m1m2m3m7、求公式的主合取范式. 、将公式p化成与之等值的且仅含，中联结词的公式. 、用主析取范式或主合取范式判断两公式是否等值. ） 等值 与，q r，r 结论：p 前提： p r，qs，p，q 结论：t 11、在自然推理系统P中，用附加前提法证明下面推理. 前提：
5、p，sp，q 结论：r前提： 12、在自然推理系统P中，用归谬法证明下面推理. 前提： p，pq 结论： rs 13、在自然推理系统P中，构造下面用自然语言给出的推理. 若小张喜欢数学，则小赵或小李也喜欢数学. 若小李喜欢数学，他也喜欢物理.小张确实喜欢数学，可小李不喜欢物理，所以小赵喜欢数学. P：小张喜欢数学 q：小赵喜欢数学 r：小李喜欢数学 前提：P ，rs，p， 证明 rs s r P p qr q 14、设p：A到过受害人房间 q：A在11点以前离开房间 r：A犯谋杀罪看门人看到A 则pqr，p，qs，s|=r s 前提引入 qs q 前提引入 拒取 S：小李喜欢物理 s pq，p
6、r，qs 结论：sr s 结论：q p 前提引入 p q 合取 第 2 页 共 6 页 pqr 前提引入 r 假言推理 二、一阶逻辑部分 1.在一阶逻辑中将下列命题符号化. 所有的整数，不是负整数，就是正整数，或者是零. 解 F：x是整数G：x是正整数H：x是负整数L：x是0 ）或x GHL） x GHL 有的实数是有理数有的实数是无理数. 解 F：x是实数 G：x是有理数 不存在能表示成分数无理数. 解 F：x能表示成分数 G：x是无理数 若x、y都是实数，且xy，则x+2y+2. 解 F：x是实数 H：xy ） xyF H H不存在最大的自然数. 解 F：x是自然数 H：xy $xyH：x
7、是无理数 ）$y H） $xG）x F） $x F H） 在北京卖菜的人不全是外地人. 解 设M(x)：x是外地人. F(x)：x在北京卖菜. 则符号化为$x(M(x)F(x). 设：M(x)：x是火车. H(x)：x是轮船. F(x)：x是汽车. G(x,y)：x比y快. 则“火车都比轮船快.”符号化为xy(M(x)H(y)G(x,y). 则“有的火车比有的汽车快.”符号化为$x$y(M(x)F(y)G(x,y). 则“不存在比所有火车都快的汽车.”符号化为($x(F(x)y(M(y)G(x,y). 4、 指出下列公式中的指导变元，量词的辖域，各个体变项的自由出现和约束出现： x(F(x)G
8、(x,y) 解 x的辖域：F(x)G(x,y).x是指导变元. x是约束出现，y是自由出现. xF(x,y)$yG(x,y) 解 x的辖域：F(x,y).x是指导变元. x是约束出现，y是自由出现. $y的辖域：G(x,y).y是指导变元. x是自由出现，y是约束出现. 5、 证明下面公式既不是永真式也不是矛盾式： x(F(x)$y(G(y)H(x,y) 证明 1o解释I1：D=R，F(x)：x是正数.G(y)：y是负数.H(x,y)：x+y=0. 存在负数y，使得x+y=0.在该解释下，命题为“真”. x(F(x)$y(G(y)H(x,y)指对任意正数x，o2解释I2：D=1,2,-3，F(
9、x)：x是正数.G(y)：y是负数.H(x,y)：x+y=0.则对x=1时，不存在负数yD，使x+y=0，故在该解释下，命题为“假”，所以公式既不是永真式也不是矛盾式. xy(F(x)G(y)H(x,y) 6、设个体域D=a,b,c，消去下列各式的量词： x$y(F(x)G(y) ($y(F(a)G(y)($y(F(b)G(y)($y(F(c)G(y) 第 3 页 共 6 页 (F(a)G(a)(F(a)G(b)(F(a)G(c)(F(b)G(a)(F(b)G(b)(F(b)G(c)(F(c)G(a)(F(c)G(b)(F(c)G(c) xy(F(x)G(y)(y(F(a)G(y)(y(F(b
10、)G(y)(y(F(c)G(y) (F(a)G(a)(F(a)G(b)(F(a)G(c) (F(b)G(a)(F(b)G(b)(F(b)G(c) (F(c)G(a)(F(c)G(b)(F(c)G(c) 7、求前束范式 $xyF） yG）$z H. GH） xF(x)yG(x,y)xF(x)yG(z,y)$xy(F(x)G(z,y) x(F(x,y)$yG(x,y,z)x(F(x,t)$yG(x,y,z)x$y(F(x,t)G(x,y,z) xF(x,y)$xG(x,y)xF(x,t)$zG(z,y) (xF(x,t)$zG(z,y)($zG(z,y)xF(x,t) $x$z(F(x,t)G(z
11、,y)($sG(s,g)rF(r,h) $x$z(F(x,t)G(z,y)sr(G(s,g)F(r,h) $x$zsr(F(x,t)G(z,y)(G(s,g)F(r,h) 8、在自然推理系统 NL中构造下面推理的证明. 前提：$xFyH），$xR$yG 结论：$x R）$x H 证明1 $x R） F R F R $x F $xFyH） yH） GH R $x R $xR$yG $yG G H $x H 证明2： $x R） $x F$x R） $x F $xFyH） yH） GH 第 4 页 共 6 页 $xR$yG $x R） $yG G H $x H 人都喜欢吃蔬菜.但说所有的人都喜欢吃
12、鱼是不对的.所以存在只喜欢吃蔬 菜而不喜欢吃鱼的人. F：x是人 G：喜欢吃蔬菜 H ：喜欢吃鱼 前提：xG） xH） 结论：$x GH） 证明： xH） $ xH） $ xH） FH xG） FG F G FH G $x GH） 任意三角形的内角和等于1800，ABC三角形，则ABC的内角和等于1800. 证明 设F：x是三角形 G：x的内角和等于1800 a：ABC 前提：xG） F 结论： G 证明： x G） F G F G 每个喜欢步行的人都不喜欢骑自行车.每个人或者喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车.所以有的人不喜欢步行. 证明 设F：x喜欢步行 G：x喜欢骑自行车 H：x喜欢乘车 x G），x H，$x H）$x F $x H H x H） G H G x G） F G F 第 5 页 共 6 页 $x F (5)每个科学工作者都是刻苦钻研的，每个刻苦钻研而有聪明的人在他的事业中都将获得成功.王大海是科学工作者，并且是聪明的.所以王大海在他的事业中将获得成功. 证明 设F：x是科学工作者 G：x喜欢钻研 H：x聪明 W：x事业成功 a：王大海 xG），x HW），F，HW x G） F G） x HW） G HW F G H G H W 第 6 页 共 6 页
