05-L.01 谓词逻辑的推理结构
- 格式：pdf
- 大小：294.80 KB
- 文档页数：5
下载文档原格式
合集下载
谓词 基本推理公式
谓词基本推理公式
谓词逻辑是逻辑学中的一种形式系统，它使用谓词来表达命题的性质和关系。
基本推理公式是谓词逻辑中的一些基本规则，用于推导命题的真假。
以下是几个常用的谓词逻辑基本推理公式：
1. 交换律：A→B ↔ B→A
2. 结合律：(A→B)→C ↔ A→(B→C)
3. 吸收律：A→(B∧C) ↔ (A→B)∧(A→C)
4. 分配律：(A∧B)→C ↔ A→(B→C)
5. 重写律：A→B ↔ ¬B→¬A
6. 否定引入律：¬(A∧B) ↔ (¬A∧¬B)
7. 否定消去律：¬¬A ↔ A
8. 双条件引入律：A↔B ↔ (A→B)∧(B→A)
9. 双条件消去律：A↔B ↔ (A∧B)∨(¬A∧¬B)
10. 全称量词引入律：∀x(P(x)) ↔ P(y)/y (y属于某个集合)
11. 存在量词引入律：∃x(P(x)) ↔ P(y)/y (y属于某个集合)
这些基本推理公式是谓词逻辑的基础，可以用于推导其他命题的真假。
在具体使用时，需要根据命题的具体情况进行选择和应用。
谓词逻辑 基本推理公式
谓词逻辑基本推理公式
谓词逻辑的基本推理公式包括：
1. 全称量词规则：如果个体域中每一个个体具有性质A，则存在一个个体具有性质A。
即，能找出一个就表示存在。
公式为A ( c ) ⇒∃ x A
( x )A(c)\Rightarrow\exists xA(x)A(c)⇒∃xA(x)。
规则成立的条件是c是个体域中某个确定的个体，代替c的x不在A©中出现过。
2. 存在量词规则：如果个体域中存在个体具有性质A，则至少存在一个个体具有性质A。
公式为∃ x A ( x ) ∀ y A ( y )\exists xA(x)\forall yA(y)∃x A(x)∀yA(y)。
3. 归结推理：将公式中的量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变。
4. 代入规则：把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号。
5. 解释（赋值）：谓词公式A的个体域D是非空集合，则每一个常项指定D中一个元素；每一个n元函数指定Dn到D的一个函数；每一个n元谓词指定Dn到{0,1}的一个谓词。
按这个规则做的一组指派，称为A的一个解释或赋值。
以上是谓词逻辑的基本推理公式，通过这些公式可以推导出更复杂的逻辑推理结果。
谓词逻辑的推理规则和证明方法
谓词逻辑的推理规则和证明方法谓词逻辑是一种用于描述命题关系以及推理过程的数学逻辑系统。
在谓词逻辑中，我们使用谓词来表示性质或关系，通过逻辑连接词进行命题的组合和推理。
本文将介绍谓词逻辑中常用的推理规则和证明方法。
一、谓词逻辑的基本符号与概念在谓词逻辑中，我们使用以下基本符号：1. 命题变量：用大写字母（如P，Q，R）表示命题变量，表示一个命题。
2. 常量：用小写字母（如a，b，c）表示常量，表示一个具体的个体。
3. 谓词：用小写字母或小写字母加括号（如P(x)，Q(y)）表示谓词，表示一个性质或关系。
4. 量词：∀表示全称量词（对于所有的），∃表示存在量词（存在一个），用于描述一组对象。
在谓词逻辑中，我们还会用到以下概念：1. 公式：一个命题是谓词逻辑中的公式。
2. 全称量化：∀xP(x)表示谓词P(x)对于所有的x成立。
3. 存在量化：∃xP(x)表示谓词P(x)存在一个x使得成立。
二、推理规则在谓词逻辑中，我们常用以下推理规则进行逻辑推理：1. 求取命题的否定：将命题的否定写为¬P(x)，表示该命题不成立。
2. 逻辑与的消除：若已知P(x)∧Q(x)，则可以得到P(x)和Q(x)。
3. 逻辑或的消除：若已知P(x)∨Q(x)，则可以得到P(x)或Q(x)。
4. 蕴含的引入：若已知P(x)成立，则P(x)→Q(x)也成立。
5. 蕴含的消除：若已知P(x)→Q(x)和P(x)，则可以得到Q(x)。
6. 等价的引入：若已知P(x)↔Q(x)成立，则P(x)和Q(x)等价。
7. 等价的消除：若已知P(x)↔Q(x)和P(x)，则可以得到Q(x)。
三、证明方法在谓词逻辑中，我们可以使用以下证明方法进行推理证明：1. 直接证明：假设命题P(x)为真，通过推理规则逐步推导出Q(x)为真，从而得到P(x)→Q(x)。
2. 反证法：假设命题P(x)为假，通过推理规则逐步推导出Q(x)为假，从而得到¬P(x)→¬Q(x)。
逻辑学基础知识点导图总结
逻辑学基础知识点导图总结导图一：逻辑学基础知识概述- 逻辑学定义与范畴- 逻辑学的研究对象与目的- 逻辑学的历史渊源- 逻辑学的发展现状与前景导图二：命题逻辑- 命题及其分类- 命题的逻辑联结词- 命题联结词的真值表- 命题联结词的逻辑等值演算- 命题的逻辑等值式- 命题逻辑的推理规则导图三：谓词逻辑- 谓词及其分类- 谓词逻辑的语言- 谓词逻辑中的量词- 谓词逻辑的真值表- 谓词逻辑的语法结构- 谓词逻辑的推理规则导图四：命题与谓词逻辑的关系- 命题逻辑与谓词逻辑的对比- 命题逻辑与谓词逻辑的转换- 命题逻辑与谓词逻辑的应用导图五：逻辑演绎- 演绎推理的基本结构- 演绎推理的形式与内容- 演绎推理的规则与方法- 演绎推理的应用领域导图六：逻辑归纳- 归纳推理的基本结构- 归纳推理的形式与内容- 归纳推理的规则与方法- 归纳推理的应用领域导图七：逻辑谬误- 逻辑谬误的概念与分类- 逻辑谬误的原因与问题- 逻辑谬误的检测与排除- 逻辑谬误的修正与改进导图八：逻辑推理与实践- 逻辑推理的实践意义- 逻辑推理的应用范畴- 逻辑推理的现实影响- 逻辑推理的未来发展逻辑学基础知识点总结逻辑学是研究思维、推理和认识规律的学科，它通过对思维规律的研究，帮助人们提高思维能力、推理能力和判断能力。
逻辑学的发展经历了命题逻辑和谓词逻辑两个阶段，它们分别研究命题之间的关系和谓词之间的关系，并在实际应用中发挥重要作用。
在命题逻辑中，命题是对事物或观点的表述，通过不同的逻辑联结词组合成复合命题，根据不同的真值表来确定其真假，通过逻辑等值式和推理规则进行推理。
谓词逻辑是对个体和属性的描述，引入量词和谓词来描述性质和关系，通过真值表和推理规则来进行推理。
命题逻辑和谓词逻辑之间有密切的联系，它们在应用中常常相互转化，丰富了逻辑学的研究内容。
逻辑分类是逻辑学中一个重要的研究领域，通过对演绎推理和归纳推理的研究，帮助人们更好地理解事物，提高认识水平。
谓词逻辑的基本原理和推理方法
谓词逻辑的基本原理和推理方法谓词逻辑是数理逻辑的一种形式，它主要研究陈述句的真值和推理关系。
本文将探讨谓词逻辑的基本原理和推理方法，以帮助读者进一步理解和运用这一重要的逻辑体系。
一、谓词逻辑的基本原理谓词逻辑是由Richard Montague在20世纪50年代提出的，它是一种基于谓词和量词的逻辑形式。
谓词是描述个体和关系的词汇，而量词则表示个体的范围。
基于这些基本元素，谓词逻辑涉及命题的真值判断和逻辑推理。
1. 命题的真值判断在谓词逻辑中，命题的真值可以通过公式化的方式进行判断。
具体而言，谓词逻辑使用谓词和个体常量构建公式，通过赋值给个体常量和谓词变量来确定命题的真假。
这种方法可以使我们更加准确地判断复杂命题的真值。
2. 逻辑运算符谓词逻辑中常用的逻辑运算符包括否定、合取、析取、蕴涵和双条件。
通过这些逻辑运算符，我们可以对命题进行复合运算，并获得更加精确的逻辑推理。
3. 量词的运用量词在谓词逻辑中起着重要作用，它用来限定命题的个体范围。
通常使用的量词有普遍量词和存在量词，分别表示“对于所有的”和“存在一个”。
量词的运用使得我们能够对具有普遍性或存在性的命题进行精确的描述和推理。
二、谓词逻辑的推理方法谓词逻辑在推理中有着广泛的应用。
下面介绍几种常用的推理方法。
1. 求解真值通过给定谓词和量词的赋值，可以求解命题的真值。
这种方法可以通过证明或反证法来进行，根据不同的情况选择合适的推理策略。
2. 归结推理归结推理是一种通过消解规则进行推理的方法。
它通过将多个命题进行归结，从而得到新的命题。
这种方法在人工智能领域得到广泛应用。
3. 等词推理等词推理是一种通过等词的等同性进行推理的方法。
它通过推导两个等词相等的命题，从而间接地得出新的命题。
等词推理在代数逻辑和数学中有着重要的应用。
4. 形式化推理形式化推理是一种将命题转化为形式逻辑公式来进行推理的方法。
通过将推理过程形式化，可以减少人为因素的干扰，提高推理的准确性和可靠性。
谓词逻辑的等值和推理演算
• 例2:人皆有死,孔子是人,所以孔子有死.
(x)(Man(x)→Mortal(x)) Man(Confucius) → Mortal(Confucius)
• 例3:若有一种又高又胖旳人,则有一种高个子而 且有一种胖子.
(x)(Tall(x)Fat(x)) → (x)Tall(x) (x)Fat(x)
(x)P(x, f(x)) = P(1, f(1)) P(2, f(2)) • 两者明显不等值.但在(不)可满足旳意义下两者
是一致旳.
Lu Chaojun, SJTU
20
谓词逻辑旳推理
• 命题逻辑中有关推理形式、重言蕴涵以 及基本旳推理公式旳讨论和所用旳术语 都可引入到谓词逻辑中,并可把命题逻辑 旳推理作为谓词逻辑旳推理旳一种部分 来看待.
• 前束范式定理:任一公式都有与之等值旳 PNF.
Lu Chaojun, SJTU
11
怎样转化成PNF
1.消去和↔ 2.否定词内移
– 应用De Morgan律
3.约束变元易名(假如必要旳话) 4.量词左移
– 应用分配等值式
Lu Chaojun, SJTU
12
例:求PNF
((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = ((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (z)Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y) Q(z,b) R(x)) = (x)(z)(y)(P(a,x,y) Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y)Q(z,b)R(x)(pp))
(x)(Man(x)→Mortal(x)) Man(Confucius) → Mortal(Confucius)
• 例3:若有一种又高又胖旳人,则有一种高个子而 且有一种胖子.
(x)(Tall(x)Fat(x)) → (x)Tall(x) (x)Fat(x)
(x)P(x, f(x)) = P(1, f(1)) P(2, f(2)) • 两者明显不等值.但在(不)可满足旳意义下两者
是一致旳.
Lu Chaojun, SJTU
20
谓词逻辑旳推理
• 命题逻辑中有关推理形式、重言蕴涵以 及基本旳推理公式旳讨论和所用旳术语 都可引入到谓词逻辑中,并可把命题逻辑 旳推理作为谓词逻辑旳推理旳一种部分 来看待.
• 前束范式定理:任一公式都有与之等值旳 PNF.
Lu Chaojun, SJTU
11
怎样转化成PNF
1.消去和↔ 2.否定词内移
– 应用De Morgan律
3.约束变元易名(假如必要旳话) 4.量词左移
– 应用分配等值式
Lu Chaojun, SJTU
12
例:求PNF
((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = ((x)(y)P(a,x,y)(x)((y)Q(y,b)R(x))) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)(y)P(a,x,y) (x)((y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (y)Q(y,b) R(x)) = (x)((y)P(a,x,y) (z)Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y) Q(z,b) R(x)) = (x)(z)(y)(P(a,x,y) Q(z,b) R(x)) = (x)(y)(z)(P(a,x,y)Q(z,b)R(x)(pp))
(逻辑学课程课件)谓词逻辑
例如：在F（x）和G（x，y）中，x，y都是自由个体变项； 在∀x F（x）和∃x ∀yG（x，y）中，x，y都是约束个体变项；∀xG（x，y）中，x是约束个体变项，y是 自由个体变项。
这样，为了确定一个个体变项是自由的还是约束词的辖域】。我们约定紧靠量词的括号内的符号表达式 是该量词的辖域，括号外的则不是；如果紧靠量词没有括号，那么，靠近量词的不包 含逻辑联结词的表达式是该量词的辖域，其他的则不是。例如：
命题形式经过解释，就成为命题。
一个命题形式的解释自然不是惟一的，而是无穷的。在不同的解释下，从命题 形式得到的命题可以出现不同的真假情况。
一个命题形式，如果在任一解释下都得到一个真命题，则称为【普遍有效式】。 一个命题形式，如果在至少一种解释下能得到真命题，则称为【可满足式】。
一个命题形式，如果在任一解释下都不能得到一个真命题，则称为【不可满足 式】。
二、量词
一个包含个体变项的谓词表达式不是命题。例如，例句（1）F（x）断定“x是 红的”，但由于x是个体变项，因而F（x）没有真假，不是命题。如何使F（x）这样 的表达式具有真假呢？有两种方法：
第一，用个体常项取代个体变项。例如令a表示“这朵牡丹”，那么F（a）就表 示“这朵牡丹是红的”，这是命题，有真假。这种方法称为解释，后面将对此进一步 解释。
上述各式的逻辑性质是直观的。但对较复杂的命题形式，难以凭直观作出断定， 这就需要新的方法。这正是谓词逻辑所要研究的。
有了谓词和量词的抽象以后，我们就获得了对自然语言及其表达的思维进行逻 辑分析和符号刻画的更有力的工具。
第二节 自然语言的谓词表达式
一、直言命题的表达式
将下列语句符号化： （1）所有的人都是要死的。 （2）有的天鹅是黑的。 （3）所有的宗教都不是科学。 （4）有的新闻报道不是真实的。 在（1）中，令P（x）表示“x是人”，D（x）表示“x是要死的”。则（1）式的 符号表达式是： ∀x （P（x）→ D（x）） 它的含义是，对所有客体x而言，如果x是人，那么x是要死的。注意，这里的含义 仅仅是：对所有客体x而言，如果x是人，那么x是要死的；至于作为人的x是否存在， 没有得到断定，即也可能存在，也可能不存在。 这样的表达是否反映了自然语言中全称命题的原意呢？确实，自然语言中当我们 断定“所有的人都是要死的”，除了断定上述符号式所断定的含义外，事实上我们还 断定“人是存在的”。但这不具有一般性。例如：“所有不受外力作用的物体都保持 匀速直线运动。”这个命题仅仅断定：对所有物体而言，如果它不受外力作用，那么 它保持匀速直线运动；至于不受外力作用的物体是否存在，没有得到断定。事实上， 这样的物体是不存在的。这说明，全称命题的语言形式自身并不包含主项存在的断定； 有的全称命题所包含的主项存在的断定，是语境附加的，例如，在词项逻辑中就是这 样。但是，为了不失一般性，全称命题的符号表达式不应包含主项存在的形式刻画。
这样，为了确定一个个体变项是自由的还是约束词的辖域】。我们约定紧靠量词的括号内的符号表达式 是该量词的辖域，括号外的则不是；如果紧靠量词没有括号，那么，靠近量词的不包 含逻辑联结词的表达式是该量词的辖域，其他的则不是。例如：
命题形式经过解释，就成为命题。
一个命题形式的解释自然不是惟一的，而是无穷的。在不同的解释下，从命题 形式得到的命题可以出现不同的真假情况。
一个命题形式，如果在任一解释下都得到一个真命题，则称为【普遍有效式】。 一个命题形式，如果在至少一种解释下能得到真命题，则称为【可满足式】。
一个命题形式，如果在任一解释下都不能得到一个真命题，则称为【不可满足 式】。
二、量词
一个包含个体变项的谓词表达式不是命题。例如，例句（1）F（x）断定“x是 红的”，但由于x是个体变项，因而F（x）没有真假，不是命题。如何使F（x）这样 的表达式具有真假呢？有两种方法：
第一，用个体常项取代个体变项。例如令a表示“这朵牡丹”，那么F（a）就表 示“这朵牡丹是红的”，这是命题，有真假。这种方法称为解释，后面将对此进一步 解释。
上述各式的逻辑性质是直观的。但对较复杂的命题形式，难以凭直观作出断定， 这就需要新的方法。这正是谓词逻辑所要研究的。
有了谓词和量词的抽象以后，我们就获得了对自然语言及其表达的思维进行逻 辑分析和符号刻画的更有力的工具。
第二节 自然语言的谓词表达式
一、直言命题的表达式
将下列语句符号化： （1）所有的人都是要死的。 （2）有的天鹅是黑的。 （3）所有的宗教都不是科学。 （4）有的新闻报道不是真实的。 在（1）中，令P（x）表示“x是人”，D（x）表示“x是要死的”。则（1）式的 符号表达式是： ∀x （P（x）→ D（x）） 它的含义是，对所有客体x而言，如果x是人，那么x是要死的。注意，这里的含义 仅仅是：对所有客体x而言，如果x是人，那么x是要死的；至于作为人的x是否存在， 没有得到断定，即也可能存在，也可能不存在。 这样的表达是否反映了自然语言中全称命题的原意呢？确实，自然语言中当我们 断定“所有的人都是要死的”，除了断定上述符号式所断定的含义外，事实上我们还 断定“人是存在的”。但这不具有一般性。例如：“所有不受外力作用的物体都保持 匀速直线运动。”这个命题仅仅断定：对所有物体而言，如果它不受外力作用，那么 它保持匀速直线运动；至于不受外力作用的物体是否存在，没有得到断定。事实上， 这样的物体是不存在的。这说明，全称命题的语言形式自身并不包含主项存在的断定； 有的全称命题所包含的主项存在的断定，是语境附加的，例如，在词项逻辑中就是这 样。但是，为了不失一般性，全称命题的符号表达式不应包含主项存在的形式刻画。
探究谓词逻辑的基本概念和语法
探究谓词逻辑的基本概念和语法谓词逻辑是一种形式化的逻辑系统，用于研究命题中谓词的逻辑关系和语义含义。
它是数理逻辑的一个重要分支，广泛应用于哲学、计算机科学和语言学等领域。
本文将探究谓词逻辑的基本概念和语法，帮助读者更好地理解和运用这一逻辑系统。
一、谓词逻辑的基本概念谓词逻辑主要研究命题形式中的谓词，谓词是对主体进行性质、状态或关系的描述。
在谓词逻辑中，谓词通常用大写字母或字母组合表示，例如P、Q、R等，而个体常用小写字母表示。
一个命题被称为谓词命题，当它包含一个或多个谓词，例如“S(x)”、“P(x, y)”等。
在谓词命题中，个体的取值范围可以是特定的集合，也可以是无限的。
谓词逻辑通过引入量词来处理命题的普遍性和存在性，常用的量词有全称量词和存在量词。
全称量词表示所有个体都具有某一性质或满足某一关系，通常用符号∀表示；存在量词则表示存在至少一个个体满足某一条件，常用符号∃表示。
量词可以用来对谓词进行限定和描述。
二、谓词逻辑的语法谓词逻辑的语法规则主要包括谓词、量词和命题连接词，以及括号等符号。
1. 谓词符号：谓词符号用来表示性质、状态或关系。
在谓词逻辑中，每个谓词符号都需要指定其所属的领域。
2. 个体变量：个体变量用来表示个体，通常用小写字母表示。
在一个命题中，个体变量可以是任意的个体。
3. 量词符号：量词符号用来表示命题的普遍性或存在性。
全称量词和存在量词分别表示所有和存在至少一个个体满足某一条件。
4. 命题连接词：命题连接词用来连接多个命题，通常包括逻辑与、逻辑或、逻辑非等。
逻辑与的符号为∧，逻辑或的符号为∨，逻辑非的符号为¬。
5. 括号：括号用来标记子命题，帮助确定命题的结构和范围。
三、谓词逻辑的推理规则谓词逻辑通过推理规则来推导和验证命题的真假。
常用的推理规则包括全称推理、存在引入等。
全称推理规则可以根据全称量词对命题进行推理，例如当∀x(P(x)→Q(x))为真时，可以推出∀xP(x)→∀xQ(x)为真。
命题逻辑与谓词逻辑的基本结构与形式
命题逻辑与谓词逻辑的基本结构与形式逻辑是一门研究思维规律和推理方法的学科，其在数学、哲学、计算机科学等领域中有着广泛的应用。
命题逻辑和谓词逻辑是逻辑学中的两个重要分支，它们分别研究命题和谓词的逻辑关系。
本文将介绍命题逻辑和谓词逻辑的基本结构与形式。
命题逻辑是研究命题之间的逻辑关系的一种形式系统。
命题是陈述句，可以是真或假的陈述。
命题逻辑通过引入逻辑运算符，如“非”、“与”、“或”等，来描述命题之间的逻辑关系。
逻辑运算符可以用符号表示，如“¬”表示非，“∧”表示与，“∨”表示或。
通过逻辑运算符的组合，可以构建出复杂的命题，形成命题逻辑的基本结构。
命题逻辑的基本形式是命题的复合形式。
例如，“如果A成立，则B也成立”可以表示为“A→B”，其中“→”表示蕴含关系。
命题逻辑的推理过程是基于逻辑运算符的规则进行的。
例如，根据蕴含的传递性，如果“A→B”和“B→C”成立，则可以推出“A→C”。
命题逻辑的推理过程是严格的，只要逻辑规则正确，推理的结果必然是正确的。
谓词逻辑是研究谓词之间的逻辑关系的一种形式系统。
谓词是带有变量的命题，它可以表示为“P(x)”或“Q(x, y)”等形式，其中变量可以是任意对象。
谓词逻辑通过引入量词，如“∀”和“∃”，来描述谓词之间的逻辑关系。
量词可以用来表达“对于所有”和“存在某个”的意义。
通过谓词和量词的组合，可以构建出复杂的谓词，形成谓词逻辑的基本结构。
谓词逻辑的基本形式是谓词的复合形式。
例如，“对于所有的x，P(x)成立”可以表示为“∀xP(x)”，其中“∀”表示全称量词。
谓词逻辑的推理过程是基于量词和谓词的规则进行的。
例如，根据全称量词的分配律，如果“∀x(P(x)∧Q(x))”成立，则可以推出“∀xP(x)∧∀xQ(x)”成立。
谓词逻辑的推理过程也是严格的，只要逻辑规则正确，推理的结果必然是正确的。
命题逻辑和谓词逻辑在逻辑学中有着重要的地位。
命题逻辑是一种简单而直观的逻辑形式，适用于描述简单的命题关系。
逻辑学 谓词逻辑
第十章 谓词逻辑
第一节 谓词逻辑概述
一、命题逻辑与谓词逻辑 二、个体词与谓词 三、量词
一、命题逻辑与谓词逻辑
通过前面关于命题逻辑的学习，我们知道命题逻 辑是关于联结词的推理理论。在命题逻辑中，简 单命题被当做基本单位来讨论，简单命题分为： 主项、谓项、联项、量项，对其内部结构不再分 析。如，
如果某甲作案，那么他一定有作案动机， 某甲没有作案动机， 所以，某甲没作案。 这个推理的根据就是关于“如果，那么”的推导 规则。这种关于联结词的推理理论，就是命题逻 辑。
而谓词逻辑和命题逻辑不一样，在谓词逻辑中，简单 命题不是被当作基本单位来讨论，而是要讨论其内部 结构，以此作为出发点展开推演。例如， 所有的作案者都有作案动机， 某甲没有作案动机， 所以，某甲不是作案者。 这个推理的前提和结论都是简单命题，推理的根据主 要涉及量词。这种关于量词的推理理论，现代逻辑称 为谓词逻辑。 谓词逻辑是命题逻辑的发展。与命题逻辑不同，它把 简单命题加以分析，区别出哪些是个体词，哪些是谓 词，哪些是量词，抽象出它们的形式，然后研究这些 命题形式的逻辑性质和关系，找出有效推理的形式和 规律。考察和研究这一部分的逻辑理论，就构成了谓 词逻辑。
3.个体词、谓词的符号化 对于一个简单命题而言，至少可将其分解为两部分： 个体词、谓词。那么，如何将个体词和谓词用符号化 来表示呢？ 我们总是在一定范围内讨论个体的性质、个体之间的 关系。表示个体词的符号一般由个体变元和个体常项。 个体变元表示一定范围内的不确定个体，记为小写的： x,y,z,…;x1,x2,x3,…; 个体常项表示一定范围内确定的个体，记为小写的： a,b,c,…; 个体变元的变化范围即变域，逻辑上一般称为论域或 个体域，记为D。个体词就是指称D中个体的语词。
第一节 谓词逻辑概述
一、命题逻辑与谓词逻辑 二、个体词与谓词 三、量词
一、命题逻辑与谓词逻辑
通过前面关于命题逻辑的学习，我们知道命题逻 辑是关于联结词的推理理论。在命题逻辑中，简 单命题被当做基本单位来讨论，简单命题分为： 主项、谓项、联项、量项，对其内部结构不再分 析。如，
如果某甲作案，那么他一定有作案动机， 某甲没有作案动机， 所以，某甲没作案。 这个推理的根据就是关于“如果，那么”的推导 规则。这种关于联结词的推理理论，就是命题逻 辑。
而谓词逻辑和命题逻辑不一样，在谓词逻辑中，简单 命题不是被当作基本单位来讨论，而是要讨论其内部 结构，以此作为出发点展开推演。例如， 所有的作案者都有作案动机， 某甲没有作案动机， 所以，某甲不是作案者。 这个推理的前提和结论都是简单命题，推理的根据主 要涉及量词。这种关于量词的推理理论，现代逻辑称 为谓词逻辑。 谓词逻辑是命题逻辑的发展。与命题逻辑不同，它把 简单命题加以分析，区别出哪些是个体词，哪些是谓 词，哪些是量词，抽象出它们的形式，然后研究这些 命题形式的逻辑性质和关系，找出有效推理的形式和 规律。考察和研究这一部分的逻辑理论，就构成了谓 词逻辑。
3.个体词、谓词的符号化 对于一个简单命题而言，至少可将其分解为两部分： 个体词、谓词。那么，如何将个体词和谓词用符号化 来表示呢？ 我们总是在一定范围内讨论个体的性质、个体之间的 关系。表示个体词的符号一般由个体变元和个体常项。 个体变元表示一定范围内的不确定个体，记为小写的： x,y,z,…;x1,x2,x3,…; 个体常项表示一定范围内确定的个体，记为小写的： a,b,c,…; 个体变元的变化范围即变域，逻辑上一般称为论域或 个体域，记为D。个体词就是指称D中个体的语词。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
−
离散数学基础
2017-11-19•定义：谓词逻辑的推理结构
−设有谓词公式 A、B，若在令 A 为真的任一解释下，B 亦为真，则说 B 是 A 的逻辑推论，或称推理结构 A├ B 是正确的（或者有效的），记为 A ⇒ B。
•例1：所有的整数都是有理数，所有的有理数都是实数，所以所有的整数都是实
数。
−解：设 P(x)：x 是整数。
Q(x)：x 是有理数。
R(x)：x 是实数。
形式化： ① (∀x)(P(x) →Q(x))
②(∀x)(Q(x) →R(x))
③(∀x)(P(x) →R(x))
推理结构： ①, ② ├ ③
•例2：人总是要死的，苏格拉底是人，所以苏格拉底也是要死的。
−解：设 P(x)：x 总是要死的。
Q(x)：x 是人。
形式化： ① (∀x)(Q(x) →P(x))
②Q(苏格拉底)
③P(苏格拉底)
推理结构： ①, ② ├ ③
•例3：有一个人又高又胖，所以必有一个高个子和一个胖子。
−解：设论域为人的集合
P(x)：x 是高的。
Q(x)：x 是胖的。
推理结构：
(∃x)(P(x)∧Q(x)) ├ (∃x)P(x)∧(∃x)Q(x)
•定理：演绎定理
−设谓词公式 A、B，如果从 A 应用推理规则得到 B，并且在推出过程中，A 中
的自由变量保持不变，则A→B 是普遍有效的。
−由于普遍有效性的不可判定性，在谓词逻辑中应用推理规则更为重要。
•推理定理
−若干常用的正确的推理形式：
(1)(∀x)P(x)∨(∀x)Q(x) ⇒ (∀x)(P(x)∨Q(x))
(2)(∃x)(P(x)∧Q(x)) ⇒ (∃x)P(x)∧(∃x)Q(x)
(3)(∀x)(P(x)→Q(x)) ⇒ (∀x)P(x)→(∀x)Q(x)
(4)(∀x)(P(x)→Q(x)) ⇒ (∃x)P(x)→(∃x)Q(x)
(5)(∀x)(∀y)P(x, y) ⇒ (∃y)(∀x)P(x, y)
(6)(∃x)(∀y)P(x, y) ⇒ (∀y)(∃x)P(x, y)
(7)(∀x)(∃y)P(x, y) ⇒ (∃x)(∃y)P(x, y)
•推理定理
−(3) 证：(∀x)(P(x)→Q(x)) ⇒ (∀x)P(x)→(∀x)Q(x)
»设 (∀x)(P(x)→Q(x))=T
»当 (∀x)P(x)=T时，对任意 x0，有P(x0)=T。
»对此 x0，由假设知，P(x0)→Q(x0)=T
»故此时只能 Q(x0)=T
»从 x0 的任意性得 (∀x)Q(x)=T
»即 (∀x)P(x)→(∀x)Q(x)=T
»故上述推理形式是有效的。
•推理定理
−(5) 证： (∀x)(∀y)P(x, y) ⇒ (∃y)(∀x)P(x, y)
»设 (∀x)(∀y)P(x, y)=T
»即任意的 x 与所有的 y 都有 P(x, y)=T
»则对任意的 x 与某一固定的 y0，都有 P(x, y0)=T
»即 (∀x)P(x, y0)=T
»故 (∃y)(∀x)P(x, y)=T
»即上述推理形式是有效的。
•推理规则
−在谓词逻辑的推理中，可以直接引用命题逻辑的推理规则。
我们还需要建立一些新的推理规则处理与个体和量词相关的推理过程。
−(1) 全称量词消去 US
»① (∀x)A(x) ⇒ A(y)
–假设 y 不在 A(x) 中约束出现
»② (∀x)A(x) ⇒ A(c)
–假设 c 是个体域中的任一常量
−(2) 全称量词引入 UG
»A(y) ⇒ (∀x)A(x)
–y 具有任意性，并假设 x 不在 A(y) 中约束出现 −(3) 存在量词消去 ES
»(∃x)A(x) ⇒ A(c)
–c 是个体域中的某一常量，且未出现在 A(x) 以及此前的证明序列中。
»例： (∃x)A(x, c) ⇒ A(c, c) 不成立
»例：证明序列
(i) (∃x)A(x) 前提
(i+1) A(c) ES
(i+2) (∃x)B(x) 前提
(i+3) B(c) ES
是错误的。
−(4) 存在量词引入 EG
»A(c) ⇒ (∃x)A(x)
–设 x 不在 A(c) 中出现
−(5) 分离、代入和置换规则
»必须保证变换发生前后公式形式的一致性（符合合式公式的定义）。
−(6) 其他推理公式
»应用谓词逻辑的7条推理定理或直接使用命题逻辑中讨论的14条推理定
律。
•演绎证明的形式结构
−例：证明 (∀x)(P(x)→Q(x)), P(苏格拉底) ⇒ Q(苏格拉底)
−证：
(1)(∀x)(P(x) → Q(x)) P
(2)P(苏格拉底) → Q(苏格拉底) US
(3)P(苏格拉底) P
(4)Q(苏格拉底) T(2)(3), I
•演绎证明的形式结构
−例：证明 (∃x)P(x)→(∀x)(P(x)∨Q(x)→R(x)), (∃x)P(x) ⇒ (∃x)(∃y)(R(x)∧R(y))
−证：
(1)(∃x)P(x)→(∀x)(P(x)∨Q(x)→R(x)) P
(2)(∃x)P(x) P
(3)(∀x)(P(x)∨Q(x)→R(x)) T(1)(2), I
(4)P(c) T(2),ES
(5)P(c)∨Q(c) T(4),I
(6)P(c)∨Q(c)→R(c) T(3),US
(7)R(c) T(5)(6),I
(8)(∃x)R(x) T(7),EG
(9)(∃y)R(y) T(7),EG
(10)(∃x)R(x)∧(∃y)R(y) T(8)(9),I
(11)(∃x)(R(x)∧(∃y)R(y)) T(10),I
(12)(∃x)(∃y)(R(x)∧R(y)) T(11),I
•演绎证明的形式结构
−例：设 P(x, y)：x > y。
已知前提 (∀x)(∃y)P(x, y)，下列推理是否正确？
(1) (∀x)(∃y)P(x, y) P
(2) (∃y)P(z, y) T(1),US
(3) P(z, b) T(2),ES
(4) (∀z)P(z, b) T(3),UG
(5) P(b, b) T(4),US
所以， b > b
−解：由已知前提 (∀x)(∃y)P(x, y)， (∃y) 在 (∀x) 的辖域内，y 的存在性对 x 形成依赖。
这种依赖并非函数依赖，称之为Skolem 依赖，写成 y= f Skolem(x)，f Skolem 为 Skolem 函数。
故在公式 (3) 中，b 对z 形成依赖：b = f Skolem(z) −要特别注意的是，当 ∃ 处于∀的辖域内时，须先消去该 ∃ ，且须引入 Skolem 函数描述依赖关系。
如上例：
(1) (∀x)(∃y)P(x, y)
(2) (∀x)P(x, f Skolem(x))
(3) P(b, f Skolem(b))
−例：有的病人喜欢任何医生；没有病人喜欢庸医；所以没有医生是庸医。
设 P(x)：x 是病人。
Q(x)：x 是庸医。
D(x)：x 是医生。
L(x, y)：x 喜欢 y。
前提：(∃x)(P(x)∧(∀ y)(D(y)→L(x, y)))
¬(∃x)(P(x)∧(∃ y)(Q(y)∧L(x, y)))
结论：¬(∃x)(D(x)∧Q(x))
•演绎证明的形式结构
(1)(∃x)(P(x)∧(∀y)(D(y)→L(x, y))) P
(2)P(c)∧(∀y)(D(y)→L(c, y)) T(1),ES
(3)¬(∃x)(P(x)∧(∃y)(Q(y)∧L(x, y))) P
(4)(∀x)(P(x)→(∀y)(Q(y)→¬L(x, y))) T(3),I
(5)P(c)→(∀y)(Q(y)→¬L(c, y))) T(4),US
(6)P(c) T(2),I
(7)(∀y)(Q(y)→¬L(c, y)) T(5)(6),I
(8)Q(y)→¬L(c, y) T(7),US
(9)L(c, y)→¬Q(y) T(8),I
(10)(∀y)(D(y)→L(c, y)) T(2),I
(11)D(y)→L(c, y) T(10),US
(12)D(y)→ ¬ Q(y) T(11)(9),I
(13)(∀y)(D(y)→ ¬Q(y)) T(12),UG
(14)(∀x)(D(x)→ ¬Q(x)) T(13),I
(15)¬(∃x)(D(x)∧Q(x)) T(14),I
下一节内容提示
−谓词逻辑的归结原理。