논리학, 그 열네 번째 이야기 | 1차 논리 ( First Order Logic )

1차 논리란, 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리 체계를 말한다. 명제논리와는 달리 변수에 대하여 한정 기호를 사용할 수 있으나, 변수들의 집합에 대한 한정 기호는 사용할 수 없다. 1차 논리라는 이름에서 알 수 있듯이 2차 논리, 3차 논리 등도 정의할 수 있으며, 일반적으로 2차 이상의 술어 논리를 고차 논리라고 한다. 이들에 대해서는 추후에 다루도록 하겠다. 1차 논리와 명제논리의 가장 큰 차이점은 양화사의 존재이다. 이런 점에서 본다면, 1차 논리는 명제논리를 일반화한 개념으로 볼 수 있다. 집합론의 언어 역시 1차 논리로 구성되어 있으며, 대수학에서 다루는 체의 언어^[각주:1] 역시 1차 논리로 구성된 언어이다. 그렇다면 1차 논리가 왜 필요할까? 예를 들어 다음과 같은 두 명제를 생각해보자.

소크라테스는 철학자이다.
플라톤은 철학자이다.

명제논리에서는 위 두 명제는 $\mathcal{B}$와 $\mathcal{C}$와 같이 전혀 상관 없는 두 명제로 고려된다. 하지만 우리는 위 두 명제가 분명히 어떤 관계가 있음을 알고 있다. 두 명제 모두 "$x$는 철학자이다."라는 공통된 구조를 가지기 때문이다. 하지만, 명제논리에서는 "$x$는 철학자이다."와 같이 명제에 변수가 있는 것은 허용되지 않는다. 그렇기에 변수를 허용하는 1차 논리가 도입되어야 하는 것이며, 1차 논리에서는 "$x$는 철학자이다."라는 술어의 변수 $x$의 자리에 소크라테스, 플라톤을 대입하면 위의 두 명제를 얻어낼 수 있다. 또한, 1차 논리가 도입되면, 다음과 같은 명제 역시 존재할 수 있다. 

모든 $x$에 대하여, $x$가 철학자라면, $x$는 학자이다.

이 명제와 앞서 예시로 들었던 두 명제로부터 다음과 같은 귀결을 얻을 수 있을 것이다.

소크라테스는 학자이다.
플라톤은 학자이다.

이는 명제논리에서는 할 수 없는 추론이지만 우리의 직관은 위의 추론이 매우 합당하다는 것을 알려준다. 이렇듯 우리의 직관과 명제논리 사이에는 알 수 없는 괴리가 존재하며, 이러한 괴리를 해결하기 위해서 1차 논리를 도입하게 되는 것이다. 이 외에도 1차 논리를 도입할 때 얻을 수 있는 이점은 많다. 그러면 이제 1차 논리가 어떻게 정의되는지 살펴보자. 

 

1차 논리 언어는 크게 다음의 세 가지 요소로 이루어진다.

• 특정 문자열들의 집합을 wff의 집합이라고 한다.
• 1차 논리 언어의 의미론이란, 그 언어의 문장들에 대하여 참인지 여부를 부여하는 구조이다.
• 특정 wff의 집합으로부터 다른 wff를 추론할 수 있다.

 

그러면 가장 먼저 wff가 무엇인지부터 살펴보기 위해 wff를 구성하는 문자에는 어떤 것이 있는지부터 살펴보도록 하겠다.

 

Definition 1. 1차 논리의 문자 ( Alphabet of First Order Logic )

Logical Symbols 일반적으로 1차 논리 언어의 문자에는 다음의 logical symbol들이 포함된다. 이에 대한 세부적인 사항은 책마다 다를 수 있으니 논리학 수업을 듣는 중이거나 개인적으로 공부하는 중이라면, 수업에서 사용하는 정의 또는 본인이 읽고 있는 책에서 사용하는 정의를 확실히 알아두어 이 차이로 인한 불이익이 없도록 하는 것을 추천한다. 1. 양화사 : $\forall$ 이 글에서 다루는 1차 논리의 언어에서는 전칭 기호 $\forall$만을 사용한다. 존재 기호 $\exists$에 대해서는 이 글의 마지막에서 다룰 것이다. 2. 논리 연결사(Logical Connectives) : $\Rightarrow$, $\neg$ 이 글에서 다루는 1차 논리의 언어에서는 $\Rightarrow$, $\neg$ 두 가지의 연결사만을 사용한다. 많이 사용하는 나머지 4개의 연결사 $\land$, $\lor$, $\Leftarrow$, $\Leftrightarrow$에 대해서는 이 글의 마지막에서 다룰 것이다. 이 외에도 $\uparrow$, $\downarrow$, $\oplus$ 등의 연결사를 사용하는 경우도 있지만, 이에 대해서는 설명하지 않는다. 3. 괄호(Parantheses) : $\left(\right.$, $\left.\right)$ 가독성을 신경 쓰지 않는다면 괄호가 없도록 정의할 수 있지만, 가독성을 높이기 위하여 사용한다. 4. 변수(Variables) : $v_1, v_2, v_3, \cdots$ 1차 논리 언어의 변수의 집합은 가산 무한집합 또는 유한집합이다. 5. 등호 : $=$ 사용하지 않는 경우도 있으며, 일반적으로 생각하는 등호의 의미를 가진다. 이 등호가 실제로 우리가 생각하는 등호와 같다는 것은 이후에 소개할 공리와 추론 규칙으로부터 증명 가능하다. Non-Logical Symbols 일반적으로 1차 논리 언어의 문자에는 다음의 non-logical symbol들이 포함된다. 이에 대한 세부적인 사항은 책마다 다를 수 있으니 논리학 수업을 듣는 중이거나 개인적으로 공부하는 중이라면, 수업에서 사용하는 정의 또는 본인이 읽고 있는 책에서 사용하는 정의를 확실히 알아두어 이 차이로 인한 불이익이 없도록 하는 것을 추천한다. 1. Predicate Symbols : 임의의 자연수 $n$에 대하여 $n$항 predicate symbol $P^n_0, P^n_1, P^n_2, \cdots$가 존재한다. 특히, $n=0$인 경우에는 propositional variable이라고 부르기도 한다. 2. Function Symbols : 임의의 자연수 $n$에 대하여 $n$항 function symbol $f^n_0, f^n_1, f^n_2, \cdots$가 존재한다. 특히, $n=0$인 경우에는 constant symbol이라고 부르기도 한다. Non-logical symbol의 개수에는 딱히 제한을 두지 않지만, 일반적으로는 유한 개 또는 가산 무한 개의 non-logical symbol만 있어도 충분하다. "$x$는 $y$의 아버지이다."를 $Fxy$와 같이 나타낼 수 있으며, 이때의 $F$가 $2$항 predicate symbol의 예시이다. 또한, "x의 아버지"를 $fx$와 같이 나타낼 수 있으며, 이때의 $f$가 $1$항 funcion symbol의 예시이다. 가독성을 위해 위의 예시에서의 $Fxy$를 $F(x,y)$, $fx$를 $f(x)$와 같이 쓰기도 한다.

 

