11.6 연언 제거 규칙

11.6 연언 제거 규칙

1. 절의 학술적 목표

본 절은 자연 연역 체계의 연언 제거 규칙(conjunction elimination rule, ∧E)을 학술적으로 검토하는 것을 목표로 한다. 연언 제거 규칙은 연언 공식으로부터 그 성분 공식을 도출하는 추론 규칙이며, 연언 도입 규칙과 함께 연언의 의미를 완전히 정의한다. 본 절은 연언 제거 규칙의 정식화, 의미론적 정당화, 적용, 예시, 학술적 의의를 체계적으로 정리한다.

2. 연언 제거 규칙의 학술적 정의

연언 제거 규칙은 연언 공식 “A ∧ B“가 이미 증명되었을 때, 그 성분 공식 A 또는 B를 도출할 수 있음을 규정하는 규칙이다. 이 규칙은 연언 연결자 “∧“를 전제에서 제거하여 더 단순한 공식을 얻는 규칙이며, 연언의 분해 조건을 형식화한다. 형식적으로, 연언 제거 규칙은 전제 “A ∧ B“로부터 결론 A 또는 결론 B로의 이행을 허용한다(Gentzen, 1935).

3. 연언 제거 규칙의 두 형태

연언 제거 규칙은 두 형태를 가진다. 첫째 형태는 “A ∧ B“로부터 좌측 성분 A를 도출하는 규칙이고, 둘째 형태는 “A ∧ B“로부터 우측 성분 B를 도출하는 규칙이다. 두 형태는 각각 “∧E₁“과 “∧E₂“로 표기되거나, 단순히 “∧E“라는 이름으로 통합되기도 한다. 두 형태는 모두 타당하며, 연언의 양면적 분해를 형식화한다(Prawitz, 1965).

4. 연언 제거 규칙의 표준 표기

연언 제거 규칙의 표준 표기는 다음과 같다.

A ∧ B           A ∧ B
───── (∧E₁)     ───── (∧E₂)
  A               B

가로줄 위의 “A ∧ B“는 전제이고, 가로줄 아래의 A 또는 B는 결론이다. 이 표기는 겐첸의 자연 연역 체계의 표준 형식을 따른다(Gentzen, 1935).

5. 연언 제거 규칙의 의미론적 정당화

연언 제거 규칙은 연언의 진리 함수적 정의에 의하여 정당화된다. 연언 “A ∧ B“가 참이면 정의에 의하여 A가 참이고 B도 참이다. 따라서 “A ∧ B“가 증명되었다면 A를 도출할 수 있고 B도 도출할 수 있다. 이러한 정당화는 연언 제거 규칙이 타당한 추론 규칙임을 보장한다. 진리 보존의 관점에서, 전제가 참이면 결론도 반드시 참이다(Mendelson, 2015).

6. 연언 제거 규칙의 단순 적용 예시

연언 제거 규칙의 단순 적용 예시는 다음과 같다. 전제로 “P ∧ Q“가 주어졌을 때, 연언 제거 규칙을 적용하여 “P“와 “Q“를 각각 도출한다.

1. P ∧ Q      (전제)
2. P          (1, ∧E₁)
3. Q          (1, ∧E₂)

괄호 안의 “1, ∧E₁“은 결론이 1행에 첫째 형태의 연언 제거 규칙을 적용하여 얻어졌음을 의미한다(Copi, Cohen, & McMahon, 2014).

7. 연언 제거 규칙과 연언 도입 규칙의 조화

연언 제거 규칙과 연언 도입 규칙은 조화 원리에 의하여 서로 대응한다. 연언 도입 규칙은 A와 B로부터 “A ∧ B“를 구성하는 방법을 제공하고, 연언 제거 규칙은 “A ∧ B“로부터 A 또는 B를 추출하는 방법을 제공한다. 두 규칙의 결합은 연언의 의미를 완전히 정의한다. 특히, 도입 규칙 직후에 제거 규칙이 적용되면 원래의 공식으로 돌아가므로, 두 단계는 정상화 과정에서 제거될 수 있다(Prawitz, 1965).

