1.1 Introduction to Proofs(What is a Proof 1.1 ~1.6)

1. Propositions

  명제(proposition)란 참 혹은 거짓인 문장을 말한다. 이때, 참과 거짓을 구별할 수 없거나 상황에 따라 참 거짓이 달라진다면 명제가 아니다.

  컴퓨터 과학에서 프로그램과 시스템을 검증하기 위해서 우리는 명제의 참 거짓을 증명하는 법을 알아야 한다.

2. Predicates

  술어(predicate)란 하나 이상의 변수에 대해 참 또는 거짓을 취하는 명제다.

  변수 값이 무엇인가에 따라 참 거짓이 달라지므로 다음과 같은 함수와 비슷한 표기법을 사용한다.

P(n) ::= "n is a perfect square"

우리는 4 is a perfect square is true, 5 is a perfect square is false 대신 P(4) is true, P(5) is false라고 할 수 있다. 이러한 표현을 일반적인 함수 표현과 햇갈리지 말자.

3. The Axiomatic Method

 공리(axiom)란 증명이 필요없이 자명하거나 기본적인 전제로 받어들어지는 명제이다.

 증명(proof)이란 공리와 이전에 증명된 명제들로부터 시작하여 문제 속 명제로 결론지어지는 논리적 추론이다.

이외에 다음과 같은 이미 증명된 명제들에 관한 일반적인 용어가 있다.

 정리(theorem)란 중요한 참인 명제를 말한다.

 보조정리(lemma)란 이후의 증명에 유용할 예비 명제들을 말한다.

 따름정리(corollary)란 기존 정리에서 몇 단계의 논리적 추론으로 증명되는 명제를 말한다.

 이러한 정의들은 정확하지는 않다. 공리를 이용해서 증명하는 방법을 axiomatic method라고 한다. 오늘날에는 Zermelo-Frankel with Choice axioms(ZFC)라는 공리들과  몇 가지 논리적 추론 규칙으로 본질적으로 모든 수학을 유도할 수 있다. 이들은 추후에 7장에서 다시 살펴본다.

 

4. Our Axioms

 ZFC Axioms는 수학의 근간(the foundations of mathematics)를 공부하고 합리화하는 것에 매우 중요하지만 이는 실용적적인 관점에서 너무 기초적이다. 예를 들어 ZFC로 2+2=4를 증명하려면 20,000단계 이상의 과정ㅇ이 필요하다. 그래서 ZFC를 시작하기 전에 우리는 거대한 규모의 공리들을 우리만의 기초(foundation)으로 사용할 것이다. 우리는 고등학교 수학에서 봤던 익숙한 사실들을 받아들일 것이다.

 

 이는 빠른 진행을 도와주지만, 이러한 부정확한 공리의 명시는 때때로 문제를 일으킬 것이다. 예를 들어, 증명 중간에 "공리로 받아들이는 것과 증명하는 것 중 무엇을 선택해야 하지?"라고 생각할 수 있다. 여기에 확실한 담은 없다. 왜냐하면 상황(circumstance)과 청중(audience)에 따라 해당 사실을 가정할지 아니면 증명할지가 달라지기 때문이다. 일반적으로 좋은 가이드라인은 단순히 무엇을 가정했는지 밝히는 것이다.

4.1 Logical Deductions

 Logical Deductions(논리적 추론) 이나 inference rules(추론 규칙)은 새로운 명제를 이전에 증명한 명제로 증명하는데 사용된다.

 기본적인 추론 규칙은 modus pones이다. 이 규칙에 따르면, P의 증명과 P IMPLIES Q(P이면 Q이다.)의 증명이 존재한다면 이는 Q의 증명이다.

  inference rule은 다음과 같은 표현으로 쓰인다. 예를 들어 modus ponens는 이렇게 쓴다.

$\frac{P,  P \ IMPLIES\ Q}{Q}$

  분자에 있는 명제들을 antecedent(전건)라고 하며, 분모에 있는 명제들을 conclusion or consequent(후건)라고 하는데 modus ponens에서는 전건들이 증명되었다면 후건도 증명된다.

 

inference rule의 중요한 필요요소는 반드시 sound(건전,타당)해야한다는 것이다. 여기서 sound(건전, 타당)는

 

이외에도 여러 자연적(natural)이고 타당한(sound) inference rule들이 있다. 예를 들어,

$\frac{ P \ IMPLIES\ Q, q \ IMPLIES\ R }{ P \ IMPLIES\ R}$

$\frac{NOT(P)\ IMPLIES \ NOT(Q)}{ Q \ IMPLIES\ P }$

가 있다.

 반면에,

$\frac{NOT(P)\ IMPLIES \ NOT(Q)}{ P \ IMPLIES\ Q }$

