직관주의 논리

직관주의 논리는 때때로 건설적 논리라고 더 일반적으로 불리는, 건설적 증명의 개념을 더 가까이 반영함으로써 고전적 논리에 사용되는 체계와 다른 상징적 논리의 체계를 말합니다. 특히 직관주의 논리학의 체계는 고전 논리학의 기본 추론 규칙인 배제된 중간과 이중 부정 제거의 법칙을 가정하지 않습니다.

형식화된 직관주의 논리는 원래 L.E.J. 브루어의 직관주의 프로그램의 형식적 기초를 제공하기 위해 아렌트 헤이팅에 의해 개발되었습니다. 증명이론적 관점에서 보면, 헤이팅의 미적분학은 배제된 중간과 이중 부정 제거의 법칙이 제거된 고전 논리학의 제약입니다. 제외된 중간 및 이중 부정 제거는 사례별로 일부 명제에 대해 여전히 증명될 수 있지만 고전 논리처럼 보편적으로 유지되지는 않습니다. 직관주의 논리의 표준적인 설명은 BHK 해석입니다.^[1]

직관주의 논리에 대한 몇 가지 의미 체계가 연구되었습니다. 이러한 시맨틱스 중 하나는 고전적인 부울 값 시맨틱스를 반영하지만 부울 대수 대신 헤이팅 대수를 사용합니다. 또 다른 의미론은 Kripke 모델을 사용합니다. 그러나 이것들은 브루어의 본래 비공식적 의미 직관의 형식화보다는 헤팅의 연역 체계를 연구하기 위한 기술적 수단입니다. 이러한 직관을 포착한다고 주장하는 의미론적 시스템은 커트 괴델의 변증법 해석, 스티븐 콜 크린의 실현 가능성, 유리 메드베데프의 유한 문제 논리 또는 ^[2]기오르기 자파리드제의 계산 가능성 논리입니다. 그러나 그러한 의미론은 헤이팅의 논리보다 더 강한 논리를 지속적으로 유도합니다. 일부 저자들은 이것이 헤이팅의 미적분학 자체의 불충분함을 나타내는 것일 수 있으며 후자를 건설적인 논리로 간주한다고 주장했습니다.^[3]

수학적 구성주의

고전 논리학의 의미론에서 명제 공식은 두 요소 집합$${$$⊤, ⊥ } ${\displaystyle$ \{\top,\bot \}(각각 참 및 "거짓")에서 진리 값을 할당합니다. 이를 '배제된 중간의 법칙'이라고 하는데, 이는 '참'이나 '거짓' 이외의 어떤 진리값의 가능성을 배제하기 때문입니다. 이와 대조적으로, 직관주의 논리에서 명제 공식은 명확한 진리값을 부여하지 않으며, 우리가 직접적인 증거를 가지고 있을 때만 "진정한" 것으로 간주되며, 따라서 증명이 됩니다. (우리는 직접적인 증거로 인해 명제 공식이 "사실"이 되는 대신, 커리-하워드 의미의 증거가 존재한다고 말할 수도 있습니다.) 따라서 직관주의 논리의 작동은 진실-평가보다는 증거와 증명가능성에 관한 정당성을 보존합니다.

직관주의 논리는 수학에서 구성주의 접근법을 개발할 때 흔히 사용되는 도구입니다. 일반적으로 구성주의 논리의 사용은 수학자와 철학자들 사이에서 논란이 된 주제입니다(예를 들어, 브루어-힐베르트 논쟁 참조). 그들의 사용에 대한 일반적인 반대는 위에서 언급한 고전 논리의 두 가지 중심 규칙, 즉 배제된 중간 및 이중 부정 제거의 법칙이 없다는 것입니다. 데이비드 힐버트는 수학의 실천에 있어서 그것들이 매우 중요하다고 생각하여 다음과 같이 썼습니다.

"수학자로부터 중간을 제외하는 원리를 취하는 것은, 예를 들어 망원경을 천문학자나 권투선수에게 주먹을 사용하는 것을 제공하는 것과 같습니다. 존재 진술과 배제된 중간의 원리를 금지하는 것은 수학의 과학을 완전히 포기하는 것과 같습니다."^[4]

직관주의 논리학은 이러한 규칙을 사용할 수 없음으로 인해 발생하는 어려움에도 불구하고 수학에서 실용화를 발견했습니다. 그 한 가지 이유는 그것의 제약이 존재하는 성질을 가진 증명을 생성하기 때문에 다른 형태의 수학적 구성주의에도 적합하기 때문입니다. 비공식적으로, 이것은 물체가 존재한다는 건설적인 증거가 있는 경우, 그 건설적인 증거가 그 물체의 예를 생성하기 위한 알고리즘으로 사용될 수 있음을 의미하며, 증명과 알고리즘 사이의 Curry-Howard 대응으로 알려진 원리입니다. 이러한 직관주의 논리의 특별한 측면이 매우 가치 있는 한 가지 이유는 실무자들이 증명 보조자로 알려진 광범위한 컴퓨터화된 도구를 사용할 수 있도록 하기 때문입니다. 이러한 도구는 사용자가 대규모 증명을 생성하고 검증하는 데 도움이 되며, 이 도구의 크기는 보통 수학적 증명을 게시하고 검토하는 데 들어가는 일반적인 인간 기반 검사를 방해합니다. 따라서 현대 수학자와 논리학자는 아그다나 코크와 같은 증명 보조 도구를 사용하여 손으로만 만들고 확인할 수 있는 시스템을 넘어 매우 복잡한 시스템을 개발하고 증명할 수 있습니다. 공식적인 검증 없이는 만족스럽게 검증할 수 없었던 증명의 한 예로 유명한 4색 정리의 증명이 있습니다. 이 정리는 가능한 반례의 많은 종류를 배제하는 증명이 개발될 때까지 100년 이상 수학자들을 괴롭혔지만, 여전히 증명을 끝내기 위해 컴퓨터 프로그램이 필요하다는 충분한 가능성을 열어두었습니다. 그 증명은 한동안 논란이 있었지만, 나중에 Coq를 사용하여 검증되었습니다.

구문

직관주의 논리의 공식 구문은 명제 논리나 1차 논리와 유사합니다. 그러나 직관주의적 연결은 고전 논리에서와 같은 방식으로 서로에 대해 정의할 수 없으므로 선택에 문제가 있습니다. 직관주의 명제 논리(IPL)에서는 →, ∧, ∨, ⊥를 기본 연결어로 사용하는 것이 일반적이며, ¬ A를 (A → ⊥)의 약어로 취급합니다. 직관주의적 1차 논리에서는 양자 ∃, ∀가 필요합니다.

힐베르트식 미적분학

직관주의 논리는 다음과 같은 힐베르트식 미적분학을 통해 정의할 수 있습니다. 이것은 고전 명제 논리를 공리화하는 방법과 유사합니다.^[5]

명제 논리에서 추론 규칙은 modus ponens입니다.

• MP: ϕ → ψ {\$displaystyle$\$phi$ \ to$$\psi } 및 ϕ {\displaystyle \phi} 추론 ψ {\displaystyle \psi }

그리고 공리는

• N-1: ψ → (ϕ → ψ) ${\displaystyle \$psi \to (\phi \to \psi )}
• 그런 다음-2$:$ (χ ${\displaystyle }$→ (ψ →${\displaystyle }$ϕ ) → (χ → ϕ) → (χ → ψ) ${\displaystyle$ {\big}\chi \to (\phi \to \psi $){\$big}}\to {\big}}\to {\big}}
• AND-1:${\displaystyle }$ϕ ∧ χ →$$ϕ {\displaystyle \phi$\$land \chi $\$to \phi}
• AND-2:${\displaystyle }$ϕ ∧ χ →$$χ {\displaystyle $\phi$\land \chi$$\to \chi }
• AND-3: ϕ → (χ → (ϕ ∧ χ$)) {\displaystyle$ \phi \to {\big(}\chi \to {\phi$$\land \chi ){\big}}
• OR-1: ϕ →$$ϕ ∨ χ {\displaystyle \phi$\$to \phi$$\lor \chi}
• OR-2: χ →$$ϕ ∨ χ {\displaystyle \chi \to \phi$$\lor \chi}
• OR-3:$$(ϕ $$→ ψ${\displaystyle )}$ → (χ $$→ ψ${\displaystyle )}$ →${\displaystyle }$(ϕ ∨ χ → ) ψ$) {\displaystyle(\phi \to$ \psi$)\$to ${\big(}(\chi$\lor \chi )\to {\psi)} {\big(}(\phi \lor \chi )}}
• $FALSE$: ⊥ → ϕ {\$displaystyle$\bot \to \phi$}$

