谓词逻辑公式也可分为三类,一是普遍有效公式、一是可满足公式、一是不可满足公式。它们的定义依赖于谓词公式的解释。
  在论域确定之后,一个谓词公式的解释,包括对谓词变项、命题变项、函数和自由个体的具体设定。
  判别一个公式的普遍有效性问题就是判定问题。

一、普遍有效的公式

  对一个谓词公式来说,如果在它的任一解释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)
  都是不可满足的。
  若一个公式是普遍有效的,那么这公式的否定就是不可满足的,反过来也成立。