명제논리의 구문과 의미

By | November 17, 2016

명제논리(propositional logic)란 간단히 말하면 명제변수와 기본 결합자(부정, 명제합, 명제곱, 함의), 그리고 몇 가지 공리와 추론규칙으로 이루어진 논리계를 뜻한다. 명제논리에서는 한정기호를 사용하지 않으므로 명제논리에서 다룰 수 있는 내용이 그렇게 다양한 것은 아니다. 그러나 추론 정리, 완전성 정리, 건전성 정리 등 더 복잡한 논리계를 다룰 때 기본적으로 만나는 정리들을 명제논리에서도 만나게 되므로, 명제논리는 수리논리를 공부하기 위해 기본으로 거쳐야 할 관문이다.

명제논리의 구문론

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

명제논리의 구문론을 다루기 위해 먼저 가산 개의 명제변수(propositional variable)의 집합 \[\left\{p_0 ,\, p_1 ,\, p_2 ,\, \cdots \right\}\]이 주어졌다고 본다. 논의 과정에서 사용하는 명제변수의 개수가 두세 개인 경우 명제변수를 첨자가 없는 \(p,\) \(q,\) \(r\)와 같은 알파벳으로 나타내거나 \(\phi,\) \(\psi,\) \(\theta\)와 같은 그리스 문자로 나타낸다.

명제논리에서는 결합자(connective)라고 불리는 기호 \[\neg , \quad \wedge , \quad \vee , \quad \rightarrow , \quad \leftrightarrow \] 를 사용한다. 이 결합자는 순서대로 '부정', '논리곱', '논리합', '함의', '양방향 함의'이라고 불린다. 또한 명제논리에서는 왼쪽 괄호오른쪽 괄호도 기호로 사용한다. 이러한 기호 전체의 집합이 명제논리의 알파벳이다.

다음으로 논리식을 정의한다. 명제논리에서 논리식(formula)이란 다음 두 가지 규칙을 사용하여 얻어지는 것이다.

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

논리식은 위 규칙을 한 번 또는 여러 번 반복 적용하여 얻어지는 것 외에는 없다. 어떠한 문자열이 논리식인지 여부는 기계적인 절차에 의하여 판별된다. 즉, 주어진 문자열이 논리식이라면 그것을 분석하여 논리식을 생성하는 규칙에 의해서만 생성되었는지 조사할 수 있다.

예컨대 다음과 같은 문자열이 주어졌다고 하자. \[ ((( \neg p_1 ) \rightarrow ( p_1 \wedge p_2 )) \vee (p_1 \wedge (p_2 \leftrightarrow p_3 ))) \] 이 문자열이 논리식임을 밝혀보자. \( (( \neg p_1 ) \rightarrow ( p_1 \wedge p_2 )) \)를 \(\phi\)로 나타내고 \( ( p_1 \wedge ( p_2 \leftrightarrow p_3 )) \)을 \(\psi\)로 나타내면 위 논리식은 \( (\phi \vee \psi )\)로 나타낼 수 있다. 다시 \( (\neg p_1 )\)을 \(\alpha\)로 나타내고 \( (p_1 \wedge p_2 )\)를 \(\beta\)로 나타내면 \(\phi\)는 \( (\alpha \rightarrow \beta )\)로 나타낼 수 있다. 논리식의 정의에 의하여 \( (\neg p_1 )\)과 \( (p_1 \wedge p_2 )\)는 각각 논리식이므로 결국 \(\phi\)도 논리식이다. 같은 방법으로 \(\psi\)도 논리식임을 밝힐 수 있다.

잘 정의된 논리식을 분석하는 과정을 트리(tree)로 시각화할 수 있다. 논리학과 컴퓨터공학에서 트리는 뿌리가 위에 있고 그 밑으로 마디와 잎사귀가 이어져 있다. 잎사귀는 끝에 있으며 잎사귀 밑에는 더 이상 아무것도 이어지지 않는다. 마디 밑에는 마디 또는 잎사귀가 이어진다. 잎사귀에는 명제변수 \(p_i\)가 새겨지며, 잎사귀를 연결해주는 마디에는 부정이나 결합자가 새겨진다. 부정이 새겨진 마디는 자녀를 하나만 가지며, 결합자가 새겨진 마디는 자녀를 둘 가진다. 예컨대 논리식 \[ ((( \neg p_1 ) \rightarrow ( p_1 \wedge p_2 )) \vee (p_1 \wedge (p_2 \leftrightarrow p_3 ))) \] 을 트리로 나타내면 다음과 같다.

