Logic and Proofs 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[계산 이론 개론#Logic and Proofs|계산 이론 개론]]

==개요==
수학적 활동은 결국 수학적 객체(objects)에 대한 명제(assertions)를 세우고 이를 증명(proof)하는 과정이다. 해당 문서에서는 이를 위해 필요한 개념들과, 증명에 필요한 구조에 대해서 다룬다.

==Classification of Theorems==
수학자들은 다양한 종류의 명제를 구분하기 위해서 다양하게 명명했다. 아래는 그 종류에 대한 표이다:
{| class="wikitable"
|+
!개념
!의미
!예시
|-
|Theorem (정리)
|중요하고 의미 있는 결과
|피타고라스 정리
|-
|Proposition (명제)
|작은 정리, 덜 중요한 결과, 또는 증명 없이 인용되는 결과
|.
|-
|Lemma (보조정리)
|더 큰 정리를 증명하기 위해 필요한 중간 결과
|조르당 보조정리
|-
|Conjecture (추측)
|아직 증명되지 않았지만, 많은 증거와 직관으로 참일 것 같다고 믿는 주장
|리만 가설
|}
이외에도 중요도가 낮은 정리를 일컫는 말로 Scholium과 같은 용어가 사용되기도 한다.

==Expressing Mathematical Assertions==
명제를 구성하기 위해서는 여러 개념들이 필요하다. 아래는 그러한 개념들을 정리한 것이다:
{| class="wikitable"
|+
!개념
!의미
!예시
|-
|Predicates(술어/조건식)
|변수에 값을 대입하면 비로소 참/거짓이 결정되는 문장의 틀
|isEven(x) 
|-
|Propositional connectives(명제 연결자)
|참/거짓이 정해진 명제들을 논리적으로 합성해 새로운 명제를 만드는 데 사용
|<math>\neg, \lor, \land, \rightarrow, \leftrightarrow</math>
|-
|Quantifiers(수량자)
|<math>\forall x P(x)</math> = “모든 x에 대해 P(x)”, <math>\exists x P(x)</math> = “어떤 x가 있어서 P(x)”.
|<math>\forall, \exists</math>
|-
|Constants(상수)
|값이 이미 정해져 있는 고정된 기호
|0, 1, 3, π, e
|-
|Variables(변수)
|맥락에 따라 값이 달라지는 기호들
|<math>x, y</math>
|}
ㅁㅇㄴㄹ

==각주==