일계논리의 의미론

By | August 16, 2017

일계논리의 구문론을 소개하면서 일계논리에서 사용하는 기호에 'not', 'if and only if', 'for all'과 같은 이름을 붙였다. 이것은 구문론에서 비록 의미를 부여하지 않은 기호의 나열을 논하지만, 실은 그러한 기호로 이루어진 문장이 어떠한 의미를 갖는지를 방법을 암시한 것이다. 이 글에서는 그러한 방법을 명확하게 밝힌 의미론(semantics)을 살펴본다.

\(\mathcal{L}\)-구조

\(\mathcal{L}\)이 일계논리언어라고 하자. \(\mathcal{L}\)은 그것이 가지고 있는 관계기호, 함수기호, 상수기호에 의하여 완전히 결정된다. 그 외의 기호(변수, 등호, 결합자, 한정기호, 괄호, 쉼표)는 모든 일계논리언어가 공통으로 가지는 것들이다. \(\mathcal{L}\)-구조(L-structure)란 공집합이 아닌 집합 \(V\)와 그 위에서 정의된 \(n\)항관계, \(n\)항함수, 그리고 \(V\)의 원소로 이루어진 구조이다. 여기서 \(n\)항관계, \(n\)항함수, \(V\)의 원소들은 각각 \(\mathcal{L}\)의 \(n\)항관계기호, \(n\)항함수기호, 상수기호들에 대응되는 것들이다. 편의상 \(V\) 위에서 정의된 \(n\)항관계, \(n\)항함수, 그리고 \(V\)의 원소를 나타낼 때 \(\mathcal{L}\)의 \(n\)항관계기호, \(n\)항함수기호, 상수기호와 같은 문자를 사용한다. 하지만 그들이 서로 구분되어야 한다는 사실을 염두에 두어야 한다.

값매김

논리식은 그 논리식이 속한 언어에서 의미를 가져야 한다. 그러나 동시에 논리식의 참거짓 여부는 변수에 할당된 값에 영향을 받는다. 이와 같은 관점에서 \(v\)가 \(\mathcal{L}\)의 값매김(valuation)이라 함은 \(\mathcal{L}\)-구조 \(V\)와 \(V\)의 원소들로 이루어진 수열 \((v_0 ,\, v_1 ,\, v_2 ,\, \cdots )\)를 나타내는 것으로 정의한다. 여기서 \(V\)와 수열 \((v_0 ,\, v_1 ,\, v_2 ,\, \cdots )\)는 \(\mathcal{L}\)의 변수에 할당되는 값이 된다.

하나의 값매김은 임의의 \(i \in \mathbb{N}\)에 대하여 \(v(x_i ) = v_i\)로서 변수들의 집합으로부터 \(V\)로의 대응으로 생각될 수 있다. 이 대응을 확장하여 \(\mathcal{L}\)의 항으로부터 \(V\)로, 그리고 \(\mathcal{L}\)의 논리식으로부터 진릿값 집합 \(\left\{ \mathrm{T,\,F}\right\}\)로의 대응을 만들 수 있다. 편의상 값매김 \(v\)를 확장한 대응 또한 동일한 문자 \(v\)로 나타내기로 하자.

먼저 항에 대하여 다음과 같이 확장한다.

  • \(x_i\)가 변수일 때 \(v(x_i )=v_i\)는 이미 정의되어 있다.
  • 상수기호 \(c\)에 대해서 \(v(c)\)는 \(c\)에 대응되는 \(V\)의 원소이다.
  • \(f\)가 \(n\)항함수이고 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)이 항일 때, \(V\)의 원소 \(v(t_1 ),\) \(v(t_2 ),\) \(\cdots ,\) \(v(t_n )\)을 인수로 갖는 함수기호 \(f\)에 대응되는 함수의 값을 \(v(f(t_1 ,\, t_2 ,\, \cdots ,\, t_n ))\)으로 정한다.

다음으로 아톰논리식에 대하여 다음과 같이 확장한다.

  • \(R\)가 \(n\)항관계기호이고 \(t_1 ,\) \(t_2 ,\) \(\cdots ,\) \(t_n\)이 항일 때, \(v(R(t_1 ,\, t_2 ,\, \cdots ,\, t_n )) = \mathrm{T}\)일 필요충분조건은 \(R\)에 대응되는 관계가 \(V\)의 원소 \(v(t_1 ),\) \(v(t_2 ),\) \(\cdots ,\) \(v(t_n )\)에 대하여 성립하는 것으로 정의한다.
  • \(v((t_1 = t_2 )) = \mathrm{T}\)일 필요충분조건은 \(V\)에서 \(v(t_1 ) = v(t_2 )\)인 것으로 정의한다.

