离散数学(2.4变元的约束)

1、122.4变元的约束变元的约束(Bound of variable2.1谓词的概念与表示谓词的概念与表示(2.2命题函数与量词命题函数与量词(Propositional functions & Quantifiers)2.3谓词公式与翻译谓词公式与翻译(Predicate formulae2.4变元的约束变元的约束(Bound of variable2.5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式(Equivalences & implications of predicate calculus)2.6前束范式前束范式(Prenex normal form2.7谓词演算的

2、推理理论谓词演算的推理理论(Inference theory of predicate calculus) 32.4变元的约束变元的约束(Bound of variable2.4变元的约束变元的约束(Bound of variable2.4.1变元的约束变元的约束2.4.2 约束变元的约束变元的换名与换名与自由变元的自由变元的代入代入42.4变元的约束变元的约束(Bound of variable2.4.1变元的约束变元的约束 (Bound of variable定义定义2.4.1:在在谓词谓词公式公式中中,形如形如( x)P(xx)P(x) )和和( x)P(xx)P(x) )的部的部分分,

3、称为称为谓词谓词公式的公式的x约束部分约束部分. ( x)P(xx)P(x) )或或( x)x)P(xP(x) )中中的的x叫做叫做量词的量词的指导变元指导变元或或作用变元作用变元，P(xP(x) )称为称为相应相应量量词的词的作用域作用域或或辖域辖域。在在 x x和和 x x的辖域中，的辖域中，x x的所有出现都称为的所有出现都称为约束出现约束出现，相，相应的应的x x称为称为约束变元约束变元; P(x; P(x) )中除约束变元以外出现的变中除约束变元以外出现的变元称为是元称为是自由变元自由变元。例例1 1： 1 1、 x x( H(x,y)H(x,y)y y( (W(yW(y) ) L(

4、x,y,z(x,y,z) ) ) 2 2、 x x( H(x)H(x)W(yW(y) ) y y( ( F(x) L(x,y,z(x,y,z) ) )52.4变元的约束变元的约束(Bound of variable 说明说明:(1)n元谓词公式元谓词公式A(x1，x2.xn) 中有中有n个自由变个自由变元元,若对其中的若对其中的k(kn)个进行约束个进行约束,则构成了则构成了n-k元谓词元谓词;如果一个公式中没有自由变元出如果一个公式中没有自由变元出现现,则该公式就变成了一个命题则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是一个公式的约束变元所使用的名称符号是无关紧要的无关

5、紧要的,如如( ( x)M(xx)M(x) )与与( ( y)M(yy)M(y) )意义相意义相同同. .62.4变元的约束变元的约束(Bound of variable2.4.2 约束变元的约束变元的换名与换名与自由变元的自由变元的代入规则代入规则在例在例1中中,一个变元在同一个公式中既是自由出现又是约一个变元在同一个公式中既是自由出现又是约束出现束出现,这样在理解上容易发生混淆这样在理解上容易发生混淆.为了避免这种混乱为了避免这种混乱,可对可对约束变元进行换名约束变元进行换名.换名规则换名规则: (对约束变元而言）对约束变元而言）对约束变元进行换名对约束变元进行换名,使得一个变元在一个公式

6、中只呈一使得一个变元在一个公式中只呈一种形式出现种形式出现(1)约束变元可以换名约束变元可以换名,其更改的变元名称范围是量词中的其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元指导变元以及该量词作用域中所出现的该变元,公式的公式的其余部分不变其余部分不变(2)换名时一定要更改为作用域中没有出现的变元名称换名时一定要更改为作用域中没有出现的变元名称72.4变元的约束变元的约束(Bound of variable 例例1: x x( P(x)P(x)R(x,yR(x,y) ) L(x,y(x,y) )换名为换名为 t t( P(t)P(t)R(t,yR(t,y) ) L(x,

7、y(x,y) ) x x( H(x,y)H(x,y) y y( (W(yW(y) ) L(x,y,z(x,y,z) ) )换名为换名为 x x( H(x,y)H(x,y) s s( (W(sW(s) ) L(x,s,z(x,s,z) ) )82.4变元的约束变元的约束(Bound of variable 代入规则代入规则（对自由变元而言）（对自由变元而言）对公式中自由变元的更改称为代入对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入对于谓词公式中的自由变元可以作代入,代代入时需要对公式中出现该自由变元的入时需要对公式中出现该自由变元的每一处每一处进行进行;(2)用以代入的变元与原公式中所有变元的名用以代入的变元与原公式中所有变元的名称不能相同称不能相同.例如对例例如对例1中的公式中的公式 x x( P(x)P(x)R(x,yR(x,y) ) L(x,y(x,y) ) 自由变元自由变元y y用用z z来代入来代入, ,得得 x x( P(x)P(x)R(x,R(x,z z) ) L(x,(x,z z) )92.4变元的约束变元的约束(Bound of variab