离散数学第四章谓词逻辑

这是一篇关于离散数学第四章谓词逻辑的思维导图，包含个体、谓词、量词和函词、谓词公式及命题的符号化、谓词公式的前束范式等。

谓词逻辑

• 个体、谓词、量词和函词
  • 个体
    • 命题考虑的对象称为个体
    • 个体是独立存在的事物。个体可以是具体的，如 5、3、2 和 张三，也可以是抽象的，如人等。
    • 特定的、具体的个体称为个体常量
    • 不确定的个体称为个体变元
    • 在讨论个体时，通常要指定个体讨论的范围，称为个体域，用 D 表示，一般假定 D 非空
    • 我们把世界上所有能想象得到的对象，如所有动物、所有植 物、所有字母、所有数字等，组成的集合称为全总个体域，简 称全域，它是最大的个体域。
  • 谓词
    • 表示个体性质以及个体之间关系的词称为谓词（predicate）。 谓词就是关系
    • 表示一个个体性质的谓词称为1 元谓词，表示 n 个个体之 间关系的谓词称为n 元谓词。
    • 对于任意的 n 元谓词，为了把谓词及其元数同时表示出来， 像表示 n 元函数一样，用诸如P(x1, x2, · · · , xn)的形式表示。
    • 而 G(x, y) : x > y，它是关于命题的函数，称为命题函数
    • 谓词的选取与个体域有关
      • 若在全域中考虑，需要两个谓词
        • P(x) 称为特性谓词，
        • 子主题
  • 量词
    • 使 P(x) 成为命题的另一种方法是量化个体变元 x
      • 全称量化
      • 存在量化。
    • 表示个体数量特征的词称为量词
      • 全称量词 ∀
      • 存在量词 ∃
    • 现在的量化仅对个体进行，不对谓词进行，因而称为一阶谓 词逻辑
    • 量词的后面一定要跟个 体变元，如 ∀x, ∀y, · · · , ∀δ，∃x, ∃y, · · · , ∃δ。所以，∀x, ∃x 是一个 整体。量词后面所跟的个体变元称为指导变元
    • 若将命题函数中的所有个体变元都进行量化，则得到一个命 题
    • 量词 ∀x 或 ∃x 的作用或管辖的范围称为 ∀x 或 ∃x 的作用域或辖 域（scope），辖域内的个体变元 x 称为约束变元
      • 若量词后有括号，括号里面的部分是其辖域，如 ∀x(P(x)→D(x))；
      • 若没有括号，则与量词相邻的部分是辖域 ，如 ∃xP(x)。
      • 不受任何量词约束的变元称为自由变元
    • 子主题
  • 函词
    • 要把如“张三的父亲”、“两个数的平方和”等表示出来，就要用函 数，在谓词逻辑中习惯称为函词
• 谓词公式及命题的符号化
  • 谓词公式
    • 谓词公式（predicate formula）简称公式，同命题公式的理解一 样，只要是书写正确、意义清楚的（含谓词）符号串或表达式就 是谓词公式
    • 对应任意自然数 n，n 元谓词 P 和 n 个任意个体 t1,t2, · · · ,tn，P(t1,t2, · · · ,tn) 是谓词公式。
    • A 是谓词公式，则 ¬A 是谓词公式。
    • 若 A 和 B 是谓词公式，则 A ⋆ B 是谓词公式，其中 ⋆ 是二元 逻辑联结词。
    • 若 A 是谓词公式，则 ∀xA，∃xA 是谓词公式。
    • 有限次使用上面的 (1)(2)(3)(4) 得到的符号串是仅有的谓词 公式。
    • 若 A 和 B 是谓词公式，则 A ⋆ B 是谓词公式，其中 ⋆ 是二元 逻辑联结词。
    • 子主题
    • 子主题
    • 子主题
    • 子主题
  • 命题的符号化
    • 子主题
    • 在谓词逻辑中将命题符号化的步骤如下
      • (1) 找出命题中的所有个体常量，并用 a, b, c, · · · , ai, bi, · · · 表示；
      • (2) 确定在给定个体域中应该选用的所有谓词，特别要注意特性 谓词的选取；
      • (3) 确定量词；
      • (4) 确定函词；
      • (5) 找出联结词，将所给命题符号化。
    • 子主题
    • 子主题
