Step1 - Computer Thinking (논리/수학) + 문제

#0 서론

프로그래밍의 어려운 점

- 문법과 라이브러리 : 그냥 규칙을 외우는게 어려움

- 논리

 

#1 논리와 증명

1. 직관과 논리를 분리하는 것의 어려움.

직관은 논리적인 느낌을 주는 것이다. 이를 분리하여 생각하는 게 중요하다.

 

예를 들어 "버스 타게 천원 있냐?" 라고 친구에게 물었을 때, 그 친구는 대충 자신이 천원 넘게 소지금이 있다는 걸 알고 "그렇다" 라고 대답한 경우가 직관이다.

허나 프로그램으로 이를 작성하려면 하드 로직을 통해 논리를 적용하게 되고 이를 표현하면 (소지금) > 1000 과 같은 논리를 사용해야 한다.

 

알고리즘을 볼 때는 항상 직관이 아닌 논리로 접근하려는 습관이 필요하다.

 

예시가 다 쉽다고 생각했는데 조금 놀란건

 

"만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다."

라는 전체 명제는 참이라는 사실을 한참 생각해보고 알았다는 것이다.

앞의 만약 문장이 거짓일 뿐, 명제 자체는 참이된다. 심지어 2080년 미국에서 월드컵이 열려도 참인 명제이다.

왜냐하면 홀수이면 열린다고 했지, 짝수일 때 열리지 않는다는 것이 아니기 때문.

 

생각해보면 프로그래밍으로 코딩을 했을 때, 오류가 나지 않으면 옳은 명제라고 판단해도 된다는 생각이 들었다.

 

위 명제로 if문을 작성하면 "미국에서 2080년 월드컵이 열린다" 라는 문장을 검증하기 위한 실행을 한번도 하지 않게 될 뿐, 작동하는 프로그램일 것이다.

 

A 이면 B 이다. 와 같은 명제에서 A가 거짓인 경우 전체 명제는 항상 참이고, B가 참이어도 전체 명제는 항상 참이된다.

 

+추가) 역 이 대우

[기존 명제]

p => q

[역]

q=>p

[이]

~p=>q

[대우]

~q=>~p

 

진리표 = p와 q가 각각 T와 F인 모든 경우에 대한 명제의 참거짓 표를 만드는 것.

 

 

2. 수학적 귀납법

p(1)이 참임을 증명하고, p(n) => p(n+1) 임을 증명하면, 전체가 참임을 증명하는 것

 

[당구공 Paradox]

당구공 색깔이 전부 같음을 논리적으로 증명하는 과정을 반박해야하는 역설.

n+1개의 당구공이 있을 때, 하나를 빼고 n개의 당구공의 색깔이 같다.

n+1개의 당구공에서 또 다른 하나를 빼고 n개의 당구공 색깔이 같다.

따라서 n+1개의 당구공 색이 같기 때문에 모든 당구공의 색이 같다.

 

위와 같은 논리인데, 반박을 위해 P(n)이 같지 않을 수 있다는 걸 반박하는 건 논리적 접근이 아니라는 것(!!!)

p(n) => p(n+1) 에서 p(n)이 참일 필요가 없기 때문이다.

즉 참일 때만 보면 되기 때문인데,

 

그렇다면 위 수학적 귀납법을 반박하기 위해서는 P(1)일 때를 반박해야한다는 것이다.

P(n+1) = P(2) 일 때, P(n) 은 P(1)이 되는데, 이 때 모든 당구공의 색이 같다는 논리가 성립이 안된다는 것으로 반박해야한다고 한다.

 

솔직히 충격적이었다. 직관과 논리의 괴리를 체험했달까.

 

[함수의 기능을 증명하는 과정]

int sum(int x)
{
	if(x<=0) return 0;
	return x + sum(x-1);
}

위 함수가 1부터 x까지의 합을 계산함을 증명하자.

 

쉬운 논리적 방법으로는

s(n) = n + s(n-1) 이라는 논리적 형태가 그대로 적용되었기 때문이라는 것을 이야기하는 것이고,

 

상세한 증명 방법은 명제를 정의하는 것부터 시작한다

1) 명제 정의 - sum(x)가 리턴하는 값은 1+2+ ... + x와 항상 같다.

2) 수학적 귀납법에 의거, "sum(1)이 리턴하는 값은 1이다" 가 참이고

"sum(x) => sum(x+1) 이다."를 증명하는 방법은, 해당 함수에서 sum(x-1)이 1+2+...+(x-1)을 리턴할 때,

sum(x)는 1+2+...+x를 리턴함을 증명하면 됨.

 

 

[버블 정렬의 증명]

그렇다면 버블 정렬을 증명하는 방법은 어떻게 될까?

배열 A[1], A[2], ... A[n]을 소팅하는 알고리즘의 정확성을 증명하려고 한다면, 증명이 가능한 명제는 다음과 같다.

"A[1] < A[2] < ... < A[n]"

 

이 명제를 증명하기 위해 버블정렬을 수행하는 방법에 대해 생각해봐야 할 것 같다.

버블 정렬은 인접한 두 수를 비교하여 앞의 수가 더 크면 뒤의 숫자와 자리를 바꾸고, 더는 바꿀 수 없을 때까지 진행한다.

 

A[1]<A[2] 이고, A[n]<A[n+1] 임을 증명하면 버블 정렬을 증명할 수 있는 것이라고 생각한다.

 

 

#2 실습 문제

1. 명제식 법칙

 

2. 생각해봐야했던 문제

1)

대우와 경우를 나누는 것 모두 사용해보았다.

"n이 3의 배수가 아니면, n^2이 3의 배수가 아니다"

 

3k+1

3k+2 인 경우를 각각 나눠보면

9k^2 +6k + 1

9k^2 +12k + 4

둘 다 3으로 묶으면 1이 남기 때문에 증명이 가능했다.

 

 

2)

n = 4k + 1 과, n = 4k + 3 으로 나누어서 계산하면 해결 가능하다.

 

3) 유리수가 된다는 것은 기약분수로 표현 가능하다는 것이다.

따라서 b/a로 두고 귀류법을 사용한다. 이때 a는 0이 아니고 a와 b는 서로소이다.

2a^2 = b^2

 

위 식이 성립해야 한다.

이는 2가 앞에 곱해져있는 b^2 은 짝수라는 뜻이다.

b = 2k로 가정하면  2a^2 = 4k^2 이 되고 2로 양 변을 나누면 a 또한 짝수가 된다.

a와 b 모두 짝수이면 서로소가 아니므로 모순이 발생한다.