3. 谓词逻辑

谓词

• \(\forall\) 全称量词
• \(\exists\) 存在量词

例题

合式公式

• 个体禅院和个体变元是项
• 若 f 是n元函数，且\(t_1,t_2,...\)是项，则\(f(t_1,t_2)\)是项
• 所有项都有 上面两条生成

例题

表示步骤

• 正确理解给定命题
• 分解、给出特性谓词
• 找出恰当量词：注意全称量词后跟 条件式，存在量词后跟 合取式
• 表示：用恰当的联结词吧灵体表示出来

谓词演算的等价式与蕴含式

若谓词公式论域为有限集，则可以通过一下方式消去量词

• \(\forall x A(x) \Leftrightarrow A(a_1)\land ... \land A (a_n)\)
• \(\exists x A(x) \Leftrightarrow A(a_1) \lor ... \lor A (a_n)\)

量词否定等价式

• \(\neg (\forall x) A \Leftrightarrow (\exists x) \neg A\)
• \(\neg (\exists x) A \Leftrightarrow (\forall x) \neg A\)

辖域扩大和缩小

• (a)(b) (e)(f) 一起记忆
• (c)(d) (g)(h) 一起记忆
• (c) 重要: \((\forall x)(A(x)\rightarrow B) \Rightarrow (\exists x) A(x)\rightarrow B\)

量词分配等价式

• \((\forall x) (A(x) \land B(x)) \Leftrightarrow (\forall x)A(x) \land (\forall x)B(x)\)
• \((\exists x) ((A(x) \lor B(x)) \Leftrightarrow (\exists x)A(x) \lor (\exists x)B(x))\)
• 全称量词与合取搭配
• 存在量词和析取搭配

蕴含式

注意以下为蕴含关系，和上面的等价关系不一样

前束范式

满足形式：

\((Q_1x_1)(Q_2x_2)(Q_nx_b)B\),

其中 \(Q_i\) 为量词，B 为不含量词的公式。

所有量词均非否定地出现在公式最前面，其辖区一致延伸到公式之末。

例题