1. 프로그래밍 논리와 수학
프로그래밍을 위한 '논리학'의 기초를 학습한다.
논리의 종류
-
Hard Logic
-
Soft Logic
Soft Logic
맥주집 문제를 풀 때는 직관을 사용한 것
직관은 논리적인 느낌을 주는 것 = Soft Logic
직관은 나쁜게 아니다
-> 직관의 장점은 (익숙한 상황에서) 빠르다는 것이다.
직관의 단점은 정확하지 않다는 것 (가끔은 익숙한 상황에서도 틀림)
-> 강한 착각을 일으킨다는 것
이치 : 과정의 순서가 올바르게 연결
논리 : 이야기의 이치
일상생활에서는 Soft Logic 이 빠르기 때문에 유용하다
- 논리적으로 부정확한 표현을 사용하더라도 어떤 의미인지는 알고 있을 것이라고 생각하고 넘어간다.
프로그래밍은 Hard Logic을 사용
-
직관적인 논리로 프로그래밍을 하면, 프로그램이 동작을 안할 것이다.
-
프로그래밍 언어의 표현들은, 모두 논리학에서 나온 것
-
Soft Logic으로 알고리즘을 이해하려고 하면 안된다. 사용되는 수 많은 알고리즘을 이해하기 위해서는 Hard Logic이 필요
배중률 : True / False 무조건 중간이 없는 것
무조건 False는 아니다 -> True
모순율 : True와 False 는 동시에 성립하지 않는다.
증명
증명은 정확한 명제식으로 표현할 수 있는 것이라야 함
보통은 정확한 명제식까지 쓰지는 않으나 근본적으로는 명제식으로 바꿀 수 있음
증명에 대한 수 많은 오해가 p→q를 p↔q와 혼동하는 것에서 일어남
모든 당구공 색이 같다는 증명에서 잘못된 것은?
수학적 귀납법 : P(1) 이 참이고, P(n) → P(n+1) 이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
모든 자연수 n에 대해 당구공 n개가 들어있는 집합에서 그 집합에 포함된 당구공은 모두 색이 같다는 것을 증명함
P(1) : 당구공 1개가 들어있는 집합은 모두 색이 같음
P(n) → P(n+1) 을 증명하기 위해 P(n) 이 참이라고 가정
당구공 n+1 개가 들어있는 임의의 집합을 생각함
이 집합에서 하나를 빼면 당구공 n개가 있는 집합이 되므로 지금 상황에서 모든 당구공의 색이 같음
방금 뺀 원소를 다시 넣고, 다른 당구공을 빼면 역시 당구공 n개가 있는 집합이 되므로 지금 상황에서도 모든 당구공의 색이 같음
위의 두 상황에서 처음 뺀 당구공과 두번째로 뺀 당구공의 색이 같음을 알 수 있으므로 당구공 n+1 개가 들어있는 임의의 집합은 색이 같은 것 만을 포함함
대부분의 사람들이 P(n)이 참이라고 가정할 수 없다고 반론함
수학적 귀납법에서 필요한 것은 P(n) → P(n+1)이 참임을 보이는 것 뿐이므로 P(n)이 정말로 참일 필요는 없음
위 증명에서 실제로 잘못된 것은 다음 부분
위의 두 상황에서 처음 뺀 당구공과 두번째로 뺀 당구공의 색이 같음을 알 수 있으므로...
처음 뺀 당구공과 두 번째로 뺀 당구공의 색이 같다는 것은 공통 부분이 있다는 것인데, 실제로 n = 1인 경우, 즉 n+1 = 2인 경우 공통 부분이 없음
