1、 第第2章章 谓词逻辑谓词逻辑 2.1 基本概念基本概念 教学内容：个体，谓词，全称量词，存教学内容：个体，谓词，全称量词，存在量词在量词2022年8月9日星期二4时31分1秒裘国永3 2.2 谓词公式与翻译谓词公式与翻译 教学内容：谓词公式，谓词逻辑符号化教学内容：谓词公式，谓词逻辑符号化2022年8月9日星期二4时31分1秒裘国永4 2.3 自由变元与约束变元自由变元与约束变元 教学内容：自由变元，自由出现，约束教学内容：自由变元，自由出现，约束变元，约束出现，辖域，闭式，换名规变元，约束出现，辖域，闭式，换名规则，代入规则则，代入规则2022年8月9日星期二4时31分1秒裘国永5 2.4
2、 谓词公式的解释与分类谓词公式的解释与分类 教学内容：谓词公式的解释教学内容：谓词公式的解释2022年8月9日星期二4时31分1秒裘国永6 2.5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式 教学内容：等价式，蕴涵式教学内容：等价式，蕴涵式2022年8月9日星期二4时31分1秒裘国永7 2.6 谓词演算中的公式范式谓词演算中的公式范式 教学内容：前束范式，柯林斯范式教学内容：前束范式，柯林斯范式2022年8月9日星期二4时31分2秒裘国永8 2.7 谓词演算的推理理论谓词演算的推理理论 教学内容：全称量词消去规则，存在量教学内容：全称量词消去规则，存在量词消去规则，全称量词引入规则，存在
3、词消去规则，全称量词引入规则，存在量词引入规则，谓词演算的推理量词引入规则，谓词演算的推理2022年8月9日星期二4时31分2秒裘国永92022年8月9日星期二4时31分2秒裘国永102022年8月9日星期二4时31分2秒裘国永12个体、谓词和命题的谓词形式个体、谓词和命题的谓词形式注注 个体可以是具体的事物，也可是抽象的概念。如个体可以是具体的事物，也可是抽象的概念。如张三、北京、计算机、大学生、精神等。张三、北京、计算机、大学生、精神等。定义定义2.1 在原子命题中，所描述的对象称为在原子命题中，所描述的对象称为个体个体(Individual)；用以刻画个体的性质或个体间关；用以刻画个体的
4、性质或个体间关系的词称为系的词称为谓词谓词(Predicate)。例例(1)张三是大学生。张三是大学生。(2)3大于大于5。个体：个体：“张三张三”、“3”、“5”谓词：谓词：“是大学生是大学生”(刻画个体刻画个体“张三张三”的性质的性质)“大于大于”(刻画个体刻画个体“3”和和“5”间的关系间的关系)2022年8月9日星期二4时31分3秒裘国永13 有了个体和谓词的概念之后，可以进一步刻画命有了个体和谓词的概念之后，可以进一步刻画命题的内在结构和命题之间的关系。题的内在结构和命题之间的关系。例如例如，“张三是大学生张三是大学生”和和“李四是大学生李四是大学生”之间之间的关系是无法表达的，现在
5、可用谓词的关系是无法表达的，现在可用谓词“是大学生是大学生”及个体及个体“张三张三”、“李四李四”刻画。刻画。2022年8月9日星期二4时31分3秒裘国永14定义定义2.2 表示具体或特定个体的词称为个体常元，表示具体或特定个体的词称为个体常元，用小写字母用小写字母a、b等表示。表示抽象或泛指个体的词等表示。表示抽象或泛指个体的词称为个体变元，用称为个体变元，用x、y等表示等表示。定义定义2.3 表示具体性质或关系的谓词称为谓词常元，表示具体性质或关系的谓词称为谓词常元，表示抽象或泛指的性质或关系的谓词称为谓词变元。表示抽象或泛指的性质或关系的谓词称为谓词变元。谓词常元或谓词变元都用大写字母谓
6、词常元或谓词变元都用大写字母P、Q等表示。等表示。例例2.1 (1)x是大学生。是大学生。x是个体变元。是个体变元。(2)3与与5具有关系具有关系F。F是谓词变元。是谓词变元。2022年8月9日星期二4时31分3秒裘国永15定义定义2.4 一个原子命题用一个谓词一个原子命题用一个谓词(如如P)和和n个有序个有序个体常元个体常元(如如a1,a2,an)表示成表示成P(a1,a2,an)，称为该原子命题的谓词形式。若称为该原子命题的谓词形式。若x1,x2,xn为个体为个体变元，称变元，称P(x1,x2,xn)为为n元谓词或元谓词或n元命题函数。元命题函数。一般而言，一元谓词表达了个体的性质，而一般
7、而言，一元谓词表达了个体的性质，而n元谓元谓词表达了词表达了n个个体之间的关系。个个体之间的关系。2022年8月9日星期二4时31分3秒裘国永16 n元谓词不是命题。只有当个体变元用特定的个元谓词不是命题。只有当个体变元用特定的个体替代时，才成为一个命题。但个体变元的取值范围，体替代时，才成为一个命题。但个体变元的取值范围，对命题的真值极有影响。对命题的真值极有影响。例例2.2 F(x)表示表示x是大学生。当取值范围限定为是大学生。当取值范围限定为某大学的全体学生时，某大学的全体学生时，F(x)是真的，但当取值范围是真的，但当取值范围限定为某中学的所有学生时，则限定为某中学的所有学生时，则F(
8、x)是假的。因此，是假的。因此，在谓词逻辑中，我们要指定个体的取值范围。在谓词逻辑中，我们要指定个体的取值范围。2022年8月9日星期二4时31分3秒裘国永17定 义定 义 2.5 个 体 的 取 值 范 围 称 为个 体 的 取 值 范 围 称 为 个 体 域 或 论 域个 体 域 或 论 域(Domain)；所有个体的取值范围称为；所有个体的取值范围称为全总个体域全总个体域(Universal domain)。注注 如果没有特别说明，个体的取值范围总是全总个体如果没有特别说明，个体的取值范围总是全总个体域。当给定个体域域。当给定个体域D后，个体常元就是后，个体常元就是D中的一个特定中的一个
9、特定元素，个体变元则可以取元素，个体变元则可以取D中任一个元素。中任一个元素。2022年8月9日星期二4时31分3秒裘国永18例例2.3 将下列命题符号化：将下列命题符号化：(1)张三和李四都是三好学生。张三和李四都是三好学生。(2)赵斌是象棋迷或围棋迷。赵斌是象棋迷或围棋迷。(3)李林比张强高。李林比张强高。(4)如果你不出去，我就不进来。如果你不出去，我就不进来。2022年8月9日星期二4时31分3秒裘国永19解解(1)S(a)S(b)，其中，其中S(x)：x是三好学生，是三好学生，a：张三，：张三，b：李四。：李四。(2)Q(a)R(a)，其中，其中，Q(x)：x是象棋迷，是象棋迷，R(
10、x)：x是围棋迷，是围棋迷，a：赵斌。：赵斌。(3)T(a,b)，其中，其中，T(x,y)：x比比y高，高，a：李林，李林，b：张强。：张强。(4)F(a)G(b)，其中，其中，F(x)：x出去，出去，G(x)：x进来，进来，a：你，：你，b：我。：我。2022年8月9日星期二4时31分3秒裘国永20有了个体和谓词的概念之后，对有些命题仍然不有了个体和谓词的概念之后，对有些命题仍然不能准确的符号化，如能准确的符号化，如“所有人都是要死的所有人都是要死的”。原。原因是还缺少表示个体数量关系的词。下面我们再因是还缺少表示个体数量关系的词。下面我们再引入量词的概念。引入量词的概念。2022年8月9日
11、星期二4时31分3秒裘国永21量词量词定义定义2.6 符号符号 x表示表示“所有的所有的x”、“每一个每一个x”和和“任意一个任意一个x”等词语，称等词语，称 x为为全称量词全称量词(Universal quantifier)；符号；符号 x表示表示“对某对某一个一个x”、“至少存在某个至少存在某个x”和和“存在某个存在某个x”等词等词语，称语，称 x 为为 存 在 量 词存 在 量 词(E x i s t e n t i a l quantifier)。以上的。以上的x称为称为指导变元指导变元(Leading variable)。全称量词和存在量词统称为。全称量词和存在量词统称为量词量词(Q
12、uantifier)。2022年8月9日星期二4时31分3秒裘国永22例例2.4 用谓词和量词将下列命题符号化：用谓词和量词将下列命题符号化：(1)所有的人都是要死的。所有的人都是要死的。(2)每个自然数都是实数。每个自然数都是实数。(3)一些大学生有远大的理想。一些大学生有远大的理想。(4)有的学生选修了有的学生选修了AI课。课。2022年8月9日星期二4时31分3秒裘国永23解解(1)(x)(S(x)L(x)，其中，其中S(x):x是人，是人，L(x):x是要死的。是要死的。(2)(x)(N(x)R(x)，其中，其中N(x):x是自是自然数，然数，R(x):x是实数。是实数。2022年8月
13、9日星期二4时31分3秒裘国永24(3)(x)(P(x)Q(x)，其中，其中，P(x):x是大是大学生，学生，Q(x):x有远大理想。有远大理想。(4)(x)(F(x)T(x)，其中，其中F(x):x是学生，是学生，T(x):x选修了选修了AI课。课。2022年8月9日星期二4时31分3秒裘国永25注注 在上述例子中，个体域都默认为全总个体域。但在上述例子中，个体域都默认为全总个体域。但如果指定一个特定的个体域，则其符号化结果将会有如果指定一个特定的个体域，则其符号化结果将会有所不同。所不同。2022年8月9日星期二4时31分3秒裘国永26例例2.4 用谓词和量词将下列命题符号化：用谓词和量词
14、将下列命题符号化：(1)所有的人都是要死的。所有的人都是要死的。(2)每个自然数都是实数。每个自然数都是实数。(3)一些大学生有远大的理想。一些大学生有远大的理想。(4)有的学生选修了有的学生选修了AI课。课。2022年8月9日星期二4时31分3秒裘国永27解解 (1)(x)L(x)，其中，其中L(x):x是要死的，个体是要死的，个体域域D:全体人。全体人。(2)(x)R(x)，其中，其中R(x):x是实数，个体域是实数，个体域D:全体自然数。全体自然数。2022年8月9日星期二4时31分3秒裘国永28(3)(x)Q(x)，其中，其中Q(x):x有远大理想，个体有远大理想，个体域域D:全体大学
15、生。全体大学生。(4)(x)T(x)，其中，其中F(x):x是学生，是学生，T(x):x选修了选修了AI课，个体域课，个体域D:全体学生。全体学生。2022年8月9日星期二4时31分3秒裘国永29 当个体域是全总个体域时，需要引进所谓的当个体域是全总个体域时，需要引进所谓的特特性谓词性谓词来限制个体变元的取值范围，如上题中的来限制个体变元的取值范围，如上题中的S(x)、N(x)、P(x)、F(x)都是。在命题符号化都是。在命题符号化时，一定要正确的使用特性谓词。时，一定要正确的使用特性谓词。当引入特性谓词时，全称量词后跟的是条件式，当引入特性谓词时，全称量词后跟的是条件式，(x)(S(x)L(
16、x)。存在量词后跟的是合取式，。存在量词后跟的是合取式，如如(x)(P(x)Q(x)。2022年8月9日星期二4时31分3秒裘国永30注注 (1)在不同的个体域内，同一命题的符号化形式在不同的个体域内，同一命题的符号化形式可能不同，也可能相同。可能不同，也可能相同。(2)同一公式，在不同的个体域中的真值可能不同，同一公式，在不同的个体域中的真值可能不同，也可能相同。也可能相同。(3)P(x)不是命题，但前面加上量词后，不是命题，但前面加上量词后，xP(x)和和 xP(x)在给定个体域内就有了真假，在给定个体域内就有了真假，才成为命题。才成为命题。2022年8月9日星期二4时31分3秒裘国永31
17、2022年8月9日星期二4时31分4秒裘国永322022年8月9日星期二4时31分4秒裘国永33谓词公式谓词公式n元谓词元谓词P(x1,x2,xn)称为谓词演算的原子公式，称为谓词演算的原子公式，其中其中x1,x2,xn是个体变元。是个体变元。2022年8月9日星期二4时31分4秒裘国永34定义定义2.7 谓词公式的递归定义如下：谓词公式的递归定义如下：(1)原子公式是谓词公式；原子公式是谓词公式；(2)若若A和和B是谓词公式，则是谓词公式，则 A、AB、AB、AB和和AB是谓词公式；是谓词公式；(3)若若A是谓词公式，是谓词公式，x是个体变元，则是个体变元，则(x)A和和(x)A都是谓词公式
18、；都是谓词公式；(4)只有有限次使用只有有限次使用(1)、(2)和和(3)规则形成的规则形成的有意义的符号串才是谓词公式。有意义的符号串才是谓词公式。谓词公式也称为合式公式。谓词公式也称为合式公式。2022年8月9日星期二4时31分4秒裘国永35谓词公式中的某些括号也可以省略，其规定与命题谓词公式中的某些括号也可以省略，其规定与命题公式相同，但量词后若有括号则不能省略。特别地，公式相同，但量词后若有括号则不能省略。特别地，命题公式也是谓词公式，因此命题逻辑包含在谓词命题公式也是谓词公式，因此命题逻辑包含在谓词逻辑中。逻辑中。2022年8月9日星期二4时31分4秒裘国永36谓词逻辑的翻译谓词逻辑
19、的翻译 把一个用自然语言表示的命题，用谓词公式表示出把一个用自然语言表示的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化。来，称为谓词逻辑的翻译或符号化。2022年8月9日星期二4时31分4秒裘国永37例例2.5 用谓词和量词将下列命题符号化：用谓词和量词将下列命题符号化：(1)每一个有理数都是实数。每一个有理数都是实数。(2)尽管有些人聪明，但并不是所有的人都聪明。尽管有些人聪明，但并不是所有的人都聪明。(3)没有最大的自然数。没有最大的自然数。(4)今天有雨雪，有些人会跌跤。今天有雨雪，有些人会跌跤。2022年8月9日星期二4时31分4秒裘国永38解解 (1)x(H(x)M(x)，其
20、中，其中H(x):x是有理是有理数，数，M(x):x是实数是实数。(3)x(N(x)y(N(y)G(y,x)，其中，其中N(x)：x是自然数，是自然数，G(x,y)：x大于大于y。(2)x(P(x)Q(x)(x(P(x)Q(x)，其中其中P(x)：x是人，是人，Q(x)：x聪明。聪明。(4)RSx(M(x)F(x)，其中，其中R：今天有：今天有雨，雨，S：今天有雪，：今天有雪，M(x)：x是人，是人，F(x)：x跌跤。跌跤。2022年8月9日星期二4时31分4秒裘国永39注注 在进行谓词公式的翻译时，一定要注意不要遗漏在进行谓词公式的翻译时，一定要注意不要遗漏量词。当有多个量词出现时，注意它们
21、的顺序。量词。当有多个量词出现时，注意它们的顺序。2022年8月9日星期二4时31分4秒裘国永40例如，例如，谓词谓词E(x,y,z):x+y=z，个体域，个体域D:全体整全体整数。请比较下列命题的含义：数。请比较下列命题的含义：x y zE(x,y,z)，y x zE(x,y,z)x y zE(x,y,z)，z x yE(x,y,z)x y zE(x,y,z)，y z zE(x,y,z)2022年8月9日星期二4时31分4秒裘国永412022年8月9日星期二4时31分4秒裘国永422022年8月9日星期二4时31分4秒裘国永43自由变元和约束变元自由变元和约束变元 定义定义2.8 在一个谓词
22、公式中，形如在一个谓词公式中，形如 xA(x)或或 xA(x)的部分称为公式的的部分称为公式的x约束部分，约束部分，A(x)称为量称为量词词 x或或 x的的辖域或作用域辖域或作用域(Scope)，x称为指导变称为指导变元或作用变元。元或作用变元。x在公式的在公式的x约束部分的任一出现都约束部分的任一出现都称为称为x的的约束出现约束出现(Bounded occurrence)，x称称为为约束变元约束变元(Bounded variable)，若若x的出现不的出现不是约束出现，称是约束出现，称x为为自由出现自由出现(Free occurrence)，x称为称为自由变元自由变元(Free variab
23、le)。2022年8月9日星期二4时31分4秒裘国永44注注 判断量词的辖域要看其后是否跟的是括号，如是判断量词的辖域要看其后是否跟的是括号，如是括号，则括号内的子公式为其辖域，否则量词邻接括号，则括号内的子公式为其辖域，否则量词邻接的子公式是其辖域的子公式是其辖域。2022年8月9日星期二4时31分5秒裘国永45例例2.6 指出下列谓词公式中量词的辖域及变元的约指出下列谓词公式中量词的辖域及变元的约束情况：束情况：(1)x(P(x)yQ(x,y)。(2)x y(P(x,y)Q(y,z)xR(x,y)。(3)(x)(P(x)xQ(x,z)yR(x,y)Q(x,y)。2022年8月9日星期二4时
24、31分5秒裘国永46解解 (1)x的辖域是的辖域是(P(x)yQ(x,y)，y的的辖域是辖域是Q(x,y)。x、y都是约束变元。都是约束变元。(2)x的辖域是的辖域是 y(P(x,y)Q(y,z)，y的辖域是的辖域是P(x,y)Q(y,z)，x和和y为约束变元，为约束变元，z为自由变元。为自由变元。x的辖域是的辖域是R(x,y)，x为约束变为约束变元，元，y为自由变元。在整个公式中，为自由变元。在整个公式中，x是约束出现，是约束出现，y既是约束出现也是自由出现，既是约束出现也是自由出现，z是自由出现。是自由出现。2022年8月9日星期二4时31分5秒裘国永47(3)x的辖域是的辖域是P(x)x
25、Q(x,z)yR(x,y)，x的辖域是的辖域是Q(x,z)，y的辖域是的辖域是R(x,y)，x和和y都是约束变元，都是约束变元，z是自由变元，但是自由变元，但Q(x,z)中中的的x是受是受 x的约束，而不是受的约束，而不是受 x的约束。的约束。Q(x,y)中的中的x和和y都是自由变元。都是自由变元。2022年8月9日星期二4时31分5秒裘国永48定义定义2.9 任一谓词公式任一谓词公式A，若，若A中无自由出现的个中无自由出现的个体变元，称体变元，称A是封闭的谓词公式，简称闭式。是封闭的谓词公式，简称闭式。例如，例如，x(P(x)Q(x)和和 x y(P(x)Q(x,y)都是闭式，但都是闭式，但
26、 x(P(x)Q(x,y)不是闭式。不是闭式。2022年8月9日星期二4时31分5秒裘国永49在谓词公式中，自由变元虽然可以出现在量词的辖在谓词公式中，自由变元虽然可以出现在量词的辖域中，但它不受相应量词中指导变元的约束。另一域中，但它不受相应量词中指导变元的约束。另一方面，在谓词公式中，一个个体变元可以既是约束方面，在谓词公式中，一个个体变元可以既是约束变元，也是自由变元。为了避免一个变元既是约束变元，也是自由变元。为了避免一个变元既是约束变元又是自由变元引起的混乱，可以对约束变元或变元又是自由变元引起的混乱，可以对约束变元或自由变元进行改名，使得一个变元在一个公式中只自由变元进行改名，使得
27、一个变元在一个公式中只呈现一种形式。呈现一种形式。2022年8月9日星期二4时31分5秒裘国永50换名规则换名规则:将量词辖域中某个约束出现的个体变元将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。变元，其余不变。代入规则代入规则:对某个自由出现的个体变元用与原公式对某个自由出现的个体变元用与原公式中和所有个体变元不同的个体变元代入，且处处代中和所有个体变元不同的个体变元代入，且处处代入。入。注注 换名规则用于约束变元，代入规则用于自由变换名规则用于约束变元，代入规则用于自由变元。元。2022年8月9日星
28、期二4时31分5秒裘国永51例例2.7 将将(x)(P(x)Q(x,y)R(x,y)中中的约束变元改名。的约束变元改名。解解 可改名为可改名为(z)(P(z)Q(z,y)R(x,y)，但不能改名，但不能改名为为(y)(P(y)Q(y,y)R(x,y)或或(z)(P(z)Q(x,y)R(x,y)。因为后两种。因为后两种更改都将使公式中量词的约束范围有所变动。更改都将使公式中量词的约束范围有所变动。2022年8月9日星期二4时31分5秒裘国永52例例2.8 将将(x)(P(x)xQ(x,z)yR(x,y)Q(x,y)中的约束变元改名。中的约束变元改名。解解 可改名为可改名为(u)(P(u)vQ(v
29、,z)wR(u,w)Q(x,y)，但不，但不能改名为能改名为(z)(P(z)xQ(x,z)yR(z,y)Q(x,y)或或(x)(P(x)zQ(z,z)yR(x,y)Q(x,y)，因为，因为后两种更改都将使公式中量词的约束范围有所变动。后两种更改都将使公式中量词的约束范围有所变动。2022年8月9日星期二4时31分5秒裘国永53例例2.9 将将(x)(P(x)Q(x,y)R(x,y)中中的自由变元改名。的自由变元改名。解解 对自由变元对自由变元x施行代入，经代入后公式为：施行代入，经代入后公式为：(x)(P(x)Q(x,y)R(z,y)，但不能是，但不能是(x)(P(x)Q(x,y)R(y,y)
30、，因为后一种，因为后一种代入与代入规则不符。代入与代入规则不符。2022年8月9日星期二4时31分5秒裘国永542022年8月9日星期二4时31分5秒裘国永552022年8月9日星期二4时31分5秒裘国永56谓词公式的解释谓词公式的解释 谓词公式一般不是一个命题，它往往包含若干谓词公式一般不是一个命题，它往往包含若干个体变元、常元、函数和谓词，要使它成为一个命个体变元、常元、函数和谓词，要使它成为一个命题，除了要为每个个体变元指定个体域以外，还需题，除了要为每个个体变元指定个体域以外，还需要对这些符号进行解释。要对这些符号进行解释。定义定义2.10 谓词公式的一个谓词公式的一个解释解释I(或赋
31、值，或赋值，Interpretation)由四部分组成：由四部分组成：非空个体域非空个体域D；D中一些特定的元素；中一些特定的元素；D上一些特定的函上一些特定的函数；数；D上一些特定的谓词。上一些特定的谓词。2022年8月9日星期二4时31分5秒裘国永57 例例2.10 给定解释给定解释I如下：如下：(1)个体域为自然数集个体域为自然数集N。(2)N中特定的元素中特定的元素a=0。(3)N上特定的函数上特定的函数f(x,y)=x+y，g(x,y)=xy。(4)N中特定的谓词中特定的谓词F(x,y)为为x=y。2022年8月9日星期二4时31分5秒裘国永58 在解释在解释I下，求下列公式的真值：
32、下，求下列公式的真值：(1)xF(g(x,a),x)。(2)x y(F(f(x,a),y)F(f(y,a),x)。(3)x y zF(f(x,y),z)。(4)x yF(f(x,y),g(x,y)。(5)F(f(x,y),f(y,z)。解解 (1)xF(g(x,a),x)xF(ax,x)x(ax=x)x(x=0)F。2022年8月9日星期二4时31分5秒裘国永59(2)x y(F(f(x,a),y)F(f(y,a),x)x y(f(x,a)=y)(f(y,a)=x)x y(a+x=y)(a+y=x)x y(x=y)(y=x)T。(3)x y zF(f(x,y),z)x y z(f(x,y)=z
33、)x y z(x+y=z)T。2022年8月9日星期二4时31分6秒裘国永60(4)x yF(f(x,y),g(x,y)x y(f(x,y)=g(x,y)x y(x+y=xy)F。(5)F(f(x,y),f(y,z)x+y=y+z x=z。由于由于(5)的真值不确定，因而它不是命题。的真值不确定，因而它不是命题。2022年8月9日星期二4时31分6秒裘国永61谓词公式的逻辑有效式谓词公式的逻辑有效式定义定义2.11 设设A是一谓词公式，如是一谓词公式，如A在任何解释下在任何解释下都是真的，称都是真的，称A为永真式或逻辑有效式；如为永真式或逻辑有效式；如A在任何在任何解释下都是假的，称解释下都是
34、假的，称A为矛盾式；若至少存在一个为矛盾式；若至少存在一个解释使解释使A为真，称为真，称A是可满足式。是可满足式。2022年8月9日星期二4时31分6秒裘国永622022年8月9日星期二4时31分6秒裘国永632022年8月9日星期二4时31分6秒裘国永64等价式等价式定义定义2.12 设设A和和B是谓词公式，若是谓词公式，若AB为逻辑有效为逻辑有效式，则称式，则称A和和B是等价的，记为是等价的，记为AB。2022年8月9日星期二4时31分6秒裘国永65 下面给出一些常见的基本谓词公式等价式。下面给出一些常见的基本谓词公式等价式。若个体域为若个体域为a1,a2,an，则有下式成立：，则有下式成
35、立：(1)xA(x)A(a1)A(a2)A(an)。(2)xA(x)A(a1)A(a2)A(an)。2022年8月9日星期二4时31分6秒裘国永66例例2.11 求下列各式的真值：求下列各式的真值：(1)x(P(x)Q(x)，其中，其中P(x)：x=1，Q(x)：x=2，个体域，个体域1,2。(2)x(PQ(x)R(a)，P：3-2，Q(x)：x3，R(x)：x5，a：3，个体域，个体域-2,3,5,6。(3)x(P(x)Q(x)T，P(x)：x1，Q(x)：x=1，T任意永真式，个体域任意永真式，个体域1。(4)x y(x+y=4)，个体域为，个体域为1,2。2022年8月9日星期二4时31
36、分6秒裘国永67解解 (1)x(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)(TF)(FT)T。(2)x(PQ(x)R(a)(PQ(-2)(PQ(3)(PQ(5)(PQ(6)R(a)(TTFF)F F。2022年8月9日星期二4时31分6秒裘国永68(3)x(P(x)Q(x)T x(P(x)Q(x)P(1)Q(1)T。(4)x y(x+y=4)x(x+1=4)(x2=4)(1+1=4)(1+2=4)(2+1=4)(2+2=4)F。2022年8月9日星期二4时31分6秒裘国永69定理定理2.2 量词否定的等价式量词否定的等价式设设A(x)是一个含个体变元是一个含个体变元x的谓词公式，则下
37、列等价的谓词公式，则下列等价式成立：式成立：(1)(xA(x)x(A(x)。(2)(xA(x)x(A(x)。2022年8月9日星期二4时31分6秒裘国永70证明证明 (1)(xA(x)为真为真 xA(x)为假为假 a使使A(a)为假为假 a使使 A(a)为真为真 x(A(x)为真，故为真，故(xA(x)x(A(x)。(2)x(A(x)为假为假 a使使 A(a)为假为假 a使使A(a)为真为真 xA(x)为真为真 (xA(x)为假，为假，故故(xA(x)x(A(x)。2022年8月9日星期二4时31分6秒裘国永71定理定理2.2 量词辖域收缩和扩张的等价式量词辖域收缩和扩张的等价式设设A(x)是
38、一个含个体变元是一个含个体变元x的谓词公式，的谓词公式，B是一个不是一个不含个体变元含个体变元x的谓词公式，则下列等价式成立：的谓词公式，则下列等价式成立：(1)x(A(x)B)xA(x)B。(2)x(A(x)B)xA(x)B。(3)x(A(x)B)xA(x)B。2022年8月9日星期二4时31分6秒裘国永72(8)x(BA(x)BxA(x)。(4)x(BA(x)BxA(x)。(5)x(A(x)B)xA(x)B。(6)x(A(x)B)xA(x)B。(7)x(A(x)B)xA(x)B。2022年8月9日星期二4时31分6秒裘国永73定理定理2.3 量词分配的等价式。设量词分配的等价式。设A(x)
39、和和B(x)都是都是含个体变元含个体变元x的谓词公式，则下列等价式成立：的谓词公式，则下列等价式成立：(1)x(A(x)B(x)xA(x)xB(x)。(2)x(A(x)B(x)xA(x)xB(x)。2022年8月9日星期二4时31分6秒裘国永74定理定理2.4 设设A(x,y)是含个体变元是含个体变元x和和y的谓词公式，的谓词公式，则下列等价式成立：则下列等价式成立：(1)(x)(y)A(x,y)(y)(x)A(x,y)。(2)(x)(y)A(x,y)(y)(x)A(x,y)。2022年8月9日星期二4时31分6秒裘国永75例例2.12 证明证明 x(A(x)B(x)xA(x)xB(x)。证明
40、证明 x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)x A(x)xB(x)xA(x)xB(x)。2022年8月9日星期二4时31分6秒裘国永76蕴含式蕴含式定义定义2.13 设设A和和B是两个谓词公式，若是两个谓词公式，若AB为逻辑为逻辑有效式，则称有效式，则称A蕴涵蕴涵B，记为，记为AB，称，称AB为蕴涵为蕴涵式。式。定理定理2.5 设设A(x)和和B(x)都是含个体变元都是含个体变元x的谓词公的谓词公式，则下列蕴含式成立：式，则下列蕴含式成立：(1)xA(x)xB(x)x(A(x)B(x)。(2)x(A(x)B(x)xA(x)xB(x)。(3)x(A(x)B(x)xA(x)x
41、B(x)。(4)x(A(x)B(x)xA(x)xB(x)。2022年8月9日星期二4时31分6秒裘国永77例例2.13 证明证明 xA(x)xB(x)x(A(x)B(x)。x(A(x)B(x)证明证明 xA(x)xB(x)xA(x)xB(x)x A(x)xB(x)x(A(x)B(x)。2022年8月9日星期二4时31分6秒裘国永78定理定理2.6 设设A(x,y)都是含个体变元都是含个体变元x和和y的谓词的谓词公式，则下列蕴含式成立：公式，则下列蕴含式成立：(1)(x)(y)A(x,y)xA(x,x)。(2)xA(x,x)(x)(y)A(x,y)。(3)(x)(y)A(x,y)(y)(x)A(
42、x,y)。(4)(x)(y)A(x,y)(y)(x)A(x,y)。(5)(x)(y)A(x,y)(y)(x)A(x,y)。2022年8月9日星期二4时31分6秒裘国永79例例2.14 下列断言是否为真，为什么？下列断言是否为真，为什么？(1)xP(x)xQ(x)x(P(x)Q(x)。(2)x(P(x)Q(x)xP(x)xQ(x)。解解 (1)、(2)不成立。不成立。(1)设个体域为设个体域为1,2，令，令P(x)：x=1，Q(x)：x=2，则则 xP(x)xQ(x)(P(1)P(2)(Q(1)Q(2)T，x(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)F，所以，该断言假。所以，该断言假
43、。2022年8月9日星期二4时31分6秒裘国永80(2)设个体域为设个体域为1,2，令，令P(x)：x=2，Q(x)：x=2，x(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)T，xP(x)xQ(x)(P(1)P(2)(Q(1)Q(2)F，所以，该断言假。所以，该断言假。2022年8月9日星期二4时31分6秒裘国永812022年8月9日星期二4时31分7秒裘国永822022年8月9日星期二4时31分7秒裘国永83 例如例如，x(A(x)B(x)为前束范式，为前束范式，而而 xA(x)xB(x)不是前束范式。不是前束范式。前束范式前束范式 定义定义2.14 设设A是谓词公式，如是谓词公式，
44、如A具有形式具有形式(Q1x1)(Q2x2)(Qkxk)B，其中，其中Qi为为 或或，B为为不含量词的公式，则称不含量词的公式，则称A为为前束范式前束范式(Prenex normal form)。2022年8月9日星期二4时31分7秒裘国永84定义定义2.15 设设A是具有形式为是具有形式为(Q1x1)(Q2x2)(Qkxk)B的前束范式，若的前束范式，若B为合取为合取范式，则称范式，则称A为前束合取范式，若为前束合取范式，若B为析取范式，则为析取范式，则称称A为前束析取范式。为前束析取范式。定理定理2.7 任何谓词公式的前束范式都存在。任何谓词公式的前束范式都存在。2022年8月9日星期二4
45、时31分7秒裘国永85(1)消去除消去除、以外的联结词；以外的联结词；(2)消去消去；(3)使使 移至量词之后；移至量词之后；(4)用到换名规则和代入规则使公式中所有变元；用到换名规则和代入规则使公式中所有变元；(5)扩大量词的辖域至整个公式之末。扩大量词的辖域至整个公式之末。求一个谓词公式的前束范式的过程求一个谓词公式的前束范式的过程:2022年8月9日星期二4时31分7秒裘国永86斯柯林范式斯柯林范式 定义定义2.16 若若B是是A的前束范式且每个存在量词均在的前束范式且每个存在量词均在全称量词之前，则称全称量词之前，则称B是是A的的斯柯林范式斯柯林范式(Skolem normal for
46、m)。2022年8月9日星期二4时31分7秒裘国永872022年8月9日星期二4时31分7秒裘国永88谓词演算的推理形式仍然为谓词演算的推理形式仍然为H1,H2,Hk C，其中，其中H1,H2,Hk和和C为谓词公式。但谓词演为谓词公式。但谓词演算的推理较命题逻辑的推理复杂的多。命题逻辑中算的推理较命题逻辑的推理复杂的多。命题逻辑中的所有推理规则和推理定律在谓词演算中都适用。的所有推理规则和推理定律在谓词演算中都适用。另外还有谓词演算特有的推理规则。另外还有谓词演算特有的推理规则。2022年8月9日星期二4时31分7秒裘国永89全称量词消去规则全称量词消去规则(US,Universal Spec
47、ification)xA(x)A(y)xA(x)A(c)两式成立的条件是：两式成立的条件是：x是是A(x)中自由出现的个体中自由出现的个体变元；变元；y为任意的不在为任意的不在A(x)中约束出现的个体变中约束出现的个体变元；元；c为任意的个体常元。为任意的个体常元。注注 在使用中，如果不注意条件是会犯错误的。在使用中，如果不注意条件是会犯错误的。2022年8月9日星期二4时31分7秒裘国永90例如，例如，在实数集上取在实数集上取F(x,y)为为xy，则公式，则公式 x yF(x,y)为真命题。若为真命题。若A(x)表示表示 yF(x,y)，则则x在在A(x)中是自由出现的是满足的，而中是自由出
48、现的是满足的，而y在在A(x)中是约束出现的。若中是约束出现的。若y取代取代x，得，得 x yF(x,y)yF(y,y)，即有，即有“存在存在y，yy”，这是假命题。，这是假命题。出错的原因是违背了条件。出错的原因是违背了条件。2022年8月9日星期二4时31分7秒裘国永91全称量词引入规则全称量词引入规则(UG,Universal Generalization)A(y)xA(x)上式成立的条件是：上式成立的条件是：y是是A(y)中自由出现中自由出现的个体变元，且的个体变元，且y取任何值取任何值A均为真；均为真；取代取代y的的x不能在不能在A(y)中约束出现。中约束出现。2022年8月9日星期
49、二4时31分7秒裘国永92在实数集上取在实数集上取F(x,y)为为xy，若，若A(y)表示表示 xF(x,y)，则对任意的，则对任意的y，A(y)均为真命题。若均为真命题。若x取代取代y，得，得 x x(xx)，这是假命题。出错的，这是假命题。出错的原因是违背了条件。原因是违背了条件。2022年8月9日星期二4时31分7秒裘国永93存在量词引入规则存在量词引入规则(EG,Existential Generalization)A(c)xA(x)上式成立的条件是：上式成立的条件是：c是特定的个体常元；是特定的个体常元；取取代代c的的x不能在不能在A(c)中出现过。中出现过。2022年8月9日星期二
50、4时31分7秒裘国永94在实数集上取在实数集上取F(x,y)为为xy，若，若A(2)表示表示 xF(x,2)，则，则A(2)为真命题，为真命题，x已在已在A(2)中出中出现过。若现过。若x取代取代2，得，得 x(xx)，这是假命题。出，这是假命题。出错的原因是违背了条件。错的原因是违背了条件。2022年8月9日星期二4时31分7秒裘国永95存在量词消去规则存在量词消去规则(ES,Existential Specification)xA(x)A(c)上式成立的条件是：上式成立的条件是：c是使是使A为真的特定的个体为真的特定的个体常元；常元；c不曾在不曾在A(x)中出现过；中出现过；A(x)中除中
