일계논리의 추론규칙

By | August 17, 2017

일계논리의 형식계는 명제논리와 마찬가지로 알파벳(alphabet), 공리(axioms), 추론규칙(rules of inference)으로 이루어져 있다. 추론규칙은 유한 개의 논리식을 입력받아 하나의 논리식을 출력하는 규칙이다. 증명(proof)이란 논리식의 유한열이다. 이때 증명의 각 줄은 공리이거나 또는 앞에 나타난 줄에 추론규칙을 적용하여 얻어지는 것이다. 증명의 마지막 줄을 정리(theorem)라고 부른다.

더 일반적으로, \(\varSigma\)가 논리식의 집합일 때, \(\varSigma\)로부터의 \(\phi\)의 증명이란 논리식의 유한열인데, 이때 증명의 각 줄은 공리이거나, \(\varSigma\)에 속한 논리식이거나 또는 앞에 나타난 줄에 추론규칙을 적용하여 얻어진 것이다. 예컨대 \(\varSigma\)가 군의 공리의 집합일 때 \(\varSigma\)로부터 증명되는 논리식을 군론의 정리라고 부른다.

일계논리의 추론규칙을 살펴보기 전에 먼저 우리가 사용하는 기호를 단순화시키자. 일계논리에서 사용하는 결합자와 한정기호는 다음 세 개의 기호만으로 모두 나타낼 수 있다. \[\lnot ,\, \rightarrow ,\, \forall\] 그 이유는 다음과 같다.

  • \((\phi \wedge \psi )\)는 \((\lnot \phi )\rightarrow \psi )\)와 동치이다.
  • \((\phi \vee \psi )\)는 \((\lnot (\phi \rightarrow (\lnot \psi )))\)와 동치이다.
  • \((\phi \leftrightarrow \psi )\)는 \(( \lnot (( \phi \rightarrow \psi ) \rightarrow (\lnot (\psi \rightarrow \phi ))))\)와 동치이다.
  • \((\exists x )\phi \)는 \((\lnot (\forall x )(\lnot \phi ))\)와 동치이다.

여기서 동치(equivalent)라는 것은 두 논리식이 구조의 임의의 값매김에 대하여 동일한 진릿값을 가짐을 의미한다.

이제 일계논리의 공리(axioms)를 살펴보자. 아래 목록에서 각 항목은 하나의 공리를 나타내는 것이 아니라 공리의 족(family)을 나타낸다. 왜냐하면 각각의 문자는 다른 논리식이나 변수 또는 항을 나타낼 수 있기 때문이다. \(\phi ,\) \(\psi ,\) \(\theta\)는 임의의 논리식을 나타내며, \(x\)는 변수를 나타내고 \(t,\) \(u\)는 항을 나타낸다. \(\phi [t/x]\)는 논리식 \(\phi\)에 나타나는 자유변수 \(x\)를 \(t\)로 치환하는 것을 의미한다. \(\phi [t/x]\)와 같은 표현을 사용할 때 \(y\)가 \(t\)에 나타나면서 \(x\)가 \(\phi\)에서 \((\forall y)\)의 유효범위에 나타나는 경우는 없는 것으로 약속한다. [만약 그러한 경우가 있다면 치환을 통해 나타난 변수 \(y\)가 원치않게 묶인변수가 되어버릴 수 있기 때문이다.] 일계논리의 공리는 다음과 같은 아홉 개의 식으로 이루어져 있다.

  • (A1) \((\phi\rightarrow (\psi \rightarrow \phi ))\).
  • (A2) \((\phi\rightarrow (\psi \rightarrow \theta )) \rightarrow ((\phi \rightarrow \psi )\rightarrow (\phi \rightarrow \theta )))\).
  • (A3) \((((\lnot \phi ) \rightarrow (\lnot \phi )) \rightarrow (\psi \rightarrow \phi ))\).
  • (A4) \(((\forall x )\phi \rightarrow \phi [t/x] )\).
  • (A5) \(x\)가 \(\phi\)에서 자유변수가 아닐 때 \(((\forall x)(\phi \rightarrow \psi )\rightarrow (\phi \rightarrow (\forall x )\psi ))\).
  • (E1) \(t\)가 항일 때 \((t=t)\).
  • (E2) \(t,\) \(u\)가 항일 때 \(((t=u) \rightarrow (u=t))\).
  • (E3) \(t,\) \(u,\) \(v\)가 항일 때 \(((t=u) \rightarrow ((u=v) \rightarrow (t=v)))\).
  • (E4) \(((t=u) \rightarrow (\phi[t/x,\,t/y]\rightarrow \phi[t/x,\,u/y]))\).

처음 세 공리는 명제논리의 공리와 동일하다. (A4)와 (A5)는 한정기호를 다루기 위한 것이다. (E1)-(E3)은 등호가 동치관계임을 설명한다. (E4)는 논리식에서 항이 그 항과 동치인 다른 항으로 치환되었을 때 논리식은 항이 치환된 논리식과 동치라는 것을 의미한다. 사실 일계논리에서 등호는 수를 다룰 때 일상적으로 사용하는 등호를 가리키는 것이 아니다. 그러나 일계논리구조에서 등호를 사용할 때에도 사실 수를 다룰 때 사용했던 등호와 같은 방법으로 사용하면 된다.

