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

《离散数学第三章 谓词演算基础-自由变元和约束变元》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章谓词演算基础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

2、,...，tm)不是句子，仅是词，因而不是公式仅是项。项的结果仍是个体名称集合中的名词，而公式的结果(真值)是成立或不成立(是1或0)。合式公式的定义定义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)为合式公

3、式。(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的作用域为：

4、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，

5、y是约束变元，而不是自由变元。例xF(x)G(x,y)指出公式的指导变元，辖域、约束变元和自由变元。解：x的辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y的出现是自由出现。所以第一个x是约束变元，第二个x是自由变元，本质上这两个x的含义是不同的；而y仅是自由变元。例x(x=yx2+x<5x

6、第一、二、三、四次出现是约束出现，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)改名是对约束变元而言，自由变元不能改名，改名时应对量词的指导变元及其作用域中所出现的约束变元处处进

7、行；(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