고차 논리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 문법
- 2.2. 증명 이론
3. 의미론
- 3.1. 표준 의미론
- 3.2. 헨킨 의미론
4. 성질
5. 1차 논리와의 비교
6. 양화 범위
참조

1. 개요

고차 논리는 변수와 상수에 종류와 차수의 개념을 도입하여 정의되는 형식 논리 체계이다. 2차 이상의 자연수 또는 가장 작은 무한 극한 순서수를 차수로 가지며, 언어는 각 종류의 변수와 상수로 구성된다. 증명 이론은 추론 규칙과 공리 기본꼴을 기반으로 하며, 표준 의미론과 헨킨 의미론의 두 가지 의미론을 가진다. 표준 의미론은 일차 논리보다 표현력이 풍부하지만, 완전한 증명 계산을 허용하지 않는다. 헨킨 의미론은 일차 논리와 동등하며 완전하고 건전한 증명 시스템을 갖는다. 고차 논리는 튜링의 단순 유형 이론과 직관주의적 유형 이론을 포함하며, 통합 가능성은 결정 불가능하다. 2차 논리는 고차 논리를 시뮬레이션할 수 있으며, "고차 논리"는 고전적인 고차 논리를 지칭하는 것으로 간주되기도 한다. 고차 논리는 1차 논리와 비교하여 양화의 범위가 더 넓다.

더 읽어볼만한 페이지

수리논리학 - NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
수리논리학 - 셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.

고차 논리
개요
유형	수리 논리학, 철학, 컴퓨터 과학
연구 분야	모델 이론, 증명 이론, 집합론, 재귀 이론
논리 체계
종류	1차 논리의 확장
표현력	1차 논리보다 강력함
특징
양화	술어와 함수에 대한 양화 허용
응용	수학적 구조의 더 정확한 표현, 프로그램 검증, 지식 표현
형식 체계
예시	단순 타입 이론, 람다 큐브
한계	불완전성 정리의 적용 가능성, 계산 복잡도 증가
역사
기원	고틀로프 프레게의 연구
발전	알프레드 노스 화이트헤드와 버트런드 러셀의 수학 원리
관련 개념
관련 개념	타입 이론, 범주론
반대 개념	1차 논리

2. 정의

고차 논리는 변수가 가질 수 있는 값의 복잡성을 나타내는 '차수'에 따라 정의된다. 변수의 차수는 변수가 가질 수 있는 값의 복잡성을 나타낸다.

2. 1. 문법

d\in\{2,3,\dots,\omega\}

가 2 이상의 자연수 또는 가장 작은 무한 극한 순서수

\omega

라고 하자.

'''''d''차 논리'''(''d''次論理, ''d''th-order logic^영어)의 '''종류'''(種類, sort^영어)와 이들의 '''차수'''(次數, order^영어)는 다음과 같다. (편의상 연산의 종류를 다루는 것을 생략하자.)

$\imath$ 는 0차 종류이다.
차수가 각각 $d_1,\dots,d_n$ 인 종류 $\sigma_1,\dots,\sigma_n$ 에 대하여, 만약 $\max\{d_1,\dots,d_n\}+1 라면, (\sigma_1\cdots\sigma_n) 은 \max\{d_1,\dots,d_n\}+1 차 종류이다.$

''d''차 논리의 언어는 각 종류의 변수와 상수들로 구성된다. 종류가

\imath

인 변수를 '''개체 변수'''(個體變數, individual variable^영어)라고 하며, 종류가

()

인 변수를 '''명제 변수'''(命題變數, propositional variable^영어)라고 한다.

''d''차 논리의 '''논리식'''(論理式, (well-formed) formula^영어)은 다음과 같다.

종류 $(\sigma_1\cdots\sigma_n)$ 의 변수 또는 상수 $t^{(\sigma_1\cdots\sigma_n)}$ 및 종류가 각각 $\sigma_1,\dots,\sigma_n$ 인 변수 또는 상수 $u_1^{\sigma_1},\dots,u_n^{\sigma_n}$ 에 대하여, $t^{(\sigma_1\cdots\sigma_n)}(u_1^{\sigma_1},\dots,u_n^{\sigma_n})$ 은 논리식이다.
$d-1$ 차 미만의 같은 종류 $\sigma$ 의 두 변수 또는 상수 $t^\sigma,u^\sigma$ 에 대하여, $t^\sigma=u^\sigma$ 는 논리식이다.
논리식 $\phi,\psi$ 및 변수 $x^\sigma$ 에 대하여,
* $\lnot\phi$ 는 논리식이다.
* 만약 $\phi$ 의 속박 변수가 $\psi$ 에 등장하지 않으며, $\psi$ 의 속박 변수가 $\phi$ 에 등장하지 않는다면, $\phi\implies\psi$ 는 논리식이다.
* 만약 $x^\sigma$ 가 $\phi$ 의 자유 변수라면, $\forall x^\sigma\phi$ 는 논리식이다.

여기서 논리식

\phi

