건전성 정리

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

공식화

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

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

증명

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

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

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

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$ 를 얻는다.

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

같이 보기

• 괴델의 완전성 정리

참고 문헌

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