기호 논리학

명제는 참 또는 거짓 중 하나의 진릿값을 가지는 문장이다. 예를 들어, "2는 짝수이다"는 참인 명제이며, "3+5=9"는 거짓인 명제이다. 반면, "이 문제는 어렵다"와 같이 주관적이거나 "x=1"과 같이 변수의 값에 따라 진릿값이 결정되는 문장은 명제가 아니다.

기본적인 논리 연산에는 논리합, 논리곱, 부정, 조건문, 쌍조건문이 있다. 이 연산들은 하나 또는 두 개의 명제를 결합하여 새로운 명제를 만든다. 각 연산은 진리표로 그 의미가 엄밀하게 정의된다. 예를 들어, 두 명제 P와 Q의 논리합(P ∨ Q)은 P와 Q 중 적어도 하나가 참일 때 참이다. 논리곱(P ∧ Q)은 P와 Q 모두 참일 때만 참이다. 부정(¬P)은 P의 진릿값을 반대로 뒤집는다.

조건문(P → Q)은 "만약 P이면 Q이다"를 의미하며, P가 참이고 Q가 거짓일 때만 거짓이다. 이 정의는 직관적인 '원인-결과' 관계와는 다를 수 있어 주의가 필요하다. 쌍조건문(P ↔ Q)은 "P는 Q와 동치이다"를 의미하며, P와 Q의 진릿값이 동일할 때 참이다.

이러한 논리 연산자들은 복잡한 논리식을 구성하는 기본 구성 요소 역할을 한다. 연산자 간의 우선순위는 일반적으로 부정(¬)이 가장 높고, 그 다음 논리곱(∧)과 논리합(∨), 조건문(→), 쌍조건문(↔) 순이다. 괄호를 사용하여 우선순위를 명시적으로 지정할 수도 있다.

진리표는 명제 논리에서 논리 연산의 의미를 정의하거나 복합 명제의 진리값을 체계적으로 분석하는 도구이다. 각 명제 변수에 가능한 모든 진리값(참 또는 거짓)의 조합을 나열하고, 그에 따른 복합 명제의 진리값을 계산하여 표로 나타낸다.

예를 들어, 논리합(∨)과 논리곱(∧)의 진리표는 다음과 같다.

두 논리식이 논리적 동치라는 것은 모든 가능한 진리값 할당에 대해 두 식의 진리값이 항상 동일함을 의미한다. 이를 기호로 P ≡ Q 또는 P ⇔ Q로 표시한다. 진리표는 두 논리식이 논리적 동치인지 확인하는 가장 직접적인 방법이다. 예를 들어, 이중 부정 법칙 ¬(¬P) ≡ P나 드 모르간의 법칙 ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)는 진리표를 작성하여 모든 경우에 진리값이 일치함을 보임으로써 증명할 수 있다.

논리적 동치는 복잡한 논리식을 간소화하거나 다른 형태로 변환하는 데 유용하게 사용된다. 특히 함의(→)를 논리합과 부정으로 표현하는 동치, 즉 (P → Q) ≡ (¬P ∨ Q)는 증명과 추론에서 자주 활용되는 중요한 관계이다. 이러한 동치 관계들의 집합은 명제 논리의 대수적 구조를 규정하는 기초가 된다.

함의는 명제 논리에서 가장 중요한 논리 연산자 중 하나로, "만약 ...이면 ...이다"라는 조건문을 형식화한다. 일반적으로 기호 → 또는 ⊃로 표시되며, 명제 p와 q에 대해 p → q로 쓴다. 이 진술은 p가 참이고 q가 거짓인 경우에만 거짓이며, 다른 모든 경우에는 참이다[1]. 이는 전건(p)이 거짓이거나 후건(q)이 참일 때 조건문 전체가 참이 된다는 것을 의미한다.

