정의
1차 논리(First‑order logic, FOL)는 수학 및 철학·컴퓨터 과학 등에서 사용되는 형식 체계 중 하나로, 개체 변수에 대한 양화사(전체 양화사 ∀, 존재 양화사 ∃)를 허용하고, 이 변수들이 가리키는 대상에 대한 관계와 함수를 표현할 수 있는 논리 체계이다. 명제 논리와 달리 개체에 대한 속성(predicate)과 함수(term)를 이용하여 보다 풍부한 서술이 가능하다.
개요
1차 논리는 19세기 말 고트롤트 프레게(Gottlob Frege)의 Begriffsschrift(1879)와 러셀이 제시한 논리 기호 체계에 뿌리를 두며, 이후 버트런드 러셀·알프레드 노스 화이트헤드의 Principia Mathematica(1910‑1913)와 데이비드 힐베르트·카르트‧노르베르그의 형식주의 프로그램을 거쳐 현대 논리학의 핵심 체계로 정립되었다. 1930년대 알프레드 터링과 클로드 쉐넬(Claude Shannon) 등은 1차 논리를 수리논리와 전산학에 적용하였으며, 20세기 중반에는 커트 괴델(Kurt Gödel)의 완전성 정리와 컴팩트성 정리, 그리고 마틴 하이더(Martin‑Hilbert)·에드워드 쿠라스키(Edward Kuratowski)의 모델 이론이 정립되면서 이론적 기반이 크게 확장되었다. 현재 1차 논리는 인공지능, 자동 정리 증명, 데이터베이스 이론 등 다양한 분야에서 활용된다.
어원/유래
- 1차: ‘첫 번째 차수(order)’를 뜻하는 한국어 어휘로, 논리 체계가 변수에 대해 ‘첫 번째 차수(개체 수준)’만을 양화한다는 의미에서 차용되었다.
- 논리: 고대 그리스어 logikē(λόγική)에서 유래한 ‘논증·사고의 법칙’을 뜻한다.
따라서 ‘1차 논리’는 ‘첫 번째 차수(개체 수준)의 논리’를 의미한다.
특징
-
문법(시스템)
- 용어: 상수, 변수, 함수 기호, 술어 기호, 논리 연결자(¬, ∧, ∨, →, ↔), 양화사(∀, ∃).
- 항(term): 변수·상수·함수 기호의 조합으로 구성.
- 원자 공식(atom): 술어 기호와 항들의 조합(예: P(x, f(y))).
- 공식: 원자 공식에 논리 연결자와 양화사를 적용하여 만든 복합식.
-
의미론(시맨틱스)
- 구조(structure, 모델): 개체의 비어 있지 않은 집합 D와 각 기호에 대한 해석(상수 → D, 함수 → Dⁿ→D, 술어 → Dⁿ→{True, False}).
- 진리 정의: 공식이 구조에서 만족되는지 여부에 따라 참·거짓이 결정된다.
-
형식적 성질
- 완전성(Theorem): 모든 참인 1차 논리 공식은 연역 시스템(예: 자연 연역, Hilbert 체계)으로 증명 가능함(Gödel, 1930).
- 음성(완비성)(Decidability): 일반적인 1차 논리(전술적 언어) 자체는 완전 결정 가능하지 않다(Church, Turing, 1936). 다만 제한된 서브클래스(예: 결정가능한 이론, 무한히 제한된 도메인)는 결정 가능성이 있다.
- 컴팩트성(Compactness): 모든 유한 부분집합이 동시에 만족 가능한 경우 전체 집합도 만족한다(Gödel, 1930).
- 완전성 및 일관성: 증명 체계가 일관성을 유지하면서 모든 논리적 진리를 포괄한다.
-
응용
- 자동 정리 증명: 정리 입증 프로그램(예: Coq, Isabelle, Prover9).
- 데이터베이스 질의: 관계형 데이터베이스의 질의 언어(SQL)는 1차 논리의 변형에 기반한다.
- 인공 지능: 지식 표현과 추론(예: 설명 논리, 온톨로지)에서 핵심 이론으로 활용된다.
관련 항목
- 명제 논리: 양화사가 없는 논리 체계로, 1차 논리의 하위 체계.
- 고차 논리(Higher‑order logic): 변수에 함수·술어 자체를 양화하는 논리 체계.
- 모델 이론: 1차 논리 공식의 모델을 연구하는 분야.
- 정형 언어(Formal language): 논리 체계의 구문을 정의하는 형식 언어.
- 컴팩트성 정리, 완전성 정리, 완비성(Decidability): 1차 논리와 관련된 핵심 정리들.
- 자동 정리 증명 시스템(Automated theorem proving), 설명 논리(Description logic).