数理逻辑考试题及答案(共5页).doc

精选优质文档-倾情为你奉上“离散数学”数理逻辑部分考核试题答案一、命题逻辑基本知识（5分）1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分）（0）小刘既不怕吃苦，又爱钻研。解：Øpq，其中，P：小刘怕吃苦；q：小刘爱钻研。（1）只有不怕敌人，才能战胜敌人。解：qØp，其中，P：怕敌人；q：战胜敌人。（2）只要别人有困难，老张就帮助别人，除非困难已经解决了。解：Ør(pp)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。（3）小王与小张是亲戚。解：p，其中，P：小王与小张是亲戚。2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分）（0）A：(Ø(p«q)®(pÙØq) Ú(ØpÙq)Ú r（1）B：(pÙØ(q®p) Ù(rÙq)（2）C：(p«Ør) ®(q«r)（3）E：p®(pÚqÚr)（4）F：Ø(q®r) Ùr解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分）（0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p®q) Ùq®p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。（1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： (p Ù q) s) Ùp Ùq) (r Ú s)。计算推理公式真值为真，由此，本题推理正确。二、命题逻辑等值演算（5分）1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分）（0）求公式p(qr) (p(ØqØr)的主析取范式。解：p(qr) (p(ØqØr) Û Øp(qrp) (qrØqØr) Û Øp(qrp) 0 Û (pqr) Û (Øp11) (qrp)Û (Øp(qØq)(rØr) (qrp) Û (Øp(qØq)(rØr) m7Û (ØpØqØr)(ØpØqr)(ØpqØr)(Øpqr)m7Ûm0m1m2m3m7.（1）求公式Ø(Ø(pq) (ØqØp)的主合取范式。解：Ø(Ø(pq) Ú (ØqØp) Û (pq) Ú (pq) Û (pq)Û ØpÚq Û M2.（2）求公式(p(pq) r的主析取范式。解：(p(pÚq) Úr Û ØpÚ (pÚq) Úr Û (ØpÚpÚqÚ r) Û1Ûm0m1m2m3m4m5m6m7.2、应用分析（总共2题，完成的题号为学号尾数取2的余，完成1题。共3分）（0）某村选村委，已知赵炼玉、钱谷王、孙竹湾被选进了村委，三村民甲、乙、丙预言： 甲预言：赵炼玉为村长，钱谷王为村支书。 乙预言：孙竹湾为村长，赵炼玉为村支书。 丙预言：钱谷王为村长，赵炼玉为村妇女主任。村委分工公布后发现，甲乙丙三人各预测正确一半。赵炼玉、钱谷王、孙竹湾各担任什么职务？解：设P1：赵炼玉为村长，p2：钱谷王为村长，p3：孙竹湾为村长，q1：赵炼玉为村支书，q2: 钱谷王为村支书，r1：赵炼玉为村妇女主任。判断公式FÛ( (p1ÙØq2) Ú (Øp1Ùq2) Ù ( (p3ÙØq1) Ú (Øp3Ùq1) Ù ( (p2ÙØr1) Ú (Øp2Ùr1) Û Øp1Ùq2Ùp3ÙØq1ÙØq2Ùr1Û1Ûq2Ùp3ÙÙr1，由此，钱谷王为村支书，孙竹湾为村长，赵炼玉为村妇女主任。说明：p1、p2、p3有且仅有一个为真，q1、q2有且仅有一个为真。一个人不能担任两职，一个职务不可由两人同时担任。（1）某公司派赵、钱、孙、李、周五人出国学习。选派条件是： 若赵去，钱也去。 李、周两人必有一人去。 钱、孙两人去且仅去一人。 孙、李两人同去或同不去。 如周去，则赵、钱也同去。如何选派他们出国？解： 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去。 (1) (p®q) (2) (sÚu) (3) (qÙØr)Ú(ØqÙr) (4) (rÙs)Ú(ØrÙØs) (5) (u®(pÙq) (1) (5)构成的合取式为：A= (p®q)Ù(sÚu)Ù(qÙØr)Ú(ØqÙr)Ù (rÙs)Ú(ØrÙØs)Ù(u®(pÙq)Û (ØpÙØqÙrÙsÙØu)Ú(pÙqÙØrÙØsÙu)由此可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去），或派赵、钱、周去（孙、李不去）。三、命题逻辑推理（5分）在自然推理系统中，构造下列推理过程（总共3题，完成的题号为学号尾数取3的余，完成1题。共5分）（0）如果张老师出国，则若李老师出国，王老师出国。现在的情况是张老师与李老师都要出国。所以，王老师不出国，则孙老师出国。解：形式化：p：张老师出国；q：李老师出国；r：王老师出国；s：孙老师出国。前提：p®(q®r)，pÙq结论：Ør®s证明： p®(q®r) 【前提引入】 ØpÚ (ØqÚr) Û pÙq®r 【置换】 pÙq 【前提引入】 r 【假言推理】 r Ús 【附加规则】 Ø Ø rs 【置换】 Ør®s 【置换】 证毕。（1）若张同学与李同学是乐山人，则王同学是雅安人，若王同学是雅安人，则他喜欢吃雅鱼，然而，王同学不喜欢吃雅鱼，张同学是乐山人。所以，李同学不是乐山人。解：形式化：p：张同学是乐山人；q：李同学是乐山人；r：王同学是雅安人；s：王同学喜欢吃雅鱼。前提：(pÙq)® r，r® s，Øs，p结论：Øq证明： (pÙq)® r 【前提引入】 r® s 【前提引入】 (pÙq)® s 【假言三段论】 Øs 【前提引入】 Ø(pÙq) 【拒取式】 ØpÚØq 【置换】 p 【前提引入】 Øq 【析取三段论】 证毕。（2）若n是偶数并且大于5，则m是奇数。只有n是偶数，m才大于6。现有n大于5。所以，若m大于6，则m是奇数。解：形式化：p：n是偶数；q：n大于5；r：m是奇数；s：m大于6。前提：(pÙq)® r，s® p，q结论：s® r证明： q 【前提引入】 ØsÚq 【附加规则】（这是证明的关键） s® q 【置换】 s® p 【前提引入】 (s® q）Ùq（s® p） 【合取】 s®(pÙq ) 【置换】 (pÙq)® r 【前提引入】 s®r 【假言三段论】 证毕。四、一阶逻辑的基本概念（5分）1、一阶逻辑命题形式化（总共6题，完成的题号为学号尾数取6的余，完成1题。共2分）（0）人人都生活在地球上。解："x(F(x) G(x)，其中，F(x)：x是人，G(x)：x生活在地球上。（1）有的人长着金色的头发。解：$x (F(x) ÙG(x)，其中，F(x)：x是人，G(x)：x长着金色的头发。（2）没有能表示成分数的无理数。解：Ø$x (F(x) ÙG(x)，其中，F(x)：x是无理数，G(x)：x能表示成分数。（3）说所有的男人比所有的女人力气大是不正确的。解：Ø"x"y (F(x) Ù G(y)S(x,y)，其中，F(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力气大。（4）有的学生不住在校内。解：$x (F(x) ÙØG(x)，其中，F(x)：x是学生，G(x)：x住在校内。（5）说有的男人比所有的女人力气大是正确的。解：$x (F(x) Ù "y(G(x)S(x,y)，其中，F(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力气大。2、给出下列公式的一个成真解释和一个成假解释（总共3题，完成的题号为学号尾数取3的余，完成1题。共3分）（0）"x(F(x) Ú G(x)解：取解释I1：个体域为人的集合，F(x)：x是男人，G(x)：x是女人。则在I1解释下，"x(F(x) Ú G(x)为真命题。取解释I2：个体域为人的集合，F(x)：x是中国人，G(x)：x是美国人。则在I2解释下，"x(F(x) Ú G(x)为假命题。（1）$x(F(x) Ù G(x) Ù H(x)解：取解释I1：个体域为人的集合，F(x)：x是教师，G(x)：x是党员，H(x)：x是班主任。则在I1解释下，$x(F(x) Ù G(x) Ù H(x)为真命题。取解释I2：个体域为人的集合，F(x)：x是男人，G(x)：x是女人，H(x)：x是班主任。则在I2解释下，$x(F(x) Ù G(x) Ù H(x)为假命题。（2）$x(F(x) Ù"y( G(y) Ù H(x,y)解：取解释I1：个体域为整数集合，F(x)：x是正整数，G(x)：x是负整数，H(x,y)：x比y大。则在I1解释下，$x(F(x) Ù"y( G(y) Ù H(x,y)为真命题。取解释I2：个体域为自然数集合，F(x)：x是奇数，G(x)：x是偶数，H(x,y)：x比y大。则在I2解释下，$x(F(x) Ù"y( G(y) Ù H(x,y)为假命题。五、一阶逻辑等值演算（5分）1、证明等值式（总共2题，完成的题号为学号尾数取2的余，完成1题。共1分）（0）证明等值式："x(A(x)®B)Û $xA(x)®B。证明："x(A(x)®B) Û "x(ØA(x) ÚB) Û "xØA(x) ÚB Û Ø$x A(x) ÚB Û $x A(x) B。（1）证明等值式：$x(A(x)®B)Û"xA(x)®B。解：$x(A(x)®B) Û $x (ØA(x) ÚB) Û $x ØA(x) ÚB Û Ø"x A(x) ÚB Û "x A(x) B2、给出下列公式的前束范式（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分）（0）Ø"x(F(x) G(x)解：Ø"x(F(x) G(x) Û $x Ø(ØF(x) ÚG(x) Û $x (F(x) Ù ØG(x)（1）Ø$x(F(x) Ù G(x)解：Ø$x(F(x) Ù G(x) Û "x Ø(F(x) ÙG(x) Û "x (ØF(x) Ú ØG(x) Û "x (F(x) ØG(x)（2）$yF(x,y) Ù"xG(x,y,z)解：$yF(x,y) Ù"xG(x,y,z) Û $yF(u,y) Ù"xG(x,v,z) Û $y "x (F(u,y) ÙG(x,v,z)（3）"xF(x) $y (G(x,y) ÙH(x,y)解："xF(x) $y (G(x,y) ÙH(x,y) Û "zF(z) $y (G(x,y) ÙH(x,y)Û "z(F(z) $y (G(x,y) ÙH(x,y) Û "z$y(F(z) (G(x,y) ÙH(x,y)3、例证（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分）（0）举例说明“"对Ú无分配律”。解："对Ú无分配律指：不存在等价关系"x(A(x) ÚB(x)Û"xA(x) Ú"xB(x)。例如，取解释I：个体域为人的集合，F(x)：x是男人，G(x)：x是女人。"x(A(x) ÚB(x)的真值为真，而"xA(x) Ú"xB(x)的真值为假。（1）举例说明“$对Ù无分配律”。解：$对Ù无分配律指：不存在等价关系$x(A(x) ÙB(x) Û $x A(x)Ù$x B(x)。例如，取解释I：个体域为人的集合，F(x)：x是男人，G(x)：x是女人。$x (A(x) ÙB(x)的真值为假，而$x A(x) Ù$x B(x)的真值为真。六、一阶逻辑推理（5分）在自然推理系统中，构造下列推理过程（总共2题，完成的题号为学号尾数取2的余，完成1题。共5分）（0）每个喜欢步行的人都不喜欢骑自行车，每个人或者喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车。所以，有的人不喜欢步行。（个体域为人类集合）解：形式化：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(F(x) ØG(x) 【前提引入】 F(y) ØG(y) 【"- 】 "x(G(x) ÚH(x) 【前提引入】 G(y) ÚH(y) 【"- 】 ØG(y) H(y) 【置换】 F(y) H (y) 【假言三段论】 ØH(y) ØF (y) 【置换】 ØH(y) $x ØF (x) 【 $+ 】 $xØH(x) $x ØF (x) 【 $+ 】 $xØH(x) 【前提引入】 $x ØF (x) 【假言推理】 证毕。（1）每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且聪明。所以，王大海在他的事业中将获得成功。（个体域为人类集合）解：形式化：F(x)：x是科学工作者；G(x)：x刻苦钻研；H(x)：x聪明；I(x)：x事业成功；a:王大海。前提："x(F(x) G(x)，"x(G(x) ÙH(x) I(x)，F(a)，H(a)。结论：I(a)证明： F(a) 【前提引入】 "x(F(x) G(x) 【前提引入】 F(a) G(a) 【"-】 G(a) 【假言推理】 H(a) 【前提引入】 "x(G(x) ÙH(x) I(x) 【前提引入】 G(a) ÙH(a) I(a) 【"- 】 G(a) ÙH(a) 【合取】 I(a) 【假言推理】 证毕。专心-专注-专业