이산수학 (Discrete Mathematics)

이산수학은 연속적이지 않은 이산적(Discrete) 구조를 다루는 수학 분야입니다. 컴퓨터 과학의 수학적 기초로서 매우 중요하며, 알고리즘 분석, 데이터 구조, 암호학, 인공지능 등 거의 모든 컴퓨터 과학 분야에서 필수적으로 사용됩니다.

이산수학이란?

연속 vs 이산의 차이

"이산(離散)"이라는 단어는 "떨어져 있다"는 뜻입니다. 이산수학은 하나하나 셀 수 있는, 띄엄띄엄 떨어진 값을 다루는 수학입니다. 반대로 미적분학이 다루는 실수는 연속적으로 이어져 있습니다.

수학적으로 정리하면 다음과 같습니다.

컴퓨터는 본질적으로 이산적인 기계입니다. 0과 1, 즉 비트(bit)로 모든 것을 표현하기 때문입니다. 따라서 컴퓨터 과학을 공부하려면 이산수학이 반드시 필요합니다.

이런 곳에 쓰여요

선수 지식: 논리학, 집합론

난이도: ★★★☆☆ (고등학교 심화)

집합과 관계

관계(Relation)는 두 집합의 카르테시안 곱의 부분집합입니다. 집합 $A$에서 $B$로의 관계 $R$은 $R \subseteq A \times B$입니다.

관계의 성질 - 실생활로 이해하기

집합 $A$ 위의 관계 $R \subseteq A \times A$에 대하여:

관계 행렬

유한 집합 $A = \{a_1, a_2, \ldots, a_n\}$ 위의 관계 $R$은 관계 행렬(Relation Matrix) $M_R$로 표현할 수 있습니다. $M_R$의 $(i, j)$ 성분은:

예시: $A = \{1, 2, 3\}$ 위의 관계 $R = \{(1,1), (1,2), (2,3), (3,1)\}$의 관계 행렬:

관계의 합성: 관계 $R_1$과 $R_2$의 합성 $R_1 \circ R_2$의 행렬은 부울 행렬 곱으로 구합니다:

여기서 $\odot$는 부울 행렬 곱(AND를 곱으로, OR를 합으로 사용)입니다.

관계 그래프 (방향 그래프)

관계 $R$은 방향 그래프(Directed Graph)로 시각화할 수 있습니다. 집합의 각 원소를 정점(vertex)으로, 순서쌍 $(a, b) \in R$을 $a$에서 $b$로의 방향 간선(directed edge)으로 나타냅니다.

동치 관계와 동치류

반사적이고 대칭적이고 추이적인 관계를 동치 관계(Equivalence Relation)라 하며, 기호 $\sim$으로 나타냅니다. 동치 관계는 집합을 서로소인 동치류(Equivalence Class)로 분할합니다.

원소 $a$의 동치류:

예시: 정수 집합 $\mathbb{Z}$ 위에서 "법 3에 대한 합동(congruence modulo 3)" 관계:

이 관계는 동치 관계이며, 세 개의 동치류를 만듭니다:

• $[0] = \{\ldots, -6, -3, 0, 3, 6, 9, \ldots\}$ — 3으로 나누어 나머지가 0인 수
• $[1] = \{\ldots, -5, -2, 1, 4, 7, 10, \ldots\}$ — 3으로 나누어 나머지가 1인 수
• $[2] = \{\ldots, -4, -1, 2, 5, 8, 11, \ldots\}$ — 3으로 나누어 나머지가 2인 수

모든 정수는 이 세 그룹 중 정확히 하나에 속합니다. 이것이 "분할"입니다.

순서 관계 (부분순서)

반사적이고 반대칭적이고 추이적인 관계를 부분 순서(Partial Order)라 하며, $(A, \preceq)$를 부분 순서 집합(Poset)이라 합니다.

전순서 vs 부분 순서:

• 전순서(Total Order): 모든 두 원소가 비교 가능 ($\forall a, b \in A$, $a \preceq b$ 또는 $b \preceq a$). 예: $(\mathbb{R}, \leq)$
• 부분 순서: 일부 원소가 비교 불가능할 수 있음. 예: $(\mathcal{P}(S), \subseteq)$

하세 다이어그램

하세 다이어그램(Hasse Diagram)은 부분 순서 집합을 간결하게 시각화하는 방법입니다. 반사적 간선과 추이적 간선을 생략하고, 아래에서 위로 순서가 커지도록 배치합니다.

하세 다이어그램을 그리는 규칙은 간단합니다.

1. 작은 원소를 아래쪽에, 큰 원소를 위쪽에 배치합니다.
2. "바로 위" 관계만 선으로 연결합니다 (중간에 다른 원소를 거쳐 갈 수 있으면 생략합니다).
3. 자기 자신으로의 화살표(반사적 간선)는 그리지 않습니다.
4. 화살표 방향은 "아래에서 위"로 약속하므로, 화살촉도 생략합니다.

예시: 집합 $\{1, 2, 3, 6\}$ 위의 정수의 약수 관계 "$\mid$"에 대한 하세 다이어그램:

하세 다이어그램에서 중요한 개념:

함수

함수(Function) $f: A \to B$는 $A$의 각 원소에 $B$의 원소를 정확히 하나 대응시키는 관계입니다. 여기서 $A$는 정의역(Domain), $B$는 공역(Codomain)입니다.

함수의 종류

함수의 개수

$|A| = m$, $|B| = n$일 때:

합성 함수와 역함수

