이산수학 정의·정리

변수를 포함하고, 변수에 값을 넣으면 명제가 되는 문장을 술어(predicate)라 합니다. 변수가 가질 수 있는 값의 모임을 영역(정의역)이라 합니다.

$\forall x\, P(x)$는 “영역의 모든 $x$에 대해 $P(x)$가 참”이라는 명제입니다. “모든 $x$에 대해”라고 읽습니다.

$\exists x\, P(x)$는 “영역에 $P(x)$를 참으로 만드는 $x$가 적어도 하나 있다”는 명제입니다. “어떤 $x$가 있어”라고 읽습니다.

$\exists y\, \forall x\, Q(x, y)$이면 $\forall x\, \exists y\, Q(x, y)$입니다. 거꾸로는 일반적으로 성립하지 않습니다.

정수 $n$이 어떤 정수 $k$에 대해 $n = 2k$이면 짝수, $n = 2k + 1$이면 홀수입니다.

정수 $a \ne 0$, $b$에 대해 $b = ak$인 정수 $k$가 있으면 “$a$가 $b$를 나눈다”고 하고 $a \mid b$로 씁니다.

두 홀수의 곱은 홀수입니다.

$a \mid b$이고 $b \mid c$이면 $a \mid c$입니다.

$n^2$이 짝수이면 $n$은 짝수입니다.

$\sqrt{2}$는 무리수입니다.

소수는 무한히 많습니다.

모든 정수 $n$에 대해 $n^2 + n$은 짝수입니다.

정수 $n$에 대해, $n$이 짝수일 필요충분조건은 $n^2$이 짝수인 것입니다.

잘 정의된 대상들의 모임을 집합(set), 그 대상을 원소(element)라 합니다. $x$가 $A$의 원소이면 $x \in A$, 아니면 $x \notin A$로 씁니다.

$A$의 모든 원소가 $B$의 원소이면 $A \subseteq B$라 씁니다. 기호로는 $\forall x\, (x \in A \to x \in B)$입니다.

$A \subseteq B$이고 $B \subseteq A$이면 $A = B$입니다.

두 집합이 같음을 보이는 표준 방법은 이 정의 그대로 양쪽 포함을 따로 보이는 것입니다. 또 공집합은 모든 집합의 부분집합입니다: $x \in \varnothing$인 $x$가 없으므로 조건문 $x \in \varnothing \to x \in A$는 항상 참입니다.

집합 $A, B, C$에 대해

• 교환: $A \cup B = B \cup A$, $A \cap B = B \cap A$
• 결합: $(A \cup B) \cup C = A \cup (B \cup C)$, 교집합도 같음
• 분배: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• 드모르간: $(A \cup B)^c = A^c \cap B^c$, $(A \cap B)^c = A^c \cup B^c$
• 차집합: $A \setminus B = A \cap B^c$

$A$의 부분집합 전체의 집합을 멱집합(power set) $\mathcal{P}(A)$라 합니다.

원소가 $n$개인 집합의 멱집합은 원소가 $2^n$개입니다.

$A \times B = \{(a, b) \mid a \in A,\ b \in B\}$. 원소 $(a, b)$를 순서쌍(ordered pair)이라 하며, 순서가 중요하므로 $(1, 2) \ne (2, 1)$입니다. 예를 들어 $\{1, 2\} \times \{x, y\} = \{(1, x), (1, y), (2, x), (2, y)\}$입니다.

$|A \cup B| = |A| + |B| - |A \cap B|$.

집합 $A$의 각 원소에 집합 $B$의 원소를 정확히 하나씩 대응시키는 규칙 $f$를 $A$에서 $B$로의 함수(function)라 하고 $f : A \to B$로 씁니다. $A$를 정의역(domain), $B$를 공역(codomain), $f(A) = \{f(a) \mid a \in A\}$를 치역(range)이라 합니다.

$|A| = m$, $|B| = n$이면 $A$에서 $B$로의 함수는 $n^m$개입니다.

함수 $f : A \to B$가

• 단사(일대일): $f(a_1) = f(a_2)$이면 $a_1 = a_2$.
• 전사(위로): 모든 $b \in B$에 대해 $f(a) = b$인 $a$가 있다. 곧 치역 = 공역.
• 전단사(bijective): 단사이면서 전사.

