<aside>

요약

• Provable이란 주어진 논리 체계와 추론 규칙에서 명제가 증명될 수 있는 상태를 의미합니다.
• 이는 구문적 추론(Syntactic Deduction)에 의존하며, $\Gamma \vdash \phi$로 표현됩니다.
• Provable은 의미론적 참(Semantic Truth)과 연관되며, 정합성과 완전성을 통해 두 개념이 논리적으로 연결됩니다. </aside>

Provable은 논리학에서 어떤 명제(statement)가 주어진 논리 체계와 추론 규칙에 따라 증명될 수 있음을 의미합니다. 이를 구체적으로 살펴보면 다음과 같습니다.

1. 정의

• Provable: 한 명제가 논리 체계에서 제공하는 **형식적 증명(formal proof)**에 의해 참임을 보일 수 있는 상태를 말합니다.
• 기호로는 보통 ⊢를 사용하여 표현됩니다.
  • $\Gamma \vdash \phi$: "전제 $\Gamma$로부터 명제 $\phi$를 증명할 수 있다."

2. 특징

1. 형식적 증명에 의존:
   • Provable은 **구문적 추론(Syntactic Derivation)**에 기반합니다. 이는 의미론적 참/거짓 여부와는 별개의 개념입니다.
   • 논리 체계 내의 추론 규칙과 공리(axioms)를 사용하여 명제를 도출할 수 있으면 Provable이라고 합니다.
2. 전제 조건:
   • Provable은 전제(assumptions, $\Gamma$)의 집합을 필요로 합니다. 전제가 주어지지 않을 경우, **공리적 체계(axiomatic system)**에서 명제를 증명할 수 있는지 평가합니다.
3. 의미론적 참과의 관계:
   • Provable과 의미론적 참은 완전성(Completeness)과 정합성(Soundness)에 의해 연관됩니다:
     • 정합성(Soundness): $\Gamma \vdash \phi$이면, $\Gamma \models \phi$ (증명 가능한 것은 의미론적으로 참이다)
     • 완전성(Completeness): $\Gamma \models \phi$이면, $\Gamma \vdash \phi$ (의미론적으로 참인 것은 증명 가능하다)

3. 기호적 표현

1. Provable: $\Gamma \vdash \phi$
   • $\Gamma$: 전제들의 집합.
   • $\phi$: 증명해야 할 명제.
   • 의미: "전제 $\Gamma$로부터 $\phi$를 증명할 수 있다."
2. Semantic Truth (의미론적 참): $\Gamma \models \phi$
   • $\Gamma$: 전제들의 집합.
   • $\phi$: 참 여부를 평가할 명제.
   • 의미: "모든 모델에서 $\Gamma$가 참이라면 $\phi$도 참이다."

4. 예시

(1) 기본 논리 증명

• 전제: $P \rightarrow Q$, $P$
• 결론: $Q$