프리넥스 표준형

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

1. 개요
2. 정의
- 2.1. 접두사
- 2.2. 매트릭스
3. 프리넥스 표준형으로의 변환
- 3.1. 변환 규칙
- 3.2. 변환 예시
4. 직관 논리에서의 프리넥스 표준형
5. 활용
6. 역사
참조

1. 개요

프리넥스 표준형은 일차 술어 논리 공식의 한 형태이다. 이 형식의 공식은 접두사와 매트릭스로 구성되며, 접두사는 전칭 기호와 존재 기호, 변수를 포함하는 문자열이고, 매트릭스는 전칭 기호를 포함하지 않는 문자열이다. 모든 일차 논리식은 논리적으로 등가인 프리넥스 표준형으로 변환될 수 있으며, 이를 위해 논리 연산자에 따라 다양한 변환 규칙이 적용된다. 직관 논리에서는 모든 논리식이 프리넥스 표준형과 동치인 것은 아니며, 부정 연산자와 함축 연산자가 고전 논리와 다르게 처리되기 때문이다. 이 개념은 증명 계산, 산술적 위계, 분석적 위계 개발에 필수적이며, 괴델의 완전성 정리 증명과 타르스키의 공리에도 활용된다. "프리넥스"라는 용어는 라틴어에서 유래되었으며, 힐베르트와 베르나이스의 저서에서 처음 사용되었다.

더 읽어볼만한 페이지

논리학 - 모순
모순은 논리학, 철학, 과학 등 다양한 분야에서 사용되는 개념으로, 서로 상반되는 두 가지 주장이나 사실이 동시에 존재하는 상태를 의미하며, 특히 헤겔과 마르크스의 변증법적 유물론에서 사물의 내재적 대립으로서 역사 발전의 원동력으로 간주된다.
논리학 - 특수
특수는 철학에서는 개별적이고 구체적인 존재를, 언어학에서는 눈에 띄는 또는 예외적인 의미를 가지며, 사회적으로 특별함이 중요하게 여겨지기도 한다.

2. 정의

1차 술어 논리 공식은 다음과 같은 형태의 공식 $\phi$ 이다.

: $\phi=\phi_{\text{prefix}}\phi_{\text{matrix}}$

여기서

$\phi_{\text{prefix}}$ 는 기호 $\exists$ 와 $\forall$ 및 변수만을 포함하는 문자열이다. 특히, $\land$ 나 $= 및 기타 연산·관계를 포함하지 않는다. 이를 \phi 의 '''접두사'''(프리픽스}})라고 한다.$
$\phi_{\text{matrix/prefix$ ^영어는 기호 $\forall$ 을 포함하지 않는 문자열이다. 즉, 변수와 $\lnot$ , $\land$ , $=$ 및 기타 연산·관계만으로 구성된다. 이를 $\phi$ 의 '''매트릭스'''(matrix^영어)라고 한다.

모든 일차 술어 논리의 논리식에는 (고전 논리에서는) 논리적으로 등가인 冠頭標準形[관두 표준형]의 논리식이 존재한다. 몇 가지 변환 규칙을 재귀적으로 적용함으로써, 논리식을 冠頭標準形[관두 표준형]으로 변환할 수 있다. 규칙은, 논리식에 나타나는 논리 연산자의 종류에 따라 다르다.

2. 1. 접두사

프리넥스 표준형에서 접두사(프리픽스/prefix^영어)는 기호

\exists

와

\forall

및 변수만을 포함하는 문자열이다. 특히,

\land

나

= 및 기타 연산·관계를 포함하지 않는다.

2. 2. 매트릭스

1차 술어 논리 공식

\phi

는

\phi_{\text{prefix}}\phi_{\text{matrix}}

와 같은 형태를 띈다. 이때,

\phi_{\text{matrix}}

는 기호

\forall

을 포함하지 않는 문자열이다. 즉, 변수와

\lnot

,

\land

,

=

및 기타 연산·관계만으로 구성된다. 이를

\phi

의 '''매트릭스'''(matrix^영어)라고 한다.

3. 프리넥스 표준형으로의 변환

모든 일차 논리식은 (고전 논리에서) 어떤 전형 정규형의 논리식과 논리적 동치이다.^[3] 논리식을 전형 정규형으로 변환하기 위해 재귀적으로 적용할 수 있는 여러 변환 규칙이 있다. 이 규칙은 논리식에 나타나는 논리 연산자에 따라 달라진다. 모든 일차 술어 논리의 논리식에는 (고전 논리에서는) 논리적으로 등가인 冠頭標準形[관두 표준형]의 논리식이 존재한다. 몇 가지 변환 규칙을 재귀적으로 적용함으로써, 논리식을 冠頭標準形[관두 표준형]으로 변환할 수 있다. 규칙은, 논리식에 나타나는 논리 연산자의 종류에 따라 다르다.

편의상, 모든 논리합( $\lor$ )이나 함의( $\implies$ )를 논리곱( $\land$ ) 및 부정( $\lnot$ )으로 나타내면 다음과 같이 변환할 수 있다.

$(\forall x\colon\phi)\land\psi$ 를 $\forall x'\colon(\phi[x'/x]\land\psi)$ 로 변환시킨다. 여기서 $x'$ 은 $\psi$ 에 포함되지 않는 임의의 변수이다.
$(\exists x\colon\phi)\land\psi$ 를 $\exists x'\colon(\phi[x'/x]\land\psi)$ 로 변환시킨다. 여기서 $x'$ 은 $\psi$ 에 포함되지 않는 임의의 변수이다.
$\lnot\exists x\colon\phi$ 를 $\forall x\colon\lnot\phi$ 로 변환시킨다.
$\lnot\forall x\colon\phi$ 를 $\exists x\colon\lnot\phi$ 로 변환시킨다.

