건전성 정리

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

건전성 정리(soundness theorem, 健全性定理)는 일차 논리학에서 연역 계산이 건전성을 가진다는 내용의 정리이다. 여기서 건전성이란, '모든 참인 것으로 증명가능한 명제(즉 정리)가 의미론상으로도 참임'을 의미한다. 이 정리는 괴델의 완전성 정리의 역을 제공한다.

공식화[편집]

어떤 논리식들의 집합 G와 논리식 p에 대하여, 이 정리는 다음과 같이 표현할 수 있다.[1]

  • 이면, 이다.

증명[편집]

이 정리의 증명은 다음과 같은 '타당성 보조정리'를 가정하면 쉽게 얻을 수 있다.[1] 사실 이 정리의 증명에서 문제가 되는 것은 타당성 보조정리의 증명인데, 이 보조정리는 의미상으로는 명백해 보이지만 그 증명은 비교적 길고 복잡하므로 여기서는 이를 받아들이고 건전성 정리의 증명만을 다루도록 한다.

  • (타당성 보조정리) 모든 논리적 공리는 타당하다.

증명은 세 부분으로 나누어 할 수 있다.

  1. p가 논리적 공리일 경우 위의 보조정리와 타당성의 정의에 의해 곧바로 을 얻는다.
  2. p가 G의 원소인 경우에도 곧바로 을 얻는다.
  3. 어떤 논리식 q가 존재해서 전건긍정식에 의해 일 경우, 귀납법에 의해 이고 라 할 수 있다. 이로부터 를 얻는다.

따라서, 모든 경우에 대해 위 정리는 성립한다.

같이 보기[편집]

각주[편집]

  1. Herbert B. Enderton (2002), A mathematical introduction to logic, Academic Press(Elsevier), p.131.

참고 문헌[편집]

  • Herbert B. Enderton (2002), A mathematical introduction to logic, Academic Press(Elsevier)