가장 어려운 논리 퍼즐

가장 어려운 논리 퍼즐은 미국의 철학자이자 논리학자인 조지 불로스가 이탈리아의 한 신문에 실었던 다음의 논리 퍼즐을 가리킨다.

세 신 A, B, C의 이름은 '참', '거짓', '랜덤' 인데 무엇이 누구의 이름인지는 모른다. '참'은 언제나 참말만을 하고 '거짓'은 언제나 거짓말을 한다. '랜덤'은 완전히 무작위로 참말이나 거짓말을 한다. 목표는 단 3번의 참/거짓 질문을 하여 A, B, C의 이름을 알아내는 것이다. 각각의 질문은 한 번에 한 신에게만 해야 한다. 신들은 우리의 언어를 알아듣지만 대답은 '예' 혹은 '아니오'의 뜻을 지닌 그들의 언어 'da'와 'ja'로 주어지는데 어떤 단어가 '예'이고 어떤 단어가 '아니오'인지는 모른다.

불로스의 보충 설명은 다음과 같다.

• 한 신에게 두 번 이상 질문할 수 있다(그렇게 되면 질문을 받지 못하는 신도 생긴다).
• 첫 번째 질문의 답변에 따라 두 번째 질문의 내용과 대상을 지정할 수 있다. (세 번째 질문도 마찬가지)
• '랜덤'이 참말을 할지 거짓말을 할지는 그의 머릿속에서 던진 동전의 앞뒷면에 따라 결정되는 것으로 생각할 수 있다. 앞면이라면, 참말을 한다. 뒷면이라면 거짓말을 할 것이다.
• '랜덤'은 참/거짓 질문을 들으면 'da'나 'ja' 로 대답할 것이다.

역사

불로스에 따르면 이 퍼즐의 원작자는 레이먼드 스멀리언 Raymond Smullyan이고 'da'와 'ja'의 뜻을 모른다는 부분은 컴퓨터 과학자 존 매카시가 추가했다고 한다. 비슷한 퍼즐을 스멀리언의 책 이곳저곳에서 찾을 수 있다. 예를 들면 '이 책의 제목은 무엇인가?'에서 스멀리언은 가상의 섬 하나를 이야기하는데 그 섬 인구의 절반은 항상 거짓말을 하는 좀비이고 나머지 반은 항상 참말을 하는 인간이다. 문제는, 그 섬 주민들은 영어를 알아듣지만, 그들 고유의 언어 이외의 말을 하면 안 된다는 터부가 있다는 것이다.따라서 그들은 참/거짓 질문에 'Bal'과 'Da'라고 대답하는데 어느 것이 '예'이고 어느 것이 '아니오'인지는 모른다. The Riddle of Scheherazade에 다른 관련된 퍼즐이 실려 있다.

더 일반적으로 이 퍼즐의 원조는 스멀리언의 유명한 기사와 악당 퍼즐들이다. (무대가 되는 상상의 섬의 모든 주민은 기사 혹은 악당인데 기사는 항상 참말만을 하고 악당은 항상 거짓말만 한다. 섬을 방문한 외지인은 참/거짓 질문을 하여 원하는 정보를 얻어내야 한다.) 이 퍼즐의 한 버전은 1980년대의 판타지 영화 Labyrinth에 등장해 유명해졌다. 문 2개 앞에 각각 보초가 서 있는데, 한 명은 참말을 하고 나머지 한명은 거짓말을 한다. 문 하나는 성으로 통하고 또 하나는 '죽음'에 이른다. 퍼즐은 보초 1명에게 참/거짓 질문 한 번만을 하여 성으로 통하는 문을 알아내는 것이다. 영화에서의 답은 "다른 보초라면 이 문이 성으로 통한다고 대답해 줄까요?"였다. 이 경우 아니오라는 대답을 한 보초가 지키고 있는 문이 성으로 통하는 문이다.

풀이

불로스는 같은 글에서 해답을 제시했다. "처음으로 할 일은 '랜덤'이 아니라고 확신할 수 있는 신을 찾아내는 것이다. 그러면 그는 '참' 아니면 '거짓'이다." 다양한 질문으로 이것을 해낼 수 있다. 한 가지 전략은 복잡한 논리적 연결식(logical connectives 수정 바람)을 이용하는 것이다.

불로스의 질문은 이렇다:

• 'da'가 '예'를 뜻하는 것과 당신이 '참'인 것과 B가 '랜덤'인 것은 모두 동치입니까?

혹은 같은 의미로:

• "당신은 '거짓'이다", "'ja'는 '예'를 뜻한다", "B는 '랜덤'이다"의 세 문장 중 참인 것이 홀수개입니까?

