谓词真值树的元理论（逻辑小知识090）

谓词真值树的元理论（逻辑小知识090）

鉴于规则的表述方式，在刚刚完成真值树的第 10 行之后，就没有进一步的方法来应用规则了。

你可能会认为，因为第 1 行没有被选中——一个普遍量化的公式从来没有被选中——我们现在可以继续对不同的常量做更多的 UI。但是 UI 规则说我们对路径中已经存在的所有常量执行 UI，如果没有，则对新常量执行 UI。我们对路径中的所有常量都做了 UI；因此我们无需再做任何事情。这就是对机器进行编程以构建真值树的方式。

现在我们可以读出开放路径中原子语句的真值，并在两个个体 a 和 b 的域中构造一个反例。展开式是

(Fa ∨ Ga) · (Fb ∨ Gb) (前提展开式)

(Fa·Fb) ∨ (Ga·Gb)（结论展开式）

现在看看开放路径。我们得到以下结果：

V(Fa) = F,

V(Gb) = F,

V(Ga) = T,

V(Fb) = T

如果我们将这些真值重新代入展开式，我们就得到了一个真前提和错误的结论。因此，在两个成员的域中，我们已经证明我们得到了真前提和假结论。

现在想象一下，情况很可能是这样——虽然我们不想把树弄得这么大，但我们正在提出一个理论观点——我们的树产生了一条开放路径，其中包含原子函数，让我们参与到一个领域，比如说， 20个人。也就是说，开放路径中有 20 个不同的常数。

如果我们尝试扩展方法来寻找反例，我们将不会在 1 或 2 或 3 的普及中找到一个反例，我们可能会在 4 或 5 之后放弃，认为这个论点是有效的。

可是，等一下！

我们怎么知道呢？

这棵树为我们提供了至少 20 个具有不同常数的原子函数，但也许展开式会在 2 个之后向我们显示无效！

这个问题的答案是可以证明的（但我们不会证明），真值树方法为我们提供了可以找到反例的最小域，除非树似乎无限增长。

因此，当真值树确实给了我们一个反例，它给了我们找到它的最小域。

从技术上讲，逻辑学家首先在域中引入了无效性的概念。如果我们可以在其中找到反例，则论证在域中是无效的。

具有 n 个成员的域称为基数 n。可以证明，如果一个论证在基数为 n 的域中无效，那么它在所有更高基数的域中都是无效的。如果一个论证在任何大于零基数的域中有反例，则该论证无效。

为了看到这些观点，我们希望更清楚地考虑以下论证：

(∃x)Fx /∴ (x)Fx

如果我们对基数为 1 的域执行展开式，这个论证可能看起来是有效的，因为没有办法让前提为真而结论为假。但是如果我们展开到一个二元域，那么就有可能使前提为真而结论为假。

这表明，使用展开式方法，我们无法证明有效性，在以下意义上：

无论我们选择多大的域来展开我们的前提和结论，更大的域都有可能产生无效性。

如果一个论证是这样的，我们无法在基数 n 的域中得到真前提和假结论，我们将无法在基数较低的域中得到真前提和假结论，但仍有可能我们可以在更高基数的域中获得这样的结果。

这实际上是丘奇所证明的。

值得注意的是，虽然我们在这里不再赘述，但这个结果是关系谓词逻辑的函数。在没有联系的情况下，有一个用于测试无效性的公式：取论证中一元谓词的数量，比如 n；那么我们只需要测试基数为 2n 的域；如果在该域中没有发现证明无效，则它是有效的。因此一元谓词逻辑确实有一个决策过程！

现在看看我们在第 3 节中构造的第二棵真值树。

看起来，我们已经通过真值树将论证展开为两个元素的域。我们从这棵真值树中得到论证有效的结果——这意味着在所有基数大于零的域中。

所以这听起来好像与我们在上一段中学到的相矛盾。

如果我们已经展开到有两个元素的域且我们没有得到反例，那为什么要告诉我们有关更高域的基数的任何信息？

我们之前的结果表明它没有告诉我们有关这些域的任何信息！

问题只是显而易见的。

首先，再次回忆一下，一棵真值树总是会考虑足够多的域——也就是说，如果真值树规则不再适用且存在开放路径，则该论证的大小是无效的。

因此，尽管展开式方法可能会因为我们无意中选择了一个不足以显示无效的域而使我们失败，但真值树方法永远不会这样做。要么真值树会停止，我们不能再应用规则，并且至少有一条开放的路径，在这种情况下我们知道它是无效的，或者真值树可能看起来永远生长，在这种情况下，我们必须保留判断，因为论证的无效性。使用真值树规则编程的机器永远不会对论证是否无效的问题给出错误的答案。

