• 프로그래밍
  • 직관이 오류를 범하는 예시
  • 논리 연습
  • 역, 이, 대우
  • 진리표
  • 증명
    • 수학적 귀납법

프로그래밍

프로그래밍이 어려운 이유?

• 프로그래밍 언어 문법과 라이브러리 사용 언어에 대해서 잘 모른다면 당연히 프로그래밍을 이해할 수 없다. 하지만 이를 익히는 것은 시간 문제!
• 논리 (hard logic) 논리 구조를 정확하게 이해하고 문제를 풀면 동일한 혹은 비슷한 논리 구조의 문제를 만났을 때 쉽게 풀 수 있다. 하지만 문제를 풀 때 논리를 생각하지 않는다면 문제 풀이가 어려울 수 밖에 없다.

일상 생활에서 문제를 풀 때, 우리는 직관을 이용한다. 처음 접한 문제에 대해서는 논리적으로 생각하며 문제를 풀이했을 지라도 익숙한 상황이 계속되면서 ‘직관’을 사용하게 된다.

이는 장.단점이 명확한데, 직관은 익숙한 상황에서 빠르게 문제를 풀수 있지만 정확하지 않을 수 있다.

직관이 오류를 범하는 예시

"합격하려면 토플 500점 이상 혹은 토익 600점 이상 필요"
vs
"복권에 당첨되면 자동차 혹은 천 만원 지급"

여기서 혹은(or)는 같은 의미일까?

nope!!

전자의 경우 토플 토익 점수 둘 다 있어도 만족할 수 있지만 후자의 경우 자동차와 천 만원 모두 지급하는 것은 은행 측에서 의도한 의미가 아닐 것이다.

이는 inclusive or 과 exclusive or의 논리가 “혹은, 또는”이라는 말로 혼용되기 때문인데 이러한 논리를 따지지 않고 직감적으로 해석하고 넘어갈 여지가 많다.

inclusive vs or exclusive or Inclusive or: A or B or both. Exclusive or: Either A or B but not both.

A	B	OR	XOR
1	0	1	1
1	1	1	0
0	1	1	1
0	0	0	0

직관적으로 완전한 이해를 얻는 것은 사실상 불가능한 일이다. “증명”할 수 있어야하고 그러기 위해서는 hard logic적 이해가 필요하다.

논리 연습

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

이 지문은 참일까? 거짓일까? => 참

그 이유는 가정이 거짓이면 논리 전체로 봤을 때 이는 참이 된다. (아들에게 100점 맞으면 치킨 사준다고 했는데, 100점 못맞았어 그 다음에 오는 행동은 어떤 것이 되든 참이다.)

만약 19474912840이 Prime Number라면, 2는 짝수이다.

이 지문은 참일까? 거짓일까? => 참

조건과 상관없이 2는 짝수이기 때문에 참이다.

역, 이, 대우

명제 : 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다.
역 : 만약 미국에서 2080년 월드컵이 열리면, 0이 홀수이다.
이 : 만약 0이 홀수가 아니라면, 미국에서 2080년 월드컵이 열리지 않는다.
대우 : 만약 미국에서 2080년 월드컵이 열리지 않으면, 0이 홀수가 아니다.

진리표

다음 명제식의 진리표를 만들자.

p ⌃ (q -> ~p)

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

증명

증명이란 무엇인가? 글을 그냥 쓰는게 아니라 정확한 명제식으로 표현할 수 있는 것 = 명제식으로 바꿀 수 있는 것만 증명으로 허용함.

수학적 귀납법

자연수 n에 대한 명제 p(n)이 모든 자연수 n에 대해서 성립함을 증명하려면 다음 두 가지를 보이면 된다.

• n=1일 때, 명제 p(n)이 성립한다.
• n=k일 때, 명제 p(n)이 성립한다고 가정하면 n=k+1일 때, 명제 p(n)이 성립한다.

프로그로그래밍에서는 수학적 귀납법을 자주 적용하개 되기 때문에 일상에서 자주 접하지 않는 수학적 귀납법을 다루는 연습을 할 필요가 있다.

다음은 x까지의 합을 구하는 함수이다.

def sum(x):
  if x <= 0:
    return 0
  else:
    return x + sum(x-1)

이를 증명 가능한 명제로 표현 하면 다음과 같다. "sum(x)가 리턴하는 값은 1+2+...+x의 값과 항상 같다."

증명이 가능한 명제를 만들고 나면 수학적 귀납법을 적용할 수 있다. => 이를 작성하는 연습이 필요하다.

연습해볼만한 것 버블소트가 정확함을 어떻게 증명할 것인가 생각해보자.