논리학, 그 첫 번째 이야기 | 명제논리 ( Propositional Calculus )

명제논리란, 내부 구조가 없는 명제에 논리 연산을 가하여 구성한 명제들을 다루는 논리 체계를 말한다.

다른 말로 하면, 명제논리는 더 이상 쪼개질 수 없는 명제인 원자 명제 (Atomic Proposition)에 유한한 논리 연산을 가하여 구성할 수 있는 명제들을 다루는 논리 체계를 뜻한다.

이때, 명제논리는 다음과 같은 조건을 만족하는 형식 체계 (Formal System) $\mathcal{L} = \mathcal{L} \left( \mathrm{A}, \Omega, \mathrm{Z}, \mathrm{I} \right)$를 말한다.

 

Definition 1. 형식 체계 ( Formal System )

$\mathrm{A}$는 가산 무한집합으로, 위에서 언급한 원자 명제의 집합이다. 모든 원자 명제는 $\mathrm{A}$의 원소이며, $\mathrm{A}$의 원소는 원자 명제이다. $\Omega$는 유한집합으로, $\Omega$의 원소는 연산자 (Operator Symbol) 또는 논리 연결사 (Logical Connective)라고 부른다. 집합 $\Omega$는 다음과 같이 유한 개의 서로소인 집합으로 분할된다. $$\Omega = \Omega_0 \cup \Omega_1 \cup \cdots \cup \Omega_j \cup \cdots \cup \Omega_m$$ 이때, $\Omega_j$는 $\Omega$의 원소 중 arity가 $j$인 것들을 모아놓은 집합이다. 여기서 arity란, 해당 논리 연결사가 몇 개의 논리식을 연결하는지를 말한다. 더 이해하기 쉽게 말하자면, $\Omega_1$의 원소는 단항 연산자를 모아놓은 집합이며, $\Omega_2$는 이항 연산자를, $\Omega_j$는 $j$항 연산자를 모아놓은 집합이다. $\mathrm{Z}$는 유한집합으로, 추론 규칙 (Inference Rule)의 집합이다. $\mathrm{I}$는 가산집합으로, 일종의 출발 지점들의 집합이다. 이때, $\mathrm{I}$의 원소를 공리 (Axiom)라고 부른다. 또한, 모든 공리는 wff이다. wff가 무엇인지에 대해서는 아래에서 설명할 것이다.

 

위와 같이 정의된 형식 체계 $\mathcal{L}$에 대하여 $\mathcal{L}$의 언어 (Language)라고 불리는 집합을 정의할 수 있다. 형식 체계 $\mathcal{L}$의 언어는 논리식 (Well-Formed Formula; wff)의 집합이며, 논리식은 다음 규칙에 따라 귀납적으로 정의된다.

 

Definition 2. 논리식 ( Well-Formed Formula; wff )

1. 모든 원자 명제는 wff이다. 2. 만약 $\mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_j$가 모두 wff이고 $f$가 $\Omega_j$의 원소라면, $f \left( \mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_j \right)$ 역시 wff이다. 3. 그 외의 모든 것들은 wff가 아니다.

 

위 규칙들을 여러번 반복 적용할수록 더 복잡한 형태의 논리식을 만들 수 있을 것이다.

이렇게 정의된 형식 체계 $\mathcal{L}$에 대하여 증명 (Proof)과 정리 (Theorem)를 다음과 같이 정의할 수 있다.

 

Definition 3. 증명 ( Proof )

$\mathcal{L}$의 wff의 유한 수열 $\mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_k$가 다음 조건을 만족할 때, 이 수열을 $\mathcal{L}$의 증명이라고 한다. 각 $i$에 대하여 $\mathscr{B}_i$는 $\mathcal{L}$의 공리이거나 그 이전의 논리식에 대하여 $\mathcal{L}$의 추론 규칙을 직접적으로 적용하여 얻어낸 결과이다. 또한, 증명 $\mathscr{B}_1, \mathscr{B}_2, \cdots, \mathscr{B}_k$를 다음과 같이 나타내기도 한다. $$\begin{matrix} \mathscr{B}_1 \\ \mathscr{B}_2 \\ \vdots \\ \mathscr{B}_{k-1} \\ \hline \mathscr{B}_k \end{matrix}$$ 각 줄마다 해당 wff에 대한 설명을 오른쪽에 적기도 한다.

 

