离散数学第三章谓词演算基础-自由变元和约束变元.ppt

第三章 谓词演算基础,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或0)。,合式公式的定义,定义1：谓词演算的合式公式(简称公式)是由 原子命题、 谓词填式（原子公式）、 或由它们利用联结词和量词 构成的式子。,合式公式的形式定义,(1) 原子命题P是合式公式； (2) 谓词填式A(x1，x2，x3，xn)是合式公式； (3) 若A是公式，则A是合式公式； (4) 若A和B是合式公式，则 (AB)，(AB)，(AB)，(AB)为公式； (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),例(29) 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=yx2+x5xz)x=5y2,指出公式的指导变元，辖域、约束变元和自由变元。,解： x=y，x2+x5，xz，x=5y2这是四个原子公式, 用逻辑词，来联结起来的。 x是指导变元、x的辖域是()内的这部分 x=yx2+x5xz 。 因此，x第一、二、三、四次出现是约束出现，x第五次出现是自由出现。 而y，z的出现均是自由出现。,第三章 谓词演算基础,3.1 谓词与个体 3.2 函数与量词 3.3 自由变元和约束变元 3.3.1 自由出现和约束出现 3.3.2 改名和代入 3.4 永真性和可满足性 3.5 唯一性量词与摹状词,一、改名,x(A(x，y)y(B(x，y)C(z) 其中, 同一个变元y既有约束出现又有自由出现。 对约束变元进行改名，使得 同一个变元要么为约束出现，要么为自由出现， 同时使不同的量词所约束的变元不同名.,改名的规则,(1) 改名是对约束变元而言，自由变元不能改名，改名时应对量词的指导变元及其作用域中所出现的约束变元处处进行； (2) 改名前后不能改变变元的约束关系； (3) 改名用的新名应是该作用域中没有使用过的变元名称。,例： x(A(x，y)y(B(x，y) 解： 可把公式改名为： x(A(x，y)z(B(x，z),例 对下面公式实施改名,(1) x(A(x，y)y(B(x，y)C(z) (2) xF(x，y)xG(x，y),解：(1) 可把公式改名为： x(A(x，y)u(B(x，u)C(z) (2) x是约束变元,y是自由变元。而x的两次出现尽管均是约束的,但分别在不同的辖域。含义是互相无关的。可以将一处换名,但不能与y同名。可以改名为： xF(x，y)uG(u，y),例 x(F(x,y) P(x) y(Q(x,y) R(x),解： x前两次出现是约束的,后两次出现是自由的。y第一次出现是自由的,第二次是约束的,准备将约束变元x改为u,约束变元y改为v,成为 u(F(u,y) P(u) v(Q(x,v) R(x),二、代入,谓词演算公式中的自由变元可以更改，称为代入。,代入是对自由变元而言， 约束变元不能代入。 代入后的式子是原式的特例,代入规则,(1) 代入必须处处进行，即代入时必须对公式中出现的所有同名的自由变元进行。 (2) 代入后不能改变原式和代入式的约束关系。 (3) 代入也可以对谓词填式而言，但也要遵循上面两条规则； (4) 命题变元也可以实施代入。,例 x(A(x，y)y(B(x，y)C(z),试把公式中的自由变元y 代以式子x2+2。,解：先对原式改名，x改为u，y改为v，改名后得： u(A(u，y)v(B(u，v)C(z) 最后代入得： u(A(u，x2+2)v(B(u，v)C(z) 验证公式可知，没有改变变元的约束关系，所以这种代入符合代入规则。,例 x(A(x，y)y(B(x，y)C(z),试把公式中的谓词变元A(e1，e2)代以 yD(e1，e2，y，x)。,解: 现在先对原式改名，x改为u，y改为v得： u(A(u，y)v(B(u，v)C(z)， 再对代入式改名，y改为t得： tD(e1，e2，t，x)， 最后代入，得： u(tD(u，y，t，x)v(B(u，v)C(z),第三章 谓词演算基础,3.1 谓词与个体 3.2 函数与量词 3.3 自由变元和约束变元 3.3.1 自由出现和约束出现 3.3.2 改名和代入 3.4 永真性和可满足性 3.5 唯一性量词与摹状词,