명제논리의 의미론

명제논리의 논리식은 일정한 규칙을 만족시키는 논리기호의 문자열이며 그것은 특별한 의미를 지니지 않는다. 이때 명제변수는 명제의 기본단위 역할을 한다. 예를 들어 군 \(G\)에 대하여 논할 때 변수 \(p_0\)을 '\(G\)는 가환군이다'라고 하고 변수 \(p_1\)을 '\(G\)의 모든 원소는 위수가 \(1\)이거나 \(2\)이다'라고 하고 변수 \(p_2\)를 '\(G\)는 유한군이다'라고 하면, 논리식 \(( p_1 \rightarrow p_0 )\)은 '\(G\)의 모든 원소의 위수가 \(1\)이거나 \(2\)이면 \(G\)는 가환군이다'가 되며 \(( \neg p_2 )\)는 '\(G\)는 무한군이다'가 된다.

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

명제변수 \(p_0 ,\) \(p_1 ,\) \(\cdots ,\) \(p_{n-1}\)을 포함하는 논리식은 집합 \(\left\{\mathrm{T} ,\, \mathrm{F} \right\} ^{n}\)으로부터 \(\left\{\mathrm{T} ,\, \mathrm{F} \right\}\)로의 \(n\)변수 함수를 정의하는 데에 사용될 수 있다. 이러한 관점에서, 논리식을 구성하는 데에 사용했던 방법을 사용하여 논리식에 의미를 부여할 수 있다.

이러한 의미 부여 과정을 명확하게 하기 위하여 값매김(valuation)을 모든 논리식의 집합으로부터 집합 \(\left\{\mathrm{T} ,\, \mathrm{F}\right\}\)으로의 함수 \(v\)로 정의한다. 값매김은 각 명제변수 \(p_i\)를 진릿값에 대응시키는데, 대응된 진릿값은 곧 명제변수가 나타내는 명제 단위의 진릿값이 된다.

값매김은 정의역이 모든 논리식의 집합인 함수이므로, 명제변수뿐만 아니라 명제변수를 결합하여 만든 논리식도 값매김에 의하여 진릿값에 대응될 수 있어야 한다. 이것은 다음과 같은 진리표에 의하여 정의된다. [원래 다섯 개의 진리표로 나타내어야 하지만 여기서는 간단하게 하나의 표로 나타냈다.]

\(\phi\) \(\psi\) \((\neg \phi )\) \((\phi \wedge \psi )\) \((\phi \vee \psi )\) \((\phi \to \psi )\) \((\phi \leftrightarrow \psi )\)
T T F T T T T
T F   F T F F
F T T F T T F
F F   F F T T

논리식에 값매김을 할 때 트리를 이용할 수도 있다. 값매김은 트리의 끝 잎사귀에 진릿값을 배정하며, 마디를 함수로 생각하여 진릿값을 계산하면서 뿌리까지 따라 올라가면 처음 논리식의 진릿값을 알 수 있다. 앞에서 봤던 트리를 이용하여 그 방법을 살펴보자.

만약 \[v(p_1 )= \mathrm{T} , \quad v(p_2 ) = \mathrm{T} , \quad v(p_3 ) = \mathrm{F} \] 라면 잎사귀 바로 위의 마디에는 순서대로 \(\mathrm{F},\) \(\mathrm{T},\) \(\mathrm{F}\)가 매겨지고, 그 위의 마디 즉 뿌리 바로 아래의 마디에는 순서대로 \(\mathrm{T},\) \(\mathrm{F}\)가 매겨지며, 뿌리에는 \(\mathrm{T}\)가 매겨진다. 즉 명제변수에 진릿값이 \[(p_1 ,\, p_2 ,\, p_3 ) = ( \mathrm{T} ,\, \mathrm{T} ,\, \mathrm{F} )\] 로 배정되었을 때 논리식 \[ ((( \neg p_1 ) \rightarrow ( p_1 \wedge p_2 )) \vee (p_1 \wedge (p_2 \leftrightarrow p_3 ))) \] 의 진릿값은 \(\mathrm{T}\)이다.

