第三章 谓词演算基础.pptVIP

第三章 谓词演算基础 3.1 谓词与个体 3.2 函数与量词 3.3 自由变元和约束变元 3.3.1 自由出现和约束出现 3.3.2 改名和代入 3.4 永真性和可满足性 3.5 唯一性量词与摹状词 复习: 项 例 考察谓词 WRITE(x,y)表示x 写了y WRITE(Shakespeare，Hamlet) WRITE(Shakespeare，y) WRITE(son(Shakespeare)，Hamlet) 变量符号 函数！ 实体 谓词演算公式的原子公式 ——谓词填式A(x1，x2，…，xn) 其中x1，…，xn是项(实体、变量符号、函数)。 原子公式是公式的最小单位，是最小的句子单位。 项不是公式。 函数f(t1,...，tm)不是句子，仅是词，仅是项。 合式公式的定义 定义1：谓词演算的合式公式(简称公式)是由 ◆ 原子命题、 ◆ 谓词填式（原子公式）、 ◆ 或由它们利用联结词和量词 构成的式子。 合式公式的形式定义 (1) 原子命题P是合式公式； (2) 谓词填式A(x1，x2，x3，…，xn)是合式公式； (3) 若A是公式，则?A是合式公式； (4) 若A和B是合式公式，则 (A?B)，(A?B)，(A?B)，(A?B)为公式； (5) 若A是合式公式，x是A中出现的任何个体变元，则?xA(x)，?xA(x)为合式公式。 (6)只有有限次使用(1)、(2)、(3)、(4)、(5)所得到的式子才是合式公式。 自由出现和约束出现 定义2：设?为任何一个谓词演算公式，并设 ?xA(x)，?xA(x)为公式?的子公式， 此时紧跟在?、?之后的x称为量词的指导变元或作用变元， A(x)称为相应量词的作用域或辖域， 在作用域中x 的一切出现均称为约束出现， 在?中除了约束出现外的一切出现x均称为自由出现。 例 ?x(A(x，y)) 例 ?x(A(x，y)??y(B(x，y)?C(z))) 指出上述公式的作用域、约束出现和自由出现。 解：?x的作用域为： A(x，y)??y(B(x，y)?C(z))； ?y的作用域为： B(x，y)?C(z)； 公式中的x为约束出现， 第一个y和z是自由出现， B(x，y)?C(z)中的y为约束出现。 自由变元和约束变元 定义3：一个变元x 若在公式中有自由出现，则称此变元为自由变元； 若有约束出现，则称为约束变元。 例 ?x(A(x，y)) x为约束变元， y为自由变元，不受全称量词约束，可以看作为公式中的参数。 例 ?x(p(x)??yQ(x,y)) 指出上述公式的指导变元、辖域、约束变元和自由变元。 解：由?x后的()，x是指导变元，?x的辖域是后面整个式子 p(x)??yQ(x,y) ， y是指导变元，辖域仅Q(x，y)此部分。 x两次出现均是约束出现，y的一次出现是约束出现，故x，y是约束变元，而不是自由变元。 例 ?xF(x)?G(x,y) 指出上述公式的指导变元、辖域、约束变元和自由变元。 解：?x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。 所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的；而y仅是自由变元。 例 ?x(x=y?x2+x5?xz)?x=5y2 指出上述公式的指导变元、辖域、约束变元和自由变元。 解： x=y，x2+x5，xz，x=5y2这是四个原子公式, 用逻辑词?，?，?来联结起来的。 x是指导变元、?x的辖域是()内的这部分 x=y?x2+x5?xz 。 因此，x第一、二、三、四次出现是约束出现，x第五次出现是自由出现。 而y，z的出现均是自由出现。 一、改名 ?x(A(x，y)??y(B(x，y)?C(z))) 其中, 同一个变元y既有约束出现又有自由出现。 对约束变元进行改名，使得 同一个变元要么为约束出现，要么为自由出现， 同时使不同的量词所约束的变元不同名. 3.3.2 改名和代入 改名的规则 (1) 改名是对约束变元而言，自由变元不能改名，改名时应对量词的指导变元及其作用域中所出现的约束变元处处进行； (2) 改名前后不能改变变元的约束关系； (3) 改名用的新名应是该作用域中没有使用过的变元名称。 例： ?x(A(x，y)??y(B(x，