3. 1. 변환 규칙

모든 일차 논리식은 (고전 논리에서) 어떤 전형 정규형의 논리식과 논리적 동치이다.^[3] 논리식을 전형 정규형으로 변환하기 위해 재귀적으로 적용할 수 있는 여러 변환 규칙이 있다. 이 규칙은 논리식에 나타나는 논리 연산자에 따라 달라진다.

논리곱과 논리합의 규칙은 다음과 같다.

:

(\forall x \phi) \land \psi

는

\forall x ( \phi \land \psi)

와 동치

:

(\forall x \phi) \lor \psi

는

\forall x ( \phi \lor \psi)

와 동치

그리고

:

(\exists x \phi) \land \psi

는

\exists x (\phi \land \psi)

와 동치

:

(\exists x \phi) \lor \psi

는

\exists x (\phi \lor \psi)

와 동치

이다. 이 규칙들은 ''x''가 ψ 내에서 자유 변수로 나타나지 않을 경우에 타당하다. 만약 ''x''가 ψ 내에서 자유 변수로 나타난다면, 다른 자유 변수로 대체해야 한다.

예를 들어, 환의 언어에서,

:

(\exists x (x^2 = 1)) \land (0 = y)

는

\exists x ( x^2 = 1 \land 0 = y)

와 동치이다.

하지만

:

(\exists x (x^2 = 1)) \land (0 = x)

는

\exists x ( x^2 = 1 \land 0 = x)

와 동치가 아니다.

왼쪽 식은, 자유 변수 ''x''가 0일 때 임의의 환에서 참이지만, 오른쪽 식에는 자유 변수가 없고, 어떤 환에서도 거짓이다.

부정의 규칙은

:

\lnot \exists x \phi

는

\forall x \lnot \phi

와 등가이며

그리고

:

\lnot \forall x \phi

는

\exists x \lnot \phi

와 등가이다.

함의에는 네 가지 규칙이 있다. 그 중 두 가지는 전제로부터 양화자를 제거하는 것이고, 나머지 두 가지는 결론으로부터 양화자를 제거하는 것이다. 이 규칙들은 함의

\phi \rightarrow \psi

를

\lnot \phi \lor \psi

로 다시 쓴 다음, 앞서 언급한 논리합에 관한 규칙을 적용하여 얻을 수 있다. 논리합의 규칙과 마찬가지로, 어떤 부분 논리식에 나타나는 양화된 자유 변항이 다른 부분 논리식에 나타나지 않는 것이 조건이 된다.

전제 부분으로부터 양화자를 제거하는 규칙은 다음과 같다.

:

(\forall x \phi ) \rightarrow \psi

는

\exists x (\phi \rightarrow \psi)

와 등가

:

(\exists x \phi ) \rightarrow \psi

는

\forall x (\phi \rightarrow \psi)

와 등가

결론 부분으로부터 양화자를 제거하는 규칙은 다음과 같다.

:

\phi \rightarrow (\exists x \psi)

는

\exists x (\phi \rightarrow \psi)

와 등가

:

\phi \rightarrow (\forall x \psi)

는

