맨위로가기

스콜렘 표준형

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

1. 개요

스콜렘 표준형은 노르웨이 수학자 토랄프 스콜렘의 이름을 따서 명명되었으며, 일계 술어 논리에서 모든 존재 양화사를 제거한 형태를 말한다. 스콜렘화는 2차 논리의 동치 관계와 1차 논리 만족도의 정의를 적용하여 작동하며, 자동 정리 증명에서 1차 논리 공식을 절 형태로 변환하는 데 사용된다. 스콜렘 이론은 특정 조건을 만족하는 이론을 의미하며, 모든 스콜렘 이론은 모델 완전 이론이다. 스콜렘화의 쌍대 개념으로는 자크 에르브랑의 에르브랑화가 있다.

더 읽어볼만한 페이지

  • 술어 논리 - 양화
    양화는 논리학과 수학에서 명제의 범위를 지정하는 개념으로, '모든', '어떤'과 같은 의미를 나타내며, 전칭 양화자 '∀'와 존재 양화자 '∃' 등의 기호로 표현된다.
  • 술어 논리 - 존재 양화사
    존재 양화사는 형식 논리에서 특정 조건을 만족하는 대상이 존재함을 나타내는 방법으로, 수리 논리학에서는 기호 "\exists"를 사용하여 변수가 특정 집합에 속하면서 주어진 조건을 만족하는 원소가 적어도 하나 존재함을 나타내며, 존재 일반화, 존재 제거 등의 추론 규칙과 관련이 있고, 담화 영역에 따라 진술의 참과 거짓이 달라질 수 있으며, 존재 양화된 명제 함수의 부정은 해당 명제 함수의 부정의 전칭 양화와 논리적으로 동치이다.
  • 모형 이론 - 괴델의 불완전성 정리
    괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
  • 모형 이론 - 괴델의 완전성 정리
    괴델의 완전성 정리는 1차 논리 이론에서 모형 이론적 진리와 증명 이론적 진리가 같음을 나타내며, 연역 체계가 완전함을 보장하고 일차 논리에서 통사론적 결과와 의미론적 결과가 동일하다는 것을 의미한다.
스콜렘 표준형
개요
유형논리식의 정규형
분야수리 논리학, 자동 정리 증명
발견자토랄프 스콜렘
정의
설명모든 존재 양 quantification사를 함수로 대체하여 모든 전칭 양 quantification사가 식의 맨 앞으로 이동되도록 변환된 논리식
변환 과정
단계

응용
분야자동 정리 증명, 논리 프로그래밍

2. 역사

스콜렘 표준형은 노르웨이의 수학자 토랄프 스콜렘의 이름을 따서 명명되었다.[1] 자크 에르브랑의 에르브랑화(Herbrandization)는 스콜렘화의 쌍대로, 충족 가능성은 보존하지 않으나 타당성은 보존한다.

3. 정의

스콜렘 표준형은 존재 양화사(∃)를 제거하고, 이를 스콜렘 함수로 대체하는 방식으로 정의된다. 우선, 보편 양화사(∀)의 범위에 들어있지 않은 존재 양화된 변수는 새로운 상수를 도입하여 치환할 수 있다. 예를 들어, \(\exists x P(x)\)는 \(P(c)\)로 치환할 수 있는데, 여기서 \(c\)는 이전에 나타나지 않은 새로운 상수이다.

더 일반적인 경우, 모든 존재 양화된 변수 \(y\)는 새로운 함수 기호 \(f\)를 사용하여 \(f(x_1, ..., x_n)\) 형태로 치환된다. 여기서 \(f\)는 스콜렘 함수라고 불린다. 만약 식이 관두 표준형(모든 양화사가 식의 맨 앞에 오는 형태)이라면, \(x_1, ..., x_n\)은 \(y\)를 양화하는 양화사보다 앞에 오는 보편 양화사들에 의해 양화되는 변수들이다.

2차 논리의 관점에서 보면, 스콜렘화는 \(\forall x \exists y . R(x,y)\)와 \(\exists f \forall x . R(x,f(x))\)가 동치라는 점에서 성립한다. 그러나 1차 논리에서는 모델론적 수단을 통해 간접적으로 이루어지므로, 충족 가능성은 보존되지만 동치성은 보장되지 않는다.

3. 1. 관두 표준형 (Prenex Normal Form)

