이산수학: 벼락치기 팩

공식 모음, 모든 주제의 핵심 풀이 단계, 연습 문제 8개가 들어 있으며 전체 풀이는 맨 뒤에 있습니다.

새 문제 강의로 돌아가기

인쇄 창에서 “PDF로 저장”을 선택하면 기기에 사본을 보관할 수 있습니다.

1공식과 풀이 방법

명제논리와 증명

진리표의 행 수: 2ⁿ
함의: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
함의의 부정: ¬(p → q) ≡ p ∧ ¬q
쌍조건: p ↔ q ≡ (p → q) ∧ (q → p)
드모르간 법칙: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
분배법칙: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
한정자의 부정: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
전건 긍정법, 후건 부정법: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

방법

서로 다른 변수의 개수를 세세요. 진리표는 2ⁿ개의 행을 가지며, 첫 행은 모두 1입니다.
모든 부분식에 각각 열을 하나씩 주고, 안쪽부터 바깥쪽으로 열을 채우세요.
각 연결자의 규칙을 적용하세요. →는 1 → 0일 때만 0이고, ↔는 양쪽이 같을 때 1입니다.
동치는 마지막 열을 행마다 비교하고, 논증은 모든 전제가 1인 행만 살펴보세요.
한정된 문장을 부정하려면 ¬를 안쪽으로 옮기고, ∀와 ∃를 서로 바꾸고, 안쪽 식을 부정하세요.

집합, 관계, 함수

집합 두 개: |A ∪ B| = |A| + |B| − |A ∩ B|
집합 세 개: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
차집합과 여집합: A − B = A ∩ B′, |A′| = |U| − |A|
멱집합과 곱집합: |𝒫(A)| = 2^|A|, |A × B| = |A|·|B|
크기 k인 부분집합: C(n, k) = n!/(k!(n − k)!)
함수 A → B: nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
n개 원소 위의 관계: 2^n²; reflexive 2^{n² − n}; symmetric 2^n(n+1)/2
합성: (g ∘ f)(x) = g(f(x))

방법

벤 다이어그램을 그리고, 집합식에 속하는 영역을 영역별로 판단하세요.
개수를 세는 문제에서는 가운데에서 바깥쪽으로 영역을 채우세요. 모든 집합, 그다음 두 집합씩, 그다음 한 집합, 마지막으로 바깥쪽 순서입니다.
포함·배제 원리로 확인하세요: |A ∪ B| = |A| + |B| − |A ∩ B|.
관계는 모든 쌍에서 각 성질을 검사하고, 성립하지 않으면 반례를 하나 드세요.
함수는 B의 각 원소로 들어오는 화살표를 세세요. 많아야 하나이면 단사이고, 적어도 하나이면 전사입니다.

그래프 이론

악수 보조정리: Σ deg(v) = 2|E|
완전그래프: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
정규그래프: |E| = n·k/2
트리와 포리스트: |E| = n − 1, |E| = n − c
트리의 잎: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
오일러: 회로: 모든 차수가 짝수; 경로: 차수가 홀수인 정점이 정확히 2개
K_n의 해밀턴 회로: (n − 1)!/2
다익스트라 갱신: d(v) = min(d(v), d(u) + w(u, v))
길이 L의 보행: (Mᴸ)_ij

방법

모든 정점의 차수를 적으세요. 차수의 합은 간선 수의 두 배입니다.
오일러 문제에서는 그래프가 연결되어 있는지 확인하고 차수가 홀수인 정점의 수를 세세요.
트리에서는 간선이 n − 1개라는 사실과 악수 보조정리를 사용하세요.
다익스트라에서는 임시 거리 표를 만들고, 매 단계마다 확정되지 않은 정점 중 거리가 가장 작은 정점을 확정하세요.
최소 신장 트리는 간선을 가중치 순으로 정렬해 사이클을 만드는 간선을 건너뛰거나(크루스칼), 시작 정점에서 트리 하나를 키워 가세요(프림).

정수론과 모듈러 연산