\forall x (\phi \rightarrow \psi)

와 등가

3. 1. 1. 논리곱과 논리합

(∀xφ) ∧ ψ ≡ ∀x(φ ∧ ψ) (단, x는 ψ에서 자유 변수가 아님)

(∀xφ) ∨ ψ ≡ ∀x(φ ∨ ψ) (단, x는 ψ에서 자유 변수가 아님)

(∃xφ) ∧ ψ ≡ ∃x(φ ∧ ψ) (단, x는 ψ에서 자유 변수가 아님)

(∃xφ) ∨ ψ ≡ ∃x(φ ∨ ψ) (단, x는 ψ에서 자유 변수가 아님)

환의 언어에서,

:(∃x (x² = 1)) ∧ (0 = y)는 ∃x ( x² = 1 ∧ 0 = y)와 동치이다.

하지만

:(∃x (x² = 1)) ∧ (0 = x)는 ∃x ( x² = 1 ∧ 0 = x)와 동치가 아니다.

왼쪽 식은, 자유 변수 ''x''가 0일 때 임의의 환에서 참이지만, 오른쪽 식에는 자유 변수가 없고, 어떤 환에서도 거짓이기 때문이다.

3. 1. 2. 부정

¬∃xφ는 ∀x¬φ와 동치이다.

¬∀xφ는 ∃x¬φ와 동치이다.

3. 1. 3. 함의

(∀xφ) → ψ ≡ ∃x(φ → ψ) (단, x는 ψ에서 자유 변수가 아님)

(∃xφ) → ψ ≡ ∀x(φ → ψ) (단, x는 ψ에서 자유 변수가 아님)

φ → (∃xψ) ≡ ∃x(φ → ψ) (단, x는 φ에서 자유 변수가 아님)

φ → (∀xψ) ≡ ∀x(φ → ψ) (단, x는 φ에서 자유 변수가 아님)

함의에는 네 가지 규칙이 있다. 그 중 두 가지는 전제로부터 양화사를 제거하는 것이고, 나머지 두 가지는 결론으로부터 양화사를 제거하는 것이다. 이 규칙들은 함의

\phi \rightarrow \psi

를

\lnot \phi \lor \psi

로 다시 쓴 다음, 앞서 언급한 논리합에 관한 규칙을 적용하여 얻을 수 있다. 논리합의 규칙과 마찬가지로, 어떤 부분 논리식에 나타나는 양화된 자유 변항이 다른 부분 논리식에 나타나지 않는 것이 조건이 된다.

전제 부분으로부터 양화자를 제거하는 규칙은 다음과 같다.

:(∀xφ) → ψ는 ∃x(φ → ψ)와 등가

:(∃xφ) → ψ는 ∀x(φ → ψ)와 등가

결론 부분으로부터 양화자를 제거하는 규칙은 다음과 같다.

:φ → (∃xψ)는 ∃x(φ → ψ)와 등가

:φ → (∀xψ)는 ∀x(φ → ψ)와 등가

3. 2. 변환 예시

(φ ∨ ∃xψ) → ∀zρ 를 프리넥스 표준형으로 변환하는 과정은 다음과 같다.

:

(\phi \lor \exists x \psi) \rightarrow \forall z \rho

.

:

( \exists x (\phi \lor \psi) ) \rightarrow \forall z \rho

,

:

\neg( \exists x (\phi \lor \psi) ) \lor \forall z \rho

,

:

(\forall x \neg(\phi \lor \psi)) \lor \forall z \rho

,

:

\forall x (\neg(\phi \lor \psi) \lor \forall z \rho)

,

:

\forall x ( ( \phi \lor \psi) \rightarrow \forall z \rho )

,

:

\forall x ( \forall z (( \phi \lor \psi) \rightarrow \rho ))

,

:

\forall x \forall z ( ( \phi \lor \psi) \rightarrow \rho )

.

이는 원래 공식과 동등한 유일한 프리넥스 표준형이 아니다. 예를 들어 전항보다 후항을 먼저 처리하면 다음과 같은 프리넥스 표준형을 얻을 수 있다.

:

\forall z \forall x ( ( \phi \lor \psi) \rightarrow \rho)

:

\forall z (  (\phi \lor \exists x \psi) \rightarrow \rho )

:

\forall z (  (\exists x (\phi \lor \psi) ) \rightarrow \rho )

,

:

\forall z (  \forall x ( (\phi \lor \psi) \rightarrow \rho ) )

,

:

