최근 수정 시각 : 2019-02-15 17:59:29

수리 논리학


영어: mathematical logic

1. 개요2. 역사3. 예비사항4. 핵심 개념들
4.1. 논증과 타당성
4.1.1. 의미론적 방식
4.1.1.1. 모형(해석),
4.1.2. 구문론적 방식
4.2. 메타 정리들
4.2.1. 논리 체계의 건전성, 완전성, 일관성4.2.2. 콤팩트성4.2.3. 뢰벤하임-스콜렘 정리4.2.4. 불완전성 정리
5. 명제 논리6. 양화 논리7. 교과 과목8. 참고 항목

1. 개요

논리학수학의 기호 및 기법을 통하여 연구하는 논리학수학의 하위 학문 혹은 방법론. 기호 논리학와 같은 의미로 쓰이거나 그 일부로 여겨진다.[1]

수학에선 집합론과 더불어 수학 기초론을 이루는 중요한 부분 중 하나. 컴퓨터과학철학에서도 핵심적인 소양 중 하나로 여겨진다.

일반적으로는 연역논리에 한정되며[2], 본 문서에서도 연역 논리, 그 중에서도 표준논리(standard logic)에 관한 내용만을 다룬다.

표준논리의 개념들은 대부분 일상 언어의 어휘들로부터 비롯된 것이다. 예를 들어 논리연산자 "∨"는 한국어 "혹은", 영어 "or"에서 비롯되었다. 그렇지만 논리학, 특히 표준 논리 개념들의 뜻은 그 본래 일상 언어 어휘의 쓰임새와 괴리가 있는 경우가 잦다. 명제 논리 문서의 선언문, 실질 조건문, 양화 논리 문서의 개요 문단과 존재함축 문서 참조. 그러므로 일상 언어 문장을 논리식으로 번역하거나, 혹은 반대로 논리식을 일상언어로 이해할 때에는 주의를 요한다.

기호 논리학과 수리 논리학에서는 오직 형식적인 것만을 다루며, 그렇기 때문에 비형식적인 오류나 논리적 기이함(oddity)에 대해서는 다루지 않는다. 비형식적 오류에 대해서는 논리적 오류/비형식적 오류 항목을 참조하라.

2. 역사

논리학을 수학적 기호를 가지고 전개할 수 있다는 발상을 처음 제안한 것은 고트프리트 빌헬름 라이프니츠다. 이후 19세기조지 부울이 처음으로 진리치 수준에서 논리를 대수처럼 계산하는 체계를 제시하였고, 고틀로프 프레게와 찰스 샌더스 퍼스는 각각 독립적으로 개념 혹은 술어 수준에서 명제를 분석하는 양화 논리 체계를 개발했다.

프레게를 이어 버트런드 러셀알프레드 노스 화이트헤드는 모든 수학적 참을 논리학적 참으로 환원하는 논리주의 기획을 개진함으로써 당대 지성계에 큰 영향을 미쳤고, 이는 수학 전체에 대한 무모순적인 공리 체계를 마련하려는 다비트 힐베르트형식주의 기획에도 영향을 미쳤다.

하지만 쿠르트 괴델불완전성 정리로 인하여 논리주의 및 형식주의의 전통적 형태는 결정적인 위기에 봉착하였고, ZFC 공리계에 관해선 그 실제 사례로 연속체 가설이 있음을 괴델과 폴 코언이 성공적으로 보이는데 이르렀다. 이런 성과를 바탕으로 20세기 후반부터 본격적인 현대 수리 논리학이 발전하기 시작했다.

3. 예비사항

본격적인 수리 논리학 개념 소개에 앞서서 알아두면 좋을 몇몇 논리학적, 논리철학적, 언어철학적 사항들이 있다. 이런 사항들은 실제 논리학 문헌에서는 종종 편의상 슬쩍 넘어가고는 하지만, 논리학적 엄밀성을 위해선 반드시 준수되어야 한다.

자세한 내용은 수리 논리학/예비사항 항목 참조.

4. 핵심 개념들

4.1. 논증과 타당성

전통적으로 논리학은 "적법한 생각(혹은 추론)의 규칙은 무엇인가?"라는 문제에 답하고자 하는 학문으로 여겨졌다. 프레게 이후 이는 "무엇이 타당한 논증인가?"라는 질문으로 전환되었다.

일반적으로 수리 논리학에서 논증이란 특정한 문장 집합("전제")과 특정한 문장("결론")으로 구성된다.[3] 이런 무수한 논증들 가운데 오직 일부만이 적법한 논증, 즉 타당한(valid) 논증이다. 그리고 이때 '타당성'은 크게 두 가지 방식으로 정의된다.

4.1.1. 의미론적 방식