와 그 속에 등장하는 변수

x^\sigma

에 대하여, 만약

\phi

가

\forall x^\sigma

를 포함하지 않는다면,

x^\sigma

를

\phi

의 '''자유 변수'''(自由變數, free variable^영어)라고 하며, 그렇지 않다면

x^\sigma

를

\phi

의 '''속박 변수'''(束縛變數, bound variable^영어)라고 한다.

2. 2. 증명 이론

고차 논리의 증명 이론은 전건 긍정, 일반화 등의 추론 규칙과 공리 기본꼴을 기반으로 한다.

다음과 같은 기호들을 사용한다.

$\phi$ , $\psi$ , $\chi$ 는 임의의 논리식이다.
각 종류 $\sigma$ 에 대하여, $x^\sigma$ , $y^\sigma$ , $z^\sigma$ , $y_i^\sigma$ , $z_i^\sigma$ 는 종류 $\sigma$ 의 변수이다.
각 종류 $\sigma$ 에 대하여, $t^{\sigma}$ 는 종류 $\sigma$ 의 변수 또는 상수이다.

''d''차 논리의 추론 규칙들은 다음과 같다.

(전건 긍정)

\begin{matrix}\phi\qquad\phi\implies\psi\\\hline\psi\end{matrix}

(일반화)

\begin{matrix}\phi\\\hline\forall x\phi\end{matrix}

* 여기서 $x$ 는 $\phi$ 의 자유 변수이어야 한다.

''d''차 논리의 공리 기본꼴들은 다음과 같다.

$\phi\implies(\psi\implies\phi)$
$(\phi\implies(\psi\implies\chi))\implies((\phi\implies\psi)\implies(\phi\implies\chi))$
$(\lnot\phi\implies\lnot\psi)\implies(\psi\implies\phi)$
$\forall x^\sigma\phi\implies\phi[t^\sigma/x^\sigma]$
* 여기서 $x^\sigma$ 는 $\phi$ 의 자유 변수이며, $\phi[t^\sigma/x^\sigma]$ 는 $\phi$ 에 등장하는 자유 변수 $x^\sigma$ 를 모두 $t^\sigma$ 로 대체하여 얻는 논리식이다. 만약 $t^\sigma$ 가 변수일 경우, $x^\sigma$ 는 $\phi$ 의 $\forall t^\sigma\cdots$ 꼴의 부분 논리식 속에 등장하지 않아야 한다.
$\forall x^\sigma(\phi\implies\psi)\implies(\phi\implies\forall x^\sigma\psi)$
* 여기서 $x^\sigma$ 는 $\phi$ 에 등장하지 않는 변수이며, $\psi$ 의 자유 변수이어야 한다.
(분류 공리 기본꼴) $\exists x^{(\sigma_1\cdots\sigma_n)}\forall y_1^{\sigma_1}\cdots\forall y_n^{\sigma_n}(x^{(\sigma_1\cdots\sigma_n)}(y_1^{\sigma_1},\dots,y_n^{\sigma_n})\iff\phi)$
* 여기서 $x^{(\sigma_1\cdots\sigma_n)}$ 은 $\phi$ 의 자유 변수일 수 없다.
$x^\sigma=x^\sigma$
$(x^\sigma=y^\sigma)\implies(z^{(\sigma)}(x^\sigma)\implies z^{(\sigma)}(y^\sigma))$
(확장 공리) $\forall z_1^{\sigma_1}\cdots\forall z_n^{\sigma_n}(x^{(\sigma_1\cdots\sigma_n)}(z_1^{\sigma_1},\dots,z_n^{\sigma_n})\iff y^{(\sigma_1\cdots\sigma_n)}(z_1^{\sigma_1},\dots,z_n^{\sigma_n}))\implies(x^{(\sigma_1\cdots\sigma_n)}=y^{(\sigma_1\cdots\sigma_n)})$

모든 공리는 ''d''차 논리의 유효한 논리식이어야 한다. 예를 들어, 확장 공리는 3차 논리에서부터 사용된다. (다른 공리들은 2차 논리에도 존재한다.) 특히, 분류 공리 기본꼴과 확장 공리는 고차 논리, 특히 3차 이상의 논리에서 중요한 역할을 한다.

3. 의미론

고차 논리에는 표준 의미론과 헨킨 의미론 두 가지가 있다.

'''표준 의미론'''(또는 전체 의미론): 고차 유형 객체에 대한 양화 기호가 해당 유형의 ''모든'' 가능한 객체를 범위로 한다.
'''헨킨 의미론''': 각 고차 유형에 대해 별도의 도메인이 각 해석에 포함된다.

3. 1. 표준 의미론

