第1篇-数理逻辑之谓词逻辑.ppt

第1篇 数理逻辑 主讲人：任长安 计算机与信息科学系 2009.07 引言 逻辑学是研究推理过程之规律的科学。 数理逻辑则是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁的表达出各种推理的逻辑关系，因此数理逻辑又称为符号逻辑或理论逻辑。 数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。 主要内容 1 命题逻辑 2 一阶逻辑 第2章 一阶逻辑 命题逻辑是逻辑理论的基础，是以命题为最小单元来分析研究推理理论的，现在来看如下日常生活中一个常见的推理。 所有学生必须上课； 他是学生； 所以，他必须上课。 符号化为： (p∧q) ? r， 显然这是一个推理，但是是不正确的推理。日常推理却是正确的。 第2章 一阶逻辑 问题在于，其正确性在命题逻辑中没有得到反映，即没有对命题“所有学生必须上课”再作分解，所以无法说明关于“学生”的任何事情。如果把“必须上课”，同“所有学生”分离开来，就有可能对任何特定的“学生”加以论述，显示出前提和结论在形式结构方面的内在联系，从而也就能认识到这种推理的形式和规律。在这一类推理中，各命题之间的逻辑关系不是体现在简单命题之间，而是体现在命题结构的更深层次，对此命题逻辑是无能为力的，这正是命题逻辑的局限性。 第2章 一阶逻辑 问题在于，其正确性在命题逻辑中没有得到反映，即没有对命题“所有学生必须上课”再作分解，所以无法说明关于“学生”的任何事情。如果把“必须上课”，同“所有学生”分离开来，就有可能对任何特定的“学生”加以论述，显示出前提和结论在形式结构方面的内在联系，从而也就能认识到这种推理的形式和规律。在这一类推理中，各命题之间的逻辑关系不是体现在简单命题之间，而是体现在命题结构的更深层次，对此命题逻辑是无能为力的，这正是命题逻辑的局限性。 第2章 一阶逻辑 在考察、研究命题和推理时，为了研究这类本质性的问题，有必要对简单命题作进一步分析，分清其中的主词、谓词等，并考虑到一般和个别、全称和存在，研究它们的形式结构、逻辑性质及其之间的的逻辑关系，从而总结出正确的推理形式和规则。这部分内容是基于谓词分析的逻辑， 本章主要讨论谓词逻辑的基本概念。 第2章 一阶逻辑 主要内容： 2.1 谓词与量词 2.2 一阶语言 2.3 一阶逻辑的等值演算 2.4 一阶逻辑的推理理论 2.1 谓词与量词 谓词逻辑是以谓词为基础的，类似以命题为基础的命题逻辑首先从命题开始，我们这里也必须先从谓词开始。 1、 谓词 在谓词逻辑中，需要将简单命题拆开，作为最为简单的命题的陈述句，至少有主语和谓语组成，谓词就是句子中相当谓语部分的词，而把主语对应的部分称为个体词。 个体词：一个简单命题中表示研究对象即主体或客体 个体常元、个体变元 个体域：个体变元的取值范围。 2.1 谓词与量词 谓词：表示一个个体词性质的或多个个体词之间关系的词。 谓词常项：表示具体关系或性质的谓词 谓词变项：不表示具体关系或性质的谓词。 示例： 张华是学生。 李明是学生。 两个句子的共同属性：“…是学生”，这是谓词，表明个体词的性质。 2.1 谓词与量词 n元谓词：含有n个个体变元的谓词 0元谓词：不含有任何个体变元的谓词。 示例： H(a)，a：张华，H(x): “…是学生” H(x)是1元谓词，不是命题；H(a)是0谓词，是命题。 注：可以用0元谓词符号化谓词逻辑，可转化为命题。 示例：小魏乘机去深圳； 设a：小魏， b：飞机，c：深圳；P(x, y, z)：x乘y去z； P(a, b, c) 2.1 谓词与量词 示例 全班学生都表现不错。 用谓词逻辑符号化，显然这是一个命题，直到目前我们还只能用0元谓词来符号化，假设全班学生有m个，为a1, a2, …, am。对于某个学生如a1，“a1表现不错”应该符号化为P(a1) P(a1) ∧ P(a2) ∧ … ∧ P(am) 由于并不知道全班学生的具体个数，而且得到的命题形式很长，所以采用简化的表示方法，引入全程量词的概念： ?x P(x) ? P(a1) ∧ P(a2) ∧ … ∧ P(am) 2.1 谓词与量词 全称量词是量词的一种，从这可以看到量词可以将谓词转化成命题。 2、 量词 （注：个体与谓词之间的数量关系是由量词来体现的。） A 全称 全称量化：对谓词量化而形成命题“对所有的个体，谓词为真” 全称量词：全称量化所用量词为全称量词，以?表示，形成的命题形式为?x P(x)，即“对所有的x，P(x)为真” 2.1 谓词与量词 我们必须注意到，个体变元是存在个体域的，在上述全称量词符号化的过程中，个体域就是全班学生，如