Terminology Summary
용어 정리
Set (집합)
Set (집합)
- Element(원소)들의 모임으로, Membership(소속성)을 제외한 어떤 구조도 갖지 않는다.
Set Operation (집합 연산)
- Intersection(∩, 교집합)
- Union(∪, 합집합)
- Difference(-, 차집합)
Complementation (여집합)
\(\bar{S}\) (혹은 \(S^{c}\)) : 집합 \(S\)의 여집합
\(\bar{S} = \{x : x ∈ U, x \notin S\}\) (단, \(U\)는 전체 집합)
Empty Set (공집합, \(\varnothing\))
- 아무 원소도 가지지 않은 집합이다.
Subset (부분집합)
S_{1} ⊆ S_{2}
: 집합 S_{1}의 모든 원소들이 집합 S_{2}의 원소이다.
Proper Subset (진부분집합)
S_{1} ⊂ S_{2}
: S_{1} ⊆ S_{2}이면서, S_{2}가 S_{1}에 없는 원소를 하나 이상 갖고있다.
Disjoint (서로소)
- 두 집합에 공통으로 속하는 원소가 없는 경우를 의미한다.
\(S_{1} \cap S_{2} = \varnothing\)
Finite Set (유한 집합)
- 원소의 개수가 유한한 집합을 의미한다.
Infinite Set (무한 집합)
- 원소의 개수가 무한한 집합을 의미한다.
Powerset (멱집합)
- 한 집합의 모든 부분 집합들의 집합을 의미한다.
- 집합 \(S\)에 대한 멱집합은 \(2^{S}\)로 표현한다.
\(| 2^S | = 2^{| S |}\)
Cartesian Product (카티션 곱)
- 한 집합의 원소들이 다른 여러 집합 원소들의 Ordered Sequence(순서열)인 집합이다.
- 두 집합의 카티션 곱이면, 이 집합은 Ordered Pair(순서쌍)를 원소로 갖는 집합이다.
\(S = S_{1} \times S_{2} = \{(x, y) : x \in S_{1}, y \in S_{2}\}\)
\(S_{1} \times S_{2} \times \cdots \times S_{n} = \{(x_1, x_2, \cdots, x_n) : x_i \in S_i\}\)
Partition (분할)
1. 부분집합들 \(S_1, S_2, \cdots S_n\)들은 Mutually Disjoint(상호간 서로소)하다.
2. \(S_1 \cup S_2 \cup \cdots \cup S_n = S\) 이다.
3. \(S_i \neq \varnothing\) 이다.
위 3가지 조건을 모두 만족시키는 \(S_1, S_2, \cdots S_n\)을 \(S\)의 Partition(분할)이라 한다.
Function and Relation (함수와 관계)
\(f : S_1 \to S_2\)
함수 f가 위와 같이 정의되었을 때,
함수 f의 Domain(정의역)은 S_1의 부분집합이고,
함수 f의 Range(치역)는 S_2의 부분집합임을 의미한다.
Total Function (전체 함수)
함수 f의 정의역이 S_1과 같은 경우를 의미한다.
Partial Function (부분 함수)
함수 f의 정의역이 S_1의 Proper Set(진부분 집합)인 경우를 의미한다.
Order of Magnitude Notation (크기 순위 표기법)
1. \(f(n) = O(g(n))\)
- \(f(n)\), \(g(n)\)은 정의역이 양의 정수들의 부분집합인 함수이고,
\(f(n) \leq c|g(n)|\) 을 만족시키는 양의 상수 \(c\)가 존재하면 위와 같이 Big-Oh Notation으로 표기할 수 있다.
- 이는 \(f\)의 순위가 \(g\)의 순위(차수)보다 높지 않음을 표현하는 방식이다.
2. \(f(n) = \Omega(g(n))\)
- \(f(n)\), \(g(n)\)은 정의역이 양의 정수들의 부분집합인 함수이고,
\(|f(n)| \geq c|g(n)|\) 을 만족시키는 양의 상수 \(c\)가 존재하면 위와 같이 Big-Omega Notation으로 표기할 수 있다.
- 이는 \(f\)의 순위가 \(g\)의 순위(차수)보다 낮지 않음을 표현하는 방식이다.
3. \(f(n) = \Theta(g(n))\)
- \(f(n)\), \(g(n)\)은 정의역이 양의 정수들의 부분집합인 함수이고,
\(c_1|g(n)| \leq |f(n)| \leq c_2|g(n)|\) 을 만족시키는 양의 상수 \(c_1\), \(c_2\)가 존재하면 위와 같이 Theta Notation으로 표기할 수 있다.
- 이는 \(f\)와 \(g\)의 순위(차수)가 같음을 표현하는 방식이다.
Relation (관계)
- 함수에서는 정의역의 각 원소들이 정확히 치역의 한 원소에 대응되지만,
관계에서는 하나의 정의역이 여러 치역의 원소들에 대응될 수 있다.
- 관계는 함수를 보다 일반화한 개념이다.
- 관계 또한, 함수와 같이 Pair들의 집합이다.
Equivalence Relation (동치 관계)
\(x \equiv y\)
- 순서쌍 \((x, y)\)가 동치 관계에 있음을 위와 같이 표기한다.
- 동치 관계는 Equality Identity(동치)의 개념을 일반화한 개념이다.
- 동치 관계는 아래 세 가지 성질을 만족해야 한다.
1. Reflexivity Rule (반사성)
\(x \equiv x \; \mathrm{for \; all} \; x\)
2. Symmetry Rule (대칭성)
\(\mathrm{if} \; x \equiv y, \; \mathrm{then} \; y \equiv x\)
3. Transitivity Rule (전이성)
\(\mathrm{if} \; x \equiv y \; \mathrm{and} \; y \equiv z, \mathrm{then} \; x \equiv z\)
Ex. \(x \; \mathrm{mod} \; 3 = y \; \mathrm{mod} \; 3 \iff x \equiv y\) 함을 보여라.
pf)
Reflexivity Rule:
\(x \equiv x \iff x \; \mathrm{mod} \; 3 = x \; \mathrm{mod} \; 3 \)
Symmetry Rule:
\(x \equiv y \iff x \; \mathrm{mod} \; 3 = y \; \mathrm{mod} \; 3 \iff y \; \mathrm{mod} \; 3 = x \; \mathrm{mod} \; 3 \iff y \equiv x\)
Transitivity Rule:
\(x \equiv y \; \mathrm{and} \; y \equiv z \iff x \; \mathrm{mod} \; 3 = y \; \mathrm{mod} \; 3 \; \mathrm{and} \; y \; \mathrm{mod} \; 3 = z \; \mathrm{mod} \; 3 \iff x \; \mathrm{mod} \; 3 = z \; \mathrm{mod} \; 3 \iff x \equiv z\)
Equivalence Classes (동치부류)
- 서로 동치인 원소들로만 구성된 집합이다.
- 즉, 동치부류에서 어떤 두 원소를 추출하더라도, 두 원소는 동치관계에 있다.
- 집합 \(S\)에 동치관계가 정의되어 있다면, 이 동치성을 사용하여 \(S\)를 동치부류들로 분할할 수 있다.
Graph (그래프)
Graph (그래프)
- Vertex(정점)들의 집합 \(V = {v_1, v_2, \cdots v_n}\)와,
Edge(간선)들의 집합 \(E = {e_1, e_2, \cdots e_n}\)으로 이루어진 구조이다.
- 각 간선은 집합 \(V\)에 있는 정점들의 Pair이다.
ex) \(e_i = (v_j, v_k)\)
- 간선 \(e_i\)는 정점 \(v_j\)에서 정점 \(v_k\)로 가는 간선이다.
Outgoing Edge (진출 간선)
- 위 예시에서 \(e_i\)는 \(v_j\)를 기준으로 했을 때 진출 간선이다.
Incoming Edge (진입 간선)
- 위 예시에서 \(e_i\)는 \(v_k\)를 기준으로 했을 때 진입 간선이다.
Directed Graph (Digraph; 유향 그래프)
- 방향을 갖는 간선들로 구성된 그래프이다.
Labeled Graph (레이블 그래프)
- 정점이나 간선에 Label(레이블)이 지정된 그래프이다.
- 레이블은 특별한 이름이나 정보 등일 수 있다.
Walk (보행)
- \((v_i, v_j), (v_j, v_k), \cdots , (v_m, v_n)\) 와 같이 표현되는 간선들의 순서열을 "\(v_i\)에서 \(v_n\)까지의 보행"이라 표현한다.
Length (길이)
- 보행의 시작 정점에서 마지막 정점까지 거치게 되는 간선들의 개수이다.
Path (경로)
- 어느 간선도 중복하여 지나지 않는 Walk을 의미한다.
Simple Path (단순 경로)
- 어느 정점도 중복하여 지나지 않는 Path를 의미한다.
Cycle (싸이클)
- 정점 \(v_i\)에서부터 어느 간선도 중복해 지나지 않고, \(v_i\) 자기 자신으로 돌아오는 Walk를
"\(v_i\)를 Base로 하는 Cycle"이라 표현한다.
Loop (루프)
- 한 정점에서 자기 자신으로 되돌아오는 간선을 의미한다.
Tree (트리)
Tree (트리)
- Cycle을 갖지 않고, Root라는 특수 정점을 가진 Digraph이다.
- Root에서는 다른 모든 노드 각각으로 정확히 하나의 Path만이 존재해야 한다.
(Root에는 Incoming Edge가 존재할 수 없음을 의미한다.)
Leaf (리프)
- Tree에서 Outgoing Edge를 갖지 않는 정점(노드)이다.
Parent Node, Child Node (부모 노드, 자식 노드)
- Tree에서 임의의 정점 v_i에서 v_j로의 간선이 존재할 때,
v_i는 v_j의 부모 노드이고,
v_j는 v_i의 자식 노드이다.
Level (레벨)
- Tree에서 한 정점에서 Root까지의 Path상에 존재하는 간선의 개수이다.
- 즉, Root의 Level은 0이다.
Height (높이)
- Tree의 Level의 최댓값이다.
Ordered Tree (순서 트리)
- 각 Level의 노드들에 순서가 부여된 트리이다.
Proof Technique (증명 기법)
Second Principle of Mathematical Induction (제2 수학적 귀납법)
- 몇 개의 Instance(특정 사례)가 True(참)라는 사실들로부터 여러 문장들이 참임을 추론해 내는 기법이다.
- 귀납적 증명 과정은 아래와 같다.
1. 어떤 \(k(k \geq 1)\)에 대해, \(P_1, P_2, \cdots, P_k\) 는 참임을 보인다.
2. \(n \geq k\)인 모든 \(n\)에 대해서 \(P_1, P_2, \cdots, P_n\) 이 참이라 가정하고, \(P_{n+1}\)가 참임을 유도한다.
(\(P_{n+1}\)가 참임을 유도하는 과정은 반드시 \(P_{n}\)이 참이라 가정한 것을 이용하여 증명해야 한다.
다른 수학적 공리를 끌어들여서 증명하면 안된다.)
Inductive Basis = Basis (기저)
- 위의 귀납 증명 과정에서 1번 과정을 "기저"라고 부른다.
Inductive Step (귀납 단계)
- 위의 귀납 증명 과정에서 2번 과정을 "귀납 단계"라고 부른다.
- 위의 귀납 증명 과정에서 문장 \(P_n\)을 \(P_{n+1}\)로 연결시키는 단계이다.
- 귀납 단계에서는 \(P_1, P_2, \cdots, P_n\)이 참이라는 Inductive Assumption(귀납 가정)을 통해,
\(P_{n+1}\) 또한 참임을 보여서 증명한다.
Proof by Contradiction (귀류법)
- 어떤 문장 P가 우선 거짓이라 가정하고, 이 가정을 통해 틀린 결론(모순)이 유도됨을 보여서
처음에 했던, P가 거짓이라 한 가정이 틀렸음을 보여서 P가 참이어야 한다고 결론짓는 증명 방식이다.
Examples
Q. Prove that every amount of postage of 12cents or more can be formed using only 4 cents and 5cents stamps
(12이상의 수는 4와 5의 합으로 나타낼 수 있음을 증명하라.)
pf-1 제 1 수학적 귀납법)
Basis Step)
\(12 = 4 + 4 + 4\)
(P(n)이 참이라 가정하는 과정은 아래와 같다.)
Inductive Step)
Assume \(P(n)\) is true i.e.
\(n = 4i + 5j\)
(\(P(n)\)이 참임을 가정하여, \(P(n+1)\)도 참임을 보이는 과정은 아래와 같다.)
I) \(i \neq 0\)
\(n + 1 = 4(i - 1) + 5(j + 1)\)
(4를 빼고, 5를 더하여 +1을 만든다. 즉, 4센트 동전 하나를 빼고, 5센트 동전 하나를 더한다.)
II) \(i = 0 (j \geq 3\) as \(n \geq 12)\)
\(n + 1 = 4 * 4 + 5(j - 3)\)
(15를 빼고, 16을 더하여 +1을 만든다. 즉, 4센트 동전 4개를 더하고, 5센트 동전 3개를 뺀다.)
pf-2 제 2수학적 귀납법)
Basis step)
\(12 = 4 + 4 + 4\)
\(13 = 4 + 4 + 5\)
\(14 = 4 + 5 + 5\)
\(15 = 5 + 5 + 5\)
Inductive Step)
Let \(n \geq 15\)
Assume \(P(12), \cdots, P(n)\) are true
\(n - 3 = 4i + 5j\)
\(n + 1 = 4(i + 1) + 5j\)
(\(n - 3\)과 \(n + 1\)은 차이가 4이므로, 위와 같이 설정한 것이다. 차이가 5가 나도록 설정해도 증명은 가능하다.)
Reference: An Introduction to Formal Languages and Automata 6E (Peter Linz 저, Jones & Bartlett Learning, 2017)