Definition 2. 1차 논리의 Terms ( Terms in First Order Logic )

1차 논리 언어의 term은 다음의 규칙에 따라 재귀적으로 정의된다. 1. 모든 변수는 term이다. 2. 자연수 $n$이 주어질 때, $n$항 function symbol $f$와 $n$개의 term $t_1, t_2, \cdots, t_n$에 대하여 $f(t_1, t_2, \cdots, t_n)$은 term이다. 3. 위의 두 규칙으로부터 얻을 수 없는 문자열은 term이 아니다. 이때, 문자열은 유한 개의 문자를 나열한 것을 말한다.

 

이제 1차 논리 언어의 wff를 정의할 준비가 끝났다. 다음 정의를 보자.

 

Definition 3. 1차 논리의 wff ( Well Formed Formulas in First Order Logic; wffs in First Order Logic )

1차 논리 언어의 wff는 다음의 규칙에 따라 재귀적으로 정의된다. 1. 자연수 $n$이 주어질 때, $n$항 predicate symbol $P$와 $n$개의 term $x_1, x_2, \cdots, x_n$에 대하여 $P(x_1, x_2, \cdots, x_n)$은 wff이다. 2. 두 term $x_1$, $x_2$에 대하여 $x_1 = x_2$는 wff이다. 3. 만약 $\varphi$가 wff라면, $\left( \neg \varphi \right)$ 역시 wff이다. 4. 만약 $\varphi$와 $\psi$가 wff라면, $\left( \varphi \Rightarrow \psi \right)$ 역시 wff이다. 5. 만약 $\varphi$가 wff고, $x$가 변수라면, $\forall x \varphi$ 역시 wff이다. 6. 위의 다섯 개의 규칙으로부터 얻을 수 없는 문자열은 wff가 아니다. 이때, 문자열은 유한 개의 문자를 나열한 것을 말한다. 추가로, 1번과 2번 조건으로부터 얻어지는 wff를 원자 명제(Atomic Formulas)라고 한다.

 

예를 들어, $f$가 $1$항 function symbol이고 $P$가 $1$항 predicate symbol이며 $Q$가 $2$항 predicate symbol이고 $x$, $y$가 변수이고 $z$가 term이라면, $\forall x \forall y \left( P(f(x)) \Rightarrow \left( \neg \left( P(x) \Rightarrow Q(f(y), x, z) \right) \right) \right)$는 wff이며, $\forall x x\Rightarrow$는 wff가 아니다. 1차 논리에서도 명제논리에서와 같이 Unique Readability Theorem이 성립한다. 이에 대한 증명은 추후에 포스팅하도록 하겠다.

1차 논리에서는 자유 변수와 종속 변수의 개념이 매우 중요하다. $2$항 predicate symbol $F$에 대하여 $Fxy$가 "$x$는 $y$를 아버지로 가진다."로 해석된다고 하자. 그러면 $\forall x \exists y Fxy$는 "모든 $x$에 대하여, $x$가 $y$를 아버지로 가지도록 하는 $y$가 존재한다."로 해석될 것이며, 이는 분명히 참인 명제이다. 하지만, $\forall x Fxy$는 "모든 $x$에 대하여 $x$는 ___를 아버지로 가진다."로 해석될 것이며, 이것을 참이라고 하는 것도, 거짓이라고 하는 것도 말이 되지 않는다. 이것이 참인지 거짓인지를 결정하기 위해서는 빈칸이 채워져야 할 것이다. 이렇듯 어떤 wff에 대하여 이 wff가 참인지, 거짓인지의 여부를 결정할 수 있는지를 따지기 위해서 수학자들은 자유 변수와 종속 변수의 개념을 정의하였다. 다음 정의를 보자.

 

Definition 4. 자유 변수와 종속 변수 ( Free Variables & Bound Variables )

자유 변수는 다음의 규칙에 따라 재귀적으로 정의된다. 1. 원자 명제 $\varphi$에 대하여 $x$가 $\varphi$의 자유 변수인 것은 $x$가 $\varphi$의 변수인 것과 동치이다. 2. $x$가 $\left( \neg \varphi \right)$의 자유 변수인 것은 $x$가 $\varphi$의 자유 변수인 것과 동치이다. 3. $x$가 $\left( \varphi \Rightarrow \psi \right)$의 자유 변수인 것은 $x$가 $\varphi$의 자유 변수이거나 $\psi$의 자유 변수인 것과 동치이다. 4. $x$가 $\forall y \varphi$의 자유 변수인 것은 $x$가 $\varphi$의 자유 변수이면서 $x \neq y$인 것과 동치이다. 또한, 종속 변수는 다음의 규칙에 따라 재귀적으로 정의된다. 1. 원자 명제 $\varphi$는 종속 변수를 가지지 않는다. 2. $x$가 $\left( \neg \varphi \right)$의 종속 변수인 것은 $x$가 $\varphi$의 종속 변수인 것과 동치이다. 3. $x$가 $\left( \varphi \Rightarrow \psi \right)$의 종속 변수인 것은 $x$가 $\varphi$의 종속 변수이거나 $\psi$의 종속 변수인 것과 동치이다. 4. $x$가 $\forall y \varphi$의 종속 변수인 것은 $x$가 $\varphi$의 종속 변수이거나 $x=y$인 것과 동치이다. 이때, 위 규칙의 서술에 사용된 $\varphi$와 $\psi$는 wff이며, $x$는 변수이다.

 