임의의 값매김 \(v\)에 대하여 \(v(\phi )=\mathrm{T}\)일 때 \(\phi\)를 항진(tautology)이라고 부르며, 임의의 값매김 \(v\)에 대하여 \(v(\phi )=\mathrm{F}\)일 때 \(\phi\)를 모순(contradiction)이라고 부른다. 예컨대 \(( p_2 \vee ( \neg p_2 )) \)는 항진이고 \(( p_1 \wedge (\neg p_1 )) \)은 모순이며, \((p_1 \rightarrow p_0 )\)은 항진도 아니고 모순도 아니다.

\(\Sigma\)가 논리식의 집합이라고 하자. '임의의 \(\sigma \in \Sigma\)에 대하여 \(v(\sigma ) = \mathrm{T}\)'인 모든 값매김 \(v\)에 대하여 \(v (\phi ) = \mathrm{T}\)가 성립하면 \(\phi\)를 \(\Sigma\)의 논리적 귀결(logical consequence)이라고 부른다. \(\phi\)가 \(\Sigma\)의 논리적 귀결인 것을 \[\Sigma \models \phi\] 로 나타낸다. [이것은 \(\phi\)가 \(\Sigma\)로부터 의미론적으로 추론된다는 뜻이다. 즉 \(\Sigma\)에 속한 모든 논리식이 참이라고 가정하면 \(\phi\)도 참이 된다는 뜻이다.] 만약 \(\Sigma\)가 공집합이면 \(\phi\)는 항진이 되는데, 이것을 \[\models \phi\] 로 나타낸다.

명제논리의 추론

이제 명제논리의 형식추론계(formal deduction system)를 살펴보자. 이 과정에서 \(\wedge,\) \(\vee,\) \(\leftrightarrow\)는 사용할 필요가 없는데, 왜냐하면 이것들은 \(\neg\)와 \(\rightarrow\)를 이용하여 표현될 수 있기 때문이다. 즉

  • \((\phi \wedge \psi )\)는 \( (\neg (\phi \rightarrow (\neg \psi ))) \)로,
  • \((\phi \vee \psi )\)는 \( ((\neg \phi ) \rightarrow \psi ) \)로,
  • \((\phi \leftrightarrow \psi )\)는 \( ( \neg (( \phi \rightarrow \psi ) \rightarrow ( \neg (\varphi \rightarrow \phi )))) \)로

대체된다.

추론계의 첫 번째 요소로서 명제논리의 공리틀(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 ) ) \)

여기서 공리틀이란 공리들의 모임을 이르는데, 공리틀을 간단히 공리라고 부르기도 한다.

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

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

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

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

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

공리와 추론규칙을 이용한 증명을 의미론적 증명과 구분하기 위하여 '형식적 증명'이라고 부르기도 한다. 추론도 마찬가지로 '형식적 추론'이라고 부르기도 한다.

증명과 정리의 간단한 (하지만 중요한) 예를 살펴보자.

정리 1. 임의의 논리식 \(p\)에 대하여 \( (p \to p )\)는 명제논리의 정리이다.

증명. (A2)의 \(p,\) \(q,\) \(r\)에 각각 \(p,\) \( ( p \to p ) ,\) \(p\)를 대입하면 다음을 얻는다. \[ \vdash ~~ (( p \to (( p \to p) \to p )) \to (( p \to ( p \to p )) \to (p \to p ))) \tag{1} \] 다음으로 (A1)의 \(p,\) \(q\) 에 각각 \(p,\) \( ( p \to p )\) 를 대입하면 다음을 얻는다. \[ \vdash ~~ ( p \to (( p \to p ) \to p )) \tag{2} \] (1), (2)와 MP에 의하여 다음을 얻는다. \[ \vdash ~~ (( p \to ( p \to p )) \to ( p \to p )) \tag{3} \] (A1)의 \(p,\) \(q\)에 모두 \(p\)를 대입하면 다음을 얻는다. \[ \vdash ~~ ( p \to (p \to p )) \tag{4} \] (3), (4)와 MP에 의하여 다음을 얻는다. \[ \vdash ~~ ( p \to p ) \] 이로써 \( ( p \to p ) \)는 명제논리의 정리이다.