일계논리의 추론규칙(rules of inference)은 다음과 같이 두 개가 있다.

  • (R1) Modus Ponens : \(\phi\)와 \(\phi \rightarrow \psi\)로부터 \(\psi\)를 추론한다.
  • (R2) 일반화 : \(x\)가 변수일 때, \(\phi\)로부터 \((\forall x)\phi\)를 추론한다.

논리식들의 집합 \(\varSigma\)로부터의 추론을 생각하는 경우 (R2)를 적용할 때 한 가지 제약이 있다. 즉 \(x\)는 \(\varSigma\)에 속한 논리식의 자유변수가 아니어야 한다는 점이다. 왜냐하면 만약 \(\varSigma\)에 속한 논리식 중 \(x\)를 자유변수로 갖는 것이 있다면 \(x\)에 값매김을 할 때마다 \(\sigma\)에 속한 모든 논리식의 변수 \(x\)에 동일한 값매김을 해야 하기 때문이다. 사실 수학의 여러 분야에서 일계논리언어를 사용할 때 \(\varSigma\)는 대부분 문장(자유변수가 없는 논리식)으로만 구성되어 있으므로 이러한 제약은 크게 문제가 되지 않는다.

\(\varSigma\)로부터 \(\phi\)를 추론하는 것은 일계논리의 공리에 \(\varSigma\)의 논리식들을 공리로 추가하여 \(\phi\)를 추론하는 것으로 생각할 수 있다. 그러나 여기에는 한 가지 차이점이 있다. 형식계에서는 주어진 논리식이 공리인지 아닌지 판별할 수 있는 기계적인 절차가 있어야 하는데, 모든 \(\varSigma\)가 그러한 조건을 만족시키는 것은 아니다(불완전성 정리).

(A1)-(A3)은 명제논리의 공리이고, 명제논리의 추론규칙인 Modus Ponens가 일계논리의 추론규칙에 포함되어 있으므로 일계논리는 명제논리를 포함하는 것으로 생각될 수 있다. 이러한 관점에서 명제논리의 완전성 정리로부터 다음을 얻는다.

정리 1. \(\varTheta\)가 명제논리의 항진이고 명제변수 \(p_1 ,\) \(p_2 ,\) \(\cdots ,\) \(p_n\)을 가진다고 하자. 그리고 \(\phi _1 ,\) \(\phi _2 ,\) \(\cdots ,\) \(\phi _n\)이 일계논리의 논리식이라고 하자. 그러면 \(\varTheta\)에서 \(p_i\)를 \(\phi_i\)로 치환하여 얻은 논리식 \(\varPhi\)는 일계논리의 정리이다.

\(\varTheta\)의 증명에서 \(p_i\)를 \(\phi_i\)로 치환하면 (A1)-(A3)과 Modus Ponens만을 이용한 \(\varPhi\)의 증명을 얻는다. 이와 같이 명제논리의 증명법으로 얻은 정리를 명제논리적 항진(propositional tautology)이라고 부른다.

정리 2. (추론 정리) \(\phi\)가 논리식의 집합 \(\Sigma \cup \left\{ \psi \right\}\)로부터 추론되면 \((\psi \rightarrow \phi )\)는 \(\Sigma\)로부터 추론된다.

증명. 명제논리의 추론 정리와 유사한 방법으로 증명한다. \(\phi\)가 공리인 경우 \(\phi \in \varSigma\) 또는 \(\phi = \psi\)이므로 이미 앞에서 증명되었다. 이제 \(\phi\)가 추론 규칙을 사용한 증명에서 이전 단계에 나타난다고 가정하자.

\(\phi\)가 Modus Ponens를 이용하여 증명되는 경우에는 이미 앞에서 증명되었다. \(\phi\)가 \((\forall x) \theta\)의 꼴이고, \(x\)가 \(\psi\) 또는 \(\varSigma\)에 속한 논리식의 자유변수가 아니며, \(\phi\)가 \(\theta\)에 일반화를 적용하여 얻어진다고 하자. 수학적 귀납법을 이용하면 \((\psi \rightarrow \theta )\)는 \(\varSigma\)로부터 증명될 수 있다. 그러므로 다음과 같은 과정을 통해 증명이 완료된다. \[ \begin{eqnarray} \varSigma & \,\, \vdash \,\, & (\forall x)(\psi \rightarrow \theta ) \\[8pt] \varSigma & \,\, \vdash \,\, & ((\forall x)(\psi \rightarrow \theta ) \rightarrow (\psi \rightarrow (\forall x) \theta )) \\[8pt] \varSigma & \,\, \vdash \,\, & (\psi \rightarrow (\forall x)\theta ) \end{eqnarray} \] 첫 번째 논리식은 우리의 가정에 일반화를 적용한 것이다. 두 번째 논리식은 (A5)를 적용한 것이며, 마지막 논리식은 Modus Ponens를 적용한 것이다. 이로써 추론 정리가 증명되었다.

Leave a Reply