예를 들어, $\forall x \forall y \left( P(f(x)) \Rightarrow \left( \neg \left( P(x) \Rightarrow Q(f(y), x, z) \right) \right) \right)$에서 $x$, $y$는 종속 변수이며, $z$는 자유 변수이고, $w$는 종속 변수도, 자유 변수도 아니다. 또한, 변수 $x$가 wff $\varphi$의 종속 변수이면서 동시에 자유 변수일 수 있다. 예를 들어, $P(x) \Rightarrow \forall x Q(x)$에서 $x$는 자유 변수임과 동시에 종속 변수이다.

만약 Definition 4에서 서술된 정의가 수학적으로 엄밀하지 않다고 생각한다면, 원자명제 $\alpha$에 대하여 함수 $h(\alpha)$가 $\alpha$의 변수의 집합으로 정의될 때, $h$의 정의역을 wff의 집합으로 확장한 함수 $\bar{h}$를 Recursion Theorem을 이용하여 정의할 수 있으며, 이 경우, 임의의 wff $\varphi$에 대하여 $\bar{h}(\varphi)$가 $\varphi$의 자유 변수의 집합이 된다. 종속 변수의 개념 역시 비슷하게 할 수 있다.

또한, 자유 변수를 가지지 않는 wff를 문장(Sentence)이라고 한다.

 

이제 1차 논리의 의미론에 대해 알아보자. 1차 논리의 의미론이란, 위에서 언급했듯이 특정 wff에 참 또는 거짓을 부여하는 것을 말한다. 1차 논리에서는 명제논리에서와는 달리, 참/거짓의 개념이 부여된 구조에 따라 다르다. 이에 대해서는 뒤에서 다시 언급하도록 하겠다. 그러면 먼저 구조가 무엇인지 살펴보도록 하자.

 

Definition 5. 1차 논리의 구조 ( Structure for First Order Logic )

형식적으로, 1차 논리 언어의 구조는 다음 조건을 만족하는 함수 $\mathfrak{A}$를 말한다. 1. $\mathfrak{A}$는 양화사 $\forall$를 $\mathfrak{A}$의 Universe $\lvert \mathfrak{A} \rvert$로 대응시킨다. 이때, $\lvert \mathfrak{A} \rvert$는 공집합이 아니다. 보통 $\lvert \mathfrak{A} \rvert$는 집합이지만, 때로는 고유모임도 허용한다. 2. $\mathfrak{A}$는 각 $n$항 predicate symbol $P$를 $\lvert \mathfrak{A} \rvert$ 위의 $n$항 관계 $P^\mathfrak{A} \subseteq \lvert \mathfrak{A} \rvert^n$로 대응시킨다. 3. $\mathfrak{A}$는 각 $n$항 function symbol $f$를 함수 $f^\mathfrak{A} : \lvert \mathfrak{A} \rvert^n \to \lvert \mathfrak{A} \rvert$로 대응시긴다.

 

결국, 구조 $\mathfrak{A}$는 좀 거칠게 말하자면, non-logical symbol을 '번역'하는 함수이다. 또한, 1차 논리 언어의 문장에 참/거짓을 부여할 때 어떤 문장이 참인지 거짓인지를 결정하는 것은 결국 이 '번역'이 어떻게 되었는가이다. 앞에서 구조에 따라 참/거짓의 개념이 달라진다는 것이 바로 이를 말하는 것이다. 구조에 따른 문장의 해석의 차이를 확인하기 위해 다음 예시를 보자.

 

Example 1.

집합론의 언어를 생각해보자. 집합론의 언어는 non-logical symbol로 $2$항 predicate symbol인 $\in$만을 가진다. 여기에 다음 조건을 만족하는 구조 $\mathfrak{A}$를 부여했다고 하자.

$$ \lvert \mathfrak{A} \rvert = \mathbb{N} \\ \in^\mathfrak{A} = \{ \left( n,m \right) \;|\; n < m \} $$

이제 집합론의 언어로 쓰여진 하나의 문장을 살펴보자.

$$ \exists x \forall y \neg y \in x $$

좀 더 형식적으로 쓰자면 다음과 같이 쓰여질 것이다.

$$ \left( \neg \forall x_1 \left( \neg \forall x_2 \left( \neg \in x_2 x_1 \right) \right) \right) $$

위의 문장은 흔히 알고 있는 집합론의 언어로 해석한다면, "그 어떤 것도 원소로 가지지 않는 집합이 존재한다." 즉, 공집합의 존재성을 말하는 문장임을 알 수 있다. 하지만, 위의 문장을 구조 $\mathfrak{A}$ 하에서 해석한다면, "그 어떤 자연수도 자신보다 작지 않도록 하는 자연수가 존재한다."로 해석될 것이다. 즉, 어떤 구조를 부여하냐에 따라 같은 문장이라도 그 해석이 달라질 수 있다. 물론 위의 경우는 집합론의 관점에서도, 구조 $\mathfrak{A}$ 위에서도 참인 명제이다. 이렇게 어떤 문장이 구조 $\mathfrak{A}$ 위에서 참일 때, $\mathfrak{A}$를 해당 문장의 모형(Model)이라고 한다. 한편, 집합론의 언어의 구조 $\mathfrak{A}$는 짝공리의 모형이 아니다. 집합론의 공리 짝공리는 다음 문장을 말한다.

$$ \forall x \forall y \exists z \forall t \left( t \in z \Leftrightarrow t=x \lor t=y \right) $$

