[CS 1-2 | 이산수학] 증명 5주차

728x90

증명관련 용어 정리

이전에 증명된 사실로, 증명 과정에서 새로운 진술의 진리값을 추론할 때 사용한다.

"가설이 증명되면, 그 가설을 정리라 한다."

수학적 정리들의 경우 전칭 기호를 생략하고 표현하는 경우가 많다.
정리는 다음과 같이 단계를 거쳐 증명한다.
- 대상 영역의 일반적 원소를 선택
- 이 원소가 문제의 성질을 갖는지 확인한다.
- 전칭 일반화를 적용하여 모든 원소에 대해 성립함을 보여준다.
  "정의역에 포함한 모든 a에 대해 P(a)는 참이면, ∀xP(x)는 참이다."

정리의 전제로부터 결론에 도달하는 방식
- 전제들로부터 시작하여 일련의 연역 과정을 거쳐 최종적으로 결론에 이른다.
  연역 과정이란, 가설을 설정하고 법칙을 도출하는 과정에서 귀납적인 과정
예를 들어 조건문 p -> q에 대해 직접 증명한다면
- 만약 p가 참이라면 q가 참일 수 밖에 없음을 보인다.
  
  p가 참이면서 동시에 q가 거짓인 경우는 절대 없다. (조건문의 진리표)
  p -> q는 참인 경우만 존재한다.
p가 참이라고 가정하고 추론 규칙들을 적용해 q가 참임을 보인다.
증명 과정에서 p가 참이라고 가정하는 공리와 정의들, 그 전에 증명된 증명들, 추론 규칙 등이 사용된다.

직접 증명은 주어진 전제로부터 일정한 증명 과정을 거쳐 최종적으로 결론에 이르는 증명이다.

# 직접 증명 예제

전제로부터 결론을 직접 도출하지 않은 형태의 증명을 간접 증명이라 한다.
- 대우에 의한 증명은 간접 증명 기법 중 하나이다.
대우에 의한 증명은 문장 p -> q가 문장 ¬q -> ¬p와 동치라는 사실을 이용한다.
- p -> q 대신 ¬q -> ¬p가 참임을 보인다.
- 가정은 p대신 ¬q를 취한다.
- 공리, 정의, 이전에 증명된 정리, 추론 규칙 등을 사용하여 ¬p가 참임을 보인다.

문장 p -> q에 대해 참임을 증명할 때, p에 대한 진리값은 없고, ¬q에 대한 참인 진리값이 존재할 때,
대우에 대한 증명을 사용해 p -> q가 참임을 증명한다. (논리적 동치 성질을 활용한 증명법)

# 대우에 의한 증명 예제

조건문 p -> q에 대해 증명할 때
- p가 거짓이라면 해당 조건문이 참임을 쉽게 알 수 있다.
- 즉, p가 거짓임을 보일 수 있다면, 조건문 p -> q가 참임을 즉시 증명할 수 있다.
- 이것을 공허한 증명이라고 한다.

주어진 전제로부터 별다른 추론 과정없이, 증명의 결과가 즉시 나오는 증명을 공허한 증명이라고 한다.

조건문 p -> q에 대해 증명할 때
- q가 참이라면 해당 조건문이 참임을 쉽게 알 수 있다.
- 즉, q가 참임을 보일 수 있다면, 조건문 p -> q가 참임을 증명할 수 있다.
- 이것을 자명한 증명이라고 한다.

p가 참이라는 것을 증명하고 싶다면
- ¬p -> q를 참으로 만드는 모순 q를 구했다고 가정한다.
- "q가 모순이다"는 "q는 항상 거짓이다."라는 의미한다.
- q는 거짓이고 ¬p -> q는 참이라면 ¬p는 거짓이 되므로, p는 참이 된다.
- 여기서 핵심은 "모순인 q를 어떻게 구할 것인가"이다.

주어진 전제로부터 결론을 증명하기 어려운 경우,
반례 증명을 통해 하나의 사례를 찾아서 증명을 할 수가 있다.
대체로 전칭한정 기호가 사용된 문장에서 반례 증명을 쓴다.

주어진 전제로부터 증명을 수행할 때, 수학적 규칙을 고려하지 않고 전개한 증명은 잘못된 증명이다.
a - b = 0 이 참이라고 주어졌을 때 a - b로 나누는 전략은 잘못된 증명이다.
논점 회피 오류
- 증명의 과정에서 증명하려는 진술이 참이라는 것에 근거한다.
- 어떤 진술이 그 자체를 사용하거나, 그 자체와 동치임을 보임으로써 증명하고자 할 때 발생한다.
- 순환 추론이라고도 한다.

정리해서, 잘못된 증명은
수학적 규칙을 고려하지 않고 전개된 전략이거나,
추론된 진술을 토대로 별다른 증명없이 동치라고 생각할 때 잘못된 증명이 발생한다.

728x90