离散数学 - 谓词逻辑

谓词逻辑处理谓词，谓词是包含变量的命题。

谓词逻辑 – 定义

谓词是在某个特定域上定义的一个或多个变量的表达式。通过为变量赋值或对变量进行量化，可以将包含变量的谓词变成命题。

以下是谓词的一些示例：

• 设 E(x, y) 表示 "x = y"
• 设 X(a, b, c) 表示 "a + b + c = 0"
• 设 M(x, y) 表示 "x 与 y 结婚"

良构公式

良构公式 (wff) 是满足以下任何条件的谓词：

• 所有命题常量和命题变量都是良构公式

• 如果 x 是一个变量，Y 是一个良构公式，则 $\forall x Y$ 和 $\exists x Y$ 也是良构公式

• 真值和假值是良构公式

• 每个原子公式都是良构公式

• 连接良构公式的所有连接词都是良构公式

量词

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

全称量词

全称量词指出其作用域内的语句对于特定变量的每个值都为真。它用符号 $\forall$ 表示。

$\forall x P(x)$ 读作对于 x 的每一个值，P(x) 为真。

示例：“人是凡人”可以转化为命题形式 $\forall x P(x)$，其中 P(x) 是表示 x 是凡人的谓词，论域是所有的人。

存在量词

存在量词指出其作用域内的语句对于特定变量的某些值成立。它用符号 $\exists$ 表示。

$\exists x P(x)$ 读作对于 x 的某些值，P(x) 为真。

示例：“有些人是不诚实的”可以转化为命题形式 $\exists x P(x)$，其中 P(x) 是表示 x 不诚实的谓词，论域是某些人。

嵌套量词

如果我们使用一个出现在另一个量词作用域内的量词，则称之为嵌套量词。

示例

• $\forall\ a\: \exists b\: P (x, y)$，其中 $P (a, b)$ 表示 $a + b = 0$

• $\forall\ a\: \forall\: b\: \forall\: c\: P (a, b, c)$，其中 $P (a, b, c)$ 表示 $a + (b + c) = (a + b) + c$

注意 – $\forall\: a\: \exists b\: P (x, y) \ne \exists a\: \forall b\: P (x, y)$