나머지가 있는 나눗셈: a = q·n + r, 0 ≤ r < n
유클리드: gcd(a, b) = gcd(b, a mod b)
최소공배수: lcm(a, b) = a·b/gcd(a, b)
역행렬: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
일차 합동식: a·x ≡ b → x ≡ a⁻¹·b (mod n)
오일러 피 함수: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
페르마: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

방법

먼저 모든 수를 n으로 나눈 나머지로 줄이세요. 나머지는 0부터 n − 1 사이에 있습니다.
최대공약수는 유클리드 호제법으로 계속 나누세요. 0이 아닌 마지막 나머지가 최대공약수입니다.
역원은 확장 알고리즘을 실행해 a의 계수를 취하고, 음수이면 n을 더하세요.
a·x ≡ b는 a⁻¹을 곱해서 풀고, 두 합동식은 x = r₁ + m₁k로 써서 합치세요.
거듭제곱은 지수를 이진수로 쓰고 거듭 제곱하세요. RSA에서는 d = e⁻¹ mod φ(n)이고 φ(n) = (p − 1)(q − 1)입니다.

2연습 문제

1.명제논리와 증명보통

((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q))의 진리표 8개 행 중 몇 개에서 참인가? 이 수를 N(이)라 하자.

((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q))

N =

2.명제논리와 증명어려움

전제 c → a; ¬c과(와) 결론 ¬a을(를) 가진 논증은 타당하지 않다. 반례가 되는 진리표의 행을 클릭하세요.

c → a¬c∴ ¬a

1a = 1, c = 1
2a = 1, c = 0
3a = 0, c = 1
4a = 0, c = 0

3.집합, 관계, 함수보통

1학년 학생 56명 중 34명이 수학(M), 33명이 물리(P), 19명이 화학(C)에 합격했다. 19명이 M과 P에, 9명이 M과 C에, 12명이 P와 C에 합격했고 5명이 세 과목 모두에 합격했다. 세 집합 어디에도 속하지 않는 것은 몇 개인가?

|U| = 56

|(M ∪ P ∪ C)′| =

4.집합, 관계, 함수어려움

원소가 3개인 집합 위의 반사적 관계는 몇 개인가? 그 수를 N(이)라 하자.

|X| = 3

N =

5.그래프 이론보통

연결 그래프에 오일러 회로가 있는가, 회로가 아닌 오일러 경로가 있는가, 둘 다 없는가? 답을 클릭하세요.

|V| = 7|E| = 9

1오일러 회로
2오일러 경로, 회로 없음
3둘 다 아님

6.그래프 이론어려움

C에서 출발해 같은 정점으로 돌아오는 길이 3의 닫힌 보행은 몇 개인가? 보행에서는 정점과 간선이 반복될 수 있다. 그 수를 N(이)라 하자.

M = 인접 행렬L = 3

N =

7.정수론과 모듈러 연산보통

x ≡ 6 (mod 8)이고 x ≡ 12 (mod 13)인 가장 작은 양의 정수 x을(를) 구하시오.

x ≡ 6 (mod 8)x ≡ 12 (mod 13)

x =

8.정수론과 모듈러 연산어려움

34x ≡ 46 (mod 82)을(를) 푸시오. 가장 작은 양의 해 x을(를) 구하시오.

34x ≡ 46 (mod 82)

x =

3용액

1.명제논리와 증명

답: N = 6

진리표: 서로 다른 변수가 n개인 식은 참값(1 = 참, 0 = 거짓)의 모든 조합마다 하나씩 2ⁿ개의 행을 가집니다. 안쪽부터 바깥쪽으로 작업하고 모든 부분식에 각각 열을 주세요. ¬a는 값을 뒤집습니다. a ∧ b는 둘 다 1일 때만 1입니다. a ∨ b는 둘 다 0일 때만 0입니다. a → b는 a = 1이고 b = 0일 때만 0입니다. a ↔ b는 양쪽이 같을 때 1입니다.

행별 진리표

p = 1, q = 1, r = 1: ¬q = 0, ¬r = 0, ¬q ∨ ¬r = 0, ¬p = 0, (¬q ∨ ¬r) ∨ ¬p = 0, ¬p ∨ ¬q = 0, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 0

