By Matthew Prast 2025年3月4日 — 7 分钟阅读

关于形式系统和谎言小妖精的简短思考

前几天我在网上看到有人在讨论电影 Labyrinth 里的一个场景，这是一部80年代的电影（如果你没看过，你应该去看一下——华丽的歌舞表演，非常令人不安的 Jim Henson 木偶戏，David Bowie 穿着氨纶短裤玩接触式杂耍，真的什么都有！）。

这个场景是这样的（我稍微编辑了一下）：

小妖精1：离开这里的唯一方法是尝试这些门中的一扇。 小妖精2：其中一扇门通向迷宫中心的城堡，另一扇门通向（砰砰砰砰！）必死之地！ 两个小妖精：呜呜呜呜！ Sarah：哪扇门是哪扇？ 小妖精1：嗯……我们不能告诉你。 Sarah：为什么？ 小妖精2：你只能问我们其中一个。这是规则！我应该警告你，我们其中一个总是说真话，另一个总是说谎。这也是一条规则。（指向另一个小妖精）_他_总是说谎。 小妖精1：我没有！我说的是实话！ 小妖精2：哦，多么大的谎言！（两个小妖精咯咯地笑）

Sarah 遇到了小妖精。

这是一个经典的谜语，也许是被称为 Knights and Knaves 类型的逻辑谜题中最著名的例子。（电影中没有明确说明，但你只能问 一个 小妖精 一个 问题，他们只能用“是”或“否”来回答。从这一个“是/否”中，你必须推断出哪扇门是正确的。你也可以假设两个小妖精都在说实话，直到他们停止解释规则的那一刻。）

人们对这个问题有点困惑——规则很简单，但解决方案似乎有点复杂，特别是如果你以前没有见过它。我想发表这篇文章是因为我认为在这种情况下，采用形式化的方法比用简单的英语解决问题要直接得多。为此，让我们用 Boolean Algebra 来建模这个问题！

如果你做了很多编程，你几乎肯定已经使用过 Boolean Algebra ——它就是你用 true、false、&&、|| 等等所做的一切。更准确地说，Boolean Algebra 是 George Boole 在 1847 年设计的一个 formal system。它有两个值，true 和 false，并使用标准的逻辑连接词，与（通常写成 ∧），或（通常写成 ∨）等等。

让我们尝试用这个 algebra 对问题进行建模。我们有一个输入——我们提出的问题（以及，从技术上讲，我们问的是哪个小妖精，但由于两个小妖精都有可能说谎，所以问一个而不是另一个不会改变任何事情）。我们有一个输出——小妖精的答案。最后，我们有两个未知数——说谎的小妖精，以及通向城堡的门。我们如何用其他三个变量来表达输出？

如果小妖精说的是实话，他会正确回答问题。如果他说谎，他会“翻转”答案。让我们用 A 代表我们从小妖精那里得到的答案，Q 代表我们所问问题的正确答案，G 代表小妖精的“说谎性”（即，如果小妖精是骗子，则为 true，否则为 false）。可能的输入和输出如下所示：

G | Q | A ---|---|--- true | true | false true | false | true false | true | true false | false | false

盯着这张表足够长的时间，你可能会注意到，当且仅当 G 和 Q 不相等时，A 才为 true。那些熟悉 Boolean Algebra 的人已经得出结论，我们可以使用 xor（“ex clusive or”）运算符将 G 和 Q 组合起来获得 A 的值，当且仅当其参数不同时，xor 运算符才为 true：

A=G⊕Q

现在我们有了用 G 和 Q 表示的 A。但是门呢？好吧，我们对可以提出的问题的类型没有任何限制，并且从问题陈述中可以很明显地看出，我们需要选择一个问题，以便小妖精的回答会告诉我们选择哪扇门（我们可以通过问一个显而易见的问题来轻松推断出哪个小妖精是骗子——但这并不能告诉我们任何关于门的信息！）。

（你可能已经注意到，由于我们可以问 任何 问题，我们可以问一些问题，这些问题是其他问题的 boolean 组合——例如，“现在是星期三吗，太阳是否绕地球运行？” 先把这个观察记在心里；我们稍后会回到它！）

要么左边的门是正确的，要么右边的门是正确的，而且我们问题的答案必须以某种方式告诉我们哪个门是正确的。所以我们知道，无论我们最终提出什么问题，它都必须以某种方式取决于门的状态——这意味着这是一个我们还不知道答案的问题。从现在开始，我们将用 QD 代替 Q，以反映这一事实（并且，为了将来参考，我们将说如果左门和右门分别通向城堡，则 DL 和 DR 为 true）。

现在我们有两个未知数——G 代表我们正在交谈的小妖精是否是骗子，QD 告诉我们应该选择哪扇门。让我们再看看那个真值表：

G | QD | A ---|---|--- true | true | false true | false | true false | true | true false | false | false

我们离解决问题更近了吗？实际上并没有，但是看看这张表，现在应该清楚为什么了——我们想倒着走，从 A 开始推导出 QD。但是我们不能这样做，因为我们有两个自由度——我们不知道小妖精是否是骗子，也不知道 QD 的真实答案是什么。我们需要做的——通过选择正确的问题——是将