추론 규칙은 이미 알려진 명제들로부터 새로운 명제를 유도하는 논리적 도구이다. 가장 기본적이고 널리 사용되는 추론 규칙은 긍정 논법(Modus Ponens)이다. 이 규칙은 "p → q"와 "p"가 모두 참이면, "q"도 참이라는 결론을 내릴 수 있게 한다. 다른 중요한 추론 규칙으로는 부정 논법(Modus Tollens)이 있다. 이 규칙은 "p → q"가 참이고 "q"가 거짓이면, "p"도 거짓이어야 한다는 것을 허용한다.

추론 규칙은 논리적 증명의 기본 구성 요소로서, 각 단계가 타당한지 검증하는 데 사용된다. 예를 들어, 다음과 같은 추론은 긍정 논법에 의한 것이다.

1. 만약 비가 오면, 길이 젖는다. (p → q)

2. 비가 온다. (p)

3. 따라서, 길이 젖는다. (q)

이러한 규칙들은 공리계와 결합되어 형식적 체계를 이루며, 복잡한 논리식의 타당성을 체계적으로 증명하는 데 기초가 된다.

명제 변수는 참(진리값 참) 또는 거짓(진리값 거짓)의 값을 가질 수 있는 기호적 표현이다. 일반적으로 로마자 소문자 p, q, r 등으로 표시한다. 이 변수들은 구체적인 내용을 담지 않은 추상적인 명제 자리를 나타내며, 논리 연산자와 결합하여 더 복잡한 논리식을 구성하는 기본 단위 역할을 한다.

논리식은 명제 변수와 논리 연산자를 결합하여 만들어진 정형화된 문자열이다. 가장 간단한 논리식은 명제 변수 자체이다. 논리 연산자 논리합(∨), 논리곱(∧), 부정(¬), 함의(→), 동치(↔) 등을 사용하여 명제 변수를 결합하면 새로운 논리식이 생성된다. 예를 들어, 'p ∧ q', '¬p → q', '(p ∨ q) ∧ ¬r' 등은 모두 논리식이다. 논리식의 구조는 일반적으로 재귀적 정의를 통해 엄밀하게 규정된다[2].

논리식의 복잡성은 그 구조에 따라 구분된다. 명제 변수만으로 이루어진 논리식을 원자식이라고 한다. 하나 이상의 논리 연산자를 포함하는 논리식은 복합 논리식이다. 복합 논리식에서 가장 바깥쪽에 적용되는 주요 연산자를 주연결사라고 부르며, 이에 따라 논리식을 분류한다. 예를 들어, '(p ∧ q) → r'의 주연결사는 함의(→)이다.

각 논리식은 명제 변수에 특정 진리값을 할당(진리값 할당)했을 때 전체 식의 진리값이 결정된다. 이 진리값은 구성 요소들의 진리값과 논리 연산자의 의미(진리표에 정의됨)에 따라 계산된다. 모든 가능한 진리값 할당에 대해 항상 참인 논리식을 항진식이라고 하며, 항상 거짓인 논리식을 모순식이라고 한다. 그 외의 경우는 불확정식이다.

명제 논리의 체계는 명제 변수와 논리 연산자로 구성된 논리식의 유효성을 체계적으로 연구하는 형식 체계이다. 이 체계는 일반적으로 공리계와 추론 규칙의 집합으로 정의되며, 이를 통해 항진명제와 같은 논리적 진리를 형식적으로 도출할 수 있다.

가장 잘 알려진 체계 중 하나는 프레게의 작업을 기반으로 한 힐베르트 체계이다. 이 체계는 몇 개의 공리와 긍정 논법이라는 추론 규칙 하나로 구성된다. 반면, 겐첸이 도입한 자연 연역 체계는 공리를 사용하지 않고, 각 논리 연산자에 대한 도입 규칙과 제거 규칙이라는 추론 규칙만으로 논리적 추론을 모델링한다. 또 다른 중요한 체계로는 해석과 증명의 관계를 연구하는 시퀀트 계산이 있다.

이러한 다양한 체계들은 서로 다른 방식으로 설계되었지만, 모두 명제 논리의 동일한 논리적 내용을 포착한다는 점에서 동등하다. 즉, 한 체계에서 증명 가능한 모든 논리식은 다른 체계에서도 증명 가능하다. 이는 명제 논리의 여러 공리화 체계들이 동치임을 보여주는 중요한 성질이다. 이러한 체계들의 비교는 다음과 같다.

