谓词逻辑＜1＞——谓词逻辑

大家好，欢迎来到IT知识分享网。

$\S 1$ 谓词逻辑的基本概念

谓词

定义1.1 个体词 个体域(论域)

陈述句中的研究对象是个体词,分为个体变元和个体常元。个体词的取值范围是个体域(论域)$D$。

定义1.2 谓词

谓词描述研究对象的性质或研究对象之间的关系,含有$n$个个体变元的谓词称为$n$元谓词,而不包含个体变元的命题可视为零元谓词。

定义1.3 函词

从一个个体域到另一个个体域的映射,含有$n$个个体变元的函词称为$n$元函词$f^{\left(n\right)}$。

定义1.4 量词

量词用于限定个体词的数量,分为代表”所有的,任意的”的全称量词$\forall$,和代表”至少有一个”的存在量词$\exists$。
量词具有以下转换关系:$\forall xP\left(x\right)\iff \neg \exists x\neg P\left(x\right)$和$\exists xP\left(x\right)\iff \neg \forall x\neg P\left(x\right)$。

定义1.5 项

归纳定义如下:

1. 个体常元和个体变元是项;
2. 若$t_1,t_2,\dots ,t_n$都是项,$n$元函词$f^{\left(n\right)}$作用下的$f^{\left(n\right)}\left(t_1,t_2,\dots ,t_n\right)$也是项;
3. 只有有限次引用以上步骤确定的表达式才是项。

谓词演算

定义1.6 合式公式

归纳定义如下:

1. 不含逻辑联结词的谓词(原子谓词公式)为合式公式;
2. 若$A$为合式公式,则$A$的否定式也是合式公式;
3. 若$A$,$B$为合式公式,则$A$,$B$的析取式,合取式,蕴含式,双向蕴含式也是合式公式;
4. 若$A$为合式公式,$x$为个体变元,则$A$关于$x$的全称命题和存在命题也是合式公式;
5. 只有有限次引用以上步骤确定的表达式才是合式公式。

定义1.7 辖域

1. 量词$\forall v(\exists x)$与公式$A$毗邻;
2. 公式$A$的任意真截断$w$($A$截断后的字符串$w$长度小于公式$A$)都不是公式。

则称公式$A$为量词$\forall v(\exists x)$的辖域。

定义1.8 约束变元 自由变元

受量词$\forall v(\exists x)$约束的个体变元$v$,且出现在量词$\forall v(\exists x)$的辖域内,$v$称为约束变元,反之则为自由变元;$v$的出现称为约束出现,反之称为自由出现。

定义1.9 可代入

若公式$A$中自由变元$v$的任意自由出现都不在量词$\forall u(\exists u)$的辖域内,则对任意项$t$,项$t$对公式$A$中自由变元$v$可代入,其中$u$是项$t$中的任意变元。若对公式$A$中$n$个自由变元$v_1,v_2,\dots v_n$同时做代入操作,其中$v_1,v_2,\dots v_n$替换为$t_1,t_2,\dots ,t_n$,记为$A_{t_1,t_2,\dots ,t_n}^{v_1,v_2,\dots v_n}$。

定义1.10 代入

若项$t$对公式$A$中自由变元$v$可代入,则对公式$A$中自由变元$v$的所有自由出现代换为项$t$的过程称为代入,代换结束后的公式$A_v^t$称为$A$的代入实例,若$A$中不存在$v$的自由出现,则$A_v^t=A$。

定义1.11 易名规则

为保持变元的独立性,可将量词变元及该量词变元在辖域内的所有出现替换为未在公式中任何地方出现的新变元。

定义1.12 子公式

若公式$B$是公式$A$的子串,且$B$的字符串长度小于$A$,则$B$是$A$的子公式。