Definition 4. 정리 ( Theorem )

$\mathcal{L}$의 wff $\mathscr{B}$에 대하여, 어떤 $\mathcal{L}$의 증명 $\mathscr{P}$가 존재하여 $\mathscr{P}$의 마지막 wff가 $\mathscr{B}$일 때, $\mathscr{B}$를 $\mathcal{L}$의 정리라고 하며, $\mathscr{P}$를 $\mathscr{B}$의 증명이라고 한다.

 

추가적으로, 형식 체계 $\mathcal{L}$의 임의의 wff에 대하여 해당 wff가 $\mathcal{L}$의 공리인지 알아낼 수 있는 기계적인 판단 방식이 있는 경우, $\mathcal{L}$을 axiomatic하다고 한다. 또한, $\mathcal{L}$의 정리 $\mathscr{T}$에 대하여 $\mathscr{T}$의 증명이 존재하는지 알아낼 수 있는 기계적인 판단 방식이 있는 경우, $\mathscr{T}$를 결정가능하다 (Decidable)고 하며, 그러한 기계적인 판단 방식이 없는 경우, $\mathscr{T}$를 결정불가능하다 (Undecidable)고 한다. 만약 $\mathcal{L}$의 모든 정리가 결정가능하다면 $\mathcal{L}$을 결정가능하다고 하며, 그렇지 않을 경우, $\mathcal{L}$을 결정불가능하다고 한다.

 

또한, 형식 체계 $\mathcal{L}$ 내에서 wff $\mathscr{C}$가 wff의 집합 $\Gamma$의 귀결 (Consequence)라고 함은, $\Gamma$의 원소 또한 공리로 받아들였을 때 $\mathscr{C}$가 정리로 취급됨을 의미하며, 이때, $\Gamma$의 원소 또한 공리로 받아들였을 때의 $\mathscr{C}$의 증명을 $\Gamma$로부터의 $\mathscr{C}$의 증명이라고 하며, $\mathscr{C}$가 $\Gamma$의 결과임은 기호로 다음과 같이 나타낸다.

$$\Gamma \vdash \mathscr{C}$$

또한, 여러 체계를 동시에 다룰 때의 혼동을 방지하기 위해 $\mathcal{L}$ 내에서 $\mathscr{C}$가 $\Gamma$의 귀결임을 $\Gamma \vdash_\mathcal{L} \mathscr{C}$와 같이 나타내기도 하며, $\Gamma$가 유한집합 $\{ \mathscr{H}_1, \mathscr{H}_2, \cdots, \mathscr{H}_m \}$일 때, $\{ \mathscr{H}_1, \mathscr{H}_2, \cdots, \mathscr{H}_m \} \vdash \mathscr{C}$ 대신에 $\mathscr{H}_1, \mathscr{H}_2, \cdots, \mathscr{H}_m \vdash \mathscr{C}$로 나타낼 수 있다. 또한, 만약 $\Gamma$가 공집합이라면, $\varnothing \vdash \mathscr{C}$ 대신에 $\vdash \mathscr{C}$와 같이 쓸 수 있다. 즉, $\vdash \mathscr{C}$는 $\mathscr{C}$가 정리임을 의미한다.

 

이때, $\vdash$는 다음의 세 가지 성질이 성립한다.

 

Proposition 1.

a. 만약 $\Gamma \subseteq \Delta$이고 $\Gamma \vdash \mathscr{C}$라면 $\Delta \vdash \mathscr{C}$이다. b. $\Gamma \vdash \mathscr{C}$인 것은 $\Delta \vdash \mathscr{C}$인 유한집합 $\Delta \subseteq \Gamma$가 존재하는 것과 논리적으로 동치이다. c. 만약 $\Delta \vdash \mathscr{C}$이고 모든 $\mathscr{B} \in \Delta$에 대하여 $\Gamma \vdash \mathscr{B}$라면, $\Gamma \vdash \mathscr{C}$이다.

 

Proof.

[a] 이는 증명의 정의로부터 자명한 결과이다.

[b] 이 명제의 절반은 a에 의한 결과이다. 나머지 절반에 대해서는 다음과 같이 증명할 수 있다.