는 타당(sound)하지 않아서 규칙이 아니다. 만약 P가 참이고 Q가 거짓이면 전건은 참이지만 거짓이다.

  앞에서 공리에 대해 말했듯이, 형식적으로 합당한 추론 규칙을 형식적으로 다루지는 않을 것이다. 다만, 증명의 각 단계는 명확하고 논리적이어야 하며 결로 도출에 사용된 이전에 증명된 사실을 명시해야 한다.

4.2 Patterns of Proof

 원칙적으로, 증명은 공리와 이전에 증명된 명제들로부터 논리적 추론을 거쳐 주어진 명제에 도달하는 어떤 논리적인 연속 과정이기만 하면 된다. 이러한 자유에 압도될 수도 있지만 여러 표준 템플릿들 존재한다. 앞으로 우리는 여러 증명 패턴들을 보며 각 패턴의 기본 아이디어, 일반적인 문제점 그리고 그 예시를 볼 것이다. 그리고 더 정교한 증명 기술도 볼 것이다.

 

 아래의 템플릿들은 때때로 매우 구체적이어서 종이에 무엇을 적을지 알려줄 것이다. 물론 자신만의 방법으로 표현해도 되지만 어느정도 알려줌으로서 아예 감도 못 잡는 것을 것을 방지하는 용도로 사용하면 된다.

5. Proving an Implication

 함의(implication)란, "If P, then Q" 형식의 명제를 말한다. 이는 "P IMPLIES Q"로 다시 표현되기도 하는데 둘은 같은 의미이다. Implication의 표준 증명법은 두 가지가 있다.

5.1 Method #1

P IMPLIES Q를 증명하기 위해서는

1. Write "Assume P" / 1. P를 가정한다라고 적는다.
2. Show that Q logically follows. / 2. 논리적으로 Q가 뒤따로 온다는 것을 보인다.

5.2 Method #2 - Prove the Contrapositive

 함의(implication) "P IMPLIES Q"는 논리적으로 대우(contropositive) NOT (Q) IMPLIES NOT(P)와 같다.

 하나를 증명하는 것은 다른 하나를 증명하는 것과 같다. 그리고 가끔 대우를 증명하는 것이 원래 명제를 증명하는 것보다 쉽다. 만일 대우 증명이 더 쉽다면 다음과 같이 진행한다.

1. Write, "We prove the contrapositive: " and then state the contrapositive.
/ 1. 우리는 대우를 증명한다 : 라고 적고 대우를 서술한다.
2. Proceed as in Method #1 / Method #1에 나온대로 진행한다.

6. Proving an "If and Only If"

 많은 수학 정리들은 다음과 같은 관계에 있을 때 두 명제가 논리적으로 동일하다고 주장한다.

one holds if and only if the other does. 하나가 성립하면 반드시 다른 것도 성립하며, 그 반대도 마찬가지이다.

 오래된 예시로는 Two triangles have the same side length if and only if two side lengths and the angle between those sides are the same. (SAS합동)가 있다.

 if and only if(필요충분조건) 구절은 "iff"로 자주 축약된다.

6.1 Method #1: Prove Each Statement Implies the Other

 "P IFF Q"는 "P IMLIES Q", "Q IMPLIES P"와 동일하다.

 따라서, 이 두 가지 implication을 증명하는 것으로 증명할 수 있다.

1. Write, "We prove P implies Q and vice-versa" / 1. 우리는 P 이면 Q이다.와 그 반대를 증명한다라고 적는다.
2. Write, "First, we show P implies Q" Do this by one of the methods in Section 5
/ 2. 먼저 우리는 P 이면 Q이다를 보인다라고 적고, Section 5의 방법들로 이를 보인다.
3. Write "Now, we show Q implies P". Again, do this by one of the methods in Section 5
/ 3. 이제 우리는 Q이면 P이다를 보인다라고 적고 다시 Section 5의 방법들로 이를 보인다.

6.2 Method #2: Construct a Chain of Iffs

1. Write "We construct a chain of if-and -only-if implications"
/ 1. "우리는 if-and-only-if 관계의 연쇄를 구성한다."라고 적는다.
2. Prove P is equivalent to a second statement which is equivalent to at third statement and so forth until you reach Q. / 2. P가 두번째 명제와 같은 것을 증명하고 이것이 또 세번째와 같다는 것을 증명한다. 그리고 최종적으로 결론이 Q와 같다에 도달할 때까지 반복한다.

 이 방법은 처음 방법보다 많은 독창성과 창의력을 요구하지만, 그 결과는 간결하고 우아하다.

---

각 method들의 예시는 교재 본문에서 보자.