명제 논리의 형식 체계에 대한 연구는 증명 이론의 핵심 주제이다. 이러한 체계들은 수학 기초론에서 수학적 명제의 형식적 증명을 분석하는 데 필수적이며, 컴퓨터 과학에서는 자동 정리 증명과 프로그램 검증의 기초를 제공한다.

양화사는 술어 논리에서 변수의 범위를 지정하고, 명제의 진리값을 결정하는 논리 기호이다. 가장 기본적인 양화사는 전칭 양화사(∀)와 존재 양화사(∃)이다. 전칭 양화사 "∀x"는 "모든 x에 대하여"라는 의미를 가지며, 존재 양화사 "∃x"는 "어떤 x가 존재하여"라는 의미를 가진다.

술어는 하나 이상의 객체를 변수로 받아 참 또는 거짓을 반환하는 함수이다. 예를 들어, "P(x)"는 "x는 식물이다"와 같은 단항 술어를, "R(x, y)"는 "x는 y를 사랑한다"와 같은 이항 술어를 나타낸다. 술어 논리는 명제 논리에서 다루기 어려운 "모든 사람은 죽는다" 또는 "어떤 새는 날지 못한다"와 같은 내부 구조를 가진 명제를 정밀하게 분석할 수 있게 해준다.

양화사와 술어를 결합하여 복잡한 논리식을 구성할 수 있다. 예를 들어, "∀x (사람(x) → 죽는다(x))"는 "모든 x에 대해, x가 사람이면 x는 죽는다"라는 명제를 형식화한다. 양화사의 적용 순서와 범위는 논리식의 의미를 결정하는 데 중요하다. "∀x∃y R(x, y)"와 "∃y∀x R(x, y)"는 일반적으로 서로 동치가 아니다[3].

술어 논리의 형식 언어는 일반적으로 다음과 같은 구성 요소를 포함한다.

술어 논리의 체계는 명제 논리를 확장하여 개체와 그들 간의 관계를 다루는 형식 체계이다. 이 체계는 양화사와 술어를 포함하는 논리식을 구성하고, 이들에 대한 엄밀한 증명 이론과 모형 이론을 제공한다.

체계의 핵심 구성 요소는 논리식의 형성 규칙, 공리계, 그리고 추론 규칙이다. 형성 규칙은 개체 변수, 상수, 함수 기호, 술어 기호, 논리 연산자(¬, ∧, ∨, →, ↔), 그리고 존재 양화사(∃)와 전칭 양화사(∀)를 결합하여 올바른 논리식을 재귀적으로 정의한다. 예를 들어, P(x)가 1항 술어라면 ∀x P(x)는 올바른 논리식이다. 대표적인 공리계로는 1차 논리를 위한 공리들을 포함하는 힐베르트 체계가 있다. 이는 명제 논리의 공리에 양화사 관련 공리, 예를 들어 ∀x φ(x) → φ(t) (단, t는 x에 대해 자유롭게 대입 가능한 항)와 같은 공리를 추가한다. 주요 추론 규칙으로는 전건 긍정과 함께 전제 일반화(φ / ∴ ∀x φ) 규칙이 사용된다.

이 체계는 증명과 모형이라는 두 측면에서 연구된다. 증명 이론적 측면에서는 주어진 공리와 추론 규칙으로부터 논리식의 연역 가능성을 다룬다. 모형 이론적 측면에서는 논리식에 의미를 부여하는 해석과 구조를 정의하고, 어떤 구조에서 논리식이 참이 되는지(즉, 만족되는지)를 연구한다. 1차 논리의 가장 중요한 성질 중 하나는 괴델의 완전성 정리로, 증명 이론적 연역 가능성과 모형 이론적 타당성(모든 모형에서 참)이 동치임을 보여준다[4]. 이 정리는 술어 논리의 체계가 그 의미론에 대해 건전하고 완전함을 의미한다.

