本系列笔记仅为个人备忘记录
如有谬误、补充，还望不吝指正

我们已经学过命题逻辑推理，那为什么还要学习谓词逻辑呢，我们看下面的例子：

这个推理显然是有效的，但它用命题逻辑是无法推证的，因为命题$A,B,C$在内部是有联系的，如果我们把它变成大写字母，这种联系就被抹除了，所以我们必须把命题这个陈述句细分

1 基本概念

1.1 个体

能够独立存在的具体或抽象的事物，称之为个体或客体，通常用小写字母$a,b,c\dots$表示

1.1.1 个体常项

具体的或特定的个体，常用$a,b,c\dots$等表示

1.1.2 个体变元

泛指某一个个体，常用$x,y,z\dots$表示

1.2 谓词

用于刻画个体属性或者表达个体之间关系的词，叫做谓词，一般使用大写字母表示

把谓词当做函数，个体当做参数，就可以构造命题

由这两个命题符号就能看出小张和小李都是大学生这个共性

谓词也有常项和变项之分，明确表达某种性质或关系的叫谓词常项，如果是泛指则是谓词变项

1.2.1 N元谓词

含有$n(n>0)$个个体变元的谓词$P$称为$n$元谓词，记作$P(x_{1},x_{2},\dots,x_{n})$

将不带个体变元的谓词称为0元谓词

1.3 命题函数

含有$n$个变元的命题函数是以个体域为定义域，以$\left\{ F,T \right\}$为值域的$n$元函数

$A(x):x身体好$，$G(x,y):x>y$，$B(x,y,z):点x在点y和点z之间$，这些都是命题函数，并且是简单命题函数

1.3.1 复杂命题函数

和复杂命题公式一样，复杂命题函数就是把简单命题函数用各种连接词连接起来

例：$A(x):x身体好,B(x):x学习好,C(x):x工作好$，则$\neg A(x)\to(\neg B(x)\land \neg C(x)):如果x身体不好，则x的学习与工作都不会好$

1.4 个体域

个体变元的取值范围，称之为个体域，也叫论域

由所有个体组成的个体域，叫全总个体域，包含世界万事万物，对于一个命题函数如果没有特殊说明，我们认为其个体变元的取值范围就是全总个体域

1.5 量词

表示对个体量化的词，称之为量词

例如：有些人是大学生、所有事务都是发展变化的

1.5.1 存在量词

记作$\exists$，表示有些，一些，某些，至少一个等

1.5.2 全称量词

记作$\forall$，表示每个，任何一个，所有，任意等

1.5.3 指导变元

指明量词对哪个个体变元进行量化，称此个体变元为指导变元

如$\forall x,\exists x$，其中的x就是指导变元

所以一般来说对于全称量词，特性谓词一般作为蕴含的前件；对于全称量词，特性谓词一般作为合取使用

2 谓词公式

2.1 原子谓词公式

称$n$元谓词$P(x_{1},x_{2},\dots,x_{n})$为原子谓词公式，例如$P,Q(x),A(x,y)$都是原子谓词公式

2.2 谓词合式公式

1. 原子谓词公式是合式公式
2. 如果$A$为合式公式，则$\neg A$也为合式公式
3. 如果$A,B$为合式公式，则$(A\land B),(A\lor B),(A\to B),(A\leftrightarrow B)$都是合式公式
4. 如果$A$是合式公式，$x$是$A$中的个体变元，则$\forall xA和\exists xA$都是合式公式
5. 有限次应用1-4得到的公式都是合式公式

为了方便，最外层括号可以省略

2.3 量词的辖域

2.3.1 量词的辖域

在谓词公式中，量词的作用范围叫做量词的作用域，也叫辖域

例：$\forall xA(x)$中$\forall x$的辖域为$A(x)$
$\exists x(A(x)\to B(x))$中$\exists x$的辖域为$(A(x)\to B(x))$
$\forall x((P(x)\land Q(x))\to \exists yR(x,y))$中$\forall x$的辖域为后面括号里的所有东西，$\exists y$的辖域是$R(x,y)$

所以我们得到以下规律：