counterfactuals(수정 바람)을 이용한 보다 간단한 풀이가 있다. 풀이의 열쇠는, 임의의 참/거짓 질문 Q에 대해서 다음의 참/거짓 질문

• 당신에게 Q를 물으면 당신은 'ja'라고 대답하겠습니까?

에 대한 대답은 Q에 대한 옳은 답이 '예'라면 'ja' 이고 '아니오'라면 'da' 일 것이라는 사실이다. 그 이유는 다음의 8가지 가능한 경우에 대해 생각해 보면 알 수 있다.

• 'ja'가 '예'이고 'da'가 '아니오'를 뜻한다고 가정하자.
  1. '참'에게 질문했고 'ja'라는 대답을 들었다면, 그는 참말을 하기 때문에 Q에 대한 옳은 답은 '예'이다.
  2. '참'에게 질문했고 'da'라는 대답을 들었다면, 그는 참말을 하기 때문에 Q에 대한 옳은 답은 '아니오'이다.
  3. '거짓'에게 질문했고 'ja'라는 대답을 들었다면, 그는 거짓말을 하기 때문에 그에게 Q를 물었다면 'da'라고 대답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 옳은 답은 'ja', 즉 '예'이다.
  4. '거짓'에게 질문했고 'da'라는 대답을 들었다면, 그는 거짓말을 하기 때문에 그에게 Q를 물었다면 'ja'라고 대답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 옳은 답은 'da', 즉 '아니오'이다.

• 'ja'가 '아니오'이고 'da'가 '예'를 뜻한다고 가정하자.
  1. '참'에게 질문했고 'ja'라는 대답을 들었다면, 그는 참말을 하기 때문에 Q에 대한 옳은 답은 '예'이다.
  2. '참'에게 질문했고 'da'라는 대답을 들었다면, 그는 참말을 하기 때문에 Q에 대한 옳은 답은 '아니오'이다.
  3. '거짓'에게 질문했고 'ja'라는 대답을 들었다면, 그는 거짓말을 하기 때문에 그에게 Q를 물었다면 'ja'라고 대답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 옳은 답은 'da', 즉 '예'이다.
  4. '거짓'에게 질문했고 'da'라는 대답을 들었다면, 그는 거짓말을 하기 때문에 그에게 Q를 물었다면 'da'라고 대답했을 것이다. 그는 거짓말쟁이이므로 Q에 대한 옳은 답은 'ja', 즉 '아니오'이다.

이 사실을 이용해서 다음처럼 진행할 수 있다.

• B에게 "당신에게 'A가 '랜덤'인가요?'라고 물으면 'ja'라고 대답하겠습니까?" 라고 묻는다. B가 'ja'라고 대답한다면 그것은 '랜덤'인 B의 무작위 대답이거나, 혹은 B가 '랜덤'이 아니고 위의 논의에 의하여 A가 '랜덤'이라는 결론에 이른다. 어느 쪽이건 C는 '랜덤'이 아니다. B가 'da'라고 대답한다면 마찬가지로 B가 랜덤이거나, 그렇지 않다면 B가 랜덤이 아니고 따라서 A가 '랜덤'이 아니다. 어느 쪽이건 A는 '랜덤'이 아니다.

• 앞의 질문에서 '랜덤'이 아닌 것으로 밝혀진 신(A 또는 C)에게 가서 "내가 당신에게 '당신이 '참'인가요?'라고 물으면 'ja'라고 대답하겠습니까?"라고 묻는다. 그는 '랜덤'이 아니므로 대답이 'ja'라면 그는 '참'일 것이고 'da'라면 '거짓'일 것이다.

• 같은 신에게 "내가 당신에게 'B가 '랜덤'인가요?'라고 물으면 'ja'라고 대답하겠습니까?"라고 묻는다. 그 대답을 들으면 B의 이름을 알 수 있고, 나머지 한 신의 이름은 자동으로 남은 하나로 정해진다.

'랜덤'의 행동

대부분의 독자들은 '랜덤'이 완전히 무작위의 답을 제시할 거라고 가정한다. 하지만 불로스의 보충 설명 3번째를 보면 그렇지 않다.

• '랜덤'이 참말을 할지 거짓말을 할지는 그의 머릿속에서 던진 동전의 앞뒷면에 따라 결정되는 것으로 생각할 수 있다. 앞면이라면, 참말을 한다. 뒷면이라면 거짓말을 할 것이다.

