[Computational Thinking] 논리와 증명

[Computational Thinking] 논리와 증명

논리

- Soft 로직

100점을 받으면 치킨을 사준다. (T)

참 > 100점을 못받아서 안사준다. (전제가 F)

참 > 100점을 못받았는데 사준다. (전제가 F) = 결과가 뭐든 전제가 F일 경우 문장은 참

거짓 > 100점을 받았는데 안사준다.

- Hard 로직

 1. 만약 0이 홀수라면 미국에서 2080년 월드컵이 열린다. (T) = 전제가 명확한 F이기 때문에 문장은 참

 2. 만약 123532423523423가 Prime Number라면 2는 짝수이다. (T) = 결과가 명확한 T이기 때문에 문장은 참

문제 1.

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

① ~p -> q    ② p∨q     ③ q -> p

[풀이]

p->q가 거짓이기 위해서는 p가 참이고 q가 거짓인 경우만 가능합니다.

문제 2.

① p ∧ (q -> ~p)

(∧ = and)

p	q	p ∧ (q -> ~p)
T	T	F
T	F	T
F	T	F
F	F	F

증명

- 증명은 정확한 명제식으로 표현할 수 있어야 합니다.

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

[EX] 당구공 Paradox 

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

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

- P(1) 은 참이다. = 공이 1개일 때 공이 모두 같다.

- P(n)->P(n+1) 증명하기 위해 P(n)이 참이라고 가정

- P(n) 에서 P(1) 을 더했을 때 참이다.

- 여기서 대부분의 사람들이 P(n)이 참이라고 가정할 수 없다고 반론합니다.

- P(n)->P(n+1)이 참임을 보이는 것 뿐이므로 P(n)이 정말 참일 필요 없습니다.

- 처음 뺀 당구공과 두번째 뺀 당구공이 같은 색이라는 것을 증명할 수 없습니다.

[EX]

- 소수의 갯수가 유한한 k개라고 가정

- 모든 소수를 다 곱하고 1을 더한 수를 n이라고 가정

- n은 어떤 소수로 나누어도 나머지가 1

- but, n은 어떤 소수보다도 크므로 합성수

- 합성수이지만 어떤 소수로도 나누어지지 않으므로 모순

- <반론> 몇 개의 소수가 더 존재하면 되는 것이 아니냐는 주장이 있습니다.

- 위 증명은 "소수가 k개 이면 모순 발생", 즉 소수가 k개 = 항상 거짓 이므로 이 명제가 항상 참.

수학적 귀납법

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

귀납법의 강한 형태 : P(1)이 참이고, P(1)∧P(2)∧P(3)∧...∧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+ .. + x의 값과 항상 같다."

귀납법 적용 >

P(1)이 참이다.

P(x) -> P(x+1)이 참이다. : sum(x-1)이 1+..+(x-1)을 리턴하면 sum(x)는 1+2+...+x를 리턴한다"를 증명하면 됩니다.

코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴함. sum(x-1)의 리턴 값은 1+2+..+(x-1)과 같다고 가정했으므로 sum(x)는 1+..+x=1+2+..+x를 리턴함을 확인할 수 있습니다.

꾸준한 연습이 필요!

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

=어떤 일이 일어나는지 생각하는 것 보다 어떤 값을 리턴하는지 약속하고 지켜진다고 가정한 후 x를 적용

버블 소트의 증명 >

High-level 증명에서는 Sorting 된다는 것을 직관적인 수준에서 설명하는 경우 많은데 상세한 증명을 위해서는 증명이 가능한 명제가 필요합니다.

배열 A[1],A[2],...,A[n]을 소팅하는 알고리즘의 정확성을 증명하려고 한다면, 증명이 가능한 명제는 다음과 같습니다. (소팅이 되어있다 라는 두루뭉실한 말 말고)

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

버블 소트가 정확함을 어떻게 증명할지 생각해 봅시다.

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

[출처] SWEA Computational Thinking 강의