증명과 반례

무엇을 보이려는가?

증명은 전제에서 결론까지의 연결을 공개하는 과정입니다

연역 증명에서는 전제를 출발점으로 두고, 이미 인정한 규칙을 사용해 한 단계씩 새로운 문장을 얻습니다. 마지막에 목표 결론에 도달하면 그 결론이 전제에서 어떻게 따라오는지 확인할 수 있습니다.

한 줄에서 다음 줄로 넘어가는 허용 규칙

추론 규칙은 증명의 이동 규칙입니다

증명에서는 원하는 결론을 마음대로 적지 않습니다. 앞에서 확보한 문장과 허용된 규칙을 사용해 다음 문장을 얻습니다. 입문에서 자주 쓰는 규칙 몇 가지를 먼저 봅니다.

규칙의 이름을 모두 외우는 것보다 “이 줄이 앞의 어느 정보에서 나왔는가?”를 확인하는 습관이 먼저입니다.

전제에서 필요한 문장을 차례로 꺼내기

직접 증명은 목표를 향해 규칙을 연속해서 적용합니다

P → Q 자체를 증명하고 싶다면

P를 잠시 가정하고 Q까지 갈 수 있음을 보입니다

조건문 P → Q를 증명할 때는 P가 성립한다고 임시로 가정한 뒤, 그 가정과 기존 전제들에서 Q를 이끌어 냅니다. 그러면 가정을 닫고 P → Q를 얻습니다.

여기서 P를 사실이라고 영구히 선언한 것이 아닙니다. “P라고 두었을 때 Q까지 갈 수 있다”는 조건 관계를 보인 것입니다.

가능한 갈래를 모두 확인하기

각 경우에서 같은 결론이 나오면 전체 결론을 얻을 수 있습니다

목표의 반대를 가정해 모순을 만들기

가정이 모순으로 이어지면 그 가정을 버립니다

귀류법은 증명하려는 결론의 부정을 잠시 가정합니다. 그 가정에서 R과 ¬R처럼 함께 참일 수 없는 결과가 나오면, 처음 가정한 부정이 성립할 수 없음을 보입니다.

증명할 수 없는 추론을 한 사례로 깨뜨리기

반례는 전제는 모두 참인데 결론은 거짓인 경우입니다

언제 증명하고, 언제 반례를 찾을까?

보편적 주장은 증명으로 세우고, 거짓임은 반례 하나로 무너뜨릴 수 있습니다