关于真值树模式识别与一阶逻辑不可判定性的技术问询

§10.3.5 保证真值树完成的扩展流程 #

Nicholas Smith所著《Logic: The Laws of Truth》的§10.3.5章节，规定了一套扩展未完成真值树的流程，确保最终得到的树是完成态的。以下是流程的精简版本：

阶段1：为树中每个命题分配地址 #

• 首个根命题的地址为1。
• 除根命题外，树中任意命题α的地址按以下规则分配：
  • 若命题直接位于地址为n的命题下方，则其地址为n1。
  • 若命题直接位于地址为n的命题左侧，则其地址为n1。
  • 若命题直接位于地址为n的命题右侧，则其地址为n2。

阶段2：按规则扩展真值树 #

按地址顺序遍历树中的每个命题，对每个访问到的命题α执行以下操作：

1. 若α不在任何开放路径上，或者α是原子命题/否定原子命题，或者α已被标记为处理完成，则跳过该命题，继续下一个。否则进入步骤2。
2. 根据α的类型应用对应规则：
   • 若α可应用联结词规则或否定量词规则：在α所在的每一条开放路径的底部应用该规则，并标记α为处理完成。
   • 若α可应用非否定量词规则：在α所在的每一条开放路径的底部应用该规则，使用路径上未出现过的字母表顺序首个名称，并标记α为处理完成。
   • 若α可应用非否定全称量词规则：在α所在的每一条开放路径的底部应用该规则——为路径上出现的每个名称各应用一次，但仅当生成的公式未在路径上出现时才执行；若路径上无任何名称，则使用名称a。由于α是全称量化合式公式，不要标记其为处理完成。
3. 每次向开放路径添加合式公式后，检查路径是否可闭合。

当所有命题处理完毕后：

• 若树有任何变化（比如添加了新命题、闭合了路径、标记了处理完成的公式等），回到阶段2的起始步骤重新遍历；否则停止流程。

根据我的理解，这套流程能保证真值树完成的原因在于：它强制我们在每一轮遍历中处理树中的所有合式公式，不会遗漏任何未处理的公式。

§10.3.6 真值树的模式识别问题 #

在上一节中，我们解决了两个问题中的一个：提出了一种策略，能将真值树的有限初始段扩展为完成态的树。接下来是第二个问题：如何识别该策略生成的树所呈现的模式，以便我们读出一个模型？这里的情况就不太乐观了。我们有一个有效的流程，可以将任何有限的真值树段扩展为完成态的树。但不存在有效的流程能判断完成后的树是否包含无限路径。这不是说没人想出这样的流程，而是已经被证明这样的流程不可能存在。

在后续章节中，这个结果被引入为一阶逻辑的不可判定性。

我的疑问 #

我对上述内容的核心要点有些困惑：

• 一个能判断真值树是否无限的流程，如何帮助我们识别树中的模式？是不是因为这样的流程必须能识别输出中的循环？
• 另外，§10.3.5中给出的算法（如本文概述的）不就是这样的流程吗？它能保证得到完成态的树，那如果我们应用它时发现一直在循环回到阶段2的起始步骤，是不是就能确定树是完成态且无限的？

备注：内容来源于stack exchange，提问作者user51462