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

1、“離散數(shù)學(xué)”數(shù)理邏輯部分考核試題答案一、命題邏輯基本知識（5分）1、將下列命題符號化（總共4題，完成的題號為學(xué)號尾數(shù)取4的余，完成1題。共2分）（0）小劉既不怕吃苦，又愛鉆研。解：pq，其中，P：小劉怕吃苦；q：小劉愛鉆研。（1）只有不怕敵人，才能戰(zhàn)勝敵人。解：qp，其中，P：怕敵人；q：戰(zhàn)勝敵人。（2）只要別人有困難，老張就幫助別人，除非困難已經(jīng)解決了。解：r(pp)，其中，P：別人有困難；q：老張幫助別人；r：困難解決了。（3）小王與小張是親戚。解：p，其中，P：小王與小張是親戚。2、判斷下列公式的類型（總共5題，完成的題號為學(xué)號尾數(shù)取5的余，完成1題。共1分）（0）A：(pq)(pq)

2、(pq) r（1）B：(p(qp) (rq)（2）C：(pr) (qr)（3）E：p(pqr)（4）F：(qr) r解：用真值表判斷，A為重言式，B為矛盾式，C為可滿足式，E為重言式，F(xiàn)為矛盾式。3、判斷推理是否正確（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共2分）（0）設(shè)y=2|x|，x為實(shí)數(shù)。推理如下：如y在x=0處可導(dǎo)，則y在x=0處連續(xù)。發(fā)現(xiàn)y在x=0處連續(xù)，所以，y在x=0處可導(dǎo)。解：設(shè)y=2|x|，x為實(shí)數(shù)。令P：y在x=0處可導(dǎo)，q：y在x=0處連續(xù)。由此，p為假，q為真。本題推理符號化為：(pq) qp。由p、q的真值，計(jì)算推理公式真值為假，由此，本題推理不正確。（1

3、）若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。本題推理符號化為： (p q) s) p q) (r s)。計(jì)算推理公式真值為真，由此，本題推理正確。二、命題邏輯等值演算（5分）1、用等值演算法求下列公式的主析取范式或主合取范式（總共3題，完成的題號為學(xué)號尾數(shù)取3的余，完成1題。共2分）（0）求公式p(qr) (p(qr)的主析取范式。解：p(qr) (p(qr) p(qrp) (qrqr) p(qrp) 0 (pqr) (p11) (qrp) (p(qq)(rr) (

4、qrp) (p(qq)(rr) m7 (pqr)(pqr)(pqr)(pqr)m7m0m1m2m3m7.（1）求公式(pq) (qp)的主合取范式。解：(pq) (qp) (pq) (pq) (pq) pq M2.（2）求公式(p(pq) r的主析取范式。解：(p(pq) r p (pq) r (ppq r) 1m0m1m2m3m4m5m6m7.2、應(yīng)用分析（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共3分）（0）某村選村委，已知趙煉玉、錢谷王、孫竹灣被選進(jìn)了村委，三村民甲、乙、丙預(yù)言： 甲預(yù)言：趙煉玉為村長，錢谷王為村支書。 乙預(yù)言：孫竹灣為村長，趙煉玉為村支書。 丙預(yù)言：錢谷王為村

5、長，趙煉玉為村婦女主任。村委分工公布后發(fā)現(xiàn)，甲乙丙三人各預(yù)測正確一半。趙煉玉、錢谷王、孫竹灣各擔(dān)任什么職務(wù)？解：設(shè)P1：趙煉玉為村長，p2：錢谷王為村長，p3：孫竹灣為村長，q1：趙煉玉為村支書，q2: 錢谷王為村支書，r1：趙煉玉為村婦女主任。判斷公式F( (p1q2) (p1q2) ( (p3q1) (p3q1) ( (p2r1) (p2r1) p1q2p3q1q2r11q2p3r1，由此，錢谷王為村支書，孫竹灣為村長，趙煉玉為村婦女主任。說明：p1、p2、p3有且僅有一個為真，q1、q2有且僅有一個為真。一個人不能擔(dān)任兩職，一個職務(wù)不可由兩人同時擔(dān)任。（1）某公司派趙、錢、孫、李、周五人

6、出國學(xué)習(xí)。選派條件是： 若趙去，錢也去。 李、周兩人必有一人去。 錢、孫兩人去且僅去一人。 孫、李兩人同去或同不去。 如周去，則趙、錢也同去。如何選派他們出國？解： 設(shè)p：派趙去，q：派錢去，r：派孫去，s：派李去，u：派周去。 (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)構(gòu)成的合取式為：A= (pq)(su)(qr)(qr) (rs)(rs)(u(pq) (pqrsu)(pqrsu)由此可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去），或派趙、錢、周去（孫、李不去）。三、命題邏輯推理（

7、5分）在自然推理系統(tǒng)中，構(gòu)造下列推理過程（總共3題，完成的題號為學(xué)號尾數(shù)取3的余，完成1題。共5分）（0）如果張老師出國，則若李老師出國，王老師出國?，F(xiàn)在的情況是張老師與李老師都要出國。所以，王老師不出國，則孫老師出國。解：形式化：p：張老師出國；q：李老師出國；r：王老師出國；s：孫老師出國。前提：p(qr)，pq結(jié)論：rs證明： p(qr) 【前提引入】 p (qr) pqr 【置換】 pq 【前提引入】 r 【假言推理】 r s 【附加規(guī)則】 rs 【置換】 rs 【置換】 證畢。（1）若張同學(xué)與李同學(xué)是樂山人，則王同學(xué)是雅安人，若王同學(xué)是雅安人，則他喜歡吃雅魚，然而，王同學(xué)不喜歡吃雅魚

8、，張同學(xué)是樂山人。所以，李同學(xué)不是樂山人。解：形式化：p：張同學(xué)是樂山人；q：李同學(xué)是樂山人；r：王同學(xué)是雅安人；s：王同學(xué)喜歡吃雅魚。前提：(pq) r，r s，s，p結(jié)論：q證明： (pq) r 【前提引入】 r s 【前提引入】 (pq) s 【假言三段論】 s 【前提引入】 (pq) 【拒取式】 pq 【置換】 p 【前提引入】 q 【析取三段論】 證畢。（2）若n是偶數(shù)并且大于5，則m是奇數(shù)。只有n是偶數(shù)，m才大于6?，F(xiàn)有n大于5。所以，若m大于6，則m是奇數(shù)。解：形式化：p：n是偶數(shù)；q：n大于5；r：m是奇數(shù)；s：m大于6。前提：(pq) r，s p，q結(jié)論：s r證明： q 【

9、前提引入】 sq 【附加規(guī)則】（這是證明的關(guān)鍵） s q 【置換】 s p 【前提引入】 (s q）q（s p） 【合取】 s(pq ) 【置換】 (pq) r 【前提引入】 sr 【假言三段論】 證畢。四、一階邏輯的基本概念（5分）1、一階邏輯命題形式化（總共6題，完成的題號為學(xué)號尾數(shù)取6的余，完成1題。共2分）（0）人人都生活在地球上。解：x(F(x) G(x)，其中，F(xiàn)(x)：x是人，G(x)：x生活在地球上。（1）有的人長著金色的頭發(fā)。解：$x (F(x) G(x)，其中，F(xiàn)(x)：x是人，G(x)：x長著金色的頭發(fā)。（2）沒有能表示成分?jǐn)?shù)的無理數(shù)。解：$x (F(x) G(x)，其中

10、，F(xiàn)(x)：x是無理數(shù)，G(x)：x能表示成分?jǐn)?shù)。（3）說所有的男人比所有的女人力氣大是不正確的。解：xy (F(x) G(y)S(x,y)，其中，F(xiàn)(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力氣大。（4）有的學(xué)生不住在校內(nèi)。解：$x (F(x) G(x)，其中，F(xiàn)(x)：x是學(xué)生，G(x)：x住在校內(nèi)。（5）說有的男人比所有的女人力氣大是正確的。解：$x (F(x) y(G(x)S(x,y)，其中，F(xiàn)(x)：x是男人，G(x)：x是女人，S(x,y)：x比y力氣大。2、給出下列公式的一個成真解釋和一個成假解釋（總共3題，完成的題號為學(xué)號尾數(shù)取3的余，完成1題。共3分）（0）x

11、(F(x) G(x)解：取解釋I1：個體域?yàn)槿说募?，F(xiàn)(x)：x是男人，G(x)：x是女人。則在I1解釋下，x(F(x) G(x)為真命題。取解釋I2：個體域?yàn)槿说募?，F(xiàn)(x)：x是中國人，G(x)：x是美國人。則在I2解釋下，x(F(x) G(x)為假命題。（1）$x(F(x) G(x) H(x)解：取解釋I1：個體域?yàn)槿说募?，F(xiàn)(x)：x是教師，G(x)：x是黨員，H(x)：x是班主任。則在I1解釋下，$x(F(x) G(x) H(x)為真命題。取解釋I2：個體域?yàn)槿说募希現(xiàn)(x)：x是男人，G(x)：x是女人，H(x)：x是班主任。則在I2解釋下，$x(F(x) G(x) H(x

12、)為假命題。（2）$x(F(x) y( G(y) H(x,y)解：取解釋I1：個體域?yàn)檎麛?shù)集合，F(xiàn)(x)：x是正整數(shù)，G(x)：x是負(fù)整數(shù)，H(x,y)：x比y大。則在I1解釋下，$x(F(x) y( G(y) H(x,y)為真命題。取解釋I2：個體域?yàn)樽匀粩?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分）（0）證明等值式：x(A(x)B) $xA(x)B。證明：x(A(x)B) x(A(x) B) x

13、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題，完成的題號為學(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)（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)

14、 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題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共2分）（0）舉例說明“對無分配律”。解：對無分配律指：不存在等價關(guān)系x(A(x) B(x)xA(x) xB(x)。例如，取解釋I：個體域?yàn)槿说募?，F(xiàn)(x)：x是男人，G(x)：x是女人。

15、x(A(x) B(x)的真值為真，而xA(x) xB(x)的真值為假。（1）舉例說明“$對無分配律”。解：$對無分配律指：不存在等價關(guān)系$x(A(x) B(x) $x A(x)$x B(x)。例如，取解釋I：個體域?yàn)槿说募?，F(xiàn)(x)：x是男人，G(x)：x是女人。$x (A(x) B(x)的真值為假，而$x A(x) $x B(x)的真值為真。六、一階邏輯推理（5分）在自然推理系統(tǒng)中，構(gòu)造下列推理過程（總共2題，完成的題號為學(xué)號尾數(shù)取2的余，完成1題。共5分）（0）每個喜歡步行的人都不喜歡騎自行車，每個人或者喜歡騎自行車或者喜歡乘汽車，有的人不喜歡乘汽車。所以，有的人不喜歡步行。（個體域?yàn)槿?/p>

16、類集合）解：形式化：F(x)：x喜歡步行；G(x)：x喜歡騎自行車；H(x)：x喜歡乘汽車。前提：x(F(x) G(x)，x(G(x) H(x)，$xH(x)結(jié)論：$xF(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) 【 $+ 】 $xH(x) $x F (x) 【 $+ 】 $xH(x) 【前提引入】 $x F (x) 【假言推理】 證畢。（1）每個科學(xué)工作者都是刻苦鉆研的，每個刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且聰明。所以，王大海在他的事業(yè)中將獲得成功。（個體域?yàn)槿祟惣希┙猓盒问交篎