逻辑与公理化系统

第一讲数理逻辑与公理化系统逻辑是人通过概念、判断、推理、论证来理解和区分客观事物的思维过程，逻辑思维，人们在认识过程中借助于概念、判断、推理等思维形式能动地反映客观现实的理性认识过程，又称理论思维。它是作为对认识着的思维及其结构以及起作用的规律的分析而产生和发展起来的。只有经过逻辑思维，人们才能达到对具体对象本质规定的把握，进而认识客观对象。它是人的认识的高级阶段，即理性认识阶段。概念是反映事物内的本质属性及其分子的的思维形式，是抽象的、普遍的想法、观念或充当指明实体、事件或关系的范畴或类的实体。其特征是概念的内涵（内容）和外延（包含在概念中的事物）；判断的特征是对事物有所断定且有真假；演绎推理的特征是如果前提真，则结论真；（数学的逻辑推理通常是演绎推理）定义是揭示概念内涵的逻辑方式，是用简洁的语词揭示概念反映的对象特有属性和本质属性。定义的基本方法是“种差”加最邻近的“属”概念。定义的规则：一是定义概念与被定义概念的外延相同；二是定义不能用否定形式；三是定义不能用比喻；四是不能循环定义。划分是明确概念全部外延的逻辑方法，是将“属”概念按一定标准分为若干种概念。划分的逻辑规则：一是子项外延之和等于母项的外延；二是一个划分过程只能有一个标准；三是划分出的子项必须全部列出；四是划分必须按属种关系分层逐级进行，不可以越级。数学中的逻辑除了上述特点之外，更重要的是定量的刻画客观事物，在这一过程中，集合是一个基本的概念，它通过集合中的一些关系将事物量化。将具有某种确定的特性的事物的全体称为一个集合。在数学中，在逻辑量化过程中，会用到量词。量词是命题中表示数量的词，分为全称量词和存在量词。全称量词断定所有的个体都具有相关谓词所表示的性质或关系，相当于自然语言中的“一切”、“所有”、“凡”等；存在量词断定存在（即至少有一个，但不一定是每一个）个体具有相关谓词所表示的性质或关系，相当于自然语言中的“有的”、“有”、“至少有一个”、“找得到一个”等。符号表示为V（任一）表示全称量词，3（存在）表示存在量词，在数学中主要有以下几种形式：Vx,F（x）表示任一x具有性质F；3x,F（x）表示存在x具有性质F（满足条件F）；VxVy,G（x，y）表示任一■x和任一■y具有关系G（满足条件G）；Vx3y,G（x,y）表示对任一x,存在y,使得x,y具有关系G（满足条件G）；3xVy,G（x,y）表示存在x,对任一y,使得x,y具有关系G（满足条件G）；3x3y,G（x,y）表示存在x,存在y,使得x,y具有关系G（满足条件G）；复杂的命题或定理、定义是由这几种形式的组合,其一般形式为：pq,pq, ,pq使得q成立。1122 nn n+1其中p(i=1,2,…,n)为逻辑符号V或3；q(i=1,2,…,n,n+1)为数学表达式。ii例1设a,bgR.证明：若对任何正数e有a<b+£，则a<b.证明(反证)若结论不成立，则根据实数的有序性，必有a>b.令e二a-b，则e>0且a=b+e,这与题设a<b+e矛盾，从而a<b.数学的定义都是用逻辑的量化形式给出来的，例如极限的定义数列极限定义：设｝是一个数列，a是一个确定的实数(3agR)，nVe>0,3NgN，当n>N时(Vn>N)，有a一a|<e,则称a是数列｛a｝的极限，+ n n此时也称数列b｝收敛于a。n定义中，数列｝在条件：a是一个确定的实数(3agR)，Vs>0,3NgN，当n +n>N时(Vn>N)下的性质是|a-a|<e。n为了更好地理解定义，从反面看一个数列不收敛，这需要对偶法则。公理系统：从一些公理出发，根据演绎法，推导出一系列定理，这样形成的演绎系统叫做公理系统。欧氏几何学是一个古典的公理系统；现代公理系统的特征：一是严格性；二是选定公理所依据的标准(不是自明的)。形式系统是一个完全形式化了的公理系统，系统包括各种初始符号、形式规则、公理、变形规则。公理4个：第一公理：重言律((pVP)Tp).第二公理：V引入律(pT(pvq)).第三公理：析取交换律((pVq)T(qvp).第四公理：((qTr)T((pVq)T(pVr)).变形规则：一、代入规则；二、分离规则；三、置换规则推演规则(8条)，重点介绍求否定规则与对偶规则求否定规则：设E为一公式，其中T和0不出现，其否定式E-可用以下方法直接得到V被代以A.A被代以V.不出现于部分公式「兀中的兀被代以「兀「兀被代以兀.对偶规则：设A,B为两个公式，在其中T和0不出现，A*和B*是A,B中把V和a互换的结果，有(1)从卜ATB，可得卜B*TA*.（2） 从卜A分B，可得卜B*分A*.注意：求否定规则实质上是数学中的求否命题，对偶规则的本质是命题与其逆否命题等价；由此可以给出对偶法则：设命题P为“PQ,PQ，…,PQ使得Q成立。”则为了TOC\o"1-5"\h\z1122 NN N+1得到P的否命题的正面叙述，只要将“PQ,PQ，…,PQ使得Q成立。中的逻辑符号1122 NN N+1P（I=1,2,…,n）从V（3）改为3（V），并将Q改为它的否定形式即可。i N+1例2定义数列｝发散：Va,玉，VN,Bn>N，使得|a一a|>£.n 0 n 0例3数集A无上界。先看数集A有上界：BM,VxgA，有x<M.则由对偶法则，数集A无上界：VM,BxgA，有x>M.公理系统的作用在于，从一些公理或推演规则出发，把某一范围内的真命题推演出来因此公理系统要求有两个重要性质，一是完全性（完备性），即从公理出发，能推出多少，是否完全；二是一致性（无矛盾性），即有没有逻辑矛盾，是否一致。一致性定义有几种，一般介绍以下三种：一、 古典定义：一公理系统是一致的，当且仅当，不存在任何公式A，A和非A都在这个系统里可证。二、 语义定义：一公理系统是一致的，当且仅当，一切在这系统里可证的公式都是真的。三、 语法定义：一公理系统是一致的，当且仅当，并非任一合式公式都在这系统里可证。完全性定义有以下三种：一、 语义定义：一公理系统是完全的，当且仅当，一切属于某一特定范围内的真命题都是在这个系统里可证的。二、 语法定义：一公理系统是完全的，当且仅当，如果把一个推演不出的公式作为公理，其结果，所得的系统就不一致。三、 古典定义：一公理系统是完全的，当且仅当，对于任一合式公式A，或者A是可证的，或者非A是可证的。独立性定义：一公式集合M是独立的，如果M中任一公式A都不能根据给定的推演规则从M中其它公式推演出来。不同命题的逻辑：（1） 古典逻辑（二值逻辑：真或假，具有排中律）；（2） 多值逻辑（变项和公式的值不止一项）；（3） 模态逻辑；（4） 构造性逻辑（真假概念是与构造的可实现性相联系的，排中律失效）附录：数理逻辑发展简史数理逻辑的五个特征：第一，数理逻辑是边缘性的学科，在它的范围内，逻辑内容和数学的内容常常交织在一起；第二，从逻辑角度考虑，数理逻辑是研究演绎方法的科学。演绎方法包括演绎推理和以演绎为基础的证明和公理方法。第三，在方法方面，数理逻辑使用了特制的符号语言并且在不同部分引用了不同程度的数学方法，随着数理逻辑的进展，还出现了一些新方法，如形式化方法、算术化方法递归论和模型论方法等。第四，数理逻辑的很大部分内容已经成长为数学的分支。第五，数理逻辑的逻辑方面是现代的形式逻辑。狭义的数理逻辑：用数学方研究数学中的演绎思维和数学基础的学科；广义的数理逻辑：包括一切用特制符号和数学方法来研究处理演绎方法的理论，有时也称为符号逻辑（1881年英国逻辑学家J.Venn提出）。数理逻辑的发展阶段从17世纪末莱布尼茨起至今有三百年历史。第一阶段，开始用数学方法研究和处理形式逻辑的时期，初始阶段。在本阶段里，用数学方法研究思维规律的想法开始被提出。从17世纪70年代的莱布尼茨到19世纪末布尔（英国）、德摩根（英国）、施罗德（德国）约200年，其成果是逻辑代数和关系逻辑。莱布尼茨是数理逻辑的创始人，他相信逻辑，更推崇数学方法。他认为，数学之所以能如此迅速的发展，数学知识之所以能如此有效，就是因为数学使用了特制的符号语言，这种符号为表达思想提供了优良的条件。他在数理逻辑方面的贡献：一是成功地将命题形式表达为符号公式；二是构成了一个关于两个概念相结合的演算。布尔是一个自学成才的数学家，1844年发表论文《关于分析中的一个普遍方法》1849年被聘为爱尔兰考克城皇后学院的教授。他的逻辑著作《逻辑的数学分析》（1847）和《思维规律的考察》（1854），布尔的目的是构造一个演绎思维演算，他的指导思想是逻辑关系和某些数学运算甚为类似，代数系统有不同的解释，把解释推广到逻辑领域，就可以构成一思维的演算。1833年GPeacock（1791—1858）提出了所谓的“形式永久性原则”他们把代数学看作为一种关于符号及其组合规律的科学，代数定理只依据于符号所遵守的组合规律，而与符号所涉及的内容无关。布尔在《思维规律的考察》中说，思维的运算和代数的运算，他们的“规律必须独立地确定是否成立；它们之间的任何形式的相符只能通过比较然后才能建立起来。”根据以上思想，布尔构成了一个抽象代数系统，对于这个系统，他给出了四种解释：一种是类的演算，两种是命题的演算，一种是概率的演算。19世纪后期德国数学家施罗德将布尔代数构成一个演绎系统。英国数学家德摩根是第一个提出关系逻辑理论的人，他提出了域论的概念，德摩根定理是逻辑学上的一个重要定理。第二阶段，19世纪中叶数学科学的发展提出了研究数学思想和数学基础的必要性。数理逻辑适应数学的需要，联系数学实际，在60年的时间内奠定了它的理论基础，创立了特有的新方法，取得了飞跃的发展，成为一门新科学，主要包含以下四个方面：（1）集合论的创立。在19世纪70年代，德国数学家GCantor由于数学理论的需要，创立了集合论，奠定了以后发展的基础。集合论是关于无穷集合和超穷数的数学理论；数学里遇到的无穷有：无穷过程、无穷小、无穷大。中国古代和西方希腊时期，数学家们已经接触到无穷过程和无穷小，可是还不能掌握其规律，对他们没有本质的认识。17世纪微积分出现以后，用到了无穷小增量，引起了对无穷小的讨论及唯心主义的攻击（英国哲学家、牧师GBerkeley在《分析学家》中写到：“这些消失的增量究竟是什么呢？它们既不是有限量，也不是无穷小，又不是零，难道我们不能称它们为消逝量的鬼魂吗？”19世纪20年代，A.L.Cauchy明确了诸如收敛性、极限等许多概念，建立了极限理论，使得人们对无穷过程才有了本质的认识。但直到20世纪60年代通过模型论的方法，即非0又非有限数量的无穷小量才重新得到肯定，并在此基础上建立了非标准分析。无穷集合的分类——比如狄立克莱函数（分类是必要的）；多维连续统：发现两个不同的无穷集——自然数集合和连续统（实数集合）更大的无穷（更大的序数——基数的扩大）康托尔定理：2a>a.良序定理，连续统假设——至今未证明；实（在）无穷与潜（在）无穷，康托尔的观点：（1）数学理论必须肯定实无穷；（2）不能把有穷所具有的性质强加于无穷，无穷有其固有的本质；（3）有穷的认识能力可以认识无穷，哲学的无穷和数学的无穷。（2）公理化方法的发展。公理方法的应用是从公元前约300年欧几里得的《几何原本》开始的，从《几何原本》到1899年希尔伯特的《几何基础》共经历了2300多年，从不成熟的实质公理学发展到具有丰富方法论的形式公理学的逻辑理论，这为20世纪公理方法与数学基础的研究开辟了道路。实质公理学，公理学所处理的对象已先于公理而给定。《几何原本》，牛顿力学都是实质公理学；形式公理学并不要求先给定某一类具体的对象。（3） 逻辑演算的建立19世纪70年代至20世纪初，为了探究数学科学的性质和数学思维的规律，经过德国数学家弗雷格、意大利数学家皮亚诺、英国逻辑学家数学家和哲学家罗素的努力，建立了一个初步自足的完全的逻辑演算。（4）证明论的提出及其后果19世纪中叶，数学基础研究获得了三方面的重要成就：（1）康托尔创建了集合论，加深了对实无穷的认识；（2）希尔伯特发展了形式公理化方法；（3）弗雷格和皮亚诺给出了一个完全的逻辑演算。出现的一些带根本性质问题：（1）是否有实无穷？（2）如何解决康托尔的“一切集合的集合”的悖论？（3）如何论证一个关于基本数学理论的形式公理系统，如实数系统的一致性？（4）数学基础是什么？（5）数学能否建立在逻辑之上？对这些问题的争论，形成了不同的数学学派：直觉主义，构造主义直觉主义学派的创始人是荷兰数学家布劳威尔，主张直觉或直接感知是认识的根本来源，是必然性知识的保证。构造主义学派主张，自然数及其某些规律，特别是数学归纳法，是数学最根本的和直观上最可信的出发点，其他一切数学对象必须能从自然数构造出来，否则就不能作为数学对象。构造主义不承认间接的存在性证明，存在就必须构造得出来——排中律不是普遍有效。第三阶段，1940年前后到70年代是数理逻辑的发展阶段。本阶段数理逻辑的主要内容大致为：逻辑演算、证明论、公理集合论、递归论和模型论。重要结果：（1）1928年希尔伯特和阿克曼从逻辑演算中把谓词演算分离出来并证明其一致性（；2）1930年歌德尔完全性定理；（3）1931年歌德尔的两个不完全性定理；（4）能行性或机械过程的数学描述；（5）一些限制性定理的不可判定性。歌德尔的完全性定理：（1）狭谓词演算的每一有效公式都可证；（2）狭谓词演算的任一公式或者是可否证或者是可满足的（而且是可数个体域可满足的）；（3）一可数无穷多公式的系统是可满足的当且仅当每一有穷子系统是可满足的。歌德尔不完全性定理：一个包括初等数论的形式系统，第一不完全性定理：如果该系统是一致的那么就是不完全的；第二不完全性定理：如果该系统是一致的那么其一致性在本系统中不可证。为此，数学分析需要的基本知识是什么？其公理化系统又是怎样的？一、建立实数的原则与完备有序域有理数全体组成的集合Q，构成一个阿基米德有序域，当它扩充为实数集R之后，仍是一个阿基米德有序域。一个数域F构成一个阿基米德有序域，指它满足以下三个条件：(1)F是域(2种运算+,X，8条规则)；(2)F是有序域，定义序关系“<”满足传递性、三歧性(加法乘法保序性)；(3)阿基米德性质：F中的任意两个正元素a,b，必存在正整数n，使得na>b.二、 戴德金分划设有理数集Q的两个子集A,A'满足：(1)A,A'都不空；AA'二Q；VagA,a'gA'，都有a<a'，称有序集合对(A,A')为Q的一个分划(戴德金分划)；并分别称A,A'为下类和上类。有端(点)分划——确定一个有理数；无端分划——确定一个无理数。戴德金定理：设(A,A')为R的一个分划，则或者A有最大元，或者A'有最小元。该定理与确界定理等价。三、 无限小数与实数回顾：(1)用无限小数定义实数；(2)无限小数的运算法则；(3)确界与确界定理例4实数的稠密性：Vx,ygR(x<y)，则在它们之间必有无穷多个实数，且有无穷多个有理数。四、 实数完备性等价命题(1)戴德金定理；(2)确界定理；(3)单调有界定理；(4)区间套定理；(5)有限覆盖定理；(6)聚点定理；(7)苛西准则关系：⑴o⑵二⑶二⑷二⑸二⑹二⑺n(2).(证明见备课本)(0.0)戴德金定理n确界定理证明只证明非空有上界的数集必有上确界，非空有下界数集必有下确界类似可证。设S为一非空有上界的数集，并令在R中的全体上界组成集合A'，记A二R\A'，从而(A,A')是R的一个分划，且SuA.由戴德金定理，或者A有最大元，或者A'有最小元,记这个元为耳，下证耳二supS.

（1）VxeS，则x<n.(2)若耳丘S，贝山必是S的最小上界；若耳纟S,Vs>0，必有n-seA，事实上,若n-sea'，则n<n-s.这是不可能的。从而n-s不是s的上界。有确界的定义，n二sups.(1.0)确界定理=戴德金定理证明设R的任一分划(a,A')，由于A'中每一个数皆为A的上界，故由确界定理，A有上确界Q二supA，又由分划定义(AuA'二R)，a或者属于A，或者属于若aeA，则因VxeA,x<a，故a为A中最大元；若aeA'，则a必A'为中最小元。若不然，必定存在beA'，使得b<a；但由b是A的上界，(而1a)A的确界定理;，单调有界定理=^>证只证明单调增加有上界数列有极限，单调减少有下界数列有极限类似可以证明。设£｝为递增数列，且有上界。由确界定理，存在上确界,｝，下面证明a又是I的极a二supla$ a laJ限。nn存在/｝，使得存在/｝，使得ae\a)且a是｝的上界，，再由极限的定+ss>0，又橋｝是递增数列，a>a-s 1a｝故当N时有<<n>N a-s<a<a<a<a义有Nnlima=a.n(2)单调有界定理，闭区间套定理，证明设1ab]｝为一闭区间套，则£｝为递增数nn n

列，并以b为上界，因而存在极限「,，且b lima=g1 n»n123。同理£｝为递减数列，且有下界，<g,n二1,2,3,… lb/从而有n极限，又limb=lim（b一a）+lima=0+g=g<b,n=1,2,….n n n n nnT8nT8 nT8ge[a,b],n二1,2,….最后证明这样的g是唯一的。（反证）若存在g另一个数乙'「bI12，则g'e[ab]n12…nng-g1<bng.3）闭区间套定理有限覆盖定理证明（反证）设h=&时为闭区间[a.]的一个无限开覆盖，假设不能用H中有限个开区间H来覆盖「b]。[ab]把「b]等分为两个子区间，则其中至少有一个[ab]子区间“不能用H中有限个开区间覆盖”记H这个子区间为[a,b]这个子区间为[a,b]u[a,b],b—a1111b—a再把[a1,b1]等分为两个子区间，同样有其中至少一个子区间

不能用H中有限个开区间覆盖”，记之为H[a[a,b],b—a2222b—a将上述步骤无限地进行下去，22.般有（1）[,][,],1,2,，[a,b]u[a,b],n二1,2,…n+1n+1 nn"2）lim（b一a）=lim_—=0.nn 2nnT8 nT8厶且每个「b]都“不能用H中有限个开区间覆[a,b] H盖”于是£,b]}构成一个闭区间套，由闭区间套定理，存在唯一一点「b]12但因ge[a,b],n二1,2,….它必含于H中某个开区间:⑺之内。设ge[a,b] H （a,卩）•疋g}0，由（2）式，当足够大时，mm{g—a,p-g}>0 n就有[a,b]uU（g,£）u（a,p）.nn这说明当足够大时，[b]只需要H中一个开n [a,b] H区间就能将它覆盖，这与构造「b]的假设“不[a,b]能用H中有限个开区间覆盖”相矛盾。所以，H必存在H的某一有限子集就能覆盖「b].H [a,b]（4）有限覆盖定理聚点定理证明设S为实轴上有界无限点集，故存在，使得这样，若有聚点，由极限M> Su[-M,M]. S的保序性知聚点必定在[MM]中。现在用反证[-M,M]法证明聚点的存在。假设[MM]中任一点都不是S的聚点，则对每[—M,M] S一个[MM]，必有相应的「使得在U（5）内xe[—M,M] 5 U（x,6）至多只有一点S。于是，这样的邻域的全体xeS

形成对闭区间[MM1的一个无限开覆盖:[-M,M]H二｛U(x,5)1xe[-M,M]｝.x由有限覆盖定理，H中存在有限个开区间HH*二｛U(x,5)|i二1,2,…,K｝uHixi便能覆盖[MM]，当然也覆盖S，从而S中至多[-M,M] S S只有K个点，这与S为无限点集相矛盾。所以KS在[,]中一定有的聚点。聚点定理有一个重要推论——致密性定理，致密性定理考虑的是数列极限及其子列极限的关系，在讨论数列的极限时经常用到。推论(致密性定理)有界数列必含有收敛的la.M,n=1,2,la.M,n=1,2,…，则必nM>0有数列橋｝的子列｛｝使得「)a/ a丿 lima=an nk kT8nk，则二a(5，则二a证明必要性若数列橋｝收敛，设「TOC\o"1-5"\h\za limnnT8由极限的定义，0当N时，有]Vs>0,BN>0n>N l是，对任何N，有n,m>Nla—aIMa—al+la—aIvs.nmn m所以柯西条件成立。充分性当柯西条件满足时，首先证明

橋}为有界数列。事实上，对于5N，当1a} £二1,3NeN+n,时，有||||||1，从而|1|1||.令n>N,m=N IaI-IaI<Ia-aI<1 IaI<1+IaI.TOC\o"1-5"\h\z1 1n N1/则有n N1M=max{laI,IaI,…,IaI,IaI+1} 、12 N1-1 N1Ial<M,n二1,2,….n由于£｝为有界数列，故由致密性定理，n，下面证明n，下面证明£｝也n在收敛的子列｛｝，设lima=ank ksnk以为极限。由柯西条件与收敛的定义时，有V£>0,3K>Nk,n,m由柯西条件与收敛的定义时，有V£>0,3K>Nk,n,m>KIa-aI<^Ian nk2就有nkI£，因此当一aI< .2K，同时有>kK，n>K n>k>KkIa-aI<Ia-aIn