p = 1, q = 1, r = 0: ¬q = 0, ¬r = 1, ¬q ∨ ¬r = 1, ¬p = 0, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 0, r ∨ (¬p ∨ ¬q) = 0, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 0

p = 1, q = 0, r = 1: ¬q = 1, ¬r = 0, ¬q ∨ ¬r = 1, ¬p = 0, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 1, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 1

p = 1, q = 0, r = 0: ¬q = 1, ¬r = 1, ¬q ∨ ¬r = 1, ¬p = 0, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 1, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 1

p = 0, q = 1, r = 1: ¬q = 0, ¬r = 0, ¬q ∨ ¬r = 0, ¬p = 1, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 1, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 1

p = 0, q = 1, r = 0: ¬q = 0, ¬r = 1, ¬q ∨ ¬r = 1, ¬p = 1, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 1, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 1

p = 0, q = 0, r = 1: ¬q = 1, ¬r = 0, ¬q ∨ ¬r = 1, ¬p = 1, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 1, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 1

p = 0, q = 0, r = 0: ¬q = 1, ¬r = 1, ¬q ∨ ¬r = 1, ¬p = 1, (¬q ∨ ¬r) ∨ ¬p = 1, ¬p ∨ ¬q = 1, r ∨ (¬p ∨ ¬q) = 1, ((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)) = 1

값이 1인 행의 수 세기

((¬q ∨ ¬r) ∨ ¬p) ↔ (r ∨ (¬p ∨ ¬q)): 0, 0, 1, 1, 1, 1, 1, 1

N = 6

답

N = 6

2.명제논리와 증명

답: a = 1, c = 0

한정자와 논증: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x). 부정을 안쪽으로 옮기고, 지나가는 모든 한정자를 바꾸고, ¬(a → b) ≡ a ∧ ¬b 같은 명제 논리 법칙으로 안쪽 식을 부정하세요. 모든 전제가 1인 모든 행에서 결론이 1이면 논증이 타당합니다. 전제는 참인데 결론이 거짓인 행이 하나라도 있으면 그것이 반례이며 그 논증은 타당하지 않음을 보여 줍니다.

행별 전제와 결론

a = 1, c = 1: 1 0 | 0

a = 1, c = 0: 1 1 | 0

a = 0, c = 1: 0 0 | 1

a = 0, c = 0: 1 1 | 1

반례

a = 1, c = 0

답

a = 1, c = 0

이런 형식의 논증은 타당한 규칙처럼 보이지만, 행 하나만으로 그렇지 않음을 보일 수 있습니다.

3.집합, 관계, 함수

답: |(M ∪ P ∪ C)′| = 5

집합과 벤 다이어그램: A ∪ B는 A 또는 B(또는 둘 다)에 속하는 원소, A ∩ B는 둘 다에 속하는 원소, A − B는 A의 원소 중 B에 속하지 않는 원소이고, 여집합 A′는 U의 원소 중 A에 속하지 않는 모든 것입니다. 벤 다이어그램에서 모든 집합식은 영역들의 합집합이므로 영역별로 세세요. 포함·배제: |A ∪ B| = |A| + |B| − |A ∩ B|, 그리고 |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

가운데와 쌍

M ∩ P ∩ C: 5

M ∩ P 만: 19 − 5 = 14

M ∩ C 만: 9 − 5 = 4

P ∩ C 만: 12 − 5 = 7

한 집합씩

M 만: 34 − 14 − 4 − 5 = 11

P 만: 33 − 14 − 7 − 5 = 7

C 만: 19 − 4 − 7 − 5 = 3

답

|M ∪ P ∪ C| = 51

|(M ∪ P ∪ C)′| = 56 − 51 = 5

답

|(M ∪ P ∪ C)′| = 5

4.집합, 관계, 함수

답: N = 64

