人工智能逻辑 课件 刘奋荣 第1-7章 引论 -偏好逻辑

第1章引论1.1人工智能与人工智能逻辑1.2推理形式：演绎、归纳、类比与溯因1.3人工智能的发展径路和目标1.4篇章结构和特色学习目标理解人工智能的起源与图灵测试掌握四种基本推理形式了解人工智能的发展路径把握本书的整体结构1.1人工智能与人工智能逻辑本节将介绍：人工智能的诞生图灵测试的核心思想人工智能逻辑的内涵逻辑推理在AI中的地位人工智能的诞生历史起点"人工智能"(ArtificialIntelligence,AI)一词最早于1956年在达特茅斯会议上被正式提出。会议组织者麦卡锡(McCarthy)明斯基(Minsky)罗切斯特(Rochester)香农(Shannon)学科定位该学科旨在通过计算技术和手段模拟人类的智能。图灵测试的提出核心问题图灵在《计算机器与智能》(Turing,1950)开篇提出："机器能思考吗？"图灵的洞察这一问题本身既模糊又难以界定，因此转而提出一个更具操作性的替代方案——图灵测试。模仿游戏的设定三方参与者1.裁判（人类）2.人类被试3.机器游戏规则裁判通过文本介质与人类和机器分别交流裁判事先不知道哪一方是机器机器的目标：生成与人类回答难以区分的回应裁判的任务：判断哪一方是人类，哪一方是机器测试标准：如果裁判无法可靠地区分两者，那么该机器即被视为通过了测试，展现出某种形式的人工智能。图灵测试的意义方法论转变将对智能这一概念的讨论从抽象定义的争论引导至基于可观察行为的实际评估。新的智能定义智能被界定为能够令人信服地模仿人类反应的能力。达特茅斯会议提案的观点(McCarthyetal.,1956)"学习的每个方面，或智能的其他任何特征，原则上都可以被精确描述，从而用机器进行模拟。"模拟智能的技术途径核心问题如何模仿或模拟智能的某个或某些特征？技术方法计算机科学和人工智能领域开发了多种技术方法：基于规则的推理与专家系统机器学习模型（近年来广泛应用）共同目标在特定任务中模拟智能的某些关键特征。人工智能逻辑的内涵本书主题以"人工智能逻辑"为题，核心聚焦逻辑推理，系统介绍多种与人工智能密切相关的逻辑系统。概念辨析"人工智能逻辑"作为一个逻辑学分支，其内涵不同于：命题逻辑（关注命题之间的逻辑关系）模态逻辑（研究"必然""可能"等模态词）人工智能逻辑的定位统摄性概念"人工智能逻辑"是一个统摄性概念，用以指称一类与人工智能密切相关的逻辑系统。包含内容作为理论基础的经典逻辑在人工智能发展推动下不断演进的新型逻辑理论类比概念类似于"哲学逻辑"——同样作为统摄性概念，指称与哲学议题紧密相关的逻辑系统。逻辑推理与智能逻辑推理的核心地位逻辑推理能力是智能的核心体现之一：表现为对知识的理解与组织体现在面对复杂环境时进行判断与决策的能力逻辑学的深度参与自人工智能诞生之初，逻辑学便深度参与其中，构成了该领域的重要理论基础。符号主义人工智能早期发展路径人工智能早期的发展以符号主义(symbolism)为主导。核心特征依赖形式语言进行知识表示与推理试图模拟人类的理性思维和推理过程代表性成果专家系统语义网这些成果构建了逻辑推理与知识表示的基本框架。当代AI的挑战与机遇技术转向随着机器学习技术的发展，人工智能逐步转向基于统计学习方法的路径。大语言模型的影响大语言模型(LargeLanguageModels,LLMs)的兴起：突破性进展：模式识别与自然语言处理暴露的问题：逻辑结构薄弱、推理能力有限当前挑战如何将逻辑推理能力有效融入以LLMs为代表的当代AI系统，已成为重要挑战与关键机遇。1.2推理形式：演绎、归纳、类比与溯因本节内容四种基本推理形式各推理形式的特征推理与人工智能的联系因果推理简介推理在AI中的作用基础作用在AI领域，逻辑推理在问题解决和决策制定中起着关键的基础作用。四种推理形式根据特征，推理被分为四种不同的形式：演绎推理(Deduction)归纳推理(Induction)类比推理(Analogy)溯因推理(Abduction)共同特点这些推理形式作为从给定信息推导结论的基础机制，每种方法都有其独特的操作方式。演绎推理的定义推理方向演绎推理从一般前提或已知事实出发，将其应用于具体实例，得出逻辑上可靠的结论。逻辑保证如果前提为真，且推理有效，那么结论也必定为真。演绎推理示例例1（演绎）所有哺乳动物都有脊柱。鲸鱼是哺乳动物。因此，鲸鱼有脊柱。分析普遍性原则："所有哺乳动物都有脊柱"具体实例："鲸鱼是哺乳动物"结论："鲸鱼有脊柱"演绎推理的历史古希腊的贡献演绎推理的研究源于古希腊时期，亚里士多德常被认为是提出演绎推理理论的第一人。三段论理论在著作《前分析篇》(Aristotle,1938)中给出了三段论理论，奠定了演绎推理形式化研究的基础。逻辑学的关注点逻辑学理论关注的是推理的模式，而不是具体的内容。三段论的形式例2（演绎）所有的人皆有死。苏格拉底是人。因此，苏格拉底有死。与例1的关系例1和例2拥有同样的推理模式，都是标准的三段论形式。谓词逻辑的发展19世纪末至20世纪初的推动者弗雷格(Frege)罗素(Russell)一阶谓词逻辑的扩展将推理的对象从命题扩展到：对个体的性质个体之间的任意元关系涉及量词的推理结构发展动力源于对数学基础问题的关注，因此也被称为数理逻辑。谓词逻辑的贡献形式化符号体系谓词逻辑引入了一套系统而形式化的符号体系，使得具体领域的知识可以被精确表达。自动定理证明在基于谓词逻辑发展出的众多技术中，自动定理证明是一项重要成果：已成为数学、计算机科学和人工智能中的核心研究课题知识表示与推理当某一领域的知识能够以形式化方式表示（知识表示）后，便可在此基础上推导出新的结论。演绎逻辑的扩展随着AI发展的演进研究者不断提出对传统演绎逻辑的扩展与改进。描述逻辑发展出了广泛应用于知识表示与本体建模的描述逻辑。本书安排将在第一部分对这些逻辑加以介绍与讨论。归纳推理的定义推理方向归纳推理从具体的观察或证据出发，推导出更一般的规律或理论。例3（归纳）到目前为止，太阳每天早晨都从东方升起。今天太阳也从东方升起。因此，可以推出明天太阳仍将从东方升起。分析基于重复的具体观察，我们可以归纳出太阳升起方向的一般规律。归纳推理的局限性不能确保结论正确归纳并不能确保结论的正确性。经典例子：黑天鹅例4（归纳）在较长一段时间内，欧洲人所观察到的天鹅都是白色的从而得出结论："所有的天鹅都是白的"然而，18世纪末探险者在澳大利亚首次发现了黑天鹅这一观察立即成为该命题的反例归纳推理的根本局限关键认识这个例子清晰地揭示了归纳推理的一个根本局限：即使存在大量正面实例，也无法保证结论的必然正确。一个反例的威力一个反例的出现，便足以推翻归纳所形成的普遍命题。归纳的价值尽管如此，归纳推理在我们的认知与科学探索中仍发挥着不可或缺的作用——我们需要通过观察总结出一般性规律，并在反例出现时及时修正原有判断。归纳推理的研究历史培根的贡献培根(Bacon)通常被认为是近代对归纳推理进行系统讨论的先驱人物。《新工具论》(NovumOrganum)提出了新的科学探究方法与亚里士多德的《工具论》形成对比主张以经验观察和系统实验为科学知识的基础将归纳视为从具体实例中推导一般原则的核心方法休谟的归纳问题批判性审视休谟对归纳推理进行了批判性审视，提出了著名的归纳问题：如何通过过去的经验证明归纳推理的合理性？引发的探讨这一挑战促使哲学家们展开了持续的探讨：概率论视角(Carnap,1950)：归纳推理可以通过概率确认加以支持实用主义视角(Popper,1972)：试图证明归纳推理在科学中的有效性归纳推理的性质研究形式学习理论由于归纳推理无法确保结论的绝对正确性，研究这一推理过程的性质成为重要课题。研究问题形式学习理论探讨：在何种条件下，从证据中学习能够逐步趋向于真理。参见Schulte(2024)和Lin(2024)。归纳推理与机器学习机器学习的本质基于大数据的机器学习本质上是一种归纳推理。核心算法目标从大量实例中识别出一般性模式，并据此对未来情形进行预测。相互促进归纳推理的研究为当代机器学习提供了重要的理论支撑人工智能的实践也为归纳推理提供了丰富而具体的分析素材类比推理的特点推理方向对比演绎推理是从一般规律推出具体实例归纳推理则是从具体实例总结出普遍规律类比推理则是从一个具体实例推断另一个具体实例常见性这种推理在科学探索和日常认知中都极为常见。类比推理的原理不建立普遍命题类比推理并不试图建立普遍命题，而是从已知的个案出发，推断另一个个案可能具有某些相似特征。依赖结构相似性类比推理依赖于对象或情境之间的结构相似性，通过识别这种结构上的对应关系，从已知对象的属性推测未知对象可能具备的属性。类比推理的形式一般形式与在属性上相似具有属性因此，也可能具有属性特点不同于演绎推理的严格有效性有别于归纳推理对统计模式的依赖更侧重于本质属性和结构的相似，而非表面类似类比推理示例例5（类比）地球是一颗拥有生命、液态水和磁场的行星火星也存在液态水的痕迹、磁场的残余，并在地质构造上与地球相似因此，火星可能也存在某种形式的生命分析这个推理依据地球与火星这两个具体对象之间的相似关系，提出一种合理猜测。注意：这类推理的结论并非必然成立。类比推理的研究与应用研究领域类比推理在逻辑学与认知科学中已有广泛研究，并至今仍是一个活跃的领域。在AI中的应用类比推理在人工智能中发挥着越来越重要的作用：迁移学习案例推理系统(Case-BasedReasoning,CBR)结构匹配模型案例推理系统CBR系统的工作原理在面对新问题时：检索历史案例中结构相似的问题及其解决方案适配以应对当前情境应用领域法律推理医学诊断技术支持系统体现的核心特征将已知案例的知识迁移到新情境中进行推断与决策。溯因推理的提出皮尔士的贡献皮尔士(Peirce)在《理论的架构》(Peirce,1903)中正式引入了溯因推理的概念。定义将其描述为一种形成解释性假设的过程。核心方法在多个竞争性假设中，选择最可能或最简单解释的方法。别称这一过程通常被称为"推理到最好的解释"。溯因推理的应用广泛应用领域实验科学对实验观察结果进行最优解释的推断过程。诊断过程根据症状推断最可能的病因或故障原因。日常决策在不完全信息下选择最合理的行动方案。溯因推理示例例6（溯因）你醒来发现街道是湿的。利用溯因推理，你想到可能的解释有：(a)昨晚下雨了(b)有街道清洁车经过(c)有人手动洒水在这些可能的解释中，你认为下雨是最可能的也是最简单的原因。溯因推理的特点根据证据选择解释溯因推理根据现有的证据选择最可能的解释，即使其他解释也存在。允许修正结论溯因推理显然是允许修正推理结论的。动态调整示例在例6中：观察到新证据："屋顶是干的"与之前结论相矛盾得出新结论：很可能是街道清洁车经过了这种动态变化在溯因推理中是非常普遍的。溯因推理在科学中的应用科学研究的常用形式溯因推理是科学研究常用的一种推理形式。科学研究的特点需要对观察到的实验证据进行解释给出的解释可能会随着新证据的出现而被抛弃在AI中的关注近年来，溯因推理在人工智能领域获得了更多关注，因为我们常常需要从不完全数据中生成合理的解释。参见Aliseda(2006)。推理形式的综合作用四种推理的共同构成演绎、归纳、类比与溯因共同构成了人工智能中逻辑推理的核心。AI任务的本质无论人工智能的任务是：基于已有知识进行推演从数据中学习一般模式生成对行为和决策的解释本质上都依赖于上述推理模式的组合与运用。演绎推理在AI中的应用推理特点从已知的规则和前提出发，推导出必然成立的结论。基础地位是知识表示与自动推理系统的基础。传统应用在专家系统等传统AI应用中得到广泛实践。归纳推理在AI中的应用核心机制通过从具体实例中总结普遍规律。理论支撑为机器学习和数据驱动的预测提供了理论支撑。类比推理在AI中的应用核心机制是迁移学习与案例推理系统的核心机制。功能能够将已有知识灵活应用于新情境中，支持跨任务的知识迁移。溯因推理在AI中的应用聚焦点聚焦于寻找最可能的原因或解释。重要价值在诊断问题和规划任务中具有重要价值。因果推理简介因果关系的重要性识别事物之间的因果关系不仅是科学探究的核心目标之一，也是人类理解世界结构的重要方式。因果关系与相关性的区别与纯粹的相关性不同，因果关系要求在事件之间确立一种：方向性的联系机制性的联系不仅观察到两个事件"在一起"，还需解释它们"为什么"在一起。因果推理的实践意义关键意义在实践中，区分因果与相关性对于以下方面具有关键意义：预测干预决策AI研究方向近年来，因果推理成为人工智能研究中的一个重要方向。因果推理的理论框架珀尔的因果图模型珀尔(Pearl)等提出了以因果图模型为基础的因果推理框架：表达复杂变量之间的因果结构通过干预等形式进行因果推断刘易斯的反事实条件句在逻辑学文献中，刘易斯(D.Lewis)的反事实条件句也在研究因果推理中发挥重要作用。即在某一事件未发生的情况下，推断另一事件是否仍会发生。本书安排将在第三部分继续对概率推理和因果推理做详细讨论。1.3人工智能的发展径路和目标本节内容符号主义与联结主义两种径路的特点与局限AI的融合发展趋势灵活性与策略性推理AI的两种发展径路基本认识到目前为止，一般认为人工智能的发展具有两种径路：符号主义(Symbolism)依赖逻辑学和基于规则的推理系统来模拟人类智能。联结主义(Connectionism)以人工神经网络为核心，模拟人脑的学习方式。符号主义人工智能核心特征符号主义人工智能依赖逻辑学和基于规则的推理系统来模拟人类智能。基本假设知识可以通过符号语言表示，并通过逻辑推理进行有效的推导。强调重点这种方法强调可解释性。常用领域数学证明法律推理专家系统符号主义的优势与局限核心优势严密的逻辑体系具有高度可解释性，推理过程透明，结论可追溯。主要局限难以处理非结构化数据缺乏从经验中学习的能力联结主义人工智能核心技术联结主义以人工神经网络为核心。模拟对象模拟人脑的学习方式，从大规模数据中提取模式。采用技术采用深度学习等技术。突破领域语音识别计算机视觉自然语言处理联结主义的优势与局限核心优势强大的学习能力能够从海量数据中自动提取特征，在复杂任务中表现卓越。主要局限"黑箱"特性使得推理过程难以解释高度依赖海量数据和计算资源两种范式的并行演进历史进程在人工智能的发展历史中，符号主义与联结主义两大路径始终并行演进。动态关系虽然在不同阶段各自的影响力有所侧重，但两者从未完全割裂，而是不断相互借鉴、交融。当前的融合趋势前沿研究方向当前，AI前沿研究正致力于融合这两种范式。融合目标试图结合：符号主义的可解释性与逻辑推理能力联结主义的数据驱动学习优势从而实现更全面、更灵活的智能行为。LLMs的逻辑推理增强融合方向的体现近几年来针对大语言模型逻辑推理能力的增强，也体现了这一融合方向的努力。具体探索有研究尝试将外部知识图谱或符号规则系统引入LLMs，以提升其推理的准确性与稳定性。意义这些探索不仅拓展了语言模型的能力边界，也预示着未来人工智能系统将更加注重逻辑。AI的最终目标核心目标无论人工智能采用何种技术路径，其最终目标始终是实现"智能"本身。智能的重要特征灵活性研究的意义研究人类自身的决策机制与策略性推理过程，建立对这些推理规律的形式刻画，对于人工智能模拟人类智能具有重要意义。人类的推理机制面对不确定性当我们面临不确定性时，往往会：基于已有信息形成信念据此进行判断与行动对未来进行预测动态调整能力当预测结果与现实出现偏差时，我们能够：及时修正原有结论不断优化自身认知智能的关键基础核心能力正是这种动态的、可自我调整的推理能力，构成了智能的关键基础。研究聚焦自20世纪80年代以来，相关研究逐渐聚焦于：如何形式化地刻画主体自身的认知机制与推理能力并发展出一系列新的逻辑系统认知逻辑的应用前景本书安排将在第二部分对这些逻辑进行详细介绍。适用场景特别适用于模拟具有交互能力和认知调节能力的智能体。应用领域在以下领域具有广泛应用前景：机器人设计人机交互全书结构概览全书分为三个部分：第一部分知识表示和推理第二部分智能体及其交互第三部分机器学习与推理第一部分：知识表示和推理主要内容重点介绍命题逻辑、谓词逻辑和描述逻辑，它们是知识表示与推理中最为重要的逻辑系统。各逻辑的作用命题逻辑关注如何表示和推理关于事实的信息谓词逻辑用于表示和推理事物的属性、事物之间的关系，以及涉及量词的推理过程知识图谱知识图谱是知识表示较为成熟的一个代表形式，其所涉及的推理涵盖了事物之间多种类型的关系，体现了描述逻辑的核心内容。第二部分：智能体及其交互聚焦点聚焦智能体本身及其与环境和其他主体的交互机制。刻画智能体的逻辑系统模态逻辑处理不确定性认知逻辑刻画认知状态信念逻辑表达信念关系偏好逻辑建模偏好结构动态逻辑的引入核心作用引入动态逻辑，用以分析智能体如何在动态环境中：处理新信息更新知识修正信念调整偏好从而实现合理决策与行为规划。交互与博弈探讨内容本部分还将探讨：智能体之间的交互多智能体系统中的协作与竞争机制社会网络的逻辑社会网络结构的逻辑建模与分析博弈场景下的逻辑建模博弈论与逻辑方法的结合应用第三部分：机器学习与推理主要内容介绍几种与当代人工智能密切相关且仍在发展中的逻辑。概率推理一种允许我们根据已有证据和统计信息推断未知事件可能性的推理方式。因果推理探讨如何利用反事实条件表达和推断因果关系。AI伦理与道义逻辑伦理挑战探讨人工智能所引发的伦理挑战。分析工具介绍用于分析此类问题的道义逻辑。大语言模型的逻辑推理分析内容分析大语言模型在逻辑推理方面的现状与所面临的挑战。发展方向探讨其潜在的发展方向。本书的特色丰富的实例本书各章节均配有不少具体实例，旨在帮助读者理解抽象逻辑理论在实际中的应用可能性。重视形式化在介绍各类逻辑系统时，我们十分重视自然语言到形式语言的形式化，这是解决实际问题的第一步。完整的形式系统针对具体的逻辑，章节不仅提供了：严格定义形式语言与语义的严格定义形式推理系统系统介绍了相应的形式推理系统练习题配有若干练习，供读者选做元定理分析出于篇幅与内容取向的考虑，书中对元定理的分析比较简略。本书的特色（二）计算性质与复杂性考虑到人工智能中的实际应用需求，我们尽可能补充了各逻辑系统的：计算性质各逻辑系统的可判定性与算法特征计算复杂性结果帮助读者评估其在实践中的可行性与局限性开放态度对于新近兴起的研究领域，本书则力求保持开放态度，鼓励感兴趣的读者进一步探索相关问题。本章总结核心知识点1.人工智能的起源1956年达特茅斯会议标志着AI作为一门学科的起点；图灵测试提供了评估智能的操作性标准2.四种推理形式演绎推理：从一般到具体，结论必然为真归纳推理：从具体到一般，结论可能为真类比推理：从具体到具体，基于结构相似性溯因推理：选择最佳解释，允许修正结论3.AI的发展径路基于逻辑和规则，强调可解释性基于神经网络，强调学习能力两种范式的融合4.本书结构知识表示和推理智能体及其交互机器学习与推理本章总结（续）关键认识逻辑推理是智能的核心体现不同推理形式在AI中发挥不同作用AI的发展需要融合多种技术路径形式化方法是连接理论与实践的桥梁第2章命题逻辑2.1智能家居系统命题设定逻辑规则场景推理2.2命题逻辑的语言公式定义联结词归纳证明2.3命题逻辑的语义真值表逻辑等值有效性2.4自然演绎系统推导规则引入与消去规则2.5元定理可靠性与完全性计算复杂性2.6结语2.1智能家居系统智能家居系统是命题逻辑实际应用的典型场景，通过逻辑规则管理多种设备的联动。本节将展示一个复杂的智能家居场景，包含：灯光控制窗帘系统安防系统空调控制命题设定基本命题符号用字母分别表示以下命题：a"有人在客厅"b"灯开着"c"窗帘关闭"d"室外亮度较低"e"安防系统已激活"f"窗户关闭"g"空调正在运行"h"室内温度超过30°C"逻辑规则（1）（1）灯光控制$$(a∧d)→b$$"如果有人在客厅且室外亮度较低，则打开灯光。"$$(¬a∨¬d)→¬b$$"如果客厅无人或室外亮度足够，则关闭灯光。"（2）窗帘与灯光联动$$b→c$$"如果灯光打开，则关闭窗帘（防止光污染）。"$$¬b→¬c$$"如果灯光关闭，则打开窗帘。"（3）安防系统$$(¬a∧f)→e$$"如果家中无人且窗户关闭，则激活安防系统。"$$(a∨¬f)→¬e$$"如果家中有人或窗户未关闭，则关闭安防系统。"（4）空调与温度控制$$h→g$$"如果室内温度超过30°C，则启动空调。"$$¬h→¬g$$"如果室温低于30°C，则关闭空调。"具体场景：逻辑推理当前环境状态a=0（客厅无人）d=1（室外亮度较低）h=1（室内温度超过30°C）f=1（窗户关闭）逻辑推理过程根据$$(¬a∨¬d)→¬b$$，灯光应关闭($$¬b$$)根据$$(¬a∧f)→e$$，安防系统激活($$e$$)根据$$h→g$$，空调启动($$g$$)根据灯光关闭($$¬b$$)，窗帘可保持打开($$¬c$$)最终状态与意义最终设备状态灯光关闭窗帘打开安防系统激活空调启动命题逻辑的重要性这个例子展示了如何使用命题逻辑：定义规则进行推理实现多设备的动态联动控制更复杂的任务需要更多命题和推理规则，因此构建智能推理系统显得尤为重要。2.2命题逻辑的语言通过将自然语言中的情景转化为命题逻辑中的符号和推理规则，建立智能系统，并利用其推理引擎快速推导出最优状态。本节系统地引入命题逻辑的形式语言。定义1（公式）公式的递归定义令$$VOC_L$$为命题字母的集合。给定$$VOC_L$$，L的公式集是根据以下规则生成的所有表达式构成的集合：（1）$$VOC_L$$中的所有命题字母都是L的公式；（2）如果$$φ$$是L的公式，那么$$¬φ$$也是L的公式；（3）如果$$φ$$和$$ψ$$是L的公式，那么$$(φ∧ψ)$$、$$(φ∨ψ)$$、$$(φ→ψ)$$和$$(φ↔ψ)$$也是L的公式；（4）只有能在有限步骤内由以上(1)~(3)生成的公式才是L的公式。公式的构成基本概念原子公式：命题字母是公式（常称为原子公式）命题变元：$$φ、ψ$$表示任意命题复合公式：通过$$（2）$$和$$（3）$$生成示例$$(p∧q)$$是公式$$((p∨q)∧(p∨r))$$是公式命题联结词：$$¬,∧,∨,→,↔$$$$¬$$是一元联结词$$∧,∨,→,↔$$是二元联结词简化规则在不引起歧义时，通常省略公式最外层的括号。子公式定义给定一个公式，在它生成过程中的每个步骤所用到的公式都是其子公式。例子考虑公式$$φ=(p→(q∧¬r))$$其所有子公式为$$\{(p→(q∧¬r)),p,(q∧¬r),q,¬r,r\}$$归纳证明方法基于公式复杂性的归纳证明要证明所有公式都具有A属性，只需证明以下三点：（1）命题字母具有A属性；（2）如果公式$$φ$$具有A属性，那么$$¬φ$$也一定具有A属性；（3）如果$$φ$$和$$ψ$$具有A属性，那么$$(φ∧ψ)$$、$$(φ∨ψ)$$、$$(φ→ψ)$$和$$(φ↔ψ)$$也一定具有A属性。原理：定义1的归纳子句(4)保证，每一个复合公式必然是由更简单的公式生成的，并且它从这些更简单的公式中继承了A属性。事实1：括号数量事实1命题逻辑语言的所有公式$$φ$$都有相等数量的左右括号。证明（施归纳于公式复杂度）（1）命题字母不包含括号，结论显然成立；（2）假设公式$$φ$$拥有相等数量的左右括号，那么$$¬φ$$的括号数量没有增减，因此具有相等数量的左右括号；（3）假设公式$$φ,ψ$$拥有相等数量的左右括号，$$($$φ∧ψ$$)$$、$$($$φ∨ψ$$)$$、$$($$φ→ψ$$)$$和$$($$φ↔ψ$$)$$正好添加了一个左括号和一个右括号，因此具有相等数量的左右括号。自然语言的形式化重要性要用命题逻辑研究日常推理，首先需要对自然语言进行形式化，将其转换为命题逻辑的公式，以便精确表达推理过程。这一步至关重要，是正确运用命题逻辑进行分析和推理的基础。练习1用命题逻辑的形式语言表示下面用自然语言表达的规则：如果车辆前方检测到障碍物，则自动驾驶系统将自动制动。如果车辆未完成高精度地图下载，则无法开启自动驾驶功能。如果天气条件恶劣或者道路湿滑，自动驾驶系统会降低车速。若传感器读取的行人距离小于5m且车辆速度大于30km/h，系统会发出警告。如果系统检测到侧方有车辆，则车辆不会变道；否则会根据导航规划变道。2.3命题逻辑的语义为了确定什么样的推理是有效的，本节将首先介绍命题逻辑的语义解释。基本约定用$$1$$表示"真"用$$0$$表示"假"使用真值表解释命题联结词的意义一旦理解了基本联结词的意义，就能够理解任何复合公式的意义。2.3.1真值表本小节将介绍各个命题联结词的真值表定义。命题联结词否定（Negation）：$$¬$$合取（Conjunction）：$$∧$$析取（Disjunction）：$$∨$$蕴涵（Implication）：$$→$$等价（Equivalence）：$$↔$$1.否定（Negation）定义一个公式为真，它的否定为假；一个公式为假，它的否定为真。说明在自然语言中，除了使用"不""不是""没有"等词语表示否定外，还有许多其他的否定表达方式。在对自然语言进行形式化的过程中，需要我们正确辨认。表2-1否定的真值表$$φ$$$$¬φ$$10012.合取（Conjunction）定义一个合取式为真，当且仅当，两个合取肢都为真，否则为假。表2-2合取的真值表$$φ$$$$ψ$$$$φ∧ψ$$1111000100003.析取（Disjunction）相容析取一个析取式为真，当且仅当，其中的一个析取肢为真。这是所谓"相容"析取式的真值表，即不排除两个析取肢都为真的析取。示例我喜欢哲学或计算机科学。可以通过阅读人工智能论文或与专家交流来学习深度学习。表2-3析取的真值表$$φ$$$$ψ$$$$φ∨ψ$$111101011000不相容析取定义不相容析取排除了析取肢都为真的情况。在汉语中通常用要么……要么……的结构表示。示例我要么学习人工智能理论，要么专注于编写代码。你可以要么从事计算机硬件开发，要么专注于软件工程。我们今晚要完成这篇论文，除非下午参加黑客马拉松。约定：在本书中，除非特别说明，当"或者"被使用时，会被理解为是相容析取。表2-4不相容析取的真值表$$φ$$$$ψ$$$$φ⊕ψ$$1101010110004.蕴涵（实质蕴涵）表2-5实质蕴涵的真值表$$φ$$$$ψ$$$$φ→ψ$$111100011001理解要点第二行容易理解：如果$$φ$$为真且$$ψ$$为假，那么$$φ→ψ$$为假。这很直观：要证明"如果$$φ$$，那么$$ψ$$"是假的，只需证明$$φ$$是真的，且$$ψ$$是假的。蕴涵的理解为什么其他行为真？事实上$$φ$$为真而$$ψ$$为假是我们可以断定$$φ→ψ$$为假的唯一情况。因为句子要么真要么假，这就意味着在所有其他情况下$$φ→ψ$$都是真的。例子"如果一个数字大于10，那么它就大于5。"这句话显然是真的。找不到一个数字n可以使得$$n>10$$且$$n\not>5$$。无论选择什么数n，都满足如果$$n>10$$，那么$$n>5$$。这也包括选取一个介于5和10之间的数的情况，即前件为假，后件为真的情况。蕴涵的自然语言表达注意在自然语言中，表示蕴涵的句子并不一定包含如果……（那么）……的表达式。示例为使液体溶解，有必要将其加热到至少60°C。为了让蒸汽消失，将其压力降至99kPa就足够了。改写为标准形式如果液体溶解了，它就被加热到了至少60°C。如果压力降至99kPa，蒸汽就会消失。5.等价表2-6等值的真值表$$φ$$$$ψ$$$$φ↔ψ$$111100010001定义根据表2-6，$$φ$$↔$$ψ$$为真，当且仅当，$$φ$$和$$ψ$$具有相同的真值。说明在数学和逻辑学之外，自然语言中出现当且仅当这一术语的情况非常少见。但是需要辨认句子之间的逻辑关系，做出正确的形式化。6.复合公式的语义计算方法一旦为所有命题字母指定了真值，并对联结词进行了解释，就可以继续使用真值表计算复合公式的真值。表2-7$$(p∨q)∧¬r$$的复合真值表pqrp∨q¬r(p∨q)∧¬r111100110111101100100111011100010111001000000010复合公式真值计算程序通用程序确定任意命题公式$$φ$$的真值：第一步确定在$$φ$$中出现了哪些命题字母$$p₁,p₂,⋯,pₙ$$；第二步绘制一张包含$$2ⁿ$$行的表，并在每一行填入$$p₁,p₂,⋯,pₙ$$的唯一真值组合；第三步按照$$φ$$的构造过程，为其中的每个子公式添加一列，并在每一行中计算其真值。练习2给出下面公式的复合真值表：$$¬¬¬¬p$$$$(p∧q)→¬r$$$$(p∨q)∧(r→¬s)$$$$(p→q)→(p→¬q)$$赋值的概念赋值（Valuation）赋值是一个函数，它为命题语言中的每个公式指派一个真值。重要限制并不是任何函数都可以成为有效的赋值，只有那些符合我们希望赋予联结词解释的函数才是恰当的赋值函数。换句话说，赋值必须确保逻辑联结词（如$$∧$$、$$∨$$、$$¬$$等）的语义解释在赋值中得到正确体现。定义2（赋值真值语义）赋值函数的定义赋值$$V$$是一个从$$FORM_L$$到$$\{0,1\}$$的函数，它满足以下要求：（1）$$V(pᵢ)∈\{0,1\}$$，对于所有的$$pᵢ∈VOC_L$$；（2）$$V(¬φ)=1\⟺V(φ)=0$$；（3）$$V(φ∧ψ)=1\⟺V(φ)=1$$且$$V(ψ)=1$$；（4）$$V(φ∨ψ)=1\⟺V(φ)=1$$或$$V(ψ)=1$$；（5）$$V(φ→ψ)=1\⟺V(φ)=0$$或$$V(ψ)=1$$；（6）$$V(φ↔ψ)=1\⟺V(φ)=V(ψ)$$；说明：这个定义与联结词的真值表是一致的。这里，只需说明公式在何种情况下为真，而其他情况则可以从赋值函数的规则中推导出来。2.3.2逻辑等值、重言式与矛盾式本节将介绍一些命题逻辑的重要概念：逻辑等值两个公式在所有赋值下具有相同真值重言式（Tautology）在所有赋值下均为真的公式矛盾式（Contradiction）在所有赋值下均为假的公式可满足式（Contingency）既非重言式也非矛盾式的公式1.逻辑等值的引入观察考虑复合真值表2-8，有两个不同的公式$$p→q$$和$$¬p∨q$$。如表2-8所示，这两个公式的真假情况在四种情形下完全一致。这时，称这两个公式逻辑等值（LogicallyEquivalent）。表2-8$$p→q$$和$$¬p∨q$$的复合真值表pq¬p$$p→q$$$$¬p∨q$$11011100000111100111逻辑等值的性质重要观察$$p→q$$和$$¬p∨q$$的逻辑等值并不依赖于其中出现的具体字母$$p$$和$$q$$。例如，$$r→s$$和$$¬r∨s$$也是逻辑等值的。关键：逻辑形式这里起作用的是逻辑形式：任何形为$$φ→ψ$$的公式都逻辑等值于形为$$¬φ∨ψ$$的公式。定义3（逻辑等值）定义$$\phi$$和$$\psi$$是逻辑等值的，当且仅当，对于所有赋值$$V$$:$$V(\phi)=V(\psi)$$。意义可以利用赋值真值定义代替真值表，证明两个公式是逻辑等值的。事实2（双重否定）事实2$$φ$$和$$¬¬φ$$是逻辑等值的。证明对任意的赋值$$V$$。假设$$V(φ)=1$$。那么$$V(¬φ)=0$$（根据赋值真值定义的第(2)条），进一步$$V(¬¬φ)=1$$（同上）。$$V(φ)=0$$的情况类似。练习3：逻辑等值关系证明下列公式是逻辑等值的1.$$φ$$,$$¬¬φ$$,$$φ∧φ$$,$$φ∨φ$$,$$φ∧(φ∨ψ)$$,$$φ∨(φ∧ψ)$$2.$$¬φ$$,$$φ→(ψ∧¬ψ)$$3.$$¬(φ∨ψ)$$,$$¬φ∧¬ψ$$（德·摩根律）4.$$¬(φ∧ψ)$$,$$¬φ∨¬ψ$$（德·摩根律）5.$$φ∨ψ$$,$$ψ∨φ$$（∨交换律）6.$$φ∧ψ$$,$$ψ∧φ$$（∧交换律）7.$$φ∧(ψ∨χ)$$,$$(φ∧ψ)∨(φ∧χ)$$（分配律）练习3（续）8.$$φ∨(ψ∧χ)$$,$$(φ∨ψ)∧(φ∨χ)$$（分配律）9.$$φ→ψ$$,$$¬φ∨ψ$$,$$¬(φ∧¬ψ)$$,$$¬ψ→¬φ$$10.$$φ→ψ$$,$$¬ψ→¬φ$$（逆否律）11.$$φ↔ψ$$,$$(φ→ψ)∧(ψ→φ)$$,$$(φ∧ψ)∨(¬φ∧¬ψ)$$12.$$(φ∨ψ)∧¬(φ∧ψ)$$,$$¬(φ↔ψ)$$,$$¬φ↔ψ$$13.$$(φ∨ψ)→χ$$,$$(φ→χ)∧(ψ→χ)$$14.$$φ→(ψ∧χ)$$,$$(φ→ψ)∧(φ→χ)$$15.$$φ→(ψ→χ)$$,$$(φ∧ψ)→χ$$定理1（替换）定理如果$$φ$$和$$ψ$$逻辑等值，那么$$χ$$与[$$φ$$/$$ψ$$]$$χ$$也逻辑等值。符号说明[$$α$$/$$β$$]$$γ$$表示用$$α$$替换$$γ$$中$$β$$的出现而得到的结果。证明思路施归纳于$$χ$$的结构。注意：$$φ$$,$$ψ$$,$$χ$$是复杂公式；命题字母根据定义是不等值的，且不包含子公式。替换定理的证明（部分）情况1：$$χ=¬ψ$$那么$$[φ/ψ]χ=¬φ$$因为对于所有的$$V$$:$$V(φ)=V(ψ)$$，所以对所有的$$V$$:$$V(¬φ)=V(¬ψ)$$。情况2：$$χ=ψ∧ξ$$那么$$[φ/ψ]χ=φ∧ξ$$因为对于所有的$$V$$:$$V(φ)=V(ψ)$$，所以，对所有的$$V$$:$$V(ψ∧ξ)=V(φ∧ξ)$$。其余情况留待读者自行验证。替换定理的意义真值条件特性替换定理揭示了命题语言公式的真值条件特性。核心原理由于公式的真假只取决于其子公式的真假，具有相同真值的等值公式可以相互替换，而不会改变整个公式的真值。练习4根据练习3中给出的等值式，证明下列公式是等值的：$$φ$$↔$$ψ$$和$$ψ$$↔$$φ$$（交换律）$$φ→¬φ$$和$$¬φ$$$$φ∧(ψ∧χ)$$和$$χ∧(ψ∧φ)$$$$φ⊕ψ$$和$$φ$$↔$$¬ψ$$$$φ⊕¬ψ$$,$$¬φ⊕ψ$$和$$φ$$↔$$ψ$$实质等值与逻辑等值的联系观察表2-9是一个简单的示例。对任意赋值$$V$$:$$V(φ)=V(¬¬φ)$$，因此，对任意$$V$$:$$V(φ↔¬¬φ)=1$$。表2-9$$φ$$↔$$¬¬φ$$的复合真值表$$φ$$$$¬φ$$$$¬¬φ$$$$φ↔¬¬φ$$10110101事实3事实3$$φ$$和$$ψ$$是逻辑等值的⟺对于任意赋值$$V$$:$$V(φ↔ψ)=1$$。说明显然，这对任意两个逻辑等值公式及其对应的实质等值关系都是成立的。2.重言式定义总是为真的公式构成了一个特殊的类别，称为重言式。例如，$$φ$$↔$$¬¬φ$$定义4（重言式）公式$$φ$$是重言式，记作：$$⊨φ$$，当且仅当，对于任意赋值$$V(φ)=1$$。重言式的证明方法两种证明方法与逻辑等值的情况一样，可以通过：给出复合真值表通过赋值真值定义来证明例子$$⊨φ→(ψ→φ)$$可由复合真值表2-10表示。表2-10$$φ→(ψ→φ)$$的复合真值表$$φ$$$$ψ$$$$ψ→φ$$$$φ→(ψ→φ)$$1111101101010011重言式的另一种证明证明假设$$φ→(ψ→φ)$$不成立，那么一定存在一个赋值$$V$$:$$V(φ)=1$$且$$V(ψ→φ)=0$$。如果$$V(φ)=1$$，那么$$V(ψ→φ)=1$$，因此有$$V(φ→(ψ→φ))=1$$。这与假设相矛盾，因此最初的假设不成立。方法：这个证明使用了所谓的归谬法（ReductioadAbsurdum）。要证明某个事实为真，先假设其为假，进一步说明依据这个假设会得到矛盾结论。练习5：证明重言式练习5证明下列公式是重言式（对于任意的$$φ$$、$$ψ$$和$$χ$$）：$$¬φ→(φ→ψ)$$（爆炸律）$$φ∨¬φ$$（排中律）$$(φ→(ψ→χ))→((φ→ψ)→(φ→χ))$$$$(φ→ψ)∨(ψ→φ)$$$$((φ→ψ)→φ)→φ$$（皮尔士律）练习6：判断重言式练习6判断下列公式是否为重言式：$$（¬p∨¬q）→¬（p∨q）$$$$((p∨q)∧(¬p→¬q))→q$$$$((p→q)→p)→((p→q)→q)$$$$((p→q)→r)→(p→(q→r))$$矛盾式定义与重言式相反的是那些永远为假的公式$$φ$$，被称为矛盾式，即对每个赋值$$V:V(φ)=0$$。例子$$φ∧¬φ$$是矛盾式，见表2-11。表2-11$$φ∧¬φ$$的复合真值表$$φ$$$$¬φ$$$$φ∧¬φ$$100010重言式与矛盾式的关系事实4如果$$φ$$是重言式，那么$$¬φ$$就是矛盾式。事实5如果$$φ$$是矛盾式，那么$$¬φ$$就是重言式。重要性质同重言式一样，所有的矛盾式都等值。可满足式定义除了重言式和矛盾式，第三类公式叫作（逻辑）可满足式。这些公式既不是重言式也不是矛盾式，即对于公式$$φ$$：既存在赋值$$V(φ)=1$$也存在赋值$$V(φ)=0$$特点在可满足式的真值表中，至少有一行是$$1$$，且至少有一行是$$0$$。与重言式和矛盾式不同，可满足式之间并不都是等值的。事实6事实6$$φ$$是可满足式，当且仅当，$$¬φ$$是可满足式。练习7令$$φ$$为重言式，$$ψ$$为矛盾式，$$χ$$为可满足式。判断下列哪些句子(i)是重言的，(ii)是矛盾的，(iii)是可满足的，(iv)是逻辑等值于$$χ$$的：$$φ∧χ$$(5)$$φ∧ψ$$$$φ∨χ$$(6)$$φ∨ψ$$$$ψ∧χ$$(7)$$χ→ψ$$$$ψ∨χ$$2.3.3有效性引言重言式是永真的公式，是普遍规律矛盾式是永假的公式，是在推理和思维中要绝对避免的要研究从前提到结论的逻辑推理，本节最后介绍一个重要的概念：有效性。定义5（论证模式）定义论证模式是一连串的公式$$φ₁,⋯,φₙ/ψ$$，其中：$$φ₁,⋯,φₙ$$称为前提$$ψ$$为结论定义6（有效性）定义一个论证模式$$φ₁,⋯,φₙ/ψ$$是有效的，当且仅当，对所有赋值$$V:V(φ₁)=⋯=V(φₙ)=1⟹V(ψ)=1$$。意义如果前提的真必然得到结论的真，那么论证模式就是有效的。或者换一种说法，不可能前提全部为真而结论为假。符号有效性：$$φ₁,⋯,φₙ⊨ψ$$无效：$$φ₁,⋯,φₙ⊭ψ$$特殊情况：当$$n=0$$时，$$φ₁,⋯,φₙ/ψ$$的有效性就会简化为$$ψ$$是重言式。有效性的证明方法两种证明方法与证明两个公式等值或一个公式是重言式的情况类似，命题逻辑中的论证模式的有效性既可以通过：真值表证明赋值真值定义和有效性定义加以证明真值表证明示例例子：$$p→(q∧r),q→¬r/¬p$$表2-12$$p→(q∧r),q→¬r/¬p$$的复合真值表pqrq∧rp→(q∧r)¬rq→¬r/¬p11111000110001101010001010000110011110010100111*10010101*10000111*1说明：用/列标注所有前提都是1的行（标记*）。如果结论在所有这些行中也都是1，那么该论证就是有效的。赋值真值定义证明示例证明假设该论证不是有效的，那么存在一个赋值V，使得$$V(p→(q∧r))=V(q→¬r)=1,V(¬p)=0$$（假设）那么$$V(p)=1$$（¬）所以$$V(q∧r)=1$$（前提一，→）那么$$V(q)=V(r)=1$$（∧）$$V(q)=1$$蕴涵$$V(¬r)=1$$（前提二，→）因此$$V(r)=0$$（¬）与$$V(r)=1$$相矛盾假设不成立，从而证明该论证是有效的。无效论证的例子例子：$$p→q$$,$$q$$/$$p$$（也称为"肯定后件的谬误"）表2-13$$p→q,q/p$$的复合真值表$$p$$$$q$$$$p→q$$$$/p$$111*11000011*00010反例有两行的前提都是1，其中一行的结论是0，这一行是前提为真而结论为假的情况，称为反例。使用复合真值表是寻找反例的一种高效的方法。练习8判断下列论证模式是否有效。如果模式无效，请给出反例。1–5$$p∧q/p$$$$p,¬p/q$$$$p∧q/q$$$$p→(q∧¬q)/¬p$$$$p∨q/p$$6–9$$p∨q,p→r,q→r/r$$$$p,q/p∧q$$$$p∨q,(p∧q)→r/r$$$$p/p∨q$$练习8（续）10–14$$p∨q,p→q/q$$$$q/p∨q$$$$p∨q,p→q/p$$$$p/p∧q$$$$p→q,¬q/¬p$$15–18$$p,p→q/q$$$$p→q/¬p→¬q$$$$p,q→p/q$$2.4自然演绎系统从语义到语法2.3节学习了如何使用语义的方法判断推理的有效性。本节将转向语法的视角介绍自然演绎系统，给出规则确保能够在该系统中进行严格的逻辑推导。推导的基本形式什么是推导？公式$$χ$$的推导是由公式组成的、有带编号的列表$$χ₁⋯χₘ⋯$$，且该列表以公式$$χ$$作为最后一个元素。推导的形式1.$$χ₁$$⋮m.$$χₘ$$⋮n.$$χ$$推导的标记两种得到公式的方式1.运用有穷规则中的一条规则2.基于假设标记方法注明所用规则，并标出运用该规则的公式行号如果是假设，则用A表示具体形式1.χ₁A⋮m.χₘRₖ,j⋮n.χRₗ,h,m假设的类型活跃假设与撤销假设关于假设，需要区分是："活跃的"（Active）假设"撤销的"（Withdrawn）假设稍后在讨论蕴涵规则时再讨论撤销的假设。论证前提注意，论证给出的前提总是活跃的假设，按照惯例，它们列在一个推导的开头。从前提出发的推导标准形式ψ从前提φ₁⋯φₙ出发的推导具有如下形式：1.φ₁A⋮n.φₙA⋮m.ψ符号表示用φ₁⋯φₙ⊢ψ表示论证模式φ₁⋯φₙ/ψ的推导。自然演绎的基本思想引入规则与消去规则自然演绎的基本思想是，每个联结词都有两条规则：引入规则（IntroductionRule）说明如何获得具有某种形式的公式消去规则（EliminationRule）说明如何使用具有某种形式的公式以下先介绍二元联结词∧、∨、→的引入和消去规则。1.合取的引入规则引入规则I∧⋮m₁.φ⋮m₂.ψ⋮n.φ∧ψI_∧,m₁,m₂说明I∧说的是，为了推导出一个合取式φ∧ψ，需要推导出它的两个合取肢，φ和ψ，或者，这两个合取肢是假设集中的公式。合取引入规则的例子证明p,q,r⊢q∧(p∧r)1.pA2.qA3.rA4.p∧rI∧,1,35.q∧(p∧r)I∧,2,4合取的消去规则消去规则E∧⋮m.φ∧ψ⋮k.φE∧,m并且⋮m.φ∧ψ⋮k.ψE∧,m说明E∧是一条规则，分成两部分：可以用合取式φ∧ψ分别推导它的两个合取肢，φ和ψ。合取交换律的证明例子："合取的交换律"p∧q/q∧p1.p∧qA2.pE∧,13.qE∧,14.q∧pI∧,3,2练习9证明下列论证模式是有效的：(p∧q)∧r⊢p∧(q∧r)（合取的结合律）p⊢p∧pp∧(q∧r)⊢r∧pp∧(q∧r)⊢(p∧q)∧(p∧r)(φ∧q)∧(p∧r)⊢p∧(q∧r)2.蕴涵的消去规则消去规则E→⋮m₁.$$φ→ψ$$⋮m₂.$$φ$$⋮k.$$ψ$$E→,m₁,m₂说明蕴涵的消去规则非常容易理解。如果有一个蕴涵式$$φ→ψ$$，它可能是推导的中间步骤，也可能是假设，只要得到前件$$φ$$，下一步就可以推导出$$ψ$$。蕴涵消去规则的例子证明p→(q∧r),r→s,p/s是有效的1.p→(q∧r)A2.r→sA3.pA4.q∧rE_→,1,35.rE_∧,46.sE_→,2,5练习10证明下列论证模式是有效的1.p∧r,r→q⊢p∧q2.p∧q,p→r,q→s⊢r∧s3.p,q,p∧q→r⊢r4.p∧q,p→(q→r)⊢r蕴涵的引入规则引入规则I→⋮m.φA⋮n-1.ψ─────────────────────n.φ→ψI→说明为推导出蕴涵式φ→ψ，首先引入前件φ作为假设，推导出后件ψ，然后撤销假设φ的同时推导出该蕴涵式。在这样的推导中，假设φ是在第m步提出的，在后面的第n步中撤销的，在第m+1步到第n-1步中是活跃的。强化前提的例子简单例子：同时使用了蕴涵的两种规则1.p→qA2.p∧rA3.pE∧,24.qE→,1,3─────────────────────5.(p∧r)→qI→这是一个"强化前提"的例子。蕴涵的传递性例子：证明p→q,q→r/p→r是有效的1.p→qA2.q→rA─────────────────────3.pA─────────────────────4.qE_→,1,35.rE_→,2,46.p→rI_→关于假设的问题活跃假设与撤销假设上面的例子表明，一个推导可以同时包含活跃和撤销的假设：p→q和q→r是活跃的假设（即论证的前提）p是撤销的假设p在提出时（第3步）是活跃的，直到第6步撤销。表示方法在推导中，从假设提出到假设撤销的步骤之间画一条线，表示该假设在此期间是活跃的。假设使用的条件正确使用假设的条件（1）撤销的假设不能在后续推导中继续使用。（2）如果一个公式依赖于已撤销的假设，那么假设撤销后，该公式也无法再使用。（3）如果有多个假设，应先撤销最后一个提出的假设。下面举例说明，当不满足这些条件时会导致哪些问题。违反条件（1）的例子错误示例─────────────────────1.p∧qA2.pE_∧,1─────────────────────3.(p∧q)→pI_→*4.qE_∧,1问题推导的第4步对p∧q使用了合取消去规则，但是这个公式是一个被撤销的假设，因此不再可用。如果允许这样做，就可以在没有任何假设的情况下推导出q，即q本身的有效性的证明。违反条件（2）的例子错误示例1.q→rA─────────────────────2.p∧qA3.qE∧,2─────────────────────4.(p∧q)→qI→*5.rE→,1,3问题在第5步中，使用了一个公式q，该公式是在假设p∧q的基础上推导出来的，而在推导过程中，假设p∧q已被撤销。违反条件（3）的例子错误示例1.p→qA2.pA3.qE_→,1,2*4.(p→q)→qI_→问题第4步撤销了一个假设，即p→q，从而抛弃了另一个假设，即p，这个假设是后来提出的，在该阶段仍然活跃。正确的撤销顺序按正确的顺序撤销假设从后往前的顺序撤销假设，就能得到正确的结果：─────────────────────1.p→qA─────────────────────2.pA3.qE_→,1,24.p→qI_→─────────────────────5.(p→q)→(p→q)I_→能够清楚地看到假设在哪里起作用。练习11证明下列论证模式是有效的1.⊢(p→(q→r))→((p∧q)→r)2.⊢(p→(p→q))→(p→q)3.p→q,p→r⊢p→(q∧r)4.p→(q→r)⊢(p∧q)→r重复规则RepetitionRule顾名思义，重复规则允许重复使用已经得到的公式：⋮m.φ⋮n.φRep,m使用条件被重复使用的公式不能是已撤销的假设，也不能依赖于已撤销的假设。例子：在推导⊢p→(q→p)时派上了用场错误使用下面的推导不满足条件会导致错误：重复规则的表达力重要说明事实上，重复规则并没有给系统增加任何表达力，它的作用也可以通过已有的规则实现。例子可以通过对φ运用I∧得到φ的"重复"，然后通过运用E∧从结果中推导出φ：练习12（1）展示如何使用蕴涵规则模拟重复规则的效果。（2）给出两个不同的推导证明⊢q→((p→q)→q)，一个使用重复规则，另一个不使用重复规则。3.析取的引入规则引入规则I∨m.φ⋮n.φ∨ψI_∨,m且m.ψ⋮n.φ∨ψI_∨,m说明这条规则不言自明：要推导出一个析取式φ∨ψ，只要推导出其中一个析取肢就足够了。析取的消去规则如何使用析取式？消去规则稍微复杂一些。如果有p∨q，无论是作为假设还是推导结果，能从中推导出什么呢？显然，p和q都不能直接从p∨q中推导出来。间接作用它的用途是间接的：如果能从每个析取肢中推导出同一个公式，那么通过这个析取式，就能推导出该公式。这正是消去规则的作用。析取消去规则E∨消去规则E∨⋮m₁.φ∨ψ⋮m₂.φ→χ⋮m₃.ψ→χ⋮k.χE∨,m₁,m₂,m₃说明因此，如果从假设φ和假设ψ分别可以推导出χ，同时有析取式φ∨ψ，那么就可以从φ∨ψ推导出χ。析取消去规则的例子证明p∨q⊢((p→q)→q)练习13证明下列论证模式是有效的1.p∨q⊢q∨p2.p∨(p∧q)⊢p3.p∨(q∨r)⊢(p∨q)∨r4.(p∨q)→r⊢p→r5.p∧(q∨r)⊢(p∧q)∨(p∧r)4.否定的消去规则复杂性关于否定的规则比二元联结词的情况更为复杂。这种复杂性与逻辑的强弱有关。消去规则E¬⋮m.¬φ⋮k.φ⋮n.⊥E¬,m,k恒假符号⊥是一个特殊的原子公式，叫作恒假（Falsum），表示矛盾式。否定消去规则的说明规则E¬的含义根据E¬，如果一个推导中同时得到¬φ和φ，那么结论可以得到⊥。例子：证明p,q→¬p,q⊢⊥1.pA2.q→¬pA3.qA4.¬pE→,2,35.⊥E¬,1,4注意在命题逻辑语言中添加⊥作为新的表达式，是为方便起见。也可以使用任意矛盾式代替⊥，例如q∧¬q。否定的引入规则引入规则I¬⋮m.φA⋮n-1.⊥─────────────────────n.¬φI¬说明如果从假设φ出发进行推导，最终得到⊥，那么下一步可以撤销假设、推导出¬φ。否定规则的例子证明⊢¬(p∧¬p)：同时使用了E¬和I¬─────────────────────1.p∧¬pA2.pE∧,13.¬pE∧,14.⊥E¬,2,3─────────────────────5.¬(p∧¬p)I¬练习14给出推导证明⊢¬((p→q)∧(p∧¬q))p→q,p→¬q⊢¬p⊢p→¬¬p⊢(p→q)→(¬q→¬p)¬p∨q⊢p→q¬p∨¬q⊢¬(p∧q)注意¬(p∧¬p)是¬(φ∧¬φ)的一个实例，被称为"无矛盾律"（PrincipleofNon-Contradiction）。EFSQ-规则（爆炸原则）ExFalsoSequiturQuodlibet拉丁语"ExFalsoSequiturQuodlibet"（EFSQ），意为"从矛盾中可以得出任何结论"。规则⋮n-1.⊥n.φEFSQ,n-1意义EFSQ-规则体现了系统中出现矛盾⊥的一个重要特性。EFSQ规则的应用例子：p∨q,¬p⊢q展示了EFSQ的作用1.p∨qA2.¬pA─────────────────────3.pA4.⊥E_¬,2,35.qEFSQ,46.p→qI_→─────────────────────7.qA8.q→qI_→─────────────────────9.qE_∨,1,6,8练习15推导证明下列公式是有效的1.⊢¬p→(p→q)2.⊢(p∧¬p)→q3.⊢(p→q)→((p→¬q)→(p→r))4.⊢((p→q)→p)→p双重否定规则最后一个规则：¬¬规则双重否定规则是自然演绎系统中的最后一条规则，用于处理双重否定的消去与引入。双重否定规则的应用例子：推导q→p,¬q→p⊢p展示了如何运用双重否定规则重要说明由上述所有规则构成的自然演绎系统所刻画的逻辑，与2.3节中语义刻画的逻辑相同，即古典逻辑。2.5元定理本节简要介绍逻辑系统的几个重要元定理，特别是一些计算性质。核心问题前文讨论了研究推理的两种方法——语义方法和语法方法，一个自然的问题是，它们之间的关系如何？核心定理可靠性和完全性定理正是回答这一问题的。定理2（可靠性）设$$Γ$$是命题公式的集合，$$φ$$是一个命题公式。如果$$Γ⊢φ$$，则$$Γ⊨φ$$。证明思路只需证明每个推理规则（引入和消去规则）都是"保真"的，即对任意的语义模型而言，若前提为真，结论一定为真。定理3（完全性）设Γ是命题公式的集合，φ是一个命题公式。如果Γ⊨φ，则Γ⊢φ。证明思路假设某公式φ不能从Γ推出（Γ⊬φ），可以使用极大一致集（MaximalConsistentSet）构造一个"反模型"，即一个使Γ中所有公式为真、但φ为假的模型。得到Γ⊭φ，由此通过逆否命题（Contraposition）可以得到：如果Γ⊨φ，就必然有Γ⊢φ。强完全性与弱完全性强完全性定理上面的定理一般称为强完全性定理。弱完全性定理当Γ为空集时，该定理又称为弱完全性定理。弱完全性定理是强完全性定理的特例。参考文献关于这些定理的详细证明，感兴趣的读者可参考文献ChiswellandHodges(2007)。判定问题计算角度的问题在命题逻辑中，有几个重要的判定问题可以从计算的角度进行考察。所谓"从计算的角度"，是指我们关心是否存在某种可行的算法，能够有效地解决这些问题。三个重要问题可满足性问题（SAT）给定一个公式，判断是否存在某个模型使该公式为真模型检测问题（ModelChecking）给定一个模型M和一个公式φ，判断𝔐⊨φ是否成立重言式判定问题（TAUT）给定一个公式，判断该公式是否在所有模型中都为真定理4（模型检测的复杂性）设M为一个有穷的模型，φ为命题逻辑中的公式。判断$$𝔐⊨φ$$是否成立可以在多项式时间内完成。结论因此，命题逻辑的模型检测问题属于P类。定理5（Cook-Levin定理）命题逻辑的SAT问题是NP-完全的。这意味着：SAT属于NP类对于任意NP问题，都存在一个多项式时间可计算的归约函数，使其归约为SAT定理6（重言式判定的复杂性）命题逻辑的TAUT问题是co-NP完全的。这意味着：TAUT属于co-NP类任意一个co-NP问题都可以在多项式时间内归约为TAUT参考文献对这些结果感兴趣的读者，参考文献Sipser(2012)。2.6结语：自然语言推理的复杂性与形式语言的作用本节总结命题逻辑在处理自然语言推理中的重要作用。自然语言推理的局限日常推理的直观性在日常交流和思维过程中经常需要进行推理。例如："如果天下雨，那么地面会湿""天下雨了"得出"地面会湿"