《数理逻辑》第七章-4

《数理逻辑》教学大纲徐海燕 编写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年，德国数学家弗雷格出版了《数论的基础》一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。

对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。

从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。

数理逻辑就是精确化、数学化的形式逻辑。

它是现代计算机技术的基础。

数理逻辑的内容两个最基本的也是最重要的组成部分，就是“命题演算”和“谓词演算”。

命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。

命题是指具有具体意义的又能判断它是真还是假的句子。

在谓词演算里，把命题的内部结构分析成具有主词和谓词的逻辑形式，然后研究这样的命题之间的逻辑推理关系。

数理逻辑的发展数理逻辑这门学科建立以后，发展比较迅速，促进它发展的因素也是多方面的。

比如，非欧几何的建立，促使人们去研究非欧几何和欧氏几何的无矛盾性。

数理逻辑教程
数理逻辑是人们认识世界的核心，它不仅是一门科学理论，也是一种基本的思考方法。

近几年，数理逻辑在电脑科学、计算机程序设计、自然语言理解、知识发现等领域均有巨大的应用，成为新兴学科中的重要力量，但由于数理逻辑学习难度大，通常会需要一门教程来帮助学生了解这门学科的基本概念和基本技能。

本书《数理逻辑教程》内容全面，深入浅出，既适合初学者，也适合高手。

在这本教程里，作者从最基础的知识出发，以统一形式完美地介绍了数理逻辑的概念、原理和技术，并以大量有趣的案例加以说明，让读者更全面、更准确地掌握和理解数理逻辑。

首先，本书着重介绍了数理逻辑的基本概念，其中包括了数理逻辑的历史、概念、概述、基本规则、公式解析法及其应用等方面，分析清楚数理逻辑的概念，是进一步学习数理逻辑的基础。

接下来，本书介绍了数理逻辑的语法和语义，帮助读者掌握数理逻辑的基本步骤，明确数理逻辑知识的表示方式，以及如何理解数理逻辑语句的语义；此外，本书还专门介绍了基本的推理技术，包括演绎、归纳和反演等，让读者系统地了解推理技术的基本概念，了解推理过程中所涉及的基本技术，并熟悉推理技术的应用方法。

最后，本书介绍了数理逻辑的一些实践应用，其中以数理逻辑方法展开了对知识发现、自然语言理解、证明技术、规则系统等领域的深入探究，使数理逻辑的技术不仅可以用于学术研究，也可以用于实际应用。

总之，《数理逻辑教程》是一本全面的、系统的数理逻辑学习参考书，适合各类人士阅读和参考。

本书以深入浅出的形式，从数理逻辑的概念到语法分析，再到实践应用，包含了每一个重要的知识点，帮助读者更全面、更深刻地理解和掌握数理逻辑。

数理逻辑课后习题答案数理逻辑课后习题答案数理逻辑是一门研究推理和思维的学科，它涉及到数学和哲学的交叉领域。

在学习数理逻辑的过程中，课后习题是巩固知识和提高能力的重要途径。

本文将为你提供一些数理逻辑课后习题的答案，希望能够帮助你更好地理解和应用这门学科。

1. 逻辑符号的运用习题：将以下自然语言句子转化为逻辑符号表示：a) 如果今天下雨，那么我就带伞。

b) 所有猫都喜欢吃鱼。

c) 除非你努力学习，否则你不会成功。

答案：a) p: 今天下雨q: 我带伞逻辑符号表示：p → qb) p: x是猫q: x喜欢吃鱼逻辑符号表示：∀x(p → q)c) p: 你努力学习q: 你成功逻辑符号表示：p → q2. 命题逻辑推理习题：使用命题逻辑进行推理，判断以下论断是否成立：a) 如果今天是周末，那么我会去看电影。

今天是周末，所以我会去看电影。

b) 如果这只猫是黑色的，那么它是一只黑猫。