위 문장을 형식적으로 서술하면 너무 길어지므로 해당 작업은 생략하도록 하겠다. 위 문장을 구조 $\mathfrak{A}$ 하에서 해석한다면 "임의의 두 자연수 $x$, $y$에 대하여, $z$보다 작은 것이 $x$와 같거나 $y$와 같은 것과 동치이도록 하는 자연수 $z$가 존재한다."로 해석되며, 이는 자명하게 거짓이다. 집합론에 익숙하다면, 위 구조 $\mathfrak{A}$가 외연성 공리, 합집합 공리, 정칙성 공리의 모형이 된다는 것을 직접 확인해볼 수 있을 것이다.

 

위의 예시를 통해 어떤 문장 $\sigma$가 주어질 때, $\sigma$의 참/거짓 여부는 구조에 따라 달라진다는 것을 알게 되었을 것이다. 그런데, 어떤 문장 $\sigma$가 구조 $\mathfrak{A}$에서 참인지, 거짓인지를 판단하는 것을 우리의 직관에 맡기는 것이 아니라 철저히 연역적인 논증을 통해 알아내기 위해서는 "$\sigma$는 $\mathfrak{A}$ 위에서 참이다."라는 명제를 형식적으로 정의내릴 필요가 있다. 이에 대해 정의내리기 전에 가장 먼저 일반적인 wff에 대해 생각해볼 필요가 있다. 다음 정의를 보자.

 

Definition 6. Satisfaction

1차 논리 언어가 주어져 있는 상태에서 $\varphi$가 해당 언어의 wff이고, $\mathfrak{A}$가 주어진 언어의 구조이며, 주어진 언어의 변수의 집합 $V$에 대하여 함수 $s : V \to \lvert \mathfrak{A} \rvert$가 주어졌다고 하자. 이때 다음을 만족하는 $s$의 확장 $\bar{s} : T \to \lvert \mathfrak{A} \rvert$를 생각할 수 있다. 이때, $T$는 주어진 언어의 term의 집합을 말한다. 1. 각 변수 $x$에 대하여 $\bar{s}(x) = s(x)$이다. 2. $t_1, t_2, \cdots, t_n$이 모두 term이고, $f$가 $n$항 function symbol일 때, $\bar{s}(ft_1t_2\cdots t_n)=f^\mathfrak{A} \left( \bar{s}(t_1), \bar{s}(t_2), \cdots, \bar{s}(t_n) \right)$이다. 이러한 $s$의 확장 $\bar{s}$가 유일하게 존재함은 Recursion Theorem이 보장한다. $\bar{s}$가 $s$뿐 아니라 $\mathfrak{A}$에도 의존한다는 것에 주의하라. 이러한 사실 때문에 $\bar{s}(t)$를 $t^\mathfrak{A}[s]$와 같이 나타내기도 한다. 이제 wff $\varphi$에 대하여 $\models_\mathfrak{A} \varphi [s]$가 어떤 의미인지에 대하여 설명하겠다. $\models_\mathfrak{A} \varphi [s]$는 wff $\varphi$에 대하여 다음과 같은 규칙을 통해 재귀적으로 정의된다. 1. $\models_\mathfrak{A} = t_1 t_2 [s]$는 $\bar{s}(t_1) = \bar{s}(t_2)$와 동치이다. 2. $n$항 predicate symbol $P$에 대하여 $\models_\mathfrak{A} P t_1 t_2 \cdots t_n [s]$는 $\left( \bar{s}(t_1), \bar{s}(t_2), \cdots, \bar{s}(t_n) \right) \in P^\mathfrak{A}$와 동치이다. 3. $\models_\mathfrak{A} \left( \neg \varphi \right) [s]$는 $\not\models_\mathfrak{A} \varphi [s]$와 동치이다. 4. $\models_\mathfrak{A} \left( \varphi \Rightarrow \psi \right) [s]$는 $\not\models_\mathfrak{A} \varphi [s]$이거나 $\models_\mathfrak{A} \psi [s]$인 것과 동치이다. 5. $\models_\mathfrak{A} \forall x \varphi [s]$는 임의의 $d \in \lvert \mathfrak{A} \rvert$에 대하여 $\models_\mathfrak{A} \varphi [s(x|d)]$인 것과 동치이다. 이때, $s(x|d)$는 다음의 함수를 말한다. $s(x|d)(y) = \begin{cases} s(y) & \mbox{ if } y \neq x \\ d & \mbox{ if } y = x \end{cases}$

 

이제 위의 정의의 이해를 돕기 위해 예시를 하나 들어보자.

 

Example 2.

Non-logical symbol로 $2$항 predicate symbol $P$, $1$항 function symbol $f$, $0$항 function symbol $c$만을 가지는 1차 논리 언어가 주어졌다고 하자. 이제 다음을 만족하는 구조 $\mathfrak{A}$를 생각하자.

$$ \lvert \mathfrak{A} \rvert = \mathbb{N} \\ P^\mathfrak{A} = \{ \left( n,m \right) \;|\; m \leq n \} \\ f^\mathfrak{A} = S : n \mapsto n+1 \\ c^\mathfrak{A} = 0 $$

이제 함수 $s : V \to \mathbb{N}$을 $s : v_i \mapsto i-1$로 정의하자.

그러면 $\models_\mathfrak{A} P c f v_1 [s]$는 $0 \leq 1$을 의미하므로 참이 된다.

또한, $\models_\mathfrak{A} \forall v_1 P c v_1$은 모든 자연수 $n$에 대하여 $\models_\mathfrak{A} P c v_1 [s(v_1|d)]$임을 의미하며, 이는 곧 모든 자연수 $n$에 대하여 $0 \leq n$임을 의미하므로 참임을 알 수 있다.

또한, $\models_\mathfrak{A} \forall v_1 P v_2 v_1 [s]$는 거짓인데, $\not \models_\mathfrak{A} P v_2 v_1 [s(v_1|0)]$이기 때문이다.

 

이제 1차 논리 언어의 문장에 참/거짓을 부여할 때 구조에 대한 정보만 있으면 충분하다는 것에 대한 근거를 부여하는 정리에 대해 설명하려 한다. 다음 정리를 보자.

 

Theorem 1.

