《数理逻辑》第七章-4
- 格式:pdf
- 大小:1.16 MB
- 文档页数:9
《数理逻辑》教学大纲徐海燕 编写535目录前言 (537)第一章数理逻辑的由来 (538)第一节 传统逻辑的不足 (538)一、传统逻辑中命题的限制 (538)二、传统逻辑中三段论的限制 (539)三、传统逻辑中量词的限制 (540)第二节 数理逻辑的兴起 (541)第三节非欧几何带来的问题 (544)第四节微积分基础的争论 (546)第五节集合论悖论 (548)第六节 蕴涵词及其怪论 (549)第二章数理逻辑的主要内容 (552)一、真值联结词真值函项重言式 (552)二、命题演算命题逻辑的公理化和形式化 (552)复习与思考题 (553)第三章数理逻辑的三个发展阶段及三大学派 (554)一、数理逻辑的三个发展阶段 (554)二、数理逻辑的三大学派 (554)第四章 数理逻辑的特征和应用 (555)复习与思考题 (555)536前言本课程由逻辑学研究所开设。
本课程是哲学专业的选修课之一。
主要介绍一阶逻辑的基本理论和方法。
主要内容包括:命题形式语言及其语义理论,命题表列,命题演算系统,命题演算系统的可靠性与完全性定理;一阶语言及其语义理论,一阶表列,谓词演算系统,谓词演算系统的可靠性与完全性定理。
本课程旨在使学生掌握公理化、形式化的现代逻辑理论和方法,提高学生现代逻辑思维的素质和能力,培养学生现代逻辑的意识,为学习哲学专业相关课程以及从事现代西方哲学研究工作打下必要的基础。
537第一章数理逻辑的由来本章教学目的和基本要求:掌握数理逻辑的产生根源学时分配:9到了今天,数理逻辑可以说已经是一门成熟的科学,它的内容十分丰富,与别的许多门学科都有牵连,互相影响,要介绍它的内容,或者描绘它与别的学科有所不同的特征,都是非常困难的,最好的办法是先从它的发展过程来考察。
因为一个事物,无论它所包含的内容如何丰富,它的特性如何复杂,如果能够从它的发展来看,先看它是如何产生的,如何一步步地成长,逐渐地由小而大、由简单而复杂的发展,这样我们便能比较容易地掌握其主要内容、找出它的基本特征。
马琦 2010.11.20 maqi08@Hilbert第十问题 第十问题对于任意多个未知数的整系数不定方程, 要求给出一个可行的方法(verfahren),使 得借助于它,通过有限次运算,可以判定 该方程有无整数解。
Hilbert第十问题1970年苏联数学家马蒂塞维奇证明: 在一般情况下,答案是否定的。
算法是关于计算过程 不一定是数值的 算法是关于计算过程(不一定是数值的 是关于计算过程 不一定是数值的) 的一个清楚能行的指令集合, 的一个清楚能行的指令集合 ,可用来 求得给定问题类中的任何一个问题的 解答。
解答。
不可解问题递归不可解问题问题类的整数解吗? 是多项式 是多项式Diophantine方程} 方程} {存在方程E的整数解吗?| E是多项式 存在方程 的整数解吗 方程 的值是什么? ∈ }( 是确定的函数 是确定的函数) {f(n)的值是什么?| n∈DN}(f是确定的函数) 的值是什么 是否是集A的元素 是确定的集合) {n是否是集 的元素?| n∈DN}( 是确定的集合) 是否是集 的元素? ∈ }(A是确定的集合 的定理吗? {A是N 的定理吗?| A是N 的wf.} }问题类和算法问题类是否是n的因数 {2是否是 的因数?| n∈DN} 是否是 的因数? ∈算法已知任意数n,求被 除所得的余数 除所得的余数。
已知任意数 ,求被2除所得的余数。
如果余数是零, 如果余数是零,是; 如果余数是1, 如果余数是 ,非。
给定任意数n,对每一 ( 给定任意数 ,对每一m(1<m<n), ),属于质数集吗? ∈ {n属于质数集吗?| n∈DN} 属于质数集吗存在求n被 除所得余数的标准方法 除所得余数的标准方法。
存在求 被m除所得余数的标准方法。
若没有一个余数是0, 是质数。
若没有一个余数是 ,则n是质数。
是质数 若有一个或几个余数是0, 不是质数。
若有一个或几个余数是 ,则n不是质数。
数理逻辑(MathematicalLogic)数理逻辑(Mathematical logic)是用数学方法研究诸如推理的有效性、证明的真实性、数学的真理性和计算的可行性等这类现象中的逻辑问题的一门学问。
其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。
数理逻辑是数学基础的一个不可缺少的组成部分。
数理逻辑的研究范围是逻辑中可被数学模式化的部分。
以前称为符号逻辑(相对于哲学逻辑),又称元数学,后者的使用现已局限于证明论的某些方面。
历史背景“数理逻辑”的名称由皮亚诺首先给出,又称为符号逻辑。
数理逻辑在本质上依然是亚里士多德的逻辑学,但从记号学的观点来讲,它是用抽象代数来记述的。
某些哲学倾向浓厚的数学家对用符号或代数方法来处理形式逻辑作过一些尝试,比如说莱布尼兹和朗伯(Johann Heinrich Lambert);但他们的工作鲜为人知,后继无人。
直到19世纪中叶,乔治·布尔和其后的奥古斯都·德·摩根才提出了一种处理逻辑问题的系统性的数学方法(当然不是定量性的)。
亚里士多德以来的传统逻辑得到改革和完成,由此也得到了研究数学基本概念的合适工具。
虽然这并不意味着1900年至1925年间的有关数学基础的争论已有了定论,但这“新”逻辑在很大程度上澄清了有关数学的哲学问题。
在整个20世纪里,逻辑中的大量工作已经集中于逻辑系统的形式化以及在研究逻辑系统的完全性和协调性的问题上。
本身这种逻辑系统的形式化的研究就是采用数学逻辑的方法.传统的逻辑研究(参见逻辑论题列表)较偏重于“论证的形式”,而当代数理逻辑的态度也许可以被总结为对于内容的组合研究。
它同时包括“语法”(例如,从一形式语言把一个文字串传送给一编译器程序,从而转写为机器指令)和“语义”(在模型论中构造特定模型或全部模型的集合)。
数理逻辑的重要著作有戈特洛布·弗雷格(Gottlob Frege)的《概念文字》(Begriffsschrift)、伯特兰·罗素的《数学原理》(Principia Mathematica)等。
数理逻辑讲稿数理逻辑又称符号逻辑、理论逻辑。
它是数学的一个分支,是用数学方法研究逻辑或形式逻辑的学科。
其主要特征之一是“形式化”,就是将数理逻辑的研究对象“数学推理形式化,推理都有前提、结论和推理规则,这些前提和结论都是命题。
一个推理系统包含命题、公理和推理规则,“形式化”即为将这样的推理系统符号化而形成一个形式系统。
用数学的方法研究逻辑的系统思想一般追溯到十七世纪莱布尼茨,他设想过能不能创造一种“通用的科学语言”,可以把推理过程象数学一样利用公式来进行计算,从而得出正确的结论。
由于当时的社会条件,他的想法并没有实现。
但是它的思想却是现代数理逻辑部分内容的萌芽,从这个意义上讲,莱布尼茨可以说是数理逻辑的先驱。
后人基本是沿着莱布尼茨的思想进行工作的。
1847年,英国数学家布尔发表了《逻辑的数学分析》,建立了“布尔代数”,并创造一套符号系统,利用符号来表示逻辑中的各种概念。
布尔建立了一系列的运算法则,利用代数的方法研究逻辑问题,初步奠定了数理逻辑的基础。
十九世纪末二十世纪初,数理逻辑有了比较大的发展,1884年,德国数学家弗雷格出版了《数论的基础》一书,在书中引入量词的符号,使得数理逻辑的符号系统更加完备。
对建立这门学科做出贡献的,还有美国人皮尔斯,他也在著作中引入了逻辑符号。
从而使现代数理逻辑最基本的理论基础逐步形成,成为一门独立的学科。
数理逻辑就是精确化、数学化的形式逻辑。
它是现代计算机技术的基础。
数理逻辑的内容两个最基本的也是最重要的组成部分,就是“命题演算”和“谓词演算”。
命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。
命题是指具有具体意义的又能判断它是真还是假的句子。
在谓词演算里,把命题的内部结构分析成具有主词和谓词的逻辑形式,然后研究这样的命题之间的逻辑推理关系。
数理逻辑的发展数理逻辑这门学科建立以后,发展比较迅速,促进它发展的因素也是多方面的。
比如,非欧几何的建立,促使人们去研究非欧几何和欧氏几何的无矛盾性。
马琦 2010.12.18 maqi08@
考察形式系统及其扩张的递归可判定性。
考察形式系统及其扩张的递归可判定性。
可对任何形式系统提出可判定性和不可判定性问题, 因为哥德尔编码对它们都适用。
而这个问题正是DN中 一个特殊的子集的递归性或非递归性的问题。
命题 2.24 可判定的 即有一种能行的方法, L 是可判定的,即有一种能行的方法, 用它可判定, 用它可判定,L 的任意给出的 wf. 是否是 L 的定理。
的定理。
第二章的命题2.24说明命题演算的形 式系统L是可判定的。
可以证明
命题7.41 命题 L的定理的哥德尔数的集合是一个递归集。
的定理的哥德尔数的集合是一个递归集。
的定理的哥德尔数的集合是一个递归集
谓词演算系统KL是否为递归不可判定的,这 依赖于语言L。
取一个特殊情形,设L1 是不含函数字母,不 含个体常项,而只有一个谓词字母的一阶语言。
命题7.42 命题 KL1是递归可判定的。
是递归可判定的。
命题7.43 命题 设L是不包含函数字母和个体常项而只包含一元谓 词字母(可能有无穷个)的一阶语言,则KL 是递归可判定 的。
一阶语言 L
变元 个体常项 谓词字母 函数字母 x1,x2,… a1,a2,… Ain fin
命题7.44 命题 系统N 是递归不可判定的(在它是相容的假定下)。
系统N 是递归不可判定的 因为一个递归集可以有非递归的子集,而一个非递归集 可以有递归的子集,所以已知一个系统是递归可判定(或不可 判定)的,无法判定其扩张的递归可判定性。
但在某些情况下, 可以找出一种联系。
命题7.45 命题 设S和 S+是有相同语言的一阶系统,又S+是S的有穷扩张 有穷扩张, 有穷扩张 即存在wf.的有穷集A1,…,An ,当这个wf.的有穷集增加到S中去 作为S的公理后,我们就得到S+ 的公理集。
若S+ 是递归不可判 若 定的, 也是递归不可判定的。
定的,则S也是递归不可判定的。
也是递归不可判定的
不完全性 • 定理集与真语句集是不同的。
递归不可判定性 • 不存在判定哪些语句对应于N 定理的算法。
N
算术的形式系统因这两种局限而受到损害。
成书为止,还没有找到其他的解决办法。
一个谓词演算的系统是递归可 判定或递归不可判定与语言L有关。
而且,不可判定是常规,不是例外。
命题7.46 命题 存在一阶语言L 使得K 是递归不可判定的。
存在一阶语言L ,使得 L是递归不可判定的。
推论7.47 推论 全一阶谓词演算(具有第3章给出的所有符号)是递归不可判定的。
是递归不可判定的。
全一阶谓词演算 是递归不可判定的
命题7.48 命题
下列系统是递归不可判定的。
▪ 一阶群论。
▪ 一阶环论。
▪ 一阶域论。
▪ 一阶半群理论。
▪ 系统ZF。
下列系统是递归可判定的。
▪ 一阶Abel群理论。
▪ 没有乘法的一阶算术 (类似N ,不包括符号f22,而且删去公理(N5)和(N6))。
。