谓词逻辑的基本概念¶
谓词表示了多个个体词之间的关系。进一步地讲是给定的个体词到集合\(\{T, F\}\)上的一个映射，因此可以将其写为函数的形式，如\(P(x, y)\)
函数表示从一个集合到另一个集合的映射，通常使用小写字母进行表示。
有两种量词，即全称量词与存在量词。受到量词约束的变元称为约束变元，否则称为自由变元。量词只能作用于变元而不能作用于命题变项与谓词变项。变元使用小写字母表示。
合式公式¶
合式公式定义如下：
- 命题常项、命题变项和原子谓词公式都是合式公式
- 若\(A\)为合式公式，则\(\lnot A\)为合式公式
- 若\(A, B\)为合式公式，且\(A, B\)中无变元在一个中约束而在另一个中自由，则\((A\land B), (A\lor B), (A\rightarrow B), (A\leftrightarrow B)\)为合式公式。
- 若\(A\)为合式公式，\(x\)在\(A\)中为自由变元，则\((\forall x)A, (\exists x)A\)为合式公式
在有限论域下，全称量词与特称量词可与i表示为命题逻辑下的合式公式：
- \((\forall x)P(x) = P(1)\land P(2)\land \dots \land P(k)\)
- \((\exists x)P(x) = P(1)\lor P(2)\lor \dots \lor P(k)\)\
对于谓词公式，若在任何解释下真值都为真，称谓词公式为普遍有效的谓词公式；若在某个解释下真值为真，称谓词公式为可满足的谓词公式，否则称为不可满足的谓词公式。
- 谓词逻辑是不可判定的
- 只含有一元谓词变项的谓词公式是可判定的
- 个体域有限的谓词公式是可判定的