看离散数学及其应用这本书的时候发现这本书非常非常的良心，每一个小结都有至少45道习题。然后这1.2节讲的逻辑推理，于是47到题中给我来了20来道逻辑推理题，你要说难也不难，但是真的很恶心，尤其是有几十道类似的问题的时候，这一堆玩意下来做了三天，快给我做吐了。其中第42道题是一个比较有难度的题，说的是爱因斯坦的斑马谜题(zebra puzzle)，也是一个比较著名的CSP问题(Constraint Satisfaction Problem，约束满足问题(顺便提一句，CSP问题是NP完全的，目前普遍使用回溯算法和启发式算法解决))，这个问题难度并不比别的问题高，但是比别的所有问题都恶心，因为他包含了至少25个基本命题(elementary/atomic sentences)：五种饮料，五种颜色，五种宠物，五种职业，五种国籍，真值表至少有2^125约4.3e37行‬，问题是这样的：

五位具有不同国籍和不同工作的人居住在一条街上挨着的五个房子里。每所房子刷着不同的颜色。他们养着不同的宠物，喜欢喝不同的饮料。根据以下提示，试确定谁养斑马(zebra)，谁喜欢喝(饮料之一的)矿泉水。英国人住在红色的房子里。西班牙人养了一条狗。日本人是一个油漆工。意大利人喜欢喝茶。挪威人住在左边的第一所房子里。绿房子紧挨着白房子的右边。摄影师养了一只蜗牛。外交官住在黄房子里。中间那个房子里的人喜欢喝牛奶。绿房子的主人喜欢喝咖啡。挪威人的房子紧挨着蓝色房子。小提琴家喜欢喝橘子汁。养狐狸的人所住的房子与医师的房子相邻。养马的人住的房子与外交官的房子相邻。

介绍

首先这题不可能用真值表和布尔代数解决，如果谁有毅力造一个4后面带37个0行数的真值表然后一点点看的话那也用不着学离散数学了，我用的方法是比较常用的方法就是画表+假设+回溯，首先我们画一张包含了已经确定的条件的表：

国籍 房子颜色 宠物 饮料 职业 房子从左到右的序号
英国 红色
西班牙 狗
日本 油漆工
意大利 茶
挪威 1

然后我们列出所有的已知条件:

  1. 挪威人的房子在最左边
  2. 绿房子在白房子的右边，也就是白房子在绿房子的左边
  3. 摄影师的宠物是蜗牛
  4. 外交官住在黄房子里
  5. 中间房子的人喜欢喝牛奶
  6. 绿房子的人喜欢喝咖啡
  7. 挪威人的房子紧挨着蓝色房子
  8. 小提琴家喜欢喝橘子汁
  9. 养狐狸的人和医师是邻居
  10. 养马的人和外交官是邻居

分析已有条件

首先我们要知道，做这类问题应该从和其他命题关系最少并且能够确定的函项入手(也就是找最简单并且可以被确定的那个命题所包含的函项)，在本题中就是命题1中挪威人的房子，根据条件我们知道了挪威人的房子的序号是1并且蓝色房子紧挨着挪威人的房子，因此蓝色房子的序号一定是2，因此我们至少得知了房子的排列顺序是? 蓝色 ? ? ?，同时我们从题目中知道绿房子和白房子相邻，因此挪威人的房子不可能是绿或者白，又因为红色房子已经知道是英国人的了，所以可知挪威人的房子是黄色的，也就是外交官，同样可以得知蓝色房子的人养了马(因为养马的人和外交官是邻居，而外交官(挪威人)唯一的邻居就是房子序号为1的蓝色房子)。

到了这里，所有的线索都陷入瓶颈了，因为从剩余的线索中无法确切分析出任何一个结论，因此我们在接下来需要分情况假设，首先让我们列出现在的表格：

国籍 房子颜色 宠物 饮料 职业 房子从左到右的序号(从0开始)
英国 红色
西班牙 狗
日本 油漆工
意大利 茶
挪威 黄色 外交官 0

分情况讨论

接着由题目和已知结论我们可以发现，剩余的房子颜色有两种可能的排列方式:
* (1) 黄色 蓝色 白色 绿色 红色
* (2) 黄色 蓝色 红色 白色 绿色

之所以这么排是因为我们之前已经从命题2知道了绿房子和白房子必定在一起并且白房子在绿房子的左边，我们一一分析两种情形

