명제논리의 개념

명제논리(propositional logic)란 간단히 말하면 명제변수와 기본 결합자(부정, 명제합, 명제곱, 함의), 그리고 몇 가지 공리와 추론규칙으로 이루어진 논리계를 뜻한다. 명제논리는 수리논리를 공부하기 위해 기본으로 거쳐야 할 관문이다.

1. 구문론

구문론(syntactics)이란 주어진 기호를 사용하여 규칙에 따라 논리식을 만들어내거나, 기호로 이루어진 문자열이 논리식인지 아닌지를 밝히는 법칙이다. 구문론에서는 문자열의 의미를 따지지 않고 오직 기호 사이의 형식적 관계에만 관심을 가진다.

명제논리의 구문론을 다루기 위해 먼저 가산 개의 명제변수(propositional variable)의 집합 \[\left\{p_0 ,\, p_1 ,\, p_2 ,\, p_3 ,\, p_4 ,\, \cdots \right\}\] 가 주어졌다고 본다. 명제논리에서는 결합자(connective)라고 불리는 기호 \[\neg , \quad \wedge , \quad \vee , \quad \rightarrow , \quad \leftrightarrow \] 를 사용한다. 이 결합자는 순서대로 '부정', '논리곱', '논리합', '함의', '양방향 함의'라고 불린다. 또한 왼쪽 괄호와 오른쪽 괄호(여는 소괄호와 닫는 소괄호)도 기호로 사용한다.

명제논리에서 논리식(formula)이란 다음 두 가지 규칙을 유한 번 사용하여 얻어지는 문자열이다.

• 명제변수는 논리식이다.
• \(\phi\)가 논리식이면 \( ( \neg \phi )\)도 논리식이다. \(\phi\)와 \(\psi\)가 논리식이면 다음 문자열도 모두 논리식이다. \[ (\phi \vee \psi) , \quad (\phi \wedge \psi) , \quad (\phi \rightarrow \psi) , \quad (\phi \leftrightarrow \psi) \]

논리식은 위 규칙을 한 번 또는 여러 번 적용하여 얻어지는 것 외에는 없다.[이와 같은 방법으로 얻어진 논리식을 'well-formed formula'(줄여서 'wff')라고 부르기도 한다.] 어떠한 문자열이 논리식인지 여부는 형식적인 절차에 의하여 판별된다.

2. 의미론

명제변수 \(p_i\)가 참인지 거짓인지 알고 있다면, 이들 명제변수를 결합하여 만든 논리식이 참인지 거짓인지 판별할 수 있다. 이러한 판별 과정을 다루는 것이 의미론(semantics)이다.

이러한 의미 부여 과정을 명확하게 하기 위하여 값매김(valuation)을 모든 논리식의 집합으로부터 집합 \(\left\{\mathrm{T} ,\, \mathrm{F}\right\}\)로의 함수 \(v\)로 정의한다. 명제논리에서 값매김은 진리표와 같이 정의한다.

임의의 값매김 \(v\)에 대하여 \(v(\phi )=\mathrm{T}\)일 때 \(\phi\)를 항진(tautology)이라고 부르며, 임의의 값매김 \(v\)에 대하여 \(v(\phi )=\mathrm{F}\)일 때 \(\phi\)를 모순(contradiction)이라고 부른다.

\(\varSigma\)가 논리식의 집합이라고 하자. 임의의 \(\sigma \in \varSigma\)에 대하여 \(v(\sigma ) = \mathrm{T}\)인 모든 값매김 \(v\)에 대하여 \(v (\phi ) = \mathrm{T}\)가 성립하면 \(\phi\)를 \(\varSigma\)의 논리적 귀결(logical consequence)이라고 부르고 \[\varSigma \models \phi\] 로 나타낸다. 만약 \(\varSigma\)가 공집합이면 \(\phi\)는 항진이 되는데, 이것을 \[\models \phi\] 로 나타낸다.

3. 형식추론계

이제 명제논리의 형식추론계(formal deduction system)를 살펴보자. 추론계의 첫 번째 요소로서 명제논리의 공리틀(schemes of axioms)을 도입한다.

  (A1) \( ( \phi \to ( \psi \to \phi )) \)
  (A2) \( (( \phi \to (\psi \to \theta )) \to (( \phi \to \psi ) \to ( \phi \to \theta ))) \)
  (A3) \( ((( \neg \phi ) \to ( \neg \psi )) \to ( \psi \to \phi ) ) \)

여기서 \(\phi\), \(\psi\), \(\theta\)는 임의의 논리식을 나타낸다. 공리틀이란 공리들의 모임을 이르는데, 공리틀을 간단히 공리라고 부르기도 한다.