이것을 1차 술어 논리의 체계로 만들기 위해, 일반화 규칙은

• ${\displaystyle \forall }$-GEN: from ${\displaystyle \psi \to \phi }$ infer ${\displaystyle \psi \to (\forall x\ \phi )}$, if ${\displaystyle x}$ is not free in ${\displaystyle \psi }$
• ${\displaystyle \exists }$-GEN: from ${\displaystyle \phi \to \psi }$ infer ${\displaystyle (\exists x\ \phi )\to \psi }$, if ${\displaystyle x}$ is not free in ${\displaystyle \psi }$

공리와 함께 추가됩니다.

• PRED-1:${\displaystyle (}$∀${\displaystyle }$x ϕ (${\displaystyle x}$ )) → ϕ (t) ${\displaystyle (\forall$x\$$\phi (x))\$to$ $\$phi (t)}$$ϕ에서$$t {\displaystyle t} 항이$$$변수$x {\$displaystyle$x}(즉, $\$displaystyle x)로 자유롭게 대체할 수 있습니다. ${\displaystyle t}$에서 $변수$가 발생하지 ${\displaystyle \mathrm{않으면}}$ϕ에서 바인딩됩니다(t ) ${\displaystyle$ \phi$($t)).
• PRED-2:${\displaystyle }$ϕ (${\displaystyle \text{t}}$)${\displaystyle \mathrm{}}$→ (exists$x$ ϕ (x))${\displaystyle \phi (t)\$to$$(\∃ x\ \phi (x))}, PRED-1과 동일한 제한이 있습니다.

부정

$연결$¬ {\displaystyle\n을 포함하려는 경우$eg$$}$은$($는) $⊥→$ $ϕ$ {\displaystyle \phi \to \bot}의 약어로 간주하기보다는 다음과 같이 추가하면 됩니다.

• NO-1':$$(ϕ → ⊥$)$ → ¬ ϕ {\$displaystyle$(\phi \to \bot $)\$ to \n$eg \phi}$
• NOT-2':$$¬ ϕ → (ϕ → ⊥) {\displaystyle \n$eg \phi \to (\phi \to \bot )}$

$연결$⊥ {\$displaystyle$\bot}을(를) 생략하려는 경우 사용할 수 있는 여러 가지 대안이 있습니다(거짓). 예를 들어, FALSE, NOT-1', NOT-2' 세 개의 공리를 두 개의 공리로 대체할 수 있습니다.

• NO-1:$$(ϕ ${\displaystyle }$→$$χ${\displaystyle )}$ → ${\displaystyle \mathrm{((}}$ϕ ${\displaystyle }$→ ¬ χ) → ¬ ϕ) {\displaystyle(\phi \$to$ \chi )\ to {\big(}(\phi \to \n))$예를 들어 \chi )\n에게$$eg \phi {\big )}}}$
• 참고-2: χ → (¬ χ → ψ) {\$displaystyle$ \chi \to (\n)$예를 들어 \chi \to \psi )}$

명제적 미적분학 § 공리에서와 같이. NOT-1의 대안은$$(ϕ → ¬ χ) → (χ → ¬ ϕ) {\displaystyle (\phi \ to \n)입니다.$예를 들어 \chi )\to (\chi \to \n$$eg \phi )}$ 또는$$($ϕ$ $→$ $¬ ϕ$) $→$ $¬ ϕ$${\displaystyle$(\phi \ to \n)$eg \phi )\to \n$$예$를 들어 $\phi$

등가성

등가성을 위한 연결 ↔ $$$displaystyle \leftrightarrow }$은(는) ∧ χ(ϕ → χ) ϕ (χ → ϕ) {\displaystyle \leftrightarrow \chi}을 나타내는 약어로 $취급$될 수 있습니다. 또는 공리를 추가할 수도 있습니다.

• IFF-1:$$(ϕ $$↔ χ) → (ϕ $$→ χ) {\$displaystyle (\phi \leftarrow$\chi )\to (\phi \to \chi )}
• IFF-2:$$(ϕ ${\displaystyle }$↔ χ) → (χ $$→ ϕ) {\displaystyle (\phi \leftarrow $\$chi )\to (\chi \to \phi )}
• IFF-3:$$(ϕ → χ) → (χ → ϕ) → (ϕ ↔ χ) {\displaystyle (\phi \to \chi )\to ((\chi$$\to \phi )\to (\phi \left arrow \chi )}

IFF-1과 IFF-2는 원하는 경우 연결을 사용하여 단일 공리$($ϕ $$↔ χ${\displaystyle )}$ → ((ϕ $$→ χ) ∧(χ → ϕ) {\displaystyle(\phi \leftrightarrow \chi )\to((\phi \to \chi )\land(\chi \to \phi )}로 결합할 수 있습니다.

수열적분학

게르하르트 겐첸은 그의 체계 LK(고전적 논리에 대한 그의 순차적 연산)의 단순한 제한이 직관주의 논리에 대해 건전하고 완전한 체계를 초래한다는 것을 발견했습니다. 그는 이 체계를 LJ라고 불렀습니다. LK에서 어떤 수의 공식도 연속체의 결론 면에 나타나는 것이 허용되지만 반대로 LJ는 이 위치에 기껏해야 하나의 공식만 허용합니다.

LK의 다른 도함수는 직관적인 도함수로 제한되지만 여전히 여러 결론을 순차적으로 허용합니다. LJ'^[6]가 한 예입니다.

정리

순수 논리의 정리는 공리와 추론 규칙에서 증명할 수 있는 진술입니다. 예를 들어, TN-2에서 TN-1을 사용하면$$(χ $$→ (ϕ $$→${\displaystyle }$ψ) → (ϕ → ψ) {\displaystyle {\big}\chi \to (\phi \to \psi ){\big}}\to {\big}}\to {\big(}\chi \to \psi ){\big}}}로 줄어듭니다. 힐버트 시스템을 사용하는 후자의 공식적인 증명은 해당 페이지에 나와 있습니다. ψ${\$displaystyle \psi $}$에 대한 ⊥ ${\$displaystyle $\$bot}을 사용하면, 이것은 차례로 (χ → ¬ ϕ) → (ϕ → ¬ χ) {\displaystyle (\chi \to \n)을 의미합니다.$eg \phi )\to (\phi \to \n$$eg \chi$ $)\}.$ 다시 말해서,$$"$χ$ ${\$displaystyle \chi}가 케이스라는 것이$$$ϕ$${\$displaystyle \phi}가 터무니없다는 것을 $의미$한다면, ϕ$${\$displaystyle$\phi}이(가) 유지되는 경우 {\displaystyle \chi} χ은 그렇지 않습니다." 문장의 대칭성으로 인해 실제로 하나가 얻어졌습니다.

${\displaystyle(\chi \to \n)예를 들어 \phi )\left right 화살표(\phi \to \n)eg \chi )}$