• 谓词公式的解释及类型
  • 谓词公式的解释
    • 谓词公式的解释有无限多种，每种解释（interpretation）I 由 5 部分组成，
      • 指定个体域 D。
      • 对于谓词公式中的命题变元指派其真值
      • 将谓词公式中的个体常量及其自由变元解释为指定个体域 D 中的元素
      • 将谓词公式中的函词解释为 D 上的函数
      • 将谓词公式中的谓词解释为 D 上的谓词
    • 两个消去量词的逻辑等值式
  • 谓词公式的类型
    • 在任何解释下均为真的谓词公式称为永真式或有效式
      • （永真式代入定理）对于命题逻辑中的任何永真式，如 (p → q) ∧ p → q，分别用任意谓词公式 A, B 全部替换命题变元 p, q 所得到的谓词公式 (A → B) ∧ A → B 是永真式
      • 子主题
      • 子主题
    • 至少存在一种解释使其为 1 的谓词公式称为可满足式 （satisfactable formula），否则称为不可满足式或矛盾式或永假式
    • 既存在取 1 的解释，又存在取 0 的解释的谓词 公式称为中性式或偶然式
    • 中性谓词公式无法在有限步内判定；永真（或永假）谓词公式可在 有限步内判定。
• 谓词逻辑中的推理
  • 逻辑蕴涵式
    • 设 H1,H2, · · · ,Hn 和 C 是命题公式，若 H1,H2, · · · ,Hn 全为真， 可得出 C 必然真的结论，则称由 H1,H2, · · · ,Hn 得出 C 的推理 形式是有效的（valid argument form），记为H1,H2, · · · ,Hn ⇒ C。
    • 设 H1,H2, · · · ,Hn 和 C 是命题公式，则 H1,H2, · · · ,Hn ⇒ C 的充 要条件是 H1 ∧ H2 ∧ · · · ∧ Hn → C 是永真式， 即H1 ∧ H2 ∧ · · · ∧ Hn ⇒ C
    • 子主题
  • 基本推理规则
    • 下列逻辑蕴涵式成立： (1) ∀xA(x) ∨ ∀xB(x) ⇒ ∀x(A(x) ∨ B(x)). (2) ∃x(A(x) ∧ B(x)) ⇒ ∃xA(x) ∧ ∃xB(x).
    • 子主题
    • 子主题
• 谓词公式的前束范式
  • 谓词公式的前束范式的定义
    • 设 A 是谓词公式，若 A = Q1x1Q2x2 · · · Qnxn(· · · B · · ·)(n ≥ 0)， 其中 Qi 为 ∀ 或 ∃，B 中不含量词，则称 A = Q1x1Q2x2 · · · Qnxn(· · · B · · ·) 为 A 的前束范式
    • 子主题
    • 子主题
  • 谓词公式的前束范式的计算
    • 1. 将逻辑联结词归约到只含 ¬, ∧, ∨ 的谓词公式。
    • 2. 使用以下两个等值式将否定联结词往里面移。 (1) ¬∀xA(x) = ∃x¬A(x) (2) ¬∃xA(x) = ∀x¬A(x)
    • 3. 使用等值式将所有量词移到最前面，必要时使用改名技巧。
    • 子主题
• 逻辑等值的谓词公式
  • 谓词公式等值的定义
    • 设 A, B 是谓词公式，若 A 和 B 在任何解释下的取值都相同， 则称 A 和 B 是逻辑等值的，记为 A = B。
    • A = B 的充要条件是谓词公式 A ↔ B 永真。
    • 子主题
  • 基本等值式
    • ¬∀xA(x) = ∃x¬A(x).
    • ¬∃xA(x) = ∀x¬A(x).
    • ∀x(A(x) ∧ B) = ∀xA(x) ∧ B
    • ∀x(A(x) ∨ B) = ∀xA(x) ∨ B
    • ∃x(A(x) ∧ B) = ∃xA(x) ∧ B
    • ∃x(A(x) ∨ B) = ∃xA(x) ∨ B.
    • ∀x(A(x) ∧ B(x)) = ∀xA(x) ∧ ∀xB(x)
      • ∀ 对 ∧ 可分配，但 ∀x(A(x) ∨ B(x)) ̸= ∀xA(x) ∨ ∀xB(x)。例如， 给定解释 I，D = Z, A(x) : x 是偶数，B(x) : x 是奇数。
    • ∃x(A(x) ∨ B(x)) = ∃xA(x) ∨ ∃xB(x)
      • ∃ 对 ∨ 可分配，但 ∃x(A(x) ∧ B(x) ̸= ∃xA(x) ∧ ∃xB(x).
    • 双重量词
      • ∀x∀yA(x, y) = ∀y∀xA(x, y).
      • ∃x∃yA(x, y) = ∃y∃xA(x, y)
      • 等值置换定理在谓词逻辑中仍然成立。
    • 子主题
  • 子主题