공리계는 증명 없이 참으로 받아들이는 기본 명제들의 집합이다. 이 공리들은 해당 논리 체계의 출발점이 된다. 추론 규칙은 이미 증명된 명제들로부터 새로운 명제를 유도하는 방법을 규정한다. 가장 대표적인 추론 규칙은 전건 긍정(Modus Ponens)이다.

명제 논리에서 널리 사용되는 공리계 중 하나는 다음과 같은 세 가지 공리 스키마로 구성된다[6].

1. A → (B → A)

2. (A → (B → C)) → ((A → B) → (A → C))

3. (¬B → ¬A) → (A → B)

이 공리들과 전건 긍정 규칙만으로 명제 논리의 모든 항진식을 증명할 수 있다. 다른 공리계로는 니코드 공리처럼 단 하나의 공리와 하나의 추론 규칙만으로도 체계를 구성하는 경우도 있다.

공리계의 선택은 증명의 간결성이나 체계의 메타적 성질 증명의 난이도에 영향을 미친다. 완전성과 무모순성은 바람직한 공리계가 가져야 할 핵심 속성이다.

정리 증명은 기호 논리학의 핵심 활동으로, 주어진 공리계와 추론 규칙을 사용하여 논리식을 유도하는 과정이다. 주요 증명 방법은 크게 연역적 증명과 형식적 증명으로 나뉜다. 연역적 증명은 전제로부터 결론을 단계적으로 도출하는 방법이며, 직접 증명법, 대우 증명법, 귀류법 등이 여기에 속한다. 형식적 증문은 증명의 각 단계를 엄격한 형식 규칙에 따라 기호로만 표현한 것을 말한다.

구체적인 증명 방법으로는 다음과 같은 것들이 있다.

* 직접 증명법: 공리나 이미 증명된 정리로부터 추론 규칙을 반복 적용하여 목표 정리에 직접 도달한다.

* 조건 증명법: 증명하려는 명제가 함의 형태일 때, 전제를 가정한 후 결론을 유도한다. 이는 추론 규칙 중 하나인 가정 도입 규칙에 해당한다.

* 귀류법: 증명하려는 명제의 부정을 가정했을 때 모순이 도출됨을 보여 원래 명제가 참임을 증명한다.

* 반례에 의한 증명: 보편적 명제의 거짓을 증명할 때 사용하며, 명제를 만족하지 않는 하나의 반례를 찾는 것으로 충분하다.

이러한 방법들은 자연 연역 체계나 공리계와 같은 형식 체계 안에서 체계화된다. 특히 수학적 귀납법은 자연수에 관한 정리를 증명하는 강력한 도구로, 기초 단계와 귀납 단계를 증명함으로써 모든 자연수에 대해 명제가 성립함을 보인다. 모든 증명 방법의 궁극적 목표는 논증의 타당성을 기호 조작의 관점에서 명확하고 오류의 여지가 없게 보여주는 데 있다.

해석은 술어 논리의 논리식에 의미를 부여하는 과정이다. 형식 언어로 표현된 기호들에 구체적인 의미를 할당하여, 그 논리식이 참인지 거짓인지를 판단할 수 있는 기반을 마련한다. 일반적으로 해석은 논의 영역(domain)과 그 영역 내에서 각 상수, 함수 기호, 술어 기호에 부여할 의미로 구성된다[7].

주어진 해석 아래에서 논리식이 참일 때, 그 논리식을 '만족한다'고 표현한다. 예를 들어, 논리식 ∀x P(x)는 '모든 x에 대해 P(x)가 성립한다'는 의미인데, 해석에서 P(x)의 의미를 'x는 자연수이다'로, 논의 영역을 자연수 집합으로 정하면 이 논리식은 참이 되어 해당 해석에 의해 만족된다. 반대로, 같은 논리식에 대해 P(x)의 의미를 'x는 짝수이다'로 부여하면, 논의 영역이 자연수 전체일 때 이 논리식은 거짓이 되어 만족되지 않는다.

