읽기부터 증명까지 스스로 이어 볼까요?

할 수 있습니다. 이번에는 작은 독서 모임의 기록을 함께 읽겠습니다. 먼저 어떤 말인지 정하고, 따라올 듯한 결론을 골라 본 뒤, 작은 세계와 증명으로 확인할 거예요. 답을 펼치기 전에 한 문장이라도 직접 적어 보세요.

두 결론을 따로 확인하겠습니다. 한 결론을 뒷받침하는 근거가 더 강한 결론까지 보장하는지는 다시 살펴봐야 합니다.

이번에는 그 독서 모임의 검토 대상인 사람 전체로 정하겠습니다. 신청하지 않은 사람도 포함될 수 있습니다. 영역에는 적어도 한 사람이 있습니다. 실제 사람이 몇 명인지는 전제에서 정하지 않았어요. 뒤에 나올 세 사람 세계는 여러 가능한 해석 가운데 하나입니다.

영역에서 누구를 골라도, 그 사람이 신청했다면 확인을 받았다는 말이기 때문입니다. 신청하지 않은 사람까지 신청자로 만드는 주장이 들어 있지는 않습니다. 반면 ‘신청한 사람이 있다’는 말에는 실제로 S를 만족하는 대상이 필요합니다.

그렇습니다. 아래 결론들은 서로 다른 내용을 요구합니다. 우선 예상을 적어 보고, 다음 절의 세계와 그 뒤의 증명으로 확인해 보세요.

‘가’는 신청자를 살피는 조건문입니다. ‘다’는 신청 여부와 관계없이 영역의 모든 사람에게 E를 요구합니다. 그리고 ‘나’의 누군가는 아직 아라로 정해져 있지 않아요.

다음 세계에서는 영역이 정확히 아라·보라·찬우 세 사람입니다. 세 사람은 서로 다르고 a는 아라를 가리킵니다. 아래 표가 S·V·E의 값을 모두 정합니다. 빈칸이나 미확인 상태는 없으며, 더 많은 사람이나 숨은 신청자를 이 세계에 덧붙이지 않습니다.

첫 전제가 금지하는 경우는 ‘신청했는데 확인을 받지 않은 사람’입니다. 찬우는 신청하지 않았으므로 그 금지된 경우에 해당하지 않습니다. 이 기록은 확인받는 다른 경로를 배제하지 않았습니다.

어느 추론의 반모형인지 결론까지 말해야 합니다. 모든 전제가 참이라는 조건은 이미 확인했습니다. 이제 목표 결론을 하나씩 계산합니다.

그 두 결론이 이 세계에서 참이라는 사실을 확인한 것입니다. 타당성은 전제를 만족하는 모든 해석을 대상으로 합니다. 다음 증명에서는 사람 수나 특정 명단에 기대지 않고, 전제에서 각 결론을 이끌겠습니다.

마지막에 무엇을 해야 하는지 먼저 봅시다. 목표 ∀x(S(x)→E(x))를 얻으려면 임의의 대상에 대해 S에서 E로 가는 이유가 필요합니다. 새로운 이름 d를 고르고, S(d)를 잠시 가정한 뒤 E(d)를 얻겠습니다. 그 가정을 닫아 조건문을 만들고 마지막에 일반화합니다.

d를 고를 때 특정한 신원이나 성질을 미리 정하지 않습니다. 그다음 조건문을 증명하기 위해 S(d)를 잠깐 가정합니다. 일반화할 때에는 이 가정을 이미 닫아서, 남는 주장이 S(d)→E(d)가 되도록 합니다. ‘누구에게나 이 조건 연결이 성립한다’고 보이는 순서입니다.

다음 표의 1~10줄은 한 증명의 앞부분입니다. 3줄의 존재 전제는 다음 절에서 쓸 것이므로 미리 적어 둡니다. ‘바깥’에는 전제 1~3만 열려 있고, ‘안’에는 4줄의 임시 가정도 열려 있습니다. d는 전제와 목표에 나오지 않는 새 이름입니다.

일반화의 출발 식인 9줄에는 d가 있습니다. 확인할 것은 d가 남은 전제나 미해제 가정에 들어 있는지, 일반화한 결론에 남아 있는지입니다. 전제 1~3에는 d가 없고 4줄 가정은 닫혔으며, 10줄에는 d가 없습니다. 대입을 거꾸로 확인해도 10줄의 x 자리에 d를 넣으면 정확히 9줄이 됩니다.

맞습니다. 앞의 1~10줄에 다음 11~15줄을 이어 붙이겠습니다. 이번에는 새 이름 e를 골라 S(e)를 가정합니다. e는 앞서 쓴 d와 구별되는 글자이지만, 두 이름이 서로 다른 사람을 뜻한다는 주장은 하지 않습니다.

14줄은 S(e)라는 임시 가정 안의 결과입니다. 15줄은 존재 전제 3과 그 하위 증명을 근거로, 임시 가정을 닫은 뒤 얻는 결과입니다. e는 존재문 3, 바깥의 전제들, 밖으로 가져오는 결론에 없습니다. 그래서 ‘그 대상을 e라고 잠시 불렀기 때문에만 생기는 정보’를 밖으로 내보내지 않았습니다.

