谓词逻辑中公式的永真性与可满足性判定咨询

我来逐个拆解这些公式，帮你明确它们的类别：

• (a) (∃x P(x)) ⇒ (∀y P(y))
  属于可满足式（不是永真式）。你的初步分析完全到位——举个简单的例子：假设论域是全体自然数，让P(x)表示“x是奇数”。此时“存在x是奇数”是真的，但“所有y都是奇数”显然是假的，整个蕴含式就成了“真⇒假”，结果为假。不过它也有成立的场景，比如让P(x)表示“x是自然数”（论域还是自然数），这时候前件后件都为真，蕴含式自然成立。所以这个公式存在使它为真和为假的解释，是可满足式。

• (b) ∀x (P(x) ⇒ ∃y P(y))
  属于永真式，不管怎么给P做解释，它都不可能为假。我们可以从逻辑上掰扯清楚：对于任意一个x，如果P(x)是真的，那至少存在一个y（就是这个x本身）满足P(y)，所以P(x)⇒∃y P(y)为真；如果P(x)是假的，那蕴含式的前件为假，根据蕴含逻辑的规则，整个式子直接为真。所以对所有x来说这个蕴含式都成立，整个公式必然为真。

• (c) ∃x (P(x) ⇒ ∀y P(y))
  属于永真式，这个可能有点反直觉，我们分两种情况看：

  1. 如果所有论域元素都满足P（也就是∀y P(y)为真），那不管x选哪个，P(x)⇒∀y P(y)都是“真⇒真”，自然存在这样的x，公式为真；
  2. 如果不是所有元素都满足P（∀y P(y)为假），那肯定存在至少一个元素a使得P(a)为假，这时候P(a)⇒∀y P(y)就是“假⇒假”，结果为真，这个a就是我们要找的x，公式也为真。
     不管P怎么定义，这个公式都能成立，所以是永真式。

• (d) ∀x∃y (P(x) ⇒ P(y))
  属于永真式。同样分情况讨论：
  随便挑一个x，如果P(x)是真的，那我们直接选y=x，此时P(y)也是真的，蕴含式成立；如果P(x)是假的，那不管选哪个y，“假⇒P(y)”都符合蕴含逻辑的真规则。所以对每一个x，都能找到对应的y让式子成立，整个公式必然为真。

• (e) ∃y∀x (P(x) ⇒ P(y))
  属于永真式。我们换个角度拆解：

  • 如果论域里所有元素都满足P，那随便选一个y，对于任意x来说，P(x)⇒P(y)都是“真⇒真”，整个式子成立；
  • 如果论域里有部分元素满足P、部分不满足，那我们选一个满足P的y。这时候，对于满足P的x，蕴含式是“真⇒真”；对于不满足P的x，蕴含式是“假⇒真”，两种情况都为真，所以∀x(P(x)⇒P(y))成立，自然存在这样的y；
  • 如果所有元素都不满足P，那任意y都能让∀x(P(x)⇒P(y))变成“假⇒假”，结果为真。
    不管哪种情况，这个公式都能成立，所以是永真式。

内容的提问来源于stack exchange，提问作者sktsasus