유키히로시 지음 | 안동현 옮김 | 프리렉
$a_{3} \times N^3 + a_{2} \times N^2 + a_{1} \times N^1 + a_{0} \times N^0$
$10^0 ?$
$10^-1 ?$
$N^a \times N^b = N^{a+b}$
$a_{n} \times \ m^n + a_{n-1} \times m^{n-1} + a_{n-2} \times m^{n-2} + \ldots + a_{2} \times m^2 + a_{1} \times m^1 + a_{0} \times m^0$
애매함을 없애는 도구; 망라(網羅)적이고 배타적인 분할
명제; 참, 거짓
누락은 없는가, 중복은 없는가
부정; A가 아님
~A (Not A), ~~A == A
Venn Diagram, 진리표
논리곱; A 이고 B
$A \wedge B (A and B)$
논리합; A 또는 B
$A \vee B (A or B)$
배타적 논리합; A 또는 B (그러나 둘 다는 아님)
$A \oplus B$
등치; A와 B는 같다
A = B
배타적 논리합의 부정 ; $(\sim(A \oplus B)) = (A = B)$
조건 명제; A라면 B A⇒B
$(\sim{A})\vee(\sim{B})=\sim(A\wedge{B})$
$(\sim{A})\wedge(\sim{B})=\sim(A\vee{B})$
쌍대성
true↔false
A↔~A
$\wedge \leftrightarrow \vee$
(!A) || (!B) = ! (A && B)
(!A) && (!B) = ! (A || B)
나머지는 그룹 나누기. 패리티Parity; 통신에서 에러를 확인할 때 사용하는 중요한 개념
나머지의 주기성
'한붓 그리기 성공' ⇒ '모든 정점은 짝수점 또는 홀수점이 2개'
Mathematical Induction, 정수에 관한 주장을 0 이상의 모든 정수(0,1,2,3,…)에 대해 증명할 때 이용하는 방법, 2단계로 증명을 수행
단계1(기저Base), 'P(0)이 성립함'을 증명한다.
단계2(귀납Induction), 0 이상의 어떤 정수 k를 선택해도 'P(k)가 성립한다면 P(k+1)도 성립함'을 증명한다.
$0 + 1 + 2 + 3 + \dots + n = \frac{(n + 1)\times{n}}{2}$
$|A\cup{B}|=|A|+|B|$
포함과 배제의 원리; The Principle of Inclusion and Exclusion
$|A\cup{B}|=|A|+|B|-|A\cap{B}|$
$|A\times{B}|=|A|\times|B|$
$_{n}P_{k}=\frac{n!}{(n-k)!}$
수형도Tree Diagram
$_{n}C_{k}=\frac{n!}{(n-k)!k!}$
$_{n}C_{k}=\frac{_{n}P_{k}}{_{k}P_{k}}=\frac{(n-0)\times(n-1)\times(n-2)\times\dots\times(n-(k-1))}{(k-0)\times(k-1)\times(k-2)\times\dots\times(k-(k-1))}$
닫힌식Closed-form Expression 또는 일반항 $H(n)=2^n-1$
[재귀를 사용한 표현] 'n 하노이'를 'n-1 하노이'를 이용하여 푸는 순서를 발견해낸다. [점화식] 'n 하노이'의 횟수를 'n-1 하노이'의 횟수를 이용하여 표현한다.
재귀Recursion와 귀납Induction은 모두 “큰 문제를 같은 형태의 작은 문제로 만든다.”
재귀적Recursive, 귀납적Inductive
0,1,1,2,3,5,8,13,21,34,55,89,…
시어핀스키 개스킨(Sierpinski Gasket, Sierpinski Triangle)
프랙털 도형
Exponential Explosion; 수가 급격하게 증가하는 것. 지수적 증가, 지수함수적 증가, 조합론적 폭발
무작위 공격(Brute-force Attack)
소수Prime Number; 1과 자기 자신의 수만으로 나누어떨어지는 2 이상의 수
페르마의 마지막정리; $x^n+y^n=z^n$
골드바흐의 추측Goldbach's conjecture; 4 이상의 모든 짝수는 소수2개의 합으로 나타낼 수 있다