만족 가능성과 타당성은 모형 이론의 핵심 개념이다. 어떤 논리식이 적어도 하나의 해석에서 참일 경우, 그 논리식을 '만족 가능하다'고 한다. 반대로, 모든 가능한 해석에서 항상 참인 논리식은 '타당하다'고 하며, 모든 해석에서 항상 거짓인 논리식은 '모순' 또는 '불만족 가능하다'고 한다. 이 관계는 다음과 같이 정리할 수 있다.

해석과 만족의 개념은 모형 이론의 기초를 이루며, 논리식의 의미론적 성질을 연구하는 데 필수적이다. 이는 후에 논리 체계의 건전성과 완전성을 논의하는 완전성 정리로 이어지는 중요한 토대가 된다.

완전성 정리는 기호 논리학의 핵심 정리 중 하나로, 특정 논리 체계 내에서 증명 가능한 모든 문장이 그 체계의 모든 모형에서 참인 문장과 정확히 일치함을 보여준다. 즉, '증명 가능성'과 '논리적 타당성'이 동등함을 의미한다. 이 정리는 쿠르트 괴델에 의해 1929년 그의 박사 논문에서 일차 술어 논리에 대해 처음 증명되었으며, 현대 논리학의 기초를 확립하는 데 결정적인 역할을 했다[8].

정리의 내용은 공리와 추론 규칙으로 구성된 형식 체계에 대해 두 가지 측면을 포함한다.

* 음의 완전성 (Soundness): 체계에서 증명 가능한 모든 문장은 논리적으로 타당하다. 즉, 모든 모형에서 참이다. 이는 체계가 '안전함'을 보장한다.

* 양의 완전성 (Completeness): 논리적으로 타당한 모든 문장은 그 체계 내에서 증명 가능하다. 즉, 참인 모든 사실을 증명할 수 있는 충분한 도구를 체계가 제공한다.

괴델의 완전성 정리는 특히 일차 술어 논리 체계가 양의 완전성을 가짐을 보였다. 이 정리의 한 가지 중요한 결과는 어떤 일차 논리식이 모순이 아닌 경우(즉, 그 부정이 논리적으로 타당하지 않은 경우), 그 논리식을 참으로 만드는 어떤 모형이 반드시 존재한다는 것이다. 이는 콤팩트성 정리로 이어지며, 무한한 공리 집합이 모형을 가질 조건을 설명한다.

완전성 정리의 증명은 일반적으로 헤닌의 방법을 사용하여, 증명 불가능한 문장에 대한 반례 모형을 구성하는 방식으로 이루어진다. 이 정리는 형식 체계의 능력에 대한 강력한 보장을 제공하지만, 괴델의 불완전성 정리는 이와 대비되며, 페아노 공리계와 같은 충분히 강력한 체계에서는 증명도 반증도 할 수 없는 문장이 존재함을 보여준다.

기호 논리학은 수학 기초론의 핵심적인 분석 도구로 작용하며, 수학적 명제의 구조를 명확히 하고 수학적 추론의 엄밀성을 확보하는 데 기여했다. 특히 19세기 말부터 20세기 초에 걸쳐 발생한 수학 기초의 위기 속에서 수학의 엄밀한 토대를 마련하려는 시도, 즉 수학 기초론 운동의 중심에 기호 논리학이 있었다. 이 운동은 크게 논리주의, 직관주의, 형식주의로 나뉘며, 각 입장은 기호 논리학을 통해 자신의 철학적 주장을 체계화하고자 했다.

논리주의의 대표적 인물인 고틀로프 프레게와 버트런드 러셀은 수학이 논리학의 한 갈래라고 주장했다. 프레게는 개념 기호를 창안하여 산술을 논리 체계 내로 환원하려 했으며, 러셀은 알프레드 화이트헤드와 함께 『수학 원리』를 집필하여 수학의 대부분을 기호 논리 체계로 유도하고자 했다. 그러나 러셀의 역설과 같은 문제가 발생하면서 이들의 계획은 근본적 난관에 부딪혔다. 형식주의의 창시자 다비트 힐베르트는 수학을 무모순적인 형식 체계로 공리화하는 힐베르트 계획을 제안했고, 이 계획의 실행을 위해 기호 논리의 방법론이 필수적이었다. 힐베르트는 메타수학을 통해 수학 체계 자체의 무모순성을 유한한 방법으로 증명하려 했으나, 쿠르트 괴델의 불완전성 정리에 의해 그 한계가 드러났다.

