일계논리의 구문론

By | August 15, 2017

일계논리란 간단히 말하면 명제논리의 체계에 한정기호를 추가하여 확장한 것이다. 논리체계에 한정기호를 추가함으로써 명제논리에서는 다루지 못하였던 수학의 다양한 체계를 일계논리에서 다룰 수 있게 된다. 명제논리와 마찬가지로 일계논리에 대하여 논할 때에도 구문론과 의미론을 생각할 수 있다. 여기서는 일계논리의 구문론을 살펴보자.

일계논리언어

수학에서 '일계논리'를 적용하여 설명할 수 있는 분야는 여러 가지가 있다. 그리고 각각의 분야는 그 분야 고유의 일계논리언어를 가진다. 수학에서 다루는 많은 공간은 집합과 그 집합에서 정의된 함수 또는 관계, 그리고 특정한 원소들로 기술된다. 이러한 기술 방법을 살펴보기 위해 몇 가지 개념을 정의한다.

\(X\)가 집합일 때, \(X^n\)으로부터 \(X\)로의 함수를 \(n\)항연산 또는 \(n\)항함수라고 부르며, \(X^n\)의 부분집합을 \(n\)항관계라고 부른다. 특히 \(n=1\)인 경우 \(1\)항을 일항 또는 단항(unary)이라고 부른다. 예컨대 \(X\)에서의 단항관계란 단순히 \(X\)의 부분집합을 이른다.

예컨대, 군(group)이란 이항연산[군 연산], 특정한 원소[항등원], 단항함수[역원]가 주어진 집합으로 볼 수 있다. 또는 군 연산을 기본개념으로 받아들인 뒤 그 개념을 이용하여 항등원과 역원을 정의할 수도 있다. 체(field)란 두 이항연산[합, 곱]과 특정한 두 원소[덧셈에 대한 항등원, 곱셈에 대한 항등원], 일항연산[덧셈에 대한 역원], 제한된 일항연산[곱셈에 대한 역원]이 주어진 집합으로 볼 수 있다. 순서집합이나 그래프는 각각 하나의 일항연산이 주어진 집합으로 볼 수 있다.

벡터공간은 조금 더 복잡하다. 보통 벡터공간을 기술할 때에는 벡터공간이 정의되는 체 \(F\)를 함께 언급한다. 이 경우 이항연산[벡터 합]과 각 스칼라 \(c\in F\)에 대한 일항연산[스칼라 \(c\)의 곱]을 생각할 수 있다. 즉 벡터공간에 관하여 논의하는 과정에서 체를 명확하게 정하는 것이 중요하다.

위상공간은 이러한 방식으로 공간을 기술하기가 어렵다. 위상공간은 집합 \(X\)와 \(X\)의 부분집합 중 특정한 조건을 만족시키는 집합 \(\mathcal{T}\)로 이루어진 공간이다. 위상은 \(X\)에서의 고정된 수의 관계나 함수로 기술할 수 없다. 이것을 해결하는 방법 중 하나는 부분집합들의 집합을 다룰 수 있는 '이계논리'를 도입하는 것이다. 또다른 방법은 일계논리를 이용하여 집합론을 전개한 뒤 집합론으로 위상공간을 기술하는 것이다.

일계논리의 기호

지금까지 살펴본 바와 같이 적용되는 분야가 무엇인지에 따라 일계논리의 언어는 달라진다. 그러나 적용되는 분야가 무엇인지에 상관없이 일계논리의 언어는 함수기호(function symbol), 관계기호(relation symbol), 상수기호(constant symbol)를 포함한다. 명제논리에서와 마찬가지로 이러한 기호들은 형식적 기호이다. 함수나 관계는 항수(arity)를 가진다. 예컨대 \(R\)가 두 개의 항을 가지는 관계이면 \(R\)를 이항관계기호라고 부른다. 함수기호가 함수를 가리키는 기호이지만 함수기호 자체가 함수는 아니다. 즉 함수기호와 함수는 구분되어야 한다. 관계기호와 관계, 상수기호와 상수도 마찬가지이다. 책에 따라서는 이들을 서로 다른 기호를 사용하여 구분하기도 한다.

일계논리는 '변수(variable)'를 포함한다. 변수는 논리구조에서 임의의 원소를 가리키는 기호이다. 각 논리식은 유한 개의 변수를 갖지만 변수의 개수를 한정시키지 않기 때문에 결국 변수의 개수는 가산인 것처럼 다루어진다. 이러한 관점에서 변수를 \(x_1 ,\) \(x_2 ,\) \(x_3 ,\) \(\cdots\)와 같이 나타낸다. 단, 변수의 개수가 적은 경우에는 \(x,\) \(y,\) \(z\)와 같이 나타내기도 한다.

일계논리에서 사용하는 다른 기호들은 논리기호이다. 논리기호는 다음과 같이 네 가지로 구분할 수 있다.

  • 등호 : \(=\).
  • 결합자 : \(\lnot\) (not), \(\vee\) (or), \(\wedge\) (and), \(\rightarrow\) (implies), \(\leftrightarrow\) (if and only if).
  • 한정기호 : \(\exists\) (there exists), \(\forall\) (for all).
  • 괄호와 쉼표 : 괄호는 논리식을 의미있게 만들어주며, 쉼표는 함수나 관계의 여러 인수를 구분하게 해준다.

