谓词逻辑公式也可分为三类,一是普遍有效公式、一是可满足公式、一是不可满足公式。它们的定义依赖于谓词公式的解释。
在论域确定之后,一个谓词公式的解释,包括对谓词变项、命题变项、函数和自由个体的具体设定。
判别一个公式的普遍有效性问题就是判定问题。
一、普遍有效的公式
对一个谓词公式来说,如果在它的任一解释I下真值都为真,便称作普遍有效的。
如 ( x)
(P(x)∨ P(x))
( x)P(x)→P(y)
(y 是x个体域中的一个元素)。
( x)P(x)∨( x)Q(x)→( x)(P(x)∨Q(x))
都是普遍有效的公式。
前两个公式的普遍有效性容易看出,仅就第三个作些说明。不难看出,在该公式的任一解释(对P(x), Q(x)的设定)下, 若
( x)P(x)∨( x)Q(x)
= T 必有
( x)
(P(x)∨Q(x)) = T
从而( x)P(x)∨( x)Q(x)→( x)P(x)∨Q(x))必总为真。
对一个谓词公式来说,如果在它的某个解释I下真值为真, 便称作可满足的。
如( x)P(x),
( x)P(x)都是可满足的。
当取P(x)表"x是运动的"(一个解释)时,便有( x)P(x)
= T。当取P(x)是"x是学生"(一个解释)时,便有( x)
P(x) = T。从而它们都是可满足的公式。
对一个谓词公式来说,如果在它的任一解释I下真值均为假,便称作不可满足的。
如 ( x)
(P(x)∧ P(x))
( x)P(x)∧( y) P(y)
都是不可满足的。
若一个公式是普遍有效的,那么这公式的否定就是不可满足的,反过来也成立。
|