SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
프로그래머가 기본으로 가지고 있어야 할 논리와 수학적인 생각을 공부한 내용을 정리한 글이다.
프로그래머는 어떤 문제를 하드 논리적으로 해결할 수 있어야 하며, 해결하기 어렵기에 논리적으로 해결하는 연습을 해야한다.
문제 1. 다음을 명제식으로 쓰고 참인지 거짓인지 판단하시오.
1번. 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
가정이 거짓(F)이면 이 명제의 결과는 무조건 참(T)이다.
이유가 뭘까?
예시를 들고 싶다.
"시험 100점이면, 치킨을 사줄게" 라는 명제가 있다고 하자.
시험 100점을 맞는 다는 가정이 맞다면 치킨을 사주는 결과가 참이 된다.
하지만, 시험 100점을 못맞았더라면? 치킨을 못사주나? 그건 아니다.
시험을 100점 맞던 맞지 않았던 치킨은 사줄수도 있다.
이해가 안갈 수 있다. 다시 한번 풀어서 얘기하면, 100점을 맞으면(T) 치킨을 먹을 수 있고 100점을 맞지 않아도(F) 치킨을 사줄 수 있다.
즉, 가정이 거짓이면 결과의 참/거짓 여부와 무관하게 명제식은 참이된다.
문제에서도 0이 홀수이든 아니든 2080 월드컵이 열린다. 2080에 미국에서 월드컵이 열리는지는 모르지만 여기서는 그 사실이 중요한게 아니다.
2번. 만약 19893827938274839이 Prime Number(소수)라면, 2는 짝수이다
1번과는 다르게 가정의 참/거짓 여부를 확인하지 못하고, 결과는 참이라는 것을 확인할 수 있다.
이럴때는 위 명제식의 대우를 생각해보자.
대우 -> "2는 홀수이면, 18719186298126981이 프라임 넘버가 아니다" 라는 식을 보자.
가정이 거짓이므로 이 명제식은 무조건 참이다.
중요 !
결론이 참인 경우, 가정의 참/거짓 여부와 무관하게 명제식은 무조건 참이다.
문제 2. p와 q가 명제이고 p → q가 거짓이라고 하자. 다음 명제식의 참/거짓은 어떻게 되는가?
2문제에서 p -> q가 거짓이기 위해서는, p가 참(T)이고 q는 거짓(F)이어야 한다.
(둘다 거짓이면 그 명제는 참이 되어버리니깐... 또한, q가 참이면 명제식 자체가 참이 되니깐,,,,,,)
1번. ~p → q
p는 참이고, ~p는 거짓이다. 또한 q는 거짓이므로 이 명제는 참이다.
2번. p ∨ q
참 and 거짓은 둘 중 하나가 참이므로 명제는 참이다.
3번. q → p
결론이 참이기에 가정은 무관하게 명제는 참이다.
문제 3. 명제식의 역, 이, 대우
명제식 : p → q
역 : q → p
이 : ~p → ~q
대우 : ~q → ~p
중요 !
위 명제식이 참이라면 이 중에서 성립되는 것은 '대우'뿐이다.
왜??
진리표는 보면 명제식와 대우가 같다.
문제 4. 다음 명제식의 진리표를 만드시오
1번. p∧ (q → ~p)
| p | q | ~p | (q→ ~p) | p∧(q→ ~p) |
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | T | F |
| F | F | T | T* | F |
2번. (p ∧ ~q )→ r
| p | q | r | (p ∧ ~q ) | (p ∧ ~q )→ r |
| T | T | T | F | T |
| T | T | F | F | T |
| T | F | T | T | T |
| T | F | F | T | F* |
| F | T | T | F | T |
| F | T | F | F | T |
| F | F | T | F | T |
| F | F | F | F | T |
증명 연습
∀x(=모든 임의의 수 x에 대해), P(x) → Q(x)를 증명하려는데, Q(x)가 항상 참인 경우
문제 1 : 다음을 증명하시오
1번. 실수 x에 대해, 만약 x < -1 이면, x²+¼ > 0 이다
x² > ¼ 이기 때문에, (*x가 실수일 경우 x의 제곱은 항상 양수이다) ≫ 결론이 참이다.
즉, 결론이 참일 때는 명제식은 무조건 참이기 때문에 Q(x)는 항상 참이다.
따라서, ∀x(=모든 임의의 수 x에 대해), P(x) → Q(x)이다.
2번. n이 홀수이면, 4n³ + 6n² + 12는 짝수이다.
4n³ + 6n² + 12은 2(2n³ + 3n² + 6)와 같다. 그러므로 결과는 참이다.
(n의 홀수여부(가정) 와 관계없다)
즉, Q(x)는 항상 참이다.
따라서, ∀x(=모든 임의의 수 x에 대해), P(x) → Q(x)이다.
∀x(=모든 임의의 수 x에 대해), P(x) → Q(x)를 증명하려는데, P(x)가 항상 거짓인 경우
P(x) = 가정이 거짓인 것을 증명하면 된다.
(*가정이 거짓이면, 결론의 참/거짓 유무와 관계없이 명제식은 늘 참이다
= 결론이 참이면, 가정의 참/거짓 유무와 관계없이 명제식은 늘 참이다.)
문제 2 : 다음을 증명하시오
1번. 실수 x에 대해, 만약 2x² - 4x + 4 < 0 이면, x > 8 이다.
2x² - 4x + 4 < 0 = 2(x²-2x+2) = 2(x-1)²+6 ≥ 0 이다.
(*실수의 제곱은 늘 양수이기 때문에)
따라서 2x² - 4x + 4 < 0은 거짓이다.
그렇기 때문에 P(x)은 거짓이므로, ∀x, P(x) → Q(x)은 참이다.
2번. 4n³ + 6n² + 11이 짝수이면, n이 홀수이다.
4n³ + 6n² + 11 = 2(2n³ + 3n² + 5) + 1 이기 때문에, 짝수 + 1은 늘 홀수이기 때문에,
4n³ + 6n² + 11은 늘 홀수이다.
그렇기 때문에 P(x)은 거짓이므로, ∀x, P(x) → Q(x)은 참이다.
[참고]
'CS 백엔드 > Computational Thinking' 카테고리의 다른 글
| [SWEA] Computational Thinking 논리와 증명 / 수와 표현 문제풀이 (3) - 귀류법 (1) | 2023.01.03 |
|---|---|
| [SWEA] Computational Thinking 논리와 증명/수와 표현 문제 (2) (0) | 2023.01.03 |
| [SWEA] Computational Thinking 논리와 증명/수와 표현 문제 (1) (0) | 2023.01.03 |
