건전성 정리

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

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

공식화[편집]

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

  • G \vdash p 이면, G \vDash p 이다.

증명[편집]

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

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

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

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

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

같이 보기[편집]

주석[편집]

  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)