数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题笞案 ★ 一、命题逻辑基本知识(5分)1、将下列命题符号化(总共4题，完成的题号为学号尾数取4的余，完成1题。共2分(0)小刘既不怕吃苦，又爱钻研。解：「pAq,其中，P：小刘怕吃苦；q：小刘爱钻研。(1)只有不怕敌人，才能战胜敌人。解：q-「p,其中，P：怕敌人；q：战胜敌人。(2)只要别人有困难，老张就帮助别人，除非困难已经解决了。解：「rf(p-p),其中，P：别人有困难；q：老张帮助别人；r：困难解决了。(3)小王与小张是亲戚。解：p,其中，P：小王与小张是亲戚。2、判断下列公式的类型(总共5题，完成的题号为学号尾数取5的余，完成1题。共1分(0)A：(「(p—q).((pA「q)v(^pAq)))vrB：(pA「(q.p))A(rAq)C：(p—「r)—(q—r)E：p—(pvqvr)F：「(q—r)a解：用真值表判断，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)Aq—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。本题推理符号化为：((paq)-s)ApAq)-(rvs)。计算推理公式真值为真，由此，本题推理正确。二、命题逻辑等值演算(5分)1、用等值演算法求下列公式的主析取范式或主合取范式(总共3题，完成的题号为学号尾数取3的余，完成1题。共2分)(0)求公式p-((qAr)A(pV(「qA「r)))的主析取范式。解：p-((qAr)A(pV(「qA「r)))=「pV(qArAp)V(qArA「qA「r)=「pV(qArAp)V0=(pAqAr)V=(「pA1A1)V(qArAp)o(「pA(qV「q)A(rV「r))V(qArAp)o(「pA(qV「q)A(rV「r))Vm7=(「pA「qA「r)V(「pA「qAr)V(「pAqA「r)V(「pAqAr)Vm7om0Vm1Vm2Vm3Vm7.(1)求公式「(「(p-q))V(「q-「p)的主合取范式。解：」(「(p-q))v(「q-「p)o(p-q)v(p-q)o(p-q)o「pvqoM2.(2)求公式(p-(pVq))Vr的主析取范式。

解：(pf(pvq))vr=「pv(pvq)vr=(^pvpvqvr)=1^mOVmlVm2Vm3Vm4Vm5Vm6Vm7.2、应用分析(总共2题，完成的题号为学号尾数取2的余，完成1题。共3分)(0)某村选村委，已知赵炼玉、钱谷王、孙竹湾被选进了村委，三村民甲、乙、丙预言：甲预言：赵炼玉为村长，钱谷王为村支书。乙预言：孙竹湾为村长，赵炼玉为村支书。丙预言：钱谷王为村长，赵炼玉为村妇女主任。村委分工公布后发现，甲乙丙三人各预测正确一半。赵炼玉、钱谷王、孙竹湾各担任什么职务？解：设P1：赵炼玉为村长，p2：钱谷王为村长，p3：孙竹湾为村长，q1：赵炼玉为村支书，q2:钱谷王为村支书，r1：赵炼玉为村妇女主任。判断公式F=((plA「q2)v(「plAq2))△((p3A「q1)v(「p3^q1))△((p2A「r1)v(「p2^r1))=「p1Aq2Ap3A「q1A「q2Ar1=1=q2Ap3aa「1,由此，钱谷王为村支书，孙竹湾为村长，赵炼玉为村妇女主任。说明：p1、p2、p3有且仅有一个为真，q1、q2有且仅有一个为真。一个人不能担任两职，-个职务不可由两人同时担任。(1)某公司派赵、钱、孙、李、周五人出国学习。选派条件是：①若赵去，钱也去。②李、周两人必有一人去。③钱、孙两人去且仅去一人。④孙'、李两人同去或同不去。⑤如周去，则赵、钱也同去。如何选派他们出国？解：①设p：派赵去，牛派钱去，,：派孙去，s:派李去，u:派周去。②⑴(ptq) (2)(svu) (3)((qa「r)v([qar))((rAs)v(「rA「s)) (5)(ut(paq))③(1)~(5)构成的合取式为：A=(ptq)A(svu)A((qA「r)v(「qAr))A((rAs)v(「rA「s))A(ut(pAq))=(「pA「qArAsA「u)v(pAqA「rA「sAu)由此可知，A的成真赋值为00110与11001,因而派孙、李去(赵、钱、周不去)，或派赵、钱、周去(孙、李不去)。三、命题逻辑推理(5分)在自然推理系统中,构造下列推理过程(总共3题,完成的题号为学号尾数取3的余,完成1题。共5分)(0)如果张老师出国,则若李老师出国,王老师出国。现在的情况是张老师与李老师都要出国。所以,王老师不出国,则孙老师出国。解：形式化：r：王老师出国；s：孙老师出国。【前提引入】【①置换】r：王老师出国；s：孙老师出国。【前提引入】【①置换】【前提引入】【②③假言推理】【④附加规则】【⑤置换】【⑥置换】 证毕前提：pT(q—r),pAq结论'：「।r-ts证明：①p-(q-r)「pv(「qvr)=pAq-rpAqrrvs「「rVs「r-s(1)若张同学与李同学是乐山人,则王同学是雅安人,若王同学是雅安人,则他喜欢吃雅鱼,然而,

