맨위로가기

크레이그의 보간 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

크레이그의 보간 정리는 명제 논리에서 항진식인 함의에 대해 보간자가 존재한다는 정리이다. 함의 X → Y가 항진식일 때, X와 Y에 모두 나타나는 논리식 Z가 존재하여 X → Z와 Z → Y도 항진식이면 Z를 X → Y의 보간자라고 부른다. 린든의 보간 정리는 일차 논리 이론에 대한 크레이그의 보간 정리의 일반화된 형태이다. 크레이그의 보간 정리는 구성적 증명과 비구성적 증명 모두 가능하며, 일관성 증명, 모델 검사, 모듈 명세 언어에서의 증명, 모듈식 온톨로지 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

  • 증명 이론 - 힐베르트 프로그램
    힐베르트 프로그램은 20세기 초 수학의 기초를 형식 체계로 구축하고 무모순성과 완전성을 증명하려 했으나, 괴델의 불완전성 정리에 의해 원래 목표 달성이 불가능해졌고 수정된 형태로 연구가 지속되고 있다.
  • 증명 이론 - 괴델의 불완전성 정리
    괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
  • 수학기초론 정리 - 괴델의 불완전성 정리
    괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
  • 수학기초론 정리 - 칸토어의 정리
    칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2κ > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.
  • 보조정리 - 베주 항등식
    베주 항등식은 주 아이디얼 정역에서 두 원소의 최대공약수를 그 두 원소의 정수 배의 합으로 나타낼 수 있다는 정리이며, 확장 유클리드 알고리즘을 통해 베주 계수를 구할 수 있고, 정수, 다항식 등 다양한 대수적 구조로 확장 가능하다.
  • 보조정리 - 모스 이론
    모스 이론은 미분다양체 위의 함수의 임계점과 지표를 이용하여 다양체의 위상수학적 성질을 연구하는 이론으로, 함수값에 따른 부분공간 변화를 관찰하여 다양체의 호몰로지를 계산하고 위상수학적 성질을 밝히는 데 응용된다.
크레이그의 보간 정리
크레이그 보간 정리
유형논리적 정리
분야수리논리학
이름의 유래윌리엄 크레이그
설명
내용만약 논리식 A ⊢ B가 유효하다면, A ⊢ C와 C ⊢ B를 만족하는 논리식 C가 존재한다. 여기서 C는 A와 B 모두에 나타나는 기호만을 사용한다.
CC를 A와 B 사이의 보간식이라고 한다.

2. 명제 논리에서의 보간 정리

명제 논리에서 크레이그의 보간 정리는 다음과 같이 정의된다.

:X \rightarrow Y

가 항진식일 때, 논리식 Z의 모든 명제 변수가 X와 Y 모두에 나타나고,

:X \rightarrow Z

와

:Z \rightarrow Y

도 항진식이라면, Z를

:X \rightarrow Y

의 "보간(interpolant)"이라고 부른다.

명제 논리에서 크레이그의 보간 정리에 따르면, 함의

:X \rightarrow Y

가 항진식이면 항상 보간이 존재한다.

2. 1. 예시

만약 φ = ~(P ∧ Q) → (~R ∧ Q)이고 ψ = (T → P) ∨ (T → ~R)이라면, φ는 ψ를 함의(동어반복적 함축)한다. 이는 φ를 논리곱 표준형으로 다음과 같이 쓰면 분명해진다.[1]

:φ ≡ (P ∨ ~R) ∧ Q.

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

명제 논리에서, 다음을 가정한다.[2]

::: \varphi = \lnot(P \land Q) \to (\lnot R \land Q)

::: \psi = (S \to P) \lor (S \to \lnot R) .

그러면 \varphi는 항진적으로 함의한다 \psi. 이는 \varphi를 결합 정규형으로 작성하여 확인할 수 있다.[2]

:::\varphi \equiv (P \lor \lnot R) \land Q.

따라서, \varphi가 참이면, P \lor \lnot R이 참이다. 다시 말해, P \lor \lnot R은 항진적으로 \psi를 함의한다. P \lor \lnot R에 나타나는 두 개의 명제 변수가 \varphi와 \psi 모두에 나타나기 때문에, 이는 P \lor \lnot R이 함의 \varphi \to \psi에 대한 보간자임을 의미한다.[2]