원래는 증명 과정에서 논리식의 앞뒤에 설명을 넣지 않는다. 즉 위 증명은 본래 다음과 같이 쓴다. \[ \begin{eqnarray} \vdash & \, & (( p \to (( p \to p) \to p )) \to (( p \to ( p \to p )) \to (p \to p ))) \\[6pt] \vdash & \, & ( p \to (( p \to p ) \to p )) \\[6pt] \vdash & \, & (( p \to ( p \to p )) \to ( p \to p )) \\[6pt] \vdash & \, & ( p \to (p \to p )) \\[6pt] \vdash & \, & ( p \to p ) \end{eqnarray} \] 보다시피 간단한 정리조차도 그것을 증명하려면 보통 여러 개의 논리식이 필요하다. 하지만 다음과 같은 명제논리의 초정리를 이용하면 증명을 더 간단하게 할 수 있다.

정리 2. (추론 정리) \(\phi\)가 \(\Sigma \cup \left\{ \psi \right\} \)의 정리이면 \( (\psi \to \phi )\)는 \(\Sigma\)의 정리이다.

증명. (A1)과 MP에 의하여, \(\phi\)가 특정한 가정 집합으로부터 추론된다면 \( (\psi \to \phi )\)도 동일한 가정 집합으로부터 추론된다. 이 사실을 염두에 두고 증명을 계속하자.

증명 길이에 대한 수학적 귀납법을 사용하자. \(\Sigma \cup \left\{\psi \right\}\)로부터 \(\phi\)의 한 줄 짜리 증명이 존재한다면 \(\phi\)는 공리이거나 \(\Sigma\)에 속하거나 \(\psi\)와 같다. 처음 두 경우, 즉 \(\phi\)가 공리이거나 \(\Sigma\)에 속하면 증명의 시작 부분에서 논한 사실에 의해 \( (\psi \to \phi )\)가 추론된다. 마지막 경우, 즉 \(\phi\)가 \(\psi\)와 같다면 정리 1에 의하여 \((\phi \to \phi )\)가 참이므로 \((\psi \to \phi )\)가 추론된다.

이제 \(\phi\)의 증명 길이 \(n\)이 \(2\) 이상이라고 하자. 그리고 증명 길이가 \(n\) 미만인 경우 정리가 성립한다고 가정하자(귀납적 가정). \(\phi\)가 공리이거나 \(\Sigma \cup \left\{\psi\right\}\)에 속하면 \(\phi\)는 한 줄 짜리 증명에 의해 추론되므로 이러한 경우는 살펴볼 필요가 없다.

그러므로 \(\phi\)가 MP에 의해 \(\theta\)와 \( (\theta \to \phi )\)로부터 추론되고, \(\theta\)와 \( (\theta \to \phi )\)는 각각 증명의 끝항이 아닌 항이라고 하자. 그러면 \(\theta\)와 \( (\theta \to \phi )\)에 대해서 각각 \(\phi\)의 증명보다 길이가 더 짧은 증명이 존재한다. 귀납적 가정에 의하여 \( (\psi \to \theta )\)와 \( (\psi \to ( \theta \to \phi )) \)는 각각 \(\Sigma\)로부터 추론된다. 이들 두 논리식에 (A2)와 MP를 적용하면 \( (\psi \to \phi )\)를 얻는다.

따라서 수학적 귀납법에 의하여 추론 정리가 증명되었다.

추론 정리를 이용하여 증명을 하는 예를 살펴보자. 논리식 \[ (( \neg \phi ) \to ( \phi \to \psi ))\] 이 명제논리의 정리임을 증명해보자. 추론 정리에 의하여 \( (\phi \to \psi )\)가 \(\left\{ (\neg \phi ) \right\}\)로부터 추론될 수 있음을 보이면 된다. 그 증명은 다음과 같다.

\[\begin{eqnarray} \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{eqnarray}\]

증명에서 첫째 항은 (A1)이며 둘째 항은 가정이고 셋째 항은 MP에 의해 얻어진 것이다. 넷째 항은 (A3)이며 다섯째 항은 넷째 항에 MP를 적용한 것이고 여섯째 항은 추론 정리에 의해 얻어진 것이다.

Leave a Reply