江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc

江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc

ID:59372465

大小:850.00 KB

页数:5页

时间:2020-09-04

江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc_第1页
江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc_第2页
江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc_第3页
江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc_第4页
江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc_第5页
资源描述:

《江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、命题1.8可数个可数集的并集是可数集.证明:设可数个可数集分别为,其中.我们令.把的元素按照如下次序排成阵列(0.1)并依据箭头指示的方向顺序对集合的元素进行枚举.不难看出该枚举算法可以保证的每个元素在有限步里被枚举到,由此说明是可数的.■命题1.2.2.实数集是不可数集.证明:根据上述分析知,只要证明所有形如(1.2.2)的小数的全体是不可数的.运用反证法:如果全体形如(1.1.2)的小数是可数的,则这些数的全体可枚举如下:(0.2)其中每个是或.我们利用枚举(2.3)构造一小数满足:如果;如果,则不同于(2.3)所枚举出的全体小数中的任

2、意一个,由此产生矛盾.此矛盾说明全体小数是不能枚举的,因此它们是不可数的,所以也是不可数的.■例3-1.证明自然数加法是原始递归函数.证明:首先我们注意到自然数集上的恒等函数是原始递归函数,因为.于是可以通过递归模式,定义.所以是原始递归函数.■例3-2.证明自然数乘法是原始递归函数.证明:我们已经证明了是原始递归的,在此基础上可以通过递归模式,定义.所以是原始递归函数.■命题6.1(可靠性定理).每个的定理都是的重言式.证明:设是的定理,则存在的证明,即公式序列满足:每个或是的公理,或是由某两个前面的公式和经得到.现在我们施归纳于公式序列

3、的长度来证明.奠基步:当时,上述序列中只有一个公式,那么必为的公理L1,L2或L3,由例6-2知一定是重言式.归纳推证步:假设命题对小于的证明序列成立.在证明序列中公式是,可分两种情况考虑:情况1.是公理,那么由奠基步的证明即得是重言式.情况2.是由公式经得到,此时不妨设为的形式.由于和是出现在之前的定理,故根据归纳假定知和均为重言式,即对任意赋值,均有和.如果,那么根据赋值的定义就有,此和矛盾.此矛盾说明对任意的赋值必有,故是的重言式.根据归纳法原理命题得证.命题6.2.形式系统是协调的.证明:如果不是协调的,则存在的公式使得并且.由可靠

4、性定理知和都是重言式,即对任意的赋值,和均为,由此而产生矛盾.■命题6.3.的扩充是协调的充要条件为存在一个合式公式不是的定理.证明:如果协调,则对任意公式,和不能同时为的定理,故至少有一公式不是的定理.反之,假定不协调,那么就有公式使得并且.由于是的扩充,那么的定理也是的定理,由例2-2(b)知是的定理,于是运用推理规则就可得到,其中为任意公式,这样任意公式都成为了的定理.换句话说,如果有公式不是的定理,那么必是协调的.■在我们通过对的公理集添加公式得到扩充时,必须保证是协调的.下面命题为我们提供了一个途径.命题6.4.设是的协调扩充,是

5、的公式并且不是的定理.则我们把加到的公理中得到的扩充是协调的.证明:设是的公式且不是的定理.现将加入的公理集得到的扩充.如果不协调,则有某公式使得并且,由此可得.由于与的区别在于只比多一条公理,所以在中,若假设则可推出,即,运用演绎定理就得到.注意到是的定理因而也是的定理,于是运用可得,这和不是的定理矛盾.命题6.5.设是的协调扩充,则存在的协调完备扩充.证明:首先注意到的全部公式是可数的,因而我们可用某种方法将之排列出来.设是的全部公式的一个枚举.我们构造的扩充序列如下:首先令,构造:如果,则令;如果没有,即不是的定理,则把加入的公理集得

6、到.根据命题6.4知是协调的.假定已有且是协调的,我们构造:如果,则令,如果没有,则把加入的公理集得到.同样是协调的.按照这样的方法依次构造下去,我们得到了一个扩充序列,其中而每个都是协调的.构造形式系统,它的公理集是由所有的公理集的并集组成.我们证明是的协调完全扩充.首先是协调的:如果不协调,那么有公式使得并且,即在中能证明和都是的定理.但由于证明的序列是有穷的,因而最多只用到的有穷条公理,因此必有某个,的公理包含这些公理,于是在中就可证明和都是的定理,这和协调矛盾.其次是完全的:设是任一的公式,不妨设为.如果是的定理,那么也是的定理;否

7、则将成为的定理,当然也是的定理.命题5在解释中,赋值满足公式的充要条件是在中至少存在一个与等价的赋值,满足。证明:设满足,则满足~,故不满足,于是有一个与等价的赋值不满足,故此满足。反之,若与等价的满足,那么不满足,故不满足,可得..满足~,即满足。命题7设是的解释,是的公式,和是中的赋值,且对中的每个自由变元均有,则满足当且仅当满足。证明:施归纳于中联结词的数目奠基步:是原子公式,如,对任意出现在中的自由变元和常元,均有和的值相同,因而,故满足的充要条件为满足。归纳推导:情形1,是;情形2,是;这两种情形可以直接证明,只要用到有关的定义以

8、及归纳假定即可,因而留作习题。情形3,是,假定满足,设是任意与等价的赋值,由于在中不自由出现,则对中出现的任意自由变元,。。我们定义如下:则是与等价的赋值,由满足知,满足知满足,

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。