유한집합 $A$, $B$에 대해 단사 $f : A \to B$가 있으면 $|A| \le |B|$, 전사가 있으면 $|A| \ge |B|$, 전단사가 있으면 $|A| = |B|$입니다.

$f : A \to B$, $g : B \to C$의 합성(composition) $g \circ f : A \to C$는 $(g \circ f)(a) = g(f(a))$입니다.

$f : A \to B$가 전단사이면 $f^{-1} \circ f = \mathrm{id}_A$, $f \circ f^{-1} = \mathrm{id}_B$인 역함수(inverse function) $f^{-1} : B \to A$가 하나 있습니다. 거꾸로 역함수가 있으면 $f$는 전단사입니다.

집합 $A$ 위의 관계(relation) $R$은 $A \times A$의 부분집합입니다. $(a, b) \in R$이면 $a\, R\, b$로 씁니다.

$A$ 위의 관계 $R$이

• 반사적(reflexive): 모든 $a$에 대해 $a\, R\, a$.
• 대칭적(symmetric): $a\, R\, b$이면 $b\, R\, a$.
• 반대칭적(antisymmetric): $a\, R\, b$이고 $b\, R\, a$이면 $a = b$.
• 추이적(transitive): $a\, R\, b$이고 $b\, R\, c$이면 $a\, R\, c$.

반사적·대칭적·추이적인 관계를 동치관계(equivalence relation)라 합니다. $a$와 동치인 원소의 집합 $[a] = \{x \mid x\, R\, a\}$를 $a$의 동치류(equivalence class)라 합니다.

동치관계의 동치류들은 서로소이고 합하면 전체가 됩니다. 곧 집합의 분할(partition)을 이룹니다. 거꾸로 분할이 주어지면 “같은 조각에 있다”는 동치관계가 됩니다.

반사적·반대칭적·추이적인 관계를 부분순서(partial order)라 합니다. 임의의 두 원소가 비교 가능하면($a\, R\, b$ 또는 $b\, R\, a$) 전순서(total order)입니다.

자연수에 대한 명제 $P(n)$에 대해

1. (기초 단계) $P(n_0)$이 참이고
2. (귀납 단계) 모든 $k \ge n_0$에 대해 $P(k) \to P(k+1)$이 참이면

모든 $n \ge 1$에 대해 $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

$1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$.

$r \ne 1$이면 $1 + r + \cdots + r^n = \dfrac{r^{n+1} - 1}{r - 1}$.

$n \ge 4$이면 $2^n < n!$.

모든 $n \ge 0$에 대해 $3 \mid n^3 + 2n$.

$P(n_0)$이 참이고, 모든 $k \ge n_0$에 대해 “$P(n_0) \land \cdots \land P(k)$이면 $P(k+1)$”이면, $n \ge n_0$인 모든 $n$에서 $P(n)$이 참입니다.

2 이상의 모든 정수는 소수들의 곱으로 쓸 수 있습니다.

$F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$ ($n \ge 2$).

$F_1 + F_2 + \cdots + F_n = F_{n+2} - 1$.

$F_n < 2^n$ ($n \ge 0$).

공집합이 아닌 자연수의 집합에는 가장 작은 원소가 있습니다.

정렬 원리는 귀납법과 동치이고, “가장 작은 반례”를 잡아 모순을 끌어내는 증명에 씁니다. 예를 들어 정리 6.8은 “소수의 곱으로 쓸 수 없는 가장 작은 수 $m$”을 잡으면, $m$이 소수가 아니므로 $m = ab$이고 $a, b < m$은 소수의 곱이 되어 모순이라고 증명할 수도 있습니다.

서로 겹치지 않는 두 경우 $A$, $B$가 각각 $m$, $n$가지이면 “$A$ 또는 $B$”는 $m + n$가지입니다. 집합으로는 서로소인 $A$, $B$에 대해 $|A \cup B| = |A| + |B|$입니다.

첫 단계가 $m$가지이고, 각 경우마다 둘째 단계가 $n$가지이면 두 단계를 차례로 하는 방법은 $mn$가지입니다. 집합으로는 $|A \times B| = |A||B|$입니다.