这只猫是黑色的，所以它是一只黑猫。

答案：a) 论断成立。

根据前提条件，今天是周末，可以推出结论我会去看电影。

b) 论断不成立。

虽然前提条件是这只猫是黑色的，但不能推出结论它是一只黑猫，因为黑色的猫不一定全身都是黑色的。

3. 谓词逻辑推理习题：使用谓词逻辑进行推理，判断以下论断是否成立：a) 所有猫都喜欢吃鱼。

汤姆是一只猫，所以汤姆喜欢吃鱼。

b) 所有学生都喜欢音乐。

小明是学生，所以小明喜欢音乐。

答案：a) 论断成立。

根据前提条件，所有猫都喜欢吃鱼，可以推出结论汤姆喜欢吃鱼。

b) 论断成立。

根据前提条件，所有学生都喜欢音乐，可以推出结论小明喜欢音乐。

4. 范式化和归结习题：使用范式化和归结法解决以下逻辑问题：a) 给定前提条件：p → q, ¬q → r, ¬r。

证明结论：¬p。

答案：首先，根据前提条件，我们可以得到以下逻辑式：1. p → q2. ¬q → r3. ¬r然后，我们可以将逻辑式1和3应用范式化规则，得到新的逻辑式：4. ¬p → ¬q接下来，我们将逻辑式4和逻辑式2应用归结规则，得到新的逻辑式：5. ¬p → r最后，我们将逻辑式5和前提条件的逻辑式3应用归结规则，得到最终的结论：6. ¬p通过范式化和归结法，我们证明了结论¬p成立。

数理逻辑大纲数理逻辑-大纲数理逻辑一、表明(一)课程性质《数理逻辑》就是数学与应用领域数学专业的方向课外。

数理逻辑又称符号逻辑、理论逻辑，就是数学的一个分支，它就是使用数学的方法去研究推理小说的形式结构和推理小说规律的数学学科，数理逻辑研究的中心问题就是推理小说。

所谓数学方法就是指数学使用的通常方法，包含采用符号和公式，尚无的数学成果和方法，特别就是采用形式的公理方法。

用数学的方法研究逻辑的系统思想通常追溯到莱布尼茨，他指出经典的传统逻辑必须改建和发展，并使之更为准确和易于编程语言。

总的来说，数理逻辑就是精确化、数学化的形式逻辑，它就是现代计算机技术的基础。

(二)教学目的本课程的教学应当使学生熟练掌握有关命题逻辑、一阶谓词逻辑的基本知识，认知并能够初步运用公理化的逻辑推理和数学证明，训练学生的逻辑思维方式，提升其数学解题能力。

(三)教学内容及学时数本课程主要讲授命题逻辑的基本概念，命题逻辑的等值和推理小说编程语言，谓词逻辑的基本概念，谓词逻辑的等值和推理小说理论等内容，总计30学时。

序号1234内容命题逻辑的基本概念命题逻辑的等值和推理小说编程语言谓词逻辑的基本概念谓词逻辑的等值和推理小说理论合计学时数（30）课堂学时数676625课堂教学学时数03025(四)教学方式数理逻辑是一门理论性课程，主要采用讲授法、研究探索法授课，讲授数理逻辑的内容时建议采用多媒体教学。

(五)考核建议1.考核的方式及成绩评定本课程的考核方式通常使用笔试，成绩测评100Elo，其中平时成绩占到50%，期末考试成绩占到50%，其中平时变成按数学系课堂“五个环节”评分细则展开测评。

2.考题设计(1)考题设计原则：考题要全面，符合大纲要求，同时要做到体现重点，题量适度，难度适中，题量和难度的梯度按照教学的三个不同层次，并能够反映出数理逻辑的思想方法、解决基本问题能力的知识点来安排，不过分强调综合。

(2)考题难度比例：基础知识（或基本概念）约35%、根据学生实际水平确认中等难度知识点约50%，稍存有难度知识点15%范围以内。