표준 의미론에서 고차 유형 객체에 대한 양화 기호는 해당 유형의 ''모든'' 가능한 객체를 범위로 한다. 예를 들어, 개체의 집합에 대한 양화 기호는 개체 집합의 전체 멱집합을 범위로 한다. 따라서 표준 의미론에서 개체 집합이 지정되면 모든 양화 기호를 지정하기에 충분하다. 표준 의미론을 가진 고차 논리(HOL)은 일차 논리보다 더 표현력이 풍부하다. 예를 들어, HOL은 범주적 자연수 및 실수의 공리화를 허용하는데, 이는 일차 논리로는 불가능하다. 그러나 쿠르트 괴델의 결과에 따라 표준 의미론을 가진 HOL은 효과적이고 건전하며 완전한 증명 계산을 허용하지 않는다.^[2] 표준 의미론을 가진 HOL의 모델 이론적 속성 또한 일차 논리의 속성보다 더 복잡하다. 예를 들어, 2차 논리의 뢰벤하임 수는 그러한 기수가 존재한다면 이미 첫 번째 가측 기수보다 크다.^[3] 반면 일차 논리의 뢰벤하임 수는 가장 작은 무한 기수인 ℵ₀이다.

3. 2. 헨킨 의미론

헨킨 의미론에서는 각 고차 유형에 대해 별도의 도메인이 각 해석에 포함된다. 따라서 예를 들어, 개체 집합에 대한 양화 기호는 개체 집합의 멱집합의 하위 집합만을 범위로 할 수 있다. 이러한 의미론을 가진 고차 논리(HOL)는 다중 정렬 일차 논리와 동등하며, 1차 논리보다 강력하지는 않다. 특히 헨킨 의미론을 가진 고차 논리(HOL)는 1차 논리의 모든 모델 이론적 속성을 가지며, 1차 논리에서 상속된 완전하고 건전하며 효과적인 증명 시스템을 가지고 있다.

4. 성질

고차 논리에는 처치의 단순 유형 이론^[4]의 분파와 다양한 형태의 직관주의적 유형 이론이 포함된다. 제라르 위트는 통합 가능성이 3차 논리의 유형 이론적 측면에서 결정 불가능하다는 것을 증명했다.^[5]^[6]^[7]^[8] 즉, 2차 용어(임의의 고차 용어는 말할 것도 없고) 사이의 임의의 방정식이 해를 갖는지 여부를 결정하는 알고리즘은 존재할 수 없다.

어떤 동형 사상의 개념까지, 멱집합 연산은 2차 논리에서 정의될 수 있다. 야코 힌티카는 이러한 관찰을 사용하여 1955년에 2차 논리가 고차 논리를 시뮬레이션할 수 있다는 것을 확립했다. 즉, 고차 논리의 모든 공식에 대해 2차 논리에서 동등 만족 가능한 공식을 찾을 수 있다.^[9]

"고차 논리"라는 용어는 일부 맥락에서 ''고전적인'' 고차 논리를 지칭하는 것으로 간주된다. 그러나 양상 고차 논리 또한 연구되었다. 여러 논리학자들에 따르면, 괴델의 존재론적 증명은 그러한 맥락에서 (기술적인 관점에서) 가장 잘 연구된다.^[10]

5. 1차 논리와의 비교

1차 논리는 개체 변수에 대한 양화만 허용하는 반면, 고차 논리는 술어, 함수, 더 고차의 변수에 대한 양화를 허용한다. 1차 논리는 완전하고 건전하며 효과적인 증명 시스템을 갖지만, 고차 논리는 표준 의미론에서 그렇지 않다.^[2] 뢰벤하임 수와 같은 모델 이론적 속성은 1차 논리와 고차 논리 간의 차이를 보인다.^[3]

6. 양화 범위

고차 논리는 1차, 2차, 3차, ..., n차 논리의 합집합이다. 즉, 고차 논리는 임의로 깊게 중첩된 집합에 대한 양화를 허용한다.^[1]

1차 논리는 개체를 범위로 하는 변수만 양화한다. 2차 논리는 집합에 대해서도 양화하며, 3차 논리는 집합의 집합에 대해서도 양화하는 방식으로 계속된다.^[1]

참조

_[1] 문서 Jacobs, 1999, chapter 5
_[2] 문서 Shapiro 1991, p. 87.
_[3] 간행물 On Löwenheim-Skolem-Tarski numbers for extensions of first order logic http://www.math.hels[...] Report No. 15 (2009/2010) of the Mittag-Leffler Institute
_[4] 논문 A formulation of the simple theory of types https://www.jstor.or[...] 1940
_[5] 학술지 The Undecidability of Unification in Third Order Logic 1973
_[6] 학위논문 Resolution d'Equations dans des Langages d'Ordre 1,2,...ω https://www.research[...] Universite de Paris VII 1976-09
_[7] 학술지 The Undecidability of the Second-Order Unification Problem http://www.sciencedi[...]
_[8] 서적 Proceedings, 15th International Conference TPHOL Springer 2002
_[9] 웹사이트 SEP entry on HOL http://plato.stanfor[...]
_[10] 서적 Types, Tableaus, and Gödel's God Springer Science & Business Media 2002
_[11] 서적 An Introduction to Mathematical Logic and Type Theory Springer 2002

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com