직관주의 논리학의 정리를 고전 논리학의 용어로 설명할 때, 그것은 그것의 약화로 이해될 수 있습니다. 그것은 추론자가 추론할 수 있도록 허용하는 동시에 고전적 논리 하에서는 할 수 없었던 새로운 추론을 허용하지 않는다는 점에서 더 보수적입니다. 직관주의 논리의 각 정리는 고전 논리의 정리이지만, 그 반대는 아닙니다. 고전 논리학의 많은 논어들은 직관주의 논리학의 정리가 아닙니다 – 특히 위와 같이 직관주의 논리학의 주요 목표 중 하나는 모순에 의한 비구조적 증명의 사용을 활성화하기 위해 배제된 중간의 법칙을 긍정하지 않는 것입니다. 존재를 증명하는 대상에 대한 명시적인 예를 제공하지 않고 존재 주장을 제공하는 데 사용될 수 있습니다.

이중부정

배제된 중간의 법칙을 "긍정하지 않는" 것에 불과할 뿐인데, 그 법칙이 반드시 어떤 맥락에서 유지되는 것은 아니지만, 어떠한 반례도 제시할 수 없기 때문입니다. 그러한 반례는 고전적 논리 하에서는 허용되지 않는 추론(특정 명제에 대한 법의 부정을 추론하는 것)일 것이므로 직관주의 논리와 같이 엄격한 약화에서는 허용되지 않습니다. 형식적으로, 임의의 두 명제에 대해$$(ψ ∨ (ψ → φ${\displaystyle )}$ → φ) φ {\displaystyle ${\big(}(\$psi \lor$(\to$ \varphi$))\$to \varphi {\big)}\좌측 화살표 \varphi}라는 간단한 정리입니다. 거짓으로 설정된 임의의$$φ {\displaystyle$$\varphi}을(를) 고려하면 이는 실제로${\displaystyle 법}$¬ ¬(ψ ∨ ¬ ψ$)$ {\displaystyle \n의 이중 부정이 있음을 보여줍니다.$예 \n$$eg(\psi \lor \n)$$eg$ \$psi$ )}은(는) 최소 논리에서 이미 자동화로 유지됩니다. 그래서 명제적 미적분학은 항상 고전적 논리와 양립할 수 있습니다. 그 법칙이 명제를 내포한다고 가정할 때, 두 번의 배치를 적용하고 이중 네거티브 배제된 중간을 사용함으로써, 다양한 엄격하게 고전적인 종양학의 이중 네거티브 변형을 증명할 수 있습니다. 술어 논리 공식의 경우 일부 정량화된 표현이 부정될 때 상황이 더 복잡합니다.

위와 유사하게 ψ ${\displaystyle }$→ ((ψ ${\displaystyle }$→ φ${\displaystyle )}$ → φ) 형태의 modus ponen부터 \displaystyle \psi \to ((\psi \to \varphi )\to \varphi )}까지 ψ → ¬ ¬ ψ {\displaystyle \psi \to \n를 따릅니다.$예 \n$$예$를 들어, \$psi$ 이들 사이의 관계는 항상 새로운 공식을 얻는 데 사용될 수 있습니다. 약화된 전제는 강력한 의미를 부여하며, 그 반대의 경우도 마찬가지입니다. 예를 들어$,$ 만약${\displaystyle }$(¬ ¬ ψ) →$$ϕ {\displaystyle(\n표시 스타일)이면 다음과 같습니다.$예 \n$$예$를 들어$,$\$psi)\$to \phi}는 유지되며, 그러면$$$ψ →$ $ϕ$ ${\displaystyle$ \$psi$ \to \phi}도 유지되지만, 반대 방향의 스키마는 이중 네거티브 제거 원리를 의미합니다. 이중 부정 제거가 가능한 명제를 안정이라고도 합니다. 직관주의 논리는 부정된 형태의 명제와 같이 제한된 유형의 명제에 대해서만 안정성을 증명합니다. 배제된 중간 홀드에 대한 공식은 아래에서 더 자세히 설명하는 교집합 삼단 논법을 사용하여 안정적임을 증명할 수 있습니다. 그러나 현재 제외된 중간 문장 자체가 안정적이지 않는 한, 그 반대는 일반적으로 성립하지 않습니다. ψ →$$ϕ {\$displaystyle$ \psi to \phi}보다 약하지만 ¬ ¬(ψ → ϕ) {\displaystyle \n$예 \n$$eg (\psi$\to$$\phi )}, 자체적으로 세 개의 동등한 $문장$을 의미하는${\displaystyle \mathrm{}}$$ψ$ $→$ ($¬ ¬ ϕ$) ${\$displaystyle \$psi$ \to (\n)$예 \n$$eg \phi$ $)\},$ ${\displaystyle \mathrm{\neg }\mathrm{\varphi \; \to }}$$eg \phi \to \n$$eg \psi$} 및${\displaystyle }$($¬ ¬ ψ$)${\displaystyle \mathrm{}}$$→$ ($¬ ¬ ϕ$) {\$displaystyle$(\n표시 스타일)$예 \n$$예를 들어 \psi)\to(\n)$$예 \n$$eg \phi )}.$앞의 네 가지는 교의적 삼단 논법을 사용하여 실제로 동등합니다. ${\displaystyle 이}$는 또한 직관적으로 유효한${\displaystyle \mathrm{}}$¬ ¬(¬ ¬ ϕ → ϕ) {\displaystyle \n을 유도합니다.$예 \n$$eg(\n$$)$$예 \n$$예$를 들어, \$phi \to \phi )}$이므로 항등식과 같습니다.

ψ$${\displaystyle \psi}가 클레임을 표현하면 이중 네거티브 ¬ ¬ ψ {\displaystyle \n$예 \n$$eg \psi$}은(는)$$$ψ$ ${\displaystyle$ \$psi$}의 반박이 일관되지 않을 것이라는 주장을 표현하는 것일 뿐입니다. 그러한 단순한 이중 부정이 입증된 것도 여전히 부정 도입을 통해 다른 진술을 부정하는 데 도움이 됩니다$.$ (ϕ → ¬ ψ) → ¬ ϕ {\displaystyle(\phi \to \n)$예를 들어 \psi)\n로$$예$를 들어 $\phi$ 이중 부정된 존재적 진술은 재산을 가진 실체의 존재를 의미하지 않으며, 오히려 그러한 실체의 existence이 아닌 것으로 추정되는 부조리. 또한 다음 섹션에서 계량기와 관련된 모든 원칙은 가상적 존재를 전제로 한 함의 사용을 설명합니다.

수식번역

존재 한정자(및 원자) 앞에 두 개의 부정을 추가하여 문을 약화시키는 것도 이중 부정 번역의 핵심 단계입니다. 그것은 고전적인 1차 논리를 직관적 논리에 포함시키는 것을 구성합니다: 1차 공식은 Gödel-Gentzen 번역이 직관적으로 증명될 수 있는 경우에만 고전적 논리에서 증명될 수 있습니다. 예를 들어, ψ → ϕ {\displaystyle${\displaystyle }$\psi \to \phi} 형태의 고전 명제 논리의 모든 정리는 ψ → ¬ ¬ ϕ {\displaystyle \psi \to \n에 대한 직관적 증명으로 구성된 증명을 가지고 있습니다.$예 \n$$예$를 들어 $\phi}$ 다음에$$ 이중 부정 제거를 한 번 적용합니다. 따라서 직관주의 논리는 고전적 논리를 건설적 의미론으로 확장하는 수단으로 볼 수 있습니다.

연산자의 비간단성

이미 최소한의 논리는 부정을 사용한 함의에 대한 접속 응답 해체와 관련하여 다음 세 가지 정리를 쉽게 증명합니다.

${\displaystyle(\phi \lor \psi)\ to \neg(\n)eg \phi \land \neg \psi )}$

${\$$eg \phi \to \n$$예 \n$$예$를 들어$$\$psi$)}, 교의적 삼단 논법의 약화된 변형

응수.

${\displaystyle(\phi \land \psi)\에서 \n로eg(\n)eg \phi \lor \neg \psi )}$

