1. 개요
Knights and Knaves항상 진실만을 말하는 기사와 항상 거짓만을 말하는 건달에 관한 논리 퍼즐.
미국의 수학자 레이먼드 스멀리언(1919~2017)이 이 분야의 거장으로 통한다. "이 책의 제목은 무엇인가?"[1] "셰에라자드의 수수께끼"[2] 등의 저서에서 이런 부류의 문제들을 다루었다. 레이먼드 스멀리안이 고안한 훨씬 난이도 높은 진화 버전으로 가장 어려운 논리 퍼즐이 있다.
2. 문제
상기 했듯이 이런 문제들로만 책 십수권이 나와있기 때문에 대표적인 문제들만을 소개한다.- 전제
- 이 곳에 사는 사람은 모두 기사, 또는 건달이다.
- 외관상으로는 기사와 건달을 구별할 수 없다.
- 기사는 항상 논리적으로 진실인 문장만을 말한다.
- 건달은 항상 논리적으로 거짓인 문장만을 말한다.
2.1. 문제 1
가장 고전적인 문제.{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | A, B, C는 기사와 건달의 섬의 주민들이다. 이 섬에 여행을 온 나는 그들 곁을 지나가다가 A에게 물었다. "당신은 기사입니까, 건달입니까?" 이에 A가 대답했지만, 발음이 애매해서 알아들을 수가 없었다. 그러자 B가 추가적으로 대답했다. "A는 자신이 건달이라고 말했습니다." 그 순간 C가 끼어들었다. "B는 지금 거짓말을 하고 있습니다." B와 C의 신분을(각각 기사인지 건달인지) 밝혀라. |
- [ 해답 ]
- ||<tablebordercolor=#552582>일단 이 문제에서 A의 신분은 중요치 않다. 만약 A가 기사였다면 사실대로 자신은 기사라고 대답했을 테고, 건달이었어도 거짓말을 해서 기사라고 대답했을 것이다. 즉 A는 기사든 건달이든 무조건 자신을 기사라고 말할 수밖에 없다.[3]
따라서 A의 답은 무조건 기사이기에 B의 'A는 자신이 건달이라고 말했다'라는 것이 거짓말이 되어야 한다. 만약 'A는 자신이 건달이라고 말했다'는 말 자체가 참이라면, A가 한 말에 모순이 생기기에, B는 건달이고, B의 거짓말을 제대로 짚어낸 C는 기사일 수밖에 없다. ||
2.2. 문제 2
문제 1을 본 레이먼드 스멀리언이 사실 C는 하는 일 없는 쩌리라는 사실을 알고 변형한 문제.{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | 내가 A에게 다음과 같이 물었다고 해보자. "여러분 중에 기사는 몇 분이나 있습니까?" A가 대답했으나 이번에도 발음이 애매해서 알아들을 수가 없었고, B가 추가적으로 대답했다. "A는 우리 중에 기사는 한 명이라고 말했습니다." 그 순간 C가 끼어들었다. "B는 지금 거짓말을 하고 있습니다." B와 C의 신분을 밝혀라. |
- [ 해답 ]
- ||<tablebordercolor=#552582>B와 C의 의견이 엇갈리므로 한 명은 기사, 한 명은 건달일 것이다. 그리고 A가 기사인가 아닌가에 따라 일행의 구성은 '기사 2 & 건달 1' 혹은 '기사 1 & 건달 2'로 나뉜다.
A가 기사일 경우, A는 B 혹은 C 중에 한 명과 자신을 합쳐서 "2명"이라고 대답했을 것이다. 이는 B의 대답과 모순되므로 B는 거짓말을 한 건달이고, B의 거짓말을 잡아낸 C는 기사이다.
A가 건달일 경우, 기사는 B 혹은 C 둘 중 1명이므로 A의 대답은 절대 "1명"이 될 수 없다. 그러나 B는 A가 기사는 1명이라고 대답했다 주장하고 있으므로 B는 건달이고, 이를 지적하는 C는 기사이다.
따라서 B는 건달이고, C는 기사이다. ||
2.3. 문제 3
{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | A, B 두 사람이 등장한다. A가 "내가 건달 혹은 B는 기사이다." 라고 말했다고 하자. A와 B는 각각 어떤 사람인가? |
- [ 해답 ]
- ||<tablebordercolor=#552582>논리학에서 문장 "ㄱ 또는(or) ㄴ이다."가 참이기 위해서는 명제 ㄱ, ㄴ 둘 중 하나 혹은 둘 다 참이면 된다. 둘다 거짓일 때만 거짓이다.
여기서 ㄱ은 '나는 건달'다시 말해 'A는 건달'이고, ㄴ은 'B는 기사'이다. 이 때 ㄱ,ㄴ 하나라도 참이면 이 문장은 참이다.
A가 건달일 경우 거짓말만 말하기에 "A는 건달이거나 혹은 B는 기사이다."는 거짓이어야 한다. 하지만 앞쪽 명제 ㄱ(A=건달)이 참이기 때문에 전체 문장은 무조건 참일 수밖에 없고, A의 "내가 건달 혹은 B는 기사이다."는 거짓이라는 것과 모순된다. 따라서 A는 건달이 될 수 없고 기사이어야만 한다.
A는 기사이고 문장 전체는 참이어야 하므로, 뒤쪽 명제(B=기사)도 참이어야 한다. 따라서 B는 기사이다.
따라서 A, B 모두 기사이다. ||
2.4. 문제 4
{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | A와 B가 있다. A가 "우리 둘다 건달이야" 라고 얘기 했다. A와 B는 각각 어떤 사람인가? |
- [ 해답 ]
- ||<tablebordercolor=#552582>화자가 건달(거짓만 얘기함)이라면 '나는 건달이다'라는 말은 절대 할 수 없다. 건달이라면 사실을 얘기 한 것이 되기에 모순된다. 마찬가지로 기사(진실만 얘기함) 역시 '나는 건달이다'는 말은 거짓말이기에 절대 못한다. 따라서 A와 B는 둘 다 건달이거나 둘 다 기사인 상황은 나올 수 없다. 따라서 A와 B 중 한명은 건달이고 한명은 기사인 상황이다. '우리 둘다 건달이야'라는 말은 거짓말을 할 수없는 기사가 할 수 있는 말이 아니다. 따라서 A가 건달이 된다.
A는 건달, B는 기사이다. ||
2.5. 문제 5
{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | A 한 명만 등장한다. A에게 "당신은 기사입니까?"라고 묻자, 그는 "내가 기사라면, 내 손에 장을 지진다."라고 대답했다. A는 자기 손에 장을 지져야 함을 증명하라. |
- [ 해답 ]
- ||<tablebordercolor=#552582>본 문제는 명제 논리에 대한 기본 지식이 없다면 이해하기 힘들 수도 있다. 일단 P이면 Q이다.(P→Q) 형식의 진리표를 확인하고 올 것. 조건문 문서도 참고하면 좋다.
'A면, 내 손에 장을 지진다.'라는 표현은 흔히, 'A가 절대 아니다' 또는 'A가 아님을 보장한다.'의 의미로 쓰인다.[4] 하지만 논리학에서 'A면 B다'라는 명제는, A가 거짓일 경우 B의 참-거짓 여부와 상관없이 참이다.[5] 오직 A가 참이고, B가 거짓일 경우에만 거짓이 된다. 즉, 누군가 "내가 기사라면, Q이다."는 진술을 했다면, 그 말을 한 당사자는 기사이어야 하며, 기사는 거짓말을 하지 않기에 Q는 참이어야만 한다.[6]
P→Q 형식의 문장은 "P는 참이고 Q는 거짓일 경우, 오직 이 경우"에만 거짓이 된다. 앞서 말한 것처럼 조건 P가 거짓일 경우에는 Q가 참이든 거짓이든 무조건 참이 된다. 만약 A가 건달이라면 조건인 P자체(내가 기사라면)가 거짓이 되는데, Q인 손에 장을 지진다가 참이냐 거짓이냐에 상관없이 무조건 참인 문장이 되어 버리기에 모순이 생긴다. 다시말해 기사가 아니라면(P가 거짓이라면), "내가 기사라면, 내 손에 장을 지진다."는 무조건 참이되는 문장이다. 거짓말만 하는 건달이 말할 수 없는 문장이다. 만약 이 문장이 거짓이 되는 조건으로 따져도 결과는 같은데, 그러기 위해선 "P:나는 기사=참, Q:장 지짐=거짓"이 두조건을 모두 충족해야 한다. 그런데 '나는 건달 즉, P:나는 기사=거짓'이므로 P 부터 충족 될 수 없다.[7]
따라서 P인 '내가 기사이다'는 절대 거짓 일수 없기에 A는 기사이어야 하며, 기사는 진실만 얘기하기에 자신이 한 말에 따라 장을 지져야 한다.기사는 진실되지만, 가끔 멍청한 말을 한다는 사실도 알 수 있다||
2.6. 문제 6
{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | 세번째 유형의 주민이 이 마을에서 발견되었다고 하자. 이 유형의 주민은 '스파이'로 진실을 얘기할 수도 있고, 거짓을 얘기할 수도 있다. 당신은 세 사람 A, B, C를 만났고, 기사, 건달, 스파이 각각 한명씩 있었지만 누가 누구인지는 알 수 없었다. 이때 A가 "나는 기사입니다."라고 말했다. 이에 B는 "A가 진실을 말하고 있습니다."라고 얘기했다. 마지막으로 C는 "나는 스파이입니다." 라고 말했다. 이때 A, B, C는 각각 누구일까?[8] |
- [ 해답 ]
- ||<tablebordercolor=#552582>우선 B의 말이 거짓말이라고 하자
- 그렇다면 "A가 진실을 말하고 있습니다."는 말은 거짓이다. 이 말을 토대로 A는 거짓을 말했기 때문에 A는 기사가 아니다. 그런데 B 역시 거짓말을 했이기에 B 역시 기사가 아니다. A와 B는 스파이 아니면 건달이어야만다. 그러면 나머지 C는 반드시 기사이어야만 한다. 하지만 C는 "나는 스파이입니다."라고 말했다. 이렇게 B의 말이 거짓이라고 하면, 모순이 생기므로 B의 말은 절대 거짓말이 되어선 안된다.
- B의 말이 거짓말이 아니기에 'A는 진실을 말하고 있습니다.'는 참이다. 그렇다면 A가 말한 "나는 기사입니다."는 참이다. 따라서 A는 기사이다. 이때 B는 참을 말했고, A가 기사이기에 기사는 될 수 없다. 따라서 B는 참도 말할 수 있는 스파이이다. 마지막으로 스파이라고 거짓을 얘기한 C는 건달이다.
따라서 A는 기사, B는 스파이, C는 건달 ||
2.7. 문제 7
{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | 다시 스파이는 없고, 기사와 건달만 있는 마을이라고 하자. 만약 이 마을에 주민들이 우리의 말을 알아 듣지만 대답은 자신의 나라의 말로 한다고 해보자. 주민들은 '예'와 '아니오'라는 대답은 못하지만 자기 나라 말인 'Ja'와 'Da'를 사용해 대답한다. 이때 우리는'Ja'와 'Da' 중 어느 것이 '예'를 의미하는 지, 어떤것이 '아니오'를 의미하는지 모른다. 만약 우리가 "'Ja'가 '예'를 의미합니까?"라는 질문을 했을 때 주민 중 어떤 사람이 Ja로 대답했다면, 이 사람은 기사일까 건달일까? |
- [ 해답 ]
- ||<tablebordercolor=#552582>답은 기사이다.
우리는 'Ja'와 'Da'의 의미는 모르지만, 이것과 상관없이 해석 할 수 있다.
우선 대답한 사람이 기사일 경우로 따져보자.- 만약 'Ja'가 '예'라면 "'Ja(예)'가 '예'를 의미합니까?"에 '예'라고 답해야 하기에, 'Ja'라고 대답할 것이다.
- 만약 'Ja'가 '아니오'라면 "'Ja(아니오)'가 '예'를 의미합니까?"에 아니오라고 답해야 하기에, 아니오의 의미인 'Ja'로 대답할 것이다.
따라서 Ja로 대답했다면 기사이다.
대답한 사람이 건달일 경우도 생각해보면- 만약 'Ja'가 '예'라면 "'Ja(예)'가 '예'를 의미합니까?"에 거짓말로 '아니오'라고 답해야 하기에, 'Da'라고 대답할 것이다.
- 만약 'Ja'가 '아니오'라면 "'Ja(아니오)'가 '예'를 의미합니까?"에 거짓말로 '예'라고 답해야 하기에, 예의 의미인 'Da'로 대답할 것이다.
따라서 Da로 대답했다면 건달이다.
결론적으로 기사는 'Ja'로 답하고, 건달은 'Da'로 답한다. ||
2.8. 문제 8
{{{#!wiki style="border:2px solid #00BFB3;border-radius:0px;padding:12px" | 위의 문제에서 'Ja'와 'Da'의 의미를 알아보고 싶어졌다. 당신은 'Ja'혹은 'Da'로 대답할 수 있는 질문을 하나 만들어서 알아내야한다. 어떤 질문을 해야하나? |
- [ 해답 ]
- ||<tablebordercolor=#552582>"당신은 기사입니까?"라고 물어 보면 된다.
대답하는 사람이 기사이건 건달이건 무조건 답은 '예'라고 해야 한다.
기사는 사실을 얘기하기에 '예'라고 할것이고, 건달은 거짓말을 해야하기에 '예'라고 해서 기사인척 해야한다.
따라서 당신은 기사입니까? 라고 물어보고,- 만약 'Ja'라고 대답했다면, 'Ja'가 '예'이고, 'Da'가 '아니오'가 된다.
- 만약 'Da'라고 대답했다면, 'Da'가 '예'이고, 'Ja'가 '아니오'가 된다.||
3. 변형
오래전부터 내려온 유서깊은 문제인만큼 배리에이션 역시 많다.- 천사와 악마 문제
- 미녀일까 호랑이일까
- 월화수에는 참말을, 다른 요일에는 거짓말을 하는 사자와 목금토에는 참말을, 다른 요일에는 거짓말을 하는 유니콘이 등장하는 사자와 유니콘 이야기. [9]
- 패턴은 사자와 유니콘과 동일하지만 둘이 똑같이 생겨 구별할 수 없는 쌍둥이 튀틀덤과 튀틀디가 나오는 문제
- 랜덤하게 거짓말도 하고 참말도 하는 보통사람이 등장
- 요상한 법률에 의해 기사는 건달과, 건달은 기사하고만 결혼해야됨.
그리고 독자는 부부파티에 초대되어 고통받는다 - 자신의 신분을 거꾸로 알고 있고 진짜 신분과 반대되는 대답을 하는[10] 정신병자가 등장[11]
4. 기타
장삼이라는 작가의 판타지 소설. 상단의 문단과는 동명일뿐 연관된 접점은 없다.[1] 책 제목이 "What Is the Name of This Book?"이다(...) 한국어로는 "퍼즐과 함께하는 즐거운 논리"라는 재미없는 이름으로 번역되었다. 내용중에 책 제목과 관련된 드립이 있는데 아쉬운 부분. 물론 원제의 뜻을 살려서 번역한 버젼도 있다.[2] 한국어로는 "사고력을 키워주는 논리퍼즐"이라는 이름으로 번역[3] A가 건달이라고 한다면 거짓말 밖에 못하는 거짓말쟁이가 '나는 거짓말쟁이'라고 말한 것과 같은 상황이 된다.[4] 원문은 I will eat my hat. 그럴 일은 없다거나 사실이 아님을 장담할 때 사용하는 표현이다. 씽2게더의 등장인물 클라우스도 누시의 이틀만에 춤을 가르치겠다는 말에 "성공하면 내 모자를 먹고 만다"라고 말하면서 비웃는다.[5] "내일 해가 서쪽에서 뜨면, 내 손에 장을 지진다."라고 누군가가 말했다 치자. 그런데 다음날 해가 서쪽에서 뜨지 않았다면, 장을 지지든 지지지 않든 이 사람은 참을 말한 것이다.[6] 기사가 아니라면 해당 문장은 무조건 참이어야한다. 건달은 참을 말하면 모순이 되므로 "내가 기사라면, Q이다."는 기사만이 할 수 있는 말이다.[7] 다른 예를 들면 100% 거짓만 말하는 거짓말쟁이가 '내가 거짓말쟁이가 아니라면, 내 손에 장을 지진다'는 말을 할 수없는 것과 같다. 오직 'P는 참이고, Q는 거짓이어야만 거짓'이 되는데 P인 '내가 거짓말쟁이가 아니다.'부터 거짓이기에 Q를 따지기 전에 무조건 위 문장은 참이 될 수밖에 없다. 따라서 거짓말쟁이가 이렇게 말하면 참을 말한 것이기에 모순이 생기게 될 터이니 이런 말은 할 수 없다.[8] 문제6,7,8은 가장 어려운 논리 퍼즐과 연관된다.[9] 일요일에는 둘 다 거짓말을 한다.[10] 즉 반대로 알고 있는 신분에 따라 답하는[11] 즉 참말만을 하는 정상 기사와 미친 건달, 거짓말만 하는 정상 건달과 미친 기사의 4종류의 인간이 등장