1. 논리와 증명
문제 1. 다음 명제들이 항진명제라는 것을 진리표를 이용해서 보이시오.
1번. ~(~p∧ q) ∨ q
2번. (~p∨ q) ∨ (p ∧ ~q)
(풀이)
* 항진명제
: 논리식 혹은 합성명제에 있어서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이,
그 합성 명제의 진리값이 항상 참의 값을 가지는 것.
∧ (and) : 둘 중 하나라도 F가 있다면, F이다. (둘 다 T인 경우에만 T)
∨ (or) : 둘 중 하나라도 T가 있다면, T이다. (둘 다 F인 경우에만 F)
1번.
| p | q | ~(~p∧ q) | ~(~p∧ q)∨ q |
| T | T | T | T |
| T | F | T | T |
| F | T | F | T |
| F | F | T | T |
네 경우 모두 T가 나오기 때문에, ~(~p∧ q)∨ q 은 항진 명제이다.
2번.
| p | q | (~p ∨ q) | (p ∧ ~q) | (~p∨ q) ∨ (p ∧ ~q) |
| T | T | T | F | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | F | T |
네 경우 모두 T가 나오기 때문에, (~p∨ q) ∨ (p ∧ ~q) 은 항진 명제이다.
문제 2. 다음 명제들이 모순명제라는 것을 진리표를 이용해서 보이시오.
1번. (~p∨ q) ∧ (p ∧ ~q)
2번. (p ∧ q) ∧ (p ∧ ~q)
(풀이)
* 모순명제
: 논리식 혹은 합성명제에 있어서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이,
그 합성 명제의 진리값이 항상 거짓의 값을 가지는 것
∧ : 둘 중 하나라도 F가 있다면, F이다. (둘 다 T인 경우에만 T)
∨ : 둘 중 하나라도 T가 있다면, T이다. (둘 다 F인 경우에만 F)
1번.
| p | q | (~p∨ q) | (p ∧ ~q) | (~p∨ q) ∧(p ∧ ~q) |
| T | T | T | F | F |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | F | F |
네 경우 모두 F가 나오기 때문에, (~p∨ q) ∧ (p ∧ ~q)은 모순 명제이다.
2번.
| p | q | (p ∧ q) | (p ∧ ~q) | (p ∧ q) ∧ (p ∧ ~q) |
| T | T | T | F | F |
| T | F | F | T | F |
| F | T | F | F | F |
| F | F | F | F | F |
네 경우 모두 F가 나오기 때문에, (p ∧ q) ∧ (p ∧ ~q)은 모순 명제이다.
문제 3. 다음 명제의 쌍들에 대해서 두 명제가 동등한지를 진리표를 이용해서 확인하시오.
1번. p∧ (p ∨ q) 와 p
2번. ~p ∨ ~q 와 ~ (p ∨ q)
(풀이)
1번.
| p | q | (p ∨ q) | p∧ (p ∨ q) |
| T | T | T | T |
| T | F | T | T |
| F | T | T | F |
| F | F | F | F |
p∧ (p ∨ q)와 p의 진리값은 늘 동등하다.
2번.
| p | q | ~p ∨ ~q | (p ∨ q) | ~ (p ∨ q) |
| T | T | F | T | F |
| T | F | T | T | F |
| F | T | T | T | F |
| F | F | T | F | T |
~p ∨ ~q 와 ~ (p ∨ q)의 진리값은 늘 동등하지는 않다.
문제 4. 명세식의 변형을 통하여 다음 명세를 간소하시오.
1번. (p ∧~q) ∨ (p ∧ q)
2번. (p ∨ ~q) ∧ (~p ∨ ~q)
(풀이)
1번.
2번.
문제 5. 다음 명제들이 참인지 확인하시오. 단, R은 실수의 집합을 의미하고, Z는 정수의 집합을 의미한다.
1번. ∀x ∈ R, x² ≥ x
2번. ∀x ∈ Z, x² ≥ x
3번. ∃x ∈ R, x² ＜ x
4번. ∃x ∈ Z, x² ＜ x
(풀이)
∀x : 모든 x
∃x : 어떤 x
1번.
[ 문제 해설 : 모든 실수 x에 대하여, x² ≥ x가 성립한다. ]
[ 증명 ]
x² ≥ x
= x(x-1) ≥0
x = 0.3인 경우 (0 < x < 1), 0.3 * -0.7 = -0.24 < 0 이다.
0 < x < 1 일 때, 위 식은 성립하지 않으므로, ∀x ∈ R, x² ≥ x 은 거짓이다.
2번.
[ 문제 해설 : 모든 정수 x에 대하여, x² ≥ x가 성립한다. ]
[ 증명 ]
x² ≥ x
= x(x-1) ≥0
ⅰ) x = 0 또는 x = 1인 경우, 0 = 0 이 성립한다.
ⅱ) x < 0 인 경우, 음수*음수=양수이므로, 위 식은 성립한다.
ⅲ) x > 1 인 경우, 양수*양수=양수이므로, 위 식은 성립한다.
모든 정수에 대해서 위 식은 성립하므로,∀x ∈ Z, x² ≥ x은 참이다.
3번.
[ 문제 해설 : 어떤 실수 x에 대하여, x² ＜ x가 성립한다. ]
[ 증명 ]
x² ＜ x
= x(x-1) ＜ 0
1번 문제와 반대의 경우이다. 즉 0 < x < 1일 때 위 식은 성립한다.
ⅰ) x < 0 인 경우, 음수*음수=양수이므로, 위 식은 성립하지 않는다.
ⅱ) x > 1 인 경우, 양수*양수=양수이므로, 위 식은 성립하지 않는다.
ⅲ) 0 < x < 1인 경우, 양수*음수=음수이므로, 위 식이 성립된다.
ⅰ, ⅱ조건에서는 성립하지 못했지만, 어떤 실수에 대해서 묻는 명제이다.
ⅲ조건이 성립한다면, x² ＜ x가 성립하는 어떤 실수 x가 존재하기 때문에,
∃x ∈ R, x² ＜ x는 참이다.
4번.
[ 문제 해설 : 어떤 정수 x에 대하여, x² ＜ x가 성립한다. ]
[ 증명 ]
x² ＜ x
= x(x-1) ＜ 0
2번 문제와 반대의 경우이다.
2번에서 모든 정수 x에 대해 x² ≥ x가 성립했기 때문에, x² ＜ x가 성립되는 정수는 없다.
ⅰ) x = 0 또는 x = 1인 경우, 0 = 0 이므로, 위 식은 성립하지 않는다.
ⅱ) x < 0 인 경우, 음수*음수=양수이므로, 위 식은 성립하지 않는다.
ⅲ) x > 1 인 경우, 양수*양수=양수이므로, 위 식은 성립하지 않는다.
위처럼 모든 정수 x에 대해서 x² ＜ x 가 성립되지 않기 때문에,
∃x ∈ Z, x² ＜ x 은 거짓이다.
문제 6. (직접 증명) n이 짝수이면, 3n+5는 홀수임을 증명하라.
(힌트 : n = 2k로 두고, 3n+5가 2(어떤 정수)+1 형태로 표현될 수 있는지)
(풀이)
문제 7. n이 홀수이면, n²+n이 짝수임을 증명하라.
(풀이)
문제 8. m이 짝수이고, n이 홀수이면, 2m+3n은 홀수임을 증명하라.
(풀이)
문제 9. (대우를 증명) 자연수 n에 대해, n² + 5 가 홀수이면, n이 짝수임을 증명하라.
(풀이)
문제 10. n²가 짝수이면, n은 짝수임을 증명하라.
(풀이)
문제 11. (경우를 나누어 증명) 자연수 n에 대해 n² + 5n + 3은 항상 홀수임을 증명하라.
(힌트 : n이 짝수인 경우와 홀수인 경우를 따로 증명한다.)
(풀이)
문제 12. n²이 3의 배수이면, n은 3의 배수임을 증명하라.
(풀이)
문제 13. n이 홀수이면, n²을 8로 나눈 나머지는 1임을 증명하라
(힌트 : n을 4로 나눈 나머지가 1인 경우와 3인 경우로 나누어보자)
(풀이)
문제 14. 어떤 자연수를 제곱하여도 그 결과를 3으로 나눈 나머지는 2가 아님을 증명하라.
(풀이)
문제 15. (귀류법) 유리수와 무리수의 합은 무리수임을 증명하라.
(힌트 : 어떤 유리수와 어떤 무리수의 합이 유리수가 된다고 가정하고, 모순을 이끌어 낼 수 있는가?)
(풀이)
문제 16. √2는 무리수임을 증명하라.
(힌트 : 유리수가 된다는 것은 기약분수로 표현이 된다는 것이다.)
(풀이)
문제 17. log₂5는 무리수임을 증명하라.
(풀이)
문제 18. (수학적 귀납법) 1+2+3+ ⋯ + n = n(n+1)/2 임을 증명하라.
(풀이)
문제 19. 1² + 2² + 3² + ⋯ + n² = n(n+1)(2n+1) / 6 임을 증명하라.
(풀이)
문제 20. r ≠ 1일 때,
임을 증명하라.
(풀이)
문제 21. 2 이상의 모든 자연수 n에 대해 n³-n은 6으로 나누어 떨어짐을 증명하라.
(풀이)
문제 22. 2 이상의 모든 자연수 n에 대해
임을 증명하라.
(풀이)
문제 23. n X n 체스판이 있다. 시작 시점에 일부 칸들이 감염되고 있다. 매 초마다 감염이 증가할 수 있다.
규칙은 다음과 같다.
어떤 감염되지 않은 칸은 상하나 좌우로 인접한 네 개의 칸들 중 2개 이상이 감염된 상태일 때 감염된다.이 규칙에 따라 모든 칸들을 감염시키기 위해서는 초기에 n개 이상의 칸들이 감염되어 있어야 함을 증명하라.
(풀이)
문제 출처 : SW Expert Academy (swexpertacademy.com/main/main.do)