$→$$eg (\phi \to \n$$예:$ \$psi$)} 및 ${\displaystyle \mathrm{유사}(}$$ϕ$ $→$${\displaystyle \mathrm{}}$$ψ$) $→$ $¬$$($$ϕ ∧ ¬ ψ$) ${\$displaystyle(\phi \to \$psi$)\to \n$eg (\phi \land \n$$)$$eg \psi )}$

실제로$$ψ {\displaystyle \psi$$}이(가)$$¬ ¬ ψ {\displaystyle \n으로${\displaystyle \mathrm{}}$대체된 보다 강력한 변형입니다.$예 \n$$예$를 들어, 왼쪽에 있는$\psi$}은(는) 논의되는 바와 같이 여전히 보류합니다. 그러나 이 5가지 의미 중 어느 것도 즉시 제외된 중간을 의미하지 않고 되돌릴 수 없습니다($$¬ ψ {\$displaystyle$ \n 고려).$예$: ${\displaystyle$\phi} $ϕ$에 대한 \$psi$} 응답. 이중 네거티브 제거(참 $ϕ$$${\displaystyle \phi}$$$consider$). 따라서, 왼쪽 측면은 오른쪽 측면의 가능한 정의를 구성하지 않습니다.

이와 대조적으로 고전 명제 논리에서는 세 가지 연결어와 부정어 중 하나를 원시적인 것으로 받아들이고, 다른 두 가지를 이와 같은 방식으로 정의하는 것이 가능합니다. 예를 들어, 우카시에비치의 명제 논리의 세 가지 공리에서 이러한 작업이 수행됩니다. 피어스 화살표(NOR) 또는 셰퍼 스트로크(NAND)와 같은 단독으로 충분한 연산자의 관점에서 모든 것을 정의할 수도 있습니다. 마찬가지로 고전적인 1차 논리에서는 양자 중 하나를 다른 것과 부정의 관점에서 정의할 수 있습니다. 이것들은 근본적으로 모든 연결들을 부울 함수로만 만드는 쌍대성 법칙의 결과입니다. 이중성의 법칙은 직관주의 논리를 유지할 필요가 없습니다. 따라서 기본적인 연결들 중 어느 것도 분리할 수 없으며 위의 공리들은 모두 필요합니다. 그래서 연결자와 양화자 사이의 고전적 정체성은 대부분 한 방향의 직관주의 논리의 정리에 불과합니다. 일부 정리는 양방향으로 진행됩니다. 즉, 이후에 논의된 바와 같이 동등성입니다.

실존 대 보편적 정량화

먼저 $명제$$$φ $\{\backslash$displaystyle$$\varphi}에서 x ${\displaystyle$ x$}$가 비어 $있지$ 않을 때,

${\displaystyle {\big(})\가 x\,(\phi(x)\to \varphi ){\big()}\,\,{\big(}\forall x\\phi(x){\big)}\to \varphi {\big()}}}\,\,\,{\big(}\to \varphi {\big)}}}$

담론의 영역이 비어 있을 때, 폭발의 원리에 의해 실존적 진술은 무엇이든 의미합니다. 도메인에 적어도 하나의 항이 포함된 경우,${\displaystyle }$∀ x ϕ (x)${\displaystyle \forall$x\,\phi (x)}에 대해 제외된 중간을 가정하면 위 의미의 역도 증명 가능하게 되며, 이는 양변이 동등해지는 것을 의미합니다. 이 역방향은 음주자의 역설(DP)과 같습니다. 게다가, 전제의 독립성 원칙(IP)에 의해 그것의 실존적이고 이중적인 변형이 주어집니다. 고전적으로, 위의 진술은 더욱이 아래에서 더 논의되는 더 모순적인 형태에 해당합니다. 그러나 건설적으로 존재 주장은 일반적으로 더 얻기 어렵습니다.

만약 담론의 영역이 비어 있지 않고$$ϕ {\displaystyle $\$phi}가 x ${\displaystyle$ x$\}$와$더$ 독립적이라면, 그러한 원리는 명제적 미적분학의 공식과 동등합니다. 여기서 공식은 아이덴티티$($ϕ ${\displaystyle }$→$$φ) → (ϕ → φ) ${\displaystyle(\phi$ \$to \$varphi$$)\to(\phi \to \varphi )}를 표현합니다. 이것은 modus ponens${\displaystyle ((}$ϕ → φ${\displaystyle )}$ ∧ ϕ) → φ {\displaystyle((\phi \to \varphi )\land \phi )\to \varphi}의 경화된 형태이며, φ {\displaystyle \varphi}를 잘못된 명제로 하는 특수한 경우에는 contrad 불가 원칙 ¬(ϕ ∧ ¬ ϕ) {\displaystyle \n$eg (\phi \land \n$$)$$eg \phi$ $)\}.$ 원래 의미에$잘못된$ 명제$$φ {\displaystyle \varphi}을(를) 고려하면 중요한 결과를 얻을 수 있습니다.

• ${\displaystyle(\exists x\\n)eg \phi (x))\to \neg (\forall x\ \phi (x))}$

즉, $"{\displaystyle$\phi} $속성$ϕ가 없는 엔티티 $x$ ${\displaystyle$ x$}$가 있으면 다음이 반박됩니다. 각 $엔티티$에는 {\displaystyle \phi$}$ 속성$$ϕ가 있습니다."

부정이 있는 계량기 공식도 위에서 도출된 비 모순 원리를 즉시 따르며, 각 인스턴스 자체는 이미 더 ${\displaystyle \mathrm{특정}}$한${\displaystyle \mathrm{}}$¬${\displaystyle \mathrm{(}}$¬ ¬ ϕ ∧ ¬ ϕ) {\$displaystyle$ \n에서 $따릅니다$.$eg(\n$$)$$예 \n$$eg \phi \land \n$$eg \phi$ $)\}.$ $주어진$$¬ ϕ$ {\$displaystyle$ \n에서 모순을 유도합니다.$eg \phi$ $negative$¬ ¬ ϕ {\$displaystyle$\n을(를) 설정하기에 충분합니다.$예 \n$$예$를 들어, \$phi}($$더$ 강한$$$ϕ$${\$displaystyle \phi$\}$과 반대)이며, 이는 이중 부정을 증명하는 것 또한 가치가 있습니다. 동일한 토큰으로, 원래의 양자 공식은 여전히${\displaystyle }$x$$ϕ(x${\displaystyle )}$ ${\displaystyle \forall$ x\ \phi (x)}를 ∀ x(∀(x))로 약화된 φ x(ϕ(x)) → φ) {\displaystyle \forall x{\big (}(\phi (x))\to \varphi )\to \varphi {\big)}}로 유지됩니다. 따라서, 실제로 더 강력한 정리는 다음과 같습니다.

${\displaystyle(\exists x\\n)eg \phi (x))\to \neg (\forall x\,\n예 \neg \phi (x)}$

즉, $"{\displaystyle$\phi} $속성$ϕ가 없는 엔티티 $x$ ${\displaystyle$ x$}$가 있으면 다음이 반박됩니다. 각 엔티티에 대해 속성$$ϕ {\displaystyle$$\phi}"가 없음을 증명할 수 없습니다.

두 번째로.

${\displaystyle {\big(}\forall x\,(\phi(x))\to \varphi ){\big )}\,\,\,\왼쪽 화살표 \,\,{\big(}(\exists x\\phi(x))\to \varphi {\big)}}}$

유사한 고려 사항이 적용되는 경우. 여기서 실존하는 부분은 항상 가설이고 이것은 동등성입니다. 특수한 경우를 다시 생각해보면,

• ${\displaystyle(모든 x에 대해\n)예를 들어 \phi(x)\왼쪽 화살표\neg (\exists x\ \phi(x))}$