现在回到关于我们的理论论证明显不相容的问题。有问题的真值树是否已经展开到两个元素的域，就像展开式方法一样？

如果是这样，我们怎么知道更大的域不会显示无效？

首先请注意，当我们构造一棵真值树时，我们使用结论的否定。

这就是我们答案的关键。

有问题的真值树告诉我们，在基数为 2 的域中，没有办法使前提和结论的否定都为真。

也就是说，由前提和结论的否定的合取组成的陈述在该域中不可能为真。

有一个元理论的结果，我们在这里也不会证明，如果一棵真值树是闭合的，那么我们已经证明了前提和结论的否定在基数为 n 的域中不可能同时为真，因此在所有具有基数大于零。

换句话说，前提和结论的否定的合取是矛盾的，因此它的否定，即论证的检验陈述，是逻辑真。在任何大于零的基数域中，没有办法使前提为真而结论为假。真值树规则保证我们将考虑大小合适的域来显示这一点。

换句话说，当真值树在没有开放路径的情况下停止时，我们实际上看到的是不需要考虑更多的情况——即不同基数的域。

所有其他情况都是这样的。

但是展开式方法这种说法不能成立，因为它没有规定使用什么大小的域执行展开式。

展开的方法是这样的，当我们取论证的前提和结论的否定并在基数 n 的域中解释它们时，我们可能会发现我们不能使前提和结论的否定都为真，这似乎证实了有效性。

但是如果我们展开到更大的领域，我们可能会发现我们可以同时使它们为真，因此这个论证将是无效的。

这就是我们之前的具有开放路径的真值树所发生的情况：

展开到一个元素的域会在前提和结论的否定之间产生不相容，但是两个元素的普及表明我们可以让它们都为真.当真值树中的所有路径都关闭时，完美机器运行的真值树方法将始终考虑正确大小的域，因此无需考虑其他情况。

让我们总结一下我们相当复杂的结果：

1. 树方法将机械地对它产生任何决定的每个论证产生一个正确的决定，并且它将对所有有效的论证产生一个正确的决定。

2. 我们应该能够使用展开式的方法来证明，如果我们选择一个特定大小的域，一个有效的论证将显示对该域有效，因此对于所有基数大于零的域。我们把它留给高级逻辑课程！

3. 如果我们通过真值树测试了论证无效，则该方法可能会失败，尽管展开式方法可能不会失败（参见上面的脚注，第 264 页。）。即使对于某些我们知道是无效的论证，真值树方法也不会产生决定。

第 1-3 点实际上是本章引言中提到的丘奇的不可判定性结果。要查看这些结果的实际效果，请考虑以下无效论证：

(x)(∃y)Lxy /∴ Laa

我们怎么知道这是无效的？

假设“Lxy”代表“x 爱 y”。

前提是每个人都爱一个人，结论是一个人爱一个人。

但是，每个人都爱某个人而不爱自己，这很容易成为事实，而如果 a 不爱自己，则结论是错误的。现在，如果我们构造一棵真值树，这就是我们得到的：

1. (x)(∃y)Lxy p /∴ Laa

2. ∼ Laa Negation of conclusion

✓ 3. (∃y)Lay 1 FC5

4. Lab 3 FC4

✓ 5. (∃y)Lby 1 FC5

6. LBC 5 FC4

✓ 7. (∃y)Lcy 1 FC5

8. Lcd 7 FC4

.

.

.

这棵树看起来好像它会永远生长。因此，机器不会给我们决定；如果是一台理想的机器，它将永远不会停止实例化。

为什么？

我们的 UI 规则告诉我们必须对开放路径中的每个常量进行 UI。

当我们从第 3 行到第 4 行执行 EI 时，我们当然必须对 a 以外的其他常量执行此操作，因为 a 已经出现在真值树中。

但这意味着第 4 行现在包含一个常量 b，当我们通过流程图回收时，我们现在必须在第 5 行做一个 UI。

现在我们还有另一个 EI 要做，整个过程重新开始。

如果我们可以构造一台机器来预测一棵真值树何时会无限增长，我们就会知道这个论证是无效的。

但丘奇的结果告诉我们，这正是机器无法做到的。如果可以的话，我们会有一个决策程序，而丘奇已经证明不可能有这样的程序。

既然我们知道这个论证是无效的，而且 丘奇已经表明，这种知识不能通过我们可以应用于所有论证的机械程序获得，这是否表明我们不是机器？

幸运的是（或者不幸的是，因为这是一个非常有趣的主题），这是其他哲学课的问题！