이 문제집은 21강부터 25강까지의 도구를 섞어 다시 묻습니다. 강의 안의 문제는 그 강의의 도구가 무엇인지 알려 준 상태에서 풀지만, 여기서는 어느 도구를 써야 하는지부터 스스로 정해야 합니다.
푸는 방법을 정해 둡니다. 문제를 읽고 먼저 무엇을 증명하는 문제인지 판단합니다. 전칭입니까 존재입니까. 참을 보이는 것입니까 거짓을 보이는 것입니까. 그 판단이 끝나면 쓸 방법이 거의 정해집니다. 22강의 표를 다시 봅니다.
명제
참임을 보이려면
거짓임을 보이려면
∀ x ∈ A , P ( x ) ∀ x ∈ A , P ( x ) 임의의 x x
반례 하나를 듭니다
∃ x ∈ A , P ( x ) ∃ x ∈ A , P ( x ) 예 하나를 듭니다
모든 x x
답을 보기 전에 반드시 손으로 먼저 씁니다. 증명 문제에서 "알겠다"는 느낌과 "쓸 수 있다"는 사실은 다릅니다.
문제 1. 다음 중 명제인 것을 모두 고르세요. (가) 16 = 4 1 6 = 4 x 2 > 0 x 2 > 0
답. (가)와 (다)입니다. (가)는 참이고 (다)도 참입니다. (나)는 변수가 있어 조건이고, (라)는 판단 기준이 없습니다.
문제 2. p p q q ( ¬ p ∨ q ) → ( p ∧ ¬ q ) ( ¬ p ∨ q ) → ( p ∧ ¬ q )
답. 참입니다. ¬ p ¬ p q q ¬ p ∨ q ¬ p ∨ q
문제 3. ¬ ( p → q ) ¬ ( p → q ) ∧ ∧
답. p ∧ ¬ q p ∧ ¬ q
문제 4. "x ≥ 0 x ≥ 0 y ≤ 5 y ≤ 5
답. "x < 0 x < 0 y > 5 y > 5
문제 5. p → q p → q
답. 역은 q → p q → p ¬ p → ¬ q ¬ p → ¬ q ¬ q → ¬ p ¬ q → ¬ p
문제 6. "n n 9 9 n n 3 3
답. 역은 "n n 3 3 n n 9 9 n = 6 n = 6
문제 7. ( p ∨ q ) ∧ ¬ p ( p ∨ q ) ∧ ¬ p q q
답. 참입니다. ¬ p ¬ p p p p ∨ q p ∨ q q q
문제 8. p → q p → q ¬ q → ¬ p ¬ q → ¬ p
답. ( T , T ) ( T , T ) ( T , F ) ( T , F ) ( F , T ) ( F , T ) ( F , F ) ( F , F )
문제 9. "x x x x 4 4
답. 필요조건이지만 충분조건은 아닙니다. 4 4 6 6 4 4
문제 10. ( p → q ) ∧ ( q → r ) → ( p → r ) ( p → q ) ∧ ( q → r ) → ( p → r )
답. 가정이 참이라고 하면 p p q q r r p → r p → r p p p → r p → r
문제 11. "모든 정수의 제곱은 0 0
답. ∀ n ∈ Z , n 2 ≥ 0 ∀ n ∈ Z , n 2 ≥ 0
문제 12. ∃ x ∈ Q , x 2 = 2 ∃ x ∈ Q , x 2 = 2
답. 거짓입니다. 24강 문제 2에서 2 2
문제 13. ∀ n ∈ N , n 2 ≥ 2 n ∀ n ∈ N , n 2 ≥ 2 n
답. n = 1 n = 1 1 ≥ 2 1 ≥ 2
문제 14. ¬ ( ∀ x ∈ A , ∃ y ∈ B , P ( x , y ) ) ¬ ( ∀ x ∈ A , ∃ y ∈ B , P ( x , y ) )
답. ∃ x ∈ A , ∀ y ∈ B , ¬ P ( x , y ) ∃ x ∈ A , ∀ y ∈ B , ¬ P ( x , y )
문제 15. "모든 실수 x x x 2 = 1 x 2 = 1 x = 1 x = 1
답. 부정은 ∃ x ∈ R , ( x 2 = 1 ∧ x ≠ 1 ) ∃ x ∈ R , ( x 2 = 1 ∧ x = 1 ) x = − 1 x = − 1
문제 16. ∀ x ∈ R , ∃ y ∈ R , y 2 = x ∀ x ∈ R , ∃ y ∈ R , y 2 = x
답. 거짓입니다. x = − 1 x = − 1 x = − 1 x = − 1
문제 17. 문제 16에서 범위를 어떻게 좁히면 참이 됩니까?
답. x ≥ 0 x ≥ 0 y = x y = x
문제 18. "어떤 자연수는 모든 자연수를 나눕니다"를 기호로 적고 참거짓을 판정하세요.
답. ∃ m ∈ N , ∀ n ∈ N , m ∣ n ∃ m ∈ N , ∀ n ∈ N , m ∣ n m = 1 m = 1
문제 19. "모든 자연수는 어떤 자연수로 나누어집니다"를 기호로 적고 문제 18과의 차이를 설명하세요.
답. ∀ n ∈ N , ∃ m ∈ N , m ∣ n ∀ n ∈ N , ∃ m ∈ N , m ∣ n n n m m n n m m
문제 20. ∀ x ∈ ∅ , x > 100 ∀ x ∈ ∅ , x > 1 0 0
답. 참입니다. 반례가 될 원소가 하나도 없으므로 공허하게 참입니다.
문제 21. "두 홀수의 합은 짝수입니다"를 증명하세요.
답. m = 2 j + 1 m = 2 j + 1 n = 2 k + 1 n = 2 k + 1 m + n = 2 ( j + k + 1 ) m + n = 2 ( j + k + 1 )
문제 22. "n n n 3 n 3
답. n = 2 k n = 2 k n 3 = 8 k 3 = 2 ( 4 k 3 ) n 3 = 8 k 3 = 2 ( 4 k 3 ) 4 k 3 4 k 3
문제 23. "7 n + 4 7 n + 4 n n
답. 대우는 "n n 7 n + 4 7 n + 4 n = 2 k + 1 n = 2 k + 1 7 n + 4 = 14 k + 11 = 2 ( 7 k + 5 ) + 1 7 n + 4 = 1 4 k + 1 1 = 2 ( 7 k + 5 ) + 1
문제 24. "모든 정수 n n n 2 + 3 n + 2 n 2 + 3 n + 2
답. n 2 + 3 n + 2 = ( n + 1 ) ( n + 2 ) n 2 + 3 n + 2 = ( n + 1 ) ( n + 2 )
문제 25. "a ∣ b a ∣ b a ∣ c a ∣ c a ∣ ( 3 b − 2 c ) a ∣ ( 3 b − 2 c )
답. b = a j b = a j c = a k c = a k 3 b − 2 c = a ( 3 j − 2 k ) 3 b − 2 c = a ( 3 j − 2 k ) 3 j − 2 k 3 j − 2 k
문제 26. "x + y x + y x x y y
답. 대우는 "x x y y x + y x + y
문제 27. "모든 정수 n n n 2 n 2 5 5 0 , 1 , 4 0 , 1 , 4
답. n = 5 k + r n = 5 k + r r = 0 , 1 , 2 , 3 , 4 r = 0 , 1 , 2 , 3 , 4 n 2 = 25 k 2 + 10 k r + r 2 n 2 = 2 5 k 2 + 1 0 k r + r 2 r 2 r 2 5 5 r 2 r 2 0 , 1 , 4 , 9 , 16 0 , 1 , 4 , 9 , 1 6 0 , 1 , 4 , 4 , 1 0 , 1 , 4 , 4 , 1 { 0 , 1 , 4 } { 0 , 1 , 4 }
문제 28. 다음 증명의 잘못을 지적하세요. "임의의 실수 x x x > 0 x > 0 x + 1 > 1 x + 1 > 1 x x x + 1 > 1 x + 1 > 1
답. 임의로 잡은 뒤 x > 0 x > 0 x = − 1 x = − 1
문제 29. "m n m n m m n n
답. 대우는 "m m n n m n m n
문제 30. "n n 3 3 n 2 − 1 n 2 − 1 3 3
답. n = 3 k + 1 n = 3 k + 1 n 2 − 1 = 9 k 2 + 6 k = 3 ( 3 k 2 + 2 k ) n 2 − 1 = 9 k 2 + 6 k = 3 ( 3 k 2 + 2 k ) n = 3 k + 2 n = 3 k + 2 n 2 − 1 = 9 k 2 + 12 k + 3 = 3 ( 3 k 2 + 4 k + 1 ) n 2 − 1 = 9 k 2 + 1 2 k + 3 = 3 ( 3 k 2 + 4 k + 1 )
문제 31. 7 7
답. 유리수라 가정해 기약분수 p / q p / q p 2 = 7 q 2 p 2 = 7 q 2 7 7 p 2 p 2 7 7 p p 7 7 p = 7 m p = 7 m q 2 = 7 m 2 q 2 = 7 m 2 q q 7 7
문제 32. "가장 큰 소수는 존재하지 않습니다"를 증명하세요.
답. 24강 문제 3에서 소수가 무한히 많음을 증명했습니다. 유한하지 않으므로 가장 큰 것도 없습니다. 직접 보이려면 가장 큰 소수 P P P P 1 1
문제 33. "0 0
답. r ≠ 0 r = 0 x x r x r x x = ( r x ) / r x = ( r x ) / r r ≠ 0 r = 0
문제 34. "모든 자연수 n n n 2 + n + 17 n 2 + n + 1 7
답. n = 16 n = 1 6 256 + 16 + 17 = 289 = 1 7 2 2 5 6 + 1 6 + 1 7 = 2 8 9 = 1 7 2 n = 17 n = 1 7
문제 35. "모든 실수 a , b a , b ∣ a + b ∣ = ∣ a ∣ + ∣ b ∣ ∣ a + b ∣ = ∣ a ∣ + ∣ b ∣
답. a = 1 a = 1 b = − 1 b = − 1 0 0 2 2
문제 36. 문제 35의 명제를 참이 되도록 두 가지로 고치세요.
답. 부호가 같다는 조건을 붙여 "a b ≥ 0 a b ≥ 0 ∣ a + b ∣ = ∣ a ∣ + ∣ b ∣ ∣ a + b ∣ = ∣ a ∣ + ∣ b ∣ ∣ a + b ∣ ≤ ∣ a ∣ + ∣ b ∣ ∣ a + b ∣ ≤ ∣ a ∣ + ∣ b ∣
문제 37. "모든 실수 x x x x = 1 x x = 1
답. x = 0 x = 0 x ≠ 0 x = 0
문제 38. 다음 귀류법의 잘못을 지적하세요. "소수가 유한개라 하자. 목록의 곱에 1 1 N N N N
답. N N 30031 = 59 ⋅ 509 3 0 0 3 1 = 5 9 ⋅ 5 0 9 N N
문제 39. "a 2 a 2 a a 2 2
답. p 2 = 2 q 2 p 2 = 2 q 2 p p q 2 = 2 m 2 q 2 = 2 m 2 q q
문제 40. "2 + 3 2 + 3
답. 유리수 r r 3 = r − 2 3 = r − 2 3 = r 2 − 2 r 2 + 2 3 = r 2 − 2 r 2 + 2 2 = r 2 − 1 2 r 2 = 2 r r 2 − 1 r ≠ 0 r = 0 2 2 r = 0 r = 0 2 + 3 = 0 2 + 3 = 0
문제 41. 모든 자연수 n n ∑ i = 1 n ( 3 i − 2 ) = n ( 3 n − 1 ) 2 ∑ i = 1 n ( 3 i − 2 ) = 2 n ( 3 n − 1 )
답. n = 1 n = 1 1 1 1 ⋅ 2 2 = 1 2 1 ⋅ 2 = 1 k ( 3 k − 1 ) 2 + ( 3 k + 1 ) = 3 k 2 − k + 6 k + 2 2 = 3 k 2 + 5 k + 2 2 = ( k + 1 ) ( 3 k + 2 ) 2 2 k ( 3 k − 1 ) + ( 3 k + 1 ) = 2 3 k 2 − k + 6 k + 2 = 2 3 k 2 + 5 k + 2 = 2 ( k + 1 ) ( 3 k + 2 ) n = k + 1 n = k + 1
문제 42. 모든 자연수 n n 5 ∣ ( 6 n − 1 ) 5 ∣ ( 6 n − 1 )
답. n = 1 n = 1 5 ∣ 5 5 ∣ 5 6 k − 1 = 5 m 6 k − 1 = 5 m 6 k + 1 − 1 = 6 ( 5 m + 1 ) − 1 = 30 m + 5 = 5 ( 6 m + 1 ) 6 k + 1 − 1 = 6 ( 5 m + 1 ) − 1 = 3 0 m + 5 = 5 ( 6 m + 1 )
문제 43. n ≥ 1 n ≥ 1 ∑ i = 1 n 1 2 i = 1 − 1 2 n ∑ i = 1 n 2 i 1 = 1 − 2 n 1
답. n = 1 n = 1 1 2 2 1 1 − 1 2 = 1 2 1 − 2 1 = 2 1 1 − 1 2 k + 1 2 k + 1 = 1 − 2 − 1 2 k + 1 = 1 − 1 2 k + 1 1 − 2 k 1 + 2 k + 1 1 = 1 − 2 k + 1 2 − 1 = 1 − 2 k + 1 1
문제 44. n ≥ 4 n ≥ 4 n ! > 2 n n ! > 2 n n = 1 n = 1
답. n = 4 n = 4 24 > 16 2 4 > 1 6 k ! > 2 k k ! > 2 k ( k + 1 ) ! = ( k + 1 ) k ! > ( k + 1 ) 2 k > 2 ⋅ 2 k = 2 k + 1 ( k + 1 ) ! = ( k + 1 ) k ! > ( k + 1 ) 2 k > 2 ⋅ 2 k = 2 k + 1 k ≥ 4 k ≥ 4 k + 1 > 2 k + 1 > 2 n = 1 , 2 , 3 n = 1 , 2 , 3 1 < 2 1 < 2 2 < 4 2 < 4 6 < 8 6 < 8 n = 1 n = 1
문제 45. 강한 귀납법으로 "n ≥ 8 n ≥ 8 3 3 5 5
답. 기초 단계로 8 = 3 + 5 8 = 3 + 5 9 = 3 + 3 + 3 9 = 3 + 3 + 3 10 = 5 + 5 1 0 = 5 + 5 k ≥ 10 k ≥ 1 0 8 8 k k k + 1 ≥ 11 k + 1 ≥ 1 1 k + 1 − 3 = k − 2 ≥ 8 k + 1 − 3 = k − 2 ≥ 8 k − 2 k − 2 3 3 k + 1 k + 1 3 3
문제 46. 다음 증명의 잘못을 찾으세요. "모든 자연수 n n n = n + 1 n = n + 1 k = k + 1 k = k + 1 1 1 k + 1 = k + 2 k + 1 = k + 2
답. 기초 단계가 없습니다. n = 1 n = 1 1 = 2 1 = 2
문제 47. 피보나치 수열에서 F 1 2 + F 2 2 + ⋯ + F n 2 = F n F n + 1 F 1 2 + F 2 2 + ⋯ + F n 2 = F n F n + 1
답. n = 1 n = 1 1 1 F 1 F 2 = 1 F 1 F 2 = 1 F k F k + 1 + F k + 1 2 = F k + 1 ( F k + F k + 1 ) = F k + 1 F k + 2 F k F k + 1 + F k + 1 2 = F k + 1 ( F k + F k + 1 ) = F k + 1 F k + 2
문제 48. n n 2 2 n ( n − 1 ) 2 2 n ( n − 1 )
답. n = 2 n = 2 1 1 2 ⋅ 1 2 = 1 2 2 ⋅ 1 = 1 k k k ( k − 1 ) 2 2 k ( k − 1 ) k ( k − 1 ) 2 2 k ( k − 1 ) k k k ( k − 1 ) + 2 k 2 = k ( k + 1 ) 2 2 k ( k − 1 ) + 2 k = 2 k ( k + 1 ) ( n 2 ) = n ! 2 ! ( n − 2 ) ! = n ( n − 1 ) 2 ( 2 n ) = 2 ! ( n − 2 ) ! n ! = 2 n ( n − 1 )
48 4 8
정답 수
판단
43 4 3 02단원으로 넘어갑니다
34 ∼ 42 3 4 ∼ 4 2 틀린 문제가 속한 강의만 다시 읽고 넘어갑니다
33 3 3 21강부터 25강까지 다시 읽습니다
특히 3부와 5부에서 절반 이하를 맞혔다면 반드시 되돌아갑니다. 증명을 쓰는 손이 만들어지지 않은 채로 26강 이후를 읽으면 정의에서 성질을 유도하는 모든 대목이 막힙니다.