1701741345
猪排问题
1701741346
1701741347
可满足性问题可能非常难。刘易斯·卡罗尔设计过一些极其枯燥的逻辑谜题，这些题要求解题者借助十几个（甚至更多）无意义的前提推出一个单独的有效结论。有几道题收在他未完成的教科书《符号逻辑》中，这些问题是对科学推理或数学推理的拙劣模仿，但是却出人意料地困难。一些更难的问题已超出了大多数人的耐心的极限（虽然这些问题已经被计算机解决）。最困难的一个问题是在他的笔记中发现的，直到1977年才发表，这个问题包含50个前提。
1701741348
1701741349
卡罗尔设计过一个被人脑和计算机广泛分析过的问题，即大名鼎鼎的“猪排问题”。这个谜题要求推出“完全结论”，即一个既与所有其他命题相一致又被所有其他命题所要求的假说。
1701741350
1701741351
猪排问题
1701741352
1701741353
（1）一个晚餐吃猪排的逻辑学家很可能丢钱；
1701741354
1701741355
（2）一个食欲旺盛的赌徒很可能丢钱；
1701741356
1701741357
（3）一个已经丢了钱的，并且可能丢更多钱的、郁闷的人，总是在凌晨5点起床；
1701741358
1701741359
（4）一个既非赌徒又不在晚餐时吃猪排的人，一定有旺盛的食欲；（5）一个凌晨4点以前起床的、有活力的人最好去开出租车；
1701741360
1701741361
（6）一个食欲旺盛的、未丢钱的、不在早晨5点起床的人，晚餐总是吃猪排；
1701741362
1701741363
（7）一个有丢钱的危险的逻辑学家，最好去开出租车；
1701741364
1701741365
（8）一个郁闷的、未丢钱的、热心的赌徒，没有丢钱的危险；
1701741366
1701741367
（9）一个不赌钱、食欲不旺盛的人，总是有活力的；
1701741368
1701741369
（10）一个真正热心的、有活力的逻辑学家，没有丢钱的危险；
1701741370
1701741371
（11）一个食欲旺盛的人不需要去开出租车，如果他是真正热心的；
1701741372
1701741373
（12）一个郁闷的、没有丢钱危险的赌徒，在凌晨4点以前不睡觉；
1701741374
1701741375
（13）一个丢了钱、晚餐不吃猪排的人，最好去开出租车，除非他在凌晨5点起床；
1701741376
1701741377
（14）一个在凌晨4点以前睡觉的赌徒不需要去开出租车，除非他食欲旺盛；
1701741378
1701741379
（15）一个郁闷的、没有丢钱危险的并且食欲旺盛的人，是一个赌徒。
1701741380
1701741381
我们习惯于把逻辑看作某种自然产生的东西。我们期望解决一个逻辑问题而无须认真考虑问题的答案是怎么来的。在卡罗尔的问题中，命题的数量太多了，而且非常不自然，无法立刻掌握。所以我们不得不将其诉诸算法，例如卡罗尔介绍的树形图和术语（或者借助于计算机）。
1701741382
1701741383
猪排问题有11个布尔变量（热心的、吃猪排、是赌徒、凌晨5点起床、丢了钱的、食欲旺盛的、很可能丢钱的、有活力的、是逻辑学家、最好去开出租车、凌晨4点以前不睡觉的）。对于其中任意一个变量，都有211=2048种不同的假说。
1701741384
1701741385
猪排问题要求给出一个结论，看起来这个问题更像是科学研究。这似乎与可满足性问题完全不同，可满足性问题是由“是”和“否”来回答的。然而，可满足性问题的这个特征并不妨碍它成为一种通用方法。就像“20个问题”这种游戏所展示的，任何信息都可以通过一系列“是—否”问题表达出来。任意一个逻辑问题（无论它提出的问题是什么）都可以表达成一个或多个“是—否”问题。
1701741386
1701741387
比方说，我们想检验这一结论：一个吃猪排的人是有活力的。解题的第一步是把原来的15个前提转换为可满足性问题的形式。这些前提是相互一致的吗？应当是，否则题就出错了。第二步，我们把待检验的结论作为第16个命题添加进去。现在这个更新之后的命题集合中的各命题依然是相互一致的吗？（这是第二个可满足性问题。）如果是一致的，那么这个新命题至少是被最初的前提允许的。
1701741388
1701741389
但这并不意味着，根据前提就可以有效地推出这个结论。你可以检验一下“月球是由绿奶酪构成的”这个命题，把它作为第16个命题，你会发现，整体也是可满足的——当然是这样。由于它对于逻辑学家、赌徒以及其他猪排问题中的胡言乱语只字未提，所以它不可能导致任何一个矛盾。
1701741390
1701741391
为了确定一个假说是原来的前提所要求的，我们需要引入第三个可满足性问题。把这个假说替换成它的否定形式，即它的负命题：“并非所有吃猪排的人都是有活力的。”把这个负命题作为第16个前提加进去，看看命题集合是否一致。
1701741392
1701741393
如果一个假说和它的负命题加进去之后都会不引起矛盾，那么很明显，这个假说与命题集无关的。“月球是由绿奶酪构成的”和“月球不是由绿奶酪构成的”这两个命题都与猪排问题一致，所以二者都不能有效地推论出来。
[
上一页 ]
[ :1.701741344e+09 ]
[
下一页 ]