항 (논리학)

논리학에서, 항(項, 영어: term)은 논의 영역 속의 대상으로 해석되는, 기호들의 정형(整形)적인 문자열이다. 변수 기호와 연산 기호를 통해 재귀적으로 구성되며, 논리식의 구성에 참여한다. 논리식과 마찬가지로, 항에 대하여 그 구조를 통한 귀납법과 재귀를 사용할 수 있다.

정의

항의 정의는 1차 논리의 언어의 정의의 일부이다.

부호수

(I,\;m\colon I\to \mathbb {N} ,\;J,\;n\colon J\to \mathbb {N} )

의 1차 논리의 언어 ${\mathcal {L}}_{I,J}$ 를 구성하는 기호의 집합

\Sigma =\{{\mathsf {x}}_{n}\}_{n\in \mathbb {N} }\sqcup \{\forall ,=,\implies ,\lnot \}\sqcup \{{\mathsf {f}}_{i}\}_{i\in I}\sqcup \{{\mathsf {R}}_{j}\}_{j\in J}

을 생각하자. 기호의 문자열의 집합 $\Sigma ^{*}$ 의 부분 집합 $T\subseteq \Sigma ^{*}$ 이 다음 조건을 만족시키면, 항을 구성하는 연산들에 대하여 닫혀 있다고 하자.

모든 변수 기호 ${\mathsf {x}}_{n}$ 에 대하여, $\ulcorner {\mathsf {x}}_{n}\lrcorner \in T$ 이다.
모든 $m_{i}$ 항 연산 기호 ${\mathsf {f}}_{i}$ 및 $m_{i}$ 개의 원소 $t_{1},\dots ,t_{m_{i}}\in T$ 에 대하여, $\ulcorner {\mathsf {f}}_{i}(t_{1},\dots ,t_{m_{i}})\lrcorner \in T$ 이다. (특히, $m_{i}=0$ 인 경우 $\ulcorner {\mathsf {f}}_{i}()\lrcorner \in T$ 이다.)

예를 들어, 모든 기호의 문자열의 집합 $\Sigma ^{*}$ 은 항을 구성하는 연산들에 대하여 닫혀 있다. 모든 항을 구성하는 연산들에 대하여 닫혀 있는 집합들의 교집합을 생각하자. 이는 항을 구성하는 연산들에 대하여 닫혀 있으며, 그 가운데 가장 작다.

${\mathcal {L}}_{I,J}$ 의 항은 이 교집합의 원소이다.^[1]^{: 45–46, 정의 2.3}

성질

가독성

모든 항 $t$ 는 다음 두 경우 가운데 정확히 하나에 속한다.^[1]^{: 46, 보조정리 2.1}

$t$ 는 어떤 변수 기호 ${\mathsf {x}}_{n}$ 이다.
어떤 연산 기호 ${\mathsf {f}}_{i}$ 및 $m_{i}$ 개의 항 $t_{1},\dots ,t_{m_{i}}$ 에 대하여, $t$ 는 ${\mathsf {f}}_{i}(t_{1},\dots ,t_{m_{i}})$ 이다.

증명:

두 경우에 동시에 속할 수 없음은 자명하다. 이제, 위 두 경우 가운데 적어도 하나 이상에 속하는 항의 집합을 생각하자. 이 집합은 항을 구성하는 연산들에 대하여 닫혀 있음을 쉽게 보일 수 있다. 항의 집합의 최소성에 따라, 이 집합은 항의 집합과 같다.

항의 가독성에 따라, 항에 대한 명제를 항의 구조에 대한 귀납법을 사용하여 증명할 수 있다.

유일 가독성

항 $t$ 의 접두 문자열(=그 처음 몇 기호로 구성된 부분 문자열) 가운데, 항인 것은 $t$ 스스로밖에 없다.^[1]^{: 46, 보조정리 2.2}

증명:

$t$ 의 (문자열로서의) 길이에 대한 수학적 귀납법을 사용하자.

$t$ 가 어떤 변수 기호인 경우, $t$ 의 접두 문자열은 빈 문자열과 $t$ 뿐이며, 이 가운데 항은 $t$ 밖에 없다.

이제, 어떤 연산 기호 $f_{i}$ 및 $m_{i}$ 개의 항 $t_{1},\dots ,t_{m_{i}}$ 에 대하여 $t$ 가 ${\mathsf {f}}_{i}(t_{1},\dots ,t_{m_{i}})$ 인 경우를 생각하자. $u$ 가 $t$ 의 접두 문자열이며, 항이라고 하자. 그렇다면 $u$ 는 빈 문자열이 아니며, 연산 기호 ${\mathsf {f}}_{i}$ 로 시작하므로, 어떤 $m_{i}$ 개의 항 $u_{1},\dots ,u_{m_{i}}$ 에 대하여 ${\mathsf {f}}_{i}(u_{1},\dots ,u_{m_{i}})$ 의 꼴이다. 만약 $t_{1}$ 과 $u_{1}$ 이 서로 다르다면, 귀납법의 가정에 따라 둘 중 하나는 다른 하나의 접두 문자열이므로 항이 아니며, 이는 모순이다. 따라서 $t_{1}$ 과 $u_{1}$ 은 서로 같다. 수학적 귀납법을 사용하여 모든 $j=1,\dots ,m_{i}$ 에 대하여 $\ulcorner t_{j}\lrcorner =\ulcorner u_{j}\lrcorner$ 임을 보일 수 있다. 즉, $u$ 는 $t$ 이다.

모든 항 $t$ 는 다음 두 경우 가운데 정확히 하나에 속한다.^[1]^{: 47, 정리 2.1}

$t$ 는 어떤 유일한 변수 기호 ${\mathsf {x}}_{n}$ 이다.
어떤 유일한 연산 기호 ${\mathsf {f}}_{i}$ 및 유일한 $m_{i}$ 개의 항 $t_{1},\dots ,t_{m_{i}}$ 에 대하여, $t$ 는 ${\mathsf {f}}_{i}(t_{1},\dots ,t_{m_{i}})$ 이다.

증명:

$t$ 가 어떤 변수 기호인 경우, 이 변수 기호는 자명하게 유일하다.

이제, $t$ 가 변수 기호가 아닌 경우를 생각하자. 연산 기호 ${\mathsf {f}}_{i}$ 및 $m_{i}$ 개의 항 $t_{1},\dots ,t_{m_{i}}$ 에 대하여 $t$ 가 ${\mathsf {f}}_{i}(t_{1},\dots ,t_{m_{i}})$ 이며, 연산 기호 $f_{j}$ 및 ${m_{j}}$ 개의 항 $u_{1},\dots ,u_{m_{j}}$ 에 대하여 $t$ 가 ${\mathsf {f}}_{j}(u_{1},\dots ,u_{m_{j}})$ 이라고 하자. 먼저, ${\mathsf {f}}_{i}^{m}$ 와 ${\mathsf {f}}_{j}^{n}$ 는 $t$ 의 첫 번째 기호이므로 서로 같다. 이제, $t_{k}$ 와 $u_{k}$ 는 서로의 진(眞)접두 문자열(=스스로를 제외한 접두 문자열)일 수 없으므로, 수학적 귀납법을 사용하여 모든 $k=1,\dots ,{m_{i}}$ 에 대하여 $\ulcorner t_{k}\lrcorner =\ulcorner u_{k}\lrcorner$ 임을 보일 수 있다. 즉, $t$ 는 유일 가독성을 만족시킨다.