자름-제거 정리

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

1. 개요
2. 시퀀트 계산
- 2.1. 시퀀트의 의미
- 2.2. 추론 규칙
3. 자름 규칙
4. 자름 제거 정리
- 4.1. 정리의 의미
- 4.2. 해석적 증명
5. 자름 제거 정리의 결과
참조

1. 개요

자름-제거 정리는 시퀀트 계산에서 자름 규칙을 사용하는 증명에서 자름 규칙을 제거하는 방법이 존재한다는 정리이다. 이 정리는 증명 이론에서 중요한 의미를 가지며, 컷 규칙을 사용하지 않는 "분석적 증명"의 존재를 보장한다. 자름-제거 정리가 성립하는 논리 체계는 무모순성을 가지며, 부분식 성질을 만족한다. 또한, 크레이그의 보간 정리 증명에 활용되며, 자동 정리 증명, 프로그램 검증, 논리 프로그래밍 언어, 커리-하워드 동형 사상 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

증명 이론 - 힐베르트 프로그램
힐베르트 프로그램은 20세기 초 수학의 기초를 형식 체계로 구축하고 무모순성과 완전성을 증명하려 했으나, 괴델의 불완전성 정리에 의해 원래 목표 달성이 불가능해졌고 수정된 형태로 연구가 지속되고 있다.
증명 이론 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2^κ > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.

자름-제거 정리
기본 정보
유형	논리적 정리
분야	증명 이론
중요성	증명 이론의 기본 정리
관련 항목	겐첸의 정리 정규화 정리
역사
이름의 유래	논리적 증명에서 "자름(cut)" 규칙을 제거하는 것에서 유래
발견	겐첸 (1930년대)
응용
응용 분야	자동 정리 증명 프로그램 검증 논리 프로그래밍

2. 시퀀트 계산

시퀀트 계산(sequent calculus^영어)은 여러 개의 논리식으로 이루어진 논리 표현의 일종이다.

: $A, B, C, \ldots \vdash P, Q, R, \ldots$

와 같은 형식이며, 이는 직관적으로 "A이며 B이며 C이며... 라 가정하면 P이거나 Q이거나 R이거나... 임을 증명가능하다"라는 의미를 가진다. 곧 논리곱을 전건, 논리합을 후건으로 삼는다. 직관논리(LJ)에서는 우변에 하나의 논리식만을 놓을 수 있다.

시퀀트 계산에서 '자름'(cut)은 추론 규칙 중 하나이다. 예를 들어 $\Gamma \vdash A,\Delta$ 이면서 $\Pi, A \vdash \Lambda$ 이라면, $\Gamma, \Pi \vdash \Delta,\Lambda$ 를 추론해낼 수 있다. 이러한 상황에서 논리식 $A$ 는 추론 과정에서 '잘라' 버릴 수 있다.^[3]

"절단(Cut)"은 시퀀트 계산의 일반적인 명제에서 추론 규칙이며, 다른 증명 이론의 다양한 규칙과 동등하다.

만약

$\Gamma \vdash A,\Delta$

그리고

$\Pi, A \vdash \Lambda$

이라면,

$\Gamma, \Pi \vdash \Delta,\Lambda$

를 추론할수 있다.

즉, 추론 관계에서 수식

A

의 발생을 "잘라낸다".

2. 1. 시퀀트의 의미

시퀀트는 여러 수식을 연관시키는 논리적 표현으로, "

A_1, A_2, A_3, \ldots \vdash B_1, B_2, B_3, \ldots

" 형태를 취한다. 이는 "

A_1, A_2, A_3, \ldots

"가 "

B_1, B_2, B_3, \ldots

"를 증명한다는 의미이며, 젠첸의 풀이에 따르면 "만약 (

A_1

그리고

A_2

그리고

A_3

…) 이면 (

B_1

또는

B_2

또는

B_3

…)"이라는 진리 함수와 동등하다.^[3] 여기서 좌변(LHS)은 논리곱(and)이고 우변(RHS)은 논리합(or)이다.

