일계논리(first-order logic)는 명제논리의 단점을 보완한 논리 체계로, 수학에서 다루는 대부분의 대상을 형식적으로 표현할 수 있게 해준다.
일계논리의 두 가지 중요한 특징은 다음과 같다.
- 관계, 함수, 상수 등을 다루는 수학적 구조에 관한 진술이 기본단위가 될 수 있다. 예를 들어 두 함수가 같을 조건이나 특정 관계를 만족시키는 원소들에 대해 논할 수 있다.
- 한정사(quantifier)를 사용할 수 있다. 주어진 범위의 모든 대상에 대한 진술(전칭 한정사)이나 범위의 일부 원소에 대한 진술(존재 한정사)을 다룰 수 있다.
일계논리의 구성 요소
일계논리의 언어는 적용 분야에 따라 달라지지만, 모든 일계논리 언어는 다음 요소들을 포함한다.
- 함수기호(function symbol): 함수를 나타내는 형식적 기호
- 관계기호(relation symbol): 관계를 나타내는 형식적 기호
- 상수기호(constant symbol): 특정 원소를 나타내는 형식적 기호
- 변수(variable): 논리구조에서 임의의 원소를 가리키는 기호
- 논리기호: 등호(\(=\)), 결합자(\(\lnot,\, \vee,\, \wedge,\, \rightarrow,\, \leftrightarrow\)), 한정기호(\(\exists,\, \forall\)), 괄호와 쉼표
명제논리에서는 명제변수와 결합자, 괄호만을 사용했던 것에 비해, 일계논리는 더 풍부한 표현이 가능하다.
일계논리에서는 먼저 항(term)을 정의한다.
- 하나의 변수는 항이다.
- 하나의 상수기호는 항이다.
- \(f\)가 \(n\)항함수기호이고 \(t_1, \,t_2, \,\ldots, \,t_n\)이 항이면 \(f(t_1, \,t_2, \,\ldots, \,t_n)\)은 항이다.
다음으로 아톰논리식(atomic formula)을 정의한다.
- \(R\)이 \(n\)항관계기호이고 \(t_1, \,t_2, \,\ldots,\, t_n\)이 항이면 \(R(t_1, \,t_2, \,\ldots,\, t_n)\)은 아톰논리식이다.
- \(t_1\)과 \(t_2\)가 항이면 \((t_1 = t_2)\)는 아톰논리식이다.
마지막으로 논리식(formula)을 정의한다.
- 아톰논리식은 논리식이다.
- \(\phi\)와 \(\psi\)가 논리식이면 \((\phi \wedge \psi)\), \((\phi \vee \psi)\), \((\lnot \phi)\), \((\phi \rightarrow \psi)\), \((\phi \leftrightarrow \psi)\)는 모두 논리식이다.
- \(\phi\)가 논리식이고 \(x\)가 변수이면 \((\exists x)\phi\)와 \((\forall x)\phi\)는 모두 논리식이다.
한정기호와 관련하여 자유변수(free variable)와 묶인변수(bounded variable)라는 개념이 중요하다. 변수 \(x\)가 \((\forall x)\phi\) 또는 \((\exists x)\phi\)의 유효범위 내에 있을 때 \(x\)는 묶인변수이며, 그렇지 않은 변수는 자유변수이다. 자유변수가 없는 논리식을 문장(sentence)이라고 부른다.
일계논리의 활용 예
일계논리를 실제 수학에 적용하는 예를 살펴보자. 군론에서는 다음과 같은 문장들로 군을 정의할 수 있다. \[\begin{aligned} & (\forall x)(\forall y)(\forall z)(\mu(\mu(x\,,y),\,z) = \mu(x,\,\mu(y,\,z))) \\[6pt] & (\forall x)((\mu(x,\,\epsilon) = x) \wedge (\mu(\epsilon,\,x) = x)) \\[6pt] & (\forall x)((\mu(x,\,\iota(x)) = \epsilon) \wedge (\mu(\iota(x),\,x) = \epsilon)) \end{aligned}\] 이 문장들은 각각 연산의 결합법칙, 항등원의 존재성, 역원의 존재성을 나타낸다. 명제논리로는 이러한 복잡한 수학적 구조와 관계를 표현할 수 없으므로, 일계논리가 수학의 형식화에 중요한 역할을 한다.