서로 다른 $n$개에서 $r$개를 골라 순서 있게 늘어놓는 것을 $r$-순열이라 하고 그 수를 $P(n, r)$로 씁니다.

$P(n, r) = n(n-1)\cdots(n-r+1) = \dfrac{n!}{(n-r)!}$. 특히 $n$개를 모두 늘어놓는 방법은 $n!$가지입니다.

서로 다른 $n$개에서 순서 없이 $r$개를 고르는 것을 $r$-조합이라 하고 그 수를 $\binom{n}{r}$ 또는 $C(n, r)$로 씁니다.

$\dbinom{n}{r} = \dfrac{n!}{r!\,(n-r)!}$.

$\binom{n}{r} = \binom{n}{n-r}$. $r$개를 고르는 것은 남길 $n - r$개를 고르는 것과 같습니다.

$\dbinom{n}{r} = \dbinom{n-1}{r-1} + \dbinom{n-1}{r}$ ($1 \le r \le n - 1$).

$(x + y)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$.

$\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n$, $\displaystyle\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$ ($n \ge 1$).

$n$종류에서 중복을 허용해 $r$개를 고르는(순서 없이) 방법은 $\binom{n + r - 1}{r}$가지입니다. 같은 말로, $x_1 + \cdots + x_n = r$의 음이 아닌 정수해는 $\binom{n + r - 1}{n - 1}$개입니다.

$n$개 가운데 같은 것이 $n_1, n_2, \dots, n_k$개씩 있으면, 늘어놓는 방법은 $\dfrac{n!}{n_1!\, n_2! \cdots n_k!}$가지입니다.

$n + 1$마리 이상의 비둘기가 $n$개의 집에 들어가면, 두 마리 이상이 들어간 집이 있습니다.

$N$마리가 $k$개의 집에 들어가면, 적어도 $\lceil N/k \rceil$마리가 들어간 집이 있습니다.

$1, 2, \dots, n$을 늘어놓을 때 어느 $i$도 $i$번째 자리에 오지 않는 순열을 교란순열(derangement)이라 하고 그 수를 $D_n$으로 씁니다.

$D_n = n! \displaystyle\sum_{k=0}^{n} \frac{(-1)^k}{k!}$.

$|A| = m$, $|B| = n$일 때 전사함수 $A \to B$의 수는

수열 $a_n$의 항을 앞의 항들로 나타낸 식을 점화식(recurrence relation)이라 하고, 수열을 정하는 데 필요한 처음 몇 항을 초기조건(initial condition)이라 합니다.

상수 $c_1, \dots, c_k$($c_k \ne 0$)에 대해 $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$ 꼴을 $k$계 선형 동차 점화식이라 합니다.

2계 점화식 $a_n = c_1 a_{n-1} + c_2 a_{n-2}$의 특성방정식 $r^2 - c_1 r - c_2 = 0$이 서로 다른 두 근 $r_1$, $r_2$를 가지면, 모든 해는

특성방정식이 중근 $r_0$을 가지면 모든 해는 $a_n = (\alpha + \beta n) r_0^n$ 꼴입니다.

정수 $a$와 양의 정수 $d$에 대해 $a = dq + r$, $0 \le r < d$인 정수 $q$, $r$이 유일하게 있습니다. $q$를 몫(quotient), $r$을 나머지(remainder)라 하고 $r = a \bmod d$로 씁니다.

정수 $a$, $b$(둘 다 0은 아님)를 모두 나누는 가장 큰 양의 정수를 최대공약수(greatest common divisor, gcd) $\gcd(a, b)$라 합니다. $\gcd(a, b) = 1$이면 $a$와 $b$는 서로소(coprime)입니다.

$a = bq + r$이면 $\gcd(a, b) = \gcd(b, r)$.

정수 $a$, $b$에 대해 $\gcd(a, b) = ax + by$인 정수 $x$, $y$가 있습니다.

$a$와 $b$가 서로소이면 $ax + by = 1$인 정수 $x$, $y$가 있습니다.