A=G⊕QD

要么完全消除 G（可能不可能），要么以某种方式将其变成一个常数。

在这一点上，你应该尝试参与神圣的数学传统——乱搞。思考问题陈述；记下你确定知道的所有事情以及你仍然需要弄清楚的事情（如果它有帮助，可以列一个清单！） 你也应该尝试玩一些 algebra 。不要太专注于得出解决方案，只是踢一些表达式，看看会发生什么。花几分钟在这个上面，看看你是否可以猜到我们要去哪里（或者如果你已经知道答案，请继续阅读！）

你可能已经意识到的两个重要的事情：

• 我们确切地知道只有一个小妖精是骗子。不能是两个，也不能是零。
• xor 是可交换的，即 true⊕false=false⊕true=true

总而言之，这意味着，如果我们使用 G1 和 G2 来代表两个小妖精的说谎性，那么 G1⊕G2 总是 true！这是一个非常有用的事实，但要利用它，我们必须找到一种方法将两个 G 都放入我们之前的表达式中。最直接的方法是直接询问另一个小妖精：即“另一个小妖精是骗子吗？” 但是等等——这甚至被允许吗？好吧，是的！问题陈述没有明确提到它，也没有禁止它（顺便说一句，当用口头方式解决问题时，“诀窍”是意识到你需要问这类问题——希望在代数上思考问题时这一点更明显！）

直接询问另一个小妖精只是用 G2 代替 QD，这给了我们 G1⊕G2（请注意，无论我们向哪个小妖精提出这个问题，答案总是肯定的）。但是 QD 必须以某种方式取决于门的状态，所以让我们找到一种方法将 DL 放回组合中。正如我们之前提到的，我们的问题可以是其他问题的 boolean 组合，因此我们可以用 G2 和 DL 代替 QD，用 boolean conjunction 连接在一起（为了保持一致性，让我们坚持使用 xor。） 在执行我们的替换后，我们最终得到：

A=G1⊕(G2⊕DL)

在我们的最后一步中，我们将使用 xor 的结合律。这基本上意味着你可以在 xor 之间移动括号，像这样：

A=G1⊕(G2⊕DL)=(G1⊕G2)⊕DL=true⊕DL

我们成功了！我们可以通过询问第一个小妖精 G2⊕DL 并反转答案来解决这个谜语。这将告诉我们左边的门是否是正确的门（因为当且仅当 x=false 时，true⊕x 才为 true。）

由于小妖精不是 Boolean Algebra 方面的专家，我们可能应该找到一种方法用简单的英语来表达我们的问题。我们可以用蛮力的方式来做到这一点（“以下内容中是否只有一个是真的：另一个小妖精是骗子，左边的门是正确的？”），但你可能已经注意到，如果我们向第二个小妖精询问左边的门，G2⊕DL 将采用 A 的形式。现在我们准备好观看小妖精场景的其余部分了：

Sarah：（对小妖精 1 说）他（指着小妖精 2）会告诉我这扇门通向城堡吗？ 小妖精 1：呃……（与另一个小妖精商议）……是吗？ Sarah：那么另一扇门通向城堡，这扇门通向必死之地！ 两个小妖精：呜呜呜呜！ 小妖精 1：你怎么知道？他可能在说实话！ Sarah：但是这样你就不会说实话了，所以如果你告诉我他会说是的，我知道答案是否定的。 小妖精 1：但是我可能在说实话！ Sarah：那么他就会说谎，所以如果你告诉我他说好的，我知道答案仍然是否定的。 小妖精 1：等一下……（对另一个小妖精说）是这样吗？ 小妖精 2：我不知道，我从来没有理解过！（两个小妖精咯咯地笑）

你可能已经注意到，在这篇文章中，我们几乎只谈论符号和操纵它们的规则。很少讨论这个问题相对于现实世界的更广泛的“性质”，我们最终通过注意到 xor 运算符的几个关键属性（而不是像 Sarah 那样通过假设来讨论）来解锁解决方案。我个人更喜欢符号方法，因为（在我看来！）它使每个步骤都非常小且易于遵循。我也认为，当你用形式术语重述问题时，证明背后的技巧会更明显。

我在做数学时经常有这种经历：细节消失了，我只想着符号本身以及我需要用它们做什么。这种“信任形式主义”的策略可能是一种非常有效的解决问题的技术——事实上，我认为 formal system 是强大而有用的，正是因为你可以在解决复杂问题时将你的推理外包给它们。当我开始将它们视为“推理工具”时，它个人帮助我更好地理解了 formal system 。

一些思考！

如果你喜欢这篇文章，Terry Tao 对蓝眼岛民的逻辑难题有一个类似但更复杂的pair of articles。这是一个很棒的难题，而且非常伤脑筋——即使在你了解解决方案之后，也很难说服自己它实际上是一个解决方案！

附：使用我们刚刚经历的相同的推理路线，你实际上可以推导出这个难题的另一个解决方案。你能弄清楚它是什么吗？

The Nerve Blog Powered by Ghost Subscribe