1차 논리

1차 논리(一次論理, 영어: first-order logic)는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리이다.^[1] 명제 논리와 달리 변수에 대하여 한정 기호를 사용할 수 있으나, 2차 논리와 달리 변수들의 집합에 대하여 한정 기호를 사용할 수 없다. 1차 논리의 경우, (2차 논리와 달리) 괴델의 완전성 정리 · 콤팩트성 정리 · 뢰벤하임-스콜렘 정리와 같은 중요한 성질들이 성립한다.

이외에 1차 술어 논리, 1계 논리 등으로도 불린다. 간단히 술어 논리(predicate logic)라 하면 1차 논리를 가리키는 경우가 많다.

정의

1차 논리는 다음의 요소들로 이루어진다.

• 특정 문자열들의 집합을 논리식의 집합이라고 한다. 논리식이 만족시켜야 하는 문법은 재귀적으로 정의된다.
• 특정 논리식 집합으로부터 다른 논리식을 추론할 수 있다. 이에 대한 규칙은 힐베르트 체계 및 다른 여러 방식으로 명시될 수 있다.
• 1차 논리 언어의 의미론이란 그 언어의 문장들에 대하여 참인지 여부를 일관적으로 부여하는 구조이다. 이는 보통 모형으로 주어진다.

문법

다음과 같은 데이터가 주어졌다고 하자. (여기서 ${\displaystyle \mathbb {N} }$은 자연수, 즉 음이 아닌 정수의 집합이다.)

• 집합 ${\displaystyle I}$ 및 함수 ${\displaystyle m\colon I\to \mathbb {N} }$, ${\displaystyle i\mapsto m_{i}}$. ${\displaystyle I}$는 유한 집합이거나 무한 집합일 수 있다. 이를 연산(演算, 영어: operation)의 집합이라고 한다.
• 집합 ${\displaystyle J}$ 및 함수 ${\displaystyle n\colon J\to \mathbb {N} }$, ${\displaystyle j\mapsto n_{j}}$. ${\displaystyle J}$는 유한 집합이거나 무한 집합일 수 있다. 이를 관계(關係, 영어: relation)의 집합이라고 한다.

그렇다면, ${\displaystyle (I,m,J,n)}$으로 정의되는 1차 논리 언어 ${\displaystyle {\mathcal {L}}_{I,J}\subseteq \Sigma ^{*}}$는 특정한 문자열들의 집합이다. 이 문자열을 구성하는 문자 집합

${\displaystyle \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}}$

은 구체적으로 다음과 같다.

• 가산 무한 개의 변수들 ${\displaystyle {\mathsf {x}}_{0},{\mathsf {x}}_{1},{\mathsf {x}}_{2},\dots }$
  • 가산 무한 개의 변수들만으로 충분한 이유는 모든 논리식의 길이가 유한하기 때문이다. 무한 논리의 경우 더 많은 변수들을 추가할 수 있다.
• 명제 논리의 연산 ${\displaystyle \implies }$ (함의) 및 ${\displaystyle \lnot }$ (부정).
  • 그 대신 다른 기호들을 사용할 수도 있다. 예를 들어, 논리합 ${\displaystyle \lor }$ 또는 논리곱 ${\displaystyle \land }$ 등이 있다.
• 등호 ${\displaystyle =}$
• 전칭 기호(全稱記號, 영어: universal quantifier) ${\displaystyle \forall }$.
  • 그 대신 존재 기호(存在記號, 영어: existential quantifier) ${\displaystyle \exists }$를 사용할 수도 있다. 사실, 임의의 변수 ${\displaystyle x}$에 대하여 ${\displaystyle \forall x\phi \iff \lnot \exists x\lnot \phi }$이며 ${\displaystyle \exists x\phi \iff \lnot \forall x\lnot \phi }$이므로, 이들은 서로 동치이다.