房子的排列方式是第(1)种

由题目给出的条件可以得到：

  • 白房间的人喜欢喝牛奶

此时我们不应当忘记表格，从表格中可以得知意大利人喝茶，而3号房子喝牛奶，4号房子喝咖啡，5号房子是个英国人，因此2号房子是意大利人，也就是意大利人喝茶，养马，住蓝房子；而唯一一个剩下的饮料是橘子汁，它对应小提琴家，当前不知道喝什么饮料的还有两个，第一是1号房子的挪威人，第二是5号房子的英国人，因为挪威人是外交官，所以可以得知5号房子的英国人是小提琴家，喜欢的饮料是橘子汁，表格变成了这样：

国籍 房子颜色 宠物 饮料 职业 房子从左到右的序号(从0开始)
英国 红色 橘子汁 小提琴家 5
西班牙 狗
日本 油漆工
意大利 蓝色 马 茶
挪威 黄色 外交官 1

接着看，我们知道摄影师养蜗牛，场上唯二不知道职业的分别是西班牙人和意大利人，问题是这两个已经知道了一个养狗一个养马，出现了悖论，因此说明这种排列组合是错误的

房子的排列方式是第(2)种

由题目给出的条件可以得到:

  • 3号房子(红色)的人喜欢喝牛奶
  • 5号房子(绿色)的人喜欢喝咖啡

而红房间的人是英国人，因此我们可以知道英国人喜欢喝牛奶，此时已知的有1号房子是挪威人，2号房子的人养马，3号房子的人是英国人，因此西班牙人一定在4号或5号(根据国籍和宠物决定)，到这里会发现再一次陷入了僵局，解决办法是继续往下分类讨论

假设西班牙人住在4号

国籍 房子颜色 宠物 饮料 职业 房子从左到右的序号
英国 红色 牛奶
西班牙 白色 狗 4
日本 油漆工
意大利 茶
挪威 黄色 外交官 1

那么可以知道西班牙人住在白色房子里，题目中给出了小提琴家喜欢喝橘子汁，而目前唯一的不知道职业又不知道饮料的就是西班牙人，因此西班牙人是小提琴家，并且喜欢喝橘子汁；因为绿色(5号)喜欢喝咖啡，中间(三号，3号)喜欢喝牛奶，而我们上一步知道了白色(4号，西班牙人)喜欢喝橘子汁，因此喜欢喝茶的意大利人一定在2号，唯一剩下的日本人一定居住在5号，表格变成了：

国籍 房子颜色 宠物 饮料 职业 房子从左到右的序号
英国 红色 牛奶 3
西班牙 白色 狗 橘子汁 小提琴家 4
日本 绿色 咖啡 油漆工 5
意大利 蓝色 马 茶 2
挪威 黄色 外交官 1

因为摄影师养蜗牛，而厂上唯一不知道职业和宠物的就是英国人，因此英国人是摄影师并且养蜗牛；剩下的一个职业就是医师了，因此意大利人是医师，而剩下的饮料就是矿泉水了，它属于外交官(因为只有外交官一栏的饮料是不知道的)；而我们知道养狐狸的人和医师相邻，医师的房子序号是2，相邻有1和3，而3已经推断出是蜗牛了，因此1号房子的挪威人养的是狐狸，顺理成章的，养斑马的就是唯一一个剩下的：住在5号房子的日本人，此题得解：

国籍 房子颜色 宠物 饮料 职业 房子从左到右的序号
英国 红色 蜗牛 牛奶 摄影师 3
西班牙 白色 狗 橘子汁 小提琴家 4
日本 绿色 斑马 咖啡 油漆工 5
意大利 蓝色 马 茶 医师 2
挪威 黄色 狐狸 矿泉水 外交官 1

结论

做这类题的时候如果基本命题数量不多可以直接用真值表推算，但是如果基本命题数量太多的话还是需要列表+分情况讨论+回溯，记得在每一步都要环视所有的已知条件，以防忘掉某一个导致卡在这一步(比如推断西班牙人是小提琴家的那一步我就卡住了，因为忘掉了小提琴家会喝橘子汁这个条件)，每一步就列一个表格，虽然比较麻烦，但是可以提供较为清晰的思路，毕竟人脑很难记住这么多种情况的分布...