$증명$된 변환$$(χ → ¬ ϕ) ↔ (ϕ → ¬ χ) {\displaystyle (\chi \ to \n)$예를 들어 \phi )\left right 화살표(\phi \to \n$$)$$eg \chi )}$을 사용하여 다음과 같은 두 가지 추가적인 의미를$$ 얻을 수 있습니다.

${\displaystyle(\모든 x에 대해\phi(x))\ to \n예(\exists x\\n)eg \phi (x)}$

${\displaystyle(\exists x\ \phi(x))\ to \neg(\forall x\\n)eg \phi (x)}$

물론, 이러한 공식의 변형은 선행에서 이중 부정을 갖는 것으로도 유도될 수 있습니다. 여기서 첫 번째 공식의 특별한 경우는${\displaystyle (}$∀ x ¬ ϕ (${\displaystyle x}$))${\displaystyle }$→ ¬ (∃ x ¬ ¬ ϕ ($x$)) {\displaystyle (\forall x\,\n)입니다.$eg \phi (x))\to \n$$예(\exists x\,\n)$$예 \n$$예$를 들어, \$phi(x)}$이고 이 값은 실제로 위에 나열된 등가 탄점의 $→$ {\$displaystyle \to }$ - $direction$보다 강합니다. 여기와 아래 논의의 단순화를 위해, 공식은 일반적으로 선행에 가능한 모든 이중 부정의 삽입 없이 약화된 형태로 제시됩니다.

더 일반적인 변종이 있습니다. 술어$$ψ {\displaystyle$$\psi}와 커리를 통합하면 아래에서 논의되는 술어 미적분학에서 함축과 결합 사이의 관계도 다음과 같은 일반화를 수반합니다.

${\displaystyle {\big(}\forall x\\phi(x)\to(\psi(x))\to \varphi ){\big( )}\,\,\,{\big(})\to \varphi(x)\land \psi(x){\big( )}\to \varphi {\big( )}}\,\,\,{\big(})\to \big(x)}}\to \barphi {\big( )}}}:$

술어$$ψ {\displaystyle $\$psi}가$$모든 x${\displaystyle$x}에 대해 확실히 거짓이면 이 동등성은 사소한 것입니다. ψ$${\$displaystyle$ \psi}이(가) 모든 x {\displaystyle x}에 대해 true로 결정되면 스키마는 이전에 언급한 동등성으로 단순 축소됩니다. In the language of classes, ${\displaystyle A=\{x\mid \phi (x)\}}$ and ${\displaystyle B=\{x\mid \psi (x)\}}$, the special case of this equivalence with false ${\displaystyle \varphi }$ equates two characterizations of disjointness ${\displaystyle A\cap B=\emptyset }$:

${\displaystyle \forall(x\in A).x\no tin B\,\,\,\n좌우 화살표\,\,\neg \가 존재합니다 (x\in A).x\in B}$

결합 대 결합

한정된 수식의 변형이 존재하며, 단 두 가지 명제가 있습니다.

• ${\displaystyle(\n)eg \phi \lor \n예를 들어 \psi)\n로eg (\phi \land \psi)}$
• ${\displaystyle(\n)eg \phi \land \n예: \psi)\좌측 화살표\neg (\phi \lor \psi)}$

첫 번째 원칙은 되돌릴 수 없습니다. ¬ ψ$${\$displaystyle$ \n 고려 중$ϕ${\displaystyle \phi}에 대한 $\$$psi$}은(는) 약한 제외된 중간, 즉 ${\displaystyle$ \n 문 $¬ ψ ∨ ¬ ¬ ψ$을 의미합니다.$eg \psi \lor \n$$예 \n$$예$를 들어 $\psi$}. 그러나 직관주의 논리만으로는${\displaystyle \mathrm{}}$¬ ψ ∨ ¬ ¬ ψ ∨을 증명할 수 ${\displaystyle \mathrm{없습니다}}$(¬ ¬ ψ → ψ). ${\displaystyle$ \n$eg \psi \lor \n$$예 \n$$eg \psi \lor (\n)$$예 \n$$예$를 들어 $\psi \to \psi )}$ 특히$,$ 클레임${\displaystyle \mathrm{}}$¬ ϕ ∨ ¬ ψ {\displaystyle $\n$을(를) 도출하는 부정에 대한 분배성 원칙이 없습니다.$eg \phi \lor \n$$¬$$($$ϕ ∧ ψ)$의 $eg$ \$psi$} {\displaystyle \n$eg (\phi \land$ \psi $)\}.$ 건설적인 읽기의 비공식적인 예를 들어, 다음을 생각해보세요. 앨리스와 밥이 둘 다 그들의 데이트에 나타났다는 결정적인 증거로부터, 이 사람이 나타나지 않았다는 결정적인 증거를 도출할 수 없습니다. 부정된 명제는 고전적으로 유효한 De Morgan의 법칙이 하나의 부정적인 가설로부터 분리를 허용한다는 점에서 자동적으로 건설적으로 유지되지 않는다는 점에서 상대적으로 약합니다. 대신 직관주의적 명제 미적분학과 그 확장들 중 일부는 불연속적인 성질을 보여주며, 이는 불연속적인 불연속적인 것들 중 하나가 개별적으로 유도되어야 한다는 것을 의미합니다.

이 두 가지의 역방향 변형은 위에서 이미 언급되었습니다. 그러나 언급된 바와 같이 이러한 공식의 더 강력한 형태는 ${\displaystyle 예}$를 들어${\displaystyle \mathrm{}}$(¬ ¬ ϕ ∧ ¬ ¬ ψ${\displaystyle \mathrm{)}}$ → ¬ (¬ ϕ ∨ ¬ ψ) {\$displaystyle$ (\n)을 유지합니다.$예 \n$$eg \phi \land \n$$예 \n$$예를 들어 \psi)\n로$$eg(\n$$)$$eg \phi \lor \n$$eg$ $psi$ )}. 이것은 모든 공식이 가상으로부터 터무니없는 결과를 도출하는 것에 관한 것이고, 이러한 진술이 특정 순서에 배치될 필요가 없기 때문에 모순되지 않는 원리에서 쉽게 도출될 수 있습니다. 동일한 추론에 의해, 함의와 그 ${\displaystyle \mathrm{반대}}$인 (¬ ϕ ∨ ψ)$$→ ¬ (ϕ ∧ ¬ ψ) {\$displaystyle$ (\n)의 혼합된 형태를 얻을 수 있습니다.$예를 들어 \phi \lor \psi)\n~$$eg (\phi \land \n$$)$${\displaystyle \mathrm{예}}$$:$ \$psi$)} ${\displaystyle 및}$($¬ ϕ ∧ ψ$)${\displaystyle }$$→$ $¬$ ($ϕ ∨ ¬ ψ$) {\displaystyle(\n)$예를 들어 \phi \land \psi)\n~$$eg (\phi \lor \n$$eg$ $psi$ )}.

${\displaystyle 술어}$ 논리에서 ∀ ${\displaystyle x}$ (φ ∨ ψ(x$))$ $displaystyle$ \forall x{\big(})\varphi \lor \psi(x){\big)}} {\displaystyle \varphi \lor \forall x\,\psi(x)}}는 분배 특성이 유한한 수의 명제에 대해 유지되지만 더 강한 ψ x φ ∨ ∀을 의미하지 않습니다. 두 개의 존재적으로 폐쇄적인 결정 가능한 술어에 관한 De Morgan 법의 변형에 대해서는 LLPO를 참조하십시오.

접속사 대 함의

일반적으로 동등성은 가져오기-내보내기를 따르며, 두 개의 서로 다른 연결을 사용하여 두 개의 술어의 비호환성을 표현합니다.

• ${\displaystyle(\phi \to \n)예: \psi)\좌측 화살표\neg (\phi \land \psi)}$

