离散数学第二章 谓词逻辑.ppt

第第二二章章 谓词逻辑谓词逻辑离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社前言命题逻辑对于反映在自然语言中的逻辑思维进行了精确的形式化描述，能够对一些比较复杂的逻辑推理，用形式化方法进行分析。在命题逻辑中，把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。但这对科学中的演绎推理和数学中的推理是不够的，有些推理用命题逻辑就难以确切地表示出来。要求n在命题逻辑中，试进行下列推理:“苏格拉底三段论”：凡人都是要死的，P苏格拉底是人，Q所以苏格拉底是要死的。R(PQ)R命题逻辑中，命题被当作一个基本的，不可分割的单位，只研究由原子命题和联接词所组成的复合命题，没有研究命题内部的内部结构以及 命题之间的内在关系。教材及资料n类似的还有很多，例如：所有的人都要呼吸，李华是人，所以李华要呼吸。所有的正整数都大于0，3是正整数，所以3大于0。n本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。PART PART 0101基本概念和表示主要内容PART PART 0 02 2PART PART 0 03 3谓词逻辑的等价式与蕴涵式PART PART 0 04 4PART PART 0 05 5格的定义与性质谓词逻辑的翻译与解释谓词逻辑中的推论理论2.1 基本概念和表示在命题逻辑中，命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。在谓词逻辑中，为揭示命题内部结构及不同命题的内部结构关系，就按照这两部分对命题进行分析，并且把主语称为个体或者客体，把谓语称为谓词。62.1 基本概念和表示n 定义2.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。n 个体，是指可以独立存在的事物。它可以是抽象的概念，也可以是一个具体的实体。如计算机，自然数，智能，情操等。表示特定的个体，称为个体常元，以a，b，c，或带下标的ai，bi，ci，表示。任何个体的变化都有一个范围，这个变化范围称为个体域(或论域)。个体域可以是有限的，也可以是无限的。所有个体域的总和叫作全总个体域。以某个个体域为变化范围的变元叫个体变元。以x，y，z，或者xi，yi，zi，表示。7个体、谓词和谓词表示2.1 基本概念和表示n谓词，当与一个个体相联系时，刻画了个体的性质；当与两个或多个个体相联系时，刻画了个体之间的关系。通常都用大写英文字母，如P，Q，R，来表示。n例如有以下两个命题：小明是大学生。刘亮是大学生。其中“是大学生”是谓词，“小明”、“刘亮”是个体。谓词在这里是用来刻划个体的性质的。如用S(x)表示“x是大学生”，a表示李洪，b表示张宾，则上述三个命题可以表示成S(a)，S(b)。8个体、谓词和谓词表示2.1 基本概念和表示n定义2.2 一个原子命题用一个谓词（如P）和n个有次序的个体常元（如a1，a2，an）表示成P(a1，a2，an)，称它为该原子命题的谓词形式或命题的谓词形式。应注意：命题的谓词形式中个体的出现顺序影响命题的真值，不能随意变动。否则真值会变化，如上面所举的例子中L(b，a，c)为假。n在谓词中包含的个体数目称为谓词的元数。与一个个体变元相联系的谓词叫一元谓词，与多个个体变元相联系的谓词叫多元谓词。例如S(x)是一元谓词，L(x，y)是二元谓词。9个体、谓词和谓词表示2.1 基本概念和表示n 一个n元谓词常可以表示成P(x1，x2，xn)，一般讲它是一个以变元的个体域为定义域，以T,F为值域的n元泛函。常称P(x1，x2，xn)为n元谓词变元命名式。它还不是一个命题，仅告诉我们该谓词变元是n元的以及个体变元之间的顺序如何。只有将其中的谓词赋予确定的含意，给每个个体变元都代之以确定的个体后，该谓词才变成一个确定的命题，有确定的真值。10个体、谓词和谓词表示2.1 基本概念和表示n定义2.3 全称量词、存在量词、存在唯一量词。（1）符号 称为全称量词符，用来表达“对所有的”、“任意的”、“每一个”等词语。“(x)P(x)”表示命题：“对于个体域中所有个体x，谓词P(x)均为T”。其中“(x)”称为全称量词，读作“对于所有的x”。谓词P(x)称为全称量词(x)的辖域或作用范围。（2）符号称为存在量词符，用来表达“存在一些”、“对于一些”、“至少有一个”等词语。“(x)Q(x)”表示命题:“在个体域中存在某些个体使谓词Q(x)为T”。其中“(x)”称为存在量词，读作“存在x”。谓词Q(x)称为存在量词(x)的辖域或存在范围。（3）符号!称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语。“(!x)R(x)”表示命题：“在个体域中恰好有一个个体使谓词R(x)为T”。其中“(!x)”称为存在量词，读作“恰有一个x”。谓词R(x)称为存在量词(!x)的辖域或存在范围。全称量词、存在量词和存在唯一量词统称量词。量词是由逻辑学家Fray引入的，有了量词之后，用逻辑符号表示命题的能力大大增强。11量词2.1 基本概念和表示n例2.1 使用量词、谓词表示下列命题：（1）每个自然数都是实数。（2）一些大学生想继续攻读研究生。（3）所有大学生都热爱祖国。解：令S(x)：x是自然数，R(x)：x是实数，G(x)：x是大学生，I(x)：x想继续攻读研究生，L(x)：x热爱祖国。则各命题分别表示为：（1）(x)(S(x)R(x)（2）(x)(G(x)I(x)（3）(x)(G(x)L(x)谓词前加上量词，称为谓词的量化。12量词2.1 基本概念和表示n当一个一元谓词常量命名式的个体域确定之后，经过量化，将被转化为一个命题，可以确定其真值。将谓词转化为命题的方法有两种：将谓词中的个体变元全部换成确定的个体；使谓词量化。注意：（1）量词本身不是一个独立的逻辑概念，可以用，联结词代替。设个体域是S：S=a1，a2，an由量词的定义不难看出，对任意谓词A(x)有:(x)A(x)A(a1)A(a2)A(an)(x)A(x)A(a1)A(a2)A(an)上述关系可以推广至n的情形。（2）由量词所确定的命题的真值与个体域有关。如上述命题(x)Q(x)的真值，当个体域是有理数或整数时为T；当个体域是自然数时为F。（3）一般来讲，量词的先后次序不可随意交换。13量词2.1 基本概念和表示n定义2.4 谓词逻辑的合式公式：（1）原子谓词公式是合式的公式；（2）若A是合式的公式，则A也是合式的公式；（3）若A和B都是合式的公式，则AB，AB，AB，AB也都是合式的公式；（4）如果A是合式的公式，x是任意变元，且A中无(x)或(x)出现，则(x)A(x)和(x)A(x)都是合式的公式；（5）当且仅当有限次使用规则(1)-(4)由逻辑联结词、圆括号构成的有意义的字符串是合式的公式。14合式谓词公式2.1 基本概念和表示n以下字符串均是谓词逻辑中合式公式的例子：A(x)；B(x)；(x)A(x)；(x)B(x);A(x)；(x)A(x)(x)B(x)(x)B(x)。n下面的字符串不是谓词逻辑中合法的合式公式。(A(x)(x)B(x)（括号不配对）(x)A(x)(x)B(x)（其中逻辑联结词缺少运算）15合式谓词公式2.1 基本概念和表示n 定义2.5 给定一个谓词公式A，其中有一部分公式形如(x)B(x)或(x)B(x)，则称它为A的x约束部分，称B(x)为相应量词的作用域或者辖域。在辖域中，x的所有出现为约束出现，x称为约束变元；B中不是约束出现的其他变元的出现称为自由出现，这些个体变元称为自由变元。对于给定的谓词公式，能够准确地判断它的辖域、约束变元和自由变元是很重要的。16自由变元和约束变元2.1 基本概念和表示n通常，一个量词的辖域是某公式A的一部分，称为A的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体来说。（1）若量词后有括号，则括号内的子公式就是该量词的辖域；（2）若量词后无括号，则与该量词邻接的子公式为该量词的辖域。n判断给定公式A中的个体变元是约束变元还是自由变元，关键是要看它在A中是约束出现还是自由出现。17自由变元和约束变元2.1 基本概念和表示n例2.2 指出下列合式公式中的量词辖域、个体变元的约束出现和自由出现。（1）(x)(P(x)(y)Q(x，y)（2）(x)H(x)L(x，y)（3）(x)(y)(P(x，y)Q(y，z)(x)R(x，y)解：（1）(x)的辖域是(P(x)(y)Q(x，y)，(y)的辖域是Q(x，y)。对于(y)辖域而言，y为约束出现，x为自由出现。对于(x)辖域而言，x和y均为约束出现。（2）(x)的辖域是H(x)，x为约束出现，L(x，y)中的x和y都为自由出现。（3）在(x)(y)(P(x，y)Q(y，z)中，(x)和(y)的辖域分别为(y)(P(x，y)Q(y，z)和(P(x，y)Q(y，z)，显然x和y为约束出现，z为自由出现。(x)的辖域为R(x，y)，x约束出现而y自由出现。在整个式子中，y既约束出现又自由出现。18自由变元和约束变元2.1 基本概念和表示n一个谓词P(x)的量化，就是从变元x的整个个体域着眼，对性质P(x)所作的一个全称判断或特称判断。其结果是将谓词变成一个命题。所以，(x)和(x)可以看成是一个消元运算。对于多元谓词来说，仅使其中一个变元量化仍不能将谓词变成命题。若n元谓词P(x1，x2，xn)经量化后仍有k个自由变元，则降为一个k元谓词Q(y1，y2，yn)(kn)。只有经过n次量化使其中的所有变元都成为约束变元时，n元谓词才成为一个命题。n所以，一般情况下给定一个谓词公式A(x)，仅表明在该公式中只有一个自由变元x，但并不限制在该公式中还存在若干约束变元。19自由变元和约束变元PART PART 0101基本概念和表示主要内容PART PART 0 02 2PART PART 0 03 3谓词逻辑的等价式与蕴涵式PART PART 0 04 4PART PART 0 05 5格的定义与性质谓词逻辑的翻译与解释谓词逻辑中的推论理论2.2 谓词逻辑的翻译与解释n把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化。一般来说，符号化的步骤如下。（1）正确理解给定命题。必要时把命题改叙，使其中每个原子命题及原子命题之间的关系能明显表达出来。（2）把每个原子命题分解成个体、谓词和量词。在全总论域中讨论时，要给出特性谓词。（3）找出适当量词。注意全称量词后跟条件式，存在量词后跟合取式。（4）用适当联结词把给定命题表示出来。21谓词逻辑的翻译2.2 谓词逻辑的翻译与解释n例2.3 试将命题：“任何整数都是实数”符号化。解：根据实际问题的需要，首先定义谓词如下。令I(x)：x是整数。R(x)：x是实数。于是问题可符号化为：(x)(I(x)R(x)。n例2.4 将语句：“今天有雨雪，有些人会摔跤”符号化。解：本语句可理解为：“若今天下雨又下雪，则存在x，x是人且x会摔跤”。令R：今天下雨，S：今天下雪，M(x)：x是人，F(x)：x会摔跤，则本语句可表示为：RS(x)(M(x)F(x)。22谓词逻辑的翻译2.2 谓词逻辑的翻译与解释n例2.5 试将语句：“有一个大于10的偶数”符号化。解：根据实际问题的需要，首先定义谓词如下。E(x)：x是偶数。G(x，y)：x大于y。于是问题可符号化为：(x)(E(x)G(x，10)。n例2.6 将命题：“没有最大的自然数”符号化。解：命题中“没有最大的”显然是对所有的自然数而言，所以可以理解为：“对于所有的x，如果x是自然数，则一定还有比x大的自然数”，再具体点，即“对于所有的x，如果x是自然数，则一定存在y，y也是自然数且y比x大”。令N(x)：x是自然数，G(x，y)：x大于y。则原命题表示为：(x)(N(x)(y)(N(y)G(y，x)。23谓词逻辑的翻译2.2 谓词逻辑的翻译与解释n例2.5 试将语句：“有一个大于10的偶数”符号化。解：根据实际问题的需要，首先定义谓词如下。E(x)：x是偶数。G(x，y)：x大于y。于是问题可符号化为：(x)(E(x)G(x，10)。n例2.6 将命题：“没有最大的自然数”符号化。解：命题中“没有最大的”显然是对所有的自然数而言，所以可以理解为：“对于所有的x，如果x是自然数，则一定还有比x大的自然数”，再具体点，即“对于所有的x，如果x是自然数，则一定存在y，y也是自然数且y比x大”。令N(x)：x是自然数，G(x，y)：x大于y。则原命题表示为：(x)(N(x)(y)(N(y)G(y，x)。24谓词逻辑的翻译2.2 谓词逻辑的翻译与解释n定义2.6 设A的个体域是D，如果用一组谓词常量、命题常量和D中的个体及函数符号（将它们简记为I）代换公式A中相应的变元，则该公式A转化成一个命题，可以确定其真值（记作P）。称I为公式A在D中的解释（或指派），称P为公式A关于解释I的真值。25谓词逻辑的解释2.2 谓词逻辑的翻译与解释n给定一个谓词公式A，它的个体域是D，若在D中无论怎样构成A的解释，其真值都为T，则称公式A在D中是永真的；如果公式A对任何个体域都是永真的，则称公式A是永真的；如果公式A对于任何个体域中的任何解释都为F，则称公式A为永假的（或不可满足的）；若公式A不是永假的，则公式A是可满足的。n给定两个谓词公式A和B，D是它们共同的个体域，若 在D中是永真式，则称遍及D有 ；若D是全总个体域，则称。若 且 ，则称 。26谓词逻辑的解释PART PART 0101基本概念和表示主要内容PART PART 0 02 2PART PART 0 03 3谓词逻辑的等价式与蕴涵式PART PART 0 04 4PART PART 0 05 5格的定义与性质谓词逻辑的翻译与解释谓词逻辑中的推论理论2.3 谓词逻辑的等价式与蕴涵式n下面介绍谓词逻辑中一些特有的等价式和永真蕴涵式，它们是由于量词的引入而产生的。无论对有限个体域还是无限个体域，他们都是正确的。（1）量词转化律设x的个体域为S=a1,a2,an。令 表示对整个被量化的命题 的否定，而不是对 的否定，于是有：A(a1)A(a2)A(an)同样可有：(x)A(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)(x)A(x)上述等价关系推广到无限个体域后仍成立。28量词转化律2.3 谓词逻辑的等价式与蕴涵式（2）量词辖域扩张及收缩律设P中不出现约束变元x，则有：用同样的方法可以证明以下3个等价式也成立。29量词转化律2.3 谓词逻辑的等价式与蕴涵式（3）量词分配律30量词分配律2.3 谓词逻辑的等价式与蕴涵式总结以上讨论，并用类似的方法，可得出谓词逻辑中特有的一些重要等价式和永真蕴涵式如下。31重要等价式2.3 谓词逻辑的等价式与蕴涵式32重要永真蕴涵式2.3 谓词逻辑的等价式与蕴涵式为了便于读者记忆，我们给出了B1B8的图解表示（见图2.1）。使用前面给出的等价式和永真蕴涵式就可以证明上述的永真式。33PART PART 0101基本概念和表示主要内容PART PART 0 02 2PART PART 0 03 3谓词逻辑的等价式与蕴涵式PART PART 0 04 4PART PART 0 05 5格的定义与性质谓词逻辑的翻译与解释谓词逻辑中的推论理论2.4 谓词逻辑中的推理理论1约束变元的改名规则谓词公式中约束变元的名称是无关紧要的，(x)P(x)和(y)P(y)具有相同的意义。需要时可以改变约束变元的名称。但必须遵守以下改名的规则。（1）欲改名之变元应是某量词作用范围内的变元，且应同时更改该变元在此量词辖域内的所有约束出现，而公式的其余部分不变。（2）新的变元符号应是此量词辖域内原先没有使用过的。35推理规则2.4 谓词逻辑中的推理理论2自由变元的代入规则自由变元也可以改名，但必须遵守以下代入规则。（1）欲改变自由变元x的名，必改x在公式中的每一处自由出现。（2）新变元不应在原公式中以任何约束形式出现。3命题变元的代换规则用任一谓词公式 代换永真公式B中某一命题变元 的所有出现，所得到的新公式 仍然是永真式（但在 的个体变元中不应有B中的约束变元出现），并有 。36推理规则2.4 谓词逻辑中的推理理论4取代规则设 都是含个自由变元的谓词公式，且A 是A 的子公式。若在 A中用B取代B 的一处或多处出现后所得的新公式为B，则有 。如果A为永真式，则B也是永真式。37推理规则2.4 谓词逻辑中的推理理论5关于量词的增加和删除规则38推理规则2.4 谓词逻辑中的推理理论5关于量词的增加和删除规则39推理规则2.4 谓词逻辑中的推理理论谓词逻辑的推理方法是命题逻辑推理方法的拓展，因此在谓词逻辑中利用的推理规则也是T规则、P规则和CP规则，还有已知的等价式、蕴涵式以及有关量词的消去和产生规则。使用的推理方法是直接构造法和间接证明法。下面举例说明。40推理实例2.4 谓词逻辑中的推理理论谓词逻辑的推理方法是命题逻辑推理方法的拓展，因此在谓词逻辑中利用的推理规则也是T规则、P规则和CP规则，还有已知的等价式、蕴涵式以及有关量词的消去和产生规则。使用的推理方法是直接构造法和间接证明法。下面举例说明。41推理实例2.4 谓词逻辑中的推理理论42推理实例PART PART 0101基本概念和表示主要内容PART PART 0 02 2PART PART 0 03 3谓词逻辑的等价式与蕴涵式PART PART 0 04 4PART PART 0 05 5格的定义与性质谓词逻辑的翻译与解释谓词逻辑中的推论理论2.5 谓词逻辑中公式范式44在谓词逻辑的公式中，不仅有联结词还有量词出现，这使得公式可以很复杂，量词之间的关系直觉上很难看清，特别是在量词分割时。为了揭示在原来公式中并不显著的逻辑结构方面的关系，给出一种标准形式，缩小公式形式的类型范围，研究谓词逻辑中范式是很重要的。命题逻辑中的两种范式都可以直接推广到谓词逻辑中来，只要把原子命题公式换成原子谓词公式即可。此外，根据量词在公式中出现的情况不同，又可分为前束范式和斯柯林范式。本小节将对这两种范式进行介绍，重点研究前束范式。2.5 谓词逻辑中公式范式n定义2.7 一个合式公式称为前束范式，如果它有如下形式：(Q1x1)(Q2x2)(Qkxk)B其中，Qi(1ik)为或，B为不含有量词的公式。称Q1x1Q2x2Qkxk为公式的首标。特别地，若A中不含量词，则A也看做是前束范式。可见，前束范式的一般特点是对任一谓词公式F，如果其中所有量词均非否定的出现在公式的最前面，且它们的辖域为整个公式，则称公式F为前束范式。45前束范式2.5 谓词逻辑中公式范式n例如：是前束范式。任一公式都可以化成与之等价的前束范式。化法如下。（1）消去公式中的联结词和 ；利用AB (AB)(A B)及；（2）将公式内的否定符号深入到谓词变元前并化简到谓词变元前只有一个否定号；（3）利用改名、代入规则使所有的约束变元均不同名，且使自由变元与约束变元亦不同名；（4）扩充量词的辖域至整个公式。46前束范式2.5 谓词逻辑中公式范式47前束范式2.5 谓词逻辑中公式范式n定义2.8 如果前束范式中所有的存在量词均在全称量词之前，则称这种形式为斯柯林范式。例如：(x)(z)(y)(P(x，y)Q(y,z)R(y)是斯柯林范式。任何一个公式都可以化为与之等价的斯柯林范式，其方法如下。（1）先将给定公式化为前束范式。（2）将前束范式中的所有自由变元用全称量词约束（UG）。（3）若经上述改造后的公式A中，第一个量词不是存在量词，则可以将A等价变换成如下形式：，其中u是A中没有的变元。48斯柯林范式2.5 谓词逻辑中公式范式（4）如果前束范式是由n个存在量词开始，然后是m个全称量词，后面还跟有存在量词，则可以利用下述等价式将这些全称量词逐一移到存在量词之后。斯柯林范式比前束范式更优越，它将任意公式分为三部分，即存在量词序列、全程量词序列、不含量词的谓词公式。这大大方便了对谓词公式的研究。49斯柯林范式2.5 谓词逻辑中公式范式50斯柯林范式2.5 谓词逻辑中公式范式51斯柯林范式52