数理逻辑 的 证明题

千文网小编为你整理了多篇相关的《数理逻辑 的 证明题》，但愿对你工作学习有帮助，当然你在千文网还可以找到更多《数理逻辑 的 证明题》。

第一篇：数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题答案

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

一、命题逻辑基本知识（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)

【⑦⑧假言推理】

证毕。

第二篇：数理逻辑心得

数理逻辑的心得

数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧

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)不完全性定理：一个足够强大的形式系统，如果是一致的则不是完全的，即有的判断在其中是不可证的，既不能断定其为假，也不能证明其为真。·各种计算模型：哥德尔的递归函数理论，邱吉尔的演算，图灵机模型

·这些计算模型是计算机科学的理论基础，是计算机的理论模型。

第三篇：数理逻辑的大发展

数理逻辑的大发展

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年才由苏联数学家诺维科夫否定解决。这些结果给数学家指明了新的方向：不要妄图去解决一大类问题。不过对于更窄的一类的对象比如一类特殊的群，群的字问题是可解的。

第四篇：数理逻辑智能

数理逻辑智能

人们一直把数理逻辑智能看成是智能的核心，学者们也认为这种智能是人类认知能力的重要部分。有关数理逻辑智能，大多数人都认为数理逻辑智能就是一种加减乘除的能力。这是一种计算的能力，但是，数理逻辑智能所包含的远远不止这些。数理逻辑智能包括：事物分类、复杂问题简单化、计算、假设和证明等具体操作能力；逻辑类型、逻辑关系、陈述句和命题、函数等抽象思维能力。数理逻辑智能是所有科目和学习的基础，它和语言智能一起组成了学业型智能，在学校里受到绝对的重视。在学校里，数理逻辑智能高的孩子学习成绩通常都很好。人们也都大都喜欢这些孩子。他们的领悟能力特别强，凡事一点就通。教给他们从1数到10，他们就能独自摸索数到99，然后教给他们数100，他们就可以一直地数下去。有时我们会听到人家说：“这孩子挺聪明的，就是不好好学，要不然成绩早就上去了。”其实这样的孩子也可以说是数理逻辑智能高的孩子，相比“有点笨，但是很用功”的孩子，这类孩子未来的成功几率会更高。因为他们只要稍微用功学习，成绩就能大幅度提高。当别的孩子都花很多时间背公式的时候，逻辑智能高的孩子不会死记硬背，他们会在理解原理的基础上，熟练地运用公式，就算遇到难题也能通过举一反

三、自我摸索找出答案。

现在很多家长都头疼孩子不会写作文，一篇文章能在哪儿写上半天的工夫。然后拿过来一看，这句子读着这个别扭，还哪都不挨哪。家长们也许都觉得这是孩子语文没有学好的原因。家长们的想法是对的，但这不是根本的。孩子们不会写作文，究其原因两条：缺乏切身的体验；数理逻辑智能差。这家长说了，你这第一条我还能接受，可是这写作文跟数理逻辑有什么关系啊！当然有，而且关系还是深层次的。孩子的作文写不好，一是没有素材，二是不会组织语言。不会组织语言、说话毫无逻辑、颠三倒四，正是孩子逻辑能力差的一个表现。孩子在描述一个物体或一件事情的时候，不知该如何去说，不知道先说什么，后说什么。抓不着重点。而对于逻辑能力强的孩子来说，他在写作文或说话之前，会先想好了这个话应该怎么说，要完成一个作文题目，需要具备哪些内容，每一段内容又该怎么安排。所以说数理逻辑智能高的孩子不仅仅在理科科目上成绩很好，在文科科目上也很优秀。

数理逻辑智能高的人解决逻辑性问题比普通人要快得多，而且由于善于推理，往往会采用科学的方法来解决具体问题。比如我们出去逛街，买东西的时候突然发现钱包不见了。一般人呢可能就慌了，“哎呀，我钱包哪去了啊？刚才买东西的时候还在呢！”然后急的大脑一片空白什么也想不起来。但是数理逻辑智能高的人，当他意识到钱包丢了的时候，他首先会把需要挂失的卡之类的东西先做挂失，把损失减到最低。然后他就开始回想：我刚刚去了哪几个地方，在这几个地方我都干了些什么，在哪个地方我最有可能把钱包给丢了。然后依次回去找。体现了他们比普通人更有理性。不但如此，他们对数字也很敏感，很快就能记住电话号码。

此外，数理逻辑智能高的孩子做事相当有条理，不仅在学习上，在日常生活中，他们的条理性也表现得非常突出。我朋友的小孩，就是数理逻辑智能高的孩子。他今年上小学三年级，早上从来不需要大人叫他起床。他自己有个时间表，早上6:40—6:50起床，穿衣服；6:50—7:10洗漱，上厕所；7:10—7:20吃早饭，然后出门上学。晚上放学回来，作业先写什么，后写什么，也都不用他们家大人操心，很快就能做完，而且质量很高。他的衣橱里的衣服摆的很整齐，书架上的书也是分类放的，玩具全部放在一个箱子里，整个屋子特别干净，根本不像是小男孩的卧室。

推荐专题： 数理逻辑的证明题