[Computational Thinking Skills] 프로그래밍과 논리/수학

SW Expert Academy - computational thinking skills

1. 프로그래밍과 논리/수학

• 문제 1:

사실-카드는 한 면은 알파벳, 다른 한 면은 숫자

주장-D 뒷면에는 숫자 3이 있다

문제-카드 [D, F, 3, 7]이 있을 때 어떤 카드를 뒤집어서 주장을 증명할 것인가?

• 문제 1 답: D, 7

F뒤에 3 이 있던 없던 주장과 상관 없음

3뒤에 꼭 d가 있어야 한다고 생각하기에 3을 뒤집어봐야한다고 생각하지만, 3뒤에 A가 있더라도 주장이 모순되지 않음

7을 뒤집어서 D가 있으면 주장이 깨지는 것이 증명되는 것이기에 7을 뒤집어봐야 함

---

• 문제 2:

규칙-20세 이하 맥주 마실 수 없음

문제-나이 혹은 마시고 있는 것을 표시한 다음 4명 중 확인이 필요한 사람은 몇 명이고 누구인가? [a:17세, b:31세, c:콜라, d:맥주]

• 문제 2 답: 2명 (a:17세, d:맥주)

---

사실 문제 1과 문제 2는 케이스 배치까지도 똑같은 논리적 구성이 동일한 문제.

근데 왜 문제2가 더 풀기 쉬울까?

-> 문제 1은 논리를 이용해 풀려 했기에 어려웠고, 문제 2는 논리가 쌓여 만든 직관을 이용해 풀었기 때문.

우리는 '직관적인 논리 vs 진짜 논리'를 구별해야 함

• ex 1:

너 과자 몇개 먹었니 vs 버스 타려는데 천원 있니

(사실 과자 3개 먹었지만 대답은) 나 과자 1개 먹었어. => 거짓말 아님. 사실이긴 사실임.

(사실 만원 있지만 대답은) 응 나 천원 있어.

=> 이때 사람들은 아니 너 만원 있다면서 왜 천원있다고 그랬어? 라고 하지 않음.

• ex 2:

합격하려면 토플 500점 이상 혹은 토익 600점 이상 필요 vs 복권에 당첨되면 자동차 혹으 천만원을 줍니다

난 토익 650점+토플 600점 다 가지고 있어서 합격함 -> inclusive or

복권 당첨돼서 자동차랑 천만원 둘 다 달라고 하면 당황할 것임 -> exclusive or (=둘 중 하나만 허용하는 것)

=> 혹은이라는 표현은 같으나 논리적인 내용은 다르다는 것을 알 수 있음.

---

이러한 직관을 soft logic 이라고 함. 그런데 수 많은 알고리즘은 hard logic 기반. -> soft logic으로 알고리즘을 이해하려고 하기에 어려움을 겪는 것!

---

기초 논리 연습

• 문제 1:

다음을 명제식 형태로 쓰고 참인지 거짓인지 판단하시오
1) 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
2) 만약 19893827938274839이 prime number라면, 2는 짝수이다.

1 해설) 미국에서 언제 월드컵이 열리는지 아무도 모름 그러나 이 한 문장 자체가 참인지 거짓인지는 우리가 판단해볼 수 있다.

(p이면 q이다 라고 생각해보자) 근데 p라는 가정조건을 살펴보자. 0이 홀수라면? 0은 홀수 아닌데,, p가 거짓임을 알 수 있다. 중요한 것은, p라는 전제조건이 거짓이면 전체 문장은 참이라는 공식(?)에 의해 1)은 참인 문장이다.

예를 들어보자, 100점 맞으면 친구에게 치킨을 사주기로 했다고 약속을 했다고 하자.

[100점 맞아서 치킨 사줌] - 약속 지킴

[100점 맞아서 치킨 안사줌] - 약속 어김

