12.9 대우 증명법의 형식적 구조

12.9 대우 증명법의 형식적 구조

1. 절의 학술적 목표

본 절은 대우 증명법(proof by contraposition)의 형식적 구조를 학술적으로 검토하는 것을 목표로 한다. 대우 증명법은 자연 연역 체계 내에서 조건 도입 규칙, 부정 도입 규칙, 이중 부정 제거 규칙의 결합으로 형식화된다. 본 절은 대우 증명법의 형식적 정의, 자연 연역 체계에서의 도식, 대우 법칙의 형식적 증명, 증명 절차, 예시, 학술적 의의를 체계적으로 정리한다.

2. 대우 증명법의 형식적 정의

대우 증명법은 조건 명제 “A → B“를 증명하기 위하여 그 대우 “¬B → ¬A“를 자연 연역 체계 내에서 형식적으로 증명한 후, 대우 법칙 “(¬B → ¬A) → (A → B)“에 의하여 원래 명제를 결론으로 도출하는 증명 방법이다. 형식적으로 대우 증명법은 두 단계로 구성된다. 첫째, 대우 명제의 증명. 둘째, 대우 법칙의 적용으로 원래 명제의 도출. 이러한 형식적 구조는 대우 증명법이 자연 연역 체계의 기본 규칙들로부터 파생되는 증명 전략임을 보여 준다(Prawitz, 1965).

3. 대우 법칙의 형식적 증명

대우 법칙 “(A → B) → (¬B → ¬A)“의 자연 연역 증명은 다음과 같다.

1. [A → B]            (가정)
2. [¬B]               (가정)
3. [A]                (가정)
4. B                  (1, 3, →E)
5. ⊥                  (4, 2, ¬E)
6. ¬A                 (3-5, ¬I)
7. ¬B → ¬A            (2-6, →I)
8. (A → B) → (¬B → ¬A) (1-7, →I)

이 증명은 세 개의 중첩된 가정(“A → B”, “¬B”, A)과 조건 제거 규칙, 부정 제거 규칙, 부정 도입 규칙, 조건 도입 규칙의 결합으로 이루어진다. 이 증명은 대우 법칙이 자연 연역 체계에서 형식적으로 증명 가능한 정리임을 보여 준다(Copi, Cohen, & McMahon, 2014).

4. 역방향 대우 법칙의 형식적 증명

역방향 대우 법칙 “(¬B → ¬A) → (A → B)“의 자연 연역 증명은 이중 부정 제거 규칙을 필요로 한다. 증명은 다음과 같다.

1. [¬B → ¬A]          (가정)
2. [A]                (가정)
3. [¬B]               (가정)
4. ¬A                 (1, 3, →E)
5. ⊥                  (2, 4, ¬E)
6. ¬¬B                (3-5, ¬I)
7. B                  (6, ¬¬E)
8. A → B              (2-7, →I)
9. (¬B → ¬A) → (A → B) (1-8, →I)

이 증명은 “¬B → ¬A“와 A의 가정으로부터 B를 도출하는 과정에서 이중 부정 제거 규칙을 본질적으로 사용한다. 이러한 사용은 역방향 대우 법칙이 고전 논리에서만 성립하며, 직관주의 논리에서는 일반적으로 성립하지 않음을 보여 준다(Heyting, 1956).

5. 대우 증명법의 자연 연역 도식

대우 증명법의 자연 연역 도식은 다음과 같이 요약된다.

[¬B]
 ⋮
¬A
───── (→I)
¬B → ¬A
───────── (대우 법칙)
 A → B

첫째, “¬B“를 가정하여 “¬A“를 도출한다. 둘째, 조건 도입 규칙으로 “¬B → ¬A“를 얻는다. 셋째, 대우 법칙의 적용으로 “A → B“를 결론으로 도출한다. 이 도식은 대우 증명법의 형식적 흐름을 명확히 보여 준다(Prawitz, 1965).

6. 대우 증명법의 단순 예시

대우 증명법의 단순 예시는 다음과 같다. 전제로 “P → Q“가 주어진 상황에서 “¬Q → ¬P“를 도출하는 증명(즉 대우 법칙의 한 방향)은 다음과 같다.

1. P → Q              (전제)
2. [¬Q]               (가정)
3. [P]                (가정)
4. Q                  (1, 3, →E)
5. ⊥                  (4, 2, ¬E)
6. ¬P                 (3-5, ¬I)
7. ¬Q → ¬P            (2-6, →I)

이 증명은 “¬Q“를 가정하여 “¬P“를 도출하는 과정을 형식화하며, 조건 제거 규칙, 부정 제거 규칙, 부정 도입 규칙, 조건 도입 규칙의 결합으로 이루어진다. 이 증명은 대우 증명법의 가장 단순한 형태를 보여 준다(Copi, Cohen, & McMahon, 2014).

7. 대우 증명법의 복합 예시

대우 증명법의 복합 예시는 전제 없이 “(P → Q) ↔ (¬Q → ¬P)“를 증명하는 것이다. 이 증명은 대우 법칙의 양방향을 쌍조건으로 결합한다.

1. [(P → Q)]                (가정)
2. ... (위의 제3절 증명)
3. ¬Q → ¬P                  (대우 법칙의 적용으로 도출)
4. (P → Q) → (¬Q → ¬P)      (1-3, →I)
5. [(¬Q → ¬P)]              (가정)
6. ... (위의 제4절 증명)
7. P → Q                    (이중 부정 제거 포함)
8. (¬Q → ¬P) → (P → Q)      (5-7, →I)
9. (P → Q) ↔ (¬Q → ¬P)      (4, 8, ↔I)