단순한 예로, 다음 식에 대해 P는 보간이다.[3]

:P \land R \rightarrow P \lor Q

3. 린든의 보간 정리

두 개의 일차 논리 이론을 각각 ''S''와 ''T''라고 하자. ''S'' ∪ ''T''는 ''S''와 ''T''를 모두 포함하는 가장 작은 이론을 나타낸다. ''S'' ∪ ''T''의 서명은 ''S''와 ''T''의 서명을 포함하는 가장 작은 서명이다. ''S'' ∩ ''T''는 두 이론 언어의 교집합이며, ''S'' ∩ ''T''의 서명은 두 언어 서명의 교집합이다.

린든의 정리는 ''S'' ∪ ''T''가 만족 불가능하면, ''S'' ∩ ''T''의 언어로 된 보간 문장 ρ가 존재하여, 모든 ''S''의 모델에서 참이고 모든 ''T''의 모델에서 거짓이라고 말한다. 또한, ρ는 다음과 같은 더 강력한 속성을 갖는다. ρ에서 긍정적 발생을 가진 모든 관계 기호는 ''S''의 어떤 공식에서 긍정적 발생을 가지며 ''T''의 어떤 공식에서 부정적 발생을 가진다. ρ에서 부정적 발생을 가진 모든 관계 기호는 ''S''의 어떤 공식에서 부정적 발생을 가지며 ''T''의 어떤 공식에서 긍정적 발생을 가진다.

4. 크레이그 보간 정리의 증명

크레이그 보간 정리는 구성적 증명과 비구성적 증명, 크게 두 가지 방법으로 증명할 수 있다.


  • 구성적 증명: 명제 논리, 기본 모달 논리 K, 직관 논리, μ-미적분 등에서 사용되는 증명 방법이다. 이 증명은 실제로 보간자를 계산하는 알고리즘을 제공한다.
  • 비구성적 증명: 모델 이론, 증명 이론, 추상 대수 논리 등에서 사용되는 증명 방법으로, 콤팩트성 정리, 로빈슨의 결합 일관성 정리, 컷 제거, 합병 속성 정리 등을 이용한다.

4. 1. 구성적 증명

명제 논리에 대한 크레이그 보간 정리의 구성적 증명은 다음과 같다.[3]

위 증명은 직관 논리에서 구성적이므로, 보간자를 계산하기 위한 알고리즘을 추출할 수 있다. 만약 ''n'' = |''atoms''(φ') − ''atoms''(ψ)|이면, 보간자 ρ는 φ보다 ''O''(exp(''n'')) 더 많은 논리 연산자를 갖는다. (빅 오 표기법 참고)

4. 2. 비구성적 증명

크레이그 보간 정리는 다음과 같은 비구성적 방법으로도 증명할 수 있다.

  • 모델 이론적으로는, 콤팩트성 정리가 존재하고, 부정과 논리곱이 있는 상황에서 로빈슨의 결합 일관성 정리와 크레이그 보간 정리는 동치이다.
  • 증명 이론적으로는, 시퀀트 미적분을 통해 가능하다. 컷 제거가 가능하고 그 결과 부분 공식 속성이 성립하면, 크레이그 보간 정리는 유도에 대한 귀납법을 통해 증명할 수 있다.
  • 추상 대수 논리적으로는, 논리를 나타내는 대수학의 다양성에 대한 합병 속성 정리를 사용한다.
  • 크레이그 보간 정리를 갖는 다른 논리로의 번역을 통해 가능하다.

5. 응용

크레이그의 보간 정리는 일관성 증명, 모델 검사[4], 모듈 명세 언어에서의 증명, 모듈식 온톨로지 등 다양한 분야에 적용된다.

참조

[1] 논문 An interpolation theorem in the predicate calculus
[2] 서적 Basic Proof Theory Cambridge University Press
[3] 문서 Harrison pgs. 426–427
[4] 간행물 Boolean Satisfiability Solvers and Their Applications in Model Checking


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com