의미론적 방식에 따르면 타당한 논증이란 전제들이 모두 참인 경우 그 결론 또한 반드시 참인 논증이다. 전제들이 모두 참임에도 불구하고 결론이 거짓일 수 있는 논증은 부당한 논증이다. 특수한 유형들로 다음 예시가 있다:
  • 전제가 항상 거짓인 경우 논증은 항상 타당하며, 결론이 항상 참인 경우 또한 논증은 항상 타당하다. 이와 같은 경우에 그 논증은 공허하게(vacantly) 타당하다.
  • 전제들이 모두 참이며 논증이 타당한 경우, 그 논증은 건전하다(sound).

전제들이 모두 참인 동시에 결론이 참이라고 해서 그 논증이 반드시 타당한 것은 아니다. 논증이 타당하기 위해선 전제들이 모두 참인 경우 결론 또한 반드시 참이어야 하지, 단순히 전제들이 모두 참인 경우 결론 또한 우연히 참인 것은 안되기 때문이다.
  • 타당한 논증의 예시: "만약 소크라테스가 철학자라면, 소크라테스는 지혜를 사랑한다. 소크라테스는 철학자다. 따라서 소크라테스는 지혜를 사랑한다."
  • 타당하지 않는 논증의 예시: "소크라테스는 철학자다. 고래는 포유류다. 따라서 박지성은 축구선수다."

논증이 의미론적으로 타당한 경우 그 결론은 전제의 논리적 귀결이다. 결론 ϕ\phi가 전제 집합 Γ\Gamma의 논리적 귀결이라는 것을 두고 표준적으로 다음과 같이 표현한다.
Γϕ\Gamma \models \phi
그리고 전제 집합 Γ\Gamma공집합인 경우 그 논리적 귀결 ϕ\phi논리적 참이다.
ϕ \models \phi
4.1.1.1. 모형(해석),
거짓의 본성을 묻는 것은 형이상학의 세부 분과 중 하나인 진리론의 중요한 문제다. 다만 논리학 보다 구체적으로는 모형 이론(model theory)에서 문장의 진릿값은 편의상 모형 혹은 해석에 상대적으로 부여된다.
예. 모형 M에서 김철수는 모든 학생들의 집합의 원소라고 하자. 그렇다면 문장 "김철수는 학생이다"는 M에서 참이다.[4]

해석은 문장에 지시체를 할당하는 작업이다. 이를테면 명제 논리에서는 각각의 명제에 T 또는 F를 할당하는 것이, 양화 논리에서는 논의 영역과 개체상항을 명시하고 문장의 지시체를 결정해서, 궁극적으로 그 문장의 참 거짓을 판별하는 것이 해석이라고 할 수 있다. 이처럼 해석을 문장에 진릿값을 할당하는 작업으로 파악하면, 참과 거짓이 도대체 무엇이냐고 하는 진리론적 논의 없이도 논리학적 문장들을 다룰 수 있게 된다.

그리고 이런 모형 이론적 개념을 취할 경우 논리적 귀결 관계는 다음과 같이 재정의될 수 있다
Γϕ \Gamma \models \phi iff Γ\Gamma 의 모든 원소들이 참인 임의의 모형 M에서 ϕ \phi 도 참이다.

더불어 논리적 참은 임의의 모형에서 참인 문장으로 이해될 수 있다.

4.1.2. 구문론적 방식

전제나 결론의 진리치를 굳이 따지지 않고서도 논증의 타당성을 따져볼 수 있다. 이때 관건은 오직 주어진 추론규칙들에 의거하여 전제들로부터 결론이 도출가능한지 혹은 증명가능한지 여부다. 결론 ϕ\phi가 전제 집합 Γ\Gamma들로부터 도출가능한 경우 이를 보통 다음과 같이 표현한다.
Γϕ\Gamma \vdash \phi
전제 집합 Γ\Gamma와 '공리'라고 불리는 일련의 문장들에 관하여 주어진 규칙들을 적절히 적용한 문장의 연쇄를 두고 '증명'이라고 부른다. 그리고 전제가 공집합일 때, 증명의 마지막 행에 놓이는 문장을 '정리'라고 부른다.

4.2. 메타 정리들

이하의 논리학적 정리들은 논리 체계 내부의 정리가 아니라, 논리 체계 그 자체에 대한 정리이기 때문에 메타 정리라고 불린다. 이 메타 정리들은 명제 논리와 1차 술어논리에서만 동시에 성립하며, 2차 이상의 논리 체계에서는 어떻게 하더라도 동시에 성립할 수 없다. 이 성질들이 동시에 성립하는 1차 술어논리는 가장 기초적인 논리 체계가 된다고 할 수 있으며, 따라서 지금까지도 수학의 기초로 활용되고 있다.

4.2.1. 논리 체계의 건전성, 완전성, 일관성

논리 체계의 건전성, 완전성, 일관성은 다음과 같이 간략하게 기술된다.