이 증명은 두 방향의 조건 증명을 결합하여 쌍조건을 구성하며, 대우 법칙의 완전한 동치성을 형식적으로 확립한다. 역방향은 이중 부정 제거를 사용하므로 고전 논리에서만 유효하다(Mendelson, 2015).

8. 대우 증명법의 절차적 구조

대우 증명법의 절차적 구조는 다음의 단계로 구성된다. 첫째, 증명 목표 “A → B“를 확인한다. 둘째, 대우 “¬B → ¬A“를 증명 목표로 대체한다. 셋째, “¬B“를 가정으로 도입한다. 넷째, 가정 “¬B“와 기존 전제로부터 “¬A“를 도출한다. 이 도출은 직접 증명 또는 약한 귀류법으로 이루어질 수 있다. 다섯째, 조건 도입 규칙으로 “¬B → ¬A“를 결론으로 얻는다. 여섯째, 대우 법칙의 동치성에 의하여 “A → B“가 증명되었다고 결론짓는다. 이러한 절차는 대우 증명법의 표준적 수행 방법이다(Copi, Cohen, & McMahon, 2014).

9. 대우 증명법과 조건 도입 규칙의 관계

대우 증명법은 조건 도입 규칙을 본질적으로 활용한다. 대우 “¬B → ¬A“의 증명은 “¬B“를 가정하여 “¬A“를 도출한 후 조건 도입 규칙으로 “¬B → ¬A“를 결론으로 얻는 절차이다. 이 절차는 조건 도입 규칙의 표준적 적용이며, 대우 증명법이 자연 연역 체계의 기본 규칙들로부터 자연스럽게 도출됨을 보여 준다. 조건 도입 규칙의 적용 시점에서 가정 “¬B“는 해소되며, 결론 “¬B → ¬A“는 더 이상 “¬B“에 의존하지 않는다(Prawitz, 1965).

10. 대우 증명법과 부정 도입 규칙의 관계

대우 증명법은 부정 도입 규칙과도 밀접하게 관련된다. 대우의 후건 “¬A“를 도출하는 과정에서 부정 도입 규칙이 자주 사용되며, 이는 약한 귀류법의 적용과 동일하다. 즉, 대우 증명법의 핵심 단계인 “¬A“의 도출이 부정 도입 규칙으로 이루어지는 경우가 많다. 이러한 관계는 대우 증명법과 귀류법이 자연 연역 체계에서 밀접하게 연관됨을 보여 주며, 두 증명 방법 사이의 구조적 유사성을 반영한다(Mendelson, 2015).

11. 대우 증명법의 형식적 구조의 학술적 의의

대우 증명법의 형식적 구조는 다음과 같은 학술적 의의를 가진다. 첫째, 그것은 대우 증명법이 자연 연역 체계의 기본 규칙들로부터 파생되는 증명 전략임을 명확히 한다. 둘째, 그것은 대우 법칙의 형식적 증명을 통하여 대우 증명법의 타당성을 보장한다. 셋째, 그것은 고전 논리와 직관주의 논리에서 대우 증명법의 유효 범위를 명확히 한다. 넷째, 그것은 조건 도입 규칙과 부정 도입 규칙의 결합으로 대우 증명법이 형식화되는 방식을 보여 준다. 다섯째, 그것은 증명 교육에서 대우 증명법의 체계적 이해를 가능하게 한다(Prawitz, 1965).

12. 본 절의 결론적 정리

대우 증명법의 형식적 구조는 자연 연역 체계 내에서 조건 도입 규칙, 부정 도입 규칙, (필요한 경우) 이중 부정 제거 규칙의 결합으로 형성된다. 대우 법칙 “(A → B) → (¬B → ¬A)“는 자연 연역 체계에서 형식적으로 증명 가능하며, 그 역방향 “(¬B → ¬A) → (A → B)“는 이중 부정 제거 규칙을 본질적으로 사용하여 고전 논리에서만 성립한다. 대우 증명법의 절차적 구조는 대우를 증명 목표로 대체하고, “¬B“를 가정하여 “¬A“를 도출한 후 조건 도입 규칙으로 “¬B → ¬A“를 얻고, 대우 법칙의 동치성에 의하여 원래 명제를 결론으로 도출하는 것이다. 대우 증명법은 조건 도입 규칙과 부정 도입 규칙과 밀접하게 관련되며, 자연 연역 체계의 기본 규칙들로부터 자연스럽게 도출된다. 학습자는 대우 증명법의 형식적 정의, 대우 법칙의 증명, 절차적 구조, 자연 연역 규칙과의 관계를 정확히 이해해야 한다.

13. 출처

  • Heyting, A. (1956). Intuitionism: An Introduction. Amsterdam: North-Holland.
  • Prawitz, D. (1965). Natural Deduction: A Proof-Theoretical Study. Stockholm: Almqvist & Wiksell.
  • Copi, I. M., Cohen, C., & McMahon, K. (2014). Introduction to Logic (14th ed.). London: Routledge.
  • Mendelson, E. (2015). Introduction to Mathematical Logic (6th ed.). Boca Raton: CRC Press.

14. 버전

  • 문서 버전: 1.0
  • 작성 기준일: 2026-04-15