이 전제들에서는 ∃x(S(x)∧E(x))도 얻을 수 있습니다. 11줄의 S(e)와 13줄의 E(e)는 같은 e에 관한 식입니다. 그 두 식을 묶어 존재문을 만들면 됩니다. 앞의 증명을 지우지 않고, 다른 결론을 얻는 가지를 따로 적어 봅시다.

그 두 존재문만으로는 같은 사람인지 알 수 없습니다. 아라만 S이고 보라만 E인 두 사람 세계에서는 각각의 존재문이 참이지만 ∃x(S(x)∧E(x))는 거짓입니다. 이번 증명에서는 두 조건 연결 덕분에 한 e에 대해 S와 E를 모두 얻었다는 차이가 있습니다.

이번에는 처음의 ①·②만 남긴 별도 추론을 살펴보겠습니다. 영역이 정확히 아라 한 명이고 S·V·E가 모두 거짓인 세계 B를 만듭니다. 전체 영역은 비어 있지 않습니다.

이 세계는 ①·②에서 ∃xE(x)로 가는 추론의 반모형입니다. 원래의 세 전제 추론에 대한 반모형으로 쓰면 안 됩니다. 세계 B에서는 원래의 ③이 거짓이기 때문입니다.

신청했지만 명단에 오르지 않은 사람입니다. 변환 과정을 한 줄씩 확인하면 반례가 갖추어야 할 조건이 분명해집니다. 여기서 ≡는 모든 관련 해석에서 같은 값을 갖는다는 동치 표시입니다.

안전한 동치 변환은 같은 내용을 다른 모양으로 나타냅니다. 예를 들어 아래 식은 ‘신청자가 한 명이라도 있으면 영역의 모든 사람이 명단에 있다’는 별도의 주장입니다. 이것을 전두형으로 바꾸어도 처음 세 전제에서 따라오게 되지는 않습니다.

여기부터는 별도의 가상 안내 사례입니다. 영역은 정확히 아라·보라·다온·라온 네 사람이고 서로 다릅니다. S는 신청자, H는 도우미, R(x,y)는 ‘x가 y에게 안내를 받았다’로 새로 약속합니다. 앞 사례의 V·E와 시각 기록은 가져오지 않습니다.

관계 R은 (아라, 다온), (보라, 라온) 두 쌍에서만 참입니다. 다른 모든 쌍에서는 거짓입니다. 따라서 모든 신청자는 도우미에게 안내를 받았지만, 두 신청자를 모두 안내한 공통 도우미는 없습니다.

‘적어도 한 명’이라고 말하면 정확합니다. ‘딱 한 명’이라고 읽히지 않도록 표현하세요. 처음 사례의 세계 A에서는 보라와 찬우 두 명이 명단에 있습니다. 그 세계에서도 전제 세 개와 존재 결론은 모두 참입니다.

두 이름이 서로 다른 사람을 가리킨다는 정보가 더 필요합니다. k가 아라의 다른 이름일 수 있습니다. a≠k, 곧 ¬(a=k)도 주어져야 그 두 이름을 서로 다른 두 증거로 셀 수 있습니다.

이제 새 가상 공방 기록입니다. 영역은 검토 대상인 사람 전체이며 비어 있지 않습니다. 모든 상태는 같은 날 오후 5시 기준입니다. T(x)는 ‘실습에 참여했다’, C(x)는 ‘확인을 받았다’, B(x)는 ‘배지를 받았다’입니다.

추가 전제 ∀x(C(x)→B(x))가 실제로 주어지는 별도 문제에서는 가능합니다. 원래 문제의 답을 맞추기 위해 이 전제를 몰래 보탤 수는 없습니다. 아래 표는 이 새 전제가 주어진 경우만 다룹니다. 원래 둘째 전제는 쓰지 않아도 되므로 표에서 생략하고, 필요한 세 전제를 새로 번호 매겼습니다.

좋습니다. 여기에 어디까지 말할 수 있는지도 덧붙여 보세요.

그 설명에는 타당성과 사실 확인의 구별이 들어 있습니다. 우리의 증명은 정한 뜻과 논리 체계 아래에서 전제들이 참이면 결론도 참임을 보입니다. 실제 신청 기록을 조사하거나 안내의 현실 이행을 확인하는 일까지 대신하지는 않습니다.

중급 논리학 스무 편은 여기서 마칩니다. 처음 모자 사례에서 ‘누구에게 어떤 성질이 있나요?’를 물었던 것처럼, 새로운 글을 만날 때도 뜻과 대상을 먼저 정해 보세요. 이어지는 결론에는 한 줄씩 근거를 붙이고, 의심되는 결론에는 전제를 지키는 반례를 찾아보면 됩니다. 아래 기록 칸에 직접 만든 사례와 아직 남은 질문을 남겨 보세요.