연결 연결의 대칭성으로 인해 이는 이미 설정된 (ϕ $$→ ¬ ψ) ↔ (ψ → ¬ ϕ) {\displaystyle(\phi \ to \n)을 의미합니다.$예를 들어 \psi)\좌측 화살표(\psi \to \n$$eg \phi$ $)\}.$ 음의 접속사에 대한 당량식은 카레링과 언커링의 특수한 경우로 이해될 수 있습니다. 이중 부정에 관한 더 많은 고려 사항이 다시 적용됩니다. 그리고 서론에서 언급한 연결과 함의와 관련된 두 개의 가역적인 정리는 모두 이 동등성에서 비롯됩니다. 하나는 역방향이고$,$ (ϕ ${\displaystyle }$→ ψ) →$$¬ (ϕ ∧ ¬ ψ$)$ {\displaystyle (\phi \to \psi)\to \n$eg (\phi \land \n$$)$$eg$\$psi$ )}은(는) $ϕ →$ $ψ$${\$displaystyle \phi \to \$psi$}가 $ϕ →$ $¬ ¬ ψ$ {\displaystyle \phi \to \n보다 강하기 $때문$에 유지됩니다.$예 \n$$예$를 들어 $\psi$}.

이제 다음 절에서 원리를 사용할 때 왼쪽에 더 많은 부정이 있는 후자의 다음 변형도 적용됩니다.

• ${\displaystyle \neg(\phi \to \psi)\왼쪽 화살표(\n)예 \neg \phi \land \neg \psi )}$

그 결과는

• ${\displaystyle \n예 \neg(\phi \land \psi)\왼쪽 화살표(\n)예 \neg \phi \land \n예 \neg \psi )}$

중간을 제외하면 약한 것으로 판명될 수 있기 때문에, 이 결합에 대한 유사는 정리가 될 수 없습니다.

해체 대 암시

모드 ${\displaystyle 포넨스}$와 유사하게, 이미 최소 논리에서$$명확하게${\displaystyle }$(ϕ ∨ ψ) → ${\displaystyle ((}$ψ → ψ) → psi)${\displaystyle$(\$phi \lor$\psi)\to ((\phi \psi)\to ((\phi \ϕ )\to \ ) )}이며, 이 정리는 부정을 포함하지도 않습니다. 고전적으로, 이것은 동등합니다. 직관주의 논리에서는$다음$과 같이$$⊥ {\$displaystyle$ \bot$}$과 관련된 변형을 얻습니다. ${\displaystyle \mathrm{첫째}}$,${\displaystyle }$¬${\displaystyle (}$ϕ ∧ ψ) ${\displaystyle$ \n에 대한 두 가지 다른 공식에 주목하십시오.위에서 언급한 $eg (\phi \land$\$psi$)}는${\displaystyle }$($¬ ϕ ∨ ¬ ψ$)${\displaystyle }$$→$ ($ϕ$ $→$ $¬ ψ$) {\displaystyle (\n)을${\displaystyle \mathrm{}}$암시하는 데 사용할 수 있습니다.$eg \phi \vee \n$$예를 들어 \psi)\to (\phi \to \n$$eg$ $psi$ )}. 후자는 부정 명제에 대한 쌍방향 삼단 논법의 형태인$$¬ ψ {\$displaystyle$\n$예$를 들어, \$psi$ 강화된 형태는 여전히 직관주의 논리를 유지하고 있습니다.

• ${\displaystyle(\n)예를 들어 \phi \lor \psi)\to (\phi \to \psi )}$

$이전$ 섹션과 마찬가지로$$¬ ϕ의 위치 {\$displaystyle$\n$예$를 들어, \$phi }$ $및$$ϕ$ ${\displaystyle$ \phi$$}을(를) 전환하여 서론에서 언급한 것보다 더 강력한 원리를 제공할 수 있습니다. $또한$ {\displaystyle \phi$}$ϕ이 {\displaystyle \n$$¬ ¬ ϕ으로${\displaystyle \mathrm{}}$약화될 수 있습니다.$예 \n$$예$를 들어 $\phi$ 이 원리들은 모순과 폭발로부터 증명될 수 있습니다. 예를 들어, 직관적으로 "$P{\displaystyle }$ ${\displaystyle P}$ 또는$$ Q ${\displaystyle$ Q$\}"$는 "$P{\displaystyle }$ ${\displaystyle$ P$}$가 아닌 경우$$$Q{\displaystyle }$ ${\displaystyle Q}"$보다 더 강력한 명제 공식이지만, 이들은 고전적으로 교환 가능합니다. 그 의미는 일반적으로 되돌릴 수 없습니다. 그것은 즉시 제외된 중간을 의미하기 때문입니다.

¬ ¬ ψ$${\$displaystyle$ \n 고려 중$예 \n$위의 삼단 논법 형식에서 $ϕ$ {\displaystyle \phi} $대신$에$$\$psi$}는 제외된 중간이 이중 부정 제거를 어떻게 의미하는지 보여줍니다.

물론 여기에 설정된 공식을 결합하여 더 많은 변형을 얻을 수 있습니다. 예를 들어, 제시된 교의적 삼단 논법은 다음과 같이 일반화됩니다.

${\displaystyle {\Big(}) {\big(})\exists x\n예를 들어, \phi(x){\big)}\lor \varphi {\big)}\,\,\,{\big(}\forall x\\\phi(x){\big)}\\barphi {\big)}}}$

만약 어떤 용어가 존재한다면, 여기서 선행은 ∃ ${\displaystyle x}$ (ϕ (${\displaystyle x)}$→ φ$) {\displaystyle \$exists x${\big (}\$phi $($x)\to \varphi {\big )}}를 의미하며, 이는 또한 여기서 결론을 의미합니다(이것은 이 섹션에서 언급된 바로 첫 번째 공식입니다).

이 섹션에서 논의하는 대부분은 최소 논리에도 적용됩니다. 그러나 일반적인$$ψ {\displaystyle \psi$}$과의 교의적 삼단논법에 대해서는, 최소 논리는 ${\displaystyle 기껏해야}$(¬ ϕ ∨ ψ) → (¬ ¬ ϕ → ψ ') {\$displaystyle$ (\n)을 증명할 수 있습니다.$예를 들어 \phi \lor \psi)\to (\n$$예 \n$$예$를 들어 $\phi \to \psi$ ')}${\displaystyle {}^{}}$여기서$$$ψ$' ${\displaystyle \{\backslash }$displaystyle \$psi$ '}는 $¬ ¬ ψ ∧$($ψ ∨ ¬ ψ$) {\displaystyle \n을 나타냅니다.$예 \n$$eg \psi \land (\psi \lor \n)$$eg$ $psi$ )}. 여기서 결론은 폭발을 사용하여$$ψ {\displaystyle \psi$}$로 단순화할 수 있습니다.

등가물

위 목록에는 동등성도 포함되어 있습니다. 결합과 분해를 포함하는 등가성은$$(${\displaystyle P}$ ∨ Q) → R ${\displaystyle$(P\$lor$Q)\to R}이 실제로 P → R {\displaystyle P\to R}보다 더 강하다는 데서 비롯됩니다. 등가성의 양쪽은 독립적인 의미의 결합으로 이해될 수 있습니다. $위$의 부조리 ⊥ {\$displaystyle$\bot}은(는) R ${\displaystyle$R}에$사용$됩니다. 함수 해석에서는 if-clause 작도에 해당합니다. 예를 들어 "Not(${\displaystyle }$ ${\displaystyle P}$ 또는$$ Q ${\displaystyle Q})"$은 "$Not{\displaystyle }$ P$${\$displaystyle P}$및 $Q{\displaystyle }$ ${\displaystyle$ Q$}"$와 동일합니다.$$

동치 자체는 일반적으로 다음과 같은 의미의 결합으로 정의됩니다.

• ${\displaystyle(\phi \left arrow \psi)\left arrow {\big(}(\phi \to \psi)\land(\psi \to \phi ){\big )}}$