기호 논리학의 발전은 수학 기초론의 핵심 문제들을 정밀하게 규정하고 탐구하는 토대를 제공했다. 괴델의 불완전성 정리, 앨런 튜링의 정지 문제에 대한 연구, 폴 코언의 강제법을 통한 연속체 가설의 독립성 증명 등은 모두 기호 논리학의 언어와 방법론 없이는 불가능했을 성과들이다. 이로써 기호 논리학은 단순한 도구를 넘어 집합론, 모형 이론, 계산 가능성 이론 등 현대 수학 기초론의 여러 분과를 연결하는 기초 학문으로 자리 잡게 되었다.

기호 논리학은 컴퓨터 과학의 이론적 기초를 형성하는 핵심 학문이다. 특히 디지털 회로 설계, 프로그래밍 언어의 의미론, 알고리즘 검증, 인공지능의 지식 표현 및 추론 등 광범위한 분야에 응용된다.

디지털 논리 회로는 명제 논리의 진리표와 논리 연산을 물리적으로 구현한 것이다. 기본적인 논리 게이트인 AND 게이트, OR 게이트, NOT 게이트는 각각 논리합, 논리곱, 부정 연산에 대응하며, 이들의 조합으로 복잡한 산술 논리 장치(ALU)와 중앙 처리 장치(CPU)가 설계된다. 불 대수는 이러한 회로의 분석과 최적화를 위한 수학적 도구로 사용된다.

프로그램 정확성 증명과 형식 검증 분야에서는 술어 논리가 핵심적 역할을 한다. 호아르 논리는 프로그램의 정확성을 논리적으로 증명하기 위한 체계로, 프로그램 문장 앞뒤의 전제조건과 후건조건을 논리식으로 표현한다. 또한, 형식 명세 언어인 Z 표기법이나 VDM은 복잡한 소프트웨어 시스템의 요구사항을 정밀하게 기술하기 위해 술어 논리를 활용한다. 컴파일러 최적화와 정적 분석 도구도 프로그램의 동작을 추론하고 오류를 발견하는 데 논리적 기법을 사용한다.

인공지능 분야에서 기호 논리학은 지식 표현과 추론의 핵심적인 수학적 기초를 제공한다. 초기 인공지능 연구는 인간의 사고 과정을 기호 조작으로 모델링하는 기호주의 AI 접근법이 주류를 이루었으며, 이때 명제 논리와 술어 논리는 세계에 대한 지식을 정형적으로 표현하고, 그 지식으로부터 새로운 결론을 도출하는 데 필수적인 도구였다. 지식 베이스는 논리식의 집합으로 구성되며, 추론 엔진은 논리적 함의 관계를 이용해 질의에 대한 답을 찾거나 새로운 사실을 증명한다.

구체적으로, 술어 논리는 객체, 속성, 관계를 표현하는 데 적합하여, "모든 사람은 죽는다"나 "소크라테스는 사람이다" 같은 사실을 정확히 서술할 수 있다. 이를 통해 "소크라테스는 죽는다"라는 결론을 연역적 추론으로 얻어낼 수 있다. 이러한 방식은 전문가 시스템의 핵심이 되었다. 또한, 계획 문제는 주어진 초기 상태, 목표 상태, 가능한 행동들을 논리식으로 표현한 후, 목표를 만족시키는 행동 순서를 찾는 것으로 형식화될 수 있다.

