[이산 수학] 증명의 이해

증명의 이해

• 증명은 어떤 사실이 참(T)임을 보이는 것으로서 증명에 사용되는 모든 내용들이 타당해야만 정당한 증명이 된다.

 

증명(Proof)

하나의 명제가 참(T) 임을 확인하는 과정

• 증명의 과정에는 추론 방식이 적용된다.
  • 추론 : 참(T)으로 판별된 전제를 이용하여 결론이 참(T) 또는 거짓(F)임을 판별하는 과정
• 그러므로 증명 과정에서도 참(T)인 전제를 사용해야 하며, 이 전제를 이용하여 주어진 명제가 참(T)임을 보여야 한다.
• 증명에서 사용되는 전제로는 공리, 정의, 정리가 있다.

 

공리(Axiom)

별도의 증명 없이도 항상 참(T)이라고 판단하는 명제

• 다음 명제들은 공리의 대표적인 예이다.
  • 명제 `p` 가 참(T)이면, 명제 $p \lor q$ 도 참(T)이다.
  • 두 점이 주어질 때, 그 두 점을 통과하는 직선을 그을 수 있다.
  • $a, b, c ∈ \mathbb{R}$ 이고 `a = b` 이면, `a + c = b + c` 이다.
  • 임의의 자연수 `n` 에 대하여, 자연수 `n + 1` 이 존재한다.

 

정의(Definition)

개념이나 기호의 의미를 확실하게 규정한 문장이나 식

• 다음 명제는 정의의 예이다.
  • 한 내각의 크기가 직각인 삼각형을 직각 삼각형이라고 한다.
  • 명제는 객관적인 기준으로 진릿값을 판별할 수 있는 문장이나 수식이다.
  • $\displaystyle \sum_{i=1}^{n} = 1 + 2 + 3 + \cdots + (n - 1) + n$
  • $n! = 1 × 2 × 3 × \cdots × (n - 1) × n$

 

정리(Theorem)

공리와 정의를 통해 참(T)으로 확인된 명제

• 다음 명제는 정리의 예이다.
  • 피타고라스의 정리 : 직각 삼각형에 대하여, (빗변의 길이)² = (밑변의 길이)² + (높이의 길이)² 이 성립한다.
  • 이항 정리 : $(a + b)^{n} = \; _{n}C_{0}a^{n}b^{0} + \; _{n}C_{1}a^{(n-1)}b^{1} + \cdots + \; _{n}C_{k}a^{(n-k)}b^{k} + \cdots + \; _{n}C_{n-1}a^{1}b^{(n-1)} + \; _{n}C_{n}a^{0}b^{n}$
  • 나머지 정리 : `x` 에 대한 다항식을 일차 다항식 `x - a` 로 나눈 나머지는 그 다항식에 `a` 를 대입하여 얻은 값과 같다.

 

• 공리, 정의, 정리를 이용하여 어떤 사실을 증명할 수 있다.
• 명제의 형태에 따라 증명 방법이 달라지며, 증명 방법의 종류는 다음과 같다.
  • 직접 증명법 : 명제의 조건을 그대로 이용하여 증명이 가능한 경우
  • 간접 증명법 : 직접 증명법을 이용해 증명하기 애매한 경우
    • 모순 증명법 : 주어진 명제의 결론을 모순 형태로 만들어 증명이 가능한 경우
    • 대우 증명법 : 명제를 대우 명제로 바꾼 후에 증명이 가능한 경우
    • 존재/반례 증명법 : 어떤 식이나 문장에 대하여 참(T) 또는 거짓(F)이 되는 값이나 원소의 존재 유무로 증명이 가능한 경우
  • 수학적 귀납법 : 어떤 식이나 문장이 특정 범위의 모든 값이나 원소에 대하여 만족하는지를 증명해야 하는 경우