논리식에 대하여 \(v\)를 확장하기 위해서는 \(i\)-인접이라는 개념을 도입해야 한다. 두 값매김 \(v\)와 \(v'\)이 \(i\)-인접(i-near)이라는 것은 \(j \neq i\)인 임의의 \(j\)에 대하여 \(v(x_j ) = v '(x_j )\)인 것을 의미한다. 즉 \(v\)와 \(v'\)이 \(i\)-인접이라는 것은 \(x_i\)를 제외한 모든 변수에 대하여 동일한 값을 매기는 것이다. 이제 논리식에 대하여 다음과 같이 확장한다.

  • \(\phi\)가 아톰논리식일 때 \(v(\phi )\)는 이미 정의되어 있다.
  • \(v(\phi \vee \psi )=\mathrm{T}\)일 필요충분조건은 \(v(\phi ) = \mathrm{T}\) 또는 \(v(\psi ) = \mathrm{T}\)인 것이다.
  • \(v(\phi \wedge \psi )=\mathrm{T}\)일 필요충분조건은 \(v(\phi ) = \mathrm{T}\)와 \(v(\psi ) = \mathrm{T}\)가 모두 성립하는 것이다.
  • \(v((\lnot \phi )) = \mathrm{T}\)일 필요충분조건은 \(v(\phi ) = \mathrm{F}\)인 것이다.
  • \(v(\phi \rightarrow \psi ) = \mathrm{T}\)일 필요충분조건은 \(v(\phi ) = \mathrm{F}\) 또는 \(v(\psi ) = \mathrm{T}\)인 것이다.
  • \(v(\phi \leftrightarrow \psi ) = \mathrm{T}\)일 필요충분조건은 \(v(\phi ) = v(\psi )\)인 것이다.
  • \(v((\forall x_i )\phi ) = \mathrm{T}\)일 필요충분조건은 \(v\)에 대하여 \(i\)-인접한 임의의 값매김 \(v '\)에 대하여 \(v'(\phi ) = \mathrm{T}\)인 것이다.
  • \(v((\exists x_i )\phi ) = \mathrm{T}\)일 필요충분조건은 \(v\)에 대하여 \(i\)-인접한 값매김 \(v '\)가 존재하여 \(v'(\phi ) = \mathrm{T}\)인 것이다.

위 목록의 두 번째부터 여섯 번째까지의 항목은 명제논리에서 살펴보았던 결합자 \(\vee ,\) \(\wedge ,\) \(\lnot ,\) \(\rightarrow ,\) \(\leftrightarrow\)의 정의를 자연스럽게 따른 것이다. 일곱 번째 항목과 여덟 번째 항목은 한정기호의 의미를 정의한 것인데, 처음 보기에는 다소 이해하기 어려운 면이 있다. 논리식의 참거짓 여부는 논리식에 등장하는 변수에 매겨진 값에 의해 결정된다. \((\forall x) \phi\)가 참이라는 것은 \(\phi\)가 참임을 의미하는 것뿐만 아니라 \(\phi\)에 등장하는 변수 \(x\)에 다른 값매김을 하여도 여전히 참이라는 것을 의미한다. \((\exists x) \phi\)가 참이라는 것은 \(\phi\)에 등장하는 변수 \(x\)에 적절한 값매김을 하여 참이 되도록 할 수 있음을 의미한다.

\(v((\forall x)\phi )\)와 \(v((\exists x)\phi )\)는 \(v\)에 의하여 매겨진 \(x\)의 값에 대하여 독립적이다. 즉 임의의 논리식 \(\phi\)에 대하여 진릿값 \(v(\phi )\)는 \(\phi\)의 자유변수에 매겨진 값에 의해서만 결정된다. 특히 \(\phi\)가 문장이면, 즉 \(\phi\)가 자유변수를 갖지 않는 논리식이면 \(v(\phi )\)는 값매김에 대하여 완전히 독립적이다. 즉 \(\phi\)는 그 자체로서 주어진 구조 내에서 참 또는 거짓 중 하나로 결정된다.

모델과 이론

문장 \(\phi\)가 구조 \(M\)에서 참일 때 \[M \models \phi\] 로 나타내고, '\(M\)은 \(\phi\)의 모델이다(\(M\) models \(\phi\))'라고 읽는다. 구조 \(M\)에서 참인 모든 문장들의 모임을 \(M\)의 이론(theory)이라고 부르고 \(\mathrm{Th} (M)\)으로 나타낸다.

예컨대 \(M\)이 하나의 이항함수기호 \(\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 )) \] 그러면 \(M\)이 위 세 문장의 모델일 필요충분조건은 \(M\)이 군(group)인 것이다. \(\mu\)와 \(\iota\)는 각각 군연산과 군연산에 대한 원소의 역원을 나타내며 \(\epsilon\)은 군연산에 대한 항등원을 나타낸다. 위 세 문장은 각각 결합법칙, 항등원의 존재성, 역원의 존재성을 나타낸다. 일반적인 대수학 교재에서는 군을 정의할 때 이 세 조건 외에 다음과 같은 또하나의 조건을 추가한다.

임의의 \(x,\,y \in M\)에 대하여 \(\mu (x,\,y )\in M\)이다.

그러나 이 조건은 일계논리에서는 이미 포함되어 있다. 왜냐하면 \(\mu\)는 \(M\) 위에서의 이항함수이기 때문이다.

Leave a Reply