프로그래밍과 논리/수학

1. 논리와 증명

- Hard vs. Soft Logic

- 카드 문제

• 사실: 모든 카드의 한쪽에는 알파벳, 다른 쪽에는 숫자
• 주장: 만약에 한쪽이 D이면 반대쪽은 3
• 문제: 주장이 사실인지 확인하기 위해 아래 카드 중 반드시 뒤집어 봐야 하는 카드는 몇 개이고 어느 것인가?

D, F, 3, 7

 

답은... 2개 D, 7

 

 

F 뒤에 3이어도 주장과 상관 없음

3 뒤에 D가 아니어도 주장과 상관 없음

7 뒤에 D가 있으면 주장과 다르다.

 

- 맥주집 문제

• 규칙: 20세 이하인 사람은 맥주를 마실 수 없음
• 문제: 나이 혹은 마시고 있는 것을 표시한 다음 4명 중 확인이 필요한 사람은 몇명이고 누구인가?

17세, 31세, 콜라, 맥주

 

답은... 17세, 맥주

 

- 맥주집 문제가 카드문제보다 쉽다.

- 논리 구조를 정확히 이해하고 맥주집 문제를 푸는 사람은 카드 문제를 똑같이 풀 수 있다.

- 맥주집 문제를 풀 때는 직관을 사용한 것

- 직관은 논리적인 느낌을 주는 것

- 직관의 장점은 익숙한 상황에서 빠르다는 것

- 직관의 단점은 정확하지 않다는 것. 가끔은 익숙한 상황에서도 틀림

- 또 다른 단점은 강한 착각을 일으킨다는 것

 

- 과자와 버스

• 과자 몇개 먹었니? vs. 버스 타려고 하는데 천원 있니?

- 두 질문은 같은 표현을 사용하지만, 하나는 정확한 개수를 요구하고, 다른 하나는 천원 이상이 있는지 물어보는 것

 

- 토플과 복권

• 합격하려면 토플 500점 이상 혹은 토익 600점 이상 필요 vs. 복권에 당첨되면 자동차 혹은 천만원을 준다.

- 두 말은 같은 표현을 사용하지만, 하나는 inclusive or. 다른 하나는 exclusive or

 

- 일상생활에서는 soft logic, 프로그래밍은 hard logic

- 명제의 q(결론)가 항상 참이면 명제는 참이다.(Trivial Proof)

 

- 당구공 Paradox

- 수학적 귀납법: 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=1인 경우, n+1=2인 경우 공통 부분이 없다.

- 쉽게 말해 당구공이 2개인 경우 하나를 빼면 나머지 하나만 남아서 남은 당구공의 색이 전부 같다고 여겨지고,

다른 하나를 빼면 마찬가지로 나머지 하나만 남아서 남은 당구공의 색이 전부 같다고 여겨진다.

그러나 처음 뺀 당구공과 나중에 뺀 당구공의 공통부분을 증명할 수가 없다.

 

- 수학적 귀납법

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

- 수학적 귀납법의 강한 형태: P(1)이 참이고, P(1)^P(2)^...^P(n) -> P(n+1)이 참이면 P(n)은 모둔 자연수 n에 대해서 참이다.

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

 

- 중요!!!

- 상세한 증명에 대한 경험이 없는 경우가 많고, 상세한 증명없이는 확인하거나 이해할 수 없는 문제들이 많다.

- 많은 연습이 필요

 

 

출처: https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

SW Expert Academy