1차 논리 언어와 그의 구조 $\mathfrak{A}$가 주어진 상황에서 주어진 1차 논리 언어의 변수의 집합 $V$에서 $\mathfrak{A}$의 universe $\lvert \mathfrak{A} \rvert$로 가는 두 함수 $s_1$과 $s_2$가 주어졌다고 하자. 이때, 주어진 1차 논리 언어의 wff $\varphi$의 모든 자유 변수 $x$에 대하여 $s_1(x) = s_2(x)$가 성립한다면, $\models_\mathfrak{A} \varphi [s_1]$과 $\models_\mathfrak{A} \varphi [s_2]$는 동치이다.

 

Proof.

$\models_\mathfrak{A} \varphi [s]$가 재귀적으로 정의되었으므로, 증명에 귀납법을 사용할 것이다.

 

먼저, 원자 명제 $\varphi = P t_1 t_2 \cdots t_n$에 대해 생각해보자. 이 경우엔 $\varphi$의 모든 변수가 자유 변수이므로 각 term $t_i$에 대하여 $\bar{s_1}(t_i) = \bar{s_2}(t_i)$가 성립한다. 이에 대한 증명은 term $t_i$에 대한 귀납법을 이용하여 간단하게 할 수 있으므로 굳이 서술하지는 않겠다. 각 term에 대하여 $\bar{s_1}$과 $\bar{s_2}$의 함숫값이 일치하므로 $\models_\mathfrak{A} \varphi [s_1]$과 $\models_\mathfrak{A} \varphi [s_2]$는 동치이다. 등호 $=$으로 정의되는 원자 명제의 경우, 이 역시 $2$항 predicate symbol로 볼 수 있으므로 같은 논리로 증명할 수 있다.

 

이제 $\varphi = \neg \psi$인 경우와 $\varphi = \psi \Rightarrow \rho$인 경우에는 $\models_\mathfrak{A} \varphi [s]$의 정의와 귀납가정에 의해 $\models_\mathfrak{A} \varphi [s_1]$과 $\models_\mathfrak{A} \varphi [s_2]$가 동치임은 즉시 알 수 있다.

 

이제 $\varphi = \forall x \psi$인 경우를 살펴보자. 그러면 $\psi$의 자유 변수로는 $\varphi$의 자유 변수와 $x$만이 가능하다. 따라서 임의의 $d \in \lvert \mathfrak{A} \rvert$에 대하여 $s_1(x|d)$와 $s_2(x|d)$는 모두 $\psi$의 자유 변수에 대한 함숫값이 일치한다. 따라서 귀납가정에 의해 $\models_\mathfrak{A} \psi [s_1(x|d)]$와 $\models_\mathfrak{A} \psi [s_2(x|d)]$는 동치이다. 따라서 $\models_\mathfrak{A} \varphi [s_1]$과 $\models_\mathfrak{A} \varphi [s_2]$는 동치이다.

 

따라서 귀납법에 의해 정리가 증명된다.

$\blacksquare$

 

Corollary 1.1.

1차 논리 언어가 주어지고 구조 $\mathfrak{A}$가 주어졌다고 하자. 주어진 1차 논리 언어의 문장 $\sigma$에 대하여 다음 둘 중 하나가 성립한다. 1. 임의의 함수 $s : V \to \lvert \mathfrak{A} \rvert$에 대하여 $\models_\mathfrak{A} \sigma [s]$이다. 2. $\models_\mathfrak{A} \sigma [s]$인 함수 $s : V \to \lvert \mathfrak{A} \rvert$가 존재하지 않는다.

 

이는 Theorem 1에 의해 자명하므로 굳이 증명을 서술하지는 않겠다.

위 정리는 다음과 같은 표기에 타당성을 부여한다. 아래의 정의를 보자.

 

Definition 7.

1차 논리 언어가 주어지고 구조 $\mathfrak{A}$가 주어졌다고 하자. 주어진 1차 논리 언어의 wff $\varphi$의 자유 변수가 $x_1, x_2, \cdots, x_k$라고 할 때, 이들을 각각 $a_1, a_2, \cdots, a_k$로 대응시키는 함수 $s : V \to \lvert \mathfrak{A} \rvert$이므로 $\models_\mathfrak{A} \varphi [s]$를 $\models_\mathfrak{A} \varphi [[a_1, a_2, \cdots, a_k]]$로 표기한다.

 

이제 1차 논리 언어의 문장의 참과 거짓을 정의하자. 아래의 정의를 보자.

 

Definition 8. 문장의 참과 거짓 ( Truth Value of Sentence )

Corollary 1.1에서 1번 문장이 성립하는 경우, 문장 $\sigma$가 구조 $\mathfrak{A}$에서 참(True)이라고 하며, 2번 문장이 성립하는 경우엔 문장 $\sigma$가 구조 $\mathfrak{A}$에서 거짓(False)이라고 한다. 또한, 문장 $\sigma$가 구조 $\mathfrak{A}$에서 참인 경우, $\models_\mathfrak{A} \sigma$로 나타내며, $\models_\mathfrak{A} \sigma$일 때 구조 $\mathfrak{A}$를 문장 $\sigma$의 모형(Model)이라고 한다. 추가로, 문장의 집합 $\Sigma$의 임의의 원소 $\sigma$에 대하여 $\models_\mathfrak{A} \sigma$가 성립한다면, 구조 $\mathfrak{A}$를 $\Sigma$의 모형이라고 한다.

 

앞서 언급했던 것과 같이, 1차 논리 언어의 문장의 참/거짓 여부는 구조에 의존한다는 것을 Definition 8로부터 알 수 있다. 그에 대한 예시를 보자.

 

Example 3.

Non-logical symbol로 $2$항 function symbol $+$와 $\times$, $0$항 function symbol $0$과 $1$이 주어졌다고 하자.

이제 두 구조 $\mathfrak{R} = \left( \mathbb{R}; \mathbf{0}, \mathbf{1}, +, \times \right)$와 $\mathfrak{Q} = \left( \mathbb{Q}; \mathbf{0}, \mathbf{1}, +, \times \right)$를 생각해보자. 여기서 $\mathfrak{R}$과 $\mathfrak{Q}$는 각각 실수체와 유리수체를 나타낸다. 즉, $\mathbf{0}$, $\mathbf{1}$, $+$, $\times$는 모두 기존에 우리가 알던 의미와 동일한 의미를 가진다.

