[SWEA] Computational Thinking 논리와 증명/수와 표현 문제 (2)

문장 뿐만 아니라 수를 이용해서 명제를 증명할 수도 있다.

 

https://ko.wikipedia.org/wiki/%EC%88%98%ED%95%99_%EA%B8%B0%ED%98%B8

수학 기호 - 위키백과, 우리 모두의 백과사전

 

∀ : 모든 것에 대하여(모든 수가 만족한다)
∃ : 존재한다(만족하는 어떤 것이 있다)

 

 

1. 문제

문제에 들어가기 앞서 위의 수학 기호를 이해하고 있어야 하고,

 

주어진 명제를 증명하기 굉장히 까다롭다고 느낀다면 서슴없이 대우를 통해 그 명제를 증명해내야 한다.

 

또한, 짝수면 2k, 홀수면 2k + 1 등등 가정과 결론에서 미지수를 적재 적소하게 활용해야 증명이 가능하다. 수는 뭐 이래 해야지 어떡해;;

 

 

문제 5 : 다음 명제들이 참인지 확인하시오

∀x ∈ R , x^2 ≥ x
해석 : 모든 x가 실수 일 때 x^2 >= x 이다

• x 가 -1 < x < 1 일 때 x^2 >= x 는 거짓이 된다
• 그러므로 명제는 거짓이다

∃x ∈ Z , x^2 < x 해석 : x^2 < x를 만족하는 정수인 어떤 x가 존재한다

• x가 1 이상일 때 양변을 x로 나누면 x < 1 -> 거짓
• x가 0일 때 대입한 결과 0 < 0 -> 거짓
• x가 -1 이하일 때 양변을 x로 나누면 x > 1 -> 거짓
• 그러므로 명제는 거짓이다

문제 6 : n이 짝수이면 3n + 5는 홀수임을 증명하라

• 자연수 k에 대해 n = 2k일 때 3n+5 == 6k+5 == 2(3k+2) + 1이다
• 따라서 3n+5는 홀수 이다

문제 7 : n이 홀수이면 n^2 + n은 짝수임을 증명하라

• 자연수 k에 대해 n = 2k+1일 때 n^2 + n == 4k^2 + 6k + 2 == 2(k^2 + 3k + 1)이다
• 따라서 n^2 + n은 짝수 이다

문제 8 : m이 짝수이고 n이 홀수이면 2m + 3n은 홀수임을 증명하라

• 자연수 k,l에 대해 m = 2k, n = 2l+1일 때 2m + 3n == 4k + 6l + 3 == 2(2k + 3l + 1) + 1이다
• 따라서 2m + 3n은 홀수 이다

문제 9 : 자연수 n에 대해 n^2+5가 홀수이면 n은 짝수임을 증명하라

• 대우 : n이 홀수일 때 n^2+5는 짝수
• 자연수 k에 대해 n = 2k+1일 때 n^2+5 == 4k^2 + 4k + 6 == 2(k^2 + 2k + 3) 이므로 짝수이다
• 따라서 명제는 참이다

문제 10 : n^2이 짝수이면 n은 짝수임을 증명하라

• 대우 : n이 홀수일 때 n^2도 홀수이다
• 자연수 k에 대해 n = 2k+1일 때 n^2 == 4k^2 + 4k + 1 == 2(2k^2 + 2k) + 1 이므로 홀수이다
• 따라서 명제는 참이다

문제 11 : 자연수 n에 대해 n^2 + 5n + 3은 항상 홀수임을 증명하라

• n이 홀수일 때 자연수 k에 대해 n = 2k+1이라 가정하면 n^2 + 5n + 3 == 4k^+14k + 9 == 2(2k^2 + 7k + 4) + 1 이므로 n^2 + 5n + 3 은 홀수이다
• n이 짝수일 때 자연수 k에 대해 n = 2k라 가정하면 n^2 +5n +3 == 4k^2 + 10k + 3 == 2(2k^2 + 5k + 1) + 1 이므로 n^2 + 5n + 3 은 홀수이다
• 따라서 명제는 참이다

문제 12 : n^2이 3의 배수이면 n은 3의 배수임을 증명하라

• 대우 : n이 3의 배수가 아니면 n^2도 3의 배수가 아니다
• 자연수 k에 대해 n = 3k+1일 때 n^2 == 9k^2 + 6k + 1 == 3(3k^2 + 2k) + 1 이므로 n^2은 3의 배수가 아니다
• 자연수 k에 대해 n = 3k+2일 때 n^2 == 9k^2 + 12k + 4 == 3(3k^2 + 4k + 1) + 1 이므로 n^2은 3의 배수가 아니다
• 따라서 명제는 참이다

문제 13 : n이 홀수이면 n^2을 8로 나눈 나머지는 1임을 증명하라

• 자연수 k에 대해 n = 4k+1일 때 n^2 == 16k^2 + 8k + 1 == 8(2k^2 + k) + 1 이므로 n^2을 8로 나눈 나머지는 1이다
• 자연수 k에 대해 n = 4k+3일 때 n^2 == 16k^2 + 24k + 9 == 8(2k^2 + 3k + 1) + 1 이므로 n^2을 8로 나눈 나머지는 1이다
• 따라서 명제는 참이다

문제 14 : 어떤 자연수를 제곱하여도 그 결과를 3으로 나눈 나머지가 2가 아님을 증명하라

• 자연수 k에 대해 n = 3k일 때 9k^2 을 3으로 나눈 나머지는 0이다
• n = 3k+1일 때 9k^2+6k+1을 3으로 나눈 나머지는 1이다
• n = 3k+2일 때 9k^2+12k+4를 3으로 나눈 나머지는 1이다
• 따라서 명제는 참이다

 

 

 

 

 

 

 

[참고]

https://velog.io/@gandi0330/SW-Expert-Academy-Computational-Thinking-%EB%85%BC%EB%A6%AC%EC%99%80-%EC%A6%9D%EB%AA%85-%EC%88%98%EC%99%80-%ED%91%9C%ED%98%84-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-3