第七章一阶谓词演算*将一阶谓词逻辑公理化和形式化,其结果就是一阶谓词演算.*一阶谓词演算包括命题逻辑作为它的子系统.7.1 一阶谓词演算的公理系统(一) 初始符号:(甲) 变项:(1) 命题变项: 小写拉丁字母p, q, r, s, p1, q1, r1, s1, p2, …(2) 个体变项: 小写拉丁字母u, v, w, x, y, z, u1, v1, …(3) 谓词变项: 大写拉丁字母F, G, H, P, Q, R, S, F1, G1, …(乙) 常项(1) 命题联结词: ┐(并非);∨(或者).(2) 量词: ∀(全称); ∃(存在).(丙) 括号和逗号: 左括号“(”; 右括号“)”; 逗号“,”. *在讨论一阶谓词演算时,我们将使用以下的语法符号:(1) 小写希腊字母π, 代表任一命题变项.(2) 大写希腊字母Δ, 代表任一个体变项.(3) 大写希腊字母Γ, 代表任一谓词变项.(4) 大写拉丁字母X,Y,Z, 代表任一符号序列.(5) 大写拉丁字母A,B,C,D,E, 代表任一合式公式.(二) 形成规则:(1) 一命题变项π是一合式公式;(2) 一谓词变项Γ后继有写在一对括号内并用逗号分开的适当数目的个体变项是一合式公式;例: P(x), R(x,y), S(x,y,z)等.(3) 如X是合式公式, 则┐X是合式公式;例: ┐p, ┐P(x), ┐S(x,y,z), ┐(p∨P(x,y))(4) 如X和Y是合式公式, 并且无一个体变项Δ,此Δ在二者之一中是约束的, 但在另一个中是自由的, 则(X∨Y)是合式公式;例: (∀xP(x)∨R(y,z)), (P(x)∨F(x))是合式公式,但(∀xP(x)∨R(x,y))不是.(5) 如X为一合式公式, 并且Δ在其中是自由的, 则∀xX和∃xX为合式公式.例: ∀xR(x,y), ∃x(p∨G(x)) 是合式公式.(6) 只有适合以上各条的是合式公式.*根据以上定义,∀xF(x)∨G(x), ∀x(∃xF(x)∨G(x)),∀xF(y), ∀x∀xR(x,x)都不是合式公式.(三) 定义(甲) (A→B)定义为(┐A∨B)(乙) (A∧B)定义为┐(┐A∨┐B)(丙) (A↔B)定义为(A→B)∧(B→A)(四) 公理(1) ├((p∨p)→p)(2) ├(p→(p∨q))(3) ├((p∨q)→(q∨p))(4) ├((q→r)→((p∨q)→(p∨r)))(5) ├(∀xF(x)→F(y))(6) ├(F(y)→∃xF(x))*∀xF(x)→F(y)表示: 如果一切个体都是F, 则某个特定个体也是F. 例如:从∀x(x是发展变化的)可以推出数理逻辑是发展变化的.这是一种从一般到个别的推理形式. 其中y可以是个体域中任一个体.* F(y)→∃xF(x)表示: 如果某个特定y是F, 则存在一个个体x 是F. 例如:从2是偶素数推出∃x(x是偶素数).这是从个别到存在的推理. 其中y是个体域中某一个个体即可.*公理都是普遍有效式.(五) 变形规则:*谓词演算有三种变项: 命题变项, 个体变项和谓词变项. 因而有三种代入规则. 对于代入规则, 我们有两个根本要求:(1) 对一合式公式, 作代入的结果仍是一个合式公式;(2) 从普遍有效式出发, 代入的结果, 必须还是普遍有效式.1.命题变项代入规则:在公式A中出现的命题变项π可由一公式B代入, 代入必π. 规则是: 须在π出现的一切位置上进行. 代入结果记作ABπ.如果├A , 则├AB对B的要求:(i) 如果Δ在A中为自由变项, 则B不的含有约束变项Δ; (ii) 如果Δ在A中为约束变项, 则B不得含有自由变项Δ; (iii) 如果Δ在A中为约束变项且π又在∀Δ或∃Δ的辖域中,则B中不得有约束变项Δ.例子:(1) p→p∨F(x)中, 用∀xG(x)代p, 得∀xG(x)→∀xG(x)∨F(x)结果不合式, 违反第(i)条.(2) ∀x(F(x)∨p)→∀xF(x)∨p, 用G(x)代p, 得∀x(F(x)∨G(x))→∀xF(x)∨G(x)结果不合式, 违反第(ii)条.(3)∀x(F(x)∨p)→∀xF(x)∨p 中, 用∀xG(x)代p, 得 ∀x(F(x)∨∀xG(x))→∀xF(x)∨∀xG(x)结果不合式, 违反第(iii)条.*给出正确的代入方法2. 自由个体变项代入规则一公式A 中的自由个体变项Δ1, 可由另一个体变项Δ2代入. 代入必须在Δ1出现的一切位置上进行. 代入结果可记为 A 21∆∆ . 规则是如果 ├ A, 则 ├ A 21∆∆对代入的要求是Δ2在A 中不作为约束变项出现.例子:(1) 在∀xF(x)→F(y) 中以x 代y, 得 ∀xF(x)→F(x)不是合式公式, 违反要求.(2) 违反要求, 代入结果失去普遍有效性的例子.∀x ∃yR(x,y)→∃yR(z,y) 是普遍有效的以y 代z, 得∀x ∃yR(x,y)→∃yR(y,y)则不是普遍有效的. 例如:∀x ∃y(x < y)→∃y(y < y) 为假.*给出正确代入的方法3. 谓词变项代入规则:一公式A 中的n 元谓词变项Γ(Δ1,Δ2,…,Δn )可以处处代之以一复合谓词B(Δ1,Δ2,…,Δn ,Δn+1,Δn+2,…,Δn+m ) (m ≥0). 代入的结果可以记为A ),,,,,,(),,,(12121m n n n n B ++∆∆∆∆∆∆∆∆Γ规则是:如果 ├ A, 则├ A ),,,,,,(),,,(12121m n n n n B ++∆∆∆∆∆∆∆∆Γ谓词代入必须满足以下要求:(i) 代入结果必须是合式的;(ii) A 中的自由个体变项,在代入后不得为B 中的量词所约束; (iii) 如果m > 0, B(Δ1,Δ2,…,Δn ,Δn+1,…,Δn+m )中的变项 Δn+1,…,Δn+m 等在代入后不得为A 中原有的量词所约束. *正确代入的例子例1: ∀xF(x)→F(y)用R(Δ,y)代入F(Δ), 得∀xR(x,y)→R(y,y) 例2: ∃x ∀yR(x,y)→∀y ∃xR(x,y)用S(Δ2,Δ1,z)代入R(Δ1,Δ2), 得∃x ∀yS(y,x,z)→∀y ∃xS(y,x,z)例3: ∀xF(x)→F(y)用(F(Δ)→G(Δ))代入F(Δ), 得∀x(F(x)→G(x))→(F(y)→G(y))*不正确代入的例子例4: ∀xF(x)→F(y) 中用∃yR(Δ,y)代入F(Δ)得∀x∃yR(x,y)→∃yR(y,y)由普遍有效式变成非普遍有效式. 违反规则(ii).例5: ∀xF(x)→∀x(F(y)∧(H(x)∨┐H(x)))用R(x,Δ)代F(Δ), 得∀xR(x,x)→∀x(R(x,y)∧(H(x)∨┐H(x)))等值于∀xR(x,x)→∀xR(x,y), 代入结果不普遍有效. 违反了第(iii)条要求.*正确的代入方法4. 分离规则:从├ A 和├A→B, 可得├ B .5. 后件概括规则:如果Δ在A中不出现, 从├A→B(Δ)可得├A→∀ΔB(Δ)*解释: 相当于├(p→q)∧(p→r)→(p→q∧r)6. 前件存在规则:如果Δ在B中不出现, 从├A(Δ)→B 可得├∃ΔA(Δ)→B*解释: 相当于├ (p→r)∧(q→r)→(p∨q→r) 7. 约束个体变项易字规则:公式A中的一约束个体变项Δ1,可由另一个个体变项Δ2替换. 替换必须在一特定量词及其辖域内到处实现. 如Δ1在多个量词内出现, 替换可以只在一个量词及其辖域内进行. 要求:(i) Δ2在A中不能作自由变项出现;(ii) 如Δ2在A中约束, 则被替换的Δ1不能在Δ2的辖域中出现.*正确替换的例子例1: ∀x(F(x)∧G(x))→∀xF(x)∧∀xG(x)替换成∀x(F(x)∧G(x))→∀yF(y)∧∀xG(x)例2: ∀xF(x)→∃yF(y)替换成∀xF(x)→∃xF(x)*错误替换的例子:例3: ∀xF(x)→F(y)替换成∀yF(y)→F(y) , 不是合式公式, 违反要求(i).例4: ∀x(F(x)∧∃yG(y))→∀xF(x)∧∃yG(y)替换成∀x(F(x)∧∃xG(x))→∀xF(x)∧∃yG(y)∀x(F(x)∧∃xG(x))不是合式公式, 违反要求(ii).7.2 定理推演*命题演算是谓词演算的一个子系统. 命题演算的定理也都是谓词演算的定理.*命题演算的推演规则:(1)从├A∨B, 可得├B∨A(2)从├B→C,可得├A∨B→A∨C(3)从├A→B和├B→C, 可得├A→C(4)从├A→B,可得├┐B→┐A(5)基本置换定理: 设├A↔B, 并且以B置换φ(A)中的A得到φ(B), 则可得├φ(A)↔φ(B).(6)从├A→B和├B→A,可得├A↔B(7) 求否定规则(8) 对偶规则其中(1), (2), (3), (4), (6)可在谓词逻辑演算中直接使用.*第(5),(7),(8)条规则不能简单地推广.*以下证明谓词演算的定理定理101: ├∀x(F(x)∨┐F(x)) (排中律)证明:(1) ├p∨┐p 定理p(2) ├F(x)∨┐F(x) 代入(x)F(3) ├q→(p→q) 定理(4) ├(F(x)∨┐F(x))→((p∨┐p)→(F(x)∨┐F(x)))代入pp p x F x F q ⌝∨⌝∨,)()( (5) ├ (p ∨┐p)→(F(x)∨┐F(x)) (2), (4)分离(6) ├ (p ∨┐p)→∀x(F(x)∨┐F(x)) 后件概括(7) ├ ∀x(F(x)∨┐F(x)) (1), (6)分离推演规则101: 概括规则 从├ A(x), 其中x 自由出现, 可得 ├ ∀xA(x)证明: 设 ├ A(x) 已证, 且x 在其中自由出现. 据定理 ├ q →(p →q), 用代入可得├ A(x)→(p ∨┐p →A(x))├ p ∨┐p →A(x) 分离├ p ∨┐p →∀xA(x) 后件概括├ ∀xA(x) 分离*解释定理102: ├∀xF(x)→∃xF(x) (全称蕴涵存在) 证明:(1) ├ ∀xF(x)→F(y) 公理(2) ├ F(y)→∃xF(x) 公理(3) ├ ∀xF(x)→∃xF(x) 三段论定理103: ├ ∀x(F(x)∧G(x))→∀xF(x)∧∀xG(x) *全称量词对合取的分配律证明:(1) ├ ∀xF(x)→F(y) 公理(2) ├ ∀x(F(x)∧G(x))→F(y)∧G(y) 代入)()()(∆∧∆∆G F F(3) ├ F(y)∧G(y)→F(y) 定理├p ∧q →p,代入 (4) ├ ∀x(F(x)∧G(x))→F(y)(2),(3)三段论 (5) ├ ∀x(F(x)∧G(x))→∀yF(y) 后件概括 (6) ├∀x(F(x)∧G(x))→∀xF(x)变项易字(7) ├ F(y)∧G(y)→G(y) ├p ∧q →q,代入 (8) ├ ∀x(F(x)∧G(x))→G(y)(2),(7)三段论 (9) ├∀x(F(x)∧G(x))→∀yG(y)后件概括 (10) ├ ∀x(F(x)∧G(x))→∀xG(x)变项易字(11) ├∀x(F(x)∧G(x))→∀xF(x)∧∀xG(x)├ (p →q)∧(p →r)→(p →q ∧r),代入和分离 定理104: ├∀xF(x)∧∀xG(x)→∀x(F(x)∧G(x))*全称量词对合取的分配律 证明: (1) ├ ∀xF(x)→F(y)公理 (2) ├ ∀xG(x)→G(y)谓词代入(3) ├∀xF(x)∧∀xG(x)→F(y)∧G(y)├ (p →q)∧(r →s)→(p ∧r →q ∧s),代入,分离 (4) ├ ∀xF(x)∧∀xG(x)→∀y(F(y)∧G(y)) 后件概括 (5) ├∀xF(x)∧∀xG(x)→∀x(F(x)∧G(x))变项易字定理105: ├∀x(F(x)∧G(x))↔∀xF(x)∧∀xG(x) 证明: 由定理103, 104和等值构成规则可得.定理106: ├ ∀x(F(x)→G(x))→(∀xF(x)→∀xG(x))*全称量词对蕴涵的分配, 逆命题不成立. 当∀xF(x)和∀xG(x)为假,∀xF(x)→∀xG(x)为真,但∀x(F(x)→G(x))可能为假.证明: (1) ├ ∀xF(x)→F(y)公理(2) ├∀x(F(x)→G(x))→(F(y)→G(y))谓词代入)()()(∆→∆∆G F F(3) ├ F(y)→(∀x(F(x)→G(x))→G(y)) (2)条件互易 (4) ├ ∀xF(x)→(∀x(F(x)→G(x))→G(y)) (1),(3)三段论(5) ├ ∀xF(x)∧∀x(F(x)→G(x))→G(y)(4)条件合取 (6) ├ ∀xF(x)∧∀x(F(x)→G(x))→∀yG(y) (5)后件概括 (7) ├ ∀xF(x)∧∀x(F(x)→G(x))→∀xG(x)变项易字(8) ├∀x(F(x)→G(x))→(∀xF(x)→∀xG(x))├ (p ∧q →r)→(q →(p →r))代入,分离定理107: ├ ∀x(F(x)↔G(x))→(∀xF(x)↔∀xG(x))定理108: ├ ∀xF(x)∨∀xG(x)→∀x(F(x)∨G(x))作业:1. 给出定理107, 108的证明.2. 判断以下代入是否正确.(1)已知:├∀x(F(x)→p)→(∃xF(x)→∀x(p∧(H(x)∨┐H(x)))) 用F(x)代p, 得├∀x(F(x)→F(x))→(∃xF(x)→∀x(F(x)∧(H(x)∨┐H(x)))) (2)已知: ├F(x)→F(x)∨∀yG(y)用R(Δ,y)代F(Δ), 得├R(x,y)→R(x,y)∨∀yG(y)(3)已知: ├∀xF(x)→∀x(F(y)∧(H(x)∨┐H(x)))用R(x,Δ)代F(Δ), 得├∀xR(x,x)→∀x(R(x,y)∧(H(x)∨┐H(x)))。