数理逻辑归结法原理
- 格式：pptx
- 大小：1.55 MB
- 文档页数：26
下载文档原格式
合集下载
离散数学 第3章 基于归结原理的推理证明
16
3.2.2原子集
定义 3.2.2 下列集合称为子句集 S 的原子集： A＝｛所有形如 P(t1, t2,…,tn)的元素｝ 其中，P(t1, t2,…,tn)是出现在 S 中的任一谓词符号，而 t1，t2，…，tn 则是 S 的 H 域上的 任意元素。 定义 3.2.3 将没有变元出现的原子、文字、子句和子句集分别称作基原子、基文字、基 子句和基子句集。 定义 3.2.4 当子句集 S 中的某个子句 C 中的所有变元符号均以其 H 域中的元素替换时， 所得到的基子句称作 C 的一个基例。 例 3.2.2 对于子句集 S＝{P(a),P(x)∨P(f(x))},它的 H 域为{a,f(a),f(f(a)),…}。 对于子句 P(a)，因为其中不含有变元，所以它已是基子句，而且 aH，所以它也是基例。
20
3.3.1.2 置换的合成
置换的合成是将两个置换合成为一个置换。 定义 3.3.3 假设 ={t1/x1,t2/x2,…,tn/xn}, ={u1/y1,u2/y2,…,um/ym}是两个置换， 则它们的合成是一个新置换， 其作用于公式 E 时， 相当于先 后 λ 对 E 的作用。 它的定义如下： 先作置换{t1· /x1,t2· /x2,…,tn· /xn,u1/y1,u2/y2,…,um/ym}。 若 yi{ x1,…,xn}时，先从上述集合中删除 ui/yi。 若 ti· =xi 时，再从上述集合中删除 ti· /xi 。 删除以后剩下元素所构成的集合称作 与 的乘积，记作 · 。
17
3.2.3 H域上的解释
定义 3.2.5 如果子句集 S 的原子集为 A，则对 A 中各元素的真假值的一个具体设定都是 S 的一个 H 解释。 可以证明，在给定域 D 上的任一个解释 I，总能在 H 域上构造一个解释 I*与之对应，使得如果 D 域上 的解释能满足子句集 S，则在 H 域的解释 I*也能满足 S（即若 S|I=T，就有 S|I*=T） 。 定理 3.2.1 设 I 是子句集 S 在域 D 上的一个解释，则存在对应于 I 的 H 域解释 I*，使得若有 S|I=T，就 必有 S|I*=T。 定理 3.2.2 子句集 S 不可满足的充要条件是 S 对 H 域上的一切解释都为假。 证明 充分性：若 S 在一般域 D 上是不可满足的，必然在 H 域上是不可满足的，从而对 H 域上的一 切解释都为假。 必要性：若 S 在任一 H 解释 I*下均为假，必然会使 S 在 D 域上的每一个解释为假。否则，如果存在一 个解释 I0 使 S 为真，那么依据定理 3.2.1 可知，一定可以在 H 域找到相对应的一个解释 I*0 使 S 为真。这与 S 在所有 H 解释下均为假矛盾。
数理逻辑归结法原理
的所有简单析取范式组成集合； (3).若Ω不可满足，则Q1,…,Qn|=R。
计算机学院
计算机学院
5
5
机械式方法
▪ 若证明Q1,…,Qn|=R，只要证明Q1…QnR 不可满足。
▪ 机械式证明：
公式Q1…QnR的合取范式； 合取范式的所有简单析取范式，即Ω；
证明Ω不可满足
▪ 则有Q1,…,Qn|=R。
▪ 开创性的工作是赫伯特·西蒙（H. A. Simon）和艾伦· 纽威尔（A. Newel）的 Logic Theorist。
▪ 机械定理证明的主要突破是1965年由鲁宾逊（ J.A.Robinson）做出的，他建立了所谓归结原理，使机械 定理证明达到了应用阶段。
▪ 归结法推理规则简单, 而且在逻辑上是完备的, 因而成为 逻辑式程序设计语言Prolog的计算计模算型机。学院
▪ 因为(PQR)((PR)(QR)计)的算合机取学范院式 (PQR) PQR
▪ 所以子句集合 Ω={P,Q, R ,PQR }
计算机学院
24
24
▪ Q1=PQR Q1Ω
▪ Q2=P
Q2Ω
▪ Q3=QR
Q3= (Q1-P) (Q2-P)
可满足，进而有Ω0可满足。 ▪ 证毕
计算机学院
计算机学院
21
21
▪ 例题：P(QR)├ (PQ) (PR) 分配律 ▪ (P(QR)) ((PQ) (PR)) ▪ (P(QR)) ((PQ) (PR)) ▪ (PQ) (PR))( P (PR)) (Q (PR)) ▪ (PQ) (PR)P ( P R) (Q P)( QR)
▪ 对一阶逻辑公式，其解释的个数通常是任意多个，丘奇 （A.Church）和图灵（A.M.Turing）在1936年证明了不存 在判定公式是否有效的通用程序。计算机学院
计算机学院
计算机学院
5
5
机械式方法
▪ 若证明Q1,…,Qn|=R，只要证明Q1…QnR 不可满足。
▪ 机械式证明：
公式Q1…QnR的合取范式； 合取范式的所有简单析取范式，即Ω；
证明Ω不可满足
▪ 则有Q1,…,Qn|=R。
▪ 开创性的工作是赫伯特·西蒙（H. A. Simon）和艾伦· 纽威尔（A. Newel）的 Logic Theorist。
▪ 机械定理证明的主要突破是1965年由鲁宾逊（ J.A.Robinson）做出的，他建立了所谓归结原理，使机械 定理证明达到了应用阶段。
▪ 归结法推理规则简单, 而且在逻辑上是完备的, 因而成为 逻辑式程序设计语言Prolog的计算计模算型机。学院
▪ 因为(PQR)((PR)(QR)计)的算合机取学范院式 (PQR) PQR
▪ 所以子句集合 Ω={P,Q, R ,PQR }
计算机学院
24
24
▪ Q1=PQR Q1Ω
▪ Q2=P
Q2Ω
▪ Q3=QR
Q3= (Q1-P) (Q2-P)
可满足，进而有Ω0可满足。 ▪ 证毕
计算机学院
计算机学院
21
21
▪ 例题：P(QR)├ (PQ) (PR) 分配律 ▪ (P(QR)) ((PQ) (PR)) ▪ (P(QR)) ((PQ) (PR)) ▪ (PQ) (PR))( P (PR)) (Q (PR)) ▪ (PQ) (PR)P ( P R) (Q P)( QR)
▪ 对一阶逻辑公式，其解释的个数通常是任意多个，丘奇 （A.Church）和图灵（A.M.Turing）在1936年证明了不存 在判定公式是否有效的通用程序。计算机学院
数理逻辑(证明论、递归论、模型论和公理集合论)
数理逻辑(证明论、递归论、模型论和公理集合论)(2010-10-28 00:14:03)转自新浪博客1930年以后，数学逻辑开始成为一个专门学科，得到了蓬勃发展。
哥德尔的两个定理证明之后，希尔伯特的有限主义纲领行不通，证明论出现新的情况，主要有两方面：通过放宽有限主义的限制来证明算术无矛盾性以及把证明形式化、标准化，这些主要是在三十年代完成。
同时哥德尔引进递归函数，发展成递归论的新分支，开始研究判定问题。
而哥德尔本人转向公理集合论的研究，从此出现公理集合论的黄金时代。
五十年代模型论应运而生，它与数学有着密切联系，并逐步产生积极的作用。
1、证明论证明论又称元数学，它研究数学的最基本活动—证明的合理性问题。
研究这类数学基础的问题原来一直是哲学家的事，后来才成为数学家的事。
这个转变发生在1893年弗雷格发表《算术基础规则》之时，后来希尔伯特和他的许多合作者使这种思想发展成一门学科—元数学，目的是用数学方法来研究整个数学理论。
要使数学理论成为一个合适的研究对象，就必须使之形式化。
自从希尔伯特和阿克曼所著《理论逻辑纲要》第一版在1928年出版以来，在实践中用得最多的是具有等式的一阶谓词演算(以及高阶谓词演算)。
许多理论可以用一阶理论来表述，它比较简单方便，具有多种形式。
从基础的观点来看，有两个理论最为重要，因而研究也最多。
这两个理论就是形式化的皮亚诺算术理论与形式化的集合论。
因为大多数观代数学理论都可以在这两个理论范围内发展，所以这两个理论的合理性如果得到证实，也就是向数学的可靠性迈进了一大步。
“希尔伯特计划”无非就是要找到一个有限的证明步骤来证明算术的无矛盾性。
这里“有限”的意义是由法国年轻数学家厄布朗明确提出的，他认为下列条件必须满足：必须只讨论确定的有限数目的对象及函数；这些对象及函数要能确定它们的真值产生协调一致的计算结果；一个对象如不指出如何构造它就不能肯定其存在；必须永远不考虑一个无穷集体中所有对象的集合；一个定理对于一组对象都成立的意思是，对于每个特殊的对象，可以重复所讲的普遍论证，而这普遍论证只能看成是结果特殊论证的原型。
第四章 归结法原理
赫布兰德解释
• 满足以下条件的解释称为赫布兰德解释： (1) I的论域是全体基项组成的集合。 (2) 对每个常元a，aI=a。 (3) 对每个元函数符号f，fI(t1,…tn)=f(t1,…,tn)
归结推演
• 设S是子句集合。如果非空子句序列C1,…,Cn中 的每个子句Ci满足以下条件之一，则称该子句 序列为S的一个归结推演。 (1) Ci在S中； (2) 存在j,k<i使得Ci是Cj和Ck的归结子句。 • 如果S的归结推演C1,…,Cn的最后一个子句Cn是 空子句□，则称C1,…,Cn为S的一个反驳 • 斯科伦范式
前束范式
• 前束范式的定义如下： • 形式为Q1y1…QnynB的公式称为前束范式，其中 n为非负整数，每个Qi是 ∀ 或 ∃ ，B是开公式，y 1,…,yn是不同变元。Q1y1…Qnyn称为该前束范式 的前束，B称为它的母式。 • 不出现存在量词的前束范式称为无 ∃ 前束范式。
文字
• 原子公式或原子公式的否定称为文字。 • 设n是正整数。若A1,…,An是文字，则称A1∨… ∨ An为简单析取式。若B1,…,Bn是简单析取式， 则称B1∧…∧ Bn为合取范式。
斯科伦范式
• 母式是合取范式的无 ∃ 前束范式称为斯科伦范 式。
谓词逻辑的归结法
• • • • • 相反文字 基子句 子句集的满足性 赫布兰德解释 归结推演
归结子句
• 设L1,L2是相反文字，并且分别在子句C1和C2中 出现，称子句(C1-{L1})(C2-{L2})为C1和C2的归 结子句。
反驳
• 如果子句C1,…,Cn序列满足以下条件，则称该子句序列为 子句集合S的一个反驳。 (1) 对每个i≤n，Ci∈S或者存在j, k<i使得Ci是Cj和Ck的归结子 句。 (2) Cn是空子句□。
数理逻辑的基本原理与推理方法
数理逻辑的基本原理与推理方法数理逻辑是一门研究命题、谓词、推理和证明的学科。
它利用符号和数学方法来描述、分析和判断一系列命题之间的关系。
在数理逻辑中，有一些基本的原理和推理方法，可以帮助我们理解和解决问题。
本文将探讨数理逻辑的基本原理和推理方法，以便读者能够更好地理解和运用数理逻辑。
数理逻辑的基本原理包括命题逻辑和谓词逻辑。
命题逻辑是最基本的逻辑系统，研究命题之间的逻辑关系。
一个命题是能够判断真假的陈述句。
在命题逻辑中，我们用符号来表示命题，如P、Q和R。
符号“∧”表示命题的合取（与）、符号“∨”表示命题的析取（或）、符号“→”表示条件（蕴含）以及符号“¬”表示否定。
这些符号可以帮助我们构建命题之间的复合命题，并进行逻辑推理。
在命题逻辑中，有一些基本的推理方法可以帮助我们根据已知命题推导出新的命题。
其中包括析取三段论、假言三段论、摩尔根定律等。
析取三段论是指如果一个命题是两个已知命题的析取，那么这个命题也成立。
例如，如果P成立，Q成立，那么(P∨Q)也成立。
假言三段论是指如果一个命题是一个已知命题的条件，另一个命题是条件成立时所得出的结论，那么这个结论也成立。
例如，如果P成立会导致Q成立，而P成立，那么Q也成立。
摩尔根定律是指命题的否定可以通过互换逻辑运算符，并对子命题进行否定得到。
例如，¬(P∧Q)等价于¬P∨¬Q。
谓词逻辑是一种更为复杂的逻辑系统，用于描述命题中涉及对象的属性和关系。
在谓词逻辑中，我们引入了量词∀和∃，分别表示“对于所有”和“存在”的含义。
谓词逻辑允许我们对命题中的对象进行全称量化和存在量化，并进行逻辑推理。
谓词逻辑的基本原理和推理方法类似于命题逻辑，但涉及到更多的概念和符号。
推理是数理逻辑的核心，它旨在根据已知命题推导出新的命题。
推理方法有很多种，例如直接证明、间接证明和归谬法。
直接证明是一种常见的推理方法，它通过列举命题的前提和规则，逐步推导出结论。
归结原则总结
归结原则总结简介归结原则是一种推理和证明方法，常用于数学和逻辑学中。
它可以将一个复杂的问题归结为一系列更简单的子问题，从而更容易理解和解决。
在归结原则中，我们首先将问题表达为一个或多个命题，然后使用归结推理规则对这些命题进行推理。
通过反复应用归结推理规则，最终可以得到一个完整的证明或解答。
归结推理规则归结推理规则是归结原则的核心。
它包括两个基本规则：归结规则和消解规则。
归结规则归结规则是将复杂的命题归结为更简单的命题的方法。
具体来说，如果我们有一个复合命题A，它可以被归结为两个更简单的命题A1和A2。
归结规则的常见形式包括析取归结和合取归结。
析取归结析取归结规则用于将一个复合命题归结为两个获取其中一个成立的更简单的命题。
设有一个复合命题A，它可以被表示为A1或A2，如果我们可以证明其中之一成立，那么就可以说A成立。
形式化表示如下：A = A1 ∨ A2A1为真或A2为真，则A为真合取归结合取归结规则用于将一个复合命题归结为两个同时成立的更简单的命题。
设有一个复合命题A，它可以被表示为A1和A2，如果我们可以证明A1和A2同时成立，那么就可以说A成立。
形式化表示如下：A = A1 ∧ A2A1为真且A2为真，则A为真消解规则消解规则是归结推理中另一个重要的规则。
它可以用于推导出新的命题，从而进一步简化问题。
消解规则的基本思想是消除归结规则中的冗余部分，从而得到更简洁的表达。
具体来说，消解规则通过删除具有相反符号的命题，产生新的命题。
形式化表示如下：A1 ∨ P¬P ∨ A2———A1 ∨ A2归结原则的应用归结原则在数学和逻辑学中有广泛的应用，特别是在证明和解答复杂问题时。
在数学中，归结原则可以用于证明定理和解决问题。
通过将问题归结为更简单的子问题，我们可以逐步推导出定理的证明或问题的解答。
在逻辑学中，归结原则可以用于构建逻辑推理系统和推理引擎。
通过应用归结推理规则，我们可以自动推理出命题的真值，从而实现自动推理和证明。
大学数学数理逻辑
大学数学数理逻辑数理逻辑是大学数学中的一门重要学科，它研究命题、论证和推理的规律和方法。
数理逻辑在数学、计算机科学、哲学等领域有着广泛的应用。
本文将从数理逻辑的基本概念、命题逻辑和谓词逻辑等方面进行论述，以帮助读者更好地理解和应用数理逻辑。
一、数理逻辑的概念和基本原理数理逻辑，又称形式逻辑，是一种通过形式化的符号系统来研究命题、论证和推理的学科。
它主要关注推理的正确性和有效性，旨在分析命题之间的逻辑关系，并通过推理规则来推断新的结论。
数理逻辑的基本原理包括命题、谓词、量词和推理规则等。
命题是陈述句，可以为真或者假，其真值可以通过逻辑运算进行组合。
谓词是对对象进行描述的函数，通过给定一个或多个对象来判断一个命题的真值。
量词用来量化命题中的变量，包括全称量词和存在量词。
推理规则是根据数理逻辑的规则进行合乎逻辑的推理步骤，如假言推理、略化推理等。
二、命题逻辑命题逻辑是数理逻辑的一个重要分支，它研究命题之间的逻辑关系。
命题逻辑主要包括命题的联结词、真值表和等价演算等。
1. 命题的联结词命题的联结词包括合取（∧）、析取（∨）、蕴含（→）和否定（¬）等，分别表示与、或、蕴含和非的关系。
通过这些联结词，可以对多个命题进行逻辑运算，得到一个新的命题。
2. 真值表真值表是用来列出所有可能的取值情况，并给出联结词的运算结果。
通过真值表，可以判断联结词的真值和命题之间的逻辑关系。
3. 等价演算等价演算是通过代换规则和等价关系，将逻辑表达式转化为等价的形式。
常用的等价演算规则包括分配律、德摩根律等，它们使得逻辑表达式的推导更加简化和便捷。
三、谓词逻辑谓词逻辑是数理逻辑的另一个重要分支，它引入了谓词和量词的概念，用于更精确地描述和推理命题。
谓词逻辑主要包括谓词符号、量词和量词的运用等。
1. 谓词符号谓词符号是用来描述对象的属性或者关系的符号，它通常代表一个函数，通过给定一个或多个参数来判断命题的真值。
谓词符号包括等于（=）、大于（>）等，通过它们可以对对象进行进一步的描述和区分。
归结原理是什么
归结原理是什么归结原理是一种思维方式和分析方法，它是指将复杂的问题或现象归结为简单的基本原理或规律，从而更好地理解和解决问题。
归结原理在科学研究、逻辑推理、问题解决等方面都有着重要的应用价值。
在本文中，我们将深入探讨归结原理的含义、特点以及在实际应用中的重要性。
首先，归结原理的核心思想是将复杂的问题简化为简单的基本原理或规律。
这种简化并不是为了忽略问题的复杂性，而是为了更好地理解和解决问题。
通过归结原理，我们可以将一个看似复杂的问题分解为若干个简单的部分，然后逐个加以分析和解决，最终得到全面而准确的结论。
这种思维方式可以帮助我们理清问题的逻辑关系，找到问题的根本原因，从而更好地应对挑战和解决困难。
其次，归结原理的特点是简洁性和普适性。
简洁性体现在归结原理能够将复杂的问题简化为简单的基本原理或规律，使得问题的分析和解决变得更加清晰和高效。
普适性则表现在归结原理适用于各种不同领域和问题，不受限于特定的学科或领域。
无论是自然科学、社会科学还是工程技术，归结原理都具有普遍的适用性，可以帮助人们更好地理解和解决问题。
最后，归结原理在实际应用中具有重要的意义。
首先，它可以帮助人们更好地理解和应对复杂的现实问题。
通过将复杂问题简化为简单的基本原理或规律，我们可以更好地理清问题的逻辑关系，找到问题的根本原因，从而更好地应对挑战和解决困难。
其次，归结原理可以帮助人们进行科学研究和创新。
在科学研究中，归结原理可以帮助科学家们理清问题的本质和规律，从而推动科学知识的发展和创新。
最后，归结原理还可以帮助人们进行有效的逻辑推理和问题解决。
通过将复杂问题简化为简单的基本原理或规律，我们可以更好地进行逻辑推理和问题分析，从而得出准确而全面的结论。
综上所述，归结原理是一种思维方式和分析方法，它能够帮助人们更好地理解和解决复杂的问题。
归结原理的核心思想是将复杂的问题简化为简单的基本原理或规律，它具有简洁性和普适性，并在实际应用中具有重要的意义。
高级数理逻辑
---------------------------------------------------------15
1.2 数理逻辑的发展过程
第五阶段：公理集合论促进了数理逻辑形式 系统的产生 英国唯心主义哲学家、逻辑学家、数 学家罗素在集合论的研究过程中，于1903 年提出了著名的罗素悖论（数学史上的第 三次危机）。罗素悖论动摇了集合论的基 础，促使人们去研究数学中的矛盾性。从 而提出了公理集合论。公理集合论的产生 和发展，促进了形式系统的产生。
10
1.1 基本概念
语义 涉及符号和符号表达式的涵义。 语法 涉及符号表达式的形式结构，不考虑 任何对语言的解释。
两者既有区别又有联系。
---------------------------------------------------------11
1.2 数理逻辑的发展过程
逻辑学→数理逻辑→形式逻辑→计算逻辑 第一阶段：逻辑学思想的提出 亚里士多德提出建立探索人类推理、 思维原则的学科，从而有了逻辑的概念。
14
1.2 数理逻辑的发展过程
第四阶段：发展为独立的学科 十九世纪末二十世纪初，数理逻辑有 了比较大的发展，1884年，德国数学家弗 雷格出版了《数论的基础》和《符号论》， 在书中引入量词的符号，使得数理逻辑的 符号系统更加完备。对建立这门学科做出 贡献的，还有美国人皮尔斯，他也在著作 中引入了逻辑符号。从而使现代数理逻辑 最基本的理论基础逐步形成，成为一门独 立的学科。
---------------------------------------------------------16
1.2 数理逻辑的发展过程
第六阶段：形式推理自动化的产生 1965年Robinson提出了归结原理 （Principle of Resolution），归结原理提 出了基于形式描述的，利用计算机的推理 方法。从而使机器定理证明和计算机辅助 软件工程得到长足的发展。
1.2 数理逻辑的发展过程
第五阶段：公理集合论促进了数理逻辑形式 系统的产生 英国唯心主义哲学家、逻辑学家、数 学家罗素在集合论的研究过程中，于1903 年提出了著名的罗素悖论（数学史上的第 三次危机）。罗素悖论动摇了集合论的基 础，促使人们去研究数学中的矛盾性。从 而提出了公理集合论。公理集合论的产生 和发展，促进了形式系统的产生。
10
1.1 基本概念
语义 涉及符号和符号表达式的涵义。 语法 涉及符号表达式的形式结构，不考虑 任何对语言的解释。
两者既有区别又有联系。
---------------------------------------------------------11
1.2 数理逻辑的发展过程
逻辑学→数理逻辑→形式逻辑→计算逻辑 第一阶段：逻辑学思想的提出 亚里士多德提出建立探索人类推理、 思维原则的学科，从而有了逻辑的概念。
14
1.2 数理逻辑的发展过程
第四阶段：发展为独立的学科 十九世纪末二十世纪初，数理逻辑有 了比较大的发展，1884年，德国数学家弗 雷格出版了《数论的基础》和《符号论》， 在书中引入量词的符号，使得数理逻辑的 符号系统更加完备。对建立这门学科做出 贡献的，还有美国人皮尔斯，他也在著作 中引入了逻辑符号。从而使现代数理逻辑 最基本的理论基础逐步形成，成为一门独 立的学科。
---------------------------------------------------------16
1.2 数理逻辑的发展过程
第六阶段：形式推理自动化的产生 1965年Robinson提出了归结原理 （Principle of Resolution），归结原理提 出了基于形式描述的，利用计算机的推理 方法。从而使机器定理证明和计算机辅助 软件工程得到长足的发展。
第四章 归结法原理
• • • •
x(R(x) Q(x))， x(R(x) Q(x))， R(b) Q(b) {R(b), Q(b)}
计算机学院
计算机学院
21 21
(4) 构造子句集S= SA∪SB∪SC (5) 构造以下反驳： • C1 = P(c) • C2 = R(x) S(c, x) • C3 = P(y) Q(z) S(y, z) • C4 = R(b), • C5 = Q(b) • C6= Q(z) S(c, z) C1, C3 ├res C6 计算机学院 • C7= S(c, b) C2, C4 ├res C7 • C8= Q(b) C6, C7 ├res C8 • C9= □ C5, C8 ├res □ 证毕。
归结子句不唯一
计算机学院 1Leabharlann 10反驳 定义：设S是子句集合，如果子句序列C1, …, Cn满足
如下条件，则称子句序列C1,…,Cn为子句集合S的一
个反驳。 (1) 对于每个1≤k<n， • CkS，或者 • Ck是Ci和Cj的归结子句，i<k，j<k。
(2) Cn是□。
计算机学院
计算机学院
计算机学院
计算机学院
5 5
定义
子句集：子句的有限集合称为子句集.
• 子句集{{P1,1, …, P1,m}, … , {Pn,1, …, Pn,m}}，
表示公式(P1,1 … P1,m) … (Pn,1 … Pn,m)的 闭包 • 子句集合{{P(x), Q(y)}, {P(c),计算机学院 Q(z)}}表示Skolem 范式xyz((P(x)Q(y)) (P(c) Q(z)))
• yz(P(y) R(z) L(y,z)) • {P(y) R(z) L(y,z)}
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
▪ 例如，Q1是子句pqr，Q2是子句pqws，q和q 是相反文字，子句prws是Q1和Q2的归结子句。
▪ 例如，Q1是子句q，Q2是子句q，q和q是相反文字， 子句□是Q1和Q2的归结子句。
▪ 例如，Q1是子句pqr，Q2是子句pws，在子句Q1 和Q2中没有相反文字出现，子句Q1Q2，即 pqrws不是Q1和Q2的归结子句。
▪ 有σ(q1…qn r1…rm)=1，即σ(Q)=1。 ▪ 证毕
反驳
▪ 定义：设Ω是子句集合，如果子句序列 Q1,…,Qn满足如下条件，则称子句序列 Q1,…,Qn为子句集合Ω的一个反驳。
▪ (1).对于每个1≤k<n，QkΩ
• Qk是Qi和Qj的归结子句，i<k，j<k。
▪ (2). Qn是□。
▪ Q1=q
Q1Ω
▪ Q2=q
Q2Ω
▪ Q3=□
▪ 因此，Q1, Q2,Q3是反驳.
▪ (3).根据命题逻辑紧致性定理，若子句集合Ω 不可满足，则有有穷子句集合Ω0，Ω0Ω，使 得Ω0是不可满足的。
▪ 若有穷子句集合Ω0是不可满足的，则Ω0中的子句必 出现相反文字。
▪ 假设有穷子句集合Ω0是不可满足的，且Ω0中的子句 不出现相反文字，那么，对于Ω0中子句的每个文字 qk，有赋值函数σ使得σ(qk)=1，因此，σ(Ω0)=1，Ω0是 可满足的，这样与Ω0是不可满足的相矛盾。
机械式方法
▪ 若证明Q1,…,Qn|=R，只要证明Q1…QnR 不可满足。
▪ 机械式证明：
• 公式Q1…QnR的合取范式； • 合取范式的所有简单析取范式，即Ω； • 证明Ω不可满足
▪ 则有Q1,…,Qn|=R。 ▪ 机械式地证明Ω不可满足是关键问题
子句与空子句
▪ 定义：原子公式及其否定称为文字(literals)； 文字的简单析取范式称为子句，不包含文字 的子句称为空子句，记为□。
▪ 开创性的工作是赫伯特·西蒙（H. A. Simon）和艾伦· 纽威尔（A. Newel）的 Logic Theorist。
▪ 机械定理证明的主要突破是1965年由鲁宾逊（ J.A.Robinson）做出的，他建立了所谓归结原理，使机械 定理证明达到了应用阶段。
▪ 归结法推理规则简单, 而且在逻辑上是完备的, 因而成为 逻辑式程序设计语言Prolog的计算模型。
▪ 对一阶逻辑公式，其解释的个数通常是任意多个，丘奇 （A.Church）和图灵（A.M.Turing）在1936年证明了不存 在判定公式是否有效的通用程序。
• 如果一阶逻辑公式是有效的，则存在通用程序可以验证它 是有效的
• 对于无效的公式这种通用程序一般不能终止。
▪ 1930年希尔伯特（Herbrand）为定理证明建立了一种重 要方法，他的方法奠定了机械定理证明的基础。
主要内容
▪ 机械证明简介 ▪ 命题逻辑归结法 ▪ 谓词逻辑归结法
基本原理
▪ Q1,…,Qn|=R，当且仅当Q1…QnR不可满足 ▪ 证明Q1,…,Qn|=R
• (1). Q1…QnR化为合取范式； • (2). 构建Ω子句集合，Ω为Q1…QnR合取范式
的所有简单析取范式组成集合； • (3).若Ω不可满足，则Q1,…,Qn|=R。
Qi, Qj|=Qk。因此，Ω|=Qk。 ▪ (3).因为Qn=□，所以有Qn-1和Qk是相反文字，不妨设
是q和q。
▪ 因此，Ω|=q，Ω|=q。Ω|=qq，Ω不可满足。
▪ 又证：设子句集合Ω是不可满足的。
▪ (1).不妨设子句集合Ω不含永真式。因为从Ω中去掉永真 式不改变Ω的不可满足性。
▪ (2).若Ω含有相反文字，不妨设是q，则
▪ 例如
• p、q、r和s都是文字 • 简单析取式pqrs是子句
–字p、q、r和s
• 因为pqrs不是简单析取范式，所以 pqrs不是子句。
▪ 定义：设Q是简单析取范式，q是Q的文字，在Q中 去掉文字q，记为Q-q。
▪ 例如，Q是子句pqrs，Q - q是简单析取范式 p rs。
归结子句
▪ 定义：设Q1,Q2是子句，q1和q2是相反文字，并且在子句 Q1和Q2中出现，称子句(Q1-q1)(Q2-q2)为Q1和Q2的归结 子句。
▪ 例题：(QR)Q├Q
皮尔斯律
▪ 证明：
▪ 因为((QR)Q)Q的合取范式Q(RQ)Q，所以 子句集合Ω={Q, RQ, Q}
▪ Q1= Q ▪ Q2= Q ▪ Q3=□
Q1Ω Q2Ω Q3= (Q1-Q) (Q2-Q)
▪ 定理：子句集合Ω是不可满足的当且仅当存在Ω的反 驳。
▪ 证明：设为Q1,…,Qn是反驳。 ▪ (1).若QkΩ，Ω|=Qk. ▪ (2).若Ω|=Qi，Ω|=Qj并且Qk是Qi, Qj的归结子句，则
▪ 定理：如果子句Q是Q1, Q2的归结子句，则Q1, Q2|=Q ▪ 证明： ▪ 设Q1=pq1…qn，Q2=pr1…rm。 ▪
▪ 赋值函数σ(Q1)=1，即σ(pq1…qn)=1， σ(p) σ(q1…qn)=1.
▪ 赋值函数σ(Q2)=1，即σ(pr1…rm)=1， σ(p) σ(r1…rm)=1.
数理逻辑归结法原理
Hale Waihona Puke 主要内容▪ 机械证明简介 ▪ 命题逻辑归结法 ▪ 谓词逻辑归结法
▪ 自动推理早期的工作主要集中在机器定理证明。
▪ 机械定理证明的中心问题是寻找判定公式是否是有效的 通用程序。
▪ 对命题逻辑公式，由于解释的个数是有限的，总可以建 立一个通用判定程序，使得在有限时间内判定出一个公 式是有效的或是无效的。
▪ 设Ω0有n种相反文字，有相反文字q和q ，Ω0中的子句分为三类， • 一类是有文字q的子句， • 另一类是有文字q的子句， • 再一类是没有文字q和q的子句
▪ Ωq ={ qPk| qPkΩ}，Ωq ={qQk| qQkΩ}， ΩC=Ω-Ωq-Ωq
▪ |Ωq |=m1，|Ωq |=m2，|ΩC|=m3。 ▪ ΩR={ Pi Qj| qPiΩq, qQjΩq} ▪ Ω1 =ΩCΩR ▪ Ω1有n-1个命题变元。 ▪ 若有rΩ1并且rΩ1，则存在反驳。
▪ 若Ωq Ωq ΩC 不可满足，则Ω1 =ΩCΩR不可满足。
▪ 若Ω1是可满足的，则有赋值函数σ，使得σ(Ω1)=1。 ▪ 如果σ(Pi)=1，i=1,...,m1，那么有σ'(q)=0，而其他命题变元
▪ 例如，Q1是子句q，Q2是子句q，q和q是相反文字， 子句□是Q1和Q2的归结子句。
▪ 例如，Q1是子句pqr，Q2是子句pws，在子句Q1 和Q2中没有相反文字出现，子句Q1Q2，即 pqrws不是Q1和Q2的归结子句。
▪ 有σ(q1…qn r1…rm)=1，即σ(Q)=1。 ▪ 证毕
反驳
▪ 定义：设Ω是子句集合，如果子句序列 Q1,…,Qn满足如下条件，则称子句序列 Q1,…,Qn为子句集合Ω的一个反驳。
▪ (1).对于每个1≤k<n，QkΩ
• Qk是Qi和Qj的归结子句，i<k，j<k。
▪ (2). Qn是□。
▪ Q1=q
Q1Ω
▪ Q2=q
Q2Ω
▪ Q3=□
▪ 因此，Q1, Q2,Q3是反驳.
▪ (3).根据命题逻辑紧致性定理，若子句集合Ω 不可满足，则有有穷子句集合Ω0，Ω0Ω，使 得Ω0是不可满足的。
▪ 若有穷子句集合Ω0是不可满足的，则Ω0中的子句必 出现相反文字。
▪ 假设有穷子句集合Ω0是不可满足的，且Ω0中的子句 不出现相反文字，那么，对于Ω0中子句的每个文字 qk，有赋值函数σ使得σ(qk)=1，因此，σ(Ω0)=1，Ω0是 可满足的，这样与Ω0是不可满足的相矛盾。
机械式方法
▪ 若证明Q1,…,Qn|=R，只要证明Q1…QnR 不可满足。
▪ 机械式证明：
• 公式Q1…QnR的合取范式； • 合取范式的所有简单析取范式，即Ω； • 证明Ω不可满足
▪ 则有Q1,…,Qn|=R。 ▪ 机械式地证明Ω不可满足是关键问题
子句与空子句
▪ 定义：原子公式及其否定称为文字(literals)； 文字的简单析取范式称为子句，不包含文字 的子句称为空子句，记为□。
▪ 开创性的工作是赫伯特·西蒙（H. A. Simon）和艾伦· 纽威尔（A. Newel）的 Logic Theorist。
▪ 机械定理证明的主要突破是1965年由鲁宾逊（ J.A.Robinson）做出的，他建立了所谓归结原理，使机械 定理证明达到了应用阶段。
▪ 归结法推理规则简单, 而且在逻辑上是完备的, 因而成为 逻辑式程序设计语言Prolog的计算模型。
▪ 对一阶逻辑公式，其解释的个数通常是任意多个，丘奇 （A.Church）和图灵（A.M.Turing）在1936年证明了不存 在判定公式是否有效的通用程序。
• 如果一阶逻辑公式是有效的，则存在通用程序可以验证它 是有效的
• 对于无效的公式这种通用程序一般不能终止。
▪ 1930年希尔伯特（Herbrand）为定理证明建立了一种重 要方法，他的方法奠定了机械定理证明的基础。
主要内容
▪ 机械证明简介 ▪ 命题逻辑归结法 ▪ 谓词逻辑归结法
基本原理
▪ Q1,…,Qn|=R，当且仅当Q1…QnR不可满足 ▪ 证明Q1,…,Qn|=R
• (1). Q1…QnR化为合取范式； • (2). 构建Ω子句集合，Ω为Q1…QnR合取范式
的所有简单析取范式组成集合； • (3).若Ω不可满足，则Q1,…,Qn|=R。
Qi, Qj|=Qk。因此，Ω|=Qk。 ▪ (3).因为Qn=□，所以有Qn-1和Qk是相反文字，不妨设
是q和q。
▪ 因此，Ω|=q，Ω|=q。Ω|=qq，Ω不可满足。
▪ 又证：设子句集合Ω是不可满足的。
▪ (1).不妨设子句集合Ω不含永真式。因为从Ω中去掉永真 式不改变Ω的不可满足性。
▪ (2).若Ω含有相反文字，不妨设是q，则
▪ 例如
• p、q、r和s都是文字 • 简单析取式pqrs是子句
–字p、q、r和s
• 因为pqrs不是简单析取范式，所以 pqrs不是子句。
▪ 定义：设Q是简单析取范式，q是Q的文字，在Q中 去掉文字q，记为Q-q。
▪ 例如，Q是子句pqrs，Q - q是简单析取范式 p rs。
归结子句
▪ 定义：设Q1,Q2是子句，q1和q2是相反文字，并且在子句 Q1和Q2中出现，称子句(Q1-q1)(Q2-q2)为Q1和Q2的归结 子句。
▪ 例题：(QR)Q├Q
皮尔斯律
▪ 证明：
▪ 因为((QR)Q)Q的合取范式Q(RQ)Q，所以 子句集合Ω={Q, RQ, Q}
▪ Q1= Q ▪ Q2= Q ▪ Q3=□
Q1Ω Q2Ω Q3= (Q1-Q) (Q2-Q)
▪ 定理：子句集合Ω是不可满足的当且仅当存在Ω的反 驳。
▪ 证明：设为Q1,…,Qn是反驳。 ▪ (1).若QkΩ，Ω|=Qk. ▪ (2).若Ω|=Qi，Ω|=Qj并且Qk是Qi, Qj的归结子句，则
▪ 定理：如果子句Q是Q1, Q2的归结子句，则Q1, Q2|=Q ▪ 证明： ▪ 设Q1=pq1…qn，Q2=pr1…rm。 ▪
▪ 赋值函数σ(Q1)=1，即σ(pq1…qn)=1， σ(p) σ(q1…qn)=1.
▪ 赋值函数σ(Q2)=1，即σ(pr1…rm)=1， σ(p) σ(r1…rm)=1.
数理逻辑归结法原理
Hale Waihona Puke 主要内容▪ 机械证明简介 ▪ 命题逻辑归结法 ▪ 谓词逻辑归结法
▪ 自动推理早期的工作主要集中在机器定理证明。
▪ 机械定理证明的中心问题是寻找判定公式是否是有效的 通用程序。
▪ 对命题逻辑公式，由于解释的个数是有限的，总可以建 立一个通用判定程序，使得在有限时间内判定出一个公 式是有效的或是无效的。
▪ 设Ω0有n种相反文字，有相反文字q和q ，Ω0中的子句分为三类， • 一类是有文字q的子句， • 另一类是有文字q的子句， • 再一类是没有文字q和q的子句
▪ Ωq ={ qPk| qPkΩ}，Ωq ={qQk| qQkΩ}， ΩC=Ω-Ωq-Ωq
▪ |Ωq |=m1，|Ωq |=m2，|ΩC|=m3。 ▪ ΩR={ Pi Qj| qPiΩq, qQjΩq} ▪ Ω1 =ΩCΩR ▪ Ω1有n-1个命题变元。 ▪ 若有rΩ1并且rΩ1，则存在反驳。
▪ 若Ωq Ωq ΩC 不可满足，则Ω1 =ΩCΩR不可满足。
▪ 若Ω1是可满足的，则有赋值函数σ，使得σ(Ω1)=1。 ▪ 如果σ(Pi)=1，i=1,...,m1，那么有σ'(q)=0，而其他命题变元