좌변은 수식의 개수에 제한이 없다. 좌변이 비어 있을 경우, 우변은 항진명제가 된다. LK(고전 논리)에서 우변 또한 수식 개수에 제한이 없으며, 우변이 비어 있다면 좌변은 모순이 된다. 반면 LJ(직관 논리)에서는 우변에 하나의 수식만 허용되거나 아예 비어 있을 수 있다. 우변에 둘 이상의 수식을 허용하는 것은 우측 축약 규칙이 있는 상태에서 배중률을 허용하는 것과 같다. 그러나 시퀀트 계산은 표현력이 풍부한 프레임워크이므로, 우변에 많은 수식을 허용하는 직관 논리를 위한 시퀀트 계산도 제안되었다. 장-이브 지라르의 논리 LC를 통해 우변이 최대 하나의 수식을 포함하는 고전 논리의 자연스러운 형식화를 쉽게 얻을 수 있다. 여기서 핵심은 논리 규칙과 구조 규칙의 상호 작용이다.

:

A, B, C, \ldots \vdash P, Q, R, \ldots

위와 같은 시퀀트는 직관적으로 다음과 같이 이해할 수 있다.

:「A와 B와 C와 …를 가정하면, P 또는 Q 또는 R 또는 …이 증명 가능하다」

(여기서 좌변은 논리곱, 우변은 논리합이다.) 전제인 좌변은 논리식 개수에 제한이 없으며, 좌변이 빈 시퀀트를 증명할 수 있다면 그 우변은 무전제로 주장 가능한 토톨로지가 된다. 반대로 결론인 우변이 비어 있다면 좌변은 모순이다. LK(고전 논리)에서는 우변도 논리식 개수에 제한이 없지만, LJ(직관 논리)에서는 우변에 많아야 하나의 문장만 놓을 수 있다. 우변에 여러 논리식을 놓을 수 있다는 것은 오른쪽 축약 규칙이 있을 때 배중률이 성립한다는 것과 같다. 하지만 시퀀트 계산은 표현 능력이 매우 높으며, 우변에 다수의 논리식이 있는 직관 논리의 시퀀트 계산도 존재한다. 장-이브 지라르의 논리 체계 LC에서는 우변에 하나의 논리식만 갖는 고전 논리의 자연스러운 공식화도 쉽게 얻을 수 있다. 여기서 핵심은 논리적 추론 규칙과 구조에 관한 추론 규칙 간의 상호 작용이다.

2. 2. 추론 규칙

시퀀트 계산은 자연 연역처럼

A \vdash A

라는 동일성의 공리만을 공리로 채택하고 많은 추론규칙들을 사용하여 증명을 구성해나가는 방식이다.

3. 자름 규칙

시퀀트 계산에서 '자름'(cut)은 추론 규칙 중 하나이다. 예를 들어 $\Gamma \vdash A,\Delta$ 이고 $\Pi, A \vdash \Lambda$ 이라면, $\Gamma, \Pi \vdash \Delta,\Lambda$ 를 추론할 수 있다. 이 경우 논리식 $A$ 를 추론 과정에서 '잘라' 버릴 수 있다.^[3]

좀 더 구체적으로 설명하면, "자름" 규칙은 다음과 같다.

$\Gamma \vdash A,\Delta$

$\Pi, A \vdash \Lambda$

이 두 가지가 성립할 때,

$\Gamma, \Pi \vdash \Delta,\Lambda$

를 추론할 수 있다. 즉, 논리식

A

가 추론 과정에서 제거된다.

오른쪽 변에 하나의 공식만 있는 시퀀트 계산의 경우 "자름" 규칙은 다음과 같이 표현된다.

$\Gamma \vdash A$

$\Pi, A \vdash B$

가 성립할 때,

$\Gamma, \Pi \vdash B$

를 추론할 수 있다. 만약

B

를 정리라고 한다면, 자름-제거 정리에 따라 이 정리를 증명하는 데 사용된 보조 정리

A

를 인라인할 수 있다. 즉, 정리의 증명에서 보조 정리

A

가 언급될 때마다

A

의 증명으로 해당 부분을 대체할 수 있다. 결과적으로 자름 규칙은 허용된다.

4. 자름 제거 정리

자름 제거 정리는 자름 규칙을 사용하는 임의의 증명에 대해 자름 규칙을 사용하지 않는 증명이 존재함을 보장한다. 즉, 어떤 논리 체계에서 컷 규칙을 사용하여 증명 가능한 명제는 컷 규칙을 사용하지 않고도 증명 가능하다는 것이다.

이 정리는 다음과 같은 다양한 응용이 가능하다.