이를 통해 이러한 연결은 다음과 같이 정의할 수 있습니다.

• ${\displaystyle(\phi \to \psi)\leftright 화살표((\phi \lor \psi)\leftright 화살표 \psi)}$
• ${\displaystyle(\phi \to \psi)\leftright 화살표((\phi \land \psi)\leftright 화살표 \phi )}$
• ${\displaystyle(\phi \land \psi)\좌측 화살표((\phi \to \psi)\좌측 화살표 \phi )}$
• ${\displaystyle(\phi \land \psi)\leftright 화살표((\phi \lor \psi)\leftright 화살표 \psi)\leftright 화살표 \phi )}$

$차례$로${$∨$,$ ↔, ⊥ } ${\$displaystyle \{\lor,\leftrightarrow,\bot \}} 및 {∧, ↔, ¬ } {\$displaystyle$ \{\land,\leftrightarrow,\n$예$를 들어 $\}}$는 직관적 연결의 완전한 기반입니다$$.

기능적으로 완벽한 연결

Alexander V. Kuznetsov에 의해 보여지듯이, 다음 연결들 중 하나인 첫 번째 삼원형, 두 번째 사원형은 그 자체로 기능적으로 완전합니다: 둘 중 하나는 직관적인 명제 논리를 위한 유일한 충분한 연산자의 역할을 할 수 있고, 따라서 고전 명제 논리로부터 셰퍼 스트로크와 유사한 것을 형성할 수 있습니다.^[7]

• ${\displaystyle {\big(}(P\lor Q)\land\nEG {\big )}\lor {\big(})\neg P\land (Q\왼쪽 화살표 R){\big )}}$
• ${\displaystyle P\to {\big(}Q)\land\nEG\land (S\lor T){\big )}}$

의미론

의미론은 고전적인 경우보다 오히려 복잡합니다. 모델 이론은 Heyting algebra에 의해 또는 이에 상응하게 Kripke 의미론에 의해 주어질 수 있습니다. 최근, 타르스키와 같은 모델 이론이 밥 콘스터블에 의해 완전하지만, 고전적인 것과는 다른 완전성의 개념으로 증명되었습니다.

직관주의 논리에서 증명되지 않은 진술에는 중간 진리값이 주어지지 않습니다(때로는 잘못 주장되기도 합니다). 이러한 진술은 1928년 Glivenko로 거슬러 올라가는 결과인 세 번째 진리값이 없다는 것을 증명할 수 있습니다.^[1] 대신, 그들은 증명되거나 반증될 때까지 진실의 가치를 알 수 없습니다. 진술은 모순을 추론함으로써 반증됩니다.

이러한 관점의 결과는 직관주의 논리가 익숙한 의미에서 2가치 논리로서도, 심지어 유한가치 논리로서도 해석되지 않는다는 것입니다. $직관주의$ 논리는 고전 논리에서 사소한 명제${$⊤$,$⊥ } {\$displaystyle$ \{\top,\bot \}}를 유지하지만, 명제 공식의 각 증명은 유효한 명제 값으로 간주되며, 따라서 헤이팅의 명제 집합 개념에 따르면 명제 공식은 (잠재적으로 무한하지 않은) 증명 집합입니다.

헤이팅 대수학 의미론

고전 논리학에서 우리는 종종 공식이 취할 수 있는 진리값을 논합니다. 값은 일반적으로 부울 대수의 멤버로 선택됩니다. 부울 대수의 meet 및 join 연산은 ∧ 및 ∨ 논리적 연결과 동일하므로 형식 A ∧ B의 공식 값은 부울 대수의 A 값과 B 값의 일치입니다. 그런 다음 공식이 모든 가치 평가에 대해 1인 경우에만, 즉 변수에 대한 값 할당에 대해 공식이 고전 논리의 유효한 명제라는 유용한 정리를 가지고 있습니다.

직관주의 논리에서는 해당 정리가 참이지만, 부울 대수에서 각 공식에 값을 할당하는 대신, 부울 대수는 특별한 경우인 헤이팅 대수의 값을 사용합니다. 공식은 어떤 헤이팅 대수에 대한 평가에서 최상위 요소의 값을 받는 경우에만 직관적 논리에서 유효합니다.

유효한 공식을 인식하기 위해서는 원소가 실수선 R의 열린 부분집합인 단일 헤이팅 대수를 고려하는 것으로 충분하다는 것을 알 수 있습니다.^[8] 이 대수학에서 우리는 다음을 갖습니다.

