离散数学 第二章 谓词逻辑 24变元的约束

给定a为一个谓词公式,其中有一部分公式形式为("xpx)或(ヨx
px))。这里
"、ヨ后面所跟的x叫做量词的指导变元或作用变元,px)叫做相应量词的
作用域或辖域。在作用域中x的一切出现,称为xa中约束出现,x亦称为被相应量词中的指导变元所约
束。在a中除去约束变元以外所出现的变元称作自由变元。自由变元是不受约束的变元,虽然它有时也在
量词的作用域中出现,但它不受相应量词中指导变元的约束,故我们可把自由变元看作是公式中的参数。

例题1 说明以下各式的作用域与变元约束的情况。

a)("x)(px)→qx))

b)("x)(px)→(ヨyrxy))

c)("x)("y)(pxy)∧qyz))∧(ヨxpxy

d)("x)(px)∧(ヨxqxy)→(ヨyrxy))∨qxy

a)("x)的作用域是px)→qx),x为约束变元。

b)("x)的作用域是px)→(ヨyrxy)),(ヨy)的作用域是rxy),xy都是
约束变元。

c)("x)与("y)的作用域是(pxy)∧qyz)),其中xy是约束变元,z是自由
变元。(ヨx)的作用域是pxy),其中x是约束变元,y是自由变元。在整个公式中,x是约束出现,
y既是约束出现又是自由出现,z是自由出现。

d)("x)的作用域是px)∧(ヨxqxy)→(ヨyrxy)),x
y都是约束变元,但qxy)中的x是受ヨx的约束,而不是受
"x的约束。
qxy)中的xy是自由变元。

从约束变元的概念可以看出,px1x2,…,xn)是n元谓词,它有n个相互独立的自由变元,若对其中
k个变元进行约束则成为n-k元谓词,因此,谓词公式中如果没有自由变元出现,则该式就成为一个命题。
例如,("xpxyz)是二元谓词。(ヨy)("xpxyz)是一元谓词。

为了避免由于变元的约束与自由同时出现,引起概念上的混乱,故可对约束变元进行换名。使得一个变
元在一个公式中只呈一种形式出现,即呈自由出现或呈约束出现。

我们知道,一个公式的约束变元所使用的名称符号是无关紧要的。故:若对其中("xpx)与
"xpy)具有相同的意义。设ax)表示x不小于0,那么

"xax)表示一切x都使得x不小于0

"xay)表示一切y都使得y不小于0

"xat)表示一切t都使得t不小于0

这三个命题在实数域中都表示假命题“一切实数均不小于 0 。同理(ヨxpx)与(ヨy
py)意义亦相同。

为此,我们可以对公式a中的约束变元更改名称符号,这种遵守一定规则的更改,称为约束变元的换
名。其规则为:
(1)
对于约束变元可以换名,其更改的变元名称范围是量词中的指导变元,以及该量词作用域中所出
现的该变元,在公式的其余部分不变。
(2)
换名时一定要更改为作用域中没有出现的变元名称。

例题2"x)(p(x)rxy))∧qxy换名

解 可换名为:"z)(p(z)rxy))∧qxy),但不能改名为:("y
)(p(y)ryy))∧qxy)以 及(
"z)(p(z)rxy))∧q
xy)。因为后两种更改都将使公式中量词的约束范围有所变动。

对于公式中的自由变元,也允许更改,这种更改叫做代入。自由变元的代入,亦需要遵守一定的规则,
这个规则叫做自由变元的代入规则,现说明如下:
(1)对于谓词公式中的自由变元,可以作代入,代入时需要对公式中出现该自由变元的每一处进行。
(2)
用以代入的变元与原公式中所有变元的名称不能相同。

例题3 ($x)(py)ùr(x,y)代入。

解对y施行代入,经代入后公式为

($x)(p(z)ùr(x,z))

但是,($x)(p(x))ùr(x,x))($x)(p(z)ùr(x,y))这两种代入都是与规则不符的。

需要指出,量词作用域中的约束变元,当论域的元素是有限时,客体变元的所有可能的取代是可枚举的。

设论域元素为:a1 , a2 , … , an

则有如下等价式: ("x)a(x) û a(a1) a(a2 ) ,, a(an)

($x)a(x) û a(a1) a(a2 ) ,, a(an)

量词对变元的约束,往往与量词的出现顺序有关。

("y)( $x)(x<(y-2))表示任何y均有x,使得x<y-2($y)( $x)(x<(y-2))
表示存在yx,使得x<y-2

这些命题中的多个量词,我们约定从左到右的次序读出。需要注意的是量词次序不能颠倒,否则将与
原题意义不符。

原文地址:https://www.cnblogs.com/emanlee/p/1799109.html