무모순성 증명: 컷 제거 정리가 성립하는 논리 체계에서는 모순 명제(빈 시퀀트)를 증명할 수 없다. 만약 모순 명제의 증명이 가능하다면, 컷 규칙을 사용하지 않는 증명도 존재해야 한다. 그러나 추론 규칙을 살펴보면 그러한 증명이 불가능함을 쉽게 알 수 있다. 따라서 컷 제거 정리를 증명하면 그 체계의 무모순성도 증명된다.
부분 논리식성: 컷 제거 정리가 성립하는 논리 체계(최소한 일차 술어 논리까지)에서는 부분 논리식성(subformula property)이 성립한다. 즉, 증명에 등장하는 모든 논리식은 결론의 부분 논리식이 된다. 이는 증명론 기반 의미론에서 중요한 역할을 한다.
기타: 크레이그의 보간 정리 증명, 프롤로그 언어의 기반이 되는 도출 기반 증명 탐색, 커리-하워드 동형 대응을 통한 고차 람다 계산에서의 추론 등에 활용된다.

4. 1. 정리의 의미

\Gamma \vdash A

와

\Pi, A \vdash B

로부터

\Gamma, \Pi \vdash B

를 추론하는 증명에서,

B

를 정리,

A

를 보조정리라 할 때, 보조정리

A

를 증명하는 과정으로 대체하여 새로운 증명을 만들 수 있다. 정리의 증명에서 보조 정리

A

가 언급될 때마다,

A

의 증명으로 해당 부분을 대체할 수 있다. 따라서 자름 규칙은 허용되는 규칙이다.

4. 2. 해석적 증명

시퀀트 계산 체계에서 자름 규칙을 사용하지 않는 증명을 해석적 증명(analytic proof^영어)이라고 한다. 이러한 증명은 반드시 그런 것은 아니지만, 일반적으로 매우 길어진다. 조지 불로스는 "Don't Eliminate Cut!" 논문에서 자름 규칙을 사용하면 1페이지 만에 도출 가능하지만, 해석적 증명으로는 우주의 수명 안에 완료할 수 없는 증명의 예시를 제시했다.^[4]

5. 자름 제거 정리의 결과

자름 제거 정리는 논리 체계의 중요한 성질들을 증명하는 데 사용된다.

조지 불로스는 그의 논문 "Don't Eliminate Cut!"에서 자름 규칙을 사용하면 1페이지 안에 도출 가능하지만, 자름 규칙을 사용하지 않고 해석적으로 나타낼 시에는 우주의 수명 안에 완료할 수 없는 증명의 예시를 보였다.^[4]

자름 제거는 크레이그의 보간 정리를 증명하는 데 강력한 도구이며, 프롤로그 프로그래밍 언어 개발의 기반이 된 해상도 기반 증명 검색 가능성은 해당 시스템에서 자름의 허용 가능성에 달려 있다.^[4] 커리-하워드 동형 사상에 따르면, 자름 제거 알고리즘은 강력한 정규화 속성에 해당한다.^[4]

5. 1. 무모순성

어떤 논리 체계가 모순 명제(빈 시퀀트)의 증명을 허용한다면, 그 체계는 모순적이다.^[4] 증명을 위해 어떤 체계에서 자름-제거 정리가 성립한다고 가정할 때, 만약 그 체계에서 빈 시퀀트를 도출할 수 있다면 자름 규칙을 사용하지 않은 빈 시퀀트 도출 방법도 있어야 한다. 그러나 그러한 방법이 없다는 것은 추론 규칙들을 확인해 보면 쉽게 알 수 있다. 따라서 자름-제거 정리가 성립하는 체계는 무모순적이다.

5. 2. 부분식 성질

자름 제거 정리가 성립하는 체계(최소한 일차 술어 논리)에서는 부분식 성질(subformula property)이 성립한다. 이는 증명 과정에 등장하는 모든 논리식이 귀결의 부분식이 되는 성질이다.^[4] 이 성질은 증명론적 의미론에서 중요하게 사용된다.

5. 3. 크레이그의 보간 정리

자름 제거는 크레이그의 보간 정리를 증명하는 강력한 도구이다.^[4] 프롤로그 프로그래밍 언어를 이끄는 본질적인 통찰력인 해상도를 기반으로 한 증명 검색 가능성은 해당 시스템에서 자름(Cut)의 허용 가능성에 달려 있다.

5. 4. 기타 응용

자동 정리 증명, 프로그램 검증 등 컴퓨터 과학 분야에 응용된다.^[4] 프롤로그와 같은 논리 프로그래밍 언어의 기반이 된다. 커리-하워드 동형 사상에 따라, 자름 제거 알고리즘은 강력한 정규화 속성에 해당한다.

참조

_[1] 서적
_[2] 서적
_[3] 간행물 Beweistheorie http://www.mathemati[...]
_[4] 서적

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

문의하기 : help@durumis.com