$$ \left( \neg \forall x \left( \neg x \times x = \mathbf{1} + \mathbf{1} \right) \right) $$

그러면 위 문장은 $\mathfrak{R}$에서는 참이며, $\mathfrak{Q}$에서는 거짓임을 알 수 있다. 즉, 같은 문장이라 할지라도 구조에 따라 참/거짓 여부가 달라질 수 있다.

 

이제 의미론적 함의 관계를 정의하자. 의미론적 함의 관계가 어떤 느낌의 개념인지에 대해서는 명제논리에 관한 다음 글을 참고하라.

 

논리학, 그 일곱 번째 이야기 | 명제논리의 Boolean Interpretation ( Boolean Interpretation for Propositional Logic )

 

Definition 9. Logically Implication

1차 논리 언어가 주어졌다고 하자. $\Gamma$를 주어진 1차 논리 언어의 wff의 집합이라고 하고 $\varphi$를 wff라고 하자. 만약 $\Gamma$의 임의의 원소 $\psi$에 대하여 $\models_\mathfrak{A} \psi [s]$를 만족는 임의의 구조 $\mathfrak{A}$와 함수 $s : V \to \lvert \mathfrak{A} \rvert$에 대하여 $\models_\mathfrak{A} \varphi [s]$가 성립한다면, 이를 $\Gamma$가 $\varphi$를 Logically Imply한다고 하며, $\Gamma \models \varphi$와 같이 나타낸다. 명제논리에서와 마찬가지로, $\Gamma = \{ \psi_1, \psi_2, \cdots, \psi_k \}$가 유한집합인 경우에는 $\psi_1, \psi_2, \cdots, \psi_k \models \varphi$와 같이 나타낼 수 있으며, $Gamma$가 공집합인 경우를 $\models \varphi$와 같이 나타낼 수 있다. $\models \varphi$인 경우, $\varphi$를 유효(Valid)하다고 하며, 두 wff $\varphi$, $\psi$에 대하여 $\varphi \models \psi$이고 동시에 $\psi \models \varphi$인 경우를 $\varphi$와 $\psi$가 Logically Equivalent하다고 하며, $\varphi \models \mathbin{\style{transform: scaleX(-1)}{\vDash}} \psi$와 같이 나타낸다.

 

Theorem 1을 적용하면, 문장 사이의 logically implication의 개념은 더 간단하게 표기될 수 있음을 알 수 있다.

 

Corollary 1.2.

문장의 집합 $\Sigma$와 문장 $\sigma$에 대하여 $\Sigma \models \sigma$는 $\Sigma$의 모든 모형이 $\sigma$의 모형이기도 한 것과 동치이며, $\sigma$가 유효한 것은 $\sigma$가 모든 구조에서 참인 것과 동치이다.

 

이제 1차 논리 언어에서의 연역에 대해 설명할 차례이다. 가장 먼저 공리부터 설명하겠다. 1차 논리 언어의 공리는 아래와 같다.

 

Axiom 1.

만약 $\alpha$, $\beta$, $\gamma$가 wff이고 $x$, $y$가 변수이고, $t$가 term이라면, 아래는 모두 공리이다. (A1) $\left( \alpha \Rightarrow \left( \beta \Rightarrow \alpha \right) \right)$ (A2) $\left( \left( \alpha \Rightarrow \left( \beta \Rightarrow \gamma \right) \right) \Rightarrow \left( \left( \alpha \Rightarrow \beta \right) \Rightarrow \left( \alpha \Rightarrow \gamma \right) \right) \right)$ (A3) $\left( \left( \left( \neg \beta \right) \Rightarrow \left( \neg \alpha \right) \right) \Rightarrow \left( \left( \left( \neg \beta \right) \Rightarrow \alpha \right) \Rightarrow \beta \right) \right)$ (Q1) $t$가 $\alpha$에서 $x$에 대해 substitutable할 때, $\left( \forall x \alpha \Rightarrow \alpha^x_t \right)$ (Q2) $x$가 $\alpha$의 자유 변수가 아닐 때, $\left( \alpha \Rightarrow \forall x \alpha \right)$ (Q3) $\left( \forall x \left( \alpha \Rightarrow \beta \right) \Rightarrow \left( \forall x \alpha \Rightarrow \forall x \beta \right) \right)$ (E1) $x=x$ (E2) $\alpha$가 원자명제이고, $\alpha'$이 $\alpha$에서 등장한 변수 $x$의 전부 또는 일부를 변수 $y$로 치환한 원자명제일 때, $\left( x=y \Rightarrow \left( \alpha \Rightarrow \alpha' \right) \right)$

 

위의 공리를 하나씩 읽다보면 뭔가 익숙치 않은 개념이 있을 것이다. 아직 이 글에서는 substitutable이 무엇인지 정의하지 않았으며, $\alpha^x_t$와 같은 표기를 정의하지 않았기 때문에 위의 공리 중 (Q1)의 의미를 정확히 이해하는 데에 어려움이 있었을 것이다. substitutable은 아래와 같이 정의되는 개념이다.

 

Definition 10. Substitutable

"term $t$가 wff $\alpha$에서 변수 $x$에 대해 substitutable하다."라는 문장은 아래의 규칙에 따라 재귀적으로 정의된다. 1. 원자명제 $\alpha$에 대하여 언제나 term $t$는 $\alpha$에서 변수 $x$에 대해 substitutable하다. 2. $t$가 $\left( \neg \alpha \right)$에서 변수 $x$에 대해 substitutable한 것은 $t$가 $\alpha$에서 변수 $x$에 대해 substitutable한 것과 동치이다. 3. $t$가 $\left( \alpha \Rightarrow \beta \right)$에서 변수 $x$에 대해 substitutable한 것은 $t$가 $\alpha$와 $\beta$ 모두에서 변수 $x$에 대해 substitutable한 것과 동치이다. 4. $t$가 $\forall y \alpha$에서 변수 $x$에 대해 substitutable한 것은 다음 줄 중 하나를 만족하는 것과 동치이다.   (a) $x$가 $\forall y \alpha$의 자유 변수가 아니다.   (b) $y$가 $t$의 변수가 아니면서 $t$가 $\alpha$에서 변수 $x$에 대해 substitutable하다.

 