• 합성: $(g \circ f)(x) = g(f(x))$, $f: A \to B$이고 $g: B \to C$이면 $g \circ f: A \to C$
• 역함수: $f$가 전단사이면 $f^{-1}$가 존재하며 $f^{-1}(f(x)) = x$
• 합성의 성질: $g \circ f$가 단사이면 $f$는 단사, $g \circ f$가 전사이면 $g$는 전사

바닥 함수와 천장 함수

이산수학에서 특히 중요한 두 가지 실수-정수 변환 함수입니다.

바닥 함수(Floor Function): $x$를 넘지 않는 가장 큰 정수

천장 함수(Ceiling Function): $x$ 이상인 가장 작은 정수

주요 성질:

• $\lfloor x \rfloor = x$ $\iff$ $x$가 정수
• $\lfloor x \rfloor \leq x < \lfloor x \rfloor + 1$
• $\lceil x \rceil = -\lfloor -x \rfloor$
• $\lfloor x + n \rfloor = \lfloor x \rfloor + n$ (정수 $n$에 대해)
• $\left\lfloor \frac{n}{2} \right\rfloor + \left\lceil \frac{n}{2} \right\rceil = n$

재귀와 점화식

재귀적 정의란?

재귀(Recursion)란 자기 자신을 이용하여 정의하는 방법입니다. "거울 속의 거울"처럼 같은 구조가 반복되는 것이 핵심입니다.

재귀적 정의에는 반드시 두 가지가 필요합니다:

1. 기저 조건(Base Case): 재귀를 멈추는 시작점. 예: $F_0 = 0$, $F_1 = 1$
2. 재귀 단계(Recursive Step): 이전 값으로 다음 값을 정의하는 규칙. 예: $F_n = F_{n-1} + F_{n-2}$

점화식(Recurrence Relation)은 수열의 항을 이전 항들로 표현하는 식입니다. 알고리즘 분석에서 시간 복잡도를 표현하는 데 핵심적으로 사용됩니다.

피보나치 수열 - 단계별 이해

피보나치 수열은 "앞의 두 수를 더해서 다음 수를 만드는" 가장 유명한 재귀적 수열입니다.

단계별로 값을 구해 봅시다:

1. $F_0 = 0$, $F_1 = 1$ (기저 조건, 그냥 외웁니다)
2. $F_2 = F_1 + F_0 = 1 + 0 = 1$
3. $F_3 = F_2 + F_1 = 1 + 1 = 2$
4. $F_4 = F_3 + F_2 = 2 + 1 = 3$
5. $F_5 = F_4 + F_3 = 3 + 2 = 5$
6. $F_6 = F_5 + F_4 = 5 + 3 = 8$ ...

처음 몇 항: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots$

일반항 (비네 공식):

여기서 $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ (황금비), $\hat{\phi} = \frac{1-\sqrt{5}}{2} \approx -0.618$입니다.

하노이 탑 - 재귀적 사고의 정수

하노이 탑(Tower of Hanoi)은 대표적인 재귀 문제입니다. 3개의 기둥과 $n$개의 크기가 다른 원반이 있습니다. 모든 원반을 한 기둥에서 다른 기둥으로 옮기되, 한 번에 하나의 원반만, 그리고 큰 원반 위에 작은 원반만 놓을 수 있습니다.

재귀적 전략 (3단계):

1. 위쪽 $(n-1)$개의 원반을 보조 기둥으로 옮깁니다 → $H_{n-1}$회
2. 가장 큰 원반을 목표 기둥으로 옮깁니다 → $1$회
3. 보조 기둥의 $(n-1)$개의 원반을 목표 기둥으로 옮깁니다 → $H_{n-1}$회

이것을 점화식으로 쓰면:

풀이: $H_n + 1 = 2(H_{n-1} + 1)$로 놓으면 $H_n + 1 = 2^n$이므로:

선형 점화식의 풀이 - 특성방정식

$k$차 선형 상수 계수 동차 점화식:

특성방정식(Characteristic Equation):

해의 형태:

예시: $a_n = 5a_{n-1} - 6a_{n-2}$, $a_0 = 1$, $a_1 = 4$를 풀어보겠습니다.

1. 특성방정식: $r^2 - 5r + 6 = 0 \implies (r-2)(r-3) = 0$
2. 근: $r_1 = 2$, $r_2 = 3$
3. 일반해: $a_n = A \cdot 2^n + B \cdot 3^n$
4. 초기 조건 적용:
   • $a_0 = A + B = 1$
   • $a_1 = 2A + 3B = 4$
5. $A = -1$, $B = 2$
6. 답: $a_n = -2^n + 2 \cdot 3^n = 2 \cdot 3^n - 2^n$

비동차 선형 점화식

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + f(n)$ 형태에서, 일반해 = 동차해 + 특수해입니다.

생성함수를 이용한 풀이

생성함수(Generating Function)는 수열 $\{a_n\}$을 멱급수의 계수로 인코딩합니다:

피보나치 수열의 생성함수 유도:

1. $F_n = F_{n-1} + F_{n-2}$, $F_0 = 0$, $F_1 = 1$
2. $G(x) = \sum F_n x^n$이라 놓으면
3. $G(x) = xG(x) + x^2 G(x) + x$ (점화식 대입 후 정리)
4. $G(x)(1 - x - x^2) = x$

부분분수 분해 후 각 항의 계수를 구하면 비네 공식을 얻습니다.

마스터 정리

분할 정복 알고리즘의 점화식 $T(n) = aT(n/b) + O(n^d)$에서:

적용 예시:

• 병합 정렬: $T(n) = 2T(n/2) + O(n)$ → $a=2$, $b=2$, $d=1$, $\log_2 2 = 1 = d$ → $O(n \log n)$
• 이진 탐색: $T(n) = T(n/2) + O(1)$ → $a=1$, $b=2$, $d=0$, $\log_2 1 = 0 = d$ → $O(\log n)$
• 카라추바 곱셈: $T(n) = 3T(n/2) + O(n)$ → $a=3$, $b=2$, $d=1$, $\log_2 3 \approx 1.58 > d$ → $O(n^{\log_2 3})$

알고리즘 복잡도

시간 복잡도(Time Complexity)는 입력 크기에 따른 알고리즘의 실행 시간 증가율을 나타냅니다. 공간 복잡도(Space Complexity)는 메모리 사용량의 증가율입니다.

점근 표기법

흔한 복잡도 비교

정렬 알고리즘의 복잡도

P vs NP 문제

계산 복잡도 이론에서 가장 중요한 미해결 문제입니다.

명제 논리와 부울 대수 - 컴퓨터와의 관계

명제 논리란?

명제(Proposition)란 참(True) 또는 거짓(False) 중 정확히 하나의 값을 가지는 문장입니다. 예를 들어 "2는 짝수이다"는 참인 명제이고, "3 > 5"는 거짓인 명제입니다.

명제를 연결하는 논리 연산자는 다음과 같습니다.

핵심 포인트: 조건문 $p \to q$에서 $p$가 거짓이면 $q$의 값에 관계없이 전체가 참입니다. 이것은 처음에 직관과 다르게 느껴질 수 있지만, "거짓인 전제에서는 무엇이든 따라 나올 수 있다"고 약속한 것입니다. 예를 들어 "만약 내가 새라면, 하늘을 날 수 있다"는 참인 명제입니다 (나는 새가 아니므로).

부울 대수가 컴퓨터의 심장인 이유

명제 논리에서 참/거짓을 1/0으로 바꾸면 그것이 바로 부울 대수입니다. 컴퓨터의 CPU 내부에는 수십억 개의 논리 게이트(Logic Gate)가 있으며, 이 게이트들이 AND, OR, NOT 연산을 물리적으로 수행합니다. 여러분이 키보드를 누르거나 게임을 할 때, 그 모든 계산은 결국 부울 대수의 연산으로 이루어집니다.

부울 대수