1차 논리에서 임의의 논리식은 논리식의 가장 앞에 모두 부정형이 아닌 전칭 기호(∀)나 존재 기호(∃)를 가지며, 그 작용역이 모두 논리식의 끝까지 미치는 표준형으로 고칠 수 있다.[7]

이러한 표준형을 '''관두 표준형'''(prenex normal form)이라고 부른다.[7] 관두 표준형의 가장 앞에서부터 세어 존재 기호(∃) 앞에 있는 전칭 기호(∀)의 수를, 그 관두 표준형의 '''차수'''(degree)라고 부른다.[7]

3. 2. 스콜렘 표준형 (Skolem Normal Form)

스콜렘 표준형은 1차 논리식에서 모든 존재 기호를 제거한 형태이다. 존재 양화된 변수 y는 스콜렘 함수 f(x₁, ..., xₙ)로 대체된다.

예를 들어, 논리식 \forall x \exists y \forall z P(x,y,z)는 존재 기호 \exists y를 포함하므로 스콜렘 표준형이 아니다. 스콜렘화는 y를 새로운 함수 기호인 f(x)로 대체하고 y에 대한 수량 기호를 제거한다. 결과 수식은 \forall x \forall z P(x,f(x),z)이다. 스콜렘 항 f(x)는 x를 포함하지만 z는 포함하지 않는데, 이는 제거할 수량 기호 \exists y가 \forall x의 범위 내에 있지만 \forall z의 범위 내에 있지 않기 때문이다. 이 수식이 전치 정규형이므로, 이는 수량 기호 목록에서 x가 y보다 앞서고 z는 그렇지 않다는 것과 같다. 이 변환을 통해 얻은 수식은 원래 수식이 만족 가능한 경우에만 만족 가능하다.

일반적으로, 스콜렘화는 모든 존재적으로 수량화된 변수 y를 함수 기호 f가 새로운 항 f(x_1,\ldots,x_n)으로 대체하여 수행된다. 이 항의 변수는 다음과 같다. 수식이 전치 정규형인 경우 x_1,\ldots,x_n은 전칭적으로 수량화되고 y의 수량 기호보다 앞에 오는 변수이다. 이 과정에서 도입된 함수 f는 '''스콜렘 함수'''(또는 차수가 0인 경우 '''스콜렘 상수''')라고 불리며, 이 항은 '''스콜렘 항'''이라고 불린다.[1]

2차 논리의 시점에서 보면 스콜렘화는 그러한 y의 존재와 적절한 함수 f의 존재가 동치인 것으로부터 성립하는 원리이다. 곧 \forall x \exists y . R(x,y)와 \exists f \forall x . R(x,f(x))의 동치를 이른다. 그러나 1차 논리에서 이는 모델론적 수단을 통해 간접적으로 이루어지며 따라서 충족가능성은 보존되나 동치성은 보장되지 않는다.[1]

4. 스콜렘화의 작동 원리

스콜렘화는 2차 논리에서의 다음 동치 관계와 1차 논리 만족도의 정의를 기반으로 작동한다.[1]

:\forall x \exists y R(x,y) \iff \exists f \forall x R(x,f(x))

여기서 f(x)는 x를 y로 매핑하는 함수이다.

직관적으로, "모든 x에 대해 R(x,y)를 만족하는 y가 존재한다"는 명제는 "모든 x를 y로 매핑하는 함수 f가 존재하여, 모든 x에 대해 R(x,f(x))가 성립한다"는 명제와 동치이다.[1]

1차 논리 모델은 모든 함수 기호의 해석을 포함하므로, 스콜렘 함수는 모델의 존재성(\exists M)에 의해 암묵적으로 존재 양화된다. 따라서 변수에 대한 존재 양화사를 함수에 대한 존재 양화사로 대체한 후에도, 이 존재 양화사를 제거하여 공식을 1차 논리 공식으로 취급할 수 있다.[1]

예를 들어, 논리식 \forall x \exists y \forall z. P(x,y,z)를 살펴보자. 이 식에는 존재 한정자 \exists y가 있으므로 스콜렘 표준형이 아니다. 스콜렘화에서는 y를 f(x)로 대체하는데, 여기서 f는 새로운 함수 기호이며, 치환과 동시에 y의 한정자를 제거한다. 결과적으로 얻어지는 논리식은 \forall x \forall z . P(x,f(x),z)가 된다. 스콜렘 항 f(x)는 x는 포함하지만 z는 포함하지 않는데, 이는 제거된 한정자 \exists y가 \forall x의 범위에는 들어가지만, \forall z의 범위에는 들어가지 않기 때문이다.[1]