\forall z \forall x ( (\phi \lor \psi) \rightarrow \rho )

.

범위가 같은 두 개의 전칭 양자화사의 순서는 명제의 의미/진리 값을 변경하지 않는다.

4. 직관 논리에서의 프리넥스 표준형

직관 논리에서는 모든 논리식이 프리넥스 표준형과 동치인 것은 아니다. 부정 연산자가 하나의 장애물이며, 함축 연산자도 직관 논리에서 고전 논리와 다르게 처리된다. 직관 논리에서는 선언과 부정을 사용하여 정의할 수 없다.

BHK 해석은 일부 공식이 직관적으로 동치인 프리넥스 형식을 갖지 않는 이유를 설명한다. 예를 들어, $(\exists x \phi) \rightarrow \exists y \psi$ (1)의 증명은 구체적인 ''x''와 $\phi (x)$ 의 증명이 주어지면, 구체적인 ''y''와 $\psi (y)$ 의 증명을 생성하는 함수이다. 반면, $\exists y ( \exists x \phi \rightarrow \psi)$ (2)의 증명은 단일 구체적인 ''y'' 값과 $\exists x \phi$ 의 모든 증명을 $\psi (y)$ 의 증명으로 변환하는 함수를 생성한다. $\phi$ 를 만족하는 각 ''x''를 사용하여 $\psi$ 를 만족하는 ''y''를 구성할 수 있지만, 그러한 ''x''에 대한 지식 없이 그러한 ''y''를 구성할 수 없는 경우 공식 (1)은 공식 (2)와 동치가 되지 않는다.

직관 논리에서 성립하지 않는 프리넥스 표준형 변환 규칙은 다음과 같다.

:(1) $\forall x (\phi \lor \psi)$ 는 $(\forall x \phi) \lor \psi$ 를 의미한다.

:(2) $\forall x (\phi \lor \psi)$ 는 $\phi \lor (\forall x \psi)$ 를 의미한다.

:(3) $(\forall x \phi) \rightarrow \psi$ 는 $\exists x (\phi \rightarrow \psi)$ 를 의미한다.

:(4) $\phi \rightarrow (\exists x \psi)$ 는 $\exists x (\phi \rightarrow \psi)$ 를 의미한다.

:(5) $\lnot \forall x \phi$ 는 $\exists x \lnot \phi$ 를 의미한다.

(''x''는 (1)과 (3)에서 $\,\psi$ 의 자유 변수로 나타나지 않으며, ''x''는 (2)와 (4)에서 $\,\phi$ 의 자유 변수로 나타나지 않는다.)

5. 활용

증명 계산법은 전형적인 정규형으로 작성된 이론만 다루는 데 사용될 수 있다. 이 개념은 산술적 위계와 분석적 위계를 개발하는 데 필수적이다.

괴델의 완전성 정리에 대한 일차 논리 증명은 모든 공식이 전형적인 정규형으로 재구성되었다는 것을 전제로 한다.

타르스키의 공리는 기하학의 논리 체계로, 모든 문장을 '''전칭-존재 형식'''으로 작성할 수 있으며, 이는 모든 전칭 기호가 모든 존재 기호 앞에 오는 전형적인 정규형의 특수한 경우이다. 따라서 모든 문장은 <math>\forall u</math> <math>\forall v</math> <math>\ldots</math> <math>\exists a</math> <math>\exists b</math> <math>\phi</math> 형식으로 다시 쓸 수 있다. 여기서 <math>\phi</math>는 어떤 기호도 포함하지 않는 문장이다. 이러한 사실은 타르스키가 유클리드 기하학이 결정 가능하다는 것을 증명할 수 있게 했다.

6. 역사

프리넥스(prenex^영어)라는 단어는 "묶인", "고정된"을 의미하는 라틴어 프라이넥수스/praenexus^la에서 유래했다. 이 용어는 다비트 힐베르트와 파울 베르나이스의 1938년 저서 《수학의 기초》(Grundlagen der Mathematik^영어)에서 처음 사용되었다.

참조

_[1] 웹사이트 tied or bound up in front http://cs.nyu.edu/pi[...] nyu.edu 2011-05-27
_[2] 서적
_[3] 서적

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

문의하기 : help@durumis.com

프리넥스 표준형
일반 정보
분야	논리학, 수학
하위 분야	수리 논리학
복잡도	결정 불가능
정의
정의	한정 기호가 모두 수식의 맨 앞으로 이동된 논리식
관련 개념
관련 개념	정규형