증명의 정의를 생각하면, 증명에 사용되는 전제는 유한하다는 것을 알 수 있으며, 따라서 필연적으로 $\Delta \vdash \mathscr{C}$인 유한집합 $\Delta \subseteq \Gamma$가 존재한다는 것을 알 수 있다.

[c] $\Delta$의 모든 wff가 $\Gamma$로부터 증명가능하다면, $\mathscr{C}$의 증명에 사용된 $\Delta$의 wff의 증명을 $\mathscr{C}$의 증명 앞에 이어붙인다면 $\Gamma$로부터 $\mathscr{C}$의 증명을 얻을 수 있다. 따라서 $\Gamma \vdash \mathscr{C}$이다.

 

이제 앞으로 사용하게 될 형식 체계인 formal axiomatic theory $L$을 소개하겠다.

 

Definition 5. Formal Axiomatic Theory

1. $L$은 논리 연결사 $\neg$와 $\Rightarrow$를 가진다. $\neg$의 arity는 1이며, $\Rightarrow$의 arity는 2이다. 또한, $L$의 원자 명제는 가산 무한 집합을 이룬다. 또한, $\neg$는 '부정'이라고 부르며, $\Rightarrow$는 '함의'라고 부른다. 2. 다음 두 명제를 통해 wff가 귀납적으로 정의되며, 그 외의 모든 식은 wff가 아니다. (a) 원자 명제는 wff이다. (b) $\mathscr{B}$와 $\mathscr{C}$가 wff이면, $(\neg\mathscr{B})$와 $(\mathscr{B}\Rightarrow\mathscr{C})$는 wff이다. 3. 만약 $\mathscr{B}$, $\mathscr{C}$, $\mathscr{D}$가 모두 wff라면, 아래 세 wff는 모두 공리이다. (A1) $\left( \mathscr{B} \Rightarrow \left( \mathscr{C} \Rightarrow \mathscr{B} \right) \right)$ (A2) $\left( \left( \mathscr{B} \Rightarrow \left( \mathscr{C} \Rightarrow \mathscr{D} \right) \right) \Rightarrow \left( \left( \mathscr{B} \Rightarrow \mathscr{C} \right) \Rightarrow \left( \mathscr{C} \Rightarrow \mathscr{D} \right) \right) \right)$ (A3) $\left( \left( \left( \neg \mathscr{C} \right) \Rightarrow \left( \neg \mathscr{B} \right) \right) \Rightarrow \left( \left( \left( \neg \mathscr{C} \right) \Rightarrow \mathscr{B} \right) \Rightarrow \mathscr{C} \right) \right)$ 4. $L$의 추론 규칙은 전건 긍정 (Modus Ponens) 하나뿐이다. 여기서, 전건 긍정이란, $\mathscr{C}$가 $\mathscr{B}$와 $\mathscr{B} \Rightarrow \mathscr{C}$의 직접적인 결과라는 것을 의미한다. 즉, $\mathscr{B}, \mathscr{B} \Rightarrow \mathscr{C} \vdash \mathscr{C}$를 의미한다. 앞으로 전건 긍정은 간단히 MP로 쓸 것이다.

 

또한, 편의를 위해 다음과 같은 3가지 논리 연결사를 추가적으로 정의하자.

 

(D1) $\left( \mathscr{B} \land \mathscr{C} \right)$는 $\left( \neg \left( \mathscr{B} \Rightarrow \left( \neg \mathscr{C} \right) \right) \right)$의 축약이며, $\land$는 '논리곱'이라고 부른다. (D2) $\left( \mathscr{B} \lor \mathscr{C} \right)$는 $\left( \left( \neg \mathscr{B} \right) \Rightarrow \mathscr{C}\right)$의 축약이며, $\lor$는 '논리합'이라고 부른다. (D3) $\left( \mathscr{B} \Leftrightarrow \mathscr{C} \right)$는 $\left( \left( \mathscr{B} \Rightarrow \mathscr{C} \right) \land \left( \mathscr{C} \Rightarrow \mathscr{B} \right) \right)$의 축약이다.

 

이제 $L$에서의 정리들에 대해 포스팅할 예정이며, 앞으로 작성하게 될 글들에서 $\Gamma \vdash \mathscr{C}$는 특별한 언급이 없는 한 $\Gamma \vdash_L \mathscr{C}$를 의미한다.