离散数学 - 谓词逻辑
谓词逻辑处理谓词，即包含变量的命题。
谓词逻辑 – 定义
谓词是在某个特定域上定义的一个或多个变量的表达式。带有变量的谓词可以通过给变量赋值或量化变量来构成命题。
以下是谓词的一些示例 -
- 设 E(x, y) 表示“x = y”
- 设 X(a, b, c) 表示“a + b + c = 0”
- 设 M(x, y) 表示“x 与 y 结婚”
结构良好的公式
格式良好的公式 (wff) 是包含以下任意一项的谓词 -
所有命题常量和命题变量都是 wffs
如果 x 是变量且 Y 是 wff，则 $\forall x Y$ 和 $\exists x Y$ 也是 wff
真值和假值是wffs
每个Atomics式都是一个wff
所有连接 wff 的连接词都是 wff
量词
谓词的变量由量词来量化。谓词逻辑中有两种类型的量词 - 通用量词和存在量词。
通用量词
通用量词指出，其范围内的陈述对于特定变量的每个值都成立。它由符号$\forall$ 表示。
$\forall x P(x)$ 被读取为对于 x 的每个值，P(x) 都为 true。
示例- “人是终有一死的”可以转化为命题形式 $\forall x P(x)$，其中 P(x) 是谓词，表示 x 是终有一死的，并且话语的宇宙是所有人。
存在量词
存在量词指出其范围内的陈述对于特定变量的某些值是正确的。它由符号$\exists $ 表示。
$\exists x P(x)$ 被读取为对于 x 的某些值，P(x) 为 true。
示例- “有些人不诚实”可以转换为命题形式 $\exists x P(x)$，其中 P(x) 是谓词，表示 x 不诚实，而话语范围是某些人。
嵌套量词
如果我们使用的量词出现在另一个量词的范围内，则称为嵌套量词。
例子
$\forall\ a\: \存在 b\: P (x, y)$ 其中 $P (a, b)$ 表示 $a + b = 0$
$\forall\ a\: \forall\: b\: \forall\: c\: P (a, b, c)$ 其中 $P (a, b)$ 表示 $a + (b + c) = ( a + b) + c$
注意- $\forall\: a\: \exists b\: P (x, y) \ne \exists a\: \forall b\: P (x, y)$