오늘의 논리학 시리즈는 현대 논리학에 대한 포괄적이고 기초적인 이해를 위한 자료들을 제공합니다.
1.3. \(\mathcal{L}_{Pr}\)의 구문론
형식 체계의 구문론은 그 기호들과 그 적형식適形式 / well-formed formula, wff으로 구성된다. 먼저 명제 논리 체계 \(Pr\)의 기호들을 규정하자. 명제 논리의 언어 \(\mathcal{L}_{Pr}\)의 (원초적) 기호들은 다음과 같다[1]:
\[\eqalign{
&\text{문장 기호: }p_1, p_2, p_3, ...\\
&\text{연결사: }\neg,\land, \lor, \supset\\
&\text{괄호: }(, )
}\tag{1.2}\]
언어 \(\mathcal{L}_{Pr}\)의 적형식은 다음과 같이 재귀적으로 정의된다:\[\eqalign{
& \text{문장 기호 }p_i\text{는 적형식이다.} \\
& \phi\text{가 적형식이라면, }\neg\phi\text{는 적형식이다.} \\
& \phi, \psi\text{가 적형식이라면, }(\phi\land\psi), (\phi\lor\psi), (\phi\supset\psi)\text{는 적형식이다.}\\
&\text{(그 외에는 적형식이 아니다.)}
}\tag{1.3}\]
이렇게 \(\mathcal{L}_{Pr}\)의 구문론이 완성된다. 단, 표기 상의 편의를 위해 다음 두 사항을 약정하자:
- \(p_1, p_2, p_3, ...\) 대신 \(p, q, r, ...\)을 문장 기호로 사용할 수 있다.
- 중의성이 없는 경우, 괄호를 생략할 수 있다.
1.4. \(\mathcal{L}_{Pr}\)의 의미론
이제 우리는 모든 적형식들에 대해(그 집합을 \(\Sigma\)라고 부르자), 해석 함수 \(\mathcal{I}_i: \Sigma \rightarrow \{1, 0\}\)와 평가 함수 \(v_{\mathcal{I}_i}: \Sigma \rightarrow \{1, 0\}\), 또는 줄여서 \(v\)를 통해 \(\mathcal{L}_{Pr}\)의 의미론을 정의할 것이다. 적형식 \(\phi\)와 \(\psi\)에 대해:\[
\eqalign{
v(p)=1 &\iff\mathcal{I}_i(p)=1\\
v(\neg\phi)=1 &\iff v(\phi)=0\\
v(\phi\land\psi)=1 &\iff v(\phi)=1 \text{이면서 } v(\psi)=1\\
v(\phi\lor\psi)=1 &\iff v(\phi)=1 \text{이거나 } v(\psi)=1\\
v(\phi\supset\psi)=1 &\iff v(\phi)=0 \text{이거나 } v(\psi)=1
}\tag{1.4}\]
\(v\)의 함수값 \(1\)을 자연어에서 ‘참’, \(0\)을 ‘거짓’에 대응되는 것으로 이해해 보자. 이렇게 이해할 때, \(\mathcal{L}_{Pr}\)의 문장 기호 \(p_i\)는 명제를 나타내고 있으며, 각 연결사들은 다음의 자연어 표현에 상응하는 개념을 나타내고 있다고 생각할 수 있다[2]:
| \(\mathcal{L}_{Pr}\) | 자연어 |
|---|---|
| \(\neg\) | ...가 아니다 |
| \(\land\) | ... 그리고 ... |
| \(\lor\) | ... 또는 ... |
| \(\supset\) | ...라면 ...이다 |
한편 \(\phi\)와 \(\psi\)에 대한 임의의 해석에 있어 가능한 경우를 모두 기술함을 통해 다음과 같은 표를 얻을 수 있는데,
| \(\phi\) | \(\psi\) | \(\neg(\phi)\) | \(\land(\phi,\psi)\) | \(\lor(\phi,\psi)\) | \(\supset(\phi,\psi)\) |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
(표 1.2)는 \(\mathcal{L}_{Pr}\)의 연결사들을 일종의 진리 함수, 즉 논항의 진리값에 따라 진리값을 내놓는 함수로 간단히 이해할 수 있음을 시사한다. 가령, \(\neg\)는 \(0\)의 값을 갖는 명제를 논항으로 가질 때 \(1\)을 함수값으로 갖는 진리함수이다. \(\land\)는 \(v(\phi, \psi)=(1, 1)\)인 \((\phi, \psi)\)를 논항으로 가질 때 \(1\)을 함수값으로 갖는 진리함수이다.
그런데 (1.3)에 따라 \(\mathcal{L}_{Pr}\)의 식들은 오로지 명제 또는 진리함수들로만 구성된 셈이니, 우리는 위의 표를 응용해 어떠한 \(\mathcal{L}_{Pr}\)의 식에 대해서도 진리표를 그릴 수 있을 것이다. 그리고 이 점을 이용해, 우리는 어떠한 \(\mathcal{L}_{Pr}\)의 식에 대해서도, 그 두 식이 항상 같은 진리값을 갖는 경우나, 둘 중 한 식의 진리값이 \(1\)일 때 다른 식의 진리값도 \(1\)인 경우 등을 찾을 수 있다. 전자의 경우를 두 식이 동치인equivalent, 후자의 경우를 한 식이 다른 식을 함축하는entails 경우라고 일컫자.
가령 (표 1.3)은 \(\phi\)가 (마찬가지로 \(\psi\)가) \(\phi\lor\psi\)를 함축하며, 또한 \(\neg(\phi\lor\psi)\)가 \(\neg\phi\land\neg\psi\)와 동치임을 보여주고 있다:
| \(\phi\) | \(\psi\) | \(\phi\lor\psi\) | \(\neg(\phi\lor\psi)\) | \(\neg\phi\land\neg\psi\) |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
1.5. \(Pr\)의 연역 체계
명제 논리에는 다양한 증명 체계들이 있는데, 여기에서는 그 중 공리(적 증명) 체계를 이야기해 보자. \(Pr\)의 공리 체계는 다음의 세 공리,[3]\[\begin{align}
\alpha&\supset(\beta\supset\alpha)\tag{AxPr$_1$}\\
(\alpha\supset(\beta\supset\gamma))&\supset((\alpha\supset\beta)\supset(\alpha\supset\gamma)\tag{AxPr$_2$}\\
(\neg\beta\supset\neg\alpha)&\supset((\neg\beta\supset\alpha)\supset\beta)\tag{AxPr$_3$}
\end{align}\] 및 다음의 도출 규칙,\[\begin{prooftree}
\AxiomC{$\phi$}
\AxiomC{$\phi\supset\psi$}
\BinaryInfC{$\psi$}
\end{prooftree}\tag{MP}\]으로 구성된다.
이 공리 체계에서, ‘\(\Gamma\)로부터 \(\phi\)가 증명 가능한’(단, \(\Gamma\)는 적형식들의 집합) 경우는 다음 뿐이다: \(\phi\)가, (MP)에 따르는 나열로, \(\Gamma\)의 원소이거나 (AxPr\(_1\)), (AxPr\(_2\)), (AxPr\(_3\))에 등장하는 \(\alpha, \beta, \gamma\)를 다른 적형식으로 대치하여 얻은 식만이 등장하는 식들의 어떤 나열 중 마지막 단에 위치할 때. 이 경우를 다음과 같이 쓰고, 이를 “\(\Gamma\)로부터 \(\phi\)가 증명 가능하다”, 또는 “\(\phi\)가 \(\Gamma\)의 구문론적 귀결syntactic conseuquence이다”라고 읽을 것이다. 한편 \(\Gamma\)가 공집합일 때, 이를 간단히 “\(\vdash\phi\)”라고 쓰면서, 이를 “\(\phi\)가 (이 체계의) 정리이다”라고 읽는다.
가령, 우리는 다음과 같이 \(\vdash(p\supset q)\supset(p\supset p)\)를 보일 수 있다는 것이다[4]:\[\begin{prooftree}
\AxiomC{$\emptyset$}
\RightLabel{$\scriptsize(\text{AxPr}_1)$}
\UnaryInfC{$p\supset(q\supset p)$}
\AxiomC{$\emptyset$}
\RightLabel{$\scriptsize(\text{AxPr}_2)$}
\UnaryInfC{$(p\supset(q\supset p))\supset((p\supset q)\supset(p\supset p))$}
\RightLabel{$\scriptsize(1, 2, (\text{MP}))$}
\BinaryInfC{$(p\supset q)\supset(p\supset p)$}
\end{prooftree}\]
이렇게 우리는 명제 논리가 어떻게 구성되는지에 대해 개괄했다. 이어서, 명제 논리에서 타당한 논증이란 무엇인지에 대해, 그리고 표준적인 명제 논리 체계가 갖는 두 가지 중요한 성질인 건전성과 완전성에 관해 이야기해 보자.
각주
1. 사실, 우리는 \(\mathcal{L}_{Pr}\)의 연결사 중 단 두 개 만을 가지고서도 명제 논리 체계를 구성할 수 있다. 가령, \(\supset\)과 \(\lor\)을 \(\neg\)와 \(\land\)를 통해 정의한다는 식으로 말이다. 어떤 조합들이 가능할지는 직접 시험해 보자.
2. 여기에서 \(\supset\)에 대해 약간의 의아함이 있을 수 있다. 이에 대해서는 이 글(링크)을 참조.
3. §2.6, Logic for Philosophy(Ted Sider 2010).
4. cf. p. 49, Sider 2010.