건전성

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

논리학에서 건전성(영어: soundness)이란, 형식 체계 내에서 증명가능한 명제(즉 정리)가 의미론 상으로도 참이 되는 성질이다. 이는 논리학에서 완전성의 역개념이 된다.

건전성 정리(영어: soundness theorem)에 따르면 1차 논리 체계에서는 연역 계산이 항상 건전성을 가지며, 이 정리도 역시 완전성 정리의 역을 제공한다.

정의[편집]

구문론적 귀결 관계 와 의미론적 귀결 관계 를 포함하는 형식 체계가 있다 하자. 임의의 논리식들의 집합 G와 논리식 p에 대하여. 다음이 항상 성립하면 형식 체계가 건전(영어: sound)하다고 한다.[1]

  • 이면, 이다.

증명[편집]

건전성 정리(soundness theorem)에 따르면 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)