8.6 형성 규칙과 적형식

8.6 형성 규칙과 적형식

1. 절의 학술적 목표

본 절은 명제 논리의 형성 규칙(formation rules)과 적형식(well-formed formula)의 개념을 학술적으로 검토하는 것을 목표로 한다. 형성 규칙은 알파벳의 기호들로부터 문법적으로 올바른 표현을 구성하는 규칙이며, 적형식은 이 규칙에 의하여 생성된 표현이다. 본 절은 형성 규칙의 구조, 적형식의 정의, 귀납적 구성 방법을 체계적으로 정리한다.

2. 형성 규칙의 개념

형성 규칙은 형식 언어에서 문법적으로 올바른 표현을 구성하는 명시적 규칙이다. 알파벳만으로는 어떤 기호 열이 언어의 표현인지 결정되지 않으며, 형성 규칙과 결합해야 형식 언어의 구문론이 완성된다. 형성 규칙은 일반적으로 귀납적(inductive) 방식으로 정의되어 무한히 많은 적형식을 체계적으로 생성할 수 있다(Enderton, 2001).

3. 적형식의 정의

적형식은 형성 규칙에 의하여 생성될 수 있는 표현이다. 문법적으로 올바르지 않은 기호 열(예: “P ∧”, “)Q(” 등)은 적형식이 아니며, 명제 논리의 형식적 분석의 대상이 되지 않는다. 적형식은 명제 논리 형식 언어의 문장(sentence) 또는 공식(formula)으로 불리며, 명제를 형식적으로 표현한다(Mendelson, 2015).

4. 명제 논리 적형식의 귀납적 정의

명제 논리 적형식은 다음과 같이 귀납적으로 정의된다. 첫째, 임의의 명제 변항은 적형식이다(기저 단계). 둘째, A가 적형식이면 ¬A도 적형식이다(재귀 단계 1). 셋째, A와 B가 적형식이면 (A ∧ B), (A ∨ B), (A → B), (A ↔ B)도 적형식이다(재귀 단계 2). 넷째, 위의 규칙을 유한 번 적용하여 얻어진 것만이 적형식이다(폐쇄 단계)(Enderton, 2001).

5. 기저 단계와 재귀 단계

적형식의 귀납적 정의는 기저 단계(base case)와 재귀 단계(recursive case)로 구성된다. 기저 단계는 가장 단순한 적형식(원자 공식)을 규정하고, 재귀 단계는 이미 생성된 적형식들로부터 더 복잡한 적형식을 구성하는 방법을 규정한다. 이러한 구조는 수학적 귀납법(mathematical induction)과 유사하며, 무한히 많은 적형식을 유한한 규칙으로 생성할 수 있게 한다(Enderton, 2001).

6. 원자 공식과 복합 공식

적형식은 원자 공식(atomic formula)과 복합 공식(compound formula)으로 구분된다. 원자 공식은 단일 명제 변항으로 이루어진 적형식이며, 기저 단계에서 생성된다. 복합 공식은 원자 공식으로부터 재귀 단계를 통하여 구성된 적형식이다. 이 구분은 형식 언어의 표현을 분석하는 기본 틀을 제공한다(Mendelson, 2015).

7. 형성 규칙의 형식적 표기

형성 규칙은 종종 배커스-나우어 형식(Backus-Naur Form, BNF)으로 표기된다. 예를 들어 명제 논리 적형식의 BNF 정의는 다음과 같다. “φ ::= P \vert ¬φ \vert (φ ∧ φ) \vert (φ ∨ φ) \vert (φ → φ) \vert (φ ↔ φ)”. 여기서 “φ“는 적형식을 나타내는 메타 변항이고, “P“는 명제 변항을 나타낸다. 이러한 표기는 형식 언어의 문법을 간결하게 표현한다(Backus, 1959).

8. 구문 분석과 공식의 구조

적형식은 구문 분석 나무(parse tree)를 통하여 구조적으로 분석될 수 있다. 구문 분석 나무는 복합 공식이 어떻게 원자 공식과 연결사로부터 구성되었는지를 시각적으로 표현한다. 이러한 분석은 공식의 주 연결사, 부분 공식, 구성 역사 등을 명확히 하며, 형식적 증명과 의미론적 분석에 활용된다(Mendelson, 2015).

9. 적형식의 유일 가독성

적형식의 중요한 성질 중 하나는 유일 가독성(unique readability)이다. 이는 적형식이 한 가지 방식으로만 구문 분석될 수 있다는 성질이다. 즉, 임의의 적형식은 주 연결사와 부분 공식의 분해가 유일하게 결정된다. 유일 가독성은 괄호의 체계적 사용과 형성 규칙의 정밀성에 의하여 보장되며, 명제 논리의 형식적 분석의 기본 전제이다(Enderton, 2001).

10. 비적형식의 예시

적형식이 아닌 기호 열의 예로는 “P ∧”, “∨Q”, “(P → Q”, “P Q” 등이 있다. 이러한 표현들은 형성 규칙을 만족하지 않으며, 명제 논리의 형식 언어의 구성원이 아니다. 비적형식은 논리적 분석의 대상이 되지 않으며, 형식적으로 의미를 가지지 않는다(Mendelson, 2015).

11. 형성 규칙과 형식 체계

형성 규칙은 형식 체계(formal system)의 구성 요소 중 구문론적 부분을 담당한다. 형식 체계는 일반적으로 알파벳, 형성 규칙, 공리, 추론 규칙의 네 구성 요소로 이루어진다. 형성 규칙은 언어의 문법을 정의하고, 공리와 추론 규칙은 증명의 구조를 정의한다. 이 네 요소의 명확한 구분은 형식 체계의 엄밀성을 확보한다(Enderton, 2001).

12. 본 절의 결론적 정리

형성 규칙은 명제 논리 알파벳의 기호들로부터 문법적으로 올바른 표현을 구성하는 규칙이며, 적형식은 이 규칙에 의하여 생성되는 표현이다. 적형식의 귀납적 정의는 기저 단계와 재귀 단계로 구성되며, 유한한 규칙으로 무한히 많은 공식을 생성할 수 있게 한다. 적형식은 유일 가독성의 성질을 가지며, 구문 분석 나무를 통하여 구조적으로 분석된다. 학습자는 형성 규칙과 적형식의 개념을 정확히 이해하고, 이후의 구문론적·의미론적 분석을 위한 기반을 마련하여야 한다.

13. 출처

  • Backus, J. W. (1959). The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference. Proceedings of the International Conference on Information Processing, 125–131.
  • Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). San Diego: Academic Press.
  • Mendelson, E. (2015). Introduction to Mathematical Logic (6th ed.). Boca Raton: CRC Press.

14. 버전

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