一阶逻辑基本概念

表示个体词性质或相互之间关系的词称为谓词. $F(x)$ 表示 $x$ 具有性质 $F$.

全称量词 $\forall$

存在量词 $\exists$

对于全称量词 $\forall$, 应当用 $\to$ 代替 $\wedge$; 对于存在量词 $\exists$, 应当用 $\wedge$ 代替 $\to$.

一阶语言

定义 设 $L$ 是一个非逻辑符集合, 由 $L$ 生成的一阶语言 $\mathcal{L}$ 的字符表包含:

• 个体常项符号
• 函数符号
• 谓词符号
• 个体变项符号
• 两次符号
• 联结词符号
• 括号与逗号

个体常项和个体变项是项.

若 $\phi (x_1,...,x_n)$ 是任意的 $n$ 元函数, $t_1,...,t_n$ 是任意的 $n$ 个项, 则 $\phi (t_1,...,t_n)$ 是项.

定义 设 $R(x_1,...,x_n)$ 是 $\mathcal{L}$ 的任意 $n$ 元谓词, $t_1,...,t_n$ 是 $\mathcal{L}$ 的任意 $n$ 个项, 则称 $R(t_1,...,t_n)$ 是 $\mathcal{L}$ 的原子公式.

变元

定义 在公式 $\forall xA$ 与 $\exists xA$ 中, 称 $x$ 为指导变元, $A$ 为相应量词的辖域.

在 $\forall x$ 和 $\exists x$ 的辖域中, $x$ 的所有出现都称为约束出现; $A$ 中不是约束出现的所有变项都称为自由出现.

指向原始笔记的链接

定义 若公式 $A$ 中不含自由出现的个体变项, 称 $A$ 为闭式.

定理 闭式在任何解释下都是命题.

定理 对于一阶逻辑, 其判定问题是不可解的.

代换实例

定义 设 $A_0$ 是含命题变项 $p_1,p_2,...,p_n$ 的命题公式, $A_1,...,A_n$ 是 $n$ 个谓词公式, 用 $A_i$ 代替 $A_0$ 中的 $p_i$, 所得公式 $A$ 称为 $A_0$ 的代换实例.

指向原始笔记的链接

指向原始笔记的链接