谓词逻辑

谓词逻辑处理谓词，谓词是命题，由变量组成。

谓词逻辑 - 定义

谓词是在某个特定域上确定的一个或多个变量的表达式。通过向变量授权一个值或量化变量，可以将具有变量的谓词变成一个命题。

• 考虑 E(x, y) 表示 "x = y"
• 考虑 X(a, b, c) 表示 "a + b + c = 0"
• 考虑 M(x, y) 表示 "x 与 y 已婚。"

量词

谓词的变量由量词量化。谓词逻辑中有两种类型的量词 - 存在量词和全称量词。

存在量词

如果 p(x) 是关于宇宙 U 的一个命题。那么它表示为 ∃x p(x)，读作“在变量 x 的宇宙中至少存在一个值，使得 p(x) 为真。量词 ∃ 称为存在量词。”

有几种方法可以用存在量词来写一个命题，即

(∃x∈A)p(x)     或     ∃x∈A     使得 p (x)     或     (∃x)p(x)     或     p(x) 对于一些 x ∈A 为真。

全称量词

如果 p(x) 是关于宇宙 U 的一个命题。那么它表示为 ∀x,p(x)，读作“对于每个 x∈U，p(x) 为真。”量词 ∀ 称为全称量词。

有几种方法可以用全称量词来写一个命题。

∀x∈A,p(x)     或     p(x), ∀x ∈A       或     ∀x,p(x)     或     p(x) 对于所有 x ∈A 为真。

量化命题的否定

当我们否定一个量化命题时，即，当一个全称量化的命题被否定时，我们得到一个存在量化的命题，当一个存在量化的命题被否定时，我们得到一个全称量化的命题。

量化命题否定的两条规则如下。这些也被称为德摩根定律。

示例：否定以下每个命题

1.∀x p(x)∧ ∃ y q(y)

解： ~.∀x p(x)∧ ∃ y q(y))
      ≅~∀ x p(x)∨∼∃yq (y)        (∴∼(p∧q)=∼p∨∼q)
      ≅ ∃ x ~p(x)∨∀y∼q(y)

2. (∃x∈U) (x+6=25)

解： ~( ∃ x∈U) (x+6=25)
      ≅∀ x∈U~ (x+6)=25
      ≅(∀ x∈U) (x+6)≠25

3. ~( ∃ x p(x)∨∀ y q(y)

解： ~( ∃ x p(x)∨∀ y q(y))
      ≅~∃ x p(x)∧~∀ y q(y)        (∴~(p∨q)= ∼p∧∼q)
      ≅ ∀ x ∼ p(x)∧∃y~q(y))

具有多个量词的命题

具有多个变量的命题可以用多个量词量化。多个全称量词可以以任何顺序排列，而不会改变所得命题的含义。同样，多个存在量词也可以以任何顺序排列，而不会改变命题的含义。

包含全称量词和存在量词的命题，这些量词的顺序不能互换，而不会改变命题的含义，例如，命题 ∃x ∀ y p(x,y) 意味着“存在某个 x，使得 p (x, y) 对每个 y 都为真。”

示例： 编写以下每个命题的否定。确定结果语句是真还是假。假设 U = R。

1.∀ x ∃ m(x²<m)

解： ∀ x ∃ m(x²<m) 的否定是 ∃ x ∀ m (x²≥m)。∃ x ∀ m (x²≥m) 的意思是存在某个 x，使得 x²≥m，对于每个 m。该语句为真，因为存在某个更大的 x，使得 x²≥m，对于每个 m。

2. ∃ m∀ x(x²<m)

解： ∃ m ∀ x (x²<m) 的否定是 ∀ m∃x (x²≥m)。∀ m∃x (x²≥m) 的意思是对于每个 m，存在某个 x，使得 x²≥m。该语句为真，因为对于每个 m，存在某个更大的 x，使得 x²≥m。