王同学不喜欢吃雅鱼，张同学是乐山人。所以，李同学不是乐山人。解：形式化：p：张同学是乐山人；q：李同学是乐山人；r：王同学是雅安人；s：王同学喜欢吃雅鱼。前提：(p前提：(p△q)fr,rfs,」s结论：」q证明：①(pAq)frrfs(pAq)fs「s⑤[Mq)—pv—iqp—qp【前提引入】【前提引入】【①②假言三段论】【前提引入】【③④拒取式】【⑤置换】【前提引入】【⑥⑦析取三段论】证毕。(2)若n是偶数并且大于5,则m是奇数。只有n是偶数，m才大于6。现有n大于5。所以，若m大于6m大于6,则m是奇数。解：形式化：p：n是偶数；q：n大于5；r：前提：(pAq)fr，sfp，q结论：sfr证明：①q—svqsfqsfp(sfq)Aq(sfp)sf(pAq)(pAq)frsfrm是奇数；s：m大于6。【前提引入】【①附加规则(这是证明的关键)【②置换】【前提引入】【③④合取】【⑤置换】【前提引入】【⑥⑦假言三段论】证毕。四、一阶逻辑的基本概念(5分)1、一阶逻辑命题形式化(总共6题,完成的题号为学号尾数取6的余,完成1题。共2分)(0)人人都生活在地球上。解：Vx(F(x)-G(x)),其中，F(x)：x是人，G(x)：x生活在地球上。(1)有的人长着金色的头发。解：3x(F(x)aG(x)),其中，F(x)：x是人，G(x)：x长着金色的头发。(2)没有能表示成分数的无理数。解：—3x(F(x)aG(x)),其中，F(x)：x是无理数，G(x)：x能表示成分数。(3)说所有的男人比所有的女人力气大是不正确的。解：—VxVy(F(x)aG(y)-S(x,y)),其中，F(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力气大。(4)有的学生不住在校内。解：3x(F(x)a—G(x)),其中，F(x)：x是学生，G(x)：x住在校内。(5)说有的男人比所有的女人力气大是正确的。。解：3x(F(x)aVy(G(x)fS(x,y))),其中，F(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力气大。2、给出下列公式的一个成真解释和一个成假解释(总共3题,完成的题号为学号尾数取3的余,完成1题。共3分)(0)Vx(F(x)vG(x))解：取解释11：个体域为人的集合，F(x)：x是男人，G(x)：x是女人。则在11解释下，Vx(F(x)vG(x))为真命题。取解释I2：个体域为人的集合，F(x)：x是中国人，G(x)：x是美国人。则在I2解释下，Vx(F(x)vG(x))为假命题。3x(F(x)aG(x)aH(x))解：取解释11：个体域为人的集合，F(x)：x是教师，G(x)：x是党员，H(x)：x是班主任。则在11解释下，3x(F(x)aG(x)aH(x))为真命题。取解释I2：个体域为人的集合，F(x)：x是男人，G(x)：x是女人，H(x)：x是班主任。则在I2解释下，3x(F(x)aG(x)aH(x))为假命题。3x(F(x)AVy(G(y)aH(x,y)))解：取解释11：个体域为整数集合，F(x)：x是正整数，G(x)：x是负整数，H(x,y)：x比y大。则在11解释下，3x(F(x)AVy(G(y)△H(x,y)))为真命题。取解释I2：个体域为自然数集合，F(x)：x是奇数，G(x)：x是偶数，H(x,y)：x比y大。则在I2解释下，3x(F(x)AVy(G(y)△H(x,y)))为假命题。五、一阶逻辑等值演算(5分)1、证明等值式(总共2题，完成的题号为学号尾数取2的余，完成1题。共1分)(0)证明等值式：Vx(4(x)fB)omxA(x)-B。证明：Vx(A(x).B)oVx(「A(x)vB)oVx「A(x)vBo「mxA(x)vB3xA(x)fB。(1)证明等值式：mx(4(x)fB)oVx4(x)-B。解：mx(4(x)fB)omx(「A(x)vB)omx「A(x)vB=「VxA(x)vB=VxA(x)-B2、给出下列公式的前束范式(总共4题，完成的题号为学号尾数取4的余，完成1题。共2分(0)「Vx(F(x)-G(x))解：「Vx(F(x)-G(x))o3x「(「F(x)vG(x))o3x(F(x)△「G(x))(1)「3x(F(x)△G(x))解：「3x(F(x)△G(x))oVx「(F(x)aG(x))oVx(「F(x)v「G(x))oVx(F(x)-「G(x))3yF(x,y)AVxG(x,y,z)解：3yF(x,y)AVxG(x,y,z)o3yF(u,y)aVxG(x,v,z)o3yVx(F(u,y)aG(x,v,z))VxF(x)-3y(G(x,y)AH(x,y))解：VxF(x)-3y(G(x,y)AH(x,y))oVzF(z)-3y(G(x,y)AH(x,y))oVz(F(z)-3y(G(x,y)AH(x,y)))oVz3y(F(z)-(G(x,y)AH(x,y)))3、例证(总共2题，完成的题号为学号尾数取2的余，完成1题。共2分(0)举例说明“V对v无分配律”。解：V对v无分配律指：不存在等价关系Vx(A(x)vB(x))oVxA(x)vVxB(x)。例如，取解释I：个体域为人的集合，F(x)：x是男人，G(x)：x是女人。Vx(A(x)vB(x))的真值为真，而VxA(x)vVxB(x)的真值为假。(1)举例说明“3对a无分配律”。解：3对△无分配律指：不存在等价关系3x(A(x)aB(x))o3xA(x)a3xB(x)。例如，取解释I：个体域为人的集合，F(x)：x是男人，G(x)：x是女人。3x(A(x)aB(x))的真值为假，而3xA(x)a3xB(x))的真值为真。六、一阶逻辑推理(5分)结论：m结论：mx「F(x)证明：①Vx(F(x)f「G(x))F(y)-「G(y)Vx(G(x)vH(x))④G(y)vH(y)⑤「G(y)-H(y)⑥F(y)-H(y)⑦「H(y)-「F(y)⑧「H(y)-3x「F(x)mx「H(x)—3x「F(x)mx「H(x)D3x「F(x)证明：①F(a)Vx(F(x)-G(x))F(a)-G(a)G(a)H(a)Vx(G(x)aH(x)-I(x))G(a)aH(a)-I(a)G(a)aH(a)I(a)在自然推理系统中，构造下列推理过程(总共2题，完成的题号为学号尾数取2的余，完成1题。共5分)(0)每个喜欢步行的人都不喜欢骑自行车，每个人或者喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车。所以，有的人不喜欢步行。(个体域为人类集合)解：形式化：F(x)：x喜欢步行；G(x)：x喜欢骑自行车；H(x)：x喜欢乘汽车。前提：Vx(F(x)f「G(x)),Vx(G(x)vH(x)),3x^H(x)【前提引入】【V-】【前提引入】【V-】【④置换】【②⑤假言三段论】【⑥置换】【⑦3+】【⑧3+】【前提引入】【⑨⑩假言推理】证毕。(1)每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且聪明。所以，王大海在他的事业中将获得成功。(个体域为人类集合)解：形式化：F(x)：x是科学工作者；G(x)：x刻苦钻研；H(x)：x聪明；I(x)：x事业成功；a:王大海。前提：Vx(F(x)-G(x)),Vx(G(x)aH(x)-I(x)),F(a),H(a)。结论：I(a)【前提引入】【前提引入】【②V-】【①③假言推理】【前提引入】【前提引入】【⑥V-】【④⑤合取】【⑦⑧假言推理】证毕。数理逻辑部分综合练习及答案一、单项选择题1.设P我将去打球，。：我有时间.命题“我将去打球，仅当我有时间时”符号化为().A.QfP B.pfQ C.尸》。 D.「尸因为语句“仅当我有时间时”是“我将去打球”的必要条件，一般地，当语句是由“……，仅当……”组成,它的符号化用条件联结词.所以选项B是正确的.正确答案：B问：如果把“我将去打球”改成“我将去学习”、“我将去旅游”等，怎么符号化呢？2.命题公式?Q的合取范式是( ).A.P2B.(PQ)(P。)c.PQD. (P复习合取范式的定义：定义一个命题公式称为合取范式，当且仅当它具有形式：…5， (n>l)其中A，a2, 4均是由命题变元或其否定所组成的析取式.由此可知，选球B和D是错的.又因为夕Q与P。不是等价的，选项A是错的.所以，选项C是正确的.正确答案：C.命题公式「(尸”Q)的析取范式是().A.尸 B」尸aQ C.「尸vQ D.尸复习析取范式的定义：定义一个命题公式称为析取范式，当且仅当它具有形式：A1VA2V-VA, (.>1)其中A，A2,A均是有命题变元或其否定所组成的合取式.由教材第167或中的蕴含等价式知道，公式「(尸-Q)与尸a是等价的，尸a满足析取范式的定义,所以，选项A是正确的.正确答案：A注：第2,3题复习了合取范式和析取范式的概念，大家一定要记住的。如果题目改为求一个变元(?或P)命题公式的合取范式或析取范式，那么答案是什么？.下列公式成立的为().A.PQ B.PfQ「PfQC.QtPP D.「P(PQ)Q因为：「P(PQ)Q(析取三段论，P171公式(10))所以，选项D是正确的.正确答案：D.下列公式()为重言式.A.「P八「QPvQ B.(QfgQ))G2a(Pv2))C.(P^(QfP))—Qf。)) D.GPv(Pa2))Q由教材第167页中的蕴含等价式，得(p-(。-夕))「Pv(QvP),(「尸-(QfQ)) Pv(^Pv2)所以，C是重言式，也就是永真式.正确答案：C说明：如果题目改为“下列公式()为永真式”，应该是一样的..设A(x)：%是人，B(x)：%是学生，则命题“不是所有人都是学生”可符号化为( ).A.(Vx)(A(x)5(%)) B.[(m%)(4(%)B(x))C.「(V%)(A(%)-5(%)) D.^(3x)(A(x)[5(%))由题设知道，表示只要是人，就是学生，而“不是所有”应该用全称量词的否定，即％,得到公式C.正确答案：c.设A(x)：%是人，B(x)：%是工人，则命题“有人是工人”可符号化为( ).A.(3x)(A(x)5(%)) B.(x)(A(x)B⑼C.[(%)(A(%)-5(%)) D.[5(%))选项A中的4%)5(%)表示％是人，而且是工人，Ek表示存在一个人，有一个人，因此印)(4%)B(x))表示“有人是工人”.正确答案：A.表达式Vx(尸(x,y)vQ(z))Amy(尺(九y)TVzQ(z))中Vx的辖域是().A.P(x,j)B.P(x,j)Q(z)C.R(x,y)D.P(x,j)R(x,y)所谓辖域是指“紧接于量词之后最小的子公式称为量词的辖域”.那么看题中紧接于量词％之后最小的子公式是什么呢？显然是？(%,y)Q(z),因此，选项B是正确的.正确答案：B注：如果该题改为判断题，即表达式Vx(P(x,y)v2(z))a才(尺(九y)fVzQ(z))中Vx的辖域是P(x,y)如何判断并说明理由呢？.在谓词公式(V%)(A(%)t5(%)C(x,y))中，( ).A.%,y都是约束变元 B.%,y都是自由变元C.%是约束变元，y都是自由变元D.%是自由变元，y都是约束变元约束变元就是受相应的量词约束的变元.而自由变元就是不受任何量词约束的变元.所以选项C是正确的.正确答案：C注：如果该题改为填写约束变元或自由变元的填空题，大家也应该掌握.补充题：设个体域为自然数集合，下列公式中是真命题的为( )A.Vx3y(x-y=1) B.Vx3y(x+y=0)C.3xVy(x-y=x) D.3xVy(x+y=2y)因为选项A表示：对任一自然数％存在自然数y满足孙=1,这样的y是不存在的选项B表示：对任一自然数％存在自然数y满足％+尸0,这样的y也是不存在的选项C表示：存在一自然数％自然数对任意自然数y满足％取即可，故选项C正确正确答案：C二、填空题.命题公式尸-(Qv尸)的真值是.因为尸“(Qv尸所以应该填写：1.应该填写：1问：命题公式Q-Q、Qv「Q的真值是什么？.设P他生病了，Q：他出差了.H：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为.一般地，当语句是由“如果……，那么……”，或"若……，则……”组成，它的符号化用条件联结词.应该填写：(PQ)R.含有三个命题变项P,Q,R的命题公式P Q的主析取范式是.复习主析取范式的定义：定义对于给定的命题变元，如果有一个等价公式，它仅仅有小项的析取组成，则该等价式称为原式的主析取范式.而小项的定义是：定义n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次.由小项的定义知道，命题公式PQ中缺少命题变项R与它的否定，因此，应该补上，即TOC\o"1-5"\h\zPQPQ (R R) (P Q R) (PQ R)得到命题公式PQ的主析取范式.应该填写：(PQR) (P Q R).设个体域D={a,b},那么谓词公式3x4(%)vVyB(y)消去量词后的等值式为.因为在有限个体域下，消除量词的规则为：设D={a1,a2,…,an},则VxA(%)今A(a)aA(a)a...aA(a)2 n3xA(x)今A(a)vA(a)v...vA(a)

1 2 n所以，应该填写：(A(a)A(b))(B(a)B(b))应该填写：(A(a)A(b))(B(a)B(b))注：如果个体域是D={1,2},D={a,b,c},或谓词公式变为3x(A(x)vB(x)),怎么做？.设个体域D={1,2,3},A(x)为“x小于3”，则谓词公式(3x)A(x)的真值为.因为(3x)A(x)oA(1)vA(2)vA⑶olvlvOol应该填写：1注：若个体域D={1,2},A(x)为“x小于3”，则谓词公式(3x)A(x)的真值是什么？或：设个体域。={1,2,3},4%)为“％是奇数”，则谓词公式(女)4%)的真值是什么？.谓词命题公式(x)((A(x)5(%)) C(j))中的自由变元为.因为自由变元就是不受任何量词约束的变元，在公式(x)((A(x)5(%)) C。))中，y是不受全称量词V约束的变元.所以应该填写：y.应该填写：y问：公式中的约束变元是什么？判断：谓词命题公式(x)((A(x)5(%)) C。))中的自由变元为％,是否正确?为什么？三、公式翻译题.请将语句“今天是天晴”翻译成命题公式.解：设P今天是天晴；则命题公式为：P.问：“今天不是天晴”的命题公式是什么？.请将语句“小王去旅游，小李也去旅游.”翻译成命题公式.解：设P小王去旅游，。：小李去旅游，则命题公式为：P Q.注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“”..请将语句“他去旅游，仅当他有时间翻译成命题公式.解：设P：他去旅游，。：他有时间，则命题公式为：P Q.注：命题公式的翻译还要注意“不可兼或”的表示.例如，教材第164页的例6“T2次列车5点或6点钟开.”怎么翻译成命题公式？这里的“或”为不可兼或..请将语句“所有人都努力工作.”翻译成谓词公式.解：设P(x)：x是人，Q(x)：x努力工作.谓词公式为：(x)(P(x)Q(x)).四、判断说明题(判断下列各题，并说明理由.).命题公式「PAP的真值是1.解错误.因为「PAP是永假式(教材167页的否定律)..命题公式P八(P Q)VP为永真式.解：正确因为，由真值表PQPQPQPA(Pf Q)VP001111011011100111110001可知，该命题公式为永真式.注：如果题目改为该命题公式为永假式，如何判断并说明理由？.下面的推理是否正确，请给予说明.(x)A(x) B(x) 前提引入A(j) B(y) US(1)解：错第2步应为：A(y) B(x)因为A(x)中的x是约束变元，而B(x)中的x是自由变元，换名时，约束变元与自由变元不能混淆.五.计算题.求PtQVR的析取范式，合取范式、主析取范式，主合取范式.分析：定义对于给定的命题变元，如果有一个等价公式，它仅仅有大项的合取组成，则该等价式称为原式的主合取范式.定义n个命题变元的析取式，称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且