• 如果量词后边只有一个原子谓词公式，则辖域就是这个原子谓词公式
• 如果量词后面有括号，则此括号的范围就是量词的辖域
• 如果量词后面紧挨着量词，则量词的辖域为后面的量词及其辖域

2.3.2 自由变元和约束变元

谓词公式中的个体变元可以分为两种，一种是受到量词约束的，称作约束变元；一种是不受量词约束的，称作自由变元

一个$n$元谓词$P(x_{1},x_{2},..,x_{n})$，若在前面添加$k$个量词，使其中的$k$个个体变元变成约束变元，$n$元谓词就变成了$n-k$元谓词，一个谓词公式如果没有自由变元，它就表示一个命题

2.3.2.1 约束变元的换名

对于上面那个例子$\forall x(F(x,y)\to \exists yP(y))\land Q(z)$，其中$y$既是自由变元又是约束变元，为了避免混淆，我们就需要对约束变元换名

换名规则：对$A$中约束变元换名，将$A$中某量词辖域内的一个约束变元的所有出现及相应的指导变元全部换成$A$中没出现过的某个变元符号，其余部分不变，就完成了换名

对于这个例子，如果我们把重复的$y$换成$t$，我们就能得到：$\forall x(F(x,y)\to \exists tP(t))\land Q(z)$

2.3.2.2 自由变元的代入

和上面一样，对象变成自由变元，不废话了

3 命题符号化

基本的命题符号化：

1. 主语里是具体的对象的，用谓词加括号来，括号里写对象~~传参~~来表达
2. 描述所有的、任意的个体对象，用全称量词，特性谓词作蕴含前件
3. 描述一些课题对象，用存在量词，特性谓词作合取项

在命题的符号化表达中，所有的个体变元都必须是约束变元，才能表示命题

4 谓词公式的等价式和蕴含式

4.1 对谓词公式的赋值

• 指定非空的个体域集合
• 把谓词公式中的命题变元用确定的命题替代
• 把谓词公式中的个体变元用个体域中的具体个体替代
• 把谓词变项用谓词常项替代

4.2 谓词公式的永真式

给定谓词公式$A$，如果不对它做任何赋值，它的真值就是真，则我们称这种谓词公式为永真式

4.3 谓词公式的等价式

给定谓词公式$A,B$，如果$A\leftrightarrow B$是永真式，则称$A$和$B$等价，记作$A\Leftrightarrow B$

例：$N(x)\to I(x)\Leftrightarrow \neg N(x)\lor I(x)$

4.4 谓词公式的永真蕴含式

给定谓词公式$A,B$，如果$A\to B$是永真式，则称$A$永真蕴含$B$，记作$A\Rightarrow B$

