數(shù)理邏輯考試題及答案

“離散數(shù)學”數(shù)理邏輯部分考核試題笞案 ★ 一、命題邏輯基本知識(5分)1、將下列命題符號化(總共4題，完成的題號為學號尾數(shù)取4的余，完成1題。共2分(0)小劉既不怕吃苦，又愛鉆研。解：「pAq,其中，P：小劉怕吃苦；q：小劉愛鉆研。(1)只有不怕敵人，才能戰(zhàn)勝敵人。解：q-「p,其中，P：怕敵人；q：戰(zhàn)勝敵人。(2)只要別人有困難，老張就幫助別人，除非困難已經(jīng)解決了。解：「rf(p-p),其中，P：別人有困難；q：老張幫助別人；r：困難解決了。(3)小王與小張是親戚。解：p,其中，P：小王與小張是親戚。2、判斷下列公式的類型(總共5題，完成的題號為學號尾數(shù)取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(xiàn)為矛盾式。3、判斷推理是否正確(總共2題，完成的題號為學號尾數(shù)取2的余，完成1題。共2分)(0)設y=2|x|,x為實數(shù)。推理如下：如y在x=0處可導，則y在x=0處連續(xù)。發(fā)現(xiàn)y在x=0處連續(xù)，所以，y在x=0處可導。解：設y=2|x|,x為實數(shù)。令P：y在x=0處可導，q：y在x=0處連續(xù)。由此，p為假，q為真。本題推理符號化為：(p—q)Aq—p。由p、q的真值，計算推理公式真值為假，由此，本題推理不正確。(1)若2和3都是素數(shù)，則6是奇數(shù)。2是素數(shù)，3也是素數(shù)。所以，5或6是奇數(shù)。解：令p:2是素數(shù)，q:3是素數(shù)，r:5是奇數(shù)，s:6是奇數(shù)。由此，p=1,q=1,r=1,s=0。本題推理符號化為：((paq)-s)ApAq)-(rvs)。計算推理公式真值為真，由此，本題推理正確。二、命題邏輯等值演算(5分)1、用等值演算法求下列公式的主析取范式或主合取范式(總共3題，完成的題號為學號尾數(shù)取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題，完成的題號為學號尾數(shù)取2的余，完成1題。共3分)(0)某村選村委，已知趙煉玉、錢谷王、孫竹灣被選進了村委，三村民甲、乙、丙預言：甲預言：趙煉玉為村長，錢谷王為村支書。乙預言：孫竹灣為村長，趙煉玉為村支書。丙預言：錢谷王為村長，趙煉玉為村婦女主任。村委分工公布后發(fā)現(xiàn)，甲乙丙三人各預測正確一半。趙煉玉、錢谷王、孫竹灣各擔任什么職務？解：設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分)在自然推理系統(tǒng)中,構造下列推理過程(總共3題,完成的題號為學號尾數(shù)取3的余,完成1題。共5分)(0)如果張老師出國,則若李老師出國,王老師出國?，F(xiàn)在的情況是張老師與李老師都要出國。所以,王老師不出國,則孫老師出國。解：形式化：r：王老師出國；s：孫老師出國?！厩疤嵋搿俊劲僦脫Q】r：王老師出國；s：孫老師出國。【前提引入】【①置換】【前提引入】【②③假言推理】【④附加規(guī)則】【⑤置換】【⑥置換】 證畢前提：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是偶數(shù)并且大于5,則m是奇數(shù)。只有n是偶數(shù)，m才大于6?，F(xiàn)有n大于5。所以，若m大于6m大于6,則m是奇數(shù)。解：形式化：p：n是偶數(shù)；q：n大于5；r：前提：(pAq)fr，sfp，q結論：sfr證明：①q—svqsfqsfp(sfq)Aq(sfp)sf(pAq)(pAq)frsfrm是奇數(shù)；s：m大于6?！厩疤嵋搿俊劲俑郊右?guī)則(這是證明的關鍵)【②置換】【前提引入】【③④合取】【⑤置換】【前提引入】【⑥⑦假言三段論】證畢。四、一階邏輯的基本概念(5分)1、一階邏輯命題形式化(總共6題,完成的題號為學號尾數(shù)取6的余,完成1題。共2分)(0)人人都生活在地球上。解：Vx(F(x)-G(x)),其中，F(xiàn)(x)：x是人，G(x)：x生活在地球上。(1)有的人長著金色的頭發(fā)。解：3x(F(x)aG(x)),其中，F(xiàn)(x)：x是人，G(x)：x長著金色的頭發(fā)。(2)沒有能表示成分數(shù)的無理數(shù)。解：—3x(F(x)aG(x)),其中，F(xiàn)(x)：x是無理數(shù)，G(x)：x能表示成分數(shù)。(3)說所有的男人比所有的女人力氣大是不正確的。解：—VxVy(F(x)aG(y)-S(x,y)),其中，F(xiàn)(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力氣大。(4)有的學生不住在校內(nèi)。解：3x(F(x)a—G(x)),其中，F(xiàn)(x)：x是學生，G(x)：x住在校內(nèi)。(5)說有的男人比所有的女人力氣大是正確的。。解：3x(F(x)aVy(G(x)fS(x,y))),其中，F(xiàn)(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力氣大。2、給出下列公式的一個成真解釋和一個成假解釋(總共3題,完成的題號為學號尾數(shù)取3的余,完成1題。共3分)(0)Vx(F(x)vG(x))解：取解釋11：個體域為人的集合，F(xiàn)(x)：x是男人，G(x)：x是女人。則在11解釋下，Vx(F(x)vG(x))為真命題。取解釋I2：個體域為人的集合，F(xiàn)(x)：x是中國人，G(x)：x是美國人。則在I2解釋下，Vx(F(x)vG(x))為假命題。3x(F(x)aG(x)aH(x))解：取解釋11：個體域為人的集合，F(xiàn)(x)：x是教師，G(x)：x是黨員，H(x)：x是班主任。則在11解釋下，3x(F(x)aG(x)aH(x))為真命題。取解釋I2：個體域為人的集合，F(xiàn)(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：個體域為整數(shù)集合，F(xiàn)(x)：x是正整數(shù)，G(x)：x是負整數(shù)，H(x,y)：x比y大。則在11解釋下，3x(F(x)AVy(G(y)△H(x,y)))為真命題。取解釋I2：個體域為自然數(shù)集合，F(xiàn)(x)：x是奇數(shù)，G(x)：x是偶數(shù)，H(x,y)：x比y大。則在I2解釋下，3x(F(x)AVy(G(y)△H(x,y)))為假命題。五、一階邏輯等值演算(5分)1、證明等值式(總共2題，完成的題號為學號尾數(shù)取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題，完成的題號為學號尾數(shù)取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題，完成的題號為學號尾數(shù)取2的余，完成1題。共2分(0)舉例說明“V對v無分配律”。解：V對v無分配律指：不存在等價關系Vx(A(x)vB(x))oVxA(x)vVxB(x)。例如，取解釋I：個體域為人的集合，F(xiàn)(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(xiàn)(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)在自然推理系統(tǒng)中，構造下列推理過程(總共2題，完成的題號為學號尾數(shù)取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)每個科學工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學工作者，并且聰明。所以，王大海在他的事業(yè)中將獲得成功。(個體域為人類集合)解：形式化：F(x)：x是科學工作者；G(x)：x刻苦鉆研；H(x)：x聰明；I(x)：x事業(yè)成功；a:王大海。前提：Vx(F(x)-G(x)),Vx(G(x)aH(x)-I(x)),F(a),H(a)。結論：I(a)【前提引入】【前提引入】【②V-】【①③假言推理】【前提引入】【前提引入】【⑥V-】【④⑤合取】【⑦⑧假言推理】證畢。數(shù)理邏輯部分綜合練習及答案一、單項選擇題1.設P我將去打球，。：我有時間.命題“我將去打球，僅當我有時間時”符號化為().A.QfP B.pfQ C.尸》。 D.「尸因為語句“僅當我有時間時”是“我將去打球”的必要條件，一般地，當語句是由“……，僅當……”組成,它的符號化用條件聯(lián)結詞.所以選項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注：如果該題改為填寫約束變元或自由變元的填空題，大家也應該掌握.補充題：設個體域為自然數(shù)集合，下列公式中是真命題的為( )A.Vx3y(x-y=1) B.Vx3y(x+y=0)C.3xVy(x-y=x) D.3xVy(x+y=2y)因為選項A表示：對任一自然數(shù)％存在自然數(shù)y滿足孫=1,這樣的y是不存在的選項B表示：對任一自然數(shù)％存在自然數(shù)y滿足％+尸0,這樣的y也是不存在的選項C表示：存在一自然數(shù)％自然數(shù)對任意自然數(shù)y滿足％取即可，故選項C正確正確答案：C二、填空題.命題公式尸-(Qv尸)的真值是.因為尸“(Qv尸所以應該填寫：1.應該填寫：1問：命題公式Q-Q、Qv「Q的真值是什么？.設P他生病了，Q：他出差了.H：我同意他不參加學習.則命題“如果他生病或出差了，我就同意他不參加學習”符號化的結果為.一般地，當語句是由“如果……，那么……”，或"若……，則……”組成，它的符號化用條件聯(lián)結詞.應該填寫：(PQ)R.含有三個命題變項P,Q,R的命題公式P Q的主析取范式是.復習主析取范式的定義：定義對于給定的命題變元，如果有一個等價公式，它僅僅有小項的析取組成，則該等價式稱為原式的主析取范式.而小項的定義是：定義n個命題變元的合取式，稱為布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xià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)消去量詞后的等值式為.因為在有限個體域下，消除量詞的規(guī)則為：設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},或謂詞公式變?yōu)?x(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%)為“％是奇數(shù)”，則謂詞公式(女)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個命題變元的析取式，稱為布爾析取或大項，其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且