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

2021.03.07歐陽德創(chuàng)編2021.03.07歐陽德創(chuàng)編2021.03.07歐陽德創(chuàng)編2021.03.07歐陽德創(chuàng)編“離散數(shù)學(xué)”數(shù)理邏輯部分考核試題答案時間：2021.03.07時間：2021.03.07創(chuàng)作：歐陽德━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━一、命題邏輯基本知識（5分）1、將下列命題符號化（總共4題，完成的題號為學(xué)號尾數(shù)取4的余，完成1題。共2分）小劉既不怕吃苦，又愛鉆研。解：?p∧q，其中，P：小劉怕吃苦；q：小劉愛鉆研。只有不怕敵人，才能戰(zhàn)勝敵人。其中，P：怕敵人；q：戰(zhàn)勝敵人。經(jīng)解決了。解：?r→(p→p)，其中，P：別人有困難；q：老張幫助別人；r：困難解決了。小王與小張是親戚。解：p，其中，P：小王與小張是親戚。2、判斷下列公式的類型（總共5題，完成的題號為學(xué)號尾數(shù)取5的余，完成1題。共1分）A：(?(p?q)?((pù?q)ú(?pùq)))úrB：(pù?(q?p))ù(rùq)（2）C：(p??r)?(q?r)E：p?(púqúr)F：?(q?r)ùr解：用真值表判斷，A為重言式，B為矛盾式，C為可滿足式，E為重言式，F(xiàn)為矛盾式。3、判斷推理是否正確（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共2分）設(shè)y=2|x|，x為實數(shù)。推理如下：如y在處可導(dǎo)，則y在x=0處連續(xù)。發(fā)現(xiàn)y在x=0處連續(xù)，所以，yx=0解：設(shè)y=2|x|，x為實數(shù)。令P：y在x=0處可導(dǎo)，q：y在x=0處連續(xù)。由此，p為假，q為真。本題推理符號化為：(p?q)ùq?p。由p、q的真值，計算推理公式真值為假，由此，本題推理不正確。若2和3都是素數(shù)，則6是奇數(shù)。2是素數(shù)，也是素數(shù)。所以，56解：令p:2是素數(shù)，q:3是素數(shù)，r:5是奇數(shù)，s:6是奇數(shù)。由此，p=1，q=1，r=1，s=0。本題推理符號化為：((pùq)→s)ùpùq)→(rús值為真，由此，本題推理正確。二、命題邏輯等值演算（5分）1、用等值演算法求下列公式的主析取范式或主合取范式（總共3題，完成的題號為學(xué)號尾數(shù)取3的余，完成1題。共2分）求公式p→((q∧r)∧(p∨(?q∧?r))范式。解：p→((q∧r)∧(p∨(?q∧?r)))??p∨(q∧r∧p)∨(q∧r∧?q∧?r)??p∨(q∧r∧p)∨0?(p∧q∧r)∨?(?p∧1∧1)∨(q∧r∧p)?(?p∧(q∨?q)∧(r∨?r))∨(q∧r∧p)?(?p∧(q∨?q)∧(r∨?r))∨m7?(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨m7?m0∨m1∨m2∨m3∨m7.求公式 ?(?(p→q))∨(?q→?p)的主合取式。解：?(?(p→q))ú(?q→?p)?(p→q)ú(p→q)?(p→q)??púq?M2.求公式(p→(p∨q))∨r解：(p→(púq))úr??pú(púq)úr?(?púpúqúr)?1?m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7.2、應(yīng)用分析（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共3分）進了村委，三村民甲、乙、丙預(yù)言：甲預(yù)言：趙煉玉為村長，錢谷王為村支書。乙預(yù)言：孫竹灣為村長，趙煉玉為村支書。丙預(yù)言：錢谷王為村長，趙煉玉為村婦女主任。村委分工公布后發(fā)現(xiàn)，甲乙丙三人各預(yù)測正確一半。趙煉玉、錢谷王、孫竹灣各擔(dān)任什么職務(wù)？解：設(shè) 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有且僅有一個為真。一個人不能擔(dān)任兩職，一個職務(wù)不可由兩人同時擔(dān)任。派條件是：① 若趙去，錢也去。② 李、周兩人必有一人去。③錢、孫兩人去且僅去一人。④ 孫、李兩人同去或同不去。⑤如周去，則趙、錢也同去。如何選派他們出國？解：①設(shè)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)構(gòu)成的合取式為：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）在自然推理系統(tǒng)中，構(gòu)造下列推理過程（總共3題，完成的題號為學(xué)號尾數(shù)取 3的余，完成 1題。共分）如果張老師出國，則若李老師出國，王老師出王老師不出國，則孫老師出國。解：形式化：p：張老師出國；q：李老師出國；r：王老師出國；s：孫老師出國。前提：p?(q?r)，pùq結(jié)論：?r?s證明：①p?(q?r) 【前提引入】②?pú(?qúr)?pùq?r 【①置換】③pùq 【前提引入】④r 【②③假言推理】⑤rús 【④附加規(guī)則】⑥??r∨s 【⑤置換】⑦?r?s 若張同學(xué)與李同學(xué)是樂山人，則王同學(xué)是雅安不是樂山人。解：形式化：p：張同學(xué)是樂山人；q：李同學(xué)是樂山人；r：王同學(xué)是雅安人；s：王同學(xué)喜歡吃雅魚。前提：(pùq)?r，r?s，?s，p結(jié)論：?q證明：①(pùq)?r 【前提引入】②r?s 【前提引入】③(pùq)?s 【①②假言三段論】④?s【前提引入】⑤?(pùq)【③④拒取式】⑥?pú?q【⑤置換】⑦p【前提引入】⑧?q 證畢。若n是偶數(shù)并且大于5，則m是奇數(shù)。只有是偶數(shù)，m才大于6?，F(xiàn)有n大于5。所以，若m大6，則m解：形式化：p：n是偶數(shù)；q：n大于5；r：m是奇數(shù)；s：m大于6。前提：(pùq)?r，s?p，q結(jié)論：s?r證明：①q 【前提引入】②?súq 【①附加規(guī)則】（證明的關(guān)鍵）③s?q 【②置換】④s?p【前提引入】⑤(s?q）ùq（s?p）【③④合取】⑥s?(pùq)【⑤置換】⑦(pùq)?r 【前提引入】⑧s?r【⑥⑦假言三段論】證畢。四、一階邏輯的基本概念（5分）1、一階邏輯命題形式化（總共6題，完成的題號為學(xué)號尾數(shù)取6的余，完成1題。共2分）人人都生活在地球上。解："x(F(x)→G(x))，其中，F(xiàn)(x)：x是人，G(x)：x生活在地球上。有的人長著金色的頭發(fā)。解：$x(F(x)ùG(x))，其中，F(xiàn)(x)：x是人，G(x)：x長著金色的頭發(fā)。沒有能表示成分數(shù)的無理數(shù)。解：?$x(F(x)ùG(x))F(x)x是無理數(shù)，G(x)：x說所有的男人比所有的女人力氣大是不正確的。解：?"x"y(F(x)ùG(y)→S(x,y))，其中，F(xiàn)(x)：x是男人，G(x)：xS(x,y)：x比y有的學(xué)生不住在校內(nèi)。解：$x(F(x)ù?G(x))，其中，F(xiàn)(x)：x是學(xué)生，G(x)：x住在校內(nèi)。解：$x(F(x)ù"y(G(x)→S(x,y)))，其中，F(xiàn)(x)：x是男人，G(x)：x是女人，S(x,y)：x比y2（共3題，完成的題號為學(xué)號尾數(shù)取3的余，完成題。共3分）（0）"x(F(x)úG(x))解：取解釋I1：個體域為人的集合，F(xiàn)(x)：x是男人，G(x)：x是女人。則在I1解釋下，"x(F(x)úG(x))為真命題。取解釋 I2：個體域為人的集合，F(xiàn)(x)：x是中人，G(x)：x是美國人。則在I2解釋下，"x(F(x)úG(x))為假命題。（1）$x(F(x)ùG(x)ùH(x))解：取解釋I1：個體域為人的集合，F(xiàn)(x)：x是教師，G(x)：x是黨員，H(x)：x是班主任。I1，$x(F(x)ùG(x)ùH(x))為真命題。取解釋I2：個體域為人的集合，F(xiàn)(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：個體域為整數(shù)集合，F(xiàn)(x)：x是正整數(shù)，G(x)：x是負整數(shù)，H(x,y)：x比y大。則在I1解釋下，$x(F(x)ù"y(G(y)ùH(x,y)))為真命題。取解釋I2：個體域為自然數(shù)集合，F(xiàn)(x)：x是奇數(shù)，G(x)：x是偶數(shù)，H(x,y)：x比y大。則在I2解釋下，$x(F(x)ù"y(G(y)ùH(x,y)))為假命題。五、一階邏輯等值演算（5分）1、證明等值式（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共1分）。證明："x(A(x)?B)?"x(?A(x) úB)?"x?A(x) úB??$xA(x) úB?$xA(x) →B。。解?$x(?A(x) úB)?$x?A(x) ??"xA(x) úB?"xA(x) →B2、給出下列公式的前束范式（總共4題，完成的題號為學(xué)號尾數(shù)取4的余，完成1題。共2分）（0）?"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)) ?"x?(F(x)ùG(x))?"x(?F(x)ú?G(x))?"x(F(x)→?G(x))$yF(x,y)ù"xG(x,y,z)解 ： $yF(x,y)ù"xG(x,y,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) →?"z(F(z) → $y(G(x,y)ùH(x,y))) ?"z$y(F(z) →(G(x,y)ùH(x,y)))3、例證（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共2分）舉例說明“"對ú解："對ú無分配律指：不存在等價關(guān)系"x(A(x)úB(x))?"xA(x)ú"xB(x)。例如，取解釋I：個體域為人的集合，F(xiàn)(x)：x是男人，G(x)：x是女人。"x(A(x)úB(x))的真值為真，而"xA(x)ú"xB(x)的真值為假。舉例說明“$對ù解：$對ù無分配律指：不存在等價關(guān)系$x(A(x)ùB(x))?$xA(x)ù$xB(x)。例如，取解釋I：個體域為人的集合，F(xiàn)(x)：x是男人，G(x)：x是女人。$x(A(x)ùB(x))的真值為假，而$xA(x)ù$xB(x))的真值為真。六、一階邏輯推理（5分）在自然推理系統(tǒng)中，構(gòu)造下列推理過程（總共2題，完成的題號為學(xué)號尾數(shù)取 2的余，完成 1題。共分）者喜歡騎自行車或者喜歡乘汽車，有的人不喜歡乘汽車。所以，有的人不喜歡步行。（個體域為人類集合）解：形式化：F(x)：x喜歡步行；G(x)：x喜歡騎自行車；H(x)：x喜歡乘汽車。前提："x(F(x)→?G(x))，"x(G(x)úH(x))，$x?H(x)結(jié)論：$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) 【⑨⑩假言推理】證畢。而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且聰明。所以，王大海在他的事業(yè)中將獲得成功。（個體域為人類集合）解：形式化：F(x)：x是科學(xué)工作者；G(x)：x刻苦鉆研；