| 논리학 Logics | |||
| {{{#!wiki style="margin: -0px -10px -5px; min-height: 28px" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -6px -1px -11px;" | <colbgcolor=#2ab5b5> 형식 논리 | 명제 논리(논리 연산 · 삼단논법(정언삼단논법) · 순환 논법) · 공리 · 진리치 · 술어 논리 · 논증(논증의 재구성) · 모순 · 역설 · 논리적 오류(논리적 오류/형식적 오류) · 변증법 | |
| <colcolor=#000,#fff> 비표준 논리 | 직관 논리 · 양상논리 · 초일관 논리 · 다치논리(퍼지논리) · 선형논리 · 비단조 논리 | ||
| 메타 논리 | 집합론 · 완전성 정리 · 불완전성 정리 | ||
| 비형식 논리 | 딜레마(흑백논리) | ||
| 비형식적 오류 | 귀납적 오류 · 심리적 오류 · 언어적 오류 · 자료적 오류 · 양비론 · 진영논리 · 편견 및 고정관념 · 궤변 · 거짓 등가성 | ||
| 분야 | 수리철학 · 수리논리학 | ||
| 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 · 수리논리학 둘러보기 | |||
| 수학기초론 Foundations of Mathematics | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문(조각적 정의) · 명제 논리(명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리(존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합(원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계(동치관계 · 순서 관계) · 순서쌍(튜플) · 서수(하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC(선택공리) · 기수(초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리(괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항(약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
數理論理學 / Mathematical logic논리학을 수학의 기호 및 기법을 통하여 연구하는 논리학과 수학의 하위 학문 혹은 방법론. 기호 논리학과 같은 의미로 쓰이거나 그 일부로 여겨진다. 수학에선 집합론과 더불어 수학 기초론을 이루는 중요한 부분 중 하나. 컴퓨터과학과 철학에서도 핵심적인 소양 중 하나로 여겨진다.[1]
일반적으로는 연역논리에 한정되며[2], 본 문서에서는 연역 논리, 그 중에서도 표준(standard) 혹은 고전(classical) 논리에 관한 내용만을 다룬다.
표준논리의 개념들은 대부분 일상 언어의 어휘들로부터 비롯된 것이다. 예를 들어 논리연산자 "∨"는 한국어 "혹은", 영어 "or"에서 비롯되었다. 그렇지만 논리학, 특히 표준 논리 개념들의 뜻은 그 본래 일상 언어 어휘의 쓰임새와 괴리가 있는 경우가 잦다. 명제 논리 문서의 선언문, 조건문, 양화 논리 문서의 개요 문단과 존재함축 문서 참고. 그러므로 일상 언어 문장을 논리식으로 번역하거나, 혹은 반대로 논리식을 일상언어로 이해할 때에는 주의를 요한다.
기호 논리학과 수리 논리학에서는 오직 형식적인 것만을 다루며, 그렇기 때문에 비형식적인 오류나 논리적 기이함(oddity)에 대해서는 다루지 않는다.
2. 역사
논리학을 수학적 기호를 가지고 전개할 수 있다는 발상을 처음 제안한 것은 고트프리트 빌헬름 라이프니츠다. 이후 19세기에 조지 부울이 처음으로 진리치 수준에서 논리를 대수처럼 계산하는 체계를 제시[3]하였고, 고틀로프 프레게와 찰스 샌더스 퍼스는 각각 독립적으로 개념 혹은 술어 수준에서 명제를 분석하는 양화 논리 체계를 개발했다.프레게를 이어 버트런드 러셀과 알프레드 노스 화이트헤드는 모든 수학적 참을 논리학적 참으로 환원하는 논리주의 기획을 개진함으로써 당대 지성계에 큰 영향을 미쳤고, 이는 수학 전체에 대한 무모순적인 공리 체계를 마련하려는 다비트 힐베르트의 형식주의 기획에도 영향을 미쳤다.
하지만 쿠르트 괴델의 불완전성 정리로 인하여 논리주의 및 형식주의의 전통적 형태는 결정적인 위기에 봉착하였고, ZFC 공리계에 관해선 그 실제 사례로 연속체 가설이 있음을 괴델과 폴 코언이 성공적으로 보이는데 이르렀다. 이런 성과를 바탕으로 20세기 후반부터 본격적인 현대 수리 논리학이 발전하기 시작했다.
3. 예비사항
본격적인 수리 논리학 개념 소개에 앞서서 알아두면 좋을 몇몇 논리학적, 논리철학적, 언어철학적 사항들이 있다. 이런 사항들은 실제 논리학 문헌에서는 종종 편의상 슬쩍 넘어가고는 하지만, 논리학적 엄밀성을 위해선 반드시 준수되어야 한다. 형식주의 언어학 계통, 특히 형식의미론에서는 밥먹고 매일 하는 것이다.4. 핵심 개념들
전통적으로 논리학은 "적법한 생각(혹은 추론)의 규칙은 무엇인가?"라는 문제에 답하고자 하는 학문으로 여겨졌다. 프레게 이후 이는 "무엇이 타당한 논증인가?"라는 질문으로 전환되었다.일반적으로 수리 논리학에서 논증이란 특정한 문장 집합("전제")과 특정한 문장("결론")으로 구성된다.[4] 이런 무수한 논증들 가운데 오직 일부만이 적법한 논증, 즉 타당한(valid) 논증이다. 그리고 이때 '타당성'은 크게 두 가지 방식으로 정의된다.
4.1. 의미론적 방식
의미론적 방식에 따르면 타당한 논증이란 전제들이 모두 참인 경우 그 결론 또한 반드시 참인 논증이다. 전제들이 모두 참임에도 불구하고 결론이 거짓일 수 있는 논증은 부당한 논증이다. 특수한 유형들로 다음 예시가 있다:- 전제가 항상 거짓인 경우 논증은 항상 타당하며, 결론이 항상 참인 경우 또한 논증은 항상 타당하다. 이와 같은 경우에 그 논증은 공허하게(vacantly) 타당하다.
- 전제들이 모두 참이며 논증이 타당한 경우, 그 논증은 건전하다(sound).
전제들이 모두 참인 동시에 결론이 참이라고 해서 그 논증이 반드시 타당한 것은 아니다. 논증이 타당하기 위해선 전제들이 모두 참인 경우 결론 또한 반드시 참이어야 하지, 단순히 전제들이 모두 참인 경우 결론 또한 우연히 참인 것은 안되기 때문이다.
- 타당한 논증의 예시: "만약 소크라테스가 철학자라면, 소크라테스는 지혜를 사랑한다. 소크라테스는 철학자다. 따라서 소크라테스는 지혜를 사랑한다."
- 타당하지 않는 논증의 예시: "소크라테스는 철학자다. 고래는 포유류다. 따라서 손흥민은 축구선수다."
논증이 의미론적으로 타당한 경우 그 결론은 전제의 논리적 귀결이다. 결론 [math(\phi)]가 전제 집합 [math(\Gamma)]의 논리적 귀결이라는 것을 두고 표준적으로 다음과 같이 표현한다.
[math(\Gamma \models \phi )]
그리고 전제 집합 [math(\Gamma)]가 공집합인 경우 그 논리적 귀결 [math(\phi)]는 논리적 참이다. [math( \models \phi )]
4.1.1. 모형(해석), 참
참과 거짓의 본성을 묻는 것은 형이상학의 세부 분과 중 하나인 진리론의 중요한 문제다. 다만 논리학 보다 구체적으로는 모형 이론(model theory)에서 문장의 진릿값은 편의상 모형 혹은 해석에 상대적으로 부여된다.예. 모형 M에서 김철수는 모든 학생들의 집합의 원소라고 하자.[5] 그렇다면 문장 "김철수는 학생이다"는 M에서 참이다.
해석은 문장에 지시체를 할당하는 작업이다. 이를테면 명제 논리에서는 각각의 명제에 T 또는 F를 할당하는 것이, 양화 논리에서는 논의 영역과 개체상항을 명시하고 문장의 지시체를 결정해서, 궁극적으로 그 문장의 참 거짓을 판별하는 것이 해석이라고 할 수 있다. 이처럼 해석을 문장에 진릿값을 할당하는 작업으로 파악하면, 최소한 표면적으로는 참과 거짓이 도대체 무엇이냐고 하는 진리론적 논의 없이도 논리학적 문장들을 다룰 수 있게 된다.[6]
그리고 이런 모형 이론적 개념을 취할 경우 논리적 귀결 관계는 다음과 같이 재정의될 수 있다
[math(\Gamma\models\phi\Leftrightarrow\Gamma)]의 모든 원소들이 참인 임의의 모형 [math(M)]에서 [math(\phi)]도 참이다.
더불어 논리적 참은 임의의 모형에서 참인 문장으로 이해될 수 있다.
4.2. 구문론적 방식
전제나 결론의 진리치를 굳이 따지지 않고서도 논증의 타당성을 따져볼 수 있다. 이때 관건은 오직 주어진 추론규칙들에 의거하여 전제들로부터 결론이 도출가능한지 혹은 증명가능한지 여부다. 결론 [math(\phi)]가 전제 집합 [math(\Gamma)]들로부터 도출가능한 경우 이를 보통 다음과 같이 표현한다.[math(\Gamma \vdash \phi )]
전제 집합 [math(\Gamma)]와 '공리'라고 불리는 일련의 문장들로부터 주어진 추론규칙들을 유한번 적용해서 얻은 문장들의 열(sequence)을 '증명'이라고 부른다. 그리고 전제가 공집합일 때, 증명의 마지막 행에 놓이는 문장을 '정리'(Theorem)라고 부른다.5. 명제 논리
6. 양화 논리
7. 메타 정리들
이하의 논리학적 정리들은 논리 체계 내부의 정리가 아니라, 논리 체계 그 자체에 대한 정리이기 때문에 메타 정리라고 불린다. 이 메타 정리들은 명제 논리와 1차 술어논리에서만 동시에 성립하며, 2차 이상의 논리 체계에서는 어떻게 하더라도 동시에 성립할 수 없다. 이 성질들이 동시에 성립하는 1차 술어논리는 가장 기초적인 논리 체계가 된다고 할 수 있으며, 따라서 지금까지도 수학의 기초로 활용되고 있다.7.1. 논리 체계의 건전성, 완전성, 일관성
논리 체계의 건전성, 완전성, 일관성은 다음과 같이 간략하게 기술된다.- 논리체계가 건전하다는 것은 문장집합 [math(\Gamma)]로부터 문장 [math(\phi)]가 도출되면, 문장 [math(\phi)]가 문장집합 [math(\Gamma)]의 귀결이라는 것이다.[math(\Gamma\vdash\phi\Rightarrow\Gamma\models\phi)]
- 논리체계가 완전하다는 것은 문장 [math(\phi)]가 문장집합 [math(\Gamma)]의 귀결일 때, 문장집합 [math(\Gamma)]로부터 문장 [math(\phi)]가 도출된다는 것이다.[math(\Gamma\models\phi\Rightarrow\Gamma\vdash\phi)]
- 논리체계가 일관적이라는 것은 공집합으로부터 모순이 도출되지 않는다는 것이다. 이는 무모순성이라고도 표현한다.[math(\emptyset\not\vdash\bot)]
여기서, (1)과 (2)는 역의 관계에 있다. 명제 논리와 1차 술어논리 체계가 건전하며 동시에 완전하다는 것은 건전성 정리와 괴델의 완전성 정리를 통해 증명되어 있다. 즉, 명제 논리와 1차 술어논리에서 모형이론적 진리와 증명이론적 진리는 서로 같다. 타당한 문장은 증명될 수 있고, 증명될 수 있는 문장은 타당하다.
[math(\Gamma\models\phi\Leftrightarrow\Gamma\vdash\phi)]
또한 표준적인 명제 논리와 1차 술어논리의 체계는 일관적이다. 이 체계에서는 공집합으로부터 모순이 도출되지 않는다. 역시 괴델의 완전성 정리에 따라 1차 논리에서 일관성이 성립함이 증명되었다.7.2. 콤팩트성
콤팩트성은 쉽게 말하자면 어떤 집합이 '닫혀 있는' 성질이라고 할 수 있다. 1차 술어논리와 명제논리에서는 모든 문장 집합에 대해 콤팩트성이 성립하는데, 이 메타증명을 콤팩트성 정리라고 한다. 이를 보다 상세하게 정의하면 다음과 같다.임의의 문장 [math(\phi)]가 임의의 문장 집합 [math(\Gamma)][7]의 귀결일 때, [math(\Delta \models \phi)]를 만족시키는 [math(\Gamma)]의 어떤 유한 부분집합 [math(\Delta)]가 존재한다.
또한 콤팩트성 정리에 따르면 논리 체계의 일관성과 콤팩트성은 동치이다. 콤팩트성이 항상 성립하는 논리 체계는 일관적인 논리 체계이며, 일관적인 논리 체계에서는 콤팩트성이 항상 성립한다.7.3. 뢰벤하임-스콜렘 정리
7.4. 불완전성 정리
괴델은 임의의 논리 체계가 자연수 산술 체계를 포함할 수 있을 정도로 강력할 경우 그 논리 체계는 불완전하다는 것을 보였다.8. 교과 과목
수학과에서는 주로 집합론과 함께 전공과목으로 다루어지지만, 경우에 따라서는 학부에서는 다루지 않기도 한다. 철학과의 경우, 대체로 학부의 전공필수 과목으로 개설되지만 커리큘럼이 일정하지 않은 철학과의 특성 상 필수 과목이 아닌 경우도 있다. 컴퓨터공학과에서는 학부의 경우 이산수학, 오토마타 강의에서 부분적으로 다룬다. 언어학과의 경우 수리언어학 강의에서 다룬다.9. 참고 도서
흔히 학부 과정에서 쓰는 교과서로는 수학과의 경우 Herbert Enderton의 <A Mathematical Introduction to Logic>이 있고, 철학과의 경우 입문 교재로 성균관대 이병덕 교수의 <코어 논리학>과 한양대 최원배 교수의 <논리적 사고의 기초> 등이 있으며, 중급의 교재로는 Benson Mates의 <Elementary Logic>(한국어 번역서명 <기호논리학>, 김영정/선우환 역)과 Boolos,Jeffrey,Burgess의 공저인 <Computability and Logic>(한국어 번역서명 <계산가능성과 논리>, 김영정 역,번역서는 현재 절판)이 있다.10. 관련 문서
[1] 종종 수리 논리학은 철학적 논리학과 구별되어 쓰이고는 하는데, 둘 사이의 경계는 없거나 애매하며 수리적 도구를 쓴다는 점에서는 차이가 없다. 차이가 있다면 '수리 논리학'이 대수학, 해석학 등 각종 수학 이론이나 집합론, 범주론 등 수학 기초론과 관련된 논리적 문제들에 초점을 기울이는 반면, '철학적 논리학'은 언어철학, 인식론, 형이상학 등 각종 철학 분야와 관련된 논리적 문제들에 초점을 기울이는 경향이 있다. 하지만 본 문서에 나오는 내용은 다 공통된 기초에 해당한다.[2] 엄밀히 따지자면 여러 비단조(non-monotonic) 논리 등이 그 반례가 될 수 있으나 넘어간다.[3] 기호는 현대와는 다르게 사칙연산에서 따온 기호들을 응용하였다.[4] Sequent Calculus 등 복수의 결론을 허용하는 논리 체계도 있다.[5] 보다 엄밀히 말하자면, M에서 "김철수"의 지시체 c는 "-는 학생이다"의 외연 집합 H의 원소라고 하자.[6] 현대 모형 이론의 창시자인 알프레트 타르스키는 모형 이론적 참 개념이 진리론의 유력한 학설 중 하나인 대응론적 참 이론의 연장선 상에 있다고 보았다.[7] 무한집합이어도 된다.