부울 대수(Boolean Algebra)는 $\{0, 1\}$ 위에서 AND($\cdot$), OR($+$), NOT($'$) 연산이 정의된 대수 구조입니다.

기본 법칙

정규형

모든 부울 함수는 두 가지 정규형(Canonical Form)으로 표현할 수 있습니다:

• 최소항의 합(SOP, Sum of Products): 곱의 합 형태. 예: $f = x'y'z + xy'z' + xyz$
• 최대항의 곱(POS, Product of Sums): 합의 곱 형태. 예: $f = (x + y + z)(x + y' + z)(x' + y + z')$

최소항 표기: $n$개 변수의 최소항 $m_i$는 $i$의 이진 표현에 대응합니다. 예를 들어 변수 $x, y, z$에 대해 $m_5 = m_{101_2} = xy'z$입니다.

카르노 맵

카르노 맵(Karnaugh Map)은 부울 함수를 시각적으로 간소화하는 방법입니다. 인접한 칸이 하나의 변수만 다르도록 (그레이 코드 순서) 배치합니다.

2변수 카르노 맵 예시: $f(A, B) = A'B + AB' + AB = A + B$

인접한 1을 묶어 간소화합니다: 세로 두 칸 ($B=1$ 열) → $B$, 가로 두 칸 ($A=1$ 행) → $A$. 결과: $f = A + B$.

3변수 카르노 맵 예시: $f(A, B, C) = \sum m(0, 2, 4, 5, 6)$

묶음: $\{m_0, m_2, m_4, m_6\}$ (4칸 묶음) → $C'$, $\{m_4, m_5\}$ → $AB'$.

결과: $f = C' + AB'$

논리 게이트

부울 함수는 논리 게이트(Logic Gate)로 물리적으로 구현됩니다.

부울 대수는 디지털 회로 설계와 프로그래밍의 조건 논리에서 핵심적으로 사용됩니다.

격자와 부울 대수의 관계

격자(Lattice)는 임의의 두 원소가 상한(join, $\vee$)과 하한(meet, $\wedge$)을 가지는 부분 순서 집합입니다.

격자의 정의와 성질

부분 순서 집합 $(L, \preceq)$이 격자이려면:

• 임의의 $a, b \in L$에 대해 $a \vee b$ (최소 상계)가 존재
• 임의의 $a, b \in L$에 대해 $a \wedge b$ (최대 하계)가 존재

격자 연산의 법칙:

격자의 종류

스톤 표현 정리: 모든 유한 부울 대수는 어떤 유한 집합의 멱집합 부울 대수와 동형입니다. 따라서 유한 부울 대수의 원소 수는 반드시 $2$의 거듭제곱입니다.

예시: 약수 격자

양의 정수 $n$의 약수 집합에 약수 관계를 부분 순서로 놓으면 격자가 됩니다:

• $a \vee b = \text{lcm}(a, b)$ (최소공배수)
• $a \wedge b = \gcd(a, b)$ (최대공약수)

$n$이 서로 다른 소수의 곱(제곱 인수 없음)이면 약수 격자는 부울 대수가 됩니다. 예를 들어 $n = 30 = 2 \cdot 3 \cdot 5$의 약수 격자는 3원소 집합의 멱집합과 동형인 부울 대수입니다.

오토마타와 형식 언어

오토마타 이론(Automata Theory)은 추상적인 계산 기계와 그것이 인식할 수 있는 형식 언어를 연구합니다. 컴파일러, 정규 표현식, 프로토콜 검증 등의 기초 이론입니다.

기본 용어

• 알파벳(Alphabet) $\Sigma$: 유한한 기호의 집합. 예: $\Sigma = \{0, 1\}$
• 문자열(String): 알파벳의 기호를 유한하게 나열한 것. 빈 문자열은 $\varepsilon$
• 언어(Language) $L$: $\Sigma^*$의 부분집합 ($\Sigma^*$는 모든 가능한 문자열의 집합)

결정적 유한 오토마톤 (DFA)

DFA(Deterministic Finite Automaton)는 5-튜플 $(Q, \Sigma, \delta, q_0, F)$로 정의됩니다:

예시: 이진 문자열에서 $1$이 짝수 개인 문자열을 인식하는 DFA:

전이 표:

($\to$: 시작 상태, $*$: 수락 상태)

비결정적 유한 오토마톤 (NFA)

NFA(Nondeterministic Finite Automaton)는 DFA와 유사하지만:

• 전이 함수가 $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$ (상태의 부분집합을 반환)
• 한 상태에서 같은 입력에 대해 여러 전이가 가능
• $\varepsilon$-전이(입력 없이 전이)를 허용

정규 언어

DFA(또는 NFA)로 인식 가능한 언어를 정규 언어(Regular Language)라 합니다.

정규 표현식과의 관계: 정규 언어는 정규 표현식으로 표현 가능하고, 역도 성립합니다.

정규 언어의 닫힘 성질: 정규 언어는 합집합, 교집합, 여집합, 연결, 클리니 스타 연산에 대해 닫혀 있습니다.

촘스키 계층

촘스키 계층(Chomsky Hierarchy)은 형식 문법을 인식 능력에 따라 4단계로 분류합니다:

각 유형의 포함 관계:

수학적 귀납법

수학적 귀납법(Mathematical Induction)은 자연수에 관한 명제를 증명하는 강력한 방법입니다. "도미노 쓰러뜨리기"와 완전히 같은 원리입니다.

수학적 귀납법의 형식

자연수 $n$에 대한 명제 $P(n)$을 증명하려면:

1. 기초 단계(Base Case): $P(1)$(또는 시작하는 자연수)이 참임을 보입니다.
2. 귀납 단계(Inductive Step): "$P(k)$가 참이면 $P(k+1)$도 참이다"를 보입니다. 여기서 "$P(k)$가 참이다"라는 가정을 귀납 가설(Inductive Hypothesis)이라 합니다.

이 두 단계가 모두 성립하면, 모든 자연수 $n$에 대해 $P(n)$이 참입니다.

예제 1: 자연수의 합

명제: 모든 자연수 $n \geq 1$에 대하여 $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$

증명:

기초 단계: $n = 1$일 때, 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$. 양변이 같으므로 성립합니다.

귀납 단계: $n = k$일 때 성립한다고 가정합니다 (귀납 가설):

$n = k + 1$일 때를 보입니다:

이것은 $n = k+1$일 때의 공식과 일치합니다. 따라서 귀납법에 의해 모든 자연수 $n$에 대해 성립합니다. $\blacksquare$

예제 2: 부등식 증명

명제: 모든 자연수 $n \geq 4$에 대하여 $2^n > n^2$

증명:

기초 단계: $n = 4$일 때, $2^4 = 16 > 16 = 4^2$... 아, 같습니다. $n = 5$일 때를 확인합니다: $2^5 = 32 > 25 = 5^2$. 성립합니다. (시작점을 $n = 5$로 조정합니다.)

귀납 단계: $k \geq 5$에서 $2^k > k^2$이 성립한다고 가정합니다.

$2k^2 > (k+1)^2 = k^2 + 2k + 1$임을 보이면 충분합니다. 이는 $k^2 > 2k + 1$, 즉 $k^2 - 2k - 1 > 0$과 같으며, $k \geq 5$이면 $25 - 10 - 1 = 14 > 0$이므로 성립합니다.

따라서 $2^{k+1} > 2k^2 > (k+1)^2$입니다. $\blacksquare$

예제 3: 하노이 탑의 이동 횟수

명제: $n$개의 원반을 가진 하노이 탑의 최소 이동 횟수는 $H_n = 2^n - 1$입니다.

증명:

기초 단계: $n = 1$일 때, $H_1 = 1 = 2^1 - 1$. 성립합니다.

귀납 단계: $H_k = 2^k - 1$이 성립한다고 가정합니다.

따라서 $n = k + 1$일 때도 성립합니다. $\blacksquare$

강한 귀납법

강한 귀납법(Strong Induction)에서는 귀납 단계에서 $P(k)$만 가정하는 것이 아니라, $P(1), P(2), \ldots, P(k)$가 모두 참이라고 가정합니다. 이 방법은 피보나치 수열처럼 두 개 이상의 이전 항에 의존하는 점화식을 다룰 때 유용합니다.

수학적 귀납법 심화

약한 귀납법 vs 강한 귀납법 — 비교

약한(보통) 귀납법과 강한 귀납법의 구조를 비교합니다.

강한 귀납법 예제: 소인수분해의 존재성

명제: 모든 $n \geq 2$인 정수는 소수들의 곱으로 표현할 수 있습니다.

증명 (강한 귀납법):

기초 단계: $n = 2$는 소수이므로, 자기 자신이 소인수분해입니다.

귀납 단계: $2, 3, \ldots, k$ 모두 소인수분해가 가능하다고 가정합니다 (강한 귀납 가설).

$n = k + 1$을 살펴봅니다.

• 경우 1: $k + 1$이 소수이면, 자기 자신이 소인수분해입니다.
• 경우 2: $k + 1$이 합성수이면, $k + 1 = a \cdot b$이며 $2 \leq a, b \leq k$입니다. 강한 귀납 가설에 의해 $a$와 $b$ 모두 소인수분해가 가능하므로, 그 곱인 $k + 1$도 소인수분해가 가능합니다. $\blacksquare$

구조적 귀납법

구조적 귀납법(Structural Induction)은 자연수가 아닌 재귀적으로 정의된 구조(트리, 수식, 문자열 등)에 대해 귀납법을 적용하는 방법입니다.

원리: 재귀적으로 정의된 집합 $S$에 대해 성질 $P$를 증명하려면:

1. 기초 단계: 기저 원소들에 대해 $P$가 성립함을 보입니다.
2. 귀납 단계: 재귀 규칙으로 만들어지는 원소가 $P$를 만족함을 보입니다 (구성 요소들이 $P$를 만족한다고 가정).

예제: 이진 트리에서 "잎 노드의 수 $\ell$과 내부 노드의 수 $i$는 $\ell = i + 1$ 관계를 만족합니다."

기초 단계: 노드가 하나뿐인 트리에서 $\ell = 1$, $i = 0$이므로 $\ell = i + 1$ 성립합니다.

귀납 단계: 이진 트리 $T$가 루트와 두 부분 트리 $T_1$, $T_2$로 구성되고, 각각 $\ell_1 = i_1 + 1$, $\ell_2 = i_2 + 1$을 만족한다고 가정합니다. 그러면 $T$의 잎 노드 수 $\ell = \ell_1 + \ell_2$이고, 내부 노드 수 $i = i_1 + i_2 + 1$이므로:

잘 정렬 원리와 귀납법의 동치

잘 정렬 원리(Well-Ordering Principle): 자연수의 모든 비공 부분집합은 최소 원소를 가집니다.

잘 정렬 원리 $\Rightarrow$ 귀납법 (증명 스케치):

$P(1)$이 참이고, $P(k) \Rightarrow P(k+1)$이 성립한다고 합시다. 귀류법으로, $P(n)$이 거짓인 $n$이 존재한다고 가정합니다. $S = \{n \in \mathbb{N} \mid P(n) \text{ 거짓}\}$이라 놓으면, 잘 정렬 원리에 의해 $S$에 최소 원소 $m$이 존재합니다. $P(1)$이 참이므로 $m > 1$이고, $m - 1 \notin S$이므로 $P(m - 1)$이 참입니다. 귀납 가정에 의해 $P(m)$도 참이어야 하는데, 이는 $m \in S$에 모순됩니다. $\blacksquare$

재귀관계 심화 — 다양한 풀이 비교

같은 재귀 관계를 여러 방법으로 풀어 보면서, 각 방법의 장단점을 비교합니다.

대상: $a_n = 3a_{n-1} - 2a_{n-2}$, $a_0 = 1$, $a_1 = 3$

풀이 1: 특성방정식

1. 특성방정식: $r^2 - 3r + 2 = 0 \implies (r - 1)(r - 2) = 0$
2. 근: $r_1 = 1$, $r_2 = 2$
3. 일반해: $a_n = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n$
4. 초기 조건: $$A + B = 1, \quad A + 2B = 3 \implies B = 2, \; A = -1$$
5. 답: $a_n = 2^{n+1} - 1$

풀이 2: 반복 대입 (Iteration)

점화식을 반복 적용하여 패턴을 찾습니다:

처음 몇 항을 직접 계산합니다:

• $a_0 = 1, \; a_1 = 3, \; a_2 = 9 - 2 = 7, \; a_3 = 21 - 6 = 15, \; a_4 = 45 - 14 = 31$

패턴 관찰: $1, 3, 7, 15, 31, \ldots$ → $a_n = 2^{n+1} - 1$로 추측합니다.

검증 (귀납법): $a_n = 2^{n+1} - 1$이 점화식을 만족하는지 확인합니다:

풀이 3: 생성함수

1. $G(x) = \sum_{n=0}^{\infty} a_n x^n$으로 놓습니다.
2. 점화식 양변에 $x^n$을 곱하고 $n \geq 2$에서 합산합니다: $$\sum_{n=2}^{\infty} a_n x^n = 3\sum_{n=2}^{\infty} a_{n-1} x^n - 2\sum_{n=2}^{\infty} a_{n-2} x^n$$
3. 정리하면: $$G(x) - 1 - 3x = 3x(G(x) - 1) - 2x^2 G(x)$$ $$G(x)(1 - 3x + 2x^2) = 1$$ $$G(x) = \frac{1}{(1-x)(1-2x)}$$
4. 부분분수 분해: $$G(x) = \frac{-1}{1-x} + \frac{2}{1-2x} = -\sum_{n=0}^{\infty} x^n + 2\sum_{n=0}^{\infty} (2x)^n$$
5. $x^n$의 계수: $a_n = -1 + 2 \cdot 2^n = 2^{n+1} - 1$ $\checkmark$

중근이 있는 경우: $a_n = 4a_{n-1} - 4a_{n-2}$

초기 조건: $a_0 = 1$, $a_1 = 4$

특성방정식: $r^2 - 4r + 4 = (r - 2)^2 = 0$ → 중근 $r = 2$

일반해: $a_n = (A + Bn) \cdot 2^n$

초기 조건 적용: $A = 1$, $2A + 2B = 4 \implies B = 1$

관계 심화 — 동치관계와 분할의 대응

동치관계 $\Leftrightarrow$ 분할 정리 (상세 증명)

이 정리는 동치관계와 분할이 "동전의 양면"이라는 것을 보여줍니다.

방향 1: 동치관계 $\Rightarrow$ 분할

집합 $A$ 위의 동치관계 $\sim$이 주어졌을 때, 동치류의 모임 $\{[a] \mid a \in A\}$는 $A$의 분할입니다.

증명해야 할 것:

1. 각 동치류는 비공집합: $a \in [a]$ (반사적 성질)
2. 동치류들의 합집합이 $A$: 모든 $a \in A$에 대해 $a \in [a]$
3. 서로 다른 동치류는 서로소: $[a] \cap [b] \neq \emptyset$이면 $[a] = [b]$임을 보입니다. $c \in [a] \cap [b]$이면, $c \sim a$이고 $c \sim b$이므로, 대칭적·추이적 성질에 의해 $a \sim b$이고, 따라서 $[a] = [b]$입니다.

방향 2: 분할 $\Rightarrow$ 동치관계

$A$의 분할 $\{A_1, A_2, \ldots\}$이 주어졌을 때, "$a \sim b$ $\iff$ 같은 블록에 속한다"로 정의하면 $\sim$은 동치관계입니다.

증명: 반사적(자기 자신과 같은 블록), 대칭적(같은 블록 관계는 방향 무관), 추이적(같은 블록은 전이됨)이 모두 명백합니다. $\blacksquare$

분할 수와 벨 수

$n$-원소 집합의 서로 다른 분할의 수를 벨 수(Bell Number) $B_n$이라 합니다.

순서관계 심화 — 반순서와 전순서

전순서(Total Order, Linear Order)와 반순서(Partial Order)의 핵심 차이는 비교 가능성입니다.

반사슬과 사슬:

• 사슬(Chain): 모든 원소 쌍이 비교 가능한 부분집합
• 반사슬(Antichain): 어떤 두 원소도 비교 불가능한 부분집합

딜워스 정리(Dilworth's Theorem): 유한 부분 순서 집합에서, 최대 반사슬의 크기 = 사슬로 분해할 때의 최소 사슬 수

하세 다이어그램 심화 예시: $D_{30}$의 약수 격자

$30$의 약수 집합 $\{1, 2, 3, 5, 6, 10, 15, 30\}$ 위의 약수 관계 하세 다이어그램입니다.

$30 = 2 \cdot 3 \cdot 5$는 제곱 인수가 없으므로, 이 약수 격자는 $\{2, 3, 5\}$의 멱집합 부울 대수 $\mathcal{P}(\{2,3,5\})$와 동형입니다. 사슬의 예: $\{1, 2, 6, 30\}$, 반사슬의 예: $\{2, 3, 5\}$.

격자 이론 기초

격자의 대수적 정의

격자는 두 가지 관점에서 정의할 수 있습니다:

1. 순서론적 정의: 임의의 두 원소가 상한과 하한을 가지는 부분 순서 집합
2. 대수적 정의: 두 이항 연산 $\vee$와 $\wedge$가 교환·결합·흡수 법칙을 만족하는 대수 구조

두 정의는 동치입니다. 순서론적 격자에서 $a \preceq b \iff a \wedge b = a \iff a \vee b = b$로 순서를 복원할 수 있습니다.

분배 격자와 비분배 격자

분배 격자(Distributive Lattice)는 분배 법칙이 성립하는 격자입니다:

분배 격자가 아닌 대표적인 예는 두 가지입니다:

모듈러 격자

모듈러 격자(Modular Lattice)는 $a \preceq c$이면 $a \vee (b \wedge c) = (a \vee b) \wedge c$가 성립하는 격자입니다. 모든 분배 격자는 모듈러 격자이지만, 역은 성립하지 않습니다 ($M_3$는 모듈러이지만 비분배). $N_5$가 부분 격자로 나타나지 않는 격자가 정확히 모듈러 격자입니다.

부울 대수와 부울 함수 심화

퀸-맥클러스키 알고리즘

퀸-맥클러스키(Quine-McCluskey) 알고리즘은 카르노 맵의 체계적인 확장으로, 5변수 이상의 부울 함수도 최소화할 수 있습니다.

알고리즘 단계:

1. 1단계 — 소항(Prime Implicant) 찾기: 최소항을 1의 개수별로 그룹화하고, 인접 그룹의 항끼리 하나의 비트만 다른 경우를 결합합니다. 더 이상 결합할 수 없는 항이 소항입니다.
2. 2단계 — 소항 표(Prime Implicant Chart): 행에 소항, 열에 최소항을 배치하고, 각 소항이 포함하는 최소항에 표시합니다.
3. 3단계 — 필수 소항(Essential Prime Implicant) 선택: 어떤 최소항이 오직 하나의 소항에만 포함되면, 그 소항은 필수입니다.
4. 4단계 — 나머지 처리: 아직 포함되지 않은 최소항을 최소 비용으로 포함하도록 소항을 선택합니다.

예시: $f(A, B, C, D) = \sum m(0, 1, 2, 5, 6, 7, 8, 9, 10, 14)$

결합 과정을 거쳐 소항을 구하고, 필수 소항을 선택하여 최소식을 얻습니다.

논리 회로 설계 예제

부울 함수 $f = AB' + A'BC$를 NAND 게이트만으로 구현하는 과정입니다.

1. 원래 식: $f = AB' + A'BC$
2. 이중 부정 적용: $f = ((AB')' \cdot (A'BC)')' $
3. 각 항을 NAND로 변환: NAND$(x, y) = (xy)'$이므로, $AB' = $ NAND(NAND$(A, B'), $ NAND$(A, B'))$처럼 분해합니다.

알고리즘 분석 심화

마스터 정리의 증명 스케치

$T(n) = aT(n/b) + cn^d$에서 재귀 트리를 분석합니다.

• 깊이 $i$에서의 문제 수: $a^i$개, 각 문제의 크기: $n/b^i$
• 깊이 $i$에서의 비용: $a^i \cdot c(n/b^i)^d = cn^d \cdot (a/b^d)^i$
• 총 깊이: $\log_b n$

총 비용은 등비급수의 합입니다:

• $a/b^d < 1$ (즉 $d > \log_b a$): 등비급수가 수렴 → $T(n) = O(n^d)$
• $a/b^d = 1$ (즉 $d = \log_b a$): 각 단계의 비용이 같으므로 → $T(n) = O(n^d \log n)$
• $a/b^d > 1$ (즉 $d < \log_b a$): 마지막 단계가 지배 → $T(n) = O(n^{\log_b a})$

분할 정복 재귀 트리 다이어그램

분할상환 분석 (Amortized Analysis)

분할상환 분석(Amortized Analysis)은 일련의 연산에서 최악의 경우 단일 연산 비용이 아니라, 연산 시퀀스의 평균 비용을 분석하는 기법입니다.

세 가지 주요 방법이 있습니다:

예시: 동적 배열 (Dynamic Array)

크기가 꽉 찰 때마다 용량을 2배로 늘리는 배열에서 $n$번 삽입의 분할상환 비용:

• 복사 비용이 발생하는 시점: $1, 2, 4, 8, 16, \ldots$번째 삽입
• 총 복사 비용: $1 + 2 + 4 + \cdots + n/2 + n = 2n - 1$
• 분할상환 비용: $(n + 2n - 1) / n = 3 - 1/n = O(1)$

오토마타 이론 심화

NFA에서 DFA로의 변환: 부분집합 구성법

부분집합 구성법(Subset Construction)은 NFA를 동치인 DFA로 변환하는 체계적인 방법입니다.

알고리즘:

1. DFA의 각 상태는 NFA 상태의 부분집합입니다.
2. 시작 상태: NFA 시작 상태의 $\varepsilon$-폐포
3. 전이: $\delta'(S, a) = \bigcup_{q \in S} \varepsilon\text{-closure}(\delta(q, a))$
4. 수락 상태: NFA 수락 상태를 포함하는 모든 부분집합

예시: NFA가 상태 $\{q_0, q_1, q_2\}$를 가지고 $q_0$에서 입력 $a$에 대해 $\{q_0, q_1\}$로 전이하면, DFA에서는 $\{q_0\} \xrightarrow{a} \{q_0, q_1\}$이 됩니다.

정규 표현식 → NFA 변환 (톰슨 구성법)

정규 표현식의 기본 연산 각각을 NFA 구성 요소로 변환합니다:

DFA 최소화

DFA 최소화(DFA Minimization)는 동치인 최소 상태 수의 DFA를 찾는 과정입니다.

호프크로프트 알고리즘 (개요):

1. 상태를 수락/비수락 두 그룹으로 분할합니다.
2. 같은 그룹의 두 상태가 어떤 입력에 대해 다른 그룹으로 전이하면, 그 그룹을 분리합니다.
3. 더 이상 분리할 수 없을 때까지 반복합니다.
4. 각 최종 그룹이 최소 DFA의 한 상태가 됩니다.

형식 언어 심화 — 촘스키 계층의 구분

문맥 자유 문법 (CFG)

문맥 자유 문법(Context-Free Grammar)은 $G = (V, \Sigma, R, S)$으로 정의됩니다:

• $V$: 변수(비단말 기호)의 유한 집합
• $\Sigma$: 단말 기호의 유한 집합 ($V \cap \Sigma = \emptyset$)
• $R$: 생성 규칙의 유한 집합, $A \to \alpha$ 형태 ($A \in V$, $\alpha \in (V \cup \Sigma)^*$)
• $S \in V$: 시작 변수

예시: $\{a^n b^n \mid n \geq 0\}$을 생성하는 CFG:

유도 과정: $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow aaabbb = a^3 b^3$

푸시다운 오토마톤 (PDA)

푸시다운 오토마톤(Pushdown Automaton)은 유한 오토마톤에 스택을 추가한 것입니다. 스택 덕분에 "개수를 세는" 능력이 생깁니다.

PDA vs DFA/NFA:

각 유형의 언어 예시와 증명 전략

계산 복잡도 이론

결정 문제와 복잡도 클래스

결정 문제(Decision Problem)는 "예/아니오"로 답할 수 있는 문제입니다. 복잡도 클래스는 결정 문제를 해결하는 데 필요한 자원(시간, 공간)에 따라 분류합니다.

다항 시간 환원

문제 $A$가 문제 $B$로 다항 시간 환원 가능(Polynomial-time reducible)하다는 것은, 다항 시간에 계산 가능한 함수 $f$가 존재하여:

이것을 $A \leq_P B$로 표기합니다. 직관적으로, "A를 풀 수 있으면 B도 풀 수 있다" 또는 "$B$가 $A$보다 적어도 같은 정도로 어렵다"는 의미입니다.

NP-완전의 정의와 쿡-레빈 정리

문제 $L$이 NP-완전(NP-complete)이려면:

1. $L \in \text{NP}$
2. 모든 $L' \in \text{NP}$에 대해 $L' \leq_P L$ (NP-난해)

쿡-레빈 정리 (Cook-Levin Theorem): SAT (부울 만족 가능성 문제)는 NP-완전입니다.

대표적인 NP-완전 문제

P vs NP에 대한 현재 상태

$P = NP$인지 $P \neq NP$인지는 2026년 현재까지 미해결입니다. 대다수의 컴퓨터 과학자는 $P \neq NP$라고 추측하지만, 증명은 아직 없습니다.

$P = NP$라면:

• RSA, ECC 등 현대 암호 체계가 무력화될 수 있습니다.
• 최적화 문제, 스케줄링 등 많은 실용적 문제를 효율적으로 풀 수 있습니다.
• 수학 정리의 증명을 자동으로 찾을 수 있게 될 수 있습니다.

$P \neq NP$라면:

• 본질적으로 "풀기 어렵지만 검증은 쉬운" 문제가 존재합니다.
• 현대 암호학의 안전성 가정이 유지됩니다.

NP-완전 환원 다이어그램

코딩 이론 기초

코딩 이론(Coding Theory)은 데이터 전송 및 저장 과정에서 발생하는 오류를 검출하고 정정하는 수학적 방법을 연구합니다.

기본 개념

오류 검출/정정 능력:

• 최소 거리 $d$인 부호는 최대 $d - 1$개의 오류를 검출할 수 있습니다.
• 최소 거리 $d$인 부호는 최대 $\lfloor (d-1)/2 \rfloor$개의 오류를 정정할 수 있습니다.

패리티 검사 부호

가장 간단한 오류 검출 부호입니다. $k$ 비트 메시지에 1비트의 패리티 비트를 추가합니다.

• 짝수 패리티: 전체 1의 개수가 짝수가 되도록 패리티 비트 설정
• 예: 메시지 $1011$ → 부호어 $10111$ (1이 4개, 짝수)
• $[k+1, k, 2]$ 부호 → 1개 오류 검출 가능, 정정 불가

해밍 부호

해밍 부호(Hamming Code)는 1비트 오류를 검출하고 정정할 수 있는 부호입니다.

해밍(7,4) 부호: $[7, 4, 3]$ 부호로, 4비트 메시지에 3비트의 검사 비트를 추가합니다.

메시지 비트: $d_1, d_2, d_3, d_4$ (위치 3, 5, 6, 7)

검사 비트: $p_1, p_2, p_3$ (위치 1, 2, 4)

부호어 $[p_1, p_2, d_1, p_3, d_2, d_3, d_4]$에서 검사 비트는 다음 조건을 만족합니다:

오류 정정 과정:

1. 수신된 비트열로 증후군(syndrome) $s_1, s_2, s_3$을 계산합니다.
2. $s_3 s_2 s_1$을 이진수로 해석하면 오류 위치를 나타냅니다.
3. $s_3 s_2 s_1 = 000$이면 오류 없음, 그 외에는 해당 위치의 비트를 반전합니다.

예시: 메시지 $1010$을 해밍(7,4)로 부호화합니다.

• $d_1 = 1, d_2 = 0, d_3 = 1, d_4 = 0$
• $p_1 = 1 \oplus 0 \oplus 0 = 1$
• $p_2 = 1 \oplus 1 \oplus 0 = 0$
• $p_3 = 0 \oplus 1 \oplus 0 = 1$
• 부호어: $[1, 0, 1, 1, 0, 1, 0]$

만약 5번째 비트에서 오류가 발생하여 $[1, 0, 1, 1, \mathbf{1}, 1, 0]$을 수신했다면:

• $s_1 = p_1 \oplus d_1 \oplus d_2 \oplus d_4 = 1 \oplus 1 \oplus 1 \oplus 0 = 1$
• $s_2 = p_2 \oplus d_1 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 \oplus 0 = 0$
• $s_3 = p_3 \oplus d_2 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 \oplus 0 = 1$
• 증후군: $s_3 s_2 s_1 = 101_2 = 5$ → 5번째 비트에 오류!

해밍 부호의 오류 검출/정정 원리

해밍 한계와 길버트-바시햄로프 한계

$[n, k, d]$ 이진 부호가 존재하기 위한 이론적 한계입니다:

• 해밍 한계 (Hamming Bound, 구 포장 한계): $$2^k \sum_{i=0}^{t} \binom{n}{i} \leq 2^n, \quad t = \left\lfloor \frac{d-1}{2} \right\rfloor$$ 이 부등식을 등호로 만족하는 부호를 완전 부호(Perfect Code)라 합니다. 해밍(7,4) 부호는 완전 부호입니다.
• 싱글턴 한계 (Singleton Bound): $k \leq n - d + 1$

참고자료

• Rosen, K. H. — Discrete Mathematics and Its Applications, McGraw-Hill
• Epp, S. S. — Discrete Mathematics with Applications, Cengage
• Sipser, M. — Introduction to the Theory of Computation, Cengage
• Hopcroft, Motwani, Ullman — Introduction to Automata Theory, Languages, and Computation, Pearson
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), MIT Press
• 논리학 — 부울 대수의 기초
• 집합론 — 관계의 기초
• 조합론 — 셈의 원리
• 그래프 이론 — 이산 구조의 응용