다음으로 추론규칙(rule of inference)을 도입한다. 추론규칙은 다음과 같은 규칙 하나 뿐이다.

\(p\)와 \( ( p \to q ) \)로부터 \(q\)를 추론한다.

이 추론규칙을 'Modus Ponens'라고 부르며 간단히 'MP'로 나타낸다.

증명이란 논리식의 열인데, 열의 각 논리식은 공리이거나 이전 항에 등장한 논리식에 추론규칙을 적용하여 얻어지는 논리식으로 이루어진다. 또한 증명의 마지막 항을 정리라고 부른다.

\(\varSigma\)가 논리식의 집합이고 \(\phi\)가 논리식이라고 하자. '\(\varSigma\)로부터의 \(\phi\)의 증명'이란 논리식의 유한열인데, 열의 각 논리식은 공리이거나 \(\varSigma\)에 속한 논리식이거나 이전 항에 등장한 논리식에 추론규칙을 적용하여 얻어지며, 열의 마지막 항은 \(\phi\)이다. 이때 \(\phi\)를 \(\varSigma\)의 정리라고 부르고 \(\varSigma\)를 가정 집합이라고 부르며 \(\varSigma\)의 원소를 가정이라고 부른다. \(\phi\)가 \(\varSigma\)의 정리인 것을 \[\varSigma \vdash \phi \] 로 나타낸다. 만약 \(\varSigma\)가 공집합이면 \(\phi\)를 '명제논리의 정리' 또는 간단하게 '정리'라고 부르며, 이 상황을 \[\vdash \phi\] 로 나타낸다.

4. 증명 예제

증명과 정리의 간단한 예를 살펴보자.

이 정리의 증명은 다음과 같이 길이가 5인(다섯 개의 항을 가진) 논리식의 열이다. \[\begin{aligned} &\vdash \quad (( p \to (( p \to p) \to p )) \to (( p \to ( p \to p )) \to (p \to p )))\\[6pt] &\vdash \quad ( p \to (( p \to p ) \to p ))\\[6pt] &\vdash \quad (( p \to ( p \to p )) \to ( p \to p ))\\[6pt] &\vdash \quad ( p \to (p \to p ))\\[6pt] &\vdash \quad ( p \to p ) \end{aligned}\] 첫 항은 (A2)의 \(\phi,\) \(\psi,\) \(\theta\)에 각각 \(p,\) \( ( p \to p ) ,\) \(p\)를 대입하여 얻은 것이다. 둘째 항은 (A1)의 \(\phi ,\) \(\psi\) 에 각각 \(p,\) \( ( p \to p )\) 를 대입하여 얻은 것이다. 셋쩨 항은 앞의 두 항에 MP를 적용하여 얻은 것이다. 넷째 항은 (A1)의 \(\phi ,\) \(\psi\)에 모두 \(p\)를 대입하여 얻은 것이다. 다섯 째 항은 앞의 두 항에 MP를 적용하여 얻은 것이다.

간단한 정리조차도 그것을 증명하려면 여러 개의 논리식이 필요하다. 하지만 다음과 같은 명제논리의 상위수학정리를 사용하면 증명을 더 간단하게 할 수 있다.

추론 정리를 사용하여 증명을 하는 예로, 논리식 \[ (( \neg \phi ) \to ( \phi \to \psi ))\] 가 명제논리의 정리임을 보일 수 있다. 추론 정리에 의하여 \( (\phi \to \psi )\)가 \(\left\{ (\neg \phi ) \right\}\)로부터 추론될 수 있음을 보이면 된다. 그 증명은 다음과 같다. \[\begin{aligned} \left\{ ( \neg \phi ) \right \} & \vdash && (( \neg \phi ) \to (( \neg \psi ) \to ( \neg \phi ))) \\[6pt] \left\{ ( \neg \phi ) \right \} & \vdash && (\neg \phi ) \\[6pt] \left\{ ( \neg \phi ) \right \} & \vdash && (( \neg \psi ) \to (\neg \phi )) \\[6pt] \left\{ ( \neg \phi ) \right \} & \vdash && ((( \neg \psi ) \to ( \neg \phi )) \to ( \phi \to \psi )) \\[6pt] \left\{ ( \neg \phi ) \right \} & \vdash && ( \phi \to \psi ) \\[6pt] & \vdash \, && (( \neg \phi ) \to ( \phi \to \psi )) \end{aligned}\] 증명에서 첫째 항은 (A1)이며 둘째 항은 가정이고 셋째 항은 MP에 의해 얻어진 것이다. 넷째 항은 (A3)이며 다섯째 항은 넷째 항에 MP를 적용한 것이고 여섯째 항은 추론 정리에 의해 얻어진 것이다.