文章转自http://blog.csdn.net/lsldd/article/details/16104747#comments
你来到两道门口，一道是天堂之门， 一道是地狱之门 。
门口都有一个守卫，只知道守卫一个只说假话，一个只说真话。
现在你只有一次提问机会，只向一个守卫问一个问题，这个守卫对你的问题，只给出“是”或者”不是“的答案。（对于无法给出是非的问题，守卫会直接把你砍死。。。）
请问怎么问才能准确进入天堂之门？
你来到两道门口，一道是天堂之门， 一道是地狱之门 。
门口都有一个守卫，只知道守卫一个只说假话，一个只说真话。
现在你只有一次提问机会，只向一个守卫问一个问题，这个守卫对你的问题，只给出“是”或者”不是“的答案。（对于无法给出是非的问题，守卫会直接把你砍死。。。）
请问怎么问才能准确进入天堂之门？
我们将守卫守门的所有情况列成如下的一个矩阵：
守卫分两种情况，第一行代表天堂守卫是诚实的情况，第二行分为天堂守卫为说谎话的情况。
而每种情况你都有2个可能，要么问到真话守卫，要么问到假话守卫。因此问题的解空间是一个2*2的矩阵。
这个问题难在，不管你问“你是说真话的吗？”还是问“你守卫的门是天堂的吗？”，都无法得到满意信息。
如下图，如果你问“你守卫的门是天堂的吗？”，所有的情况如下图所示：
红色的勾表示如果你问这个守卫（勾连接的那个画圈的守卫）问题，他会说“是”。”叉“表示说”否“。
看到这个图你就明白为什么问不出答案了。因为无论是上下哪种情况，天堂的守卫既有可能说”是“，也有可能说”不是“。
解法1：通过解空间反求问题x
我们的目的是找出天堂之门。也就是说，需要设计一个问题，将解空间按照天堂和地狱来进行分离。
也就是说，我们需要设计一个问题，将解空间分解为如下情况：
这样解空间按照天堂和地狱分开了。只要回答是”是“，该守卫就是天堂守卫。反之就是地狱守卫。
如何寻找这样的问题呢？
容易知道，为得到天堂地狱相关的信息，我们问的问题一定是描述当前守卫守门状况的一个描述。（例如你问1+1=2吗，真话守卫说是，假话守卫说否，这样只能区分出守卫真假，但是无法区分天堂和地狱）
如果我们把这个状态当做函数的输入x，守卫对该问题的回答的解空间当做y，那么这个函数可以写作：
Y = f(X)
由于y和x是2*2的矩阵。那么可把上式写成：
那么f函数执行的是什么操作呢？
我们知道，x表示的是一个描述在四种守卫情况中的真值表，真值表是客观存在的，所以一定是为真的。真话守卫不会修改这个真值，而谎话守卫一定会给出相反结果。那么，这个f可以表示为：
由于f只做了反转操作，显然f操作是可逆的。
要让天堂守卫都说”是“，地狱守卫都说”否“，就是说y应该是：y1=y3=1, y2=y4=0。
既然我们已经知道我们需要什么样的y了。因此，已知y反求x，如下：
这个x就是我们可以拿出来问守卫的问题。
还记得我们对矩阵的定义吗？
因此，把上面的x代入该矩阵定义，得到如下的守卫状态：
守天堂的是真话守卫； 守地狱的是假话守卫；
守天堂的不是假话守卫；守地狱的不是真话守卫；
这实际上是一个状态的四个等价描述的。因此，这个状态就是满足输出y的问题x。
因此，只要向任意一个守卫问上面的任意一个问题即可。只要回答是”是“，该守卫就是天堂守卫。反之就是地狱守卫。
解法2：构造高阶逻辑表达式
假设说真话的守卫对问题的回答为f=T(x),假话的为f=F(x),那么有：
T(0) = 0, T(1) = 1;
F(0) = 1, F(1) = 0;
注意到：
T(F(0)) = 1; T(F(1))=0;
F(T(0)) = 1; F(T(1))=0;
这说明通过一个问题x经过F和T的两次加工，最后的答案是一样的也即
T(F(x)) = F(T(x)) = !x
因此，我们可以构造如下问题：
”另外那个守卫会告诉我你是天堂守卫吗？“
得到的回答一定和”你是天堂守卫“相反。也就是说，他说”是“，那他就是地狱守卫；他说不是，那他就是天堂守卫。