이것은 '랜덤'이 무작위적으로 '참말쟁이' 나 '거짓말쟁이' 가 된다는 뜻이지, 무작위적으로 'da' 나 'ja'라고 대답한다는 뜻이 아니다. 즉 사실은 '랜덤'에게 "현재의 마음 상태의 당신에게 Q를 물으면 당신은 'ja'라고 대답하겠습니까?"라고 물으면 우리가 원하는 대답을 할 수밖에 없다. ('참'이건 '거짓'이건 저 질문으로 원하는 답을 얻었던 것을 생각해 보라.) 이렇게 되면 문제가 매우 쉬워진다.

불로스의 세 번째 보충 설명을 다음과 같이 수정하면 풀이장의 끝에서 이야기했던 방법이 필요해진다.

• '랜덤'이 'ja'라고 대답할지 'da'라고 대답할지는 그의 머릿속에서 던진 동전의 앞뒷면에 따라 결정되는 것으로 생각할 수 있다. 앞면이라면, 'ja'라고 말한다. 뒷면이라면 'da'라고 대답한다.

신의 머리 폭발하다

A simple solution to the hardest logic puzzle ever에서, B. Rabern 과 L. Rabern 은 신이 줄 수 있는 대답이 'ja'와 'da'뿐만이 아님을 지적했다. 때로는 신이 아예 대답할 수 없을 때도 있다. 예를 들면, "당신은 이 질문에 '아니오'라는 뜻을 가진 단어로 대답할 것입니까?"라는 질문을 '참'에게 던진다면 그는 'ja'로도 'da'로도 대답할 수 없다. (논문은 이것을 가리켜 '머리 폭발'이라고 표현했다. "...그들은 신이고 오류가 있을 수 없다! 그들에게 주어진 선택은 하나이다. - 머리가 폭발한다.") 이 "머리 폭발"을 허용하면 변형된 퍼즐('랜덤'이 실제 무작위로 대답하도록)의 새로운 풀이를 줄 수 있으며, 원래의 퍼즐을 질문 2번만으로 (3번이 아님) 해결할 수 있게 된다. 저자들은 유사하지만 간단한 다음 퍼즐을 질문 2번만 써서 풀어낸다.

• 세 신 A, B, C의 이름은 각각 Zephyr, Eurus, Aeolus 인데 누가 누구인지는 모른다. 각 신은 항상 참말만을 한다. 이제 참/거짓 질문 3번만 해서 누가 누구인지 알아내어라. 단, 각 질문은 한 번에 한 명에게만 할 수 있다. 신은 영어를 이해하고 영어로 대답할 것이다.

이 퍼즐은 (당연히) 질문 3번으로 해결할 수 있다. 이제 질문 2번으로 해결하기 위해서는 다음의 보조정리를 쓴다.

Tempered Liar Lemma. A에게 "{[(당신은 이 질문에 '아니오'라고 대답한다) 그리고 (B는 Zephyr이다)] 또는 (B가 Eurus이다)}인 것이 사실입니까?" 라고 묻는다고 하자. 대답이 '예'라면 B가 Eurus 이고, '아니오'라면 Aeolus 일 것이며 A의 머리가 폭발한다면 B는 Zephyr일 것이다. 따라서 우리는 질문 한 번만으로 B가 누구인지 알아낼 수 있다.

이 보조정리를 쓰면 이 퍼즐을 질문 2번만에 푸는 것은 간단하다. 비슷한 방법을 쓰면 원래의 퍼즐을 질문 2번으로 해결할 수 있다.

같이 보기

• 조지 불로스
• 레이먼드 스멀리언
• 기사와 악당
• 논리 퍼즐

각주

• George Boolos, The hardest logic puzzle ever (The Harvard Review of Philosophy, 6:62–65, 1996).
• T.S. Roberts, Some thoughts about the hardest logic puzzle ever (Journal of Philosophical Logic 30:609–612(4), December 2001).
• Brian Rabern and Landon Rabern, A simple solution to the hardest logic puzzle ever (Analysis 68 (298), 105–112, April 2008).
• Raymond Smullyan, What is the Name of This Book? (Prentice Hall, Englewood Cliffs, NJ, 1978).
• Raymond Smullyan, The Riddle of Sheherazade (A. A. Knopf, Inc., New York, 1997).

외부 링크

• George Boolos. The hardest logic puzzle ever. The Harvard Review of Philosophy, 6:62–65, 1996.
• T.S. Roberts. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609–612(4), December 2001.
• Brian Rabern and Landon Rabern. A simple solution to the hardest logic puzzle ever. Analysis 68 (298), 105–112, April 2008. Archived 2019년 9월 27일 - 웨이백 머신
• Tom Ellis. Even harder than the hardest logic puzzle ever.