1장 : 문제해결을 위한 기초지식

대우

A → B 는 !B → !A를 의미한다

• AND OR 배타적 OR
  A → B가 !A OR B와 동일,
  A XOR B가 !(A ↔ B)와 동일
  A → B가 B → A를 의미하지 않는다

• 드모르간의 법칙
  !(A AND B) = !A OR !B,
  !A AND !B = !(A OR B)
  ex) 계절은 여름인동시에 겨울일 수 없다
  계절은 여름이 아니거나 겨울이 아니다
  계절이 여름이 아니면서 동시에 겨울도 아닌 때는 '계절이 여름이 아니거나 겨울이 아닐때'이다

순열

N개의 항목이 있을 때 이를 N가지 구별되는 방법으로 배열 할 수 있다

n! = n X (n - 1) X (n - 2) X ... X 2 X 1

• 중복 항목이 존재하는 순열
  n개중에 r개 항목이 중복된다고 할 때, 중복 항목을 재배열 하는방법의 가지수는 r!이다
  n!은 r!개만큼의 순열을 중복으로 세는 셈이다
  서로 구별되는 순열의 수를 구하기 위해서는 n! / r!이다

조합

이항계수 $\begin{pmatrix}n\\m\\ \end{pmatrix}$ 는 n개 항목의 잡합에서 순서를 고려하지 않고 m개 항목을 선택하는 방법의 수

$\begin{pmatrix}n\\m\\ \end{pmatrix}$ = $\frac{n!}{m!(n - m)!}$

확률

P(사건) = $\frac{사건이 일어날 수 있는 방법의 수}{사건이 일어날 수 있는 모든 결과의 수}$

• 독립사건
  한 사건의 결과가 다른 사건의 결과에 영향을 미치지 않는 경우 두 사건은 독립사건이다
  두 독립사건이 모두 일어날 확률은 두 사건이 일어날 개별 확률을 서로 곱한 값이다
  

• 상호배타적 사건
  두 사건이 동시에 일어나는 것이 불가능한 경우
  상호배타적 사건 중 하나가 일어날 확률을 구해야한다면 개별 사건이 일어날 확률의 합을 구하면 된다
  ex) 주사위를 한번 굴렸을때 4와 홀수가 동시에 나올 확률?
  1/6 + 1/2 = 2/3

• 상호보완적 사건
  상호배타적인 두 사건이 일어날 수 있는 모든 결과를 망라하는 경우, 두 사건을 상호보완적이라고 한다
  상호보완적 사건들의 개별 확률을 모두 합하면 100%가 된다
  (이때, 독립사건은 더하면 안됨)