$m \mid a - b$이면 “$a$와 $b$는 $m$을 법으로 합동”이라 하고 $a \equiv b \pmod m$으로 씁니다. 같은 말로 $a \bmod m = b \bmod m$입니다.

$a \equiv b$, $c \equiv d \pmod m$이면 $a + c \equiv b + d$, $ac \equiv bd \pmod m$입니다.

$a\bar a \equiv 1 \pmod m$인 $\bar a$를 $a$의 $m$에 대한 역원(inverse)이라 합니다.

$a$의 $m$에 대한 역원은 $\gcd(a, m) = 1$일 때 그리고 그때만 있습니다.

$p$가 소수이고 $p \nmid a$이면 $a^{p-1} \equiv 1 \pmod p$.

그래프 $G = (V, E)$는 꼭짓점의 집합 $V$와 변의 집합 $E$로 이루어지고, 각 변은 두 꼭짓점을 잇습니다. 이 강에서는 따로 말하지 않으면 단순 그래프(방향이 없고, 자기 자신으로 가는 변과 겹친 변이 없는 그래프)를 다룹니다.

꼭짓점 $v$에 붙은 변의 수를 $v$의 차수(degree) $\deg v$라 합니다.

• 완전그래프 $K_n$: 꼭짓점 $n$개, 모든 두 꼭짓점이 인접. 변은 $\binom{n}{2}$개.
• 순환그래프 $C_n$: 꼭짓점이 원을 이루는 $n$개의 변.
• 완전이분그래프 $K_{m,n}$: $m$개와 $n$개의 두 무리, 서로 다른 무리끼리만 모두 인접. 변은 $mn$개.

$\displaystyle\sum_{v \in V} \deg v = 2|E|$.

차수가 홀수인 꼭짓점은 짝수 개입니다.

꼭짓점 $v_0, v_1, \dots, v_k$가 차례로 인접할 때 이를 길이 $k$인 보행(walk)이라 합니다. 꼭짓점이 겹치지 않으면 경로(path), 처음과 끝이 같고 그 밖에 겹치지 않으면 회로(사이클)입니다.

임의의 두 꼭짓점 사이에 경로가 있으면 그래프가 연결되어 있다고 합니다. “경로로 이어짐”은 동치관계이고, 그 동치류를 연결 성분(connected component)이라 합니다.

모든 변을 정확히 한 번씩 지나는 회로를 오일러 회로(Eulerian circuit), 처음과 끝이 달라도 되면 오일러 경로라 합니다.

연결된 그래프에 오일러 회로가 있을 필요충분조건은 모든 꼭짓점의 차수가 짝수인 것입니다. 오일러 경로(회로가 아닌)가 있을 필요충분조건은 홀수 차수 꼭짓점이 정확히 2개인 것입니다.

꼭짓점을 두 무리로 나눠, 모든 변이 서로 다른 무리를 잇게 할 수 있으면 이분 그래프(bipartite graph)입니다.

그래프가 이분 그래프일 필요충분조건은 길이가 홀수인 회로가 없는 것입니다.

꼭짓점이 $v_1, \dots, v_n$인 그래프의 인접행렬(adjacency matrix) $A$는 $v_i$와 $v_j$가 인접하면 $A_{ij} = 1$, 아니면 0인 $n \times n$ 행렬입니다. 방향 없는 그래프에서 $A$는 대칭입니다.

$(A^k)_{ij}$는 $v_i$에서 $v_j$로 가는 길이 $k$인 보행의 수입니다.

변이 서로 교차하지 않게 평면에 그릴 수 있는 그래프를 평면 그래프(planar graph)라 합니다. 그렇게 그렸을 때 평면이 나뉘는 영역을 면이라 합니다(바깥 영역 포함).

연결된 평면 그래프의 꼭짓점 수 $v$, 변 수 $e$, 면 수 $f$는 $v - e + f = 2$를 만족합니다.

회로가 없는 연결 그래프를 트리(tree)라 합니다. 회로가 없는(연결되지 않아도 되는) 그래프를 숲(forest)이라 합니다. 트리에서 차수가 1인 꼭짓점을 잎(leaf)이라 합니다.

꼭짓점이 2개 이상인 트리에는 잎이 적어도 2개 있습니다.