한계와 발전 측면에서, 전통적인 기호 논리 기반 접근법은 프레임 문제나 단조 논리의 한계 같은 이론적·실용적 난제에 부딪혔다. 이는 불완전하거나 변화하는 세계에 대한 지식 처리를 복잡하게 만든다. 이에 대한 대응으로, 비단조 논리, 상황 산술, 지식과 행동에 대한 논리 등 다양한 새로운 논리 체계가 인공지능 연구 내에서 개발되었다. 최근의 기계 학습 중심 패러다임에서도, 논리 프로그래밍 언어나 자동 정리 증명 기술은 여전히 설명 가능한 AI와 형식 검증 같은 분야에서 중요한 역할을 계속하고 있다.

고전 논리는 아리스토텔레스에 의해 체계화된 삼단논법을 중심으로 한 전통적인 논리 체계를 가리킨다. 이는 주어와 술어로 구성된 명제들 간의 관계를 분석하며, '모든 A는 B이다'와 같은 정언 명제의 형식을 다룬다. 고전 논리는 2,000년 이상 서양 사고의 근간을 이루었으나, 관계 논리나 복합 명제의 내부 구조를 체계적으로 분석하는 데 한계가 있었다.

19세기 중후반에 이르러 조지 불, 고틀로프 프레게, 주세페 페아노 등의 학자들이 논리학에 수학적 방법을 도입하면서 현대 논리가 태동하기 시작했다. 불은 명제의 진리값을 대수적으로 다루는 불 대수를 개발했고, 프레게는 1879년 저서 《개념기호》에서 양화사와 함수를 포함한 완전한 1차 논리 체계를 최초로 공식화했다[9]. 이로써 논리학은 철학의 한 분과에서 독립된 형식 과학으로 변모했다.

20세기 초 버트런드 러셀과 알프레드 노스 화이트헤드는 《수학 원리》에서 논리학을 수학의 기초로 삼으려는 논리주의 프로그램을 추진했다. 그러나 쿠르트 괴델의 불완전성 정리는 그러한 포괄적 체계의 한계를 보여주었다. 한편, 데이비드 힐베르트의 형식주의와 증명 이론, 알프레드 타르스키의 모형 이론 등 현대 논리학의 주요 분야가 확립되며 급속히 발전했다.

이 발전은 다음과 같은 핵심적 전환을 포함한다.

이러한 전환을 통해 논리학은 정밀한 기호 체계를 바탕으로 무한, 진리, 계산 가능성 같은 근본 문제를 탐구할 수 있는 강력한 도구가 되었다.

아리스토텔레스는 연역적 추론의 체계를 확립하고 삼단논법을 체계화하여 고전 논리학의 기초를 마련했다. 그의 저서 『오르가논』은 논리학을 하나의 학문 분야로 정립하는 데 결정적인 역할을 했다. 이후 중세 스콜라 철학자들에 의해 논리학이 계승되고 발전되었다.

19세기 중반, 조지 불은 논리를 대수적 형식으로 표현하는 불 대수를 창시했다. 그의 저서 『사유의 법칙에 관한 연구』는 명제 논리의 수학적 토대를 제공했다. 거의 같은 시기, 고틀로프 프레게는 술어 논리를 완성하고 『개념 표기』를 출판하여 현대 기호 논리학의 기초를 세웠다. 그는 양화사와 변항의 개념을 도입하여 아리스토텔레스의 논리를 넘어선 체계를 구축했다.

20세기 초, 버트런드 러셀과 알프레드 노스 화이트헤드는 『수학 원리』에서 형식 논리 체계를 정교화하고 러셀의 역설을 해결하기 위한 유형 이론을 제안했다. 데이비드 힐베르트는 공리적 방법을 강조하고 증명 이론을 발전시켜 수학 기초론에 큰 영향을 미쳤다. 쿠르트 괴델은 불완전성 정리를 증명하여 형식 체계의 한계를 보여주었다.

이후 알론조 처치는 람다 대수를 개발했고, 앨런 튜링은 튜링 기계 개념을 통해 계산 가능성 이론에 기여했다. 솔 크립키는 가능세계 의미론을 제시하여 양상 논리의 발전에 중요한 역할을 했다. 이들의 작업은 컴퓨터 과학과 인공지능의 이론적 토대를 형성하는 데 결정적이었다.