강의수강) 기초 논리 & 수학

1. 논리와 증명

카드 와 맥주) 과자와 버스) 토플과 복권) inclusive or / exclusive or

논리구조를 정확히 이해하고 문제를 푸는가?

• 직관은 논리적인 느낌을 주는 것 : 일상생활에서 직관을 이용해서 문제를 풀고 있다. (익숙한 상황에서 매우 빠름 / 강한 착각을 일으킬 가능성 있음)
• 일상생활에서는 soft logic이 유용하나 프로그래밍은 hard logic을 사용한다.
• soft logic으로 알고리즘을 이해하려고 하는 오류 -> 증명을 봐도 이해하기 어려울 수 있다.

컴퓨터 알고리즘은 수학적 귀납법 증명이 주로 사용된다.

• 기본형: P(1)이 참이고,  P(n) - <P(n+1)이 참이면 P(n)은 모든 자연수 n에 대하여 참이다.
• 강한형태: P(1)이 참이고, P(1) ^ P(2) ^ ... ^ 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의 값과 항상 같다"

->  수학적 귀납법

1. P(1)이 참이다: "sum(1)이 리턴하는 값은 1이다"를 증명하면 됨.
2. 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-1)+x = 1+2+...+x를 리턴함을 확인할 수 있음.
• sum(x-1)을 블랙박스로 보는 것이 이해에 도움을 줄 때가 있음 -> 재귀

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

• 버블 소트된 배열 A[1],A[2],...,A[n],의 값이 A[1] < A[2] < ...< A[n] 이다.

,,