크레이그의 보간 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

크레이그의 보간 정리(Craig's interpolation theorem, -補間 定理)는 증명 이론정리로, 미국철학자이자 논리학자윌리엄 크레이그가 제시하였다. 간단히 말해 다음과 같이 쓸 수 있다.

  • 어떤 논리식 a에서 다른 논리식 b를 추론할 수 있다고 하자. 그러면, c에서 나타나는 모든 비논리적 기호는 a와 b 각각에서도 나타나는 제3의 논리식 c가 존재하여 a에서 c를 추론할 수 있고, 다시 c에서 b를 추론할 수 있다. 이 c를 보간(interpolant)이라 한다.

크레이그는 1957년 이 정리를 일차 논리학에 대해 증명하였다. 미국 수학자 로저 린든이 일차 논리학에 대한 이 정리의 보다 강한 판본을 1959년 증명하였으므로 이 둘을 합쳐 크레이그-린든 정리라 부르기도 한다.

사례[편집]

명제 논리학에 대해 간단한 경우를 생각해 보자. 만약,

φ = ~(P ∧ Q) → (~R ∧ Q)
ψ = (T → P) ∨ (T → ~R).

라 한다면, φ는 ψ를 함의(동어반복적 함축)한다. 이는 φ를 논리곱 표준형으로 다음과 같이 쓰면 분명해진다.

φ ≡ (P ∨ ~R) ∧ Q.

그런데 사실 (P ∨ ~R)에서도 ψ를 함의하게 된다. (P ∨ ~R)에 나타나는 명제 변수는 a와 b 각각에서도 나타나므로 (P ∨ ~R)는 하나의 보간이 된다.

같이 보기[편집]

참고 문헌[편집]

  • John Harrison (2009). Handbook of Practical Logic and Automated Reasoning. Cambridge University Press. ISBN 0-521-89957-5.
  • Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
  • Dov M. Gabbay and Larisa Maksimova (2006). Interpolation and Definability: Modal and Intuitionistic Logics (Oxford Logic Guides). Oxford science publications, Clarendon Press. ISBN 978-0-19-851174-8.
  • Eva Hoogland, Definability and Interpolation. Model-theoretic investigations. PhD thesis, Amsterdam 2001.
  • W. Craig, Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory, The Journal of Symbolic Logic 22 (1957), no. 3, 269–285.