(1) 논리체계가 건전하다는 것은 문장집합 G로부터 문장 ϕ가 도출되면, 문장 ϕ가 문장집합 G의 귀결이라는 것이다.
ΓϕΓϕ\Gamma \vdash \phi \Rightarrow \Gamma \models \phi
(2) 논리체계가 완전하다는 것은 문장 ϕ가 문장집합 G의 귀결일 때, 문장집합 G로부터 문장 ϕ가 도출된다는 것이다.
ΓϕΓϕ\Gamma \models \phi \Rightarrow \Gamma \vdash \phi
(3) 논리체계가 일관적이라는 것은 공집합으로부터 모순이 도출되지 않는다는 것이다. 이는 무모순성이라고도 표현한다.
\emptyset \not\vdash \bot
여기서, (1)과 (2)는 역의 관계에 있으며, 괴델의 완전성 정리에 따르면 명제 논리와 1차 술어논리 체계에서 건전성과 완전성은 동치이다. 명제 논리와 1차 술어논리 체계가 건전하며 동시에 완전하다는 것 역시 건전성 정리와 괴델의 완전성 정리를 통해 이미 증명되어 있다. 즉, 명제 논리와 1차 술어논리에서 모형이론적 진리와 증명이론적 진리는 서로 같다. 타당한 문장은 증명될 수 있고, 증명될 수 있는 문장은 타당하다.
ΓϕΓϕ\Gamma \models \phi \Leftrightarrow \Gamma \vdash \phi
또한 표준적인 명제 논리와 1차 술어논리의 체계는 일관적이다. 이 체계에서는 공집합으로부터 모순이 도출되지 않는다. 역시 괴델의 완전성 정리에 따라 1차 논리에서 일관성이 성립함이 증명되었다.

4.2.2. 콤팩트성

콤팩트성은 쉽게 말하자면 어떤 집합이 '닫혀 있는' 성질이라고 할 수 있다. 1차 술어논리와 명제논리에서는 모든 문장 집합에 대해 콤팩트성이 성립하는데, 이 메타증명을 콤팩트성 정리라고 한다. 이를 보다 상세하게 정의하면 다음과 같다.
임의의 문장 ϕ\phi가 임의의 문장 집합 Γ\Gamma[5]의 귀결일 때, Δϕ\Delta \models \phi를 만족시키는 Γ\Gamma의 어떤 유한 부분집합 Δ\Delta가 존재한다.
또한 콤팩트성 정리에 따르면 논리 체계의 일관성과 콤팩트성은 동치이다. 콤팩트성이 항상 성립하는 논리 체계는 일관적인 논리 체계이며, 일관적인 논리 체계에서는 콤팩트성이 항상 성립한다.

4.2.3. 뢰벤하임-스콜렘 정리

뢰벤하임-스콜렘 정리 문서 참조.

4.2.4. 불완전성 정리

괴델은 임의의 논리 체계가 자연수 산술 체계를 포함할 수 있을 정도로 강력할 경우 그 논리 체계는 불완전하다는 것을 보였다. 불완전성 정리 문서 참조.

5. 명제 논리

명제 논리 문서 참조.

6. 양화 논리

양화 논리 문서 참조.

7. 교과 과목

수학과에서는 주로 집합론과 함께 전공과목으로 다루어지지만, 경우에 따라서는 학부에서는 다루지 않기도 한다. 철학과의 경우, 대체로 학부의 전공필수 과목으로 개설되지만 커리큘럼이 일정하지 않은 철학과의 특성 상 필수 과목이 아닌 경우도 있다. 컴퓨터공학과에서는 학부의 경우 이산수학 수업에서 부분적으로 다룬다.

흔히 학부 과정에서 쓰는 교과서로는 수학과의 경우 Herbert Enderton의 A Mathematical Introduction to Logic, 철학과의 경우 Benson Mates의 Elementary Logic (한국어 번역서명 <기호논리학>, 김영정/선우환 역) 등이 있다. 아오 머리야

8. 참고 항목

보다 자세한 개념들에 관해서는 논리학 관련 정보 참조.

파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 논리학 문서의 r107 판, 2번 문단에서 가져왔습니다. 이전 역사 보러 가기



파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 연역논증 문서의 r60 판, 3번 문단에서 가져왔습니다. 이전 역사 보러 가기



[1] 종종 수리 논리학은 철학적 논리학과 구별되어 쓰이고는 하는데, 현대의 철학적 논리학 또한 수학 기호를 적극적으로 받아들이므로 "기호논리학"과 "수리논리학"이 뜻이 아예 같다고 할 경우엔 자칫 오해가 빚어질 수 있다.[2] 엄밀히 따지자면 현대의 공리적 확률론 혹은 비단조(non-monotonic) 논리 등이 그 반례가 될 수 있으나 넘어간다.[3] Sequent Calculus 등 복수의 결론을 허용하는 논리 체계도 있다.[4] 엄밀히 말하자면 모형 혹은 해석은 "김철수", "학생" 등에 적절한 대상을 할당해야 하므로 해당 예시는 엄밀히 말하자면 틀렸다.[5] 무한집합이어도 된다.