기사와 건달

 

Knights and Knaves
1. 개요
2. 문제
2.1. 문제 1
2.2. 문제 2
2.3. 문제 3
2.4. 문제 4
3. 해답
3.1. 문제 1
3.2. 문제 2
3.3. 문제 3
3.4. 문제 4
4. 변형
5. 기타


1. 개요

항상 진실만을 말하는 기사와 항상 거짓만을 말하는 건달에 관한 논리 퍼즐.
미국의 수학자 레이먼드 스멀리언(1919~2017)이 이 분야의 거장으로 통한다. "이 책의 제목은 무엇인가?"[1] "셰에라자드의 수수께끼"[2] 등의 저서에서 이런 부류의 문제들을 다루었다. 레이먼드 스멀리안이 고안한 훨씬 난이도 높은 진화 버전으로 가장 어려운 논리 퍼즐가 있다.

2. 문제

상기 했듯이 이런 문제들로만 책 십수권이 나와있기 때문에 대표적인 문제들만을 소개한다.
  • 전제
    • 이 곳(주로 섬)에 사는 사람은 모두 기사, 또는 건달이다.
    • 외관상으로 기사와 건달을 구별할 수는 없다.
    • 기사는 항상 논리적으로 진실인 문장만을 말한다.
    • 건달은 항상 논리적으로 거짓인 문장만을 말한다.

2.1. 문제 1

가장 고전적인 문제.

A,B,C는 기사와 건달의 섬의 주민들이다. 이 섬에 여행을 와서 그들 곁을 지나가던 내가 A에게 물었다.

'당신은 기사입니까 건달입니까?'

이에 A가 대답했으나 발음이 불분명하여 알아들을 수가 없었다. B가 추가적으로 대답했다.

'A는 자신이 건달이라고 말했습니다.'

그 순간 C가 끼어들었다.

'B는 지금 거짓말을 하고있습니다.'

B와 C의 신분을(각각 기사인지 건달인지) 밝혀라.


2.2. 문제 2

문제1을 본 레이먼드 스멀리언이 사실 C는 하는 일 없는 쩌리라는 사실을 알고 변형한 문제.

내가 A에게 다음과 같이 물었다고 해보자.

'여러분 가운데 기사는 몇 분이나 되십니까?'

이에 A가 대답했으나 발음이 불분명하여 B가 추가적으로 대답했다.

'A는 우리중 기사는 한 명이라고 말했습니다.'

그 순간 C가 끼어들었다.

'B는 지금 거짓말을 하고있습니다.'

B와 C의 신분을 밝혀라.


2.3. 문제 3

A, B 두 사람이 등장한다.

A가 "나는 건달이거나 혹은 B는 기사이다." 라고 말했다고 하자.

A와 B는 각각 어떤 사람인가?


2.4. 문제 4

A 한 명만 등장한다.

A에게 "당신은 기사입니까?"라고 묻자, 그는 "내가 기사면 내 손에 장을 지진다.[3]

"라고 대답했다.

A는 자기 손에 장을 지져야 함을 증명하라.


3. 해답


3.1. 문제 1

일단 이 문제에서 A의 신분은 중요치 않다. 만약 A가 기사였다면 그대로 진실되게 자신은 기사라고 말했을테고, A가 건달이었다면 일부러 거짓말을 해서 자신은 기사라고 말했을 것 이다. 즉 A는 기사든 건달이든 무조건 자신을 기사라고 말한다.
고로, B가 주장한 'A는 스스로를 건달이라고 말했다'는 성립될 수 없는 거짓말이며 따라서 '''B는 건달''', B의 말이 거짓말이라고 말한 C는 기사인 것 이다.

3.2. 문제 2

B와 C의 의견이 엇갈리므로 한 명은 기사, 한 명은 건달일 것이다. 따라서 A가 기사이냐 건달이냐에 따라 기사2/건달1 또는 기사1/건달2의 구성이어야 한다. A가 기사일 경우, A는 "2명"이라고 말했을 것이고, 따라서 거짓말을 한 B는 건달, 이를 지적한 C는 기사가 된다. A가 건달일 경우, A는 "1명"을 제외한 다른 대답을 해야 한다. 따라서 "A는 1명이라고 대답했다"고 진술한 B역시 건달이며, 이를 지적한 C는 기사가 된다.
따라서 B는 건달, C는 기사이다.

