谜题和悖论之间有着深刻的联系。面对一个谜题，我们可以提出许多假说，其中一个可以避免矛盾，这个假说就是答案。但是在悖论中，所有假说都是不合理的。
逻辑谜题的味道很怪——有点儿像生牡蛎。有些人觉得逻辑谜题是有趣的挑战，有些人则很讨厌它。一个重要的问题是，是否存在解决逻辑谜题的通用方法？是否存在所有人都可以掌握的固定的程序、窍门或方法，可以解决所有的逻辑谜题？如果这种东西存在，那么它在科学以及其他领域都是无价之宝。
在实际操作中，逻辑表现为两种方法的混合：其一是按部就班的演绎推理，其二是穷尽所有可能性的搜索。第一种方法可以通过一组经典悖论展示。
忒修斯之船
根据普卢塔克的记载，特修斯杀死人身牛头怪物之后返回雅典，他乘坐的船被雅典人一直保存到法莱雷奥斯的德米特里（Dmetrius Phaleron）的时代。之所以可以保存这么久，是因为在船上的老木板腐朽以后，人们用结实的新木板替换了以前的木板。在哲学家那里，这艘船成为争论点，他们用这个活生生的例子探讨“事物的发展”这一逻辑问题。一方认为，这艘船还是以前的那艘船，另一方则主张它已经不是了。
所有人都同意，在一艘船上换掉一块木板并不会改变这艘船的“身份”，在撤换一块木板之后船还是原来的船。在修理过的船上再换掉一块木板，情况还是一样。可是，也许到某个时刻，整条船上连一块最初的木板也不剩了，此时，如果雅典人还把这艘船称为特修斯之船，那就是自欺欺人了。假如这艘船当初没有被保留下来，后来的雅典人只是用这些后来的木板直接造了一艘船，那么所有人都会把这艘船称为“特修斯之船的复制品”，大家不会认为这艘船还可以被称为别的东西。
一些较小的、同一类型的悖论在古希腊很流行。芝诺说，一粒谷子掉在地上没有声音，但是，当一大袋谷子掉在地上时，为什么却发出了声音？袋子里除了一粒一粒的谷子之外什么都没有。“谷堆悖论”[1]与这个问题属于同类问题：无论什么时候，从一堆沙子里拿走一粒沙子，剩下的还是一堆沙子。想象有一堆沙子，从沙堆里取走一粒沙子。根据你过去的经验，是否存在这样一种可能性：本来是一堆沙子，取走一粒沙子以后，剩下的就不是一堆沙子了？当然不可能。于是，我们从一堆沙子开始，一粒一粒来取，最终，这堆沙子只剩下孤零零的一粒了，但它必须依然是一堆！然后把这仅存的一粒也取走，什么也不剩了，但是，在这种情况下，它也必须是一堆！
当然，为了逃脱困境，我们可以规定“堆”的最小标准。“一堆至少要包含1 000粒，于是规则变成这样：‘在粒数不少于1 001粒的一堆中取走一粒，剩下的依然是一堆。’”然而，这个规定念起来都非常别扭。它不是已经误解最初的问题了吗？“堆”这类词的含义原本就被视为是模糊的。
这个悖论的一个现代版本是王浩悖论（以王浩的名字命名）。王浩声称，如果一个数x是小的，那么x+1也是小的。所有人都同意0这个数是小的吧？是的。于是，1（“0+1”）是小的，2（“1+1”）是小的，3（“2+1”）也是小的……所有数都是小的。这是荒唐的。
连锁推理
一个连锁推理是由一连串推理构成的一个链条。在这种推理形式中，每一个命题的谓项与下一个命题的主项相同。换一个说法，如同下例：
所有大乌鸦都是乌鸦；
所有乌鸦都是鸟；
所有鸟都是动物；
所有动物都需要氧气。
在这个连锁推理中，各个前提联系在一起导致了一个明显的结论（“所有大乌鸦都需要氧气”）。在许多逻辑谜题中，关键就在于发现连锁推理。上一章（插曲）提到的“公司的流言加工厂”的例子，就是一个明显的连锁推理。
连锁推理（sorites）这个词源于希腊语中与“堆”对应的单词。这是因为，在谷堆悖论中正是（错误地）应用了这种推理方法：
如果x构成一堆，那么x减去1粒构成一堆；
如果x减去1粒构成一堆，那么x减去2粒构成一堆；
如果x减去2粒构成一堆，那么x减去3粒构成一堆；
如果x减去3粒构成一堆，那么x减去4粒构成一堆；
……
如果x减去12 882 902粒构成一堆，那么x减去12 882 903粒构成一堆：
这样下去，这个推理可以包含上百万个步骤。
连锁悖论可能是最简单的演绎悖论了。这里没有任何难以理解的东西。一个前提轻微地不精确，在这个前提不断地重复应用之后，这种不精确性累积起来——所有的连锁悖论都是根据这种方法生成的。这种悖论的迷人之处在于，它利用（滥用）了一种极为常见而重要的推理形式。我们的大多数知识和观念都是通过连锁推理达到的。
有一天你看见一只乌鸦，以前你从未见过这只乌鸦，任何鸟类学家也没见过这只乌鸦。即便如此，你还是知道许多关于这只乌鸦的事。你知道（或者说有强烈的理由相信），它是恒温动物，它的羽毛和皮肤下面有骨头，它是从蛋里孵出来的，为了生存它需要水、氧气和食物，等等。这些知识既非来自直接经验，也不是别人明确地告诉你的。你曾经把某只乌鸦放进充满纯氮的屋子里吗（更别说这只特定的乌鸦了）？你曾经在某本书上见过“所有乌鸦都有骨头”这样直截了当的陈述吗？你通过建构必需的连锁推理，才能了解关于这只乌鸦的这些事实。
科学建立于连锁推理之上。根据这种推理形式，任何人都可以从几个既得的概括陈述出发，推出很多信息。信赖连锁推理可以使实验过程更经济。很可能从没有人做过实验以检验乌鸦是否需要氧气。实验已经表明各种不同种类的动物都需要氧气，如果存在什么理由令我们相信乌鸦也许是厌氧型生物，那么这种可能性应当已经有人检验过了。就像上面介绍的那样，我们依赖于连锁推理。
科学家寻求“所有X都是Y”这样的概括陈述，因为这类陈述使他们可以迅速地推理。“控制实验”的概念已预先假定，关于这个世界的重要事实符合这类陈述（在控制实验中，原因与结果的关系是独立可辨的）。然而，这并不意味着，所有真理都可以如此简单地表达。每当我们发现一部分真理时，这些真理总是反映出我们已掌握的、关于真相的片段可能与真相的整体并不相符。
复杂性
上一章介绍了“UND”谜题，这道题无法用“合乎逻辑”的方法解决。福尔摩斯对这道题的抱怨显示了一个相反的问题类型，与那些可以用逻辑程序处理的问题相对。连锁推理式的按部就班的程序，在这里无法应用。
“UND”谜题涉及一个被称为“复杂性理论”的数理逻辑分支。复杂性理论在客观、抽象的程度上研究“一个问题会困难到什么程度”。计算机程序员根据经验发现，用计算机处理某些类型的问题要比处理其他类型的问题困难得多，这一发现催生了复杂性理论。
如果复杂性理论只应用于计算机，那它的用处就小多了。实际上，这个理论同样可以应用于人类解决问题的过程。一个人解决问题必须依赖方法，方法（而非硬件）正是复杂性理论关注的焦点。
寻找一个客观标准来衡量一个问题的困难程度，达到这个目标看起来也许是徒劳的。大多数在真实世界中出现的问题都是这样：一些人觉得容易，另一些人觉得困难。许多问题的解决依赖于在问题和其他的特定事实之间建立的各种各样的思想联系。你或者能建立起联系，或者不能建立起联系。
某些谜题需要建立特定的思想联系（例如华生提出的分割土地问题），从某种角度说，这类问题是最困难的一类逻辑谜题，因为如何去解一点儿道理也讲不出来。换一个角度来说，这类问题又是最容易的——一旦联系建立好就一点儿难度也没有了。
复杂性理论最关心这样一类问题：即使存在程序化的解法，问题也是难解的。有些问题在本质上是困难的，不仅人类无法解决，科学幻想中遥远的未来计算机也解决不了，但这些问题是可解的，它们不是悖论，也不是没有解的骗人的问题。
复杂性理论的一个核心概念是“算法”。算法是处理某问题的一个确定的、机械的程序。它是一套完备的指令，在执行过程中，洞察力、直觉和想象力都是不需要的。所有计算机程序都是算法。做蔬菜汤的菜谱、装配自行车的操作指南、许多简单游戏的规则等，这些都是算法的例子。在小学里教的算术规则也是算法。我们知道，当我们把两个数相加时，无论数有多大，应用这些规则总会得出正确的答案。如果我们的答案错了，原因一定是误用了规则。没有人会怀疑算法本身。
算法必须是确切的。“如果你在树林里迷路了，保持冷静，调动常识，走一步看一步。”这是建议而非算法。童子军的条例则不同：如果你在树林里迷路了，一直往低处走，直到溪流旁，然后顺流而下，最后你会到达一个城镇。这则是一个算法。
给出一个有效的算法是很难的。未预料到的情况将会发生，童子军的算法可能失效，这种情形不难想象。你有可能身处于沙漠盆地，一直往低处走会到达一个干涸的湖底，却找不到溪流。在地球上的某些偏远地区，有的溪流通向一个内陆湖或者海洋，附近历来没有人类的住所。更糟的情况是，如果你发现自己处于一个非常平坦的平原上，不存在明显的“低处”，此时，算法对你一点儿用也没有。一个理想的算法应当在任何环境下都有效。
我们并非总是依赖算法。有些厨师按菜谱炒菜，还有些厨师愿意自由地即兴操作，以至于他们声称无法描述一道菜是怎么炒的。两种方法无所谓谁对谁错，但是只有算法化的方法值得我们分析。
说假话的和说真话的
逻辑谜题是我们用以理解世界的演绎推理的缩影。我们来看一下，如何用程序化的方法解决一个逻辑问题。逻辑谜题中最古老的类型之一建立于如下背景：在一个遥远的海岛上有一些居民，其中有些人总说真话，还有些人总说假话。他们分别属于两个部落：说真话者的部落，其成员总说真话；说谎者的部落，其成员总说谎话。必须强调的是，说谎者并不狡诈，他们不会采用时而说真话的办法来掩盖一个谎言，他们说出的每一句话都与真话完全相反。两个部落的服饰是一样的，对于外地人，也没有其他线索能够区分某个人属于哪个部落。也许最常被重复的“说真话—说假话”的问题是纳尔逊·古德曼（此人因提出绿蓝—蓝绿问题而著名）设计的一个问题。这个问题于1931年发表于《波士顿邮报》的谜题专栏，但是没有指明其发明者。我们把这个问题稍加变动，表述如下：
在一个“说真话–说假话”的海岛上，你遇到三个人，分别是艾丽斯、本和查理。
你问艾丽斯，她是说谎话的还是说真话的。她用方言作答，你没听懂。
然后你问本，艾丽斯说的是什么。本会说英语，他说：“艾丽斯称自己在说谎。”你又问本关于查理的情况，本回答道：“查理也是说假话的。”
最后，查理补充说：“艾丽斯是说真话的。”
你能推出这三个人各自属于哪个部落吗？
谁在说谎？
在演绎推理中，基本原则与主观性的因素无关；在“说真话—说假话”的问题中，也是如此。假如这个问题这么开头：我们的主人公从飞机上跳伞，落到一个海岛上——这不会产生任何影响。然后给这三个人换上不同的名字，也不会有什么不同，只不过答案中出现的名字变了。这个问题的最关键之处在于发现了一种逻辑联系，这是唯一重要的。
我们只关心一件事：确定这三个人所属的部落。在解决算术问题时，我们经常利用“x=12+5y”之类的公式。其中x和y是变量，表示未知的量，在一个可能的变化范围内取值。解决这类问题的关键，在于确定x和y必须取什么特定的值。逻辑问题也可以用同样的方法处理。在这个逻辑谜题中，有三个未知量：艾丽斯是否说真话，本是否说真话以及查理是否说真话。
当然你也可以说，未知量是艾丽斯、本、和查理是否说谎话。这不会带来什么差别。不过我们对这个思路不加评判，我们仅仅以艾丽斯、本和查理是否说真话为未知量。这样，我们就得到了三个简单的命题，其真假未定：
艾丽斯是说真话的。
本是说真话的。
查理是说真话的。
以上三个命题是对整个情景最基本的描述，它们构成了这个问题的逻辑结构的原子，不存在比它们更基本的命题。这三个命题不是我们已经确知的事实，它们只是我们构造出来的或真或假的命题，因此，它们的地位非常类似于代数中的变量。当然，这些语句的“值”可以是“真”，也可以是“假”。用逻辑学术语说，这些命题是“布尔变量”，这个术语得名于英国逻辑学家乔治·布尔（George Boole，1815~1864）。
在这个逻辑问题中，我们首先问了艾丽斯一个问题。但是，艾丽斯的回答我们听不懂，我们从中推不出任何有效信息。
第一个有效信息来自本。本说艾丽斯称自己是说谎的。你很可能已经想到了，我们不能按照该句的表面意思接受这个命题。本在转述艾丽斯的话时可能在说谎，艾丽斯本人在介绍自己的情况时也可能在说谎。只有在确定了三个人分别属于哪个部落之后，也就是说，只有在确定了谁说假话、谁说真话以后，本的话的真正意思才可以确定。
我们分析一下。艾丽斯和本不可能都说真话。如果他们都说真话，那么艾丽斯会诚实地说她是说真话的，而本也会诚实地把艾丽斯的话翻译给我们。由于本说艾丽斯称自己是说谎的，因此我们得出结论，这两个人并非都说真话。
艾丽斯和本有可能都说假话吗？有可能。当我们问艾丽斯她是否说谎时，她会回答说她不说谎。本也是嘴里没有一句真话的撒谎精，他会对艾丽斯的话加以否定，这样就形成了双重否定。本会说艾丽斯称自己是说谎的。我们听到他就是这么说的。
实际上，没有人会说“我是说谎的”。说真话的人不会这样说——因为这是谎话；说谎话的人也不会这样说——因为这是真话。如果直截了当地问一个人是否说谎，每个人都会说自己是说真话的（在现实生活中也是如此）。
本说艾丽斯称自己是说谎的，这句话彻底暴露了他自己。无论艾丽斯实际上属于哪个部落，她一定会说自己是说真话的。本的话与此相反，所以本是说谎话的。
（如果艾丽斯根本没听懂我们的问题，又会怎么样呢？她很可能会说“我听不懂英语”，或者相反，“我能听懂英语”——如果她是说谎话的。本会向我们报告其中的一个反应，如果本是说谎的，他会给我们一个错误的答案。由于说谎者部落如此缺乏想象力，从本的实际回答我们得知，艾丽斯一定已经听懂了问题，并且做出了一个关于她的部落归属的回答。）
由于本是说谎的，他的第二句话 （“查理是说谎的”）一定也是假的。因此，查理一定是说真话的。
下面只剩查理的话了。查理说艾丽斯是说真话的，我们已经知道查理是说真话的，所以这一定是实际情况。答案是，艾丽斯说真话，本说谎话，查理说真话。
在以上解题过程中是否存在什么方法？是的，的确有一些方法。没有人会说自己是说谎的，意识到这一点是有用的。这就揭示了本是说谎的，而后问题迎刃而解。
但是这个方法（假定我们称之为“方法”）不能应用于全部的、任意的“说真话—说假话”问题。例如，雷蒙德·斯穆里安提出的一个简单而新颖的问题：有一个部落归属不明的人说：“或者我是说谎话的，或者2+2=5。”那么，他属于哪个部落？
在这个例子中，当事人没有说自己是说谎话的。他把两个命题用“或者”联系起来，这意味着，如果说话者是说真话的，那么这两个命题中至少有一个是真的。
关于说话者我们可以提出两种可能的假设：他是说真话的，以及他是说谎话的。如果说话者是说真话的，那么他所说的就是真的。因此，“或者说话者是说谎话的，或者2+2=5”这个命题就是真的。
但这是不可能的。在“或者……或者……”的复合命题中，整体为真，则两个子命题中至少有一个为真。“2+2=5”不可能为真，所以“我是说谎话的”这个子命题必须为真，而这与假定（说话者是说真话的）矛盾。
于是，我们尝试另一个假设。假定说话者是说谎话的。于是，“或者说话者是说谎话的，或者2+2=5”这个命题是假的，其中的两个子命题必须都是假的。如果其中有一个子命题是真的，那么由“或者……或者……”构成的整个复合命题就是真的。因此，判定“或者A或者B”为假等于判定“A和B都是假的”。如果说话者是说谎话的，那么“我是说谎话的”和“2+2=5”这两个命题必须都是假的。可是我们又遇到了一个矛盾。如果说话者是说真话的，那么他必须是说谎话的；如果说话者是说谎话的，那么他又必须是说真话的。
事实上，斯穆里安提出的这个谜题是说谎者悖论的一个巧妙的变种。这个谜题的“答案”是：答案不存在。（或者用斯穆里安的话说，唯一能够得出的结论是：这道题的出题者不是说真话的。）
有一个方法可以应用于任何“说真话—说假话”问题，即使无解的问题（就像斯穆里安提出的问题那样）也不例外。对于任意一个问题中提到的海岛居民，无非有两种可能：他属于说真话部落或者属于说谎话部落。我们把关于每一个海岛居民的部落归属的一个猜测称为一个“完全假说”（例如，“艾丽斯说真话，本说谎话，查理说真话”是一个完全假说）。对于任意一个问题，关于海岛居民的完全假说的数量是固定的（在古德曼的问题中，其数量是2×2×2=8）。我们需要做的全部工作就是，列出所有这些假说，看看哪个假说与题中的命题相符。
在验证各个完全假说的过程中，我们的目标是找矛盾，换句话说，我们在使用归谬法。例如，在古德曼的问题中，有一个完全假说是三个人都说真话，这个完全假说导致一个结论：本会说出他不应当说出的话。这是一个矛盾，于是我们可以排除这个完全假说。把全部8个完全假说检验一遍，我们发现只有一种情况不导致矛盾：艾丽斯、本和查理分别说真话、谎话、真话。通过排除法，此题得到解决。
在《四签名》（The Sign of Four）中，福尔摩斯说道：“我跟你说过多少遍了，在我们排除了所有不可能的情况以后，剩下的情况——无论多么不可思议——一定是真的。”应用排除法可以解决许多类型的问题，但它并非总是切实可行的。
麻烦在于，排除的过程是缓慢的，这是因为需要检验的完全假说数量经常是无比巨大的。
一个布尔变量只能是真的或假的。对于一个未知量来说，有两种可能性。每一个未知量使得完全假说的总量倍增。在涉及三个未知的布尔变量的问题中，可能的完全假说的数量是23=8。一般地，当存在n个或真或假的未知量时，有2n个可能的完全假说。如果一个“说真话—说假话”问题牵涉24个海岛居民，完全假说个数将有上百万。
可满足性
现在我们已经触及演绎推理的核心。逻辑问题的花哨背景（关于此问题看起来在讨论什么东西）与问题的解决无关。撇开这些花哨的虚饰之后，还剩下什么？
剩下的是“可满足性”。对于复杂性理论来说，可满足性是最基本的、不可还原的逻辑内核。每一个演绎推理问题的内部，都以可满足性为骨骼。
459个苹果加上273个苹果是多少、459个橘子加上273个橘子是多少、459根棒球棍加上273根棒球棍是多少，在我们看来，所有这些问题在本质上都是一个问题。算术的基础就在于意识到所有这类问题就其基础而言是一样的。
复杂性理论得以建立的基础，在于意识到许多更复杂的问题实际上是同一个问题。算术发源于古代人计数的问题。人们意识到，对小麦的蒲式耳数[2]进行加减，与对骡子和金币的数量进行加减没什么两样。在20世纪60年代和70年代，计算机程序员面临一些问题，这些问题导致了复杂性理论的诞生。这些程序员发现，许多看起来不同的问题是相互等价的。
习惯上，可满足性可以表达为一个用“是—否”来回答的问题：给定一组前提，它们是否相互一致？或者说：它们是否描述了一个可能的世界？或者说：它们是否包含不可解的悖论？
一个完整的可满足性问题包括一组布尔变量（即最初真假未定的基本命题）和一组关于这些布尔变量的逻辑命题，这些命题可以包含“或者”“并且”“并非”“如果……那么……”之类的标准的逻辑连接词。
通常，每个命题描述一个单独的、不明确的观察结果。以古德曼的“说真话—说假话”问题为例，以三个人的名字为符号表示三个布尔变量。这个问题实际上就是：
布尔变量：
艾丽斯（表示艾丽斯是说真话的）
本（表示本是说真话的）
查理（表示查理是说真话的）
命题：
1.如果（艾丽斯并且本）那么并非艾丽斯
2.如果本那么并非查理
3.如果查理那么艾丽斯
第一个命题是最难处理的，它对应着本断言艾丽斯称自己是说谎的。如果本和艾丽斯都是说真话的，那么这个命题就是可信的，而在此情况下，艾丽斯就不是说真话的。[3]
猪排问题
可满足性问题可能非常难。刘易斯·卡罗尔设计过一些极其枯燥的逻辑谜题，这些题要求解题者借助十几个（甚至更多）无意义的前提推出一个单独的有效结论。有几道题收在他未完成的教科书《符号逻辑》中，这些问题是对科学推理或数学推理的拙劣模仿，但是却出人意料地困难。一些更难的问题已超出了大多数人的耐心的极限（虽然这些问题已经被计算机解决）。最困难的一个问题是在他的笔记中发现的，直到1977年才发表，这个问题包含50个前提。
卡罗尔设计过一个被人脑和计算机广泛分析过的问题，即大名鼎鼎的“猪排问题”。这个谜题要求推出“完全结论”，即一个既与所有其他命题相一致又被所有其他命题所要求的假说。
猪排问题
（1）一个晚餐吃猪排的逻辑学家很可能丢钱；
（2）一个食欲旺盛的赌徒很可能丢钱；
（3）一个已经丢了钱的，并且可能丢更多钱的、郁闷的人，总是在凌晨5点起床；
（4）一个既非赌徒又不在晚餐时吃猪排的人，一定有旺盛的食欲；（5）一个凌晨4点以前起床的、有活力的人最好去开出租车；
（6）一个食欲旺盛的、未丢钱的、不在早晨5点起床的人，晚餐总是吃猪排；
（7）一个有丢钱的危险的逻辑学家，最好去开出租车；
（8）一个郁闷的、未丢钱的、热心的赌徒，没有丢钱的危险；
（9）一个不赌钱、食欲不旺盛的人，总是有活力的；
（10）一个真正热心的、有活力的逻辑学家，没有丢钱的危险；
（11）一个食欲旺盛的人不需要去开出租车，如果他是真正热心的；
（12）一个郁闷的、没有丢钱危险的赌徒，在凌晨4点以前不睡觉；
（13）一个丢了钱、晚餐不吃猪排的人，最好去开出租车，除非他在凌晨5点起床；
（14）一个在凌晨4点以前睡觉的赌徒不需要去开出租车，除非他食欲旺盛；
（15）一个郁闷的、没有丢钱危险的并且食欲旺盛的人，是一个赌徒。
我们习惯于把逻辑看作某种自然产生的东西。我们期望解决一个逻辑问题而无须认真考虑问题的答案是怎么来的。在卡罗尔的问题中，命题的数量太多了，而且非常不自然，无法立刻掌握。所以我们不得不将其诉诸算法，例如卡罗尔介绍的树形图和术语（或者借助于计算机）。
猪排问题有11个布尔变量（热心的、吃猪排、是赌徒、凌晨5点起床、丢了钱的、食欲旺盛的、很可能丢钱的、有活力的、是逻辑学家、最好去开出租车、凌晨4点以前不睡觉的）。对于其中任意一个变量，都有211=2048种不同的假说。
猪排问题要求给出一个结论，看起来这个问题更像是科学研究。这似乎与可满足性问题完全不同，可满足性问题是由“是”和“否”来回答的。然而，可满足性问题的这个特征并不妨碍它成为一种通用方法。就像“20个问题”这种游戏所展示的，任何信息都可以通过一系列“是—否”问题表达出来。任意一个逻辑问题（无论它提出的问题是什么）都可以表达成一个或多个“是—否”问题。
比方说，我们想检验这一结论：一个吃猪排的人是有活力的。解题的第一步是把原来的15个前提转换为可满足性问题的形式。这些前提是相互一致的吗？应当是，否则题就出错了。第二步，我们把待检验的结论作为第16个命题添加进去。现在这个更新之后的命题集合中的各命题依然是相互一致的吗？（这是第二个可满足性问题。）如果是一致的，那么这个新命题至少是被最初的前提允许的。
但这并不意味着，根据前提就可以有效地推出这个结论。你可以检验一下“月球是由绿奶酪构成的”这个命题，把它作为第16个命题，你会发现，整体也是可满足的——当然是这样。由于它对于逻辑学家、赌徒以及其他猪排问题中的胡言乱语只字未提，所以它不可能导致任何一个矛盾。
为了确定一个假说是原来的前提所要求的，我们需要引入第三个可满足性问题。把这个假说替换成它的否定形式，即它的负命题：“并非所有吃猪排的人都是有活力的。”把这个负命题作为第16个前提加进去，看看命题集合是否一致。
如果一个假说和它的负命题加进去之后都会不引起矛盾，那么很明显，这个假说与命题集无关的。“月球是由绿奶酪构成的”和“月球不是由绿奶酪构成的”这两个命题都与猪排问题一致，所以二者都不能有效地推论出来。
如果一个假说与前提一致，但是它的负命题与前提不一致，那么这个假说就是从前提出发可以推出的正确结论。（如果一个假说与前提不一致，但是它的负命题与前提一致，那么这个负命题就是可以有效推出的。）[4]
可满足性问题，就像所有的一般性问题一样，有时很简单。即使布尔变量和语句的数量极其巨大，问题也可能是简单的。因为我们并不总是需要检验所有的可能性，有时甚至不需要检验大多数的可能性。许多命题经常可以通过连锁推理连接起来。如果如此，那么这般，并且如果这般，那么如此……这种推理在梳理数量巨大的命题时极具威力。
连锁推理中的每一个连接都可以表达为“如果……那么……的形式，其中包含两个未知的布尔值。如果一个可满足性问题的每一个命题都恰好包含两个布尔变量，此时问题是简单的。解决这类问题有高效率的方法，比检验每一个可能的假说以发现符合要求者要快得多。
并不是所有的逻辑问题都如此简单。当命题包含3个或更多未知的布尔值时，不存在明显比排除法迅捷的通用解法。卡罗尔的猪排问题显然很困难，因为该问题的前提涉及三到四个布尔变量（逻辑学家、吃猪排的人、丢钱的人等）。
电梯问题
一旦命题涉及三个未知量，问题难度便会上升——这种情况在“电梯问题”中表现得很明显。
假设电梯中有6个人，则或者其中至少有三个人互相认识，或者至少有三个人互相都不认识。你能证明这总是正确的吗？
这是正确的，但是难以用“逻辑方法”证明。关于“认识”和“不认识”的常识推理没有任何用处。我们不能从“B认识C”推出“A认识B”，这道题没说两个人之间是否认识，它说的是三个人之间的关系。
此类电梯问题有很多版本。例如，在一次聚会上，有6个客人被错误地安排在一张桌上，其中有些人因为宿怨而互相不说话。已知任何三个客人都不构成两两互相说话的关系，证明存在三个客人，这三个人中谁与谁都不说话。另一个比较淫秽的版本这样说：在大学宿舍里任选6名住户，则或者至少有三个人，其中任两个人都在一起睡过，或者至少有三个人，其中任两个人都没在一起睡过。
电梯问题展示了一个被称为“图论”的数学分支。图论（经常是隐蔽地）出现于许多问题中，娱乐性的问题和实际问题都有。最著名的问题之一就是“气、水、电”问题，此题因亨利·欧内斯特·杜登尼的介绍而普及，杜登尼在19世纪与20世纪之交为报纸和杂志写谜题和谜语。这个问题的最初版本的答案是，答案不存在。把三个点和另外三个点连接起来，任意两条线都不相交——这是不可能的。在一个此类的谜题正风靡时，没有人太在意一个心地单纯的读者是否会在一个无解的问题上耗费几个小时甚至几天时间。当然，在上一章中华生和福尔摩斯给出的巧妙的解答不在此列！
图论研究的不是表示股票市场的平均值或者年降雨量之类的图。图论所研究的图是由点构成的网络，点之间还有线相连，就像我们在机场见到的航班线路图。线是直是弯无关紧要，点和点的相对位置也不重要。整个网络结构中唯一重要的拓扑性质是——哪些点之间有线相连。所有这些点和线都非常正确，但是它们并没有说明为什么这种性质是重要或有用的。从更广的意义上说，图论是关于元素之间的关系或联系的研究。
电梯问题很容易转换成图。把6个人表示为点（如图）。在任意两点之间，我们可以画一条线表示二者之间的关系。用黑线表示两个人互相认识，用灰线表示两个人互相不认识。三个人互相都认识表现为一个黑色三角形；三个人互相都不认识表现为一个灰色三角形；是否有可能在所有点之间画线以保证黑色三角形和灰色三角形都不出现？
证明的过程很容易理解。从A开始。我们从A出发画出5条线，分别代表这个人与电梯里的另外5个人认识或不认识。无论如何，其中至少有3条线同色。这是因为，一共有5条线和2种颜色，最均匀的分配方案是一种颜色3条而另一种颜色2条，否则将有4条（甚至5条）线同色。
我们不知道，A是至少认识三个人（黑线），还是至少不认识三个人（灰线）。讨论第一种可能性。假定三条黑线把A与C、D、E连接起来，那么，在C、D、E之间，线的颜色如何呢？
如果C、D、E之间存在一条黑线，则产生一个全黑的三角形，也就是说，有三个人互相都认识。为了避免全黑的三角形出现，唯一的办法是令C、D、E之间的线都是灰色的。但是这就产生了一个全灰的三角形，也就是说，有三个人互相都不认识。无论哪种情况，一定会出现三个互相都认识的人或者三个互相都不认识的人。
如果A不认识三个（或更多）人，推理过程类似，结论一样，必然存在一个全黑的三角形或全灰的三角形。
这不是一个逻辑问题等价于一个几何问题的唯一的例子。复杂性理论发现，许多不同类型的问题在解决程序上是相同的。
科学与谜题
一条谜语、一段密码、一个拼板谜题——许多诸如此类的问题反映了科学方法的特点。通常，证实更像是解一道逻辑谜题，而非前几章讨论的归纳模式。一个简单的概括陈述可以被任何相关的观察结果证实或反驳，但是大多数科学理论则复杂得多，必须根据大量的观察结果进行评价。我们甚至不能说某一个特定的观察结果能单独地提供证实或反驳。
请考虑“地球是圆的”这个假说。对这个假说的证实不在于汇集一大堆关于“圆的地球”的观察结果（从宇航员的视角？），而且没有反例。实际上，人们接受“地球是圆的”这个假说，是因为它联系并解释了许多先前看来无意义的经验事实。对于古代人来说，这些都是非常琐碎而且没有关联的事实：在极北之地，午夜可以见到太阳；月食发生时可以见到圆形阴影；船只离港远去时看起来就像沉于波涛之下。现在所有这些现象，都被视为“地球是圆的”这一假说的逻辑推论。这一假说解释了如此众多各不相关的观察结果，正是因为这样，它才如此令人信服。假如事实上地球不是圆的，那么只有不可思议的巧合才能使所有这些观察结果如此协调地与这些假说一致。
这是一个更加精致的证实类型，它混合了演绎和归纳。一个能推出逻辑结论的假说，首先必须解释以往的观察结果，然后必须做出新的预言。预言如果是真的，则证实假说。归纳和演绎的相互影响是某些悖论的根源，这些悖论甚至比我们讨论过的悖论还要奇妙。
[1] 原文为“paradox of the Heap”，直译应为“堆的悖论”，但是中国学者习惯称之为“谷堆悖论”，所以此处译为“谷堆”，尽管下面说的是“沙堆”而非“谷堆”。——译者注
[2] 蒲式耳（Bushel），谷物计量单位。——译者注
[3] 原著此处有瑕疵。在把原题中的语句翻译为标准的逻辑命题时，作者犯了错误。正确的翻译应当是：1. 本当且仅当（艾丽斯当且仅当并非艾丽斯）；2. 本当且仅当并非查理；3. 查理当且仅当艾丽斯。有兴趣的读者可耐心推敲，亦可参考斯穆里安的奇书《这本书叫什么？》，此书已有汉译本。原著的这个例子意在展示问题的表达形式的转换，所以技术性的错误并不造成关键性影响。——译者注
[4] 也许有些读者想知道猪排问题的答案。答案是：“一个热心的逻辑学家总是凌晨5点起床而且凌晨4点以前不睡觉。”