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

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

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

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

 

Definition 1. 형식 체계 ( Formal System )

$\mathrm{A}$는 가산 무한집합으로, 위에서 언급한 원자 명제의 집합이다. 모든 원자 명제는 $\mathrm{A}$의 원소이며, $\mathrm{A}$의 원소는 원자 명제이다. $\mathrm{\Omega }$는 유한집합으로, $\mathrm{\Omega }$의 원소는 연산자 (Operator Symbol) 또는 논리 연결사 (Logical Connective)라고 부른다. 집합 $\mathrm{\Omega }$는 다음과 같이 유한 개의 서로소인 집합으로 분할된다. $$\mathrm{\Omega }={\mathrm{\Omega }}_0\cup {\mathrm{\Omega }}_1\cup \cdots \cup {\mathrm{\Omega }}_j\cup \cdots \cup {\mathrm{\Omega }}_m$$ 이때, ${\mathrm{\Omega }}_j$는 $\mathrm{\Omega }$의 원소 중 arity가 $j$인 것들을 모아놓은 집합이다. 여기서 arity란, 해당 논리 연결사가 몇 개의 논리식을 연결하는지를 말한다. 더 이해하기 쉽게 말하자면, ${\mathrm{\Omega }}_1$의 원소는 단항 연산자를 모아놓은 집합이며, ${\mathrm{\Omega }}_2$는 이항 연산자를, ${\mathrm{\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. 만약 ${\mathcal{B}}_1,{\mathcal{B}}_2,\cdots ,{\mathcal{B}}_j$가 모두 wff이고 $f$가 ${\mathrm{\Omega }}_j$의 원소라면, $f({\mathcal{B}}_1,{\mathcal{B}}_2,\cdots ,{\mathcal{B}}_j)$ 역시 wff이다. 3. 그 외의 모든 것들은 wff가 아니다.

 

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

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

 

Definition 3. 증명 ( Proof )

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

 

Definition 4. 정리 ( Theorem )

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

 

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

 

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

$$\mathrm{\Gamma }⊢\mathcal{C}$$

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

 

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

 

Proposition 1.

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

 

Proof.

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

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

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

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

 

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

 

Definition 5. Formal Axiomatic Theory

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

 

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

 

(D1) $(\mathcal{B}\wedge \mathcal{C})$는 $\left(\mathrm{\neg }(\mathcal{B}\Rightarrow \left(\mathrm{\neg }\mathcal{C}\right))\right)$의 축약이며, $\wedge$는 '논리곱'이라고 부른다. (D2) $(\mathcal{B}\vee \mathcal{C})$는 $(\left(\mathrm{\neg }\mathcal{B}\right)\Rightarrow \mathcal{C})$의 축약이며, $\vee$는 '논리합'이라고 부른다. (D3) $(\mathcal{B}\iff \mathcal{C})$는 $((\mathcal{B}\Rightarrow \mathcal{C})\wedge (\mathcal{C}\Rightarrow \mathcal{B}))$의 축약이다.

 

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