3.3. 문제 3

논리학에서 문장 "ㄱ 또는(or) ㄴ이다."가 참이기 위해서는 명제 ㄱ, ㄴ 둘 중 하나 혹은 둘 다 참이면 된다. A가 건달일 경우, "A는 건달이거나 혹은 B는 기사이다."가 거짓이어야 한다. 하지만 앞쪽 명제(A=건달)가 참이기 때문에 전체 문장은 무조건 참일 수밖에 없다. 따라서 A는 건달일 수 없으며, 따라서 기사이다. A가 기사이기 때문에 문장 전체가 참이기 위해선 뒤쪽 명제(B=기사)가 참이어야 한다. 따라서 B는 기사이다.
따라서 A, B 모두 기사이다.

3.4. 문제 4

본 문제는 논리학에 대한 기본 지식이 없다면 이해하기 힘들 수도 있다. 일단 P이면 Q이다.(P→Q) 형식의 진리표를 확인하고 올 것.
답부터 말하면, 누군가 "내가 기사라면, Q이다."는 진술을 했다면, 그 말을 한 당사자는 기사이며, Q는 참이어야만 한다. 증명은 다음과 같다.
P→Q 형식의 문장은 "P는 참이고 Q는 거짓일 경우, 그리고 오직 그 경우"에만 거짓이 된다. (진리표 참고) 따라서 A가 건달이라면 문장 "나는 기사이다→나는 장을 지질 것이다." 는 거짓이어야 하는데, 그러기 위해서는 "나는 기사=참, 장 지짐=거짓"이어야 한다. 하지만 「나는 기사이다」는 참일 수 없으므로, 건달은 절대로 위와 같은 문장을 말할 수 없다. 따라서 A는 기사이며, 따라서 자신이 한 말에 따라 장을 지져야 한다.

4. 변형

오래전부터 내려온 유서깊은 문제인만큼 배리에이션 역시 많다.
  • 천사와 악마 문제
  • 월화수에는 참말을, 다른 요일에는 거짓말을 하는 사자와 목금토에는 참말을, 다른 요일에는 거짓말을 하는 유니콘이 등장하는 사자와 유니콘 이야기.
  • 패턴은 사자와 유니콘과 동일하지만 둘이 똑같이 생겨 구별할 수 없는 쌍둥이 튀틀덤과 튀틀디가 나오는 문제
  • 랜덤하게 거짓말도 하고 참말도 하는 보통사람 이 등장
  • 요상한 법률에 의해 기사는 건달과, 건달은 기사하고만 결혼해야됨.
  • 자신의 신분을 거꾸로 알고 있고 진짜 신분과 반대되는 대답을 하는[4] 정신병자가 등장[5]
  • 기사와 건달이 외국인이라 듣기는 가능하지만 말하는 것은 자기나라 말만 가능함. Yes/No에 해당되는 단어가 Bal/Da지만 어떤 단어가 Yes인지는 알 지 못함.

5. 기타

장삼이라는 작가의 판타지 소설. 상단의 문단과는 동명일뿐 연관된 접점은 없다.

[1] 책 제목이 "What Is the Name of This Book?"이다(...) 한국어로는 "퍼즐과 함께하는 즐거운 논리"라는 이름으로 번역되었다. 내용중에 책 제목과 관련된 드립이 있는 데 아쉬운 부분. 물론 원제의 뜻을 살려서 번역한 버젼도 있다.[2] 한국어로는 "사고력을 키워주는 논리퍼즐"이라는 이름으로 번역[3] 원문은 I will eat my hat.[4] 즉 반대로 알고 있는 신분에 따라 답하는[5] 즉 참말만을 하는 기사와 미친 건달, 거짓말만 하는 건달과 미친 기사의 4종류의 인간이 등장

분류