${\displaystyle {begin{aligned}{\text{Value}}[\bot]&\emptysset \\{\text{Value}[\top]&\mathbf {R}\{\text{Value}[A\land B]&={\text{Value}[A]\cap {\text{Value}[B]\\{\text{Value}}[A\lor B]&={\text{Value}[A]\cup {\text{Value}[B]\\{\text{Value}}[A\to B]&={\text{int}}\left({\text{Value}}[A]^{\complement}\cup {\text{Value}[B]\right]\end{aligned}}$

여기서 int(X)는 X와 그 보형물의^∁ 내부입니다.

A → B에 관한 마지막 항등식을 통해 ¬A의 값을 계산할 수 있습니다.

${\displaystyle {begin{aligned}{\text{Value}}[\negA]&={\text{Value}[A\to \bot]\&={\text{int}\left({\text{Value}}[A]^{\complement}\cup {\text{Value}[\bot]\right)\\&={\text{int}}\left({\text{Value}}[A]^{\complement}\cup \emptyset \right)\\&={\text{int}}\left({\text{Value}}[A]^{\complement}\right)\end{aligned}}$

이러한 할당에서 직관적으로 유효한 공식은 전체 라인의 값이 할당된 공식입니다.^[8] 예를 들어, 공식 ¬(A ∧ ¬A)는 유효합니다. 왜냐하면 어떤 집합 X를 공식 A의 값으로 선택하더라도 ¬(A ∧ ¬A)의 값은 전체 선이 될 수 있기 때문입니다.

${\displaystyle {begin{aligned}{\text{Value}}[\neg (A\land \n)eg A)]&={\text{int}}\left({\text{Value}}[A\land \negA]^{\complement}\right)&{\text{Value}[\neg B]={\text{int}}\left({\text{Value}}[B]^{\complement}\right)\\&={\text{int}}\left(\text{Value}[A]\cap {\text{Value}[\n]egA]\right)^{\comple먼트}\right)\\&={\text{int}}\left(\text{Value}[A]\cap{\text{int}}\left({\text{Value}[A]^{\complement}\right)\right)^{\comple먼트}\right)\\&={\text{int}}\left(X\cap{\text{int}}\left(X^{\complement}\right)\right)^{\comple먼트}\right)\\&={\text{int}}\left(\emptysset ^{\complement}\right)&{\text{int}\left(X^{\complement}\right)\subseteq X^{\complement}\&={\text{int}(\mathbf {R})\&=\mathbf {R}\end{aligned}}$

따라서 이 공식의 가치 평가는 사실이며 실제로 공식은 유효합니다. 그러나 제외된 중간인 A ∨ ¬A의 법칙은 A에 대한 양의 실수 집합의 특정 값을 사용함으로써 무효임을 보여줄 수 있습니다.

${\displaystyle {begin{aligned}{\text{Value}}[A\lor\negA]&={\text{Value}[A]\cup {\text{Value}[\neg A]\\&={\text{Value}[A]\cup {\text{int}\left({\text{Value}[A]^{\complement}\right)&{\text{Value}[\neg B]={\text{int}}\left({\text{Value}}[B]^{\complement}\right)\\&=\{x>0\}\cup {\text{int}}\left(\{x>0\}^{\complement}\right)\\&=\{x>0\}\cup {\text{int}}\left(\{x\leqslant 0\}\right)\\&=\{x>0\}\cup \{x<0\}\\&=\{x\neq 0\}\\&\neq \mathbf {R} \end{aligned}}$

위에서 설명한 무한 하이팅 대수에서 직관적으로 유효한 공식의 해석은 공식의 변수에 할당된 대수의 값에 관계없이 공식의 값으로 참을 나타내는 최상위 요소로 귀결됩니다.^[8] 반대로, 모든 유효하지 않은 공식에 대해 상위 요소와 다른 값을 산출하는 변수에 값이 할당됩니다.^[9][10] 유한 헤팅 대수는 이 두 가지 성질 중 두 번째 성질을 갖지 않습니다.^[8]

크립케 의미론

Saul Kripke는 모달 논리학의 의미론에 대한 그의 연구를 기반으로, Kripke 의미론 또는 관계론적 의미론으로 알려진 직관주의 논리학의 또 다른 의미론을 만들었습니다.^[11][12][5]

타르스키어와 유사한 의미론

직관주의 논리에 대한 타르스키적 의미론은 완전성을 입증할 수 없다는 사실을 발견했습니다. 그러나 로버트 콘스터블은 타르스키와 같은 모델 하에서 완전성에 대한 더 약한 개념이 여전히 직관주의 논리를 유지한다는 것을 보여주었습니다. 이 완전성의 개념에서 우리는 모든 모델에 맞는 문장이 아니라 모든 모델에서 동일한 방식으로 맞는 문장에 관심을 갖습니다. 즉, 모형이 공식을 참이라고 판단한다는 단 하나의 증거가 모든 모형에서 유효해야 합니다. 이 경우에는 완전성의 증명만이 아니라 직관주의 논리에 따라 유효한 증명이 있습니다.^[13]

메탈로직

허용규칙

직관주의 논리나 그 논리를 이용한 고정된 이론에서는 함축성이 항상 메타 이론적으로는 성립하지만 언어에서는 성립하지 않는 상황이 발생할 수 있습니다. 예를 들어, 순수 명제 미적분학에서 ${\displaystyle \mathrm{만약}}{\displaystyle (}$¬ A) →${\displaystyle }$(B ∨ $C$) {\$displaystyle$ (\n)$eg A)\to (B\lor C)}$는 증명 가능하며$,$ ${\displaystyle \mathrm{그러면}\mathrm{}}$($¬$ $A$$→$ B) $∨$ ($¬$ $A$ $→$ C) {\displaystyle (\n)$eg A\to B)\lor (\n$$예 A\to$ C$)\}.$ 또 다른 예는$$(${\displaystyle A}$ → ${\displaystyle B)}$ →${\displaystyle }$($A$∨ C) ${\displaystyle$ ($A\to$B)\to $($A\lor C)}가 항상 증명 가능하다는 것을 의미하기도 합니다. (A → B) → A (A → B) → C) {\displaystyle {\big (}(A\to B)\to A{\big )}\lor {\big (}(A\to B)\to C{\big )}}. 어떤 사람은 시스템이 규칙과 같은 의미로 폐쇄되어 있으며 이를 채택할 수 있다고 말합니다.

다른 로직과의 관계

파라컨스턴스 논리

직관주의 논리는 이중성에 의해 브라질식, 반직관주의 논리 또는 이중직관주의 논리로 알려진 역설적 논리와 관련이 있습니다.^[14]

FALSE(resp. NOT-2) 공리가 제거된 직관주의 논리의 하위 시스템은 최소 논리로 알려져 있으며 몇 가지 차이점은 위에서 자세히 설명되었습니다.

중간논리학

1932년에 쿠르트 괴델은 고전 논리와 직관 논리의 중간 논리 체계를 정의했습니다. 실제로, 부울 대수와 동치가 아닌 유한 헤이팅 대수는 (의미론적으로) 중간 논리를 정의합니다. 반면에, 순수 직관주의 논리에서 공식의 유효성은 어떤 개별적인 헤이팅 대수에 연결되는 것이 아니라 어떤 헤이팅 대수와 모든 헤이팅 대수와 동시에 연관됩니다.

따라서 예를 들어, 부정을 포함하지 않는 스키마의 경우, 고전적으로 유효한 $({\displaystyle A}$ →${\displaystyle B}$)${\displaystyle }$∨ ($B$ → A) ${\displaystyle$ ($A\to$B)\$lor$(B$\backslash$to A)}를 고려합니다. 직관주의 논리보다 이를 채택하면 괴델-두메트 논리라는 중간 논리가 나옵니다.

고전논리와의 관계

고전 논리의 체계는 다음과 같은 공리 중 하나를 더하여 얻어집니다.

• ${\$$eg \phi }$ $$(제외된 중간의 법칙) $($ϕ ${\displaystyle }$→ χ${\displaystyle )}$ → ((¬ ϕ ${\displaystyle }$→ χ) → χ) {\displaystyle (\phi \to \chi )\to ((\n)로 공식화할 수도 있습니다.$예:$ \$phi \to \chi )\to \chi )}.$
• $→$$예 \n$$eg \phi \to \phi }$ $$(이중 부정 제거)
• ${\displaystyle ((\varphi \to }$χ${\displaystyle )}$ →${\displaystyle }$ϕ${\displaystyle )}$ → ϕ {\displaystyle((\phi \to \chi )\to \phi )\to \phi}(피어스의 법칙)
• ${\displaystyle (\neg \mathrm{}\varphi \; \to }$$eg \phi \to \n$$예$를 들어, \$chi$)\$to$(\$chi \to \phi$)}$$ (위치의 법칙)

일반적으로, 2요소 크립케 $프레임$∘ ⟶ ∘ {\$displaystyle$ \longrightarrow}\circ}(즉, 스메타니치 논리에 포함되지 않음)에서 유효하지 않은 고전적 자동론을 추가 공리로 취할 수 있습니다.

다가치 논리

다가치 논리를 포함하는 쿠르트 괴델의 연구는 1932년에 직관주의 논리가 유한 가치 논리가 아니라는 것을 보여주었습니다.^[15] (직관적 논리에 대한 무한한 가치 논리 해석은 위의 헤이팅 대수학 의미론이라는 제목의 섹션을 참조하십시오.)

모달논리

직관주의 명제 논리(IPC)의 공식은 다음과 같이 일반 모달 논리 S4의 언어로 번역될 수 있습니다.

${\displaystyle {\begin{aligned}\bot ^{*}&=\bot \\A^{*}&=\Box A&{\text{if}}}A{\text{ is prime(양의 문자 그대로)}}\\(A\wedge B)^{*}&=A^{*}\(A\vee B)^{*}&=A^{*}\A^{*}\(A\to B)^{*}&=\Box \left(A^{*}\to B^{*}\right)\(\n)eg A)^{*}&=\Box(\n)eg (A^{*})&\n예 A:=A\to \bot \end{aligned}}}$

그리고 원래 공식이 IPC에서 유효한 경우에만 번역된 공식이 명제 모드 논리 S4에서 유효하다는 것이 입증되었습니다.^[16] 위의 공식들의 집합을 괴델-맥킨지-타르스키 번역이라고 합니다. 또한 건설적인 모달 로직 CS4라고 불리는 모달 로직 S4의 직관적인 버전도 있습니다.^[17]

람다 미적분학

IPC와 단순 유형 람다 미적분학 사이에는 확장된 커리-하워드 동형이 있습니다.^[17]

참고 항목

메모들

참고문헌

외부 링크

• Van Atten, Mark (4 May 2022). "The Development of Intuitionistic Logic". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.

• McCarty, David Charles. "Intuitionism in Mathematics". In Shapiro, Stewart (ed.). The Oxford Handbook of Philosophy of Mathematics and Logic. pp. 356–386. doi:10.1093/oxfordhb/9780195325928.003.0010.

• Moschovakis, Joan (16 December 2022). "Intuitionistic Logic". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.

• "Tableaux'method for intuitionistic logic through S4-translation". Laboratoire d'Informatique de Grenoble. tests the intuitionistic validity of propositional formulae