Methods of Proof증명방법: Discrete Mathematics이산수학 뿐만 아니라 모든 수학에 적용 가능

   

   

   

이산수학(Discrete Mathematics) .증명방법(Methods of Proof) 이산수학(Discrete Mathematics) .증명방법(Methods of Proof) 증명의중요성증명의중요성 1.5 Methods of Proof 수학에서 증명이란 . 수학적 문장의 진실성을 정밀하고 부정할 수 없도록 설명하는 정확(correct) 하고 완전 (complete) 한 기술이다 . . A correct (well-reasoned, logically valid) and complete (clear, detailed) argument that rigorously and undeniably establishes the truth of a mathematical statement 증명에서의 기본적 사항 . 정확성: Correctness prevents us from fooling ourselves. . 완전성: Completeness allows anyone to verify the result. Page 2 증명의응용분야증명의응용분야 1.5 Methods of Proof 학문의 많은 분야에서 , 논리적이고 정확한 의사 교환 (clear communication) 을위 해 사용한다 . 수학 분야의 기본적인 행동 (연구)은 흥미롭고 밝혀지지 않은 많은 정리 (theorem) 를 증명을 통해 발견하는 것이다 . 정리의 증명은 프로그램 검증 (program verification), 컴퓨터 보안 , 자동화된 추론 시스템(automated reasoning system) 등에서 사용된다 . . . . Page 3 용어(Terminology) (1/3) 용어(Terminology) (1/3) 1.5 Methods of Proof 정리(theorem) . 정리란 참 (true) 으로 밝혀진 명제이다 . . A statement that has been proven to be true. 공리(axiom, postulates) . 증명된 정리 혹은 증명하고자 하는 정리의 가정 /명제이다. (증명이 불필요한 ) . Assumptions (often unproven) defining the structures about which we are reasoning. (예: n이 짝수라면 n = 2k라 나타낼 수 있다 .) 추론 규칙 (rules of inference) . 논리적으로 유효한 주장 (logically valid deductions) 을 사용하여 , 가정을 결론 으로 이끌어가는 증명의 과정이다 . . Patterns of logically valid deductions from hypotheses to conclusions. Page 4 용어(Terminology) (2/3) 용어(Terminology) (2/3) 1.5 Methods of Proof 보조정리(lemma) . 다른 정리를 증명하는데 사용하는 간단한 정리이다 . . A minor theorem used as a stepping-stone to proving a major theorem. .“복잡한 내용이 정리이고 , 간단한 내용이 보조정리”를 의미하는 것은 아님에 유의! 따름정리(corollary) . 어떤 정리가 증명되면 , 이에 의하여 자연스럽게 증명되는 정리이다 . . A minor theorem proved as an easy consequence of a major theorem. Page 5 용어(Terminology) (3/3) 용어(Terminology) (3/3) 1.5 Methods of Proof 가설(conjecture) . 증명되지는 않았지만 참으로 믿어지는 명제이다 . . A statement whose truth values has not been proven. (A conjecture may be widely believed to be true, regardless.) 이론(theory) . 주어진 공리 (axiom) 로부터 증명이 가능한 모든 정리 (theorem) 의 집합이다 . . The set of all theorems that can be proven from a given set of axioms. Page 6 추론규칙(Inference Rules) (1/2) 추론규칙(Inference Rules) (1/2) 1.5 Methods of Proof 추론 규칙의 의미 . 주어진 가정 (antecedent) 이참 (true) 일때 , 결론(consequent) 이 참이라는 패턴 . “x = 3”(= p)이면, “x + 1 = 4”(= q)이다. -상기 예에서 p(가정)가 참이면 , q(결론)은 참이 된다 . 추론 규칙의 표기 antecedent 1 antecedent 2 … .consequent 가정 결론 “.”은“ therefore” 를 의미한다 . Page 7 추론규칙(Inference Rules) (2/2) 추론규칙(Inference Rules) (2/2) 1.5 Methods of Proof 각 추론 규칙은 “항진 명제인 함축 (implication)” 에 해당한다 . ant.1 ant.2 … .con. 에 해당하는 tautology 는“ ((ant.1 . ant.2 . … ) . con.”이다. Page 8 추론규칙예제(1/2) 추론규칙예제(1/2) 1.5 Methods of Proof 예제 . “It is below freezing now. Therefore, it is either below freezing or raining now.” 가 참인 것은 어떤 추론 규칙에 근거하는가 ? . 풀이 . p = “It is below freezing now.”, q = “It is raining now.” . 주어진 문장은 다음과 같은 추론 규칙에 근거하며 , 이를 addition rule 이라 한다 . p .p .q Page 9 추론규칙예제(2/2) 추론규칙예제(2/2) 1.5 Methods of Proof 예제 . “If it rains today, then we will not have a barbecue today. If we do not have a barbecue today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a barbecue tomorrow.” 의 추론 근거는 ? . 풀이 . p = “It is raining today.” . q = “We will not have a barbecue today” . r = “We will have a barbecue tomorrow.” p .q q .r .p .r Hypothetical syllogism (삼단논법) Page 10 추론규칙종류(1/2) 추론규칙종류(1/2) 1.5 Methods of Proof Rule of inference Tautology Name p . p . q p . (p . q) Addition p . q . p (p . q) . p Simplification p q . p . q ((p) . (q)) . (p . q) Conjunction p p . q . q (p . (p . q)) . q Modus ponens ( 긍정 논법 ) (the mode of affirming) ￢q p . q . ￢p (￢q . (p . q)) . ￢p Modus tollens ( 부정 논법 ) (the mode of denying) p . q가 true 이면, 당연히 p와 q 모두 true 이다. p가 true 인 상태에서 p . q가 true 이면, 당연히 q는 true 이다. Page 11 추론규칙종류(2/2) 추론규칙종류(2/2) 1.5 Methods of Proof Rule of inference Tautology Name p . q q . r . p . r ((p . q) . (q . r)) . (p . r) Hypothetical syllogism (삼단 논법 ) p . q ￢p . q ((p . q) . ￢p) . q Disjunctive syllogism p . q ￢p . r . q . r ((p . q) . (￢p . r)) . (q . r) Resolution ( 분해) p가 false 이고 p . q이 true 이면, 당연히 q는 true 이다. Page 12 Formal Proofs (1/2) Formal Proofs (1/2) 1.5 Methods of Proof Formal Proof 의 정의 . Formal proof 란 주어진 가정 (antecedent) 에 기반하여 추론 규칙을 적용한 일 련의 단계 (step) 를 거쳐서 결론 (consequent) 을 도출하는 과정이다 . . A formal proof of a conclusion C, given antecedents p1, p2, …, pn consists of a sequence of steps, each of which applies some inference rule to antecedents or to previously proven statements to yield a new true statement (the consequent). . 증명(proof) 은 주어진 모든 가정이 true 일 때 결론이 true 임을 보이는 과정이다 . . A proof demonstrates that if the antecedents are true, then the conclusion is true. Page 13 Formal Proofs (2/2) Formal Proofs (2/2) 1.5 Methods of Proof 예제 . 다음가정이 “ We will be home by sunset.” 이라는 결론을 도출함을 보여라 . . “It is not sunny this afternoon and it is colder than yesterday.” . “We will go swimming only if it is sunny.” (. If we will go swimming, then it is sunny this …) . “If we do not go swimming, then we will take a canoe trip.” . “If we take a canoe trip, then we will be home by sunset.” . 풀이 . p = “It is sunny this afternoon.” . q = “It is colder than yesterday.” . r = “We will go swimming.” . s = “We will take a canoe trip.” . t = “We will be home by sunset.” p p . q Modus ponens . q ￢q p . q Modus tollens . ￢p 단계 과정 이유 1 2 3 4 5 6 7 8 ￢p . q ￢p r . p ￢r ￢r . s s s . t t 가정 단계 1의 simplification 가정 단계 2, 3 기반의 Modus tollens 가정 단계 4, 5 기반의 Modus ponens 가정 단계 6, 7 기반의 Modus ponens Page 14 Inference Rules for Quantifiers (1/3) Inference Rules for Quantifiers (1/3) 1.5 Methods of Proof Quantifier 를 포함하는 추론 규칙 . Universal instantiation . .xP(x)가 주어졌을 때 , .xP(x)이 true라면, domain 에 속하는 임의의 값 (요소) c에대 해서 P(c)가 true임을 보이는데 사용되는 추론 규칙이다 . . Universal generalization . .xP(x)가 주어졌을 때 , domain 에 속하는 모든 값 (요소) c에 대해서 P(c)가 true이면, .xP(x)가 true임을 보일 때 사용되는 추론 규칙이다 . . Existential instantiation . .xP(x)가 주어졌을 때 , .xP(x)가 true라면, domain 안에 P(c)를 true로하는 값 (요소) c가 적어도 하나 이상 있다는 것을 나타내는 추론 규칙이다 . . Existential generalization . .xP(x)가 주어졌을 때 , 특정 값 (요소) c에 대해서 P(c)가 true이면, .xP(x)이 true라는 추론 규칙이다 . Page 15 Inference Rules for Quantifiers (2/3) Inference Rules for Quantifiers (2/3) 1.5 Methods of Proof Quantifier 사용 명제의 추론 규칙 정리 Rule of inference Tautology Name .xP(x) . P(c) .xP(x) . P(c) Universal instantiation P(c) for an arbitrary c . .xP(x) P(c) for an arbitrary c . .xP(x) Universal generalization .xP(x) . P(c) for some c .xP(x) . P(c) for some c Existential instantiation P(c) for some c . .xP(x) P(c) for an some c . .xP(x) Existential generalization Page 16 Inference Rules for Quantifiers (3/3) Inference Rules for Quantifiers (3/3) 1.5 Methods of Proof 예제 . 다음가정이 “ Maria has taken a course in computer science.” 이라는 결론을 도출함을 보여라. . “Everyone in this discrete mathematics class has taken a course in computer science.” . “Maria is a student in this class.” . 풀이 . D(x) = “x is in this discrete mathematics class.” . C(x) = “x has taken a course in computer science.” . 가정: .x(D(x) . C(x)), D(Maria) . 결론: C(Maria) . 추론 과정 단계 과정 이유 1 2 3 4 .x(D(x) . C(x)) D(Maria) . C(Maria) D(Maria) C(Maria) 가정 단계 1의 universal instantiation 가정 단계 2, 3 기반의 Modus ponens Page 17 Summary of Proof Methods Summary of Proof Methods 1.5 Methods of Proof 함축(implication) p . q의 증명을 위하여 , 다음 방법들을 사용한다 . . Direct proof: Assume p is true, and prove q. . Indirect proof: Assume ￢q, and prove ￢p.(대우의 증명에 해당 ) . Vacuous proof: Prove ￢p by itself. (가정이 false임을 증명 ) . Trivial proof: Prove q by itself. (결론이 항시 true임을 증명 ) . Proof by cases: To prove (p1 . p2 . .... . pn) . q, prove ((p1 . q) . (p2 . q) . .... . (pn . q)) Page 18 Direct Proof ( 직접증명) Direct Proof ( 직접증명) 1.5 Methods of Proof Implication p . q의 증명을 위하여 , p가 true라 가정하고 여러 규칙과 기 존에 true로 증명된 정리를 사용하여 q가 true임을 증명한다 . 예제 . Definition: An integer n is called odd iff n=2k+1 for some integer k; n is even iff n=2k for some k. . Axiom: Every integer is either odd or even. . Theorem: (For all numbers n) If n is an odd integer, then n 2 is an odd integer. . Proof: . If n is odd, then n = 2k+1 for some integer k. . Thus, n 2 = (2k+1)2 = 4k2+ 4k + 1 = 2(2k2+ 2k) + 1. . Therefore, n 2 is of the form 2j + 1 (with j the integer 2k2+ 2k), thus n 2 is odd. □ Page 19 Indirect Proof ( 간접증명) Indirect Proof ( 간접증명) 1.5 Methods of Proof Implication p . q 대신 이의 대우인 ￢q . ￢p를 증명한다 . 예제 . Theorem: (For all integers n) If 3n+2 is odd, then n is odd. . Proof: . Suppose that the conclusion is false, i.e., n is even. . Then n=2k for some integer k. . Then 3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1). . Thus 3n+2 is even, because it equals 2j for integer j = 3k+1. . So 3n+2 is not odd. . We have shown that ￢(n is odd)→￢(3n+2 is odd), thus its contra-positive (3n+2 is odd) → (n is odd) is also true. □ Page 20 Vacuous Proof ( 무의미한증명) Vacuous Proof ( 무의미한증명) 1.5 Methods of Proof 가정(p)이 false 임을 보임으로서 , 결론(q)이 true임을 증명한다 . 예제 . Theorem: (For all n) If n is both odd and even, then n 2= n + n. . Proof: . The statement “n is both odd and even” is obviously false since no number can be both odd and even. . So, the theorem is vacuously true. □ Page 21 Trivial Proof ( 자명한증명) Trivial Proof ( 자명한증명) 1.5 Methods of Proof Implication p . q에서, 결론(q)이 trivial 하게 true임을 증명한다 . 예제 . Theorem: (For integers n) If n is the sum of two prime numbers, then either n is odd or n is even. . Proof: . Any integer n is either odd or even. . So the conclusion of the implication is true regardless of the truth of the antecedent. . Thus the implication is true trivially. □ Page 22 Proof by Contradiction ( 모순에의한증명) (1/2) Proof by Contradiction ( 모순에의한증명) (1/2) 1.5 Methods of Proof 증명 방법 . A method for proving p. (p를 증명하고자 하는 방법이다 .) . Assume ￢p, and prove some proposition q is contradiction (i.e., q is always false.) (p를 부정하면 항시 거짓이 되는 명제가 있음을 보인다 . 즉, ￢p.F을 보인다 .) . Then, ￢p.F, which is only true if ￢p=F (￢p.F이 참이 되기 위해서는 ￢p가 거짓이어야 한다 .) . Thus, p is true. (따라서, p는 참이 된다 .) .주어진 가정 (p)을 부정 (false)했을 때항상 false 가 되는 명제 q가 있음을 보이면 , p의 가정이 잘못되었으므로 p는 true가 된다 . (가정을 부정했을 때 , 결론이 항시 거짓이 되면 , “ 가정을 부정”한 것이 잘못된 것이다 . 따라서, 가정은 참이다 .) * 타임머신의 예 : “ 우리는 과거로 돌아갈 수 없다 .” 왜? 내가 과거로돌아갈 수있다하자 . 만일 과거로 돌아가서 , 내 부모님이 만나지 못하게 한다면 … 지금의 나는 ? Page 23 Proof by Contradiction ( 모순에의한증명) (2/2) Proof by Contradiction ( 모순에의한증명) (2/2) 1.5 Methods of Proof 예제 (. skip) . Theorem: (For all integers n) If 3n+2 is odd, then n is odd. (indirect proof 의 예제 ) . Proof: . Suppose 3n+2 is odd and n is even. [￢(p . q) . ￢(￢p . q) . p . ￢q ] . And, we can prove that “If n is even, then 3n+2 is odd.”. (by the same proof steps showed in the example of indirect proof.) . Then, this conclusion is contradiction of assumption (i.e., 3n+2 is odd.) . Therefore, the given implication is true. □ 개념적인 다른 예제 : n이 정수라 할 때 , 2n은 짝수이다 . . 만일, 2n이 홀수라 하자 . 그러면, 2n = 2k+1인 정수 k가 존재한다 . . 그러면, k = (2n . 1)/2 가 되는데 , 이는 정수가 아니다 . . 따라서, 2n은 홀수가 아니고 , 이는 가정 (2n이 홀수 )이 잘못되었음을 의미한다 . . 따라서, 2n은 짝수이다 . Page 24 Proof by Cases ( 사례에의한증명) (1/2) Proof by Cases ( 사례에의한증명) (1/2) 1.5 Methods of Proof 가정이 논리합으로 구성된 (p1 . p2 . .... . pn) . q 형태를 증명하기 위 하여, 다음과 같은 tautology를 사용한다 (p1 . p2 . .... . pn) . q . ((p1 . q) . (p2 . q) . .... . (pn . q)) 즉, 각각의 (pi . q)를 증명함으로써 전체를 증명하는 방법이다 . Page 25 Proof by Cases ( 사례에의한증명) (2/2) Proof by Cases ( 사례에의한증명) (2/2) 1.5 Methods of Proof 예제 . Theorem: |xy| = |x||y|, where x and y are real numbers. (|x| = x if x . 0, |x| = -x if x < 0) . Proof: . p = x and y are real numbers, q = |xy| = |x||y| . p = {x . 0, y . 0} . {x . 0, y < 0} . {x < 0, y . 0} . {x < 0, y < 0} . {x . 0, y . 0} . q: |xy| = xy = |x||y| . {x . 0, y < 0} . q: |xy| = -xy = x(-y) = |x||y| .… . All the possible cases are proven to true, and thus, the theorem is proven.□ Page 26 Proof of Equivalence ( 동치증명) Proof of Equivalence ( 동치증명) 1.5 Methods of Proof 상호조건 p ↔ q(“p if and only if q”)을 증명하기 위해서는 다음과 같은 tautology를 사용한다 . (p ↔ q) . ((p . q) . (q . p)) . 즉, (p . q)를 증명하고 (q . p)를 증명함으로써 , (p ↔ q)를 증명한다 . Page 27 Existence Proof (존재증명) (1/2) Existence Proof (존재증명) (1/2) 1.5 Methods of Proof 증명하고자 하는 문장에 .xP(x) 형태의 quantifier/predicate 가 포함된 경 우를 존재 증명 (existence proof)이라 한다 . If the proof of a statement of the form .xP(x) is called an existence proof. Page 28 Existence Proof (존재증명) (2/2) Existence Proof (존재증명) (2/2) 1.5 Methods of Proof 예제 . Theorem: There exists a positive integer n that is the sum of two perfect cubes in two different ways. (두 수의 세제곱의 합을 두 가지 방법으로 나타낼 수 있는 정수가 존재한다 .) (In other words, there exists a positive integer n such that n = j3+ k3= l3+ m 3, where j, k, l, and m are positive integers, and {j, k} . {l, m}.) . Proof: Consider n = 1729, j = 9, k = 10, l = 1, m = 12. Now just check that the equalities hold. □ Page 29 Uniqueness Proof ( 유일성증명) Uniqueness Proof ( 유일성증명) 1.5 Methods of Proof 유일하게 하나의 값 (요소)만이 주어진 특성을 만족하는 경우를 유일성이 라 하고 , 이의 증명을 유일성 증명 (uniqueness proof)이라 한다 . 유일성의 증명 과정 . 존재 : x가 주어진 특성을 가짐을 보인다 . . 유일성 : 만일 y . x이면, y는 주어진 특성을 갖지 않음을 보인다 . “P(x)를 만족하는 x가 유일하게 하나 존재함을 증명하는 과정은 다음 표 현을 증명하는 것과 동일하다 . (. 가장 절친한 친구는 오직 한 명이다 .) .x(P(x) ..y(y . x . ￢P(y))) Page 30 Mistakes in Proofs Mistakes in Proofs 1.5 Methods of Proof 예제 (mistakes in proof) . Theorem: Prove 1 = 2. . Proof: . Let a and b be the same positive integers. . a = b [주어진 정의 ] . a2= ab [양변에 a를 곱함 ] . a2-b2= ab-b2 [양변에서 b2를뺌] . (a . b)(a + b) = b(a . b) [인수분해] . a + b = b [양변을 (a-b) 로 나눔 ] . 2b = b [since a = b] . 2 = 1. [양변을 b로 나눔 ] What is wrong? . (a . b) is zero since a = b, and thus, we cannot use (a . b) as a divisor. Page 31