by
Mar 29. 2020
논리 체계의 완전성과 건전성
연역 논리 마무리
시작하는 글에서 논리학을 이렇게 소개해드렸습니다.
올바른 논증과 올바르지 않은 논증을 구분해내는 법을 체계적으로 연구하는 학문
그리고 올바른 논증이란 전제들이 모두 참일 때 결론도 반드시 참이 되거나 적어도 결론이 참일 개연성이 높은 논증이라고 했었죠. 그 올바른 논증이 연역 논증이라면 결론은 반드시 참이 되어야 할 것이고, 귀납 논증이라면 결론이 참일 개연성이 높아야 할 것입니다.
연역 논증이 올바른지(=타당한지) 확인하기 위해 우리는 해석을 하기도 하고,
도출을 하기도 했죠.
의미론 vs. 구문론
해석은 의미론적 작업입니다. 언어적 표현에 지시체(=의미론적 값)을 할당하는 것이죠. 그리고 어떤 문장 집합 Γ에 속한 문장들이 모두 참인 해석 아래에서 문장 φ도 참일 때, φ가 Γ의 귀결이라고 혹은 Γ가 φ를 함축한다고 말합니다. 기호로는 Γ ⊨ φ라 쓰고요. 공집합으로부터 귀결되는(=공집합이 함축하는) 문장이 바로 항진 문장이죠. φ가 항진 문장임을 기호로 나타낼 땐 ⊨ φ라 씁니다.
반면 도출은 구문론적 작업으로서 일련의 규칙에 따라 어떤 문장 혹은 문장 집합으로부터 다른 문장을 이끌어내는 것이죠. 어떤 문장 집합 Γ에 추론 규칙을 적용하여 문장 φ을 얻어낼 수 있을 때, Γ로부터 φ를 도출할 수 있다고 말합니다. 기호로는 Γ ⊢ φ라 쓰고요. 그리고 이런 도출 과정을 보여주는 일이 증명입니다. 공집합으로부터 도출되는 문장을 정리라고 불렀었죠? φ가 정리라는 건 ⊢ φ와 같이 기호로 표시할 수 있습니다.
논리 체계의 완전성과 건전성
논리 체계가 완전complete하다는 건 그 논리 체계에서 임의의 문장 집합 Γ로부터 귀결되는 임의의 문장 φ가 또한 Γ로부터 도출될 수도 있다는 걸 의미합니다. (Γ⊨φ)→(Γ⊢φ)가 참이란 거죠.
반면 논리 체계가 건전sound하다는 건 그 논리 체계에서 임의의 문장 집합 Γ로부터 도출되는 임의의 문장 φ는 Γ의 귀결이기도 하다는 걸 의미해요. 이런 논리 체계에선 (Γ⊢φ)→(Γ⊨φ)가 참이죠.
명제 논리 체계와 정언 논리 체계, 그리고 술어 논리 체계만 공부한 상태에선 이런 생각이 드실 겁니다.
논리 체계가 불완전하거나 불건전할 수가 있나?
어떤 문장 집합이 함축하는 문장을 그 집합으로부터 도출하는 게 불가능한 경우가 있나? 어떤 문장 집합으로부터 도출할 수 있는 문장이 그 집합의 귀결이 아닐 가능성이 열려 있다고?
괴델 슨상님이 던지고 가신 그 불완전성 정리가 바로 그 불완전성에 관한 겁니다. 어떤 논리 체계에선 참이라는 건 알아도 증명할 수는 없는 문장이 존재한다는 거죠.