요컨대 일계논리의 기호는 함수기호, 관계기호, 상수기호, 변수, 등호, 결합자, 한정기호, 괄호, 쉼표이다.

논리식

논리식(formula)은 기호의 문자열이다. 그러나 모든 문자열이 논리식인 것은 아니다. 논리식은 다음과 같이 정의된다.

먼저 다음 규칙을 유한 번 사용하여 만든 문자열을 (term)이라고 부른다.

  • 하나의 변수만으로 이루어진 문자열은 항이다.
  • 하나의 상수기호만으로 이루어진 문자열은 항이다.
  • \(f\)가 \(n\)항함수기호이고 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)이 항이면 \(f(t_1 ,\, t_2 ,\, \cdots ,\, t_n )\)은 항이다.

다음으로 아톰논리식(atomic formula)은 다음 두 규칙을 유한 번 사용하여 만든 문자열이다.

  • \(R\)가 \(n\)항관계기호이고 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)이 항이면 \(R(t_1 ,\, t_2 ,\, \cdots ,\, t_n )\)은 아톰논리식이다.
  • \(t_1\)과 \(t_2\)가 항이면 \((t_1 = t_2 )\)는 아톰논리식이다.

끝으로 논리식(formula)은 다음 세 규칙을 유한 번 사용하여 만든 문자열이다.

  • 아톰논리식은 논리식이다.
  • \(\phi\)와 \(\psi\)가 논리식이면 \((\phi \wedge \psi )\), \((\phi \vee \psi )\), \((\lnot \phi )\), \(( \phi \rightarrow \psi )\), \(( \phi \leftrightarrow \psi )\)는 모두 논리식이다.
  • \(\phi\)가 논리식이고 \(x\)가 변수이면 \((\exists x ) \phi \)와 \(( \forall x )\phi\)는 모두 논리식이다.

이로써 명제논리에서처럼 문자열이 논리식인지 여부를 기계적으로 판별할 수 있게 되었다. 논리식을 분석할 때 명제논리에서와 같이 트리를 사용할 수 있다. 그러나 각 마디가 갖는 자녀의 수는 둘을 초과할 수도 있다. 왜냐하면 \(n\)항함수기호를 나타내는 마디의 자녀는 \(n\)개이기 때문이다.

한정기호

\(\phi\)와 \(\psi\)가 논리식이고, 논리식이 생성 규칙에 따라 \(\psi\)를 생성하는 과정에서 \(\phi\)가 등장할 때 \(\phi\)를 \(\psi\)의 부분논리식(subformula)이라고 부른다.

한정기호 \(\forall\)의 유효범위(scope)란 해당 한정기호를 포함하고 있는 부분논리식 \((\forall x) \phi\)를 가리킨다. 이때 '부분논리식 \((\forall x) \phi\)는 변수 \(x\)에 의하여 한정되었다(quantified)'라고 말한다. 한정기호 \((\exists x) \phi\)에 대해서도 마찬가지로 정의한다.

논리식에서 '변수 \(x\)가 묶여있다(bounded)'라는 것은 \(x\)가 \(x\)에 의하여 한정된 부분논리식의 유효범위 내에 있는 것을 의미한다. 즉 \((\forall x ) \phi \), \((\exists x)\phi \)에서 \((\forall x )\)와 \((\exists x)\)에 있는 \(x\)와 \(\phi\)에 등장하는 \(x\)는 묶인변수이다. 묶여있지 않은 변수를 자유변수(free variable)라고 부른다. 묶인변수와 자유변수는 논리식에서 변수가 나타나는 형태에 따라 구분하는 것이며, 변수 자체의 종속 여부에 따라 구분하는 것이 아니라는 사실을 유념해야 한다. 하나의 논리식이 두 개 이상의 부분논리식을 품고 있을 때 하나의 변수가 한 부분논리식에서는 묶인변수이고 다른 부분논리식에서는 자유변수일 수 있다.

자유변수가 없는 논리식을 논리문장 또는 간단히 문장(sentence)이라고 부른다. 예컨대, 언어가 하나의 이항함수기호 \(\mu\)와 일항함수기호 \(\iota\), 그리고 하나의 상수기호 \(\epsilon\)을 가진다고 하자. 그러면 다음 세 논리식은 모두 문장이다. \[ (\forall x)(\forall y)(\forall z)(\mu (\mu (x,\,y) ,\,z) = \mu (x,\, \mu(y,\,z ))) \\[8pt] (\forall x)((\mu (x,\,\epsilon ) = x ) \wedge (\mu (\epsilon ,\,x ) =x )) \\[8pt] (\forall x)((\mu (x,\,\iota (x)) = \epsilon ) \wedge (\mu (\iota (x) ,\, x ) = \epsilon )) \]

사실 위 세 문장은 군론의 언어이다. 세 문장은 각각 연산의 결합법칙, 항등원의 존재성, 역원의 존재성을 나타낸다. 즉 군론은 위와 같은 일계논리의 문장을 이용하여 형식적으로 다루어질 수 있다.

Leave a Reply