경우를 나누거나 모순을 찾아 어떻게 증명하나요?

그럴 때에는 경우를 나누어 볼 수 있습니다. p인 경우에도 원하는 결론이 나오고, q인 경우에도 같은 결론이 나온다면 어느 쪽인지 몰라도 결론을 얻을 수 있습니다. 다만 실제 전제가 그 경우들을 빠짐없이 덮어 주어야 합니다.

그때에는 모순을 이용하는 증명을 살펴볼 수 있습니다. 막연히 이상하다고 말하는 데서 끝내지 않고, 같은 내용과 그 부정이 어떻게 함께 나왔는지 보여야 합니다. 두 방법 모두 지난 편의 가정 범위를 정확히 사용합니다.

이 규칙을 선언 제거라고 합니다. 여기서 선언은 ∨로 묶은 식을 뜻합니다. 오늘은 뜻이 잘 드러나도록 “경우 나누기”라고도 부르겠습니다. 8줄에는 첫째 전제와 두 가정 구간 전체가 필요합니다.

맞습니다. 원래 전제 세 개가 모두 참이면 적어도 한 갈래가 적용되고, 어느 갈래를 적용하든 r이 참입니다. p와 q의 임시 가정은 모두 닫았지만 원래 전제에 대한 의존은 남아 있습니다.

p인 경우를 검토할 때 q가 거짓이라고 덧붙이지 않았다면, 둘 다 참인 경우도 이미 포함됩니다. q인 경우에도 마찬가지입니다. 경우들이 서로 겹칠 수 있어도, 빠진 경우가 없고 각 경우에서 같은 결론을 얻으면 됩니다.

그렇습니다. 원래 말에 없는 “오직”을 보태면 검토 범위가 달라집니다. 사례를 말로 읽을 때도 “연필이 있는 경우”라고 하고, 근거 없이 “연필만 있는 경우”로 바꾸지 않습니다.

맞습니다. p=거짓, q=참, r=거짓을 넣어 보세요. p∨q는 참이고 p→r도 참입니다. 하지만 결론 r은 거짓입니다. 처리하지 않은 경우가 실제 반례를 허용합니다.

새 논증에서는 가능합니다. 그러나 그것은 원래 두 전제만으로 증명한 결과가 아닙니다. 조건을 추가했다는 점을 분명하게 밝혀야 합니다. 추론이 막힌 자리에 원하는 근거를 조용히 끼워 넣지 마세요.

안 됩니다. 두 결과는 서로 다른 임시 가정 아래에서 얻었습니다. ∧로 묶으려면 지금 같은 구간에서 두 결과를 모두 사용할 수 있어야 합니다. p 가정을 닫고 q 경우로 넘어간 뒤에는 닫힌 p를 가져다 쓸 수 없습니다.

p=참, q=거짓을 넣으면 p∨q는 참이고 p∧q는 거짓입니다. 어느 경우든 하나가 있다는 근거를 둘 다 있다는 근거로 바꾸어 버린 것이지요.

좋습니다. ∨로 넓혀 적을 때에는 다른 쪽도 참이라고 주장하지 않습니다. r만으로 r∨s가 참이고, s만으로도 같은 r∨s가 참입니다. 두 구간이 같은 목표에 도달했으므로 경우 나누기를 마칠 수 있습니다.

그렇지 않습니다. 여기서는 어떤 식과 그 식 전체의 부정을 같은 구간에서 얻었는지 확인합니다. 예를 들어 q와 ¬q가 함께 나오면 같은 상자의 같은 시점에 지우개가 있으면서 없다는 결과입니다. 고전 이값 논리에서는 둘 다 참일 수 없습니다.

그때에는 시점이 다릅니다. 서로 다른 내용을 같은 q로 쓰면 안 됩니다. 또 연필과 지우개가 함께 있는 p∧q는 그 자체로 모순이 아닙니다. 각 글자의 뜻과 부정의 범위를 먼저 확인해야 합니다.

이 방법을 부정 도입이라고 합니다. p를 원래 전제들과 함께 참으로 유지하려고 했더니 모순이 나왔습니다. 따라서 원래 전제들이 참인 경우에는 p가 참일 수 없으며 ¬p가 따라옵니다.