$\alpha^x_t$와 같은 표기는 아래와 같이 정의된다.

 

Definition 11. Substitution

$\alpha^x_t$는 아래의 규칙에 따라 재귀적으로 정의된다. 1. 원자명제 $\alpha$에 대하여 $\alpha^x_t$는 $\alpha$에서 변수 $x$를 모두 term $t$로 치환한 명제를 나타낸다. 2. $\left( \neg \alpha \right)^x_t = \left( \neg \alpha^x_t \right)$ 3. $\left( \alpha \Rightarrow \beta \right)^x_t = \left( \alpha^x_t \Rightarrow \beta^x_t \right)$ 4. $\left( \forall y \alpha \right)^x_t = \begin{cases} \forall y \alpha & \mbox{ if } x=y \\ \forall y \alpha^x_t & \mbox{ if } x \neq y \end{cases}$

 

이제 1차 논리 언어의 모든 공리를 설명했으므로 추론 규칙에 대해 이야기할 차례이다.

1차 논리 언어의 추론 규칙은 명제논리와 마찬가지로 전건 긍정 뿐이다. 즉, 아래의 추론 규칙이 유일하다.

$$\begin{matrix} \alpha \Rightarrow \beta \\ \alpha \\ \hline \beta \end{matrix}$$

또한, 정리, 증명 등의 정의는 명제논리에서와 똑같다.

 

이제 1차 논리 언어에서 등호 $=$가 동치관계임을 증명할 차례이다. 아래의 정리를 보자.

 

Theorem 2.

1차 논리 언어에서 등호 $=$는 동치관계이다.

 

Proof.

일단, (E1)에 의해 $\vdash x=x$이다.

이제 $x=y \vdash y=x$임을 증명하자.

(E2)에서 $\alpha$를 $x=x$로, $\alpha'$을 $y=x$로 놓으면, $\vdash x=y \Rightarrow \left( x=x \Rightarrow y=x \right)$임을 알 수 있다.

따라서 Deduction Theorem에 의해 $x=y \vdash y=x$이다.

이제 $x=y, y=z \vdash x=z$임을 증명하자.

(E2)에서 $\alpha$를 $x=y$로, $\alpha'$를 $x=z$로 놓으면, $\vdash y=z \Rightarrow \left( x=y \Rightarrow x=z \right)$임을 알 수 있다.

따라서 deduction theorem에 의해 $x=y, y=z \vdash x=z$이다.

$\blacksquare$

 

위의 증명에서 명제논리의 메타정리인 deduction theorem을 사용하였는데, deduction theorem이 1차 논리에서도 성립한다는 사실은 매우 쉽게 확인할 수 있으므로 이에 대한 증명은 생략하도록 하겠다. deduction theorem 외에도 명제논리에서 사용할 수 있었던 여러 추론 규칙은 모두 1차 논리에서도 성립한다.

 

이제 글의 초반부에서 언급했었던 $\lor$, $\land$, $\Leftarrow$, $\Leftrightarrow$, $\exists$의 정의를 소개하고 글을 마치도록 하겠다.

 

Definition 11.

$\alpha$, $\beta$가 wff이고 $x$가 변수라고 하자. 그러면 $\lor$, $\land$, $\Leftarrow$, $\Leftrightarrow$, $\exists$는 다음과 같이 정의된다. 1. $\left( \alpha \lor \beta \right) = \left( \left( \neg \alpha \right) \Rightarrow \beta \right)$ 2. $\left( \alpha \land \beta \right) = \left( \neg \left( \alpha \Rightarrow \left( \neg \beta \right) \right) \right)$ 3. $\left( \alpha \Leftarrow \beta \right) = \left( \beta \Rightarrow \alpha \right)$ 4. $\left( \alpha \Leftrightarrow \beta \right) = \left( \left( \alpha \Rightarrow \beta \right) \land \left( \alpha \Leftrightarrow \beta \right) \right)$ 5. $\exists x \alpha = \left( \neg \forall x \left( \neg \alpha \right) \right)$

 

위와 같이 정의하면 우리가 흔히 아는 연산법칙이 모두 성립함을 쉽게 확인할 수 있다.

이제 1차 논리에서의 연역에서 자주 사용되는 몇 가지 정리를 살펴보자.

 

Theorem 3. Generalization Theorem

만약 $\Gamma \vdash \varphi$이고 변수 $x$를 자유변수로 가지는 $\Gamma$의 원소가 존재하지 않는다면, $\Gamma \vdash \forall x \varphi$이다.

 

Proof.

귀납법을 이용하여 증명하자.

Case 1. $\varphi$가 공리일 때.

$\varphi$가 공리라면, $\vdash \forall x \varphi$이므로 $\Gamma \vdash \forall x \varphi$ 역시 성립한다.

Case 2. $\varphi \in \Gamma$일 때.

정리의 조건에 의해 $x$는 $\varphi$의 자유변수가 아니므로 (Q2)에 의해 $\varphi \Rightarrow \forall x \varphi$가 공리이며, MP를 적용하면 $\Gamma \vdash \forall x \varphi$를 얻는다.

Case 3. $\varphi$가 $\psi \Rightarrow \varphi$, $\psi$에 MP를 적용한 결과일 때.

귀납가정에 의해 $\Gamma \vdash \forall x \left( \psi \Rightarrow \varphi \right)$이고 $\Gamma \vdash \forall x \psi$이다.

이때, (Q3)에 의해 $\forall x \left( \psi \Rightarrow \varphi \right) \Rightarrow \left( \forall x \psi \Rightarrow \forall x \varphi \right)$가 공리이며, 여기에 MP를 두 번 적용하면 $\Gamma \vdash \forall x \varphi$를 얻는다.

