数理逻辑(讲义).pdf

《数理逻辑(讲义).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数理逻辑》教案许道云(2011.8)教材：《面向计算机科学的数理逻辑》(第二版)(陆钟万著)出版社：科学出版社版本：2006年6月第8次印刷绪言（课程介绍）什么是逻辑？命题（判断）对象、以及对象间的（推理）关系。数理逻辑：用数学的方法研究逻辑。数理逻辑研究分支：模型论、集合论、递归论、证明论。数理逻辑研究什么？逻辑推理：当前提为真时，保证结论为真。逻辑研究这样的可推理关系。即，前提和结论之间的推理关系是否正确。演绎推理---演绎逻辑。它不同于归纳逻辑。归纳逻辑是从前提出发，使用归纳推理，得到的结论与自身协调，或与前提协调。数理逻辑属于演绎逻辑范围。只研究推理及可推理关系，不

2、关心前提与结论中各个命题的真假。例1.前提：所有大于2不被自身整除的自然数为素数。7不被自身整除。结论：7不是素数。例2.前提：所有中学生打网球。王君不打网球。结论：王君不是中学生。命题有内容和形式：内容决定命题的真或假。决定前提和结论之间的可推导关系，是命题逻辑形式。如：前提：集合S中的所有元素具有R性质。a不具有R性质。结论：a不是S中元素。命题的陈述需要语言。元语言：描述对象的所用的最基本语言。如：自然语言（汉语）。对象语言：描述“对象所用元语言”的语言。如：形式语言（符号语言）。自然语言中语言上的相似并不保证逻辑形式上的相同。1例1：X认识Y。（前提）Y是足球队长。（

3、前提）X认识足球队长。（结论）例2：X认识A班某学生。（前提）A班某学生是足球队长。（前提）X认识足球队长。（结论）近代数理逻辑思想：Leibniz力图建立一种精确的、普适的科学语言作为形式语言。直到1879年，Frege才建立了这样的语言。近代数理逻辑介绍的就是这种形式语言。所以，数理逻辑史从1879年算起。在数理逻辑中要构造一种符号语言来代替自然语言，这种人工构造的符号语言称为形式语言。对象的描述和对象间的推理关系全部用形式语言表示。数理逻辑研究的主要内容：（1）引入一个形式语言，以表示非结构化对象。并且要求表示公式的语言是递归生成的。（2）引入一套形式化推理规则，基于这

4、些规则进行符号化演算。引入形式证明的一般形式。(

5、A)（3）引入一套解释系统---语义(映射)函数，赋予形式符号在给定环境下的具体含义。（4）基于语义模型，引入逻辑推理概念。(

6、A)（5）研究形式推理与逻辑推理之间的关系。（可靠性和完备性）。形式推理系统的可靠性：

7、

8、AA。形式推理系统的完备性：

9、

10、AA。一般，逻辑中的语言和推理是某类智能推理的抽象，语言解决表示问题(即，数据结构问题)。从某种意义上讲，应该是先有具体实例，想找一种一般描述，这就产生了形式语言和形式推理。实例数据对形式符号给出一种解释(或赋值)。两者之间的映射关系形成一个解释系统。实

11、例数据与形式符号有解释(或赋值)和被解释(或赋值)之分。如：a:=0.可以理解为：将数字0赋给符号a.也可理解为：a被解释为0.2其中，a是抽象的，而0是具体的。为什么会有各种逻辑？由逻辑研究内容，我们可以观察下表：语法语义形式语言解释系统(表达方式和能力)语义(映谢)函数形式推理：

12、A逻辑推理：

13、A可靠性：

14、

15、AA完备性：

16、

17、AA在表中，形式语言、解释系统、推理规则是可变的。(1)当形式语言的表达能力不够用时，新的语言就会出现。(2)不同规则系统的引入，直接关系到形式推理的能力说、有效性、以及单调性等。(3)不同的解释系统，给出不同的语义模型。思

18、考题：1、逻辑研究的主要内容。2、为什么会有各种逻辑？3第一章预备知识集合：某些对象全体。集合表述方式：内涵：元素具有的性质P。外延：所含元素的全体。自然数集合N上的二元关系<（作为集合）：（内涵）m

19、

20、

21、

22、ST可数无限集：与自然数集等势的集合。可数集：有限集或可数无限集。

23、

24、

25、SN

26、定理：（1）可数集的子集仍然可数。（2）有限个可数集的并仍为可数集。（3）可数个可数集的并仍为可数集。自然数集合N的归纳定义：（1）0N.（2）如果

27、nN，则（后继）nN'。（3）N只含通过（1）（2）有限次使用得到的数。等价定义：自然数集合N是满足如下条件的最小集合S（1）0S。（2）如果nS，则（后继）nS'。设R是一个性质，Rx()表示x具有性质R。定理1（数学归纳法）如果（1）R(0)。（2）对于任意的nN，如果Rn()则Rn(')。则对于任意的nN有Rn()。设h,g为两个N上的己知函数。递归定义N上一个函数f如下：4(1)fg(0)(0).(2)fn(')hfn(()).定理2（递归原理）对于给定的函数g和h，能唯一定义