이산수학
1. 집합론 (Set Theory)
기본 개념
| 기호 |
의미 |
예시 |
| ∈ |
원소 속함 |
1 ∈ {1, 2, 3} |
| ∉ |
원소 속하지 않음 |
4 ∉ {1, 2, 3} |
| ⊆ |
부분집합 |
{1,2} ⊆ {1,2,3} |
| ∅ |
공집합 |
원소가 없는 집합 |
| |A| |
집합의 크기(원소 수) |
|{1,2,3}| = 3 |
집합 연산
| 연산 |
기호 |
설명 |
| 합집합 |
A ∪ B |
A 또는 B에 속하는 원소 |
| 교집합 |
A ∩ B |
A와 B 모두에 속하는 원소 |
| 차집합 |
A - B |
A에 속하고 B에 속하지 않는 원소 |
| 여집합 |
Aᶜ |
전체집합에서 A를 제외한 원소 |
포함-배제 원리
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |B∩C| - |A∩C| + |A∩B∩C|
2. 명제 논리
논리 연산자
| 연산 |
기호 |
설명 |
| 논리곱 (AND) |
p ∧ q |
둘 다 참일 때만 참 |
| 논리합 (OR) |
p ∨ q |
하나라도 참이면 참 |
| 부정 (NOT) |
¬p |
참↔거짓 반전 |
| 배타적 논리합 (XOR) |
p ⊕ q |
둘의 값이 다를 때 참 |
| 조건문 |
p → q |
p가 참이고 q가 거짓일 때만 거짓 |
| 쌍조건문 |
p ↔ q |
둘 다 같을 때 참 |
진리표 (AND / OR / XOR)
| p |
q |
p∧q |
p∨q |
p⊕q |
| T |
T |
T |
T |
F |
| T |
F |
F |
T |
T |
| F |
T |
F |
T |
T |
| F |
F |
F |
F |
F |
조건문 관련 명제
| 명제 |
형태 |
관계 |
| 원래 명제 |
p → q |
|
| 역 |
q → p |
원래와 동치 아님 |
| 이 |
¬p → ¬q |
원래와 동치 아님 |
| 대우 |
¬q → ¬p |
원래와 동치 |
3. 부울 대수 (Boolean Algebra)
논리 회로 설계의 수학적 기반입니다.
기본 법칙
| 법칙 |
AND |
OR |
| 항등 법칙 |
A·1 = A |
A+0 = A |
| 영 법칙 |
A·0 = 0 |
A+1 = 1 |
| 보수 법칙 |
A·Ā = 0 |
A+Ā = 1 |
| 멱등 법칙 |
A·A = A |
A+A = A |
| 이중 부정 |
──A = A |
|
드모르간 법칙 (De Morgan's Law)
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
논리 게이트 변환, 디지털 회로 최소화에 활용
4. 그래프 이론 기초
기본 용어
| 용어 |
설명 |
| 정점(Vertex/Node) |
그래프의 점 |
| 간선(Edge) |
정점을 연결하는 선 |
| 차수(Degree) |
정점에 연결된 간선 수 |
| 경로(Path) |
정점을 거치는 이동 경로 |
| 사이클(Cycle) |
시작과 끝이 같은 경로 |
그래프 종류
| 종류 |
설명 |
| 무방향 그래프 |
간선에 방향 없음 |
| 방향 그래프(유향) |
간선에 방향 있음 |
| 가중치 그래프 |
간선에 가중치(비용) 있음 |
| 완전 그래프 |
모든 정점이 연결됨 |
| 트리 |
사이클 없는 연결 그래프 |
| DAG |
방향 있고 사이클 없는 그래프 |
주요 정리
- 오일러 경로: 모든 간선을 한 번씩 지나는 경로 (차수가 홀수인 정점이 0개 또는 2개)
- 해밀턴 경로: 모든 정점을 한 번씩 지나는 경로
- 악수 보조정리: 모든 정점의 차수의 합 = 간선 수 × 2
시험 포인트
- 집합 포함-배제: |A∪B| = |A| + |B| - |A∩B|
- XOR: 두 값이 다를 때 참
- 대우: p→q 와 ¬q→¬p 는 동치
- 드모르간: ¬(A∧B) = ¬A∨¬B, ¬(A∨B) = ¬A∧¬B
- 조건문 p→q: p가 참, q가 거짓일 때만 거짓
- 트리: 정점 n개, 간선 n-1개, 사이클 없음