일계논리(first-order logic)는 명제논리에서 하나의 단위로 취급하던 명제를 변수, 함수, 관계, 한정기호를 사용하여 분석하는 논리 체계이다. 이를 이용하면 대수적 구조나 순서구조처럼 수학에서 다루는 많은 대상을 하나의 형식언어 안에서 표현할 수 있다.
이 책에서는 등호를 논리기호로 포함하는 일계논리를 다룬다. 명제논리와의 연결을 단순하게 하기 위하여 \(\neg,\to,\forall\)를 기본 논리기호로 사용하고, 나머지 결합자와 존재 한정기호는 약어로 사용한다. 즉 12장에서와 같이 \(\neg\), \(\to\)를 사용하여 \(\wedge\), \(\vee\), \(\leftrightarrow\)를 정의하고 \[ (\exists x)\phi:=\neg(\forall x)\neg\phi \] 로 둔다.
정의 14.1. (일계논리언어)
일계논리언어 \(\mathcal L\)은 다음 기호들로 이루어진다.
- 가산 개의 변수(variable) \(x_0,x_1,x_2,\ldots\)
- 논리기호 \(=,\neg,\to,\forall\) 및 괄호와 쉼표
- 각각 고정된 항수(arity)를 갖는 함수기호(function symbol)와 관계기호(relation symbol)
- 상수기호(constant symbol)
함수기호, 관계기호, 상수기호를 \(\mathcal L\)의 비논리기호라고 부른다. 상수기호를 \(0\)항 함수기호로 보아도 된다.
뒤의 완전성 정리에서는 비논리기호가 가산 개인 언어를 먼저 다룬다. 구문론과 의미론 자체는 이러한 가산성 가정 없이도 정의할 수 있다.
정의 14.2. (항)
항(term)은 다음 재귀규칙을 사용하여 정의한다.
- 변수와 상수기호는 항이다.
- \(f\)가 \(n\)항 함수기호이고 \(t_1,\ldots,t_n\)이 항이면 \[ f(t_1,\ldots,t_n) \] 도 항이다.
이 규칙에 의하여 얻어지는 것만을 항이라고 부른다.
정의 14.3. (아톰논리식과 논리식)
아톰논리식(atomic formula)은 다음 두 꼴의 논리식이다.
- \(R\)이 \(n\)항 관계기호이고 \(t_1,\ldots,t_n\)이 항일 때 \[ R(t_1,\ldots,t_n), \]
- \(t_1,t_2\)가 항일 때 \[ t_1=t_2. \]
일계논리의 논리식은 다음 재귀규칙을 사용하여 정의한다.
- 아톰논리식은 논리식이다.
- \(\phi,\psi\)가 논리식이면 \(\neg\phi\)와 \(\phi\to\psi\)는 논리식이다.
- \(\phi\)가 논리식이고 \(x\)가 변수이면 \((\forall x)\phi\)는 논리식이다.
이 규칙에 의하여 얻어지는 것만을 논리식이라고 부른다. \(\wedge\), \(\vee\), \(\leftrightarrow\), \(\exists\)가 들어간 식은 앞에서 정한 약어를 풀어 논리식으로 해석한다.
문제 14.1. 상수기호 \(c\), 1항 함수기호 \(f\), 2항 함수기호 \(g\), 1항 관계기호 \(P\), 2항 관계기호 \(R\)를 갖는 언어 \(\mathcal L\)을 생각하자. 다음 각 문자열을 항, 아톰논리식, 아톰논리식이 아닌 논리식, 잘 만들어진 식이 아님 중 하나로 분류하시오.
- \(x\).
- \(g(x,f(c))\).
- \(P(f(x))\).
- \(R(g(x,c),f(c))\).
- \(g(P(x),c)\).
- \((\forall x)R(x,f(y))\).
- \(\neg P(c)\to R(x,c)\).
각 경우에 재귀적 정의의 어느 규칙을 사용했는지도 설명하시오.
정의 14.4. (자유변수와 묶인변수)
논리식 안의 변수는 기호 자체가 아니라 각 발생(occurrence)을 기준으로 자유로운지 묶여 있는지를 판단한다. \((\forall x)\phi\)에서 \(\phi\)를 이 한정기호의 유효범위(scope)라고 부른다. 이 범위 안에 있는 \(x\)의 자유로운 발생은 \(\forall x\)에 의하여 묶인다.
어떤 한정기호에도 묶이지 않은 변수를 자유변수(free variable)라고 부르고, 한정기호에 묶인 변수를 묶인변수(bound variable)라고 부른다. 자유변수가 하나도 없는 논리식을 문장(sentence)이라고 부른다.
같은 변수기호가 한 논리식에서 자유롭게도, 묶여서도 나타날 수 있다. 예를 들어 \[ P(x)\to(\forall x)Q(x) \] 에서 첫 번째 \(x\)는 자유롭고 뒤의 두 \(x\)는 \(\forall x\)에 묶여 있다.
문제 14.2. 다음 각 논리식에서 자유변수들의 집합을 구하시오. 또한 묶인변수가 존재하는 경우 그 변수가 어떤 한정기호에 묶여 있는지 표시하시오.
- \(R(x,y)\to(\forall y)P(y)\).
- \((\forall x)(R(x,y)\to(\exists y)S(x,y))\).
- \((\forall x)(\exists y)R(x,y)\).
- \((\forall x)P(x)\to Q(x)\).
정의 14.5. (치환)
항 \(u\)에서 변수 \(x\)를 항 \(t\)로 바꾼 결과를 \(u[t/x]\)로 나타낸다. 논리식 \(\phi\)에서는 변수 \(x\)의 자유로운 발생만을 \(t\)로 바꾸고 그 결과를 \(\phi[t/x]\)로 나타낸다. 이때 \(t\)에 나타나는 어떤 변수도 치환 과정에서 새로 한정기호에 묶이지 않으면 “\(t\)가 \(\phi\)에서 \(x\)에 대해 자유롭게 대입 가능하다(free for \(x\))”라고 표현한다.
예를 들어 \(\phi=(\forall y)R(x,y)\)에서 \(y\)는 \(x\)에 대해 자유롭게 대입 가능하지 않다. 단순히 \(x\)를 \(y\)로 바꾸면 원래 자유로웠던 변수가 \(\forall y\)에 포획되기 때문이다. 뒤의 전칭 예화 공리에서는 이 조건이 필요하다.
문제 14.3. 논리식 \(\phi\)가 다음과 같이 주어졌다고 하자. \[ \phi=R(x,y)\to(\forall y)S(x,y) \] \(c\)는 상수기호이고 \(f\)는 1항 함수기호이며 \(z\)는 \(x,y\)와 다른 변수이다.
- \(\phi\)를 구하시오.
- \(y\)가 \(\phi\)에서 \(x\)에 대해 자유롭게 대입 가능한지 판정하고 이유를 설명하시오.
- \(f(z)\)가 \(\phi\)에서 \(x\)에 대해 자유롭게 대입 가능한지 판정하고, 가능하면 \(\phi[f(z)/x]\)를 구하시오.
- 묶인변수의 이름을 바꾸어 \[ \psi=R(x,y)\to(\forall z)S(x,z) \] 로 쓰자. 이제 \(y\)가 \(\psi\)에서 \(x\)에 대해 자유롭게 대입 가능한지 판정하고 \(\psi[y/x]\)를 구하시오.
문제 14.4. 다음 논리식을 기본 논리기호 \(\neg\), \(\to\), \(\forall\)만 사용하도록 약어를 모두 풀어 쓰시오.
- \((\exists x)P(x)\).
- \(P(x)\wedge Q(x)\).
- \((\exists x)(P(x)\vee Q(x))\).
- \((\forall x)(P(x)\leftrightarrow Q(x))\).
일계논리를 실제 수학에 적용하는 예를 살펴보자. 군을 다루는 언어 \[ \mathcal L_{\mathrm{grp}}=\{\mu,\iota,\epsilon\} \] 을 생각하자. 여기서 \(\mu\)는 2항 함수기호, \(\iota\)는 1항 함수기호, \(\epsilon\)은 상수기호이다. 다음 문장들은 각각 결합법칙, \(\epsilon\)이 항등원이라는 조건, \(\iota(x)\)가 \(x\)의 역원이라는 조건을 나타낸다.
\[ \begin{aligned} &(\forall x)(\forall y)(\forall z)\bigl(\mu(\mu(x,y),z)=\mu(x,\mu(y,z))\bigr),\\[3pt] &(\forall x)\bigl((\mu(x,\epsilon)=x)\wedge(\mu(\epsilon,x)=x)\bigr),\\[3pt] &(\forall x)\bigl((\mu(x,\iota(x))=\epsilon)\wedge(\mu(\iota(x),x)=\epsilon)\bigr). \end{aligned} \]
여기서는 항등원과 역원 함수가 언어의 기호로 이미 지정되어 있는데, 이러한 상황을 “위 문장들은 그 기호들이 원하는 성질을 가진다”라고 표현한다. 항등원과 역원의 존재 자체를 표현하려면 \(\epsilon\), \(\iota\)를 쓰지 않고 존재 한정기호를 사용하여 나타낼 수도 있다.
문제 14.5. 군의 언어 \(\mathcal L_{\mathrm{grp}}=\{\mu,\iota,\epsilon\}\)을 사용하여 다음 조건을 각각 하나의 문장으로 나타내시오.
- 연산 \(\mu\)는 교환법칙을 만족시킨다.
- 모든 원소는 자기 자신의 역원이다.
- 항등원이 아닌 원소 \(x\) 중 \(\mu(x,x)=\epsilon\)을 만족시키는 것이 존재한다.
- 역원 함수를 두 번 적용하면 원래 원소로 돌아온다.
각 문장에 자유변수가 없음을 확인하시오.