第一篇：數理邏輯考試題及答案

“離散數學”數理邏輯部分考核試題答案

━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━

一、命題邏輯基本知識（5分）

1、將下列命題符號化（總共4題，完成的題號為學號尾數取4的余，完成1題。共2分）（0）小劉既不怕吃苦，又愛鉆研。

解：?p∧q，其中，P：小劉怕吃苦；q：小劉愛鉆研。（1）只有不怕敵人，才能戰勝敵人。

解：q→?p，其中，P：怕敵人；q：戰勝敵人。

（2）只要別人有困難，老張就幫助別人，除非困難已經解決了。

解：?r→(p→p)，其中，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→((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.（1）求公式?(?(p→q))∨(?q→?p)的主合取范式。

解：?(?(p→q))?(?q→?p)?

(p→q)?(p→q)?(p→q)? ?p?q ? M2.

（2）求公式(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、應用分析（總共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

【④附加規則】 ⑥ ? ? r∨s

【⑤置換】

⑦ ?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)→B

2、給出下列公式的前束范式（總共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)

【⑦⑧假言推理】

證畢。

第二篇：數理邏輯練習題及答案-3

命題邏輯的推理

1． 判斷下面推理是否正確。先將簡單命題符號化，再寫出前提、結論、推理的形式結構（以蘊涵式的形式給出）和判斷過程（至少給出兩種判斷方法）：

（1）若今天是星期一，則明天是星期三；今天是星期一。所以明天是星期三。

（2）若今天是星期一，則明天是星期二；明天是星期二。所以今天是星期一。

（3）若今天是星期一，則明天是星期三；明天不是星期三。所以今天不是星期一。

（4）若今天是星期一，則明天是星期二；今天不是星期一。所以明天不是星期二。

（5）若今天是星期一，則明天是星期二或星期三。

（6）今天是星期一當且僅當明天是星期三；今天不是星期一。所以明天不是星期三。

2． 構造下面推理的證明：

（1）前提：p→(q→r), p, q

結論：r∨s

（2）前提：p→q, ┐(q∧r), r 結論：┐p

（3）前提：p→q

結論：p→(p∧q)

（4）前提：q→p, qs, st, t∧r 結論：p∧q

（5）前提：p→r, q→s, p∧q 結論：r∧s

（6）前提：┐p∨r, ┐q∨s, p∧q 結論：t→(r∨s)

3． 用附加前提法證明下面各推理：

（1）前提：p→(q→r), s→p, q

結論：s→r

（2）前提：(p∨q)→(r∧s),(s∨t)→u

結論：p→u

4． 用歸謬法證明下面推理：

（1）前提：p→┐q, ┐r∨q, r∧┐s

結論：┐p

（2）前提：p∨q, p→r, q→s

結論：r∨s

5． 構造下面推理的證明。

（1）如果小王是理科學生，他必學好數學；如果小王不是文科生，他必是理科生；小王沒學好數學。所以，小王是文科生。

（2）明天是晴天，或是雨天；若明天是晴天，我就去看電影；若我看電影，我就不看書。所以，如果我看書，則明天是雨天。答案

1．設p：今天是星期一，q：明天是星期二，r：明天是星期三。

（1）推理的形式結構為

(p→r)∧p→r

此形式結構為重言式，即

(p→r)∧pr 所以推理正確。

（2）推理的形式結構為

(p→q)∧q→p

此形式結構不是重言式，故推理不正確。

（3）推理形式結構為

(p→r)∧┐r→┐p

此形式結構為重言式，即

(p→r)∧┐r┐p

故推理正確。

（4）推理形式結構為

(p→q)∧┐p→┐q

此形式結構不是重言式，故推理不正確。

（5）推理形式結構為

p→(q∨r)它不是重言式，故推理不正確。

（6）推理形式結構為(pr)∧┐p→┐r

此形式結構為重言式，即(pr)∧┐p┐r

故推理正確。

推理是否正確，可用多種方法證明。證明的方法有真值表法、等式演算法。證明推理正確還可用構造證明法。

下面用構造證明法證明（6）推理正確。

前提: pr, ┐p

結論: ┐r

證明: ① pr 前提引入

②(p→r)∧(r→p)①置換

③ r→p ②化簡律

④ ┐p 前提引入 ⑤ ┐r ③④拒取式

所以，推理正確。2．

（1）證明：

①p→(q→r)②p ③q→r ④q ⑤r ⑥r∨s

前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 ⑤附加律

（2）證明：

①┐(q∧r)②┐q∨┐r ③r ④┐q ⑤p→q ⑥┐p

前提引入 ①置換 前提引入 ②③析取三段論 前提引入 ④⑤拒取式

（3）證明：

①p→q ②┐p∨q

③(┐p∨q)∧(┐p∨p)④┐p∨(p∧q)⑤p→(p∧q)

前提引入 ①置換 ②置換 ③置換 ④置換

也可以用附加前提證明法，更簡單些。

（4）證明：

①st 前提引入 ①置換 ②化簡 ②(s→t)∧(t→s)③t→s

④t∧r ⑤t ⑥s ⑦qs ⑧(s→q)∧(q→s)⑨s→q ⑩q q→p p p∧q

前提引入 ④化簡 ③⑤假言推理 前提引入 ⑦置換 ⑧化簡 ⑥⑨假言推理 前提引入 ⑩⑩

假言推理 合取

（5）證明：

①p→r ②q→s ③p∧q ④p ⑤q ⑥r ⑦s ⑧r∧s

前提引入 前提引入 前提引入 ③化簡 ③化簡 ①④假言推理 ②⑤假言推理 ⑥⑦合取

（6）證明：

①t ②┐p∨r ③p∧q ④p ⑤r ⑥r∨s

附加前提引入 前提引入 前提引入 ③化簡

②④析取三段論 ⑤附加

說明：證明中，附加提前t，前提┐q∨s沒用上。這仍是正確的推理。

3．（1）證明：

①s 附加前提引入

②s→p ③p ④p→(q→r)⑤q→r ⑥q ⑦r

前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理

（2）證明：

①p ②p∨q

附加前提引入 ①附加

③(p∨q)→(r∧s)前提引入 ④r∧s ⑤s ⑥s∨t ⑦(s∨t)→u ⑧u

②③假言推理 ④化簡 ⑤附加 前提引入 ⑥⑦假言推理

4．（1）證明：

①p ②p→┐q ③┐q ④┐r∨q ⑤┐r ⑥r∧┐s ⑦r ⑧┐r∧r

結論否定引入 前提引入 ①②假言推理 前提引入 ③④析取三段論 前提引入 ⑥化簡 ⑤⑦合取

⑧為矛盾式，由歸謬法可知，推理正確。

（2）證明：

①┐(r∨s)②p∨q ③p→r ④q→s ⑤r∨s

⑥┐(r∨s)∧(r∨s)

結論否定引入 前提引入 前提引入 前提引入 ②③④構造性二難 ①⑤合取

⑥為矛盾式，所以推理正確。

5．（1）

令p：小王是理科生，q：小王是文科生，r：小王學好數學。

前提：p→r, ┐q→p, ┐r

結論：q 證明：

①p→r ②┐r ③┐p ④┐q→p ⑤q

前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式

（2）

令p：明天是晴天，q：明天是雨天，r：我看電影，s：我看書。

前提： p∨q, p→r, r→┐s

結論： s→q

證明：

①s ②r→┐s ③┐r ④p→r ⑤┐p ⑥p∨q ⑦q

附加前提引入 前提引入 ①②拒取式 前提引入 ③④拒取式 前提引入 ⑤⑥析取三段論

第三篇：數理邏輯心得

數理邏輯的心得

數理邏輯：是計算機科學的基礎，應熟練掌握將現實生活中的條件化成邏輯公式，并能做適當的推理，這對程序設計等課程是極有用處的。是大四接觸到的，現簡單介紹一下數理邏輯的發展史，算是一點感悟吧

1數理邏輯的發展前期

·前史時期——古典形式邏輯時期：亞里斯多德的直言三段論理論·初創時期——邏輯代數時期（17世紀末）

·資本主義生產力大發展，自然科學取得了長足的進步，數學在認識自然、發展技術方面起到了相當重要的作用。

·人們希望使用數學的方法來研究思維，把思維過程轉換為數學的計算。·萊布尼茲(Leibniz, 1646~1716)完善三段論，提出了建立數理邏輯或者說理性演算的思想：

·提出將推理的正確性化歸于計算，這種演算能使人們的推理不依賴于對推理過程中的命題的含義內容的思考，將推理的規則變為演算的規則。

·使用一種符號語言來代替自然語言對演算進行描述，將符號的形式和其含義分開。使得演算從很大程度上取決與符號的組合規律，而與其含義無關。

·布爾(G.Boole, 1815~1864)代數：將有關數學運算的研究的代數系統推廣到邏輯領域，布爾代數既是一種代數系統，也是一種邏輯演算。

數理邏輯的奠基時期

·弗雷格(G.Frege, 1848~1925)：《概念語言——一種按算術的公式語言構成的純思維公式語言》(1879)的出版標志著數理邏輯的基礎部分——命題演算和謂詞演算的正式建立。

·皮亞諾(Giuseppe Peano, 1858~1932)：《用一種新的方法陳述的算術原理》(1889)提出了自然數算術的一個公理系統。

·羅素(Bertrand Russell, 1872~1970)：《數學原理》(與懷特黑合著，1910, 1912, 1913)從命題演算和謂詞演算開始，然后通過一元和二元命題函項定義了類和關系的概念，建立了抽象的類演算和關系演算。由此出發，在類型論的基礎上用連續定義和證明的方式引出了數學（主要是算術）中的主要概念和定理。

·邏輯演算的發展：甘岑(G.Gentzen)的自然推理系統(Natural Deduction System)，邏輯演算的元理論：公理的獨立性、一致性、完全性等。

·各種各樣的非經典邏輯的發展：路易斯(Lewis, 1883~1964)的模態邏輯，實質蘊涵怪論和嚴格蘊涵、相干邏輯等，盧卡西維茨的多值邏輯等。

集合論的悖論使得人們覺得數學產生了第三次危機，提出了數學的基礎到底是什么這樣的問題。

·羅素等的邏輯主義：數學的基礎是邏輯，倡導一切數學可從邏輯符號推出，《數學原理》一書是他們這一思想的體現。為解決悖論產生了邏輯類型論。

·布勞維爾(Brouwer, 1881~1966)的直覺主義：數學是心靈的構造，只承認可構造的數學，強調構造的能行性，與計算機科學有重要的聯系。堅持潛無窮，強調排中律不能用于無窮集合。海丁(Heyting)的直覺主義邏輯。

·希爾伯特(D.Hilbert)的形式主義：公理化方法與形式化方法，元數學和證明論，提倡將邏輯演算和數學證明本身形式化，把用普通的語言傳達的內容上的數學科學變為用數學符號和邏輯符號按一定法則排列的一堆公式。為了消除悖論，要數學建立在公理化基礎上，將

各門數學形式化，構成形式系統，并證明其一致性，這是希爾伯特的數學綱領。

·哥德爾(Godel, 1906~1978)不完全性定理：一個足夠強大的形式系統，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。·各種計算模型：哥德爾的遞歸函數理論，邱吉爾的?演算，圖靈機模型

·這些計算模型是計算機科學的理論基礎，是計算機的理論模型。

第四篇：數理邏輯智能

數理邏輯智能

人們一直把數理邏輯智能看成是智能的核心，學者們也認為這種智能是人類認知能力的重要部分。有關數理邏輯智能，大多數人都認為數理邏輯智能就是一種加減乘除的能力。這是一種計算的能力，但是，數理邏輯智能所包含的遠遠不止這些。數理邏輯智能包括：事物分類、復雜問題簡單化、計算、假設和證明等具體操作能力；邏輯類型、邏輯關系、陳述句和命題、函數等抽象思維能力。數理邏輯智能是所有科目和學習的基礎，它和語言智能一起組成了學業型智能，在學校里受到絕對的重視。在學校里，數理邏輯智能高的孩子學習成績通常都很好。人們也都大都喜歡這些孩子。他們的領悟能力特別強，凡事一點就通。教給他們從1數到10，他們就能獨自摸索數到99，然后教給他們數100，他們就可以一直地數下去。有時我們會聽到人家說：“這孩子挺聰明的，就是不好好學，要不然成績早就上去了。”其實這樣的孩子也可以說是數理邏輯智能高的孩子，相比“有點笨，但是很用功”的孩子，這類孩子未來的成功幾率會更高。因為他們只要稍微用功學習，成績就能大幅度提高。當別的孩子都花很多時間背公式的時候，邏輯智能高的孩子不會死記硬背，他們會在理解原理的基礎上，熟練地運用公式，就算遇到難題也能通過舉一反

三、自我摸索找出答案。

現在很多家長都頭疼孩子不會寫作文，一篇文章能在哪兒寫上半天的工夫。然后拿過來一看，這句子讀著這個別扭，還哪都不挨哪。家長們也許都覺得這是孩子語文沒有學好的原因。家長們的想法是對的，但這不是根本的。孩子們不會寫作文，究其原因兩條：缺乏切身的體驗；數理邏輯智能差。這家長說了，你這第一條我還能接受，可是這寫作文跟數理邏輯有什么關系啊！當然有，而且關系還是深層次的。孩子的作文寫不好，一是沒有素材，二是不會組織語言。不會組織語言、說話毫無邏輯、顛三倒四，正是孩子邏輯能力差的一個表現。孩子在描述一個物體或一件事情的時候，不知該如何去說，不知道先說什么，后說什么。抓不著重點。而對于邏輯能力強的孩子來說，他在寫作文或說話之前，會先想好了這個話應該怎么說，要完成一個作文題目，需要具備哪些內容，每一段內容又該怎么安排。所以說數理邏輯智能高的孩子不僅僅在理科科目上成績很好，在文科科目上也很優秀。

數理邏輯智能高的人解決邏輯性問題比普通人要快得多，而且由于善于推理，往往會采用科學的方法來解決具體問題。比如我們出去逛街，買東西的時候突然發現錢包不見了。一般人呢可能就慌了，“哎呀，我錢包哪去了啊？剛才買東西的時候還在呢！”然后急的大腦一片空白什么也想不起來。但是數理邏輯智能高的人，當他意識到錢包丟了的時候，他首先會把需要掛失的卡之類的東西先做掛失，把損失減到最低。然后他就開始回想：我剛剛去了哪幾個地方，在這幾個地方我都干了些什么，在哪個地方我最有可能把錢包給丟了。然后依次回去找。體現了他們比普通人更有理性。不但如此，他們對數字也很敏感，很快就能記住電話號碼。

此外，數理邏輯智能高的孩子做事相當有條理，不僅在學習上，在日常生活中，他們的條理性也表現得非常突出。我朋友的小孩，就是數理邏輯智能高的孩子。他今年上小學三年級，早上從來不需要大人叫他起床。他自己有個時間表，早上6:40—6:50起床，穿衣服；6:50—7:10洗漱，上廁所；7:10—7:20吃早飯，然后出門上學。晚上放學回來，作業先寫什么，后寫什么，也都不用他們家大人操心，很快就能做完，而且質量很高。他的衣櫥里的衣服擺的很整齊，書架上的書也是分類放的，玩具全部放在一個箱子里，整個屋子特別干凈，根本不像是小男孩的臥室。

第五篇：數理邏輯的大發展

數理邏輯的大發展

1930年以后，數學邏輯開始成為一個專門學科，得到了蓬勃發展。哥德爾的兩個定理證明之后，希爾伯特的有限主義綱領行不通，證明論出現新的情況，主要有兩方面：通過放寬有限主義的限制來證明算術無矛盾性以及把證明形式化、標準化，這些主要是在三十年代完成。同時哥德爾引進遞歸函數，發展成遞歸論的新分支，開始研究判定問題。而哥德爾本人轉向公理集合論的研究，從此出現公理集合論的黃金時代。五十年代模型論應運而生，它與數學有著密切聯系，并逐步產生積極的作用。

1、證明論

證明論又稱元數學，它研究數學的最基本活動—證明的合理性問題。研究這類數學基礎的問題原來一直是哲學家的事，后來才成為數學家的事。這個轉變發生在1893年弗雷格發表《算術基礎規則》之時，后來希爾伯特和他的許多合作者使這種思想發展成一門學科—元數學，目的是用數學方法來研究整個數學理論。

要使數學理論成為一個合適的研究對象，就必須使之形式化。自從希爾伯特和阿克曼所著《理論邏輯綱要》第一版在1928年出版以來，在實踐中用得最多的是具有等式的一階謂詞演算(以及高階謂詞演算)。許多理論可以用一階理論來表述，它比較簡單方便，具有多種形式。

從基礎的觀點來看，有兩個理論最為重要，因而研究也最多。這兩個理論就是形式化的皮亞諾算術理論與形式化的集合論。因為大多數觀代數學理論都可以在這兩個理論范圍內發展，所以這兩個理論的合理性如果得到證實，也就是向數學的可靠性邁進了一大步。“希爾伯特計劃”無非就是要找到一個有限的證明步驟來證明算術的無矛盾性。

這里“有限”的意義是由法國年輕數學家厄布朗明確提出的，他認為下列條件必須滿足：必須只討論確定的有限數目的對象及函數；這些對象及函數要能確定它們的真值產生協調一致的計算結果；一個對象如不指出如何構造它就不能肯定其存在；必須永遠不考慮一個無窮集體中所有對象的集合；一個定理對于一組對象都成立的意思是，對于每個特殊的對象，可以重復所講的普遍論證，而這普遍論證只能看成是結果特殊論證的原型。

數學理論的無矛盾性有了這種有限的、可構造性的論證之后，任何人都可以放心了。希爾伯特計劃提出后，幾組數學家分別為實現它而努力：一組是希爾伯特及貝耐斯，以及阿克曼關于把數學理論形式化的研究，一組是馮·諾依曼關于算術無矛盾性的初步研究及哥德爾的不完全性定理以及甘岑的最后解決；還有一組是厄布朗及甘岑關于證明的標準形式等的研究。

厄布朗是法國天才的青年數學家，1931年8月在登阿爾卑斯山時遇難，年僅23歲。他對代數數論尤其是數理邏輯進行過重要的研究工作，1929年他在博士論文《證明論研究》中提出他的基本定理。從某種意義上來講，這個定理是想把謂詞演算歸結為命題演算。由于前一理論是不可判定的，而后一理論是可判定的，因此這種歸結不可能是完全的。

但是，由于厄布朗局限于希爾伯特有限主義立場，他應用的證明方法比較繞彎子。而且在1963年發現，他的證明中有漏洞，他的錯誤很快就得到了彌補。厄布朗定理可以便我們在證明中擺脫三段論法。他的許多結果，后來也為甘岑獨立地得出。

甘岑的自然演繹系統是把數學中的證明加以形式化的結果。他由此得出所謂“主定理”，即任何純粹邏輯的證明，都可以表示成為某種正規形式，雖然正規形式不一定是唯一的。為了證明這個主定理，他又引進了所謂的式列(Sequenz)演算。

在普通的數學證明中，最常用則是三段論法，即如果A→B，且若A成立，則B成立。其實這就是甘岑推論圖中的“斷”。但是甘岑的主定理就是從任何證明圖中可以消除掉所有的“斷”。也就是：如果在一個證明中用到三段論法，那么定理表明，它也可以化成為不用三段論法的證明，也得到同樣的結論。

這個定理乍一看來似乎不可理解，其實正如甘岑所說，一個證明圖中有三段論法實際上是“繞了彎子”，而不用三段論法是走直路。這種沒有三段論法的證明圖稱為“正規形式”，利用這沒有三段論法的證明圖稱為“正規形式”。利用這個主定理很容易得出許多重要結果，其中之一就是極為簡單地證明“一階謂詞演算是無矛盾的”，而且能夠推出許多無矛盾性的結果。后來還可以用來證明哥德爾的完全性及不完全性定理，當然，最重要的事還是要證明算術的無矛盾性。

希爾伯特引進證明論的目標是證明整個數學的無矛盾性，其中最重要的是集合論的無矛盾性(至少ZF系統無矛盾)、數學分析的無矛盾性，最基本的當然是算術的無矛盾性。哥德爾的不完全性定理說明，用有限的辦法這個目標是達不到的。由于哥德爾不完全定理的沖擊，希爾伯特計劃需要修改。

有限主義行不通就要用非有限的超窮步驟。1935年，甘岑用超窮歸納法證明自然數算術形式系統的無矛盾性。其后幾年，他和其他人又給出了其他的證明。這種放寬了的希爾伯特計劃在第二次世界大戰之后發展成為證明論的分支，這些證明也推廣到分支類型論及其他理論。

甘岑在第二次大戰行將結束時去世，他的結果代表當時證明論的最高成就，希爾伯特和貝納斯的《數學基礎》第二卷中總結了他的工作，但是證明論遠遠未能完成它的最初目標。戰后隨著模型論和遞歸論乃至六十年代以來公理集合論的發展，證明論一直進展不大。

五十年代中，日本數學家竹內外史等人開始對于實數理論(或數學分析)的無矛盾性進行探索。因為實數一開始就同有理數的無窮集和有關，描述它的語言用一階謂詞演算就不夠了，所以第一步就要先把甘岑的工作推廣到高階謂詞演算中去。

1967年，日本年輕數學家高橋元男用非構造的方法證明，單純類型論中也可以消去三段論法。由此可以推出數學分析子系統的無矛盾性。但是，由于證明不是構造的，數學分析的無矛盾性至今仍然有待解決。

厄布朗及甘岑的結果雖然不可能完成希爾伯特計劃的最初目標，但是由于其有限性、可構造性的特點，現在已廣泛地應用于機械化證明，成為這門學科的理論基礎。

證明論的方法對于數理邏輯本身有很大的推動，特別是得出新的不可判定命題。最近，英國年輕數學家巴黎斯等人有了一項驚人的發現。他們發現了一個在皮亞諾算術中既不能證明也不能否證的純粹組合問題，這不僅給哥德爾不完全性定理一個具體的實例，而且使人懷疑要解決許多至今尚未解決的數論難題可能都是白費力氣。這無疑開辟了證明論一個完全新的方向。

2、遞歸論

遞歸論討論的是從形式上刻劃一個運算或一個進程的“能行”性這種直觀的觀念，也就是從原則上講，它們能機械地進行而產生一個確定的結果。“能行”的這個概念含有可具體實現的、有效的、有實效的等等意思。法國數學家保萊爾首先在1898年他的函數論教科書中引進了這個詞，他把數學的對象局限于能行的對象，這種主張實際上就是“法國經驗主義”。因為函數論主要討論集合、函數、積分等等，從這種觀點產生出描述集合論、拜爾函數等概念。

遞歸論中所討論的函數是比較簡單的。它討論有效可計算的函數，也就是遞歸函數。遞歸函數在歷史上曾從不同角度提出來，后來證明它們都是等價的。

1931年秋天，丘奇在普林斯頓開了一門邏輯課，克林和羅塞爾當時作為學生記了筆記。丘奇在講課中引進了他的系統，并且在其中定義自然數。這就很自然引起一個問題，在丘奇系統中如何發展一個自然數理論。于是克林開始進行研究，結果克林和丘奇得到一類可計算的函數，他們稱之為A可定義函數。

1934年春天，哥德爾在普林斯頓做了一系列講演(克林和羅塞爾記了筆記)。在講演中，哥德爾引進了另外一套可以精確定義的可計算函數類，他稱為一般遞歸函數。據他講，他是受了厄布朗的啟發得到的。

這時自然出現了一個問題。一般遞歸函數類是否包括所有能行可計算的函數，它是否與克林與丘奇研究的A可定義函數類重合。1934年春末，丘奇和哥德爾討論一般遞歸函數問題，結果丘奇明確提出他的“論點”，所有直覺上可看成能行可計算函數都是λ可定義函數，于是丘奇花了好幾個月反復思考。當時克林表示懷疑，他認為這論點不太可能是對的，他想如果從A可定義函數類用對

角化方法可以得出另外一個能行可計算函數，那么它就不是A可定義的。但他又想到這事行不通。不久之后，丘奇和克林在1936年分別發表論文，證明A可定義函數類正好就是一般遞歸函數類。有了這個有力的證據，丘奇于是公開發表他的“論點”。

也是在1936年，英國年輕數學家圖林發表了另外一篇重要文章，這標志著所謂圖林機的產生。在這篇文章中，圖林也定義了一類可計算函數，也就是用圖林機可以計算的函數。同時，他也提出他的一個論點：“能行可計算的函數”與“用圖林機可計算的函數”是一回事。1937年圖林證明了用圖林機可計算的函數類與可定義函數類是一致的，當然，也就和一般遞歸函數類相重合。這樣一來，丘奇的論點與圖林的論點就是一回事。當時許多人對于丘奇的論點表示懷疑，由于圖林的思想表述得如此清楚，從而消除了許多人的疑慮，哥德爾就是其中一位。從這時起大家對于丘奇—圖林論點一般都抱支持的態度了。

與圖林同時，美國數學家波斯特也發表了一篇文章，類似于圖林的可計算函數，他的文章過于簡短，一直到1943年波斯特才發表了第四個表述，結果證明他的與別人的也都一樣。

遞歸的概念并不難理解，它就是由前面的結果可以遞推得到后面的結果。哥德爾等人引進的實際上是一般遞歸函數，一股遞歸函數都可以由原始遞歸函數算出來。

另一個復雜一些的概念稱為遞歸集合S，它的定義是存在一種能行的辦法來判斷任何正整數n是否屬于S。正數數集合是遞歸的當且僅當它與它在N中的補集都是遞歸可枚舉的。任何無窮遞歸可枚舉集都包含一個無窮遞歸集。但是，存在正整數的遞歸可枚舉集而不是遞歸集。

于是波斯特提出問題：是否存在兩個遞歸可按舉但是非遞歸的集合，使得第一個集合相對于第二個是遞歸的，但第二個相對于第一個卻不是遞歸的。一直到十二年后的1956年，蘇聯人穆其尼克及美國人弗里德伯格才獨立地肯定地解決了這個問題。

蘇聯數學家馬爾科夫在1947年發表《算法論》，首先明確提出算法的概念。但是它同以前定義的遞歸函數及可計算函數的計算過程都是等價的。這幾個定義表面上很不相同，并有著十分不同的邏輯出發點，卻全都證明是等價的。這件事看來決非巧合。它表明：所有這些定義都是同一個概念，而且這個概念是自然的、基本的、有用的。這就是“算法”概念的精確的數學定義。大家都接受了這個定義之后，判定問題從我們平時直觀的概念也上升為精確的數學概念，判定問題也成為一門數理邏輯的重要分支了。從這時起，判定問題有突飛猛進的發展。

判定問題有了精確的數學表述之后，立即在數學基礎乃至整個數學中產生了巨大的影響。因為這時一些不可判定命題的出現，標志著人們在數學歷史上第一次認識到：有一些問題是不可能找到算法解的。在過去，人們一直模模糊糊地覺

得，任何一個精確表述的數學問題總可以通過有限步驟來判定它是對還是錯，是有解還是沒有解。找到不可判定問題再一次說明用有限過程對付無窮的局限性，它從另外一個角度反映了數學的內在固有矛盾。

怎樣得到這些結果的呢？丘奇的論點發表之后，不難看出存在不可計算的函數，也就是非一般遞歸的函數。因為所有可能不同的算法共有可數無窮多(粗淺來講，算法都是用有限多個字來描述的)，可是所有數論函數的集合卻是不可數的。

不過，頭一個明顯的不可判定的結果是1936年丘奇得到的。他首先得到與λ可定義性有關的不可判定結果。然后，他把這個結果應用到形式系統的判定問題上，特別他證明，形式化的一階數論N是不可判定的。也是在1936年，丘奇證明純粹的謂詞演算也是不可判定的。當時大家的反應是：這種不完全性的范圍到底有多廣？

甚至于象丘奇這樣的數學家，也想找到一條出路能避開哥德爾的結果。比如說，可以采用伺哥德爾所用的系統完全不同的其他的特殊系統。一旦算法的精確定義和丘奇論點出現之后，大家就認識到躲不過哥德爾不完全性定理的影響，可計算性和不完全性這兩個概念是緊密聯系在一起的。

實際上克林在1936年就證明了(作為丘奇論點的應用)：甚至在能夠能行地認出公理和證明的形式系統中，哥德爾的定理仍然成立。消去量詞方法對許多理論行不通。一般的判定問題是試圖找出一個能行的步驟，通過這個步驟可以決定什么東西具有某種指定的元數學特征。

在純粹邏輯演算的元理論中，有最明顯的一類判定問題：對于給定的演算和給定類的公式，求出一個步驟，能夠在有限多步內判定這類的任何特殊公式是否可以形式地推導出來。有些情形、問題已經得到肯定的解決，在另外一些情形，答案是否定的，可以證明不存在這樣一個步驟。這種否定的證明，特別對于數學理論，很大程度上依賴于遞歸論。

最早明確提出的數學判定問題是希爾伯特第十問題。他在1900年國際數學家大會上提出了著名的二十三個問題，其中第十個問題是：給定一個有任意多未知數的、系數為有理整數的丟番圖方程，設計一個步驟，通過它可以經有限步運算判定該方程是否有有理整數解。這個到1970年才被否定解決的問題不僅解決了一個重大問題，而且解決問題過程中所得到的工具和結果對數理邏輯和數學發展有著極大影響，比如表示素數的多項式，尤其與整個數理邏輯有關的是得出了一個更確切的哥德爾不完全性定理。

現在我們來看希爾伯特第十問題，為了清楚起見，我們考慮多項式方程，看看一般的多項式丟番圖方程的次數和未定元的數目是否可以降低。

1938年斯科蘭姆證明，任何丟番圖方程的次數可約化成次數小于等于4的方程；1974年馬蒂亞謝維奇和羅濱遜證明未定元的數目可約化成小于等于3。對

于齊次方程，阿德勒在1971年證明，任何齊次方程可以能行地約化為二次齊次方程組，從而等價于一個四次齊次方程。對于一次方程早就有具體方法解丟番圖方程了。對于任意多未定元的二次方程，1972年西格爾也找到一個算法。四次方程不能判定，三次方程尚不知道。

解決丟番圖方程解是否存在的判定問題的方法是引進丟番圖集。我們把丟番圖方程的變元分成兩有一組解。每個丟番圖集合是遞歸可枚舉集。1970年，蘇聯大學生馬蒂亞謝維奇證明了每個遞歸可枚舉集也是丟番圖集合。這樣一來，由于存在不可判定的遞歸可枚舉集，所以存在一些特殊的丟番圖方程，使得對是否有解的判定問題不可解。當然對一般丟番圖方程的判定問題就更不可解了。

另一個判定問題是半群和群論中字的問題，半解問題是挪威數學家圖埃在1907年首先提出來的。問題是對于一個半群，如果給定它的有限多生成元和有限多關系，那么能否找到一個方法來判定任何一個特殊的字是否等于單位元素。1947年，波斯特否定地解決了這個問題。

群論中字的問題更為重要，它是在1911年由德恩首先研究的，一直到1955年才由蘇聯數學家諾維科夫否定解決。這些結果給數學家指明了新的方向：不要妄圖去解決一大類問題。不過對于更窄的一類的對象比如一類特殊的群，群的字問題是可解的。