离散数学第五章__谓词逻辑.ppt

对于给定的谓词公式，能够准确地判定它的辖域、约束变元和自由变元是很重要的。 通常，一个量词的辖域B(x)是某公式A的一部分，称此辖域为A的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲： ①若量词后有括号，则括号内的子公式就是该量词的辖域； ②若量词后无括号，则与量词邻接的子公式为该量词的辖域。 判定给定公式A中个体变元是约束变元还是自由变元，关键是要看它在A中是约束出现，还是自由出现。 例 指出下列各合式公式中的量词辖域、个体变元的约束出现和自由出现。 (1) (?x) (P(x)→(?y) Q(x,y)),量词(?x)的辖域是P(x) → (?y) Q(x,y),量词(?y)的辖域是Q(x,y),对于(?y)的辖域而言，y为约束出现，x为自由出现。对于(?x)的辖域而言，x和y均为约束出现，x约束出现2次，y约束出现1次。 (2) (?x) H(x)∧L(x,y),量词(?x)的辖域是H(x) ，x为约束出现，L(x,y)中的x和y都为自由出现。对于整个公式而言，x的约束出现1次，自由出现1次，y自由出现1次。 (3) (?x) (?y) (P(x,y)∨Q(y,z))∧(?x)R(x,y),在公式(?x) (?y) (P(x,y)∨Q(y,z))中，量词(?x)的辖域是(?y) (P(x,y)∨Q(y,z))，量词(?y)的辖域是(P(x,y)∨Q(y,z))，x和y为约束出现，z为自由出现；在公式(?x)R(x,y)中,量词(?x)的辖域是R(x,y)，x为约束出现，y为自由出现。在整个公式中，x为约束出现，y为约束出现又为自由出现，z为自由出现。 今后常用元语言符号A(x)表示x是其中的一个个体变元自由出现的任意公式，一旦在A(x)前加上量词(?x)或(?x)，即得公式(?x)A(x),或(?x)A(x)。这时，x即是约束出现了。 类似地，用A(x,y)表示x和y是自由出现的公式。 从前面讨论可以看出，在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则，使得一个变元在一个公式只呈一种形式出现。 (1)约束变元换名规则： 约束变元换名时, 该变元在量词及其辖域中的所有出现(显然是约束出现)均须同时更改, 公式的其余部分不变。 换名时一定要更改为该量词辖域中没有出现过的符号。最好是公式中未出现过的符号。 (2)自由变元代入规则： ①对于谓词公式中的自由变元, 可以代入, 代入时须对该自由变元的所有出现(显然是自由出现)同时进行代入。 ②代入时所选用的变元符号与原公式中所有变元的符号不能相同。 例：将公式(?x)(P(x)→Q(x,y))∧R (x,y)中的约束变元改名。下面哪个正确？ 注意到此公式中，约束变元只有x, 1）(?y)(P(y) →Q (y,y))∧R (x,y) 2）(?z)(P(z) →Q (x,y))∧R (x,y) 3）(?z)(P(z) →Q (z,y))∧R (x,y) 例 在公式(?x) (Q(x) → R(x, y))∨(?z) P(x, z)中，x既为约束出现，又为自由出现，下面用两种方法，使变元x在公式中只呈一种形式出现 解 用约束变元的改名规则得: (?u) (Q(u) → R(u, y))∨(?z) P(x, z); 或用自由变元得代入规则得: (?x )(Q(x) → R(x, y))∨(?z) P(u, z)。 改名规则 代入规则 对象 约束变元 自由变元 范围 一个量词及其辖域内 整个公式 结果 只能换名为另一变元,而不能换名为个体常元, 换名后公式的含义不变。 可以代以另一变元；还可代入个体常元，此时公式由具有普遍意义变成仅对该个体常元有意义。 改名规则与代入规则的主要区别 5.2.2 公式解释与类型 1．公式解释 一般情况下，谓词逻辑中的公式含有：个体常元、个体变元（约束变元或自由变元）、函数变元、谓词变元等，对各种变元用指定的特殊常元去代替，就构成了一个公式的解释。下面给出解释的一般定义。 定义5.2.3谓词公式A的每一个解释I由如下四部分组成: 非空个体域DI； DI中部分特定元素a’,b’,…； DI上的特定一些函数f’,g’,…； DI上特定谓词：P’,Q’,…。 即,解释是针对谓词逻辑中的符号进行的,其对应关系为： 个体变元x,y,…在DI内取值； 个体常元a,b,…被解释成a’,b’,…； 函数符号f,g,…被解释成f’,g’,…； 谓词符号P,Q,…被解释成P’,Q’,…。 例5-15 给定解释I如下： （1）