스콜렘화의 정당성은 선택 공리를 통해 증명될 수 있다.[1]

5. 스콜렘화의 활용

스콜렘 표준형은 자동 정리 증명에서 1차 논리 공식을 절(clause) 형태로 변환하는 데 활용된다. 예를 들어, 분석적 타블로 방법에서 존재 양화된 공식이 나타날 때마다 스콜렘화를 통해 해당 양화사를 제거할 수 있다.[2] 예를 들어, \exists x \Phi(x,y_1,\ldots,y_n)이 타블로에 나타나고, 여기서 x,y_1,\ldots,y_n은 \Phi(x,y_1,\ldots,y_n)의 자유 변수일 경우, \Phi(f(y_1,\ldots,y_n),y_1,\ldots,y_n)을 타블로의 동일한 분기에 추가할 수 있다. 이러한 추가는 타블로의 만족 가능성을 변경하지 않는다. 이전 공식의 모든 모델은 f에 대한 적절한 해석을 추가하여 새 공식의 모델로 확장될 수 있다.

이러한 형태의 스콜렘화는 공식 내에서 자유로운 변수만 스콜렘 항에 배치한다는 점에서 "고전적인" 스콜렘화보다 개선된 것이다. 이는 타블로의 의미론이 공식 자체에 없는 보편적으로 정량화된 변수의 범위에 암묵적으로 공식을 배치할 수 있기 때문에 개선된 것이다. 이러한 변수는 스콜렘 항에 존재하지 않지만, 스콜렘화의 원래 정의에 따르면 존재했을 것이다. 또 다른 개선 사항은 변수 이름 바꾸기를 최대로 하여 동일한 공식에 동일한 스콜렘 함수 기호를 적용하는 것이다.[2]

스콜렘 표준형은 (일차 논리에서의 해법)에서도 활용되며, 여기서 공식은 보편적으로 정량화된 것으로 이해되는 절 집합으로 표현된다.

모형 이론의 중요한 결과인 뢰벤하임-스콜렘 정리는 이론을 스콜렘화하고 결과 스콜렘 함수 아래에서 닫음으로써 증명할 수 있다.[3]

6. 스콜렘 이론 (Skolem Theories)

어떤 이론 ''T''에서 자유 변수 x₁, ..., xₙ, y를 가진 각 공식에 대해 y에 대한 스콜렘 함수임을 증명할 수 있는 n항 함수 기호 F가 존재하면, ''T''를 '''스콜렘 이론'''이라고 한다.[4]

모든 스콜렘 이론은 모델 완전 이론이다. 즉 모델의 모든 부분 구조가 기본 부분 구조이다. 스콜렘 이론 ''T''의 모델 ''M''이 주어졌을 때, 특정 집합 ''A''를 포함하는 ''M''의 가장 작은 부분 구조를 ''A''의 '''스콜렘 헐'''이라고 한다. ''A''의 스콜렘 헐은 ''A''에 대한 원자 소 모델이다.

7. 에르브랑화 (Herbrandization)

자크 에르브랑의 에르브랑화(Herbrandization)는 충족가능성은 보존하지 않으나 타당성은 보존한다.[1]

참조

[1] 웹사이트 Normal Forms and Skolemization http://www.mpi-inf.m[...] Max-Planck-Institut für Informatik 2012-12-15
[2] 서적 Tableaux and related methods Handbook of Automated Reasoning
[3] 논문 The Lowenheim-Skolem Theorem http://ozark.hendrix[...] 2009
[4] 간행물 "Sets, Models and Proofs" (3.3) by I. Moerdijk and J. van Oosten https://webspace.sci[...]
[5] 문서 スコーレム化（Skolemization）によって得られる標準形の論理式は元の論理式と等価とは限らないが、その充足可能性は同値である。
[6] 서적 ヒルベルト、アッケルマン(1954) p.95
[7] 서적 この冠頭標準形の利点は、前置記号の後の論理式を命題論理における複合命題と同等に扱うことができるところにある。また考慮すべき論理式の範囲を著しく限定することができるため、論理式の一般的な性質を明らかにするにあたって都合が良い


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

문의하기 : help@durumis.com