逻辑语词典(逻辑基础 —)
谓词逻辑的语法(syntax)
相较于命题逻辑，谓词逻辑的词汇更加复杂一些。谓词逻辑的词汇集合可以表示为 \mathcal{L}=\{c,d,e,\cdots,P,Q,R,\cdots,f,g,h,\cdots\} . 可以看到，谓词逻辑的词汇包括三部分：
常数(constant)符号，一般用 c,d,e,\cdots 表示.
谓词(predicate)符号，一般用 P,Q,R,\cdots 表示，也称为关系(relation)符号.
函数(function)符号，一般用 f,g,h,\cdots 表示.
用归纳的方法可以定义 \mathcal{L}- 项(term)，简称项.
变量符号 x,y,z,\cdots 是项.
常数符号 c,d,e,\cdots 是项.
如果 t_1,t_2,\cdots,t_n 是项， f 是n元函数符号，那么 ft_1\cdots t_n 是项.
也可以简记为 t:=x\,|\,c\,|\,ft_1\cdots t_n .
紧接着，可以在项的基础上定义 \mathcal{L}- 公式(formula)，简称公式.
如果 t_1,t_2,\cdots,t_n 是项， P 是n元谓词符号，那么 Pt_1\cdots t_n 是公式，这是最简单的一类公式，又称为原子公式.
如果 \varphi 是公式，那么 \neg\varphi 是公式.
如果 \varphi 、 \psi 是公式，那么 (\varphi\wedge\psi) 、 (\varphi\vee\psi) 、 (\varphi\rightarrow\psi) 、 (\varphi \leftrightarrow \psi) 是公式.
如果 \varphi 是公式，那么 \forall x\varphi 、 \exists x\varphi 是公式.
上面这种定义也可以简写为
受到存在，任意两个量词的限制，变量又进一步分为约束变量和自由变量。这里引用另一本教材对于约束变量的定义：定义 \mathcal{F}(\varphi) 为一个映射，其像为 \varphi 中所有自由变量构成的集合，则有
\mathcal{F}(c)=\varnothing
\mathcal{F}(x)=\{x\}
\mathcal{F}(ft_1\cdots t_n)=\bigcup_{i=1}^{n}\mathcal{F}(t_i)
\mathcal{F}(\neg\varphi)=\mathcal{F}(\varphi)
\mathcal{F}((\varphi\,*\,\psi))=\mathcal{F}(\varphi)\cup\mathcal{F}(\psi) （其中星号表示命题联结词）
\mathcal{F}(\forall x\varphi)=\mathcal{F}(\varphi)-\{x\}
\mathcal{F}(\exists x\varphi)=\mathcal{F}(\varphi)-\{x\}
如果一个公式中没有自由变元，则将其称为句子(sentence).
谓词逻辑的语义(semantics)
类比命题逻辑，我们也需要一个赋值或者解释，来给 \mathcal{L} 中的符号赋予具体的意义. 对应于词汇 \mathcal{L} ，一个谓词逻辑公式的解释是一个二元组，记为 \mathcal{M}=(M,I) ，其中 M 是一个集合， I 是一个映射，其定义域为 \mathcal{L} 。 I 将词汇中的常数符号解释为 M 中具体的元素，将谓词（关系）符号解释为 M 上的关系（或子集），将函数符号解释为到 M 上的映射. 对于 \mathcal{L} 中的元素，我们一般不把映射写为 I(\cdot) ，而是写为 \cdot^I 或者 \cdot^\mathcal{M} . 我们有
对常数符号 c ， c^\mathcal{M}\in M .
对n元谓词符号 P ， P^\mathcal{M}\subseteq M^n .
对n元函数符号 f ， f^\mathcal{M}:M^n\rightarrow M
这样我们就构造了谓词逻辑公式的一个解释(interpretation)，更常用的称呼是称其为一个模型(model).
下面需要研究谓词公式在给定模型 \mathcal{M} 下的真假。这里有一个特殊情况，如果公式中不含自由变元，则可以类比命题逻辑给出真假性的定义，进一步定义 \mathcal{M}\models\varphi 。但对于含自由变元的公式 \varphi(x) ，是不存在所谓“真假”一说的，因为其中的变元 x 没有赋值。所以，我们还需要做的一项工作是给变元指派(assignment)意义，所谓指派实际上也是一个映射 \sigma(x)=a\in M . 我们将指派代入，就可以判定公式的真假了，如果得到的 \varphi(a) 在模型下为真，那么我们可以记作 \mathcal{M}\models\varphi(x)[\sigma] 或 \mathcal{M}\models\varphi(x)[a] .当命题中有多个变元时，同样可以记作 \mathcal{M}\models\varphi(x_1,\cdots,x_n)[a_1,\cdots,a_n] ， \mathcal{M}\models\varphi(x_1,\cdots,x_n)[\sigma] ，或 \mathcal{M}\models\varphi(\bar{x})[\bar{a}] .
部分教材会将变元指派视为模型的一部分，即 \mathcal{M}=(M,I,\sigma) ，此种情形下则无需区分公式与句子.
以上介绍了符号与变元的解释，下面可以定义项的解释.
若 t=x ，则 t^{\mathcal{M},[\sigma]}=\sigma(x) .
若 t=c ，则 t^{\mathcal{M},[\sigma]}=c^\mathcal{M} .
若 t=ft_1\cdots t_n ，则 t^{\mathcal{M},[\sigma]}=f^\mathcal{M}(t^{\mathcal{M},[\sigma]}_1,\cdots,t^{\mathcal{M},[\sigma]}_n) .
现在，我们可以定义公式的解释.
\mathcal{M}\models Pt_1\cdots t_n[\sigma] 当且仅当 P^\mathcal{M}t^{\mathcal{M},[\sigma]}_1\cdots t^{\mathcal{M},[\sigma]}_n ，或者 (t^{\mathcal{M},[\sigma]}_1,\cdots,t^{\mathcal{M},[\sigma]}_n)\in P^\mathcal{M} .
对于否定、合取、析取、蕴含、等价联结词的定义与命题逻辑中相同.
\mathcal{M}\models\exists x\varphi(\bar{x})[\sigma] 当且仅当存在 a\in M 使得 \mathcal{M}\models \varphi(\bar{x})[\sigma(a/x)] .
\mathcal{M}\models\forall x\varphi(\bar{x})[\sigma] 当且仅当对于任意 a\in M ，总有 \mathcal{M}\models \varphi(\bar{x})[\sigma(a/x)] .