맞습니다. 그리고 6줄의 ¬p도 두 원래 전제에 기대고 있습니다. 두 전제의 실제 참이 확인되어야 실제 상자에 연필이 없다는 판단까지 정당화할 수 있습니다.

원래 전제가 p→q와 p→¬q라고 해 보겠습니다. 두 전제에 q나 ¬q가 따로 적혀 있지는 않습니다. 그래도 ¬p를 얻을 수 있을까요?

좋습니다. 두 원래 전제 자체가 언제나 함께 불가능한 것은 아닙니다. p가 거짓이면 두 조건문은 모두 참일 수 있습니다. 그 전제들에 p까지 더했을 때 함께 참일 수 없다는 것을 증명한 것입니다.

6줄을 특히 보세요. 가정한 식이 ¬p였으므로 그것을 부정하면 ¬¬p가 됩니다. 이어서 고전논리의 이중 부정 제거로 p를 얻습니다. 목표의 부정을 가정해 모순을 보이고 목표를 얻는 방식을 귀류법이라고 부릅니다.

네. 이 편은 고전논리를 배우고 있으므로 이 단계를 사용합니다. 모든 논리 체계가 같은 방식의 귀류법이나 이중 부정 제거를 채택하는 것은 아닙니다. 여기서는 적용하는 규칙의 범위를 기억하면 됩니다.

목표가 p∧q라면 가정해야 하는 것은 ¬(p∧q)입니다. 드모르간 법칙으로 ¬p∨¬q와 동치입니다. 둘 다 있다는 주장이 틀리려면 둘 중 하나만 없어도 됩니다. ¬p∧¬q는 둘 다 없다는 더 강한 조건입니다.

맞습니다. p∧q를 증명하는데 ¬p∧¬q만 가정하면 p=참, q=거짓인 경우나 p=거짓, q=참인 경우를 놓칩니다. 목표 전체의 정확한 부정에서 시작해야 합니다.

그렇게 알 수는 없습니다. q와 ¬q는 같은 뜻·시점으로는 함께 참일 수 없습니다. 이 경우에는 p를 더하지 않아도 모순이 나옵니다. 원래 전제들을 모두 실제 사실로 받아들일 수 없는 상태입니다.

우리의 고전 증명 규칙은 모순된 원래 전제를 썼다는 이유만으로 형식적 추론을 금지하지는 않습니다. 그런 전제들에서는 p도 ¬p도 도출할 수 있습니다. 하지만 그것이 실제 상자에 연필이 있으면서 없다는 사실을 확인해 준 것은 아닙니다. 15편에서 배운 것처럼 건전한 논증의 근거가 되지 못합니다.

네. 추론이 올바르다면 함께 사용한 조건들이 모두 참일 수 없다는 것을 알 수 있습니다. 원래 전제들을 참으로 유지할 근거가 있어야 임시 가정을 실제 사실 판단에서 배제할 수 있습니다. 서로 충돌하는 관찰 기록이라면 대상·시점·기록 내용을 다시 확인해야 합니다.

아닙니다. 증명 방법을 아직 찾지 못한 것일 수 있습니다. 모순을 이용하려면 구체적으로 어떤 식과 그 부정이 나왔는지 보여야 합니다. “더 진행할 수 없었다”, “낯선 결과가 나왔다”, “예상과 달랐다”만으로는 충분하지 않습니다.

맞습니다. 앞서 사용한 줄의 근거와 가정 범위를 먼저 확인하고, 기호의 뜻이나 전제를 잘못 옮긴 곳은 없는지도 봅니다. “불가능하다”는 판단에는 그에 맞는 논리적 근거가 필요합니다.

마지막으로 경우 나누기 하나와 모순을 이용하는 증명 하나를 해 보겠습니다. 각 구간에서 원래 전제는 무엇이며, 어떤 가정을 닫는지 함께 말해 보세요.

좋습니다. 원래 근거를 유지한 채 각 구간을 바르게 마치고, 닫은 뒤 얻는 결론을 정확히 적는 것이 핵심입니다. 마지막 20편에서는 기호화·진리표·반례·증명을 한 문제에서 연결하며 기초 과정을 마무리하겠습니다.