SWEA [Computational Thinking] 0. 프로그래밍과 논리 / 수학

https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

 

1. 논리와 증명

 

- 일상 생활에서는 Soft Logic이 빠르기 때문에 유용하지만 프로그래밍은 Hard Logic을 사용해야됨. (직관으로 프로그래밍을 이해하려면 많은 어려움이 따름)

 

- 알고리즘 설명을 봐도 이해가 안됨 -> 증명을 안봤기 때문

- 증명을 봐도 이해가 안되는것 -> 직관으로 이해하려하기 때문

 

논리 연습

-문제 1: 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.

가정이 거짓이라면 결론이 참이든 거짓이든 전체는 참이다.

그 이유를 설명하기 위해 예를 들자면 만약 아들에게 100점을 맞으면 치킨을 사주겠다고 약속을 하였다.

이때 100점을 맞았다면 (가정이 T) 치킨을 사주면 된다. (결론 T) 하지만 100점을 맞지 않았다고 (가정이 F), 치킨을 사주지 않을 이유는 없다. 교육상에 문제가 생길 순 있어도 치킨을 사주든 안사주든 문제가 생기지 않는다. (결론이 T이든 F이든 아무 상관없이 전체가 T)

따라서 이 문제는 참이다. 

 

-문제 2: 만약 19384893773이 prime number(소수)라면, 2는 짝수이다.

결론이 참이면 전체는 참이다. 

이 명제의 대우를 생각해 본다면 

만약 2가 홀수라면, 19384893773이 prime number(소수)가 아니다. 인데 가정이 거짓이므로 결론에 상관없이 이 명제식은 참이다. 대우가 참이므로 본 명제 또한 참이 되야하는데 정리하자면 결론이 참인 명제식은 전체가 참이다. 

 

이 문제 두개로 알 수 있는 사실은 두가지이다.

 

1. 가정이 거짓이면 전체는 참이다.

 

2. 결론이 참이면 전체는 참이다.

 

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

 

p -> q 가 거짓인 경우는 p가 참일때 q가 거짓인 경우밬에 없으므로 각각을 대입하여 명제식을 풀어주면된다.

 

역, 이, 대우는 p -> q 일때 역은 q -> p , 

이는 ~p -> ~q 이고

대우는 ~q -> ~p이다.

 

p and (q -> ~p) 의 진리표를 만들자.

p q 명제식

T T F

T F T

F T F

F F F

이런식으로 된다.

 

증명이란? 정확한 명제식으로 표현할 수 있는것이다.

보통 정확한 명제식까지는 쓰지 않지만 근본적으로는 명제식으로 바꿀 수 있다.

증명에 대한 수많은 오해가 p -> q 와 p <-> q 를 혼동하는 것에서 일어난다.

 

당구공 paradox

모든 당구공은 색이 같다는 다음 증명에서 잘못된 것은?

- 수학적 귀납법: P(1)이 참이고, P(n) -> P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

-어떤 집합이라도 그 당구공의 갯수가 n개짜리인 당구공집합을 

 

n이 충분히 크다고 생각하기 때문에 n =1 일때는 생각하지 못함 실제로 코테 문제를 풀때 많이 실수하는 부분이다.

 

!수학적 귀납법

 수학적 귀납법의 기본형: P(1)이 참이고, P(n) -> P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

 

수학적 귀납법의 강한 형태: P(1)이 참이고, P(1) or P(2) or ... or P(n) -> P(n + 1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다. 

 

다음 함수가 1부터 x까지의 합을 계산함을 증명해 보자.

 

int sum(int x)

{

 if (x <= 0) return 0;

 return x + sum(x - 1);

}

 

 

"sum(x)가 리턴하는 값은 1+2+3+...+x의 값과 항상 같다."라는 명제부터 세우자.

 

P(1)이 참이다. -> 실제로 코드에 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+2+...+(x-1) + x = 1 +2+...+x를 리턴함을 알 수 있음

sum(x-1)을 블랙박스로 보는 것이 이해에 도움을 줄 때가 있음.

 그냥 푼것을 보는것은 쉽지만 실제로 이런 식을 세우기는 어렵다.

 

수학적 귀납법을 적용할 때 P(n)이 참인지 걱정할 필요가 없고 P(n)은 참이라고 가정을 하고 그 경우에 P(n+1)이 참인지만 생각하면 된다.

 

버블 소트의 증명! 연습문제

 

중요!!! 상세한 증명에 대한 경험이 없는 경우가 많고, 상세한 증명 없이는 확인하거나 이해할 수 없는 문제들이 많으므로 연습 문제들은 상세한 증명을 제시하는 것을 목표로한다.

 

 

 

 

평소 알고리즘과 코테 문제를 풀면서 약간 손가는 대로 푸는 듯한 느낌을 받은 적이 있다. 이는 내가 아직 Hard Logic을 사용하지 않고 Soft Logic만을 사용해서 알고리즘을 풀었기 때문이라는 확신이 든다. 

 

SSAFY에서 입과 전 이런 강의를 내게 권한것은 이제부터 풀게 될 더 높은 차원의 코딩을 하려면 논리적인 사고를 바탕으로 정확히 확인하고 코드를 짜야함을 의미한다.

 

이전에 가지고 있던 버릇을 고치긴 힘들겠지만 이 방법이 정도임을 깨닫고 천천히 나아가는 수밬에 없을것이다. 또한 쉬운 문제들을 정확하게 확인하는 것을 연습해보자. 

 

이러한 정확하게 확인하는 과정을 수많은 세월동안 정리해 둔것이 "증명"기법이다.

 

확인이 안된 상태에서 프로그램을 짜기 시작하면 결과가 정확할지, 얼마나 빠를지 예측할 수 없고, 제대로 된 결과가 나오지 않으면 고치는 것이 어렵고 무작정 여러가지를 시도해 볼 수 밬에 없음을 가슴속에 깊이 묻자. 이번에 입과 코딩 테스트를 칠때도 2번문제를 풀지 못했던 것은 이러한 과정을 하지 않고 무작정 문제를 풀었기 때문이다.