꼭짓점이 $n$개인 그래프 $G$에 대해 다음은 모두 동치입니다.

1. $G$는 트리입니다(연결, 회로 없음).
2. 임의의 두 꼭짓점 사이에 경로가 정확히 하나 있습니다.
3. $G$는 연결이고 변이 $n - 1$개입니다.
4. $G$는 회로가 없고 변이 $n - 1$개입니다.
5. $G$는 연결이지만, 어떤 변을 지워도 연결이 끊깁니다.

성분이 $c$개인 숲은 변이 $n - c$개입니다.

꼭짓점 하나를 뿌리로 정한 트리를 뿌리 트리(rooted tree)라 합니다. 뿌리에서 $v$로 가는 경로에서 $v$ 바로 앞의 꼭짓점이 $v$의 부모, $v$가 부모인 꼭짓점이 $v$의 자식입니다. 뿌리에서 가장 먼 꼭짓점까지의 거리를 높이라 합니다.

모든 꼭짓점의 자식이 2개 이하인 뿌리 트리를 이진 트리(binary tree), 잎이 아닌 모든 꼭짓점의 자식이 정확히 2개인 것을 완전 이진 트리(full)라 합니다.

높이 $h$인 이진 트리의 잎은 $2^h$개 이하입니다. 그러므로 잎이 $\ell$개이면 높이는 $\lceil \log_2 \ell \rceil$ 이상입니다.

내부 꼭짓점이 $i$개인 완전 이진 트리는 잎이 $i + 1$개, 꼭짓점이 $2i + 1$개입니다.

연결 그래프 $G$의 모든 꼭짓점을 포함하는 부분그래프 가운데 트리인 것을 신장 트리(spanning tree)라 합니다.

모든 연결 그래프에는 신장 트리가 있습니다.

변을 비용이 작은 것부터 보며, 이미 고른 변들과 회로를 만들지 않으면 고릅니다. $n - 1$개를 고르면 멈춥니다. 이렇게 얻은 트리는 최소 신장 트리입니다.

꼭짓점에 $1, \dots, n$의 이름이 붙은 트리는 $n^{n-2}$개입니다. 곧 $K_n$의 신장 트리는 $n^{n-2}$개입니다.

실험에서 나올 수 있는 모든 결과의 집합을 표본공간(sample space) $S$, 그 부분집합을 사건(event)이라 합니다.

표본공간의 각 결과 $s$에 $0 \le p(s) \le 1$, $\sum_{s \in S} p(s) = 1$인 수를 정한 것을 확률분포(probability distribution)라 하고, 사건 $E$의 확률을 $P(E) = \sum_{s \in E} p(s)$로 정합니다.

$P(E^c) = 1 - P(E)$, $P(E \cup F) = P(E) + P(F) - P(E \cap F)$.

$P(F) > 0$일 때 $P(E \mid F) = \dfrac{P(E \cap F)}{P(F)}$를 “$F$가 일어났을 때 $E$의 확률”이라 합니다.

$P(E \cap F) = P(E)P(F)$이면 $E$와 $F$는 독립(independent)입니다. $P(F) > 0$이면 $P(E \mid F) = P(E)$와 같습니다.

$F_1, \dots, F_n$이 표본공간을 나누면 $P(E) = \sum_i P(E \mid F_i)P(F_i)$.

$P(F \mid E) = \dfrac{P(E \mid F)P(F)}{P(E \mid F)P(F) + P(E \mid F^c)P(F^c)}$.

표본공간에서 실수로 가는 함수 $X : S \to \mathbb{R}$를 확률변수(random variable)라 합니다.

$E[X] = \sum_{s \in S} p(s) X(s) = \sum_x x \cdot P(X = x)$.

확률변수 $X$, $Y$와 상수 $a$, $b$에 대해 $E[aX + bY] = aE[X] + bE[Y]$. $X$와 $Y$가 독립이 아니어도 성립합니다.

$V(X) = E[(X - E[X])^2] = E[X^2] - E[X]^2$. 표준편차는 $\sqrt{V(X)}$입니다.

$X$와 $Y$가 독립이면 $V(X + Y) = V(X) + V(Y)$. 또 $V(aX + b) = a^2 V(X)$.