• 각 ${\displaystyle i\in I}$에 대하여, 기호 ${\displaystyle {\mathsf {f}}_{i}}$. 이를 ${\displaystyle m_{i}}$항 연산이라고 하며, ${\displaystyle m_{i}}$를 ${\displaystyle {\mathsf {f}}_{i}}$의 항수(項數, 영어: arity)라고 한다. 0항 연산을 상수(영어: constant)라고 한다.
• 각 ${\displaystyle j\in J}$에 대하여, 기호 ${\displaystyle {\mathsf {R}}_{j}}$. 이를 ${\displaystyle n_{j}}$항 관계라고 하며, ${\displaystyle n_{j}}$를 ${\displaystyle {\mathsf {R}}_{j}}$의 항수(項數, 영어: arity)라고 한다. 1항 관계를 술어(영어: predicate)라고 한다. (항수가 0인 관계는 고전 명제 논리에서는 참 또는 거짓이 되므로 자명하다.)
• 이 밖에도, 괄호 ${\displaystyle ()}$ 및 반점 ${\displaystyle ,}$ 등은 엄밀히 말해 불필요하지만, 가독성을 돕기 위해 첨가한다. 예를 들어, ${\displaystyle {\mathsf {f}}_{i}{\mathsf {x}}_{0}{\mathsf {x}}_{2}}$ 대신 ${\displaystyle {\mathsf {f}}_{i}({\mathsf {x}}_{0},{\mathsf {x}}_{2})}$로 쓴다.

이 기호들 가운데, ${\displaystyle \{{\mathsf {f}}_{i}\}_{i\in I}}$ 및 ${\displaystyle \{{\mathsf {R}}_{j}\}_{j\in J}}$를 제외한 기호들을 논리 기호(영어: logical symbol)라고 한다.

1차 논리의 항(項, 영어: term)은 다음 문법을 따른다.

• 모든 변수는 항이다.
• 임의의 ${\displaystyle i\in I}$와 ${\displaystyle m_{i}}$개의 항 ${\displaystyle t_{1},t_{2},\dots ,t_{m_{i}}}$에 대하여, ${\displaystyle {\mathsf {f}}_{i}(t_{1},t_{2},\dots ,t_{m_{i}})}$은 항이다. (상수의 경우, 즉 ${\displaystyle m_{i}=0}$일 때, 보통 괄호 ${\displaystyle {\mathsf {f}}_{i}()}$를 생략하여 ${\displaystyle {\mathsf {f}}_{i}}$로 쓴다.)

1차 논리의 논리식(영어: (well-formed) formula)은 다음 문법을 따르는, 위 기호들의 문자열이다.

• 임의의 ${\displaystyle j\in J}$와 ${\displaystyle n_{j}}$개의 항 ${\displaystyle t_{1},\dots ,t_{n_{j}}}$에 대하여, ${\displaystyle {\mathsf {R}}_{j}(t_{1},\dots ,t_{n_{j}})}$은 논리식이다.
• 두 항 ${\displaystyle t_{1}}$, ${\displaystyle t_{2}}$에 대하여, ${\displaystyle t_{1}=t_{2}}$는 논리식이다.
• 논리식 ${\displaystyle \phi }$와 ${\displaystyle \chi }$에 대하여, ${\displaystyle \lnot \phi }$와 ${\displaystyle \phi \implies \chi }$는 논리식이다.
• 논리식 ${\displaystyle \phi }$에 등장하는 변수 ${\displaystyle x_{i}}$가 자유 변수라면, ${\displaystyle \forall x\phi }$는 논리식이다.

여기서 논리식 ${\displaystyle \phi }$ 및 그 속에 등장하는 변수 ${\displaystyle x}$에 대하여, 만약 ${\displaystyle \phi }$가 ${\displaystyle \forall x}$를 포함하지 않는다면, ${\displaystyle x}$를 ${\displaystyle \phi }$의 자유 변수(영어: free variable)라고 하며, 그렇지 않다면 ${\displaystyle x}$를 ${\displaystyle \phi }$의 종속 변수(영어: bound variable)라고 한다.