관계: 집합 X 위의 관계 R은 순서쌍 (x, y)의 집합입니다. X의 모든 x에 대해 (x, x) ∈ R이면 R은 반사적, (x, y) ∈ R이면 항상 (y, x) ∈ R도 성립하면 대칭적, (x, y)와 (y, x)가 모두 R에 있는 경우가 x = y일 때뿐이면 반대칭적, R에 (x, y)와 (y, z)가 있으면 (x, z) ∈ R이어야 하면 추이적입니다. 동치 관계는 반사적이고 대칭적이며 추이적이고, X를 서로소인 류로 나눕니다.

자유로운 선택 세기

N = 2^{3² − 3} = 64

답

N = 64

5.그래프 이론

답: 오일러 경로, 회로 없음

오일러, 해밀턴, 트리: 연결 그래프는 모든 정점의 차수가 짝수이면 오일러 회로(모든 간선을 한 번씩 지나 출발점으로 돌아옴)를 가지고, 차수가 홀수인 정점이 정확히 두 개이면 회로가 아닌 오일러 경로를 가집니다. 이 경로는 한 홀수 정점에서 다른 홀수 정점까지 이어집니다. 해밀턴 회로는 모든 정점을 한 번씩 방문하며, K_n에는 (n − 1)!/2개가 있습니다. 정점이 n개인 트리는 간선이 n − 1개이고, 간선이 m개인 연결 그래프는 m − n + 1개의 간선을 제거한 뒤에도 신장 트리를 유지합니다.

차수

deg(A) = 1, deg(B) = 4, deg(C) = 2, deg(D) = 3, deg(E) = 4, deg(F) = 2, deg(G) = 2

홀수 정점

A, D → 2

오일러 경로, 회로 없음

답

오일러 경로, 회로 없음

오일러 경로는 한 홀수 정점에서 시작해 다른 홀수 정점에서 끝납니다.

6.그래프 이론

답: N = 4

차수: 정점의 차수는 그 정점에 닿는 간선의 수입니다. 모든 간선은 양 끝이 있으므로 차수의 합은 간선 수의 두 배입니다: Σ deg(v) = 2|E|(악수 보조정리). 따라서 차수가 홀수인 정점의 수는 짝수입니다. K_n은 간선이 n(n − 1)/2개이고, 정점이 n개인 k-정규그래프는 nk/2개이며, 정점이 n개인 트리는 간선이 n − 1개입니다.

인접 행렬

A: 0 1 1 0 0

B: 1 0 1 0 1

C: 1 1 0 0 1

D: 0 0 0 0 1

E: 0 1 1 1 0

한 걸음 더

(M³)_CC = 1·1 + 2·1 + 3·0 + 1·0 + 1·1 = 4

답

N = 4

7.정수론과 모듈러 연산

답: x = 38

역원과 합동식: a는 gcd(a, n) = 1일 때, 그리고 그때에만 n을 법으로 하는 역원을 가집니다. 확장 유클리드 알고리즘은 1 = s·n + t·a로 쓰고, 그러면 a⁻¹ ≡ t (mod n)입니다. gcd(a, n) = 1인 합동식 a·x ≡ b (mod n)의 해는 x ≡ a⁻¹·b입니다. 법이 서로소인 두 합동식 x ≡ r₁ (mod m₁)과 x ≡ r₂ (mod m₂)는 m₁·m₂를 법으로 해가 하나 있습니다(중국인의 나머지 정리). 오일러 φ(n)은 1부터 n까지의 수 중 n과 서로소인 수의 개수입니다: φ(n) = n·∏(1 − 1/p).

첫 번째 합동식

x = 6 + 8k

두 번째 합동식

6 + 8k ≡ 12 (mod 13) → 8k ≡ 6 (mod 13)

k ≡ 5·6 ≡ 4 (mod 13)

결과

x = 6 + 8·4 = 38

x = 38

검산: 38 mod 8 = 6, 38 mod 13 = 12

답

x = 38

8.정수론과 모듈러 연산

답: x = 11

gcd로 나누기

gcd(34, 82) = 2

17x ≡ 23 (mod 41)

줄인 합동식 풀기

17⁻¹ ≡ 29 (mod 41) → x ≡ 11 (mod 41)

82을(를) 법으로 한 해

x ∈ {11, 52}

x = 11

답

x = 11

ExamProblems · examproblems.com/courses/discrete-mathematics