[90점 맞아서 치킨 사줌] - 약속 지킴 = 100점을 못받앗을 때 치킨 안사준다고 말하지도 않았기 때문이다.

[90점 맞아서 치킨 안사줌] - 약속 지킴 = 100점을 못받앗을 때 치킨 안사준다고 말하지도 않았기 때문이다.

p가 거짓이면 전체는 항상 참이다

2 해설) 저 긴 숫자가 진짜 prime number는 아무도 모름. 그러나 저 숫자가 prime number인지 아닌지와 무관하게 뒷 쪽은 우리가 판단해 볼 수 있다.

(p이면 q이다 라고 생각해보자) 지금 2는 짝수이다 라는 것은 참임을 우리가 알 수 있다. q가 참이라면 전체가 참이다 라는 공식에 의해 2)는 참임을 알 수 있다.

p가 거짓이고 q가 참이면- 전체가 참

p가 참이고 q가 참이면 - 전체가 참

q가 참이면 전체는 항상 참이다

• 문제 2:

p와 q가 명제이고 p->q가 거짓이라고 하자. 다음 명제식의 참 거짓은 어떻게 되는가?
~p -> q, p v q, q -> p

해설) p->q가 거짓이 되는 경우는 정해져 있음.

: p가 참이고 q가 거짓인 경우.

p->q가 거짓일 때는 p가 참이고 q가 거짓인 경우이다.

~p -> q [참] = not p는 거짓이기에 전체 명제식은 참.

p v q [참] = p는 참이고 q는 거짓이기에 p or q는 당연히 참.

q -> p [참] = q는 거짓이기에 전체 명제식은 참

• 문제 3:

다음 명제들의 역, 이, 대우를 쓰시오
1) 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
2) 만약 19893827938274839이 prime number라면, 2는 짝수이다.

1 역) 미국에서 2080년 월드컵이 열린다면, 0이 홀수이다.

1 이) 0이 홀수가 아니라면, 미국에서 2080년 월드컵이 열리지 않는다

1 대우) 미국에서 2080년 월드컵이 열리지 않는다면, 0이 홀수가 아니다.

2 역) 2가 짝수이면, ~가 prime number이다.

2 이) ~가 prime number가 아니라면, 2는 짝수가 아니다

2 대우) 2가 짝수가 아니라면, ~가 prime number가 아니다.

• 문제 4:

다음 명제식의 진리표를 만드시오
1) p ^ (q -> ~p)
2) (p ^ ~q) -> r

p	q	p ^ (q -> ~p)
T	T	F (q가 참, ~p가 거짓이므로 T&&F로 인해)
T	F	T (q가 거짓이므로 T&&T로 인해)
F	T	F (AND연산자 때문)
F	F	F (AND연산자 때문)

AND (^) 연산자는 둘 다 참일때만 참이다

p가 참이고 q가 거짓이므로 p -> q는 거짓이다

p	q	(p ^ ~q) -> r
T	T	T (p ^ ~q가 거짓이라)
T	F	r이 거짓이라면 (p ^ ~q가 참이기에) F
F	T	T (p ^ ~q가 거짓이라)
F	F	T (p ^ ~q가 거짓이라)

---

• 당구공 paradox
  

  

  
  

  

위 증명 방법에서 잘못된 것은?

p(n)이 참이라고 가정한 것이 잘못되었는가? -> 아니다.

왜냐하면, p -> q일 때, p가 거짓이면 전체가 참이 되는 수학적 귀납법이 있기에 p(n)이 참으로 설정하던 거짓으로 설정하던 잘못된 것은 아니다.

그러나 p(1)일 때 집합은 모두 색이 같다. 그렇기에 p(2)도 색이 같다라는 도출과정이 틀린 것. 하나일 때 색이 같은 것은 단순히 공이 하나일 뿐. 2개여도 색이 같다는 것은 어디에서도 도출할 수 없음.

---

• Infinitely Many Prime Numbers(=소수)