따라서 귀납법에 의해 정리가 증명된다.

$\blacksquare$

 

Theorem 4. Generalization on Constants

$\Gamma \vdash \varphi$이고 constant symbol $c$가 $\Gamma$의 그 어떤 원소에서도 등장하지 않는다고 하자. 그러면 $\Gamma \vdash \forall y \varphi^c_y$가 성립하도록 하는 변수 $y$가 존재한다. 더 나아가서, $c$가 전혀 등장하지 않는 $\varphi^c_y$의 $\Gamma$로부터의 연역과정이 존재한다.

 

Proof.

$\left< \alpha_0, \alpha_1, \cdots, \alpha_n \right>$가 $\varphi$의 $\Gamma$로부터의 연역과정이라고 하자. 이제 $\alpha_0, \alpha_1, \cdots, \alpha_n$에서 등장하지 않는 변수 $y$를 선택하자.

그러면 $\left< (\alpha_0)^c_y, (\alpha_1)^c_y, \cdots, (\alpha_n)^c_y \right>$가 $\varphi^c_y$의 $\Gamma$로부터의 연역과정임을 Theorem 3과 귀납법을 통해 간단히 보일 수 있다.

따라서 정리가 증명된다.

$\blacksquare$

 

Corollary 4.1.

$\Gamma \vdash \varphi^x_c$이고 $c$는 $\Gamma$와 $\varphi$에서 등장하지 않는 constant symbol이라고 하자. 그러면 $\Gamma \vdash \forall x \varphi$이다.

 

Theorem 5. 귀류법 ( Reducto ad Absurdum )

만약 $\Gamma \cup \{ \varphi \}$가 Inconsistent하다면, $\Gamma \vdash \left( \neg \varphi \right)$이다.

 

Proof.

연역 정리에 의해 $\Gamma \vdash \left( \varphi \Rightarrow \beta \right)$와 $\Gamma \vdash \left( \varphi \Rightarrow \left( \neg \beta \right) \right)$가 성립하도록 하는 wff $\beta$가 존재한다. 그런데, 공리꼴 (A1), (A2), (A3)과 $\left( \varphi \Rightarrow \beta \right)$, $\left( \varphi \Rightarrow \left( \neg \beta \right) \right)$를 톤해 $\left( \neg \varphi \right)$를 연역해낼 수 있으므로 $\Gamma \vdash \left( \neg \varphi \right)$가 성립한다.

$\blacksquare$

 

Theorem 6. Existence of Alphabetic Variants

wff $\varphi$, term $t$, 변수 $x$가 주어질 때, 다음 두 조건을 만족하는, $\varphi$에서 양화된 변수만을 바꾼 어떤 wff $\varphi'$이 존재한다. (a) $\varphi \vdash \dashv \varphi'$ (b) $t$가 $\varphi'$에서 $x$에 대해 substitutable하다.

 

Proof.

term $t$와 변수 $x$가 고정된 것으로 간주하고 $\varphi$에 대하여 $\varphi'$를 구성하는 방향으로 증명할 것이다.

$\varphi$에 대한 귀납법을 사용하자.

먼저, $\varphi$가 원자명제인 경우에는, $\varphi'$으로 $\varphi$를 선택하면 조건을 만족한다.

또한, $\left( \neg \varphi \right)'$으로는 $\left( \neg \varphi' \right)$를, $\left( \varphi \Rightarrow \psi \right)'$으로는 $\left( \varphi' \Rightarrow \psi' \right)$를 선택하면 귀납가정에 의해 조건을 만족한다.

이제 $\left( \forall y \varphi \right)'$를 선택하기만 하면 증명이 끝나게 된다.

만약 $y$가 $t$에 등장하지 않는다면, 그냥 $\forall y \varphi'$를 선택하면 조건을 모두 만족한다.

하지만, 그렇지 않은 경우를 고려한다면, 양화된 변수를 바꿀 필요가 있다.

먼저, $\varphi'$나 $t$에 등장하지 않으면서 $x$가 아닌 변수 $z$를 잡자.

그리고 $\left( \forall y \varphi \right)'$로 $\forall z \varphi' {}^y_z$를 선택하자.

이렇게 고른 wff가 조건을 만족함을 보이면 증명이 완료된다.

먼저, (b) 조건을 만족하는지를 확인하자.

$z$가 $t$에 등장하지 않으면서, 귀납가정에 의해 $t$가 $\varphi'$에서 $x$에 대해 substitutable하므로 $t$는 $\forall z \varphi' {}^y_z$에서도 $x$에 대해 substitutable하다. 즉, 조건 (b)를 만족한다.

이제 (a) 조건을 만족하는지를 살펴볼 차례이다.

먼저, 귀납가정에 의해 $\varphi \vdash \varphi'$이며, 따라서 $\forall y \varphi \vdash \forall y \varphi'$이다.

이때, $z$가 $\varphi'$에 등장하지 않는 변수이므로 $\forall y \varphi' \vdash \varphi' {}^y_z$임을 알 수 있다.

따라서 Theorem 3에 의해 $\forall y \varphi' \vdash \forall z \varphi' {}^y_z$이며, 이로 인해 $\forall y \varphi \vdash \forall z \varphi' {}^y_z$임이 증명된다.

이제 $\forall z \varphi' {}^y_z \vdash \forall y \varphi$임을 보이면 증명이 끝난다.

먼저, $\forall z \varphi' {}^y_z \vdash \left( \varphi' {}^y_z \right)^z_y$이며, 오른쪽의 wff는 $\varphi'$이므로 $\forall z \varphi' {}^y_z \vdash \varphi'$임을 알 수 있다.

귀납가정에 의해 $\varphi' \vdash \varphi$이므로 $\forall z \varphi' {}^y_z \vdash \varphi$이며, 역시 Theorem 3에 의해 $\forall z \varphi' {}^y_z \vdash \forall y \varphi$임을 확인할 수 있다.

$\blacksquare$

 

 

1. 아직 포스팅하지 않았기에 추후 체에 대하여 포스팅하게 되면 링크를 걸어놓도록 하겠다. [본문으로]