面向计算机科学的数理逻辑复习文档.doc

绪论一、数理逻辑研究什么？ 研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的二、数理逻辑如何研究？ 形式语言第一章 预备知识第一节 集合一、集合1、 集合的内涵和外延（所有元素的共同性质/构成集合的所有元素）2、 有序偶和笛卡儿集二、关系1、 概念：集合S上的n元关系R2、 特殊情况：集合S上的一元关系R（集合S上的性质R）三、函数（映射）1、 概念：函数（集合有序偶性质）、定义域dom（f）、值域ran（f）2、 概念：f（x）（函数f在x处的值）3、 概念：f：ST（函数f是由S到T的映射）、满射、一一映射四、等价1、 概念：关系R是集合S上的等价关系（自反对称传递）2、 概念：元素x的R等价类3、 性质：R等价类对集合S的一个划分（两两不相交，且并为S）五、基数1、 概念：ST（两个集合S和T是等势的）2、 概念：集合S的基数|S|（集合中的元素个数）3、 概念：可数无限集 第二节 归纳定义和归纳证明一、归纳定义1、 集合的归纳定义、直接生成某些元素、给出运算，将其作用在已有元素上，以产生新的元素、只有这样才是集合中的元素，除此之外，再也没有了2、 典例：自然数集N的两个归纳定义二、归纳证明1、 归纳定理：设R是一个性质，如果、R（0）、对于任何nN，如果R（n），则R（n）那么，对于任何nN，都有R（n）2、概念：归纳基础、归纳步骤（包括归纳变元和归纳假设）、归纳命题、归纳证明3、概念：串值归纳法及其变形三、递归定义1、 递归定义（在归纳定义的集合上，定义函数）在自然数集N上定义一个这样的函数f：g，h是N上的已知函数f（0） g（0）f（n）h（f（n）2、 递归定义原理（这样的函数是存在而且唯一的）第二章 经典命题逻辑第一节 联结词一、基本概念1、 概念：命题（陈述句+确定值）（要么是真，要么是假）2、 概念：简单命题和复合命题（区分的关键）3、 小结：只考虑复合命题的真假是如何确定的二、联结词1、 非A：2、 A与B：A为真并且B为真3、 A或B：A为真或B为真（A为真或B为真或AB同时为真）4、 A蕴涵B：如果A真，则B真（并非A假B真）5、 A等值于B：如果A蕴涵B，同时B蕴涵A第二节 命题语言一、基本概念1、 概念：命题语言（命题逻辑使用的形式语言）2、 归纳：命题语言的三类符号（命题符号联结符号标点符号）3、 概念：表达式、长度、空表达式、两个表达式相等4、 概念：段、真段、初始段、结尾段二、基本概念1、 定义：原子公式，记为Atom（LP）（单独一个命题符号）2、 定义：公式，记为Form（LP）（经典归纳定义及其两种变形） 经典定义容易理解，然而两种变形更容易使用3、 定理：如何证明LP的所有公式都满足R性质？ 关键：假设S=AForm（LP）| R（A）4、 概念：对公式的结构做归纳（上述归纳证明）三、习题解析1、 关键：利用二叉树表示公式的生成过程2、 关键：蕴涵有多种不同的叙述方式（关键：分清楚充分条件和必要条件）、如果p，则q、只要p，则q、p仅当q 、只有p，才q、除非p，否则q（思路：想方设法转化为上述情形）第三节 公式的结构一、引理1、 引理1：LP的公式是非空的表达式2、 引理2：在LP的每个公式中，左括号和右括号出现的数目相同3、 引理3：真初始段不是公式（在LP的公式的任何非空的真初始段中，左括号出现的次数比右括号多。因此，LP的公式的非空的真初始段不是LP的公式（同理分析真结尾段）二、定理1、 定理：LP的每个公式恰好具有以下6种形式之一；并且在各种情形中，公式所具有的那种形式是唯一的 注意：仔细分析其证明过程2、 推论：LP的公式的生成过程是唯一的3、 概念：否定式、合取式、析取式、蕴涵式、等值式三、辖域1、 概念：辖域、左辖域、右辖域2、 定理：任何A中的任何辖域存在并且唯一3、 性质：如果A是B中的段，则A中的任何联结符号在A中的辖域和它在B中的辖域是相同的4、 定理：如果A是（B）的段，则A（B）或者A是B中的段；如果A是（B*C）中的段，则A（B*C）或者A是B或C中的段四、其它1、 算法：判断一个LP的表达式是不是公式的算法2、 符号的省略：最外层括号其它形式的括号联结符号的优先级五、习题解析 第四节 语义一、基本概念1、 概念：真假赋值2、 概念：公式的真假值AV（真假赋值v给公式A指派的真假值递归定义）3、 定理：对于任何AForm（LP）和任何真假赋值V，AV0，1 关键：如何证明LP的所有公式都满足R性质？二、基本概念1、 概念：V（表示公式集）2、 概念：是可满足的（存在V，使得V1） 注意：是可满足的蕴涵中的所有公式都是可满足的，但逆命题不成立3、 概念：A是重言式、A是矛盾式4、 概念：A的真假值表（真假赋值V给公式A指派的值，仅涉及V给A中出现的不同的命题符号所指派的值）5、 性质：简化公式（熟练掌握简化公式）三、习题解析1、 性质：联结符号满足交换律和结合律2、 性质：A是重言式，则AB是重言式当且仅当B是重言式第五节 逻辑推论一、逻辑推论1、 符号：A（A是的逻辑推论，读作逻辑地蕴涵A）2、 概念：A，当且仅当对于任何的逻辑赋值V，如果V1，则AV13、 概念：|A（存在逻辑赋值V，使得V1，AV0）4、 特殊情况：A（这时存在着性质：A是重言式）5、 概念：逻辑等值公式A|B6、 例题分析：注意找到捷径和方法、如何证明一个逻辑推论是成立的（直接证明或者反证法）、如何证明一个逻辑推论是不成立的（构造出这样的真假赋值V，使得V1，AV0）二、定理1、 性质：合取符号和析取符号都满足交换律和结合律2、 定理：、A1，AnA，当且仅当A1AnA、A1，AnA，当且仅当A1（AnA）3、 引理：如果A|A并且B|B，则有A|A等5条性质4、 等值替换定理：设B|C并且在A中把B的某些出现替换为C而得到A，则A|A5、 对偶性定理：A|A（其中A是A的对偶）第六节 形式推演一、形式推演1、 形式推演本质（形式推演仅涉及公式的结构，而与公式的语义无关）2、 形式推演规则（共有11条规则）3、 推论：如果A，则A二、形式可推演1、 概念：形式可推演A（A，当且仅当存在有限序列1A1，nAn，其中的每一项kAk都是由使用某一形式推演规则生成，并且n，AnA）2、 概念的剖析：归纳定义三、基础定理1、 定理：如果A，则存在有限的EO，使得OA（对A的结构做归纳）2、 概念推广：（注意可以推广到无限情形）3、 推演传递定理：如果，A，则A四、定理集群一（每一条都要求严格证明，并且反复记忆，作为后面证明的出发点）1、 定理：（定理群；定理2.6.4）、性质：AB，AB、性质：AB，B A、性质：ABA、性质：AB，BC AC（蕴涵传递）、性质：A（BC）、ABAC2、 定理：（定理群；定理2.6.5）、性质：AA；A A、性质：如果，AB；，A B，则 A（归谬律，或称（）、性质：A，AB3、 定理：（定理群之一；定理2.6.6）、性质：AB BA（以此为基础衍生的4条性质）、性质：如果AB，则B A（以此为基础衍生的4条性质）、性质：AB，当且仅当AB（严格证明之）4、 定理（定理群之二；定理2.6.7）、性质：AAA（相似性质：AA A）、性质：AB，AB A（相似性质：AB，ABB）、性质：（AB）A（相似性质：（AB） B）五、定理集群二（每一条都要求严格证明，并且反复记忆，作为后面证明的出发点）1、 概念：语法等值公式A|B2、 定理（定理群；定理2.6.8）、性质：AB|A，B、性质：AB| BA（交换律）、性质：（AB）C| A(BC)（结合律）、性质：（AB）| AB（相似性质：（AB）| AB）、性质： （AA）（不矛盾律）3、 定理（定理群；定理2.6.9）、性质：AAB，BA（最关键还是规则本身：允许在前面或后面增加）、性质：AB |BA（交换律）、性质：（AB）C| A(BC)（结合律）、性质：AB | AB（相似性质：AB | AB）（分析其证明步骤）、性质：（AB）| AB（Morgen定律）、性质：（AB）| AB（Morgen定律）、性质： AA（排中律）4、 定理（定理群；定理2.6.10）、性质：A（BC）| (AB)（AC)（分配律）、性质：A（BC）| (AB)（AC)（分配律）、性质：A（BC）| (AB)（AC)、性质：A（BC）| (AB)（AC)、性质：（AB）C| (AC)（BC)、性质：（AB）C| (AC)（BC)5、定理（定理群；定理2.6.11）、性质：AB|AB，BA（严格证明）、性质：AB| BA（交换律）、性质：AB| AB、性质：（AB）| AB、性质：（AB）| AB、性质：AB|（AB）（AB）、性质：AB|（AB）（AB）、性质：（AB）C|A( BA)（结合律）、性质：AB；BCAC、性质：AAB、性质： （AB）（AB）六、定理群1、 定理：、A1，AnA，当且仅当A1AnA、A1，AnA，当且仅当A1（AnA）2、引理：如果A|A并且B|B，则有A|A等5条性质3、等值替换定理：如果B|C并且在A中把B的某些出现替换为C而得到A，则A|A4、对偶性定理：A|A（其中A是A的对偶）第七节 析取范式和合取范式一、基本概念1、 概念：单式（原子公式或者原子公司的否定式）2、 概念：子式、析取子式、合取子式3、 概念：析取范式、合取范式二、定理1、 定理：任何AForm（LP）逻辑等值于某一析取范式2、 定理：任何AForm（LP）逻辑等值于某一合取范式三、基本概念1、 概念：公式A的析取范式（合取范式）2、 概念：互补公式（一个公式和它的否定式，称为互补公式）3、 定理：一个析取范式是矛盾式，当且仅当它的每个合取子式含互补的单式 一个合取范式是重言式，当且仅当它的每个析取子式含互补的单式4、 定理：一个公式是矛盾式，当且仅当它的析取范式的每个合取子式含互补的单式一个公式是矛盾式，当且仅当它的析取范式的每个合取子式含互补的单式5、 概念：完全析取范式、完全合取范式四、由公式导出它的析取范式（合取范式）的方法1、 利用逻辑等值关系消去、等符号（等值替换定理）2、 利用逻辑等值关系进行化简第八节 联结符号的完备集一、基本概念1、 概念：fA1An（n元联结符号f，联结公式A1An所构成的公式）2、 性质：对于任何的n1，有2（2n）个不同的n元联结符号二、基本概念1、 概念：完备集（联结符号集称为完备的，当且仅当所有的n元联结符号都能由其中的联结符号定义）2、 定理：，是联结符号的完备集3、 推论：，、，、，是联结符号的完备集4、 概念：称为与非式，即pq |=| （pq）5、 概念：称为或非式，即pq |=| （pq）6、 定理：，是联结符号的完备集第三章 经典一阶逻辑第一节 量词一、基本概念1、 概念：结构（论域个体关系函数）2、 概念：变元（以论域为变化范围的变元，用来构成关于个体的一般性命题或条件）二、基本概念1、 概念：全称量词和存在量词（对于所有（论域中的）个体：存在（论域中的）个体）2、 概念：全称命题和存在命题（对于所有x，都有R（x）：存在x，使得R（x）三、基本概念1、 概念：命题函数（它不是命题，只有将某一个体指派为x的值时，它才成为命题）2、 概念：自由变元、约束变元（命题函数中的变元、被量化的变元）3、 归纳：量词的作用（将n元命题函数逐步转换为命题）四、基本概念1、 性质：论域D是有限集，可以将全称量词和存在量词，分别解释为合取和析取的推广2、 概念：受限制的量词（范围受到限制的量词：范围由原来的论域，限制为论域的某个子集）3、 性质：将受限制的量词，转换成为不受限制的量词（受限制的全称量词：全称量词蕴涵、受限制的存在量词：存在量词合取）4、 概念：一阶逻辑和高阶逻辑（个体变元和个体量词/集的变元和量词）第二节 一阶语言一、基本概念：一阶语言的八类符号1、个体符号：a、b、c2、关系符号：F、G、H（n元关系符号、相等符号（特殊的二元关系符号）3、函数符号：f、g、h（m元函数符号）4、自由变元符号和约束变元符号（u、v、w和x、y、z）5、联结符号（5类联结符号）6、量词符号（全称量词符号、存在量词符号）（量词、全称量词、存在量词）7、标点符号（左括号、右括号和标点）二、基本概念：项1、 概念： tTerm（L），当且仅当它能由（有限次使用）以下的、生成：、a、uTerm（L）（单独一个个体符号是项、单独一个自由变元符号是项）、如果t1，tnTerm（L），并且f是n元函数符号，则f（t1，tn）是项2、 概念：闭项（不含自由变元符号的项）3、 概念：对项的结构作归纳（如何证明Term（L）中所有的元都具有某个性质）三、基本概念：原子公式1、 概念：L的表达式是Atom（L）中的元，当且仅当它有、两种形式之一、F（t1，tn），其中F是n元关系符号，并且t1，tnTerm（L）、（t1，t2）（可以更直观的简写为：t1t2）2、 注意：原子公式不是归纳定义四、基本概念：公式1、 概念：U（s1，sn） 表示符号s1，sn出现在表达式U中2、 概念：AForm（L），当且仅当它能由（有限次使用）以下的生成：、Atom（L）Form（L）、如果AForm（L），则（A）Form（L）、如果A、BForm（L），则（A*B）Form（L）、如果A（u）Form（L），x不在A（u）中出现，则xA（x），xA（x）Form（L）3、 概念：闭公式（语句）（不含自由变元符号的公式）4、 概念：拟公式（与公式结构相似的表达式、拟公式不是公式）5、 概念：对公式的结构作归纳五、定理群11、 定理1：L的任何项恰好具有以下三种形式之一：2、 定理2：如果t是f（t1，tn）的段，则tf（t1，tn）或t是ti的段3、 定理3：L的任何公式恰好具有以下八种形式之一：六、定理群21、 概念：全称公式、存在公式（全称公式：xA（x），存在公式：xA（x）2、 概念：量词的辖域（如果xA（x）是B的段，则称A（x）是x在B中的辖域）3、 性质：量词的辖域是拟公式，联结符号如果出现在量词的辖域中，则可能是拟公式4、 定理1：L的任何公式中任何全称量词或存在量词有唯一的辖域5、 定理2：如果A是xB（x）中的段，则AxB（x）或是xB（x）的段第三节 语义一、基本概念：一阶语言的解释（后面五类符号，在所有一阶语言中都是相同的）1、一阶语言和某个结构有联系（一阶语言是用来描述这个结构的）2、一阶语言和任何结构无联系（一阶语言是一个一般的，抽象的一阶语言）首先需要一个论域（只要求是不空的集合），然后再在该论域中如下解释：、个体符号解释为论域中的个体、n元关系符号解释为论域上的n元关系、m元函数符号解释为论域上的m元全函数3、概念：全函数（处处有定义的函数，函数的运算结果不会跑到论域之外）二、基本概念1、 基本规定、项f（t1，tn）被解释为论域中的个体：（a1，an）、原子公式F（t1，tn）被解释为命题：a1，an有R关系2、 系列结论、闭项和闭公式的解释（分别解释为论域中的个体，或命题）、含自由变元的项，经过解释（得到论域上的n元全函数）和指派，得到论域中的个体、对于一个含自由变元的公式，经过解释（得到命题函数）和指派，得到命题3、 说明、区分：个体符号解释为个体，自由变元符号指派为个体、一次性指派：同时将所有的可数无限多个自由变元符号，指派为论域中的个体三、基本概念1、 概念：一阶语言L的赋值v（包括一个论域D和一个赋值函数v）2、 概念：项的值（L的项在以D为论域的赋值v之下的值，递归定义如下）3、 定理：设v是以D为论域的赋值，并且tTerm（L），则tVD（对项的结构做归纳）四、基本概念1、 概念：定义一个新的赋值v（u/a）：它与原来的v处处相同，只是作用在自由变元符号u时，可能会不同2、 概念：公式的真假值（L的公式在以D为论域的赋值v之下的真假值，递归定义如下）、取u不在A（x）中出现，由A（x）构作A（u）、xA（x）是由A（u）生成的，所以xA（x）V要由A（u）V来决定、xA（x）V1的涵义：无论v指派u为D中的哪一个个体a，都有A（u）V1、对于原来在A（x）中，现在仍在A（u）中的自由变元w来说，wV保持不变归纳：如果v是xA（x）V中的指派，那么v（u/a）表示除此之外，还要给自由变元符号U作指派3、定理：设v是以D为论域的赋值，A是公式，则AV0，1五、基本概念1、 概念：一致的（有相同论域的两个赋值v和v，在四类符号上是一致的）2、 定理：设v和v是有相同论域的两个赋值，并且它们在项t和公式A所含的四类符号上都是一致的，则tVtV，AV=AV六、基本概念1、 概念：V（表示Form（L）中的公式集）2、 概念：是可满足的（存在赋值v，使得V1）3、 概念：AForm（L）是有效的（对于任何赋值v，都有V1）4、 性质：可满足是由命题的内容决定的，而有效性是由公式的逻辑形式决定的5、 性质：不存在一个统一的算法，用来判断L中公式的有效性或者可满足性第四节 逻辑推论一、逻辑推论1、 符号：A（A是的逻辑推论，其中Form（L），AForm（L）2、 概念：A，当且仅当对于任何赋值V，如果V1，则AV13、 概念：|A（存在赋值V，使得V1，AV0）前者是指任何论域上的任何赋值V，后者是指存在以D为论域的赋值V4、 性质：A（则A是有效公式）5、 概念：逻辑等值公式A|B二、例题分析：注意找到捷径和方法1、 如何证明一个逻辑推论是成立的（直接证明或者反证法）2、 如何证明一个逻辑推论是不成立的（构造出这样的赋值V，使得V1，AV0）、性质：当确定赋值的论域时，问题在于论域的大小，和论域中有怎样的个体无关、D上的n元关系F：FV|a1D，anD，且a1，an满足F关系三、定理群1、 引理1：如果A|A并且B|B，则有A|A等7条性质2、 约定：B、C是拟公式，则B|=|C的含义是指B|=|C（注意B、C的形成）3、 等值替换定理：设B|C并且在A中把B的某些出现替换为C而得到A，则A|A（注意：B和C可能是拟公式）4、 对偶性定理：A|A（其中A是A的对偶）第五节 形式推演一、一阶逻辑的形式推演规则1、 新增的形式推演规则（6条）2、 规则的理解和分析、条件和结论的强弱：xA（x）A（t）xA（t）、u不在中出现：u表示的可以是论域中的任何一个个体、区别：t比u的范围更广、代入和替换3、 量词的形式推演规则的推广（只有t系列可以相同，也可以不同，u和x都不行）4、 概念：A（A是在一阶逻辑中，由形式可推演的），当且仅当A能由（有限次使用）一阶逻辑的形式推演规则生成二、定理群11、 定理1（定理3.5.2）、性质：xA（x）|yA（y）（相似性质：xA（x）|yA（y）、性质：xy A（x，y）|yx A（x，y）（相似性质：xyA（x，y）、性质：xA（x）xA（x）、性质：xy A（x，y）yx A（x，y）2、 定理2（定理群，定理3.5.3）、性质：xA（x）|x A（x）、性质：xA（x）|x A（x）三、定理群21、 定理（定理群，定理3.5.4）、性质：xA（x）B（x） xA（x）xB（x）类似性质：xA（x）B（x） xA（x）xB（x）类似性质：xA（x）B（x） ，xB（x）C（x）xA（x）C（x）、性质：Ax B（x）|xAB（x）类似性质：Ax B（x）|xAB（x）、性质：x A（x）B|xAB（x）类似性质：x A（x）B|xAB（x）2、重要思路、当出现在左边，使用xA（x）A（u）（-） 当出现在右边，使用规则（+）、当出现在左边，使用规则（-） 当出现在右边，使用反证法，或者规则（）四、定理群31、 定理1（定理群，定理3.5.5）、性质：Ax B（x）|xAB（x）类似性质：Ax B（x）|xAB（x）、性质：xA（x）B（x） |xA（x）xB（x）类似性质：xA（x）B（x） xA（x）xB（x）、性质：Q1A（x）Q2B（y）|Q1Q2A（x）B（y）2、 定理2（定理群，定理3.5.6）、关键：通过摩根定理，将转化为、最后一条性质：注意充分利用最开始的两条性质3、 定理3（定理群，定理3.5.7）（相对简单）五、两个新的量词关于的两条规则1、 概念：!x A（x）、!x A（x）、分析：利用已有的两个量词定义出新的两个量词、分析：解析公式详细涵义2、 定理：、常规性质：的交换律、的传递律、重要性质：!x A（x）|xA（x），!x A（x）（分析其证明，曾经未能证明）六、等值公式替换和对偶性1、 引理：7条引理（5个常规联结符号2个量词符号）2、 等值公式替换3、 对偶定理第六节 前束范式一、基本概念1、 概念：前束范式（Qx1QxnB，其中B不再有量词）2、 概念：前束词、母式二、定理1、 定理（约束变元符号替换）：将公式A中的xB（x）的某些出现替换为yB（y）2、 定理：L的任何公式与某个前束范式等值（极其重要的8条公式）3、 关键：将公式变换为前束范式的步骤（共三个步骤）第四章 可靠性和完备性第一节 可满足性和有效性一、可满足性和有效性1、 定理：（可满足和有效的相互转换）、性质：A是可满足的，当且仅当A是不有效的、性质：A是有效的，当且仅当A是不可满足的2、 定理（可满足和、有效和的相互转换）、性质：A（u1，un）是可满足的，当且仅当x1xn A（x1，xn）是可满足的、性质：A（u1，un）是有效的，当且仅当x1xn A（x1，xn）是有效的3、 定理（前束范式）、性质：A是可满足的，当且仅当A的前束范式是可满足的、性质：A是有效的，当且仅当A的前束范式是有效的二、在D中的可满足性和有效性1、 定义：在D中的可满足性和有效性、在D中是可满足的（当且仅当有以D为论域的赋值v，使得V1）、A在D中是有效的（当且仅当对于任何以D为论域的赋值v，有AV1）2、 性质：（可满足性变强了，有效性变弱了）、性质：在D中是可满足的是可满足的、性质：A是有效的 A在D中是有效的三、论域变大变小的讨论1、 定理（论域越大越满足，论域越小越有效）设Form（L），AForm（L），和A不含相等符号，D和D1是论域且|D|D1|、在D中是可满足的，则在D1中是可满足的、A在D1中是有效的，则A在D中是有效的2、 定理的证明、符号准备：以D-v构作D1-v1（关键：a对应过去，而b*对应回来）、引理1：以D1-v1构作D-v1*，则项t有这样的性质、引理2：同样以D1-v1构作D-v1*，则公式A有这样的性质3、 重要反例（以证明上述定理不能含有相等符号，否则不成立）第二节 可靠性一、可靠性定理：设Form（L），AForm（L）1、 定理：如果A，则A2、 推论：如果A，则A（若A是形式可证明的，则A是有效的）二、性质1、 性质：A（u）|xA（x）；A（u）|xA（x）2、 推论：A（u）|xA（x）；A（u）|xA（x）三、协调性1、 定义：Form（L）是协调的（当且仅当不存在AForm（L），使得A且|A）2、 可靠性定理的协调性描述：设Form（L），AForm（L）、定理：如果是可满足的，则是协调的、推论：如果A是可满足的，则A是协调的两个定理和两个推论是两两等价的3、 定理：Form（L）是协调的，当且仅当存在A，使得|A第三节 极大协调性一、极大协调性1、 定义：是极大协调的，当且仅当满足于以下的和、是协调的、对于任何A，A不协调）2、 定理：是极大协调的，则对于任何A，A等价于A，|+A等价于A二、封闭于形式推演1、 定义：封闭于形式推演（如果对于任何A，A蕴涵A）2、 定理：设是极大协调的，则封闭于形式推演三、定理1、 定理：如果是极大协调的，则对于任何的A和B、A， 当且仅当A、AB，当且仅当A且B等等2、 Lindenbaum定理：任何协调的公式集能够扩充为极大协调集关键：先由构造0、1、n，再令*01n第四节 命题逻辑的完备性一、命题逻辑完备性的证明之一1、 引理：设AForm（LP）含不同的原子公式p1，pn，构作Ai，那么、AV1A1，AnA、AV0A1，AnA证明：对公式A的结构作归纳2、 定理：设AForm（LP），Form（LP），并且是有限集、如果A，则A、如果A，则A证明：关键在于利用（pnpn）AA二、命题逻辑完备性的证明之二1、 引理：设*是极大协调集，用*构作真假赋值v，使得对于任何的原子公式p pV1当且仅当p*，那么AV1当且仅当A*2、 可靠性定理：设Form（LP），AForm（LP）、如果是协调的，则是可满足的、如果A是协调的，则A是可满足的3、 可靠性定理：设Form（LP），AForm（LP）、定理：如果A，则A、推论：如果A，则A第五节 一阶逻辑的完备性一、存在性质1、 概念：LO（在原先L的基础之上，增加新的可数无限多个自由变元符号）2、 概念：Form（LO），有存在性质（当且仅当对于Form（LO）中的任何存在公式xA（x），如果xA（x），则存在d使得A（d）3、 引理：极大扩充和存在性质（设Form（L）并且是协调集，那么能扩充为极大协调集*Form（LO），并且*有存在性质）证明步骤：由构作n（协调）由n构作O（协调）O扩充为极大协调*二、一阶逻辑的完备性1、 规定、首先：令论域T t | tTerm（LO）、然后：由*构作以T为论域的赋值v2、 引理1：对于任何tTerm（LO），tVtT（对t的结构作归纳）3、 引理2：对于任何ATerm（LO），AV1当且仅当A*（对A的结构作归纳）4、 可靠性定理：设Form（L），AForm（L）、如果是协调的，则是可满足的、如果A是协调的，则A是可满足的5、 可靠性定理：设Form（L），AForm（L）、定理：如果A，则A、推论：如果A，则A三、带相等符号的一阶逻辑的完备性1、 首先：上面由*构作以T为论域的赋值v过程中，在由n元关系符号F确定FV时，如果关系符号是相等符号，则不再适用（即t1t2t1t2*不能保证）2、 解决方案：、在Term（LO）定义二元关系R，t1Rt2t1t2*、依次证明：R是等价关系；用R将Term（LO）划分为等价类；以及构造出T*、由*构作以T*为论域的赋值v、最后分析：这样的处理避免了上面的