8. 연언 제거 규칙의 복합 적용 예시

연언 제거 규칙의 복합 적용 예시는 다음과 같다. 전제로 “(P ∧ Q) ∧ R“이 주어졌을 때, 그로부터 Q를 도출하는 증명은 다음과 같다.

1. (P ∧ Q) ∧ R    (전제)
2. P ∧ Q          (1, ∧E₁)
3. Q              (2, ∧E₂)

이 증명은 연언 제거 규칙이 두 번 연속 적용되어 내부의 성분 공식을 추출하는 방법을 보여 준다(Mendelson, 2015).

9. 연언 제거 규칙과 연언 교환의 증명

연언 제거 규칙과 연언 도입 규칙을 결합하여 연언의 교환 법칙의 자연 연역 증명을 구성할 수 있다. 전제로 “P ∧ Q“가 주어졌을 때, “Q ∧ P“를 도출하는 증명은 다음과 같다.

1. P ∧ Q      (전제)
2. P          (1, ∧E₁)
3. Q          (1, ∧E₂)
4. Q ∧ P      (3, 2, ∧I)

이 증명은 연언 제거 규칙과 연언 도입 규칙의 결합으로 교환 법칙을 형식적으로 증명할 수 있음을 보여 준다(Copi, Cohen, & McMahon, 2014).

10. 연언 제거 규칙과 다른 규칙의 결합

연언 제거 규칙은 다른 추론 규칙과 결합되어 복잡한 증명을 구성할 수 있다. 예를 들어, 전제로 “P ∧ Q“와 “P → R“이 주어졌을 때, “R“을 도출하는 증명은 다음과 같다.

1. P ∧ Q      (전제)
2. P → R      (전제)
3. P          (1, ∧E₁)
4. R          (2, 3, →E)

이 증명은 연언 제거 규칙과 조건 제거 규칙(전건 긍정)의 결합을 보여 준다. 이러한 결합은 자연 연역 증명의 전형적인 패턴이다(Mendelson, 2015).

11. 연언 제거 규칙의 학술적 의의

연언 제거 규칙은 다음과 같은 학술적 의의를 가진다. 첫째, 그것은 연언 연결자의 분해 조건을 형식화하며, 연언 도입 규칙과 함께 연언의 의미를 완전히 정의한다. 둘째, 그것은 자연 연역 체계에서 가장 기본적이고 명확한 규칙 중 하나이다. 셋째, 그것은 조화 원리에 의하여 연언 도입 규칙과 대응하며, 정상화 정리의 환원 단계에서 중요한 역할을 한다. 넷째, 그것은 연언 공식으로부터 그 성분을 추출하는 기본 수단이며, 복잡한 증명의 진행에서 빈번히 사용된다(Gentzen, 1935).

12. 본 절의 결론적 정리

연언 제거 규칙은 연언 공식 “A ∧ B“로부터 그 성분 공식 A 또는 B를 도출할 수 있음을 규정하는 자연 연역 체계의 기본 규칙이다. 이 규칙은 두 형태(좌측 성분 도출, 우측 성분 도출)를 가지며, 연언의 진리 함수적 정의에 의하여 정당화된다. 연언 제거 규칙은 연언 도입 규칙과 조화 원리에 의하여 대응하며, 두 규칙이 함께 연언의 의미를 완전히 정의한다. 이 규칙은 다른 추론 규칙과 결합되어 복잡한 증명을 구성하는 데 활용되며, 교환 법칙과 같은 메타정리의 형식적 증명에도 사용된다. 학습자는 연언 제거 규칙의 정식화, 의미론적 정당화, 적용 방법을 정확히 이해하고, 자연 연역 증명에 활용할 수 있어야 한다.

13. 출처

  • Gentzen, G. (1935). Untersuchungen über das logische Schließen. Mathematische Zeitschrift, 39, 176–210, 405–431.
  • 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