서두르지 말고 쉬지 말자

Every nonempty set of nonnegative integers has a smallest element.모든 비어있지 않은 자연수의 집합은 최소 원소를 가진다.이 문장은 The Well Ordering Principle로 알려져 있다. 이 원리는 이산수학에서 중요한 증명규칙 중 하나를 제공한다.2.1 Well Ordering Proofs 우리는 이미 Well Ordering Pinciple을 당연하게 받아들었다. 예를 들여, $\sqrt 2$가 유리수임을 증영할 때 $\sqrt 2$를 양의 정수 m,n으로 이루어진 기약분수 m/n으로 가정했는데 ,어떻게 이런 가정이 항상 가능할까? 기약분수 꼴로 나타낼 수 없는 양의 정수 m,n으로 이루어진 분수 m/n를 가정하자. 이제 이에 해당하는 분수..

1.7. Proof by Cases 복잡한 증명을 여러 경우들로 나누고 따로 증명하는 것은 흔하고 유용한 증명 전략이다. 이 문제 예제는 인상깊어서 한번 다뤄 보겠다. 예제Every collection of 6 people includes a club of 3 people or a group of 3 strangers. 이라는 정리를 증명해 보자.두 사람이 만났다 만나지 않았다 둘 중 하나의 상태일수만 있는데, 그룹 안의 모든 사람이 서로 만났다면 우리는 이 그룹을 club이라고 하고, 그룹 안의 모든 사람이 서로 만나지 않았다면 이 그룹을 group of stranger라고 한다. 증명.x를 6명의 사람들 중 한명이라고 하자. 여기에는 두가지 경우가 있다.x를 제외한 5명의 사람들 중 최소한 3명은 x..

1. Propositions  명제(proposition)란 참 혹은 거짓인 문장을 말한다. 이때, 참과 거짓을 구별할 수 없거나 상황에 따라 참 거짓이 달라진다면 명제가 아니다.  컴퓨터 과학에서 프로그램과 시스템을 검증하기 위해서 우리는 명제의 참 거짓을 증명하는 법을 알아야 한다.2. Predicates  술어(predicate)란 하나 이상의 변수에 대해 참 또는 거짓을 취하는 명제다.  변수 값이 무엇인가에 따라 참 거짓이 달라지므로 다음과 같은 함수와 비슷한 표기법을 사용한다.P(n) ::= "n is a perfect square"우리는 4 is a perfect square is true, 5 is a perfect square is false 대신 P(4) is true, P(5) is ..

6.042J 과정을 완료하면, 학생들은 컴퓨터 과학에서 이산(비연속) 수학의 기본적인 방법들을 설명하고 적용할 수 있게 됩니다. 또한, 이 방법들을 알고리즘 설계 및 분석, 계산 가능성 이론, 소프트웨어 공학, 그리고 컴퓨터 시스템 분야의 후속 과목에서 활용할 수 있습니다.특히, 학생들은 다음과 같은 능력을 갖추게 됩니다:기본 데이터 타입 및 구조에 대한 수학적 추론:컴퓨터 알고리즘과 시스템에서 사용되는 수, 집합, 그래프, 트리 등의 기본 데이터 타입과 구조에 대해 수학적으로 추론하고, 엄밀한 정의와 결론을 그저 그럴듯한 것과 구분하며, 특히 귀납법을 이용한 기초 증명을 구성할 수 있다.계산 과정의 모델링 및 분석:해석적 및 조합적 방법을 사용하여 계산 과정을 모델링하고 분석할 수 있다.이산 확률의 원..