자유 변수를 갖지 않는 (즉, 그 속에 등장하는 모든 변수가 종속 변수인) 논리식을 문장(文章, 영어: sentence)이라고 한다.

공리와 추론 규칙

1차 논리의 증명 이론은 다양한 방식으로 공리화할 수 있다. 예를 들어 다비트 힐베르트의 힐베르트 체계(영어: Hilbert system)나, 게르하르트 겐첸의 시퀀트 계산(영어: sequent calculus)이나 자연 연역(영어: natural deduction) 등을 사용할 수 있다.

1차 논리를 힐베르트 체계를 사용하여 공리화하면, 다음과 같다. 우선, 편의상 다음과 같은 기호만을 사용한다고 하자.

• 명제 논리에서, 오직 함의 ${\displaystyle \implies }$와 부정 ${\displaystyle \lnot }$만을 사용한다고 하자. (논리합이나 논리곱과 같은 다른 명제 논리 기호는 이 둘로 나타낼 수 있다.)
• 술어 논리에서, 오직 전칭 기호 ${\displaystyle \forall }$만을 사용한다고 하자. (존재 기호 ${\displaystyle \exists }$는 ${\displaystyle \forall }$만으로 나타낼 수 있다.)

이 경우, 다음과 같은 공리 기본꼴(영어: axiom schema)들을 정의한다. 이 공리 기본꼴들에서 사용된 기호들은 다음과 같다.

• ${\displaystyle \phi }$, ${\displaystyle \chi }$, ${\displaystyle \psi }$는 임의의 논리식을 뜻한다.
• ${\displaystyle t}$, ${\displaystyle u}$는 임의의 항을 뜻한다.
• ${\displaystyle x}$는 임의의 변수를 뜻한다.

즉, 공리 기본꼴에서 위의 기호들을 실제의 논리식·항·변수로 치환하면 공리들을 얻는다.

우선, 추론 규칙으로 전건 긍정의 형식

㈀ ${\displaystyle {\begin{matrix}\phi \implies \chi \\\phi \\\hline \chi \end{matrix}}}$

과 일반화

㈁ ${\displaystyle {\begin{matrix}\phi \\\hline \forall x\phi \end{matrix}}}$

추론 규칙 ㈁에서, ${\displaystyle x}$는 ${\displaystyle \phi }$의 자유 변수이어야 한다.

가 있다. 이 밖에, 다음과 같은 명제 논리의 공리 기본꼴들이 사용된다.

㈂ ${\displaystyle \phi \implies \left(\chi \implies \phi \right)}$

㈃ ${\displaystyle \left(\phi \implies \left(\chi \implies \psi \right)\right)\implies \left(\left(\phi \implies \chi \right)\implies \left(\phi \implies \psi \right)\right)}$

㈄ ${\displaystyle \left(\lnot \phi \implies \lnot \chi \right)\implies \left(\chi \implies \phi \right)}$

1차 술어 논리의 경우, 다음과 같은 추가 공리 기본꼴들이 사용된다.

㈅ ${\displaystyle \forall x\phi \implies \phi [t/x]}$

㈆ ${\displaystyle \forall x\left(\phi \implies \chi \right)\implies \left(\forall x\phi \implies \forall x\chi \right)}$

㈇ ${\displaystyle x=x}$

㈈ ${\displaystyle \left(t=u\right)\implies \left(\phi [t/x]\implies \phi [u/x]\right)}$

공리 기본꼴 ㈈에서, ${\displaystyle x}$는 논리식 ${\displaystyle \phi }$의 자유 변수이어야 한다.

위 공리 기본꼴들에서, ${\displaystyle \phi [t/x]}$는 논리식 ${\displaystyle \phi }$에 등장하는 자유 변수 ${\displaystyle x}$를 항 ${\displaystyle t}$로 대체하여 얻는 논리식을 뜻한다. 예를 들어, 체의 언어에서

