(资料图片)

translation

现有一个推理系统，有如下符号组成：

• 圆括号：\((\) 和 \()\)
• 逻辑连词：\(\lnot\) 和 \(\to\)
• 全称量词：\(\forall\)
• 变量：\(u-z\)
• 常量：\(a-e\)
• 函数：\(f-h\)
• 谓词：\(P-T\)

这个推理系统还包括项（term）、公式（formula）、自由出现（free occurrence）和替换（replacement）等概念。基于这些概念，我们可以定义某个项 \(t\) 是否可以毫无冲突地替换某个变量 \(x\)。这是推理的基础之一，你想先解决这个问题。

项（term）的定义如下：

• 所有的变量 \(v\) 是一个项
• 所有的常量 \(c\) 是一个项
• 如果 \(t_1,t_2,\dots,t_n\) 是一些项，\(f\) 是一个函数，则 \(f_{t_1,t_2,\dots,t_n}\) 是一个项

公式（formula）的定义如下：

• 如果 \(t_1,t_2,\dots,t_n\) 是一些项，\(P\) 是一个谓词，则 \(P_{t_1,t_2,\dots,t_n}\) 是一个公式，而且这种公式被称为原子公式（atomic formula）
• 如果 \(\varphi\) 和 \(\psi\) 都是公式，则 \((\lnot\varphi)\) 和 \((\varphi\to\psi)\) 都是公式
• 如果 \(\varphi\) 是公式，\(v\) 是变量，则 \(\forall v\varphi\) 是公式

\(x\) 可以在 \(\varphi\) 中自由出现（free occurrence）的定义如下：

• 如果 \(\varphi\) 是原子公式，\(x\) 可以在 \(\varphi\) 中自由出现当且仅当在 \(\varphi\) 中有 \(x\)（可以理解为字符 \(x\) 在字符串 \(\varphi\) 中出现）
• 如果 \(\varphi\) 是 \((\lnot\psi)\)，\(x\) 可以在 \(\varphi\) 中自由出现当且仅当 \(x\) 可以在 \(\psi\) 中自由出现
• 如果 \(\varphi\) 是 \((\psi\to\gamma)\)，\(x\) 可以在 \(\varphi\) 中自由出现当且仅当 \(x\) 可以在 \(\psi\) 中自由出现或在 \(\gamma\) 中自由出现
• 如果 \(\varphi\) 是 \(\forall v\psi\)，\(x\) 可以在 \(\varphi\) 中自由出现当且仅当 \(x\) 可以在 \(\psi\) 中自由出现且 \(x\neq v\)

对于所有公式 \(\varphi\)，变量 \(x\)，项 \(t\)，替换（replacement）\(\varphi^x_t\) 的定义如下：

• 如果 \(\varphi\) 是原子公式，那么 \(\varphi^x_t\) 是通过简单地将每个字符 \(x\) 替换为字符串 \(t\) 形成的表达式
• 如果 \(\varphi\) 是 \((\lnot\psi)\)，那么 \((\lnot\psi)^x_t=(\lnot\psi^x_t)\)
• 如果 \(\varphi\) 是 \((\psi\to\gamma)\)，那么 \((\psi\to\gamma)^x_t=(\psi^x_t\to\gamma^x_t)\)
• 如果 \(\varphi\) 是 \(\forall y\psi\)，那么 \((\forall y\psi)^x_t=\left\{\begin{array}{ll}\forall y(\psi^x_t) & & \text{if}\ x\neq y\\\forall y\psi & & \text{if}\ x=y\end{array}\right.\)

最后，无冲突替换的定义如下：

• 如果 \(\varphi\) 是原子公式，那么 \(t\) 始终可以在 \(\varphi\) 中无冲突替换 \(x\)
• 如果 \(\varphi\) 是 \((\lnot\psi)\)，那么 \(t\) 在 \(\varphi\) 中可以无冲突替换 \(x\) 当且仅当 \(t\) 在 \(\psi\) 中可以无冲突替换 \(x\)
• 如果 \(\varphi\) 是 \((\psi\to\gamma)\)，那么 \(t\) 在 \(\varphi\) 中可以无冲突替换 \(x\) 当且仅当 \(t\) 在 \(\psi\) 和 \(\gamma\) 中都可以无冲突替换 \(x\)
• 如果 \(\varphi\) 是 \(\forall y\psi\)，那么 \(t\) 在 \(\varphi\) 中可以无冲突替换 \(x\) 当且仅当：
  • \(x\) 不能在 \(\varphi\) 中自由出现，或
  • \(y\) 不能在 \(t\) 中自由出现，且 \(t\) 在 \(\psi\) 中可以无冲突替换 \(x\)