例：$(G(x)\land N(x)\Rightarrow N(x)$

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

只要不涉及到量词，名词逻辑的东西可以直接拿过来用，这里不再废话

4.5.1 有限个体域消去量词的等价公式

设论域为$\left\{ a_{1},a_{2},\dots,a_{n} \right\}$，则

1. $\forall xA(x)\Leftrightarrow A(a_{1})\land A(a_{2})\land\dots \land A(a_{n})$
2. $\exists xA(x)\Leftrightarrow A(a_{1})\lor A(a_{2})\lor\dots \lor A(a_{n})$

---

上面是有限个体域情况下的处理办法，但是很多个体域都是无限的，对于这些问题，我们只要研究清楚量词与$\neg,\land,\lor$之间的关系，谓词表达式的运算也就清楚了

4.5.2 量词否定等价公式

$$
\begin{align}
\neg \forall xA(x)\Leftrightarrow \exists x\neg A(x) \\
\neg \exists xA(x)\Leftrightarrow \forall x\neg A(x)
\end{align}
$$

这个等价公式被称为量词的转换律，即量词通过一个$\neg$转换之后就可以实现全称变存在，存在变全称

4.5.3 量词辖域的扩充与收缩

$$
\begin{align}
&\forall xA(x)\lor B\Leftrightarrow \forall x(A(x)\lor B) \\
&\forall xA(x)\land B\Leftrightarrow \forall x(A(x)\land B) \\
&\exists xA(x)\lor B\Leftrightarrow \exists x(A(x)\lor B) \\
&\exists xA(x)\land B\Leftrightarrow \exists x(A(x)\land B) \\
\\
&B\to \forall xA(x)\Leftrightarrow \forall x(B\to A(x)) \\
&B\to \exists xA(x)\Leftrightarrow \exists x(B\to A(x)) \\
&\forall xA(x)\to B\Leftrightarrow \exists x(A(x)\to B) \\
&\exists xA(x)\to B\Leftrightarrow \forall x(A(x)\to B)
\end{align}
$$

4.5.4 量词分配公式

$$
\begin{align}
&\forall x(A(x)\land B(x))\Leftrightarrow \forall xA(x)\land \forall xB(x) \\
&\exists x(A(x)\lor B(x))\Leftrightarrow \exists xA(x)\lor \exists xB(x) \\
&\exists x(A(x)\land B(x))\Rightarrow \exists xA(x)\land \exists xB(x) \\
&\forall xA(x)\land \forall xB(x)\Rightarrow \forall x(A(x)\lor B(x)) \\
&\exists x(A(x)\to B(x))\Leftrightarrow \forall xA(x)\to \exists xB(x) \\
&\exists xA(x)\to \forall xB(x)\Rightarrow \forall x(A(x)\to B(x))
\end{align}
$$

4.6 前束范式

• 所有量词前面都没有连接词
• 所有量词都在公式的左边
• 所有量词的辖域都延伸到公式的末尾
  如果一个谓词公式满足以下条件，它就是前束范式

例：$\exists y\forall x\exists z(A(x)\to(B(x,y)\lor C(x,y,z)))$

4.6.1 求前束范式的步骤

1. 消去公式中的$\to,\leftrightarrow$
2. 如果量词之前有$\neg$，用量词转化把$\neg$后移
3. 用约束变元的改名或自由变元的代入对变元换名
4. 用量词辖域扩充公式提取量词，使之成为前束范式的形式

5 谓词演算的推理

在谓词逻辑中，我们多了一个量词的概念，所以谓词演算的推理实际上相比命题逻辑来说就是增加了量词的处理，我们增加了四个规则,US,ES,EG,UG，用于脱掉和添加量词

5.1 推理方法

• 直接推理
• 条件论证
• 反证法

5.2 所用公式

• 基础等价公式
• 基础重言蕴含公式
• 谓词公式特有的各种等价公式

5.3 推理规则

• P，T，CP

5.3.1 全称特指规则 US

$\forall xA(x)\Rightarrow A(c)$(其中$c$是个体域内任意指定个体)

可以用于去掉全称量词

5.3.2 存在特指规则 ES

$\exists xA(x)\Rightarrow A(c)$(其中$c$是个体域内使$A(c)$为$T$的某个体)

可以用于去掉存在量词

5.3.3 存在推广规则 EG

$A(c)\Rightarrow \exists xA(x)$(其中$c$是个体域内某个体)

添加存在量词

5.3.4 全称推广规则 UG

$A(c)\Rightarrow \forall xA(x)$(其中$c$是个体域内任意某个个体)

添加存在量词

一	二	三
(1)	$M(a)$	P
(2)	$\forall x(M(x)\to C(x))$	P
(3)	$M(a)\to C(a)$	US(a)
(4)	$C(a)$	T(1)(3)I

一	二	三
(1)	$\exists xA(x)$	P
(2)	$A(c)$	ES(1)
(3)	$\forall x(A(x)\to B(x))$	P
(4)	$A(c)\to B(c)$	US(3)
(5)	$B(c)$	T(2)(4)I
(6)	$\exists xB(x)$	EG(5)

例：$\exists x(P(x)\to Q(x))\Rightarrow \forall xP(x)\to \exists xQ(x)$

一	二	三
(1)	$\exists x(P(x)\to Q(x))$	P
(2)	$\forall xP(x)$	P
(3)	$P(a)$	US(2)
(4)	$P(a)\to Q(a)$	ES(1)
(5)	$Q(a)$	T(3)(4)I
(6)	$\exists xQ(x)$	EG(5)
(7)	$\forall xP(x)\to \exists xQ(x)$	CP