증명(Proof)

술어에 관련된 용어들

술어

• 정의
  • 유한한 개수의 변수(술어변수)를 가진 문장
• 특징
  • 술어변수(Predicate variables)에 특정값을 대입하면 명제가 됨
  • 술어기호 P로 나타낼 수 있음(예: P(x))

정의역(Domain)

• 변수 자리에 대입할 수 있는 술어변수의 집합
  → x의 집합

진리집합(Truth set)

• 정의
  • 어떤 술어 P(x)를 참으로 만드는 모든 원소들의 집합
• 표기: { x ∈ D | P(x) } → P의 진리집합
  • x: 변수
  • D: 정의역
  • P: 술어

한정화명제

한정화명제(Quantified Statements)

• 정의
  • P(x)의 x에 대해 적절한 한정(Quantifier)을 추가한 명제

전칭 한정화명제(Universal Quantified Statements)

• 정의
  • 어떤 술어 P(x)에 대해 어떤 정의역 D의 모든 변수 x가 참인 명제
    → 모든 x가 참인 명제
• 특징
  • 반례가 하나라도 나오면 전칭 한정화명제가 거짓이 됨
  • 정의역이 유한한 경우 전수조사법으로 증명 가능하다
  • 전칭 한정화명제 ⊂ 한정화명제 ⊂ 명제
• 표기
  • ∀x ∈ D, Q(x) → D에 속하는 모든 x에 대해서 Q(x)가 성립한다

존재 한정화명제(Existential Quantified Statements)

• 정의
  • 어떤 술어 P(x)에 대해 어떤 정의역 D의 x가 적어도 하나는 참인 명제
    → x가 하나라도 참이면 존재 한정화명제
• 특징
  • 반례가 있어도 상관없으나 모든 x에 대해 거짓이면 거짓임
• 표기
  • ∃x ∈ D such that Q(x) → D에 속하는 어떤 x에 대해서 Q(x)가 존재한다

전칭 조건명제(Universal Conditional statements)

• 정의
  • 어떤 정의역 D의 모든 변수 x가 P(x)이면, Q(x)와 성립하는 명제
    → 수학에서 중요
• 표기
  • ∀x ∈ D, if P(x) then Q(x)

증명(Proof)

존재명제(∃x ∈ D such that Q(x))의 증명

• 구성적 증명(Constructive Proof of Existence) → a.k.a 노가다
  • Q(x)를 참으로 만드는 x를 직접 찾는 증명
  • 또는 x를 찾는 일련의 방법을 제시하는 증명
• 비구성적 증명(Non-constructive Proof of Existence) → a.k.a 논리
  • Q(x)를 참으로 만드는 x가 존재함을 이미 증명된 방법으로 보장됨을 보이는 증명
  • 또는 존재명제가 거짓이라는 가정이 모순이 됨을 보이는 방법

전칭명제(∀x ∈ D, if P(x) then Q(x))의 증명

• 반증(Disproof)
  • 가정 Q(x)가 참이고 결론 Q(x)가 거짓임을 찾는 방법
  • 그 부정이 참임을 보이는 방법으로 거짓인 값 x를 반례(counterexample)이라 한다
    → 참이 아닌 증거를 하나라도 찾으면 거짓
• 전수조사법(a.k.a 노가다)
  • 정의역 D의 모든 x를 일일이 조사함으로써 증명하는 방법
  • D가 유한하거나 조건 P(x)를 만족시키는 경우가 유한한 경우에 사용
    → A to Z 일일이 대입해서 참임을 증명
• 직접증명법(Direct Proof)
  • 특정적이지만 임의로 선택된 x로 P(x)가 참이됨을 증명하고 그 x가 `Q(x)를 만족시킴을 보이는 방법
• 간접증명법(Indirect Proof)
  • 모순에 의한 증명(Proof by contradiction)
    • 어떤 명제가 참 또는 거짓일 수 있지만 둘 다 될 수는 없다는 사실에 근거한 증명
      → 모두 뚫을 수 있는 창, 절대 뚫을 수 없는 방패 → 모순(있을 수 없음)
  • 대우에 의한 증명(Proof by contraposition)
    • 명제와 대우는 논리적 동치라는 사실에 근거한 증명