prime number는 무한히 많다라는 것을 증명하는 과정

prime number가 p1, p2, ~, pk 까지 k개가 있다.

p1+p2+~+pk하면 n이다.

그렇다면 이 n은 그 어떤 prime수보다도 더 큰 숫자이다. 즉, prime이 아니다.

prime이 아니므로 소인수분해가 될 것임. 그런데, n을 어떤 수로 나누어봐도 나머지가 1.

이러한 도출로 미루어보았을 때 prime number는 무한히 많다는 것을 알 수 있음.

위 증명에 대한 반론

k개보다 몇개 더 많을 뿐이지 무한개는 아니지 않음? =[prime number가 k개이면 모순이 발생]

그러나 이 반론은 틀림.

저 주장을 참이라고 생각하는 반론의 전체 문장을 뜯어보면

p(prime number가 k개)이면 q(모순이 발생)이다라고 생각할 때, 전체 문장이 항상 참이기 위해서는 p가 항상 거짓이어야 함. 그러므로 prime number가 k개는 항상 거짓이다. 즉, prime number는 무한하다를 알 수 있음

---

수학적 귀납법을 적용해보자

수학적 귀납법의 기본형:

p(1)이 참이고, p(n) -> p(n+1)이 참이면 p(n)은 모든 자연수 n에 대해 참이다

수학적 귀납법의 강한 형태:

p(1)이 참이고, p(1), p(2), ~, p(n)까지 모두 참이면, p(n+1)이 참이다

• ex)

다음 함수가 1부터 x까지의 합을 계산함을 증명해 보자
int sum(int x)
{
    if(x<=0) return 0;
    return x + sum(x-1);
}

high-level 증명) 위 코드는 1부터 x까지의 합의 정의 중 하나인 s(n) = s(n-1) + n을 그대로 코딩한 것으로, 증명돈 것이다!

라고 증명해도 되지만 우리는 조금 더 세밀하게 증명해보자.

상세한 증명)

1. 상세한 증명을 위해서는 증명이 가능한 명제를 만들어야 함

위 코드에서 증명이 가능한 명제:

sum(X)가 리턴하는 값은 1+2+~+x의 값과 항상 같다.

2. 위에 써놓은 수학적 귀납법을 적용할 수 있음

p(1)이 참이고, p(n) -> p(n+1)이 참이면 p(n)은 모든 자연수 n에 대해 참이다

p(1)이 참이고, p(1), p(2), ~, p(n)까지 모두 참이면, p(n+1)이 참이다

p(1)이 참이다. [참] = 실제로 코드에 1 집어넣으면 sum(1)이 리턴하는 값은 1임을 알 수 있음.

p(x) -> p(x+1)는 참이다. [참] =이 문장을 증명하기 위해서는 sum(x-1)이 1+2+

+x-1를 리턴하면 sum(x)는 1+2+

+x를 리턴한다를 증명하면 됨.

코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴함. 근데 우리는 'sum(x-1)이 1+2+

+x-1를 리턴하면'라고 가정했으므로 sum(x)는 1+2+

+x를 리턴함을 확인할 수 있음

즉, sum(x)를 넣으면 어떤 일이 생길까 생각할 필요없이 sum(x-1)이 어떤 값을 리턴하는지만 가정하고, 이 가정이 지켜지는지만 가정한다음에, 똑같은 가정을 sum(x)에 적용해 성립하는지만 보면 됨

->p(n)이 참이면 p(n+1)이 참이다에서 p(n)이 진짜 참인지를 걱정하는 것처럼 p(n-1)이 제대로 된 값을 진짜로 리턴하는지 걱정하기보다! 진짜로 리턴한다고 가정하고, 그때 p(n)이 제대로 리턴하는지 알면 됨

---

버블 소트의 증명

소팅 됐어! 보다,

a[1]<a[2]<~<a[n]의 상태가 최종적으로 이루어지는 것을 증명하는 것이 더 정확.