수리 논리학
mathematical logic
1. 개요
논리학을 수학의 기호 및 기법을 통하여 연구하는 논리학과 수학의 하위 학문 혹은 방법론. '''기호 논리학'''과 같은 의미로 쓰이거나 그 일부로 여겨진다. 수학에선 집합론과 더불어 '''수학 기초론'''을 이루는 중요한 부분 중 하나. 컴퓨터과학과 철학에서도 핵심적인 소양 중 하나로 여겨진다.[1]
일반적으로는 '''연역논리'''에 한정되며[2], 본 문서에서는 연역 논리, 그 중에서도 '''표준(standard)''' 혹은 '''고전(classical) 논리'''에 관한 내용만을 다룬다.
표준논리의 개념들은 대부분 일상 언어의 어휘들로부터 비롯된 것이다. 예를 들어 논리연산자 "∨"는 한국어 "혹은", 영어 "or"에서 비롯되었다. 그렇지만 논리학, 특히 표준 논리 개념들의 뜻은 그 '''본래 일상 언어 어휘의 쓰임새와 괴리가 있는 경우'''가 잦다. 명제 논리 문서의 선언문, 조건문, 양화 논리 문서의 개요 문단과 존재함축 문서 참조. 그러므로 일상 언어 문장을 논리식으로 번역하거나, 혹은 반대로 논리식을 일상언어로 이해할 때에는 주의를 요한다.
기호 논리학과 수리 논리학에서는 오직 형식적인 것만을 다루며, 그렇기 때문에 비형식적인 오류나 논리적 기이함(oddity)에 대해서는 다루지 않는다. 비형식적 오류에 대해서는 논리적 오류/비형식적 오류 항목을 참조하라.
2. 역사
논리학을 수학적 기호를 가지고 전개할 수 있다는 발상을 처음 제안한 것은 고트프리트 빌헬름 라이프니츠다. 이후 19세기에 조지 부울이 처음으로 진리치 수준에서 논리를 대수처럼 계산하는 체계를 제시하였고, 고틀로프 프레게와 찰스 샌더스 퍼스는 각각 독립적으로 개념 혹은 술어 수준에서 명제를 분석하는 양화 논리 체계를 개발했다.
프레게를 이어 버트런드 러셀과 알프레드 노스 화이트헤드는 모든 수학적 참을 논리학적 참으로 환원하는 논리주의 기획을 개진함으로써 당대 지성계에 큰 영향을 미쳤고, 이는 수학 전체에 대한 무모순적인 공리 체계를 마련하려는 다비트 힐베르트의 형식주의 기획에도 영향을 미쳤다.
하지만 쿠르트 괴델의 불완전성 정리로 인하여 논리주의 및 형식주의의 전통적 형태는 결정적인 위기에 봉착하였고, ZFC 공리계에 관해선 그 실제 사례로 연속체 가설이 있음을 괴델과 폴 코언이 성공적으로 보이는데 이르렀다. 이런 성과를 바탕으로 20세기 후반부터 본격적인 현대 수리 논리학이 발전하기 시작했다.
3. 예비사항
본격적인 수리 논리학 개념 소개에 앞서서 알아두면 좋을 몇몇 논리학적, 논리철학적, 언어철학적 사항들이 있다. 이런 사항들은 실제 논리학 문헌에서는 종종 편의상 슬쩍 넘어가고는 하지만, 논리학적 엄밀성을 위해선 반드시 준수되어야 한다. 사실상 '수학'의 탈을 쓴 국어과 과목(그 중에서도 작문)에 가깝기 때문에 국어과목에 자신이 없다면 상상 이상으로 혼란을 겪을 수 있다.
자세한 내용은 수리 논리학/예비사항 항목 참조.
4. 핵심 개념들
전통적으로 논리학은 '''"적법한 생각(혹은 추론)의 규칙은 무엇인가?"'''라는 문제에 답하고자 하는 학문으로 여겨졌다. 프레게 이후 이는 '''"무엇이 타당한 논증인가?"'''라는 질문으로 전환되었다.
일반적으로 수리 논리학에서 논증이란 특정한 문장 집합('''"전제"''')과 특정한 문장('''"결론"''')으로 구성된다.[3] 이런 무수한 논증들 가운데 오직 일부만이 적법한 논증, 즉 타당한(valid) 논증이다. 그리고 이때 '타당성'은 크게 두 가지 방식으로 정의된다.
4.1. 의미론적 방식
의미론적 방식에 따르면 타당한 논증이란 '''전제들이 모두 참인 경우 그 결론 또한 반드시 참인 논증'''이다. 전제들이 모두 참임에도 불구하고 결론이 거짓일 수 있는 논증은 '''부당한''' 논증이다. 특수한 유형들로 다음 예시가 있다:
- 전제가 항상 거짓인 경우 논증은 항상 타당하며, 결론이 항상 참인 경우 또한 논증은 항상 타당하다. 이와 같은 경우에 그 논증은 공허하게(vacantly) 타당하다.
- 전제들이 모두 참이며 논증이 타당한 경우, 그 논증은 건전하다(sound).
- 타당한 논증의 예시: "만약 소크라테스가 철학자라면, 소크라테스는 지혜를 사랑한다. 소크라테스는 철학자다. 따라서 소크라테스는 지혜를 사랑한다."
- 타당하지 않는 논증의 예시: "소크라테스는 철학자다. 고래는 포유류다. 따라서 손흥민은 축구선수다."
그리고 전제 집합 $$\Gamma$$이 공집합인 경우 그 논리적 귀결 $$\phi$$는 '''논리적 참'''이다.$$\Gamma \models \phi $$
$$ \models \phi $$
4.1.1. 모형(해석), 참
참과 거짓의 본성을 묻는 것은 형이상학의 세부 분과 중 하나인 진리론의 중요한 문제다. 다만 논리학 보다 구체적으로는 모형 이론(model theory)에서 문장의 진릿값은 편의상 '''모형''' 혹은 '''해석'''에 상대적으로 부여된다.
해석은 문장에 지시체를 할당하는 작업이다. 이를테면 명제 논리에서는 각각의 명제에 T 또는 F를 할당하는 것이, 양화 논리에서는 논의 영역과 개체상항을 명시하고 문장의 지시체를 결정해서, 궁극적으로 그 문장의 참 거짓을 판별하는 것이 해석이라고 할 수 있다. 이처럼 해석을 문장에 진릿값을 할당하는 작업으로 파악하면, 최소한 표면적으로는 참과 거짓이 도대체 무엇이냐고 하는 진리론적 논의 없이도 논리학적 문장들을 다룰 수 있게 된다.[5]예. 모형 M에서 김철수는 모든 학생들의 집합의 원소라고 하자.[4]
그렇다면 문장 "김철수는 학생이다"는 M에서 참이다.
그리고 이런 모형 이론적 개념을 취할 경우 논리적 귀결 관계는 다음과 같이 재정의될 수 있다
더불어 논리적 참은 임의의 모형에서 참인 문장으로 이해될 수 있다.$$ \Gamma \models \phi $$ iff#s-1 $$\Gamma $$의 모든 원소들이 참인 임의의 모형 M에서 $$ \phi $$도 참이다.
4.2. 구문론적 방식
전제나 결론의 진리치를 굳이 따지지 않고서도 논증의 타당성을 따져볼 수 있다. 이때 관건은 오직 주어진 추론규칙들에 의거하여 전제들로부터 결론이 '''도출가능'''한지 혹은 '''증명가능한지''' 여부다. 결론 $$\phi$$가 전제 집합 $$\Gamma$$들로부터 도출가능한 경우 이를 보통 다음과 같이 표현한다.
전제 집합 $$\Gamma$$와 '공리'라고 불리는 일련의 문장들로부터 주어진 추론규칙들을 유한번 적용해서 얻은 문장들의 열(sequence)을 '증명'이라고 부른다. 그리고 전제가 공집합일 때, 증명의 마지막 행에 놓이는 문장을 '정리'(Theorem)라고 부른다.$$\Gamma \vdash \phi $$
5. 명제 논리
명제 논리 문서 참조.
6. 양화 논리
양화 논리 문서 참조.
7. 메타 정리들
이하의 논리학적 정리들은 논리 체계 내부의 정리가 아니라, 논리 체계 그 자체에 대한 정리이기 때문에 메타 정리라고 불린다. 이 메타 정리들은 명제 논리와 1차 술어논리에서만 동시에 성립하며, 2차 이상의 논리 체계에서는 어떻게 하더라도 동시에 성립할 수 없다. 이 성질들이 동시에 성립하는 1차 술어논리는 가장 기초적인 논리 체계가 된다고 할 수 있으며, 따라서 지금까지도 수학의 기초로 활용되고 있다.
7.1. 논리 체계의 건전성, 완전성, 일관성
논리 체계의 건전성, 완전성, 일관성은 다음과 같이 간략하게 기술된다.
(1) 논리체계가 건전하다는 것은 문장집합 G로부터 문장 ϕ가 도출되면, 문장 ϕ가 문장집합 G의 귀결이라는 것이다.
(2) 논리체계가 완전하다는 것은 문장 ϕ가 문장집합 G의 귀결일 때, 문장집합 G로부터 문장 ϕ가 도출된다는 것이다.$$\Gamma \vdash \phi \Rightarrow \Gamma \models \phi$$
(3) 논리체계가 일관적이라는 것은 공집합으로부터 모순이 도출되지 않는다는 것이다. 이는 무모순성이라고도 표현한다.$$\Gamma \models \phi \Rightarrow \Gamma \vdash \phi$$
여기서, (1)과 (2)는 역의 관계에 있으며, 괴델의 완전성 정리에 따르면 명제 논리와 1차 술어논리 체계에서 건전성과 완전성은 동치이다. 명제 논리와 1차 술어논리 체계가 건전하며 동시에 완전하다는 것 역시 건전성 정리와 괴델의 완전성 정리를 통해 이미 증명되어 있다. 즉, 명제 논리와 1차 술어논리에서 모형이론적 진리와 증명이론적 진리는 서로 같다. 타당한 문장은 증명될 수 있고, 증명될 수 있는 문장은 타당하다.$$\emptyset \not\vdash \bot $$
또한 표준적인 명제 논리와 1차 술어논리의 체계는 일관적이다. 이 체계에서는 공집합으로부터 모순이 도출되지 않는다. 역시 괴델의 완전성 정리에 따라 1차 논리에서 일관성이 성립함이 증명되었다.$$\Gamma \models \phi \Leftrightarrow \Gamma \vdash \phi$$
7.2. 콤팩트성
콤팩트성은 쉽게 말하자면 어떤 집합이 '닫혀 있는' 성질이라고 할 수 있다. 1차 술어논리와 명제논리에서는 모든 문장 집합에 대해 콤팩트성이 성립하는데, 이 메타증명을 콤팩트성 정리라고 한다. 이를 보다 상세하게 정의하면 다음과 같다.
또한 콤팩트성 정리에 따르면 논리 체계의 일관성과 콤팩트성은 동치이다. 콤팩트성이 항상 성립하는 논리 체계는 일관적인 논리 체계이며, 일관적인 논리 체계에서는 콤팩트성이 항상 성립한다.임의의 문장 $$\phi$$가 임의의 문장 집합 $$\Gamma$$[6]
의 귀결일 때, $$\Delta \models \phi$$를 만족시키는 $$\Gamma$$의 어떤 유한 부분집합 $$\Delta$$가 존재한다.
7.3. 뢰벤하임-스콜렘 정리
뢰벤하임-스콜렘 정리 문서 참조.
7.4. 불완전성 정리
괴델은 임의의 논리 체계가 자연수 산술 체계를 포함할 수 있을 정도로 강력할 경우 그 논리 체계는 '''불완전'''하다는 것을 보였다. 불완전성 정리 문서 참조.
8. 교과 과목
수학과에서는 주로 집합론과 함께 전공과목으로 다루어지지만, 경우에 따라서는 학부에서는 다루지 않기도 한다. 철학과의 경우, 대체로 학부의 전공필수 과목으로 개설되지만 커리큘럼이 일정하지 않은 철학과의 특성 상 필수 과목이 아닌 경우도 있다. 컴퓨터공학과에서는 학부의 경우 이산수학 수업에서 부분적으로 다룬다.
9. 참고 도서
흔히 학부 과정에서 쓰는 교과서로는 수학과의 경우 Herbert Enderton의 ''A Mathematical Introduction to Logic'', 철학과의 경우 Benson Mates의 ''Elementary Logic'' (한국어 번역서명 <기호논리학>, 김영정/선우환 역) 등이 있다.
10. 참고 항목
보다 자세한 개념들에 관해서는 논리학 관련 정보 참조.
[1] 종종 수리 논리학은 '''철학적 논리학'''과 구별되어 쓰이고는 하는데, 둘 사이의 경계는 없거나 애매하며 수리적 도구를 쓴다는 점에서는 차이가 없다. 차이가 있다면 '수리 논리학'이 대수학, 해석학 등 각종 수학 이론이나 집합론, 범주론 등 수학 기초론과 관련된 논리적 문제들에 초점을 기울이는 반면, '철학적 논리학'은 언어철학, 인식론, 형이상학 등 각종 철학 분야와 관련된 논리적 문제들에 초점을 기울이는 경향이 있다. 하지만 본 문서에 나오는 내용은 다 공통된 기초에 해당한다.[2] 엄밀히 따지자면 여러 비단조(non-monotonic) 논리 등이 그 반례가 될 수 있으나 넘어간다.[3] Sequent Calculus 등 복수의 결론을 허용하는 논리 체계도 있다.[4] 보다 엄밀히 말하자면, M에서 "김철수"의 지시체 c는 "-는 학생이다"의 외연 집합 H의 원소라고 하자.[5] 현대 모형 이론의 창시자인 알프레트 타르스키는 모형 이론적 참 개념이 진리론의 유력한 학설 중 하나인 대응론적 참 이론의 연장선 상에 있다고 보았다.[6] 무한집합이어도 된다.