《数理逻辑复习10级.docxVIP

可计算性概念：可枚举与不可枚举。能行可计算的：按照一组给定指令能够原则上确定从Z到Z的函数f在任意自变量n处的值f(n)，则f是能行可计算的。不可计算性。对角线函数d和停机函数h都是不可计算的。递归算盘可计算图灵可计算递归图灵论题：能行可计算的函数都是图灵可计算的。丘奇论题：能行可计算的函数都是递归的。原始递归：由基本函数（零函数，后继函数，恒同函数）出发通过复合和递归能够得到的函数为原始递归函数。递归函数：由基本函数（z,s,id）出发经过Cn,Pr,Mn能得到的函数称为递归函数。递归集合/递归关系：它的特征函数是（原始）递归的，则它是（原始）递归的。（原始）递归关系的封闭性：代入，图关系，否定，合取，析取，有界全称量化，有界存在量化，有界极小化，有界极大化通用函数/通用关系/通用图灵机。存在k元递归函数的通用函数，其图是半递归的。半递归关系等价于能行半可判定关系。n元能行半可判定关系为从n+1元能行可判定关系通过（无界）存在量化得到的关系。半递归关系的封闭性：递归都是半递归的；代入；合取，析取；有界全称量化，存在量化半递归集与递归可枚举集(r.e.)是等价的。逻辑概念：（开/闭）项，（开/闭）公式，语句，自由/约束变元，解释，蕴涵/推论，有效，可满足/不可满足的，等价，逻辑等价模型，同构，等价，型构语法概念语义概念推演deduction推论consequence反驳refutation不可满足unsatisfiability证明demonstration有效性validity可推导的derivable 安全的secure=：可靠性定理=：哥德尔完备性定理推导derivation，可推演的，可反驳的，可证的，协调的，不协调的证明，定理，理论，可公理化，可有限公理化，完全的，协调的，可判定的算术的arithmetically，初等公式，存在-初等公式存在-初等公式的封闭性：初等公式=存在-初等公式；合取析取；有界量化；无界存在量化可定义，可表示。它们在TA中等价。极小算术Q。递归函数在Q中可表示；递归关系在Q中可定义。Q+归纳公理=P(Peano算术)一些逻辑的重要否定结果，包括：塔斯基定理：TA*不是算术可定义的。算术的不可判定性：TA*不是递归的。实质不可判定性：Q的协调扩张（包括Q）都不是可判定的。丘奇定理：有效语句集合不可判定。哥德尔第一不完全性定理：不存在Q的协调的，完全的，可公理化的扩张。★问题一：两集合等势。思想：1.直接证明：寻找一个双射函数，能从集合A影射到集合B。2.间接证明：寻找一个集合C，A与C等势且B与C等势。例子：作业一Ex 1.6 证明以下两集合等势(a)分母为2的幂的有理数集合；(b)正整数的所有有限子集与余有限子集的并。用间接证明法。分别证明(a)与N等势且(b)与N等势。即证(a)(b)都为无限可数集。有理数集合是可数的，(a)是有理数集合的子集，故也是可数的。正整数的有限子集和余有限子集分别都是可数的，所以它们的并也是可树的。显然(a)(b)都是无限集合，所以他们是等势的。作业一Ex 2.9 证明0,1间实数集合A等势于正整数集合的集合B。直接证明法，构造一个从B到A的双射h.可以借助无限序列的集合L（由无限个0或1组成的序列的集合）。B到L存在双射且L到A存在双射。★★问题二：对角线证明法思想：反证归谬。（一）停机问题及其变种。例子：停机问题是不可判定的。（程序在某输入时是否打印1是不可判定的）假设存在一个算法H(P,I)。当程序P在输入I时停机，则返回halt。构造程序K（P），如果H（P,P）返回halt则进入无限循环。那么考虑程序K在输入K时：K不停机当且仅当H(K,K)返回halt当且仅当K停机。矛盾。作业一 Ex 4.2 是否存在一个从带子上任意位置开始的图灵机，它最终停机，iff带子最初完全空白？假设存在这样的图灵机T。T会停机，则一定在执行n条指令之后。考虑以下初始状态：前面n个空白之后才有1个1。则T会停机。但带子不全为0，故假设错误。（二）其他例子：作业二附加题：证明：（1）不是所有的全递归函数是原始递归的（2）对全部一元递归关系来说，没有递归通用关系R(x,y)(1)假设全部全递归函数都是原始递归的，把它们列出来f1,f2…（递归函数是可数的）令d(n)=fn(n)+1，那么一方面d不等于任一个fn，另一方面d是全递归函数。故矛盾。(2)假设存在这样的通用关系。那么任一个递归一元关系都可用R表示。将所有能用R表示的一元递归关系列出来R1,R2,…（递归关系是可数的）令一元关系R’(n)=~Rn(n)则R’不为R1不为R2…R’不在R1R2…中，不可由R表示。故矛盾。★★问题三：证明递归/半递归（重点中的重点）思想：1.Kleene定理：集合A是递归的当且仅当A和A的补