${\displaystyle {\text{“}}\lnot (x=2)\land \left(\forall xx=y)\right)\lor x=3{\text{”}}[(1+1)/x]={\text{“}}\lnot \left((1+1)=2\right)\land \left(\forall xx=y)\right)\lor 1+1=3{\text{”}}}$

이다. 이때, 논리식 내부의 ‘${\displaystyle \forall xx=y}$’에서 ${\displaystyle x}$가 치환되지 않는 이유는 이 부분에서는 ${\displaystyle x}$가 종속 변수이기 때문이다.

성질

의미론

1차 논리의 의미론은 보통 모형으로 주어진다. 주어진 연산 집합 ${\displaystyle I}$와 관계 집합 ${\displaystyle J}$을 갖는 1차 논리 언어 ${\displaystyle {\mathcal {L}}_{I,J}}$가 주어졌다고 하자. 그렇다면, 이 언어의 모형은 집합 ${\displaystyle X}$ 및 각 ${\displaystyle n}$항 연산 ${\displaystyle i\in I}$에 대하여 ${\displaystyle {\mathsf {f}}_{i}}$의 해석 ${\displaystyle {\mathsf {f}}_{i}^{X}\colon X^{n}\to X}$ 및 각 ${\displaystyle n_{j}}$항 관계 ${\displaystyle {\mathsf {R}}_{j}}$에 대하여 그 해석 ${\displaystyle {\mathsf {R}}_{j}^{X}\in {\mathcal {P}}(X^{n_{j}})}$으로 구성된다. 이를 통해, ${\displaystyle {\mathcal {L}}_{I,J}}$의 문장 ${\displaystyle \phi }$와 ${\displaystyle {\mathcal {L}}_{I,J}}$의 모형 ${\displaystyle M}$에 대하여, ${\displaystyle \phi }$가 ${\displaystyle M}$에서 참인지 또는 거짓인지 여부를 정의할 수 있다. ${\displaystyle \phi }$가 ${\displaystyle M}$에서 참이라는 것은

${\displaystyle M\models \phi }$

로 표기한다.

보다 일반적으로, ${\displaystyle {\mathcal {L}}_{I,J}}$의 논리식 ${\displaystyle \phi }$가 자유 변수 ${\displaystyle x_{1},\dots ,x_{k}}$를 갖는다고 하자. 그렇다면, ${\displaystyle {\mathcal {L}}_{I,J}}$의 모형 ${\displaystyle M}$ 및 그 속의 ${\displaystyle k}$개의 원소

${\displaystyle (m_{1},\dots ,m_{k})\in M^{k}}$

가 주어졌을 때,${\displaystyle \phi }$가 ${\displaystyle M}$에서 ${\displaystyle (m_{i})_{i=1}^{k}}$에 대하여 참인지 또는 거짓인지 여부를 정의할 수 있다. 이는

${\displaystyle M\models \phi [m_{1}/x_{1},\dots ,m_{k}/x_{k}]}$

로 표기한다.

1차 논리의 경우 콤팩트성 정리와 뢰벤하임-스콜렘 정리가 성립한다.

증명 이론

비논리 기호를 포함하지 않는 1차 논리 문장들의 집합을 ${\displaystyle {\mathcal {L}}_{=}^{0}}$라고 하자. 그 가운데, 모든 모형에서 참인 문장들의 부분 집합

${\displaystyle {\mathcal {T}}=\{\phi \in {\mathcal {L}}_{=}^{0}\colon \forall M\in \operatorname {Model} ({\mathcal {L}}_{=})\colon M\models \phi \}}$

을 생각하자. 또한, ${\displaystyle {\mathcal {L}}_{=}^{0}}$ 속에서, 위의 힐베르트 체계를 통해 증명할 수 있는 문장들의 집합을

${\displaystyle {\mathcal {T}}'=\{\phi \in {\mathcal {L}}_{=}^{0}\colon \vdash \phi \}}$

그렇다면, 다음이 성립한다.

• 1차 논리의 건전성 정리에 따르면, ${\displaystyle {\mathcal {T}}={\mathcal {T}}'}$이다. 즉, 명제가 증명 가능한지 여부는 명제가 참인지 여부와 동치이다.
• ${\displaystyle {\mathcal {T}}}$는 재귀 집합이다. (이는 레오폴트 뢰벤하임이 1915년에 증명하였다.)

보다 일반적으로, 임의의 가산 연산 집합 ${\displaystyle I}$와 관계 집합 ${\displaystyle J}$를 갖는 1차 논리 언어 ${\displaystyle {\mathcal {L}}_{I,J}}$ 속에서, 문장들의 집합을 ${\displaystyle {\mathcal {L}}_{I,J}^{0}\subseteq {\mathcal {L}}_{I,J}}$라고 하자. 그 가운데, 모든 모형에서 참인 문장들의 부분 집합

${\displaystyle {\mathcal {T}}=\{\phi \in {\mathcal {L}}_{I,J}^{0}\colon \forall M\in \operatorname {Model} ({\mathcal {L}}_{I,J})\colon M\models \phi \}}$

을 생각하자.

• 괴델의 완전성 정리에 따르면, ${\displaystyle {\mathcal {T}}}$는 재귀 열거 집합이다.
• 만약 ${\displaystyle {\mathcal {R}}}$에 (등호를 제외한) 2항 이상의 항수를 갖는 관계가 존재한다면, ${\displaystyle {\mathcal {T}}}$는 재귀 집합이 아니다.
• 만약 ${\displaystyle I=\varnothing }$이며, ${\displaystyle J}$의 모든 관계가 술어(1항 관계) 또는 등호라면, ${\displaystyle {\mathcal {T}}}$는 재귀 집합이다. 이러한 언어를 1항 1차 언어(영어: monadic first-order language)라고 한다.

린드스트룀 정리

린드스트룀 정리(영어: Lindström’s theorem)에 따르면, 1차 술어 논리는 (가산) 콤팩트성 정리와 하향 뢰벤하임-스콜렘 정리를 만족시키는 가장 강력한 논리 체계이다.^[2]

예

집합론

체르멜로-프렝켈 집합론의 언어는 하나의 2항 관계 ${\displaystyle \in }$ 만을 포함하며, 아무런 연산을 갖지 않는다. 집합론에서 사용되는 대부분의 명제들은 이 언어로 나타낼 수 있다.

체와 순서체

체의 1차 논리 언어

${\displaystyle I=\{+,\cdot ,-,0,1\}}$

${\displaystyle m_{+}=m_{\cdot }=2}$

${\displaystyle m_{-}=1}$

${\displaystyle m_{0}=m_{1}=0}$

${\displaystyle J=\varnothing }$

는 두 개의 이항 연산과 하나의 1항 연산 및 두 개의 상수(0항 연산)을 포함하며, 등호 밖의 관계를 갖지 않는다. 보통 ${\displaystyle {\mathsf {f}}_{+}(a,b)}$는 ${\displaystyle a+b}$와 같이 표기한다.

순서체의 1차 논리 언어

${\displaystyle I=\{+,\cdot ,-,0,1\}}$

${\displaystyle m_{+}=m_{\cdot }=2}$

${\displaystyle m_{-}=1}$

${\displaystyle m_{0}=m_{1}=0}$

${\displaystyle J=\{\leq \}}$

${\displaystyle n_{\leq }=2}$

는 두 개의 이항 연산과 하나의 1항 연산 및 두 개의 상수(0항 연산)을 포함하며, 하나의 2항 관계를 갖는다. 보통 ${\displaystyle {\mathsf {R}}_{\leq }(a,b)}$는 ${\displaystyle a\leq b}$와 같이 표기한다.

범주

범주의 1차 논리 언어는 다음과 같이, 하나의 3항 관계

• ${\displaystyle {\mathsf {C}}(-,-,-)}$ (${\displaystyle {\mathsf {C}}(x,y,z)}$는 ${\displaystyle x\circ y=z}$임을 뜻함)

와 두 개의 1항 연산

• ${\displaystyle \operatorname {dom} (-)}$ (사상의 정의역)
• ${\displaystyle \operatorname {codom} (-)}$ (사상의 공역)

으로 나타낼 수 있다. 변수들은 사상을 나타내며, 대상들은 항등 사상으로 나타내어진다. 편의상 다음과 같은 술어를 정의하자.

${\displaystyle {\mathsf {Obj}}(x)\iff \operatorname {dom} (x)=\operatorname {codom} (x)=x}$

이는 ${\displaystyle x}$가 항등 사상(즉, 대상)임을 뜻한다. 그렇다면, 범주의 1차 논리 이론은 다음과 같은 공리들로 구성된다.

• ${\displaystyle \operatorname {dom} (x)=x\iff \operatorname {codom} (x)=x}$ (항등 사상의 두 정의의 동치성)
• ${\displaystyle {\mathsf {Obj}}(\operatorname {dom} x)}$ (사상의 정의역은 대상)
• ${\displaystyle {\mathsf {Obj}}(\operatorname {codom} x)}$ (사상의 공역은 대상)
• ${\displaystyle {\mathsf {C}}(x,y,z)\implies \operatorname {dom} x=\operatorname {codom} y}$ (사상 합성의 존재의 필요 조건)
• ${\displaystyle {\mathsf {C}}(x,y,z)\implies \operatorname {dom} y=\operatorname {dom} z}$ (합성 사상의 정의역)
• ${\displaystyle {\mathsf {C}}(x,y,z)\implies \operatorname {codom} x=\operatorname {codom} z}$ (합성 사상의 공역)
• ${\displaystyle {\mathsf {C}}(x,y,a)\land {\mathsf {C}}(a,z,c)\land {\mathsf {C}}(y,z,b)\land {\mathsf {C}}(x,b,d)\implies c=d}$ (사상 합성의 결합 법칙)
• ${\displaystyle {\mathsf {Obj}}(x)\land {\mathsf {C}}(x,y,z)\implies y=z}$ (항등 사상과의 합성)
• ${\displaystyle {\mathsf {Obj}}(y)\land {\mathsf {C}}(x,y,z)\implies x=z}$ (항등 사상과의 합성)

이 이론의 모형의 개념은 작은 범주의 개념과 동치이다.

역사

고틀로프 프레게가 1879년에 출판된 《개념 표기법》^[3]에서 사용한 논리는 (현대적 용어로는) 2차 논리였다.^{[4]:295[5]:101–102} 이후 1885년에 찰스 샌더스 퍼스는 1차 논리와 2차 논리를 구분하였다.^{[6][4]:296[5]:99} 퍼스는 1차 논리를 "1차 내포 논리"(영어: first-intensional logic)로, 2차 논리를 "2차 내포 논리"(영어: second-intensional logic)로 일컬었다.^[5]:99–100

이후 에른스트 체르멜로는 2차 논리를 사용하여 집합론을 개발하였다. 토랄프 스콜렘은 1922년에 체르멜로의 집합론을 1차 논리로 재정의하였다.^{[7][5]:123–124[8]:153–156[9]:447} 이는 오늘날 사용되는 체르멜로-프렝켈 집합론의 기반이 되었다.

제2차 세계 대전 이후 1차 논리는 (2차 논리나 유형 이론 등을 대신하여) 통상적으로 사용되는 수학의 기반이 되었다.^[9]:448

같이 보기

• 논리 기호
• 로지반
• 프리넥스 표준형
• 프롤로그 (프로그래밍 언어)
• 관계대수
• 관계형 모델
• 스콜렘 표준형
• 진리표

각주

외부 링크

• “Logical calculus”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Characterization theorems for logics”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “First-order logic”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Interpretation”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Sentence”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Sentential formula